【数据结构】C语言实现单链表基本操作_设立尾指针的单循环链表的十二个基本操作c语言要有菜单-程序员宅基地
【数据结构】C语言实现单链表基本操作
实现单链表的基本操作并测试
1、定义单链表的存储结构
//单链表的存储结构
typedef struct LNode
{
ElemType data;
struct LNode *next; //next指向自身类型struct LNode *的指针
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
2、初始化单链表
建立一个只有头结点的空链表。
//初始化单链表
/*生成新结点作为头结点，头指针L指向头结点
*头结点的指针域设置为空NULL
*/
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(LNode)); //生成新结点作为头结点并指向头指针L
(*L)->next = NULL; //头结点的指针域设置空
return OK;
}
3、头插法建立链表
由于前期卡在了这，这里是另一篇记录文章，简单描述了一下整个头插法过程。
/*头插法（前插法）
*/
void CreateList_H(LinkList *L,int n) //形参L 是指向inkList类型的指针变量指针（用于指向新开辟储存单元），逆序储存n个元素值
{
*L = (LinkList)malloc(sizeof(LNode)); //为头结点开辟储存空间，并使头指针指向头节点
(*L)->next = NULL; //含头结点的空链表
int i; //元素数量计数
printf("请输入%d个链表元素:",n);
for(i=0;i<n;i++) //循环输入元素
{
LNode *p=(LinkList)malloc(sizeof(LNode)); //为新结点开辟空间并令指针指向该地址
scanf("%d",&p->data); //向新结点数据域输入数据
p->next = (*L)->next; //头结点指针域的值（即新结点后继结点地址）赋给新结点指针域进行连接
(*L)->next = p; //指针域指针连接顺序不可颠倒 新结点地址赋值给头结点指针域进行连接
}
}
4、尾插法建立单链表。
/*尾插法（后插法）
*/
void CreateList_R(LinkList *L,int n)
{
LNode *r;
*L = (LinkList)malloc(sizeof(LNode)); //头指针指向新开辟的头结点
(*L)->next = NULL; //创建空链表，指针域设置为NULL
r = (*L); //尾指针指向头结点
int i;
printf("请输入%d个链表元素:",n);
for(i=0;i<n;i++)
{
LNode *p = (LinkList)malloc(sizeof(LNode)); //为新结点p开辟储存空间
scanf("%d",&p->data); //为新结点输入数据
p->next = NULL; //新结点作为尾结点，其指针域设置为NULL
r->next = p; //尾指针指向的结点的指针域设置为p结点的地址进行连接
r = p; //尾指针向前移动，指向新的尾结点
}
}
5、判断单链表是否为空。
/*判断链表是否为空
* 思路：判断头结点指针域是否为空
*/
Status ListEmpty(LinkList L)
{
if(L->next) return FALSE; //非空 0
return TRUE; //空 1
}
6、输出单链表长度。
/*求链表长度
* 思路：从首元结点开始，依次计数所有结点，长度不包括头结点
*/
Status ListLength(LinkList L)
{
LNode *p;
p = L->next; //从首元结点开始
int len = 0;
while(p) //循环条件设置为非空
{
++len; //第一次循环开始，首元结点非空则长度为1，之后循环都是指向下一个结点再判断是否为空再+1
p = p->next; //指向下一结点
}
return len; //返回长度
}
7、取值
按结点位置进行取值
//取值
Status GetElem(LinkList L,int i,ElemType *e) //形参L为指向头结点的指针
{
int j=1;
LNode *p; //定义指向LNode类型的指针变量
p=L->next; //p指向首元结点
while(p&&j<i) //循环条件为p非空和取值位置i合法（大于1），i等于1相当于取首元结点的data值
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR; //i不合法即返回ERROR，p为空（可能空表或是i值超过表长即i>n) i<=0也是不合法
*e = p->data;
return OK;
}
8、按值查找
即输入结点所储存数据值进而输出地址。
/*按值查找，返回元素位置
* 1、从首元结点开始找
* 2、直到找到结点data值等于e或者超过表长指向空值
* 3、最后返回p的指针地址值（数据域等于data的指针值或者NULL）
*/
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p;
p = L->next;
while(p && p->data!=e)
p=p->next;
return p;
}
9、单链表插入结点
/*链表插入元素
* 1、寻找i位置前驱结点
* 2、判断前驱结点地址以及插入位置是否合理
* 3、开辟新结点储存单元
* 4、新结点数据域赋值插入元素值，指针域指向前驱结点下一个结点地址
* 5、将前驱结点指针域指向新结点地址
*/
Status ListInsert(LinkList L,int i,ElemType e) //输入插入位置i、同类型ElemType元素值
{
LNode *p,*s; //定义LNode类型指针变量
p = L; //p指向L头结点
int j = 0; //定义计数
while(p && j<i-1) //循环条件 p非空和j小于i-1（i的前驱结点位置）一般情况下：j=i-1结束循环
{
p = p->next; //p继续指向下一个结点
j++; //位置数累计
}
if(!p || j>i-1) return ERROR; //p为前驱结点的指针值（地址），为NULL则超链表长；j>i-1表示位置小于0
s = (LinkList)malloc(sizeof(LNode)); //为新插入结点开辟空间并指针s指向该储存单元
s->data = e; //将插入数据赋值给储存单元数据域
s->next = p->next; //新结点指针域指向下一个结点ai
p->next = s; //前去结点指针域指向新结点
return OK;
}
10、删除结点
/*链表删除元素
* 1、找到前驱结点
* 2、判断前驱结点指针域和前驱结点位置是否合理
* 3、将前驱结点指针域指向的下一个结点的指针域赋值给前驱结点的指针域，形成跨元素连接
* 4、最后释放内存
*/
Status ListDelete(LinkList L,int i)
{
LNode *p,*q;
p = L; //指针p指向头结点
int j=0;
while(p->next && j<i-1) //判断前驱结点指针域是否为空和前驱位置值
{
p = p->next;
j++;
}
if(!(p->next) || j>i-1) return ERROR; //判断删除位置合理与否：前驱结点指针域是否为空，为空证明超链长了
q = p->next;
p->next = q->next; //前驱结点指针域指向的指针域的值 赋给 前驱结点的指针域 有点向二重指针的感觉
free(q); //释放空间
return OK;
}
11、清空链表
该链表仍存在，只是头结点的指针域的值为NULL
/*清空链表
*依次释放所有结点，将头结点指针域设置为空
*/
Status ClearList(LinkList L)
{
LNode *p,*q; //指针p所指结点释放内存，指针q则是记录下一个结点（辅助作用）
p = L->next; //一开始将p指向首元结点
while(p) //循环条件是p非空
{
q=p->next; //将q指向下一个结点
free(p); //释放p
p=q; //将p和q同步
}
L->next = NULL; //最后将头结点指针域设置为空
return OK;
}
12、销毁链表
该链表彻底删除，最后头指针指向NULL。
/*销毁单链表
* 思路：从头结点开始，依次释放所有结点
*/
Status DestroyList(LinkList L)
{
LNode *p; //定义辅助结点p
while(L) //循环条件为非空
{
p = L; //p指向当前的L
L = L->next; //L指向下一个结点，相当于L++
free(p); //释放辅助结点p所指的结点
}
return OK;
}
13、遍历链表。
//遍历链表
void print(LinkList L)
{
LNode *p;
p = L->next; //p的值为首元结点地址值，进而一开始就指向首元结点
while(p) //循环条件是下一个结点地址为空结束
{
printf("%d ",p->data);
p = p->next; //继续指向下一个结点
}
}
最后，附上所有代码（含main函数测试代码）
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
//单链表的存储结构
typedef struct LNode
{
ElemType data;
struct LNode *next; //next指向自身类型struct LNode *的指针
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
//初始化单链表
/*生成新结点作为头结点，头指针L指向头结点
*头结点的指针域设置为空NULL
*/
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(LNode)); //生成新结点作为头结点并指向头指针L
(*L)->next = NULL; //头结点的指针域设置空
return OK;
}
//取值
Status GetElem(LinkList L,int i,ElemType *e) //形参L为指向头结点的指针
{
int j=1;
LNode *p; //定义指向LNode类型的指针变量
p=L->next; //p指向首元结点
while(p&&j<i) //循环条件为p非空和取值位置i合法（大于1），i等于1相当于取首元结点的data值
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR; //i不合法即返回ERROR，p为空（可能空表或是i值超过表长即i>n) i<=0也是不合法
*e = p->data;
return OK;
}
//遍历链表
void print(LinkList L)
{
LNode *p;
p = L->next; //p的值为首元结点地址值，进而一开始就指向首元结点
while(p) //循环条件是下一个结点地址为空结束
{
printf("%d ",p->data);
p = p->next; //继续指向下一个结点
}
}
/*判断链表是否为空
* 思路：判断头结点指针域是否为空
*/
Status ListEmpty(LinkList L)
{
if(L->next) return FALSE; //非空 0
return TRUE; //空 1
}
/*销毁单链表
* 思路：从头结点开始，依次释放所有结点
*/
Status DestroyList(LinkList L)
{
LNode *p; //定义辅助结点p
while(L) //循环条件为非空
{
p = L; //p指向当前的L
L = L->next; //L指向下一个结点，相当于L++
free(p); //释放辅助结点p所指的结点
}
return OK;
}
/*清空链表
*依次释放所有结点，将头结点指针域设置为空
*/
Status ClearList(LinkList L)
{
LNode *p,*q; //指针p所指结点释放内存，指针q则是记录下一个结点（辅助作用）
p = L->next; //一开始将p指向首元结点
while(p) //循环条件是p非空
{
q=p->next; //将q指向下一个结点
free(p); //释放p
p=q; //将p和q同步
}
L->next = NULL; //最后将头结点指针域设置为空
return OK;
}
/*求链表长度
* 思路：从首元结点开始，依次计数所有结点，长度不包括头结点
*/
Status ListLength(LinkList L)
{
LNode *p;
p = L->next; //从首元结点开始
int len = 0;
while(p) //循环条件设置为非空
{
++len; //第一次循环开始，首元结点非空则长度为1，之后循环都是指向下一个结点再判断是否为空再+1
p = p->next; //指向下一结点
}
return len; //返回长度
}
/*按值查找，返回元素位置
* 1、从首元结点开始找
* 2、直到找到结点data值等于e或者超过表长指向空值
* 3、最后返回p的指针地址值（数据域等于data的指针值或者NULL）
*/
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p;
p = L->next;
while(p && p->data!=e)
p=p->next;
return p;
}
/*链表插入元素
* 1、寻找i位置前驱结点
* 2、判断前驱结点地址以及插入位置是否合理
* 3、开辟新结点储存单元
* 4、新结点数据域赋值插入元素值，指针域指向前驱结点下一个结点地址
* 5、将前驱结点指针域指向新结点地址
*/
Status ListInsert(LinkList L,int i,ElemType e) //输入插入位置i、同类型ElemType元素值
{
LNode *p,*s; //定义LNode类型指针变量
p = L; //p指向L头结点
int j = 0; //定义计数
while(p && j<i-1) //循环条件 p非空和j小于i-1（i的前驱结点位置）一般情况下：j=i-1结束循环
{
p = p->next; //p继续指向下一个结点
j++; //位置数累计
}
if(!p || j>i-1) return ERROR; //p为前驱结点的指针值（地址），为NULL则超链表长；j>i-1表示位置小于0
s = (LinkList)malloc(sizeof(LNode)); //为新插入结点开辟空间并指针s指向该储存单元
s->data = e; //将插入数据赋值给储存单元数据域
s->next = p->next; //新结点指针域指向下一个结点ai
p->next = s; //前去结点指针域指向新结点
return OK;
}
/*链表删除元素
* 1、找到前驱结点
* 2、判断前驱结点指针域和前驱结点位置是否合理
* 3、将前驱结点指针域指向的下一个结点的指针域赋值给前驱结点的指针域，形成跨元素连接
* 4、最后释放内存
*/
Status ListDelete(LinkList L,int i)
{
LNode *p,*q;
p = L; //指针p指向头结点
int j=0;
while(p->next && j<i-1) //判断前驱结点指针域是否为空和前驱位置值
{
p = p->next;
j++;
}
if(!(p->next) || j>i-1) return ERROR; //判断删除位置合理与否：前驱结点指针域是否为空，为空证明超链长了
q = p->next;
p->next = q->next; //前驱结点指针域指向的指针域的值 赋给 前驱结点的指针域 有点向二重指针的感觉
free(q); //释放空间
return OK;
}
/*头插法（前插法）
*/
void CreateList_H(LinkList *L,int n) //形参L 是指向inkList类型的指针变量指针（用于指向新开辟储存单元），逆序储存n个元素值
{
*L = (LinkList)malloc(sizeof(LNode)); //为头结点开辟储存空间，并使头指针指向头节点
(*L)->next = NULL; //含头结点的空链表
int i; //元素数量计数
printf("请输入%d个链表元素:",n);
for(i=0;i<n;i++) //循环输入元素
{
LNode *p=(LinkList)malloc(sizeof(LNode)); //为新结点开辟空间并令指针指向该地址
scanf("%d",&p->data); //向新结点数据域输入数据
p->next = (*L)->next; //头结点指针域的值（即新结点后继结点地址）赋给新结点指针域进行连接
(*L)->next = p; //指针域指针连接顺序不可颠倒 新结点地址赋值给头结点指针域进行连接
}
}
/*尾插法（后插法）
*/
void CreateList_R(LinkList *L,int n)
{
LNode *r;
*L = (LinkList)malloc(sizeof(LNode)); //头指针指向新开辟的头结点
(*L)->next = NULL; //创建空链表，指针域设置为NULL
r = (*L); //尾指针指向头结点
int i;
printf("请输入%d个链表元素:",n);
for(i=0;i<n;i++)
{
LNode *p = (LinkList)malloc(sizeof(LNode)); //为新结点p开辟储存空间
scanf("%d",&p->data); //为新结点输入数据
p->next = NULL; //新结点作为尾结点，其指针域设置为NULL
r->next = p; //尾指针指向的结点的指针域设置为p结点的地址进行连接
r = p; //尾指针向前移动，指向新的尾结点
}
}
//测试函数
int main()
{
LinkList L; //定义指向LNode类型的指针变量L
ElemType *e;
int num,status,num_1,n,i; //num:操作序号 status：函数状态值 num_1:赋值操作序号 n:插入的元素 i:插入链表位置序号
printf("****************单链表基本操作测试*******************\n");
printf(" 1-初始化空链表 2-建立链表\n");
printf(" 3-链表是否空 4-输出链表长度\n");
printf(" 5-取值 6-按值查找\n");
printf(" 7-插入元素 8-删除元素\n");
printf(" 9-清空链表 10-销毁链表\n");
printf(" 11-遍历链表 12退出测试系统\n");
printf("***************单链表基本操作测试********************\n");
while(1)
{
printf("\n请输入操作序号:");
scanf("%d",&num);
switch (num)
{
case 1:
{
status = InitList(&L);
if(status)printf("链表初始化已完成～\n");
else printf("链表初始化失败～\n");
};
break;
case 2:
{
printf("\n***********选择赋值方式***************\n");
printf(" 1-头插法 2-尾插法\n");
printf("选择赋值方式:");
scanf("%d",&num_1);
printf("为多少个元素赋值:");
scanf("%d",&n);
if(num_1==1) CreateList_H(&L,n);
else if(num_1==2) CreateList_R(&L,n);
else printf("方式选择有误～\n");
}; break;
case 3:
{
if(ListEmpty(L)) printf("链表为空～\n");
else printf("链表非空～\n");
};break;
case 4:
{
status = ListLength(L);
printf("链表长度为%d\n",status);
};break;
case 5:
{
printf("请输入取出元素位置:");
scanf("%d",&i);
GetElem(L,i,e);
printf("位置%d元素值为%d\n",i,*e);
};break;
case 6:
{
LNode *p;
printf("请输入目标元素值:");
scanf("%d",&n);
p=LocateElem(L,n);
printf("该值指针地址为:%d\n",p);
};break;
case 7:
{
printf("请输入需插入的目标元素:");
scanf("%d",&n);
printf("请输入插入目标位置:");
scanf("%d",&i);
ListInsert(L,i,n);
};break;
case 8:
{
printf("请输入删除结点位置：");
scanf("%d",&i);
if(ListDelete(L,i)) printf("删除操作已完成～\n");
};break;
case 9:
{
if(ClearList(L)) printf("链表已清空～\n");
else printf("清空操作失败～\n");
};break;
case 10:
{
if(DestroyList(L)) printf("链表已销毁～\n");
else printf("销毁操作失败～\n");
};break;
case 11:
{
printf("当前链表:");
print(L);
printf("\n");
};break;
case 12:
{
printf("成功退出测试系统~\n");
exit(1);
};break;
default: printf("输入操作序号有误～\n");
}
}
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
基于惯性主轴方向的CATIA包围盒(Bounding Box)_catia bounding box-程序员宅基地
文章浏览阅读3k次，点赞4次，收藏13次。基于惯性主轴方向的CATIA包围盒(Bounding Box)通俗地说，对象的包围盒(Bounding Box)指的是一个最小的能将对象包含在内的长方体盒子。在机械设计中，零件（部件）的包围盒可用于确定是否和其他零件在装配中发生干涉，或者用于确定加工该零件所需的最小材料尺寸。在CATIA中，使用惯量测量（Mearure Inertia)工具可以直接测量得到3D模型的包围盒，这是一种确定对象包围盒尺寸的常用工具。惯量测量工具所测的包围盒等尺寸为相对于坐标系方向的包围盒，但有时候我们希望测得相对于惯性主轴的_catia bounding box
线程 vs 进程_线程vs进程-程序员宅基地
文章浏览阅读1.8w次，点赞15次，收藏87次。进程与线程的区别是很重要的一个知识点，也是面试中经常问到的。网上转载博客痕迹明显，且千篇一律。我简单提取下，记录下来，希望能帮到你。另外在 LeetCode 上也有关于此问题的讨论，可以直接浏览“Read more” 部分。引入进程之前–多道程序设计概述多道程序设计技术是操作系统最早引入的技术，它的设计思想是允多个程序同时进入内存并运行，其目的是为了CPU的利用率，进而提高系统效率。特点多道程序设_线程vs进程
pydev连接数据库mysql布署及python连接mysql问题及Python学习_those products with missing-程序员宅基地
文章浏览阅读2.2k次。 mysql本地、远程连接及'mysql' 不是内部或外部命令错误 - 程序员宅基地 https://blog.csdn.net/sjpljr/article/details/80115364Python3 MySQL 数据库连接 | 菜鸟教程(好用！) http://www.runoob.com/python3/python3-mysql.html安装：pip install p..._those products with missing
Python类里的__init__方法函数，Python类的构造函数_python中构造函数-程序员宅基地
文章浏览阅读1w次。如果某类里没有__init__方法函数，通过类名字创建的实例对象为空，切没有初始化；如果有此方法函数，通常作为类的第一个方法函数，有点像C++等语言里的构造函数。——————————————————————————————————————class Ca: def __init__(self, v): # 注意前后各两个下划线 sel_python中构造函数
Conflux人物志-杨光博士：徜徉在密码学中的“宝藏男孩”-程序员宅基地
文章浏览阅读531次。说起密码学，大多数人最先联想到的可能是波诡云谲的谍战，为了取得对方密码不惜一切代价的特工；或许也有人会想到二战时期的布莱奇利公园，年轻的图灵带领着一群天才数学家成功破解了..._密码专家阳光
面向对象-静态变量与单例设计模式_单例模式,使用static 变量-程序员宅基地
文章浏览阅读449次。1. Static1.1 什么是Staticstatic：静态的static可以用来修饰：方法、属性、代码块、内部块1.2 Static的使用1.2. 1static修饰属性：静态变量;属性：按是否使用static修饰，又分为静态变量 vs 非静态变量实例变量：当我们创建了类的多个对象，每个对象都独立的拥有一套类中的非静态属性，当修改其中一个对象中的非静态属性时，不会导致其它对象中同样的属性值修改静态变量：我们创建了类的多个对象，多个对象共享同一个静态变量，当通过某一个对_单例模式,使用static 变量
随便推点
Java将数据按列写入Excel并设置格式（字体、背景色、自动列宽、对齐方式等）-程序员宅基地
文章浏览阅读3.3k次，点赞5次，收藏6次。本文使用jxl.jar工具类库将数据按列写入Excel并设置格式（字体、背景色、自动列宽、对齐方式等）。
Android中使用代码开关GPS、移动网络(GPRS)、WiFi_android 网络开关工具 github-程序员宅基地
文章浏览阅读1.1w次。以下方法在2.1中测试成功。理论上2.1以上应该也可以。不过2.1以后的Android版本中已经有提供了相关方法，详见android.provider.Settings.Secure类。记得在AndroidManifest.xml中声明相关权限： android:name="android.permission.ACCESS_NETWORK_STATE"/>_android 网络开关工具 github
go技术日报--2020-05-29_技术日报接口-程序员宅基地
文章浏览阅读745次。go 语言中文网(每日资讯)_2020-05-29一、Go 语言中文网Go 语言之父：拿过奥运银牌，发明过航天望远镜，想用 Go 语言解放程序员！Go Web 开发如何优雅的包含静态资源文件？Go：从 context 源码领悟接口的设计Go 异常处理详解Go Redis 客户端源码阅读（3）协程间的通信二、亚军进化史Go 技术日报（2020-05-28）三、xueyuanjunGo 语言 Web 编程系列（十六）—— 设置、读取和删除 Cookie四、 _技术日报接口
vs2013+NetCDF二维数据的读取方法-程序员宅基地
文章浏览阅读137次，点赞9次，收藏4次。说明：根据自己的实际情况请参考使用，更多问题请参考博客中的其他文章。环境：win7+vs2013+NetCDF4.4.2。
风险评估在应对网络安全威胁中扮演着重要的角色-程序员宅基地
文章浏览阅读771次，点赞15次，收藏8次。是从风险管理角度，运用科学的方法和手段，系统地分析信息系统所面临的威胁及其存在的脆弱性，评估安全事件一旦发生可能造成的危害程度，提出有针对性的防护对策和整改措施，防范和化解信息安全风险，将风险控制在可接受的水平，最大限度地保障信息安全提供科学依据。——风险对策会付出一定代价，需将不同风险对策的适用性与不同风险的后果结合考虑，使不同风险选择适宜的风险对策，形成高效的风险对策组合。：涉及多个国家和地区的业务运营，面临政治风险、汇率风险、文化差异等复杂因素，风险评估有助于企业更好地适应不同环境并降低潜在风险。
维基百科（Wikipedia）网址_维基中文百科官网入口-程序员宅基地
文章浏览阅读10w+次，点赞103次，收藏492次。分享几个维基百科网址镜像，服务器在国内，可以直接访问，并且打开速度比较快，因镜像网址的原因，搜索的结果也几乎相同，若无法访问国外的维基百科，那就来试试这个吧。_维基中文百科官网入口