数据结构与算法 | 单链表的基本操作

发布于:2021-10-24 06:26:20


1024G 嵌入式资源大放送!包括但不限于C/C++、单片机、Linux等。关注微信公众号【嵌入式大杂烩】,回复1024,即可免费获取!



线性表的存储结构有顺序存储结构(顺序表)和链式存储结构(链表)两种。顺序表在之前的博客有介绍过,不明白的朋友可查看:静态分配顺序表的基本操作及动态分配顺序表的基本操作。相对于顺序表来说,链表稍微难一些,本人花了两天的时间认真查看了一些资料,终于大致明白了一些东西。现在做一些总结,分享给大家,有错误的地方欢迎大家指正。


一、相关概念术语

1、链表结点由数据域(存放本身信息)和指针域(指向后继结点的指针)构成。如下图所示:



? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图1 结点的构成


其C语言定义可表示为:


typedef struct LNode
{
int data; //data中存放结点数据域(默认是int型)
struct LNode *next; //指向后继结点的指针
}LNode;

2、头结点:在开始结点之前的结点(可有可无)。其值域不包含任何信息。


3、开始结点:第一个元素所在的结点。


4、头指针:永远指向链表中第一个结点的位置(如果链表有头结点,头指针指向头结点;否则,头指针指向开始结点)。


5、单链表



? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??图2 带头结点的单链表


(1)带头结点的单链表:头指针head指向头结点。头指针head始终不等于NULL,head->next等于NULL的时候链表为空。


(2)不带头结点的单链表:头结点head指向开始结点,即图2中的a1,当head等于NULL时链表为空。


6、头结点和头指针的区别:头指针是一个指针,头指针指向链表的第一个结点(如果链表有头结点,头指针指向头结点;否则,


头指针指向开始结点);头结点是一个实际存在的点,它包含有数据域和指针域。两者在程序上的直接体现就是:头指针至声明


而没有分配存储空间,头结点进行了声明并分配了一个结点的实际物理内存。


?


二、代码部分

?


1、单链表结点定义


typedef struct LNode
{
int data; //data中存放结点数据域(默认是int型)
struct LNode *next; //指向后继结点的指针
}LNode;

2、单链表的创建


单链表的创建有两种方法,即头插法和尾插法。原理如下图所示:



? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图3 头插法与尾插法


(1)头插法创建单链表(生成的链表是逆序的)的代码如下:


LNode *HeadCreateList(int len)
{
LNode *L = (LNode*)malloc(sizeof(LNode)); //创建一个头结点
LNode *temp = L;//声明一个中间变量,指向头结点,用于遍历链表(曾因没有这个中间变量而出错)
temp->next = NULL; //该链表此刻只带头结点

for(int i=1;i<=len;i++) //循环申请len个结点来接收scanf得到的元素
{
LNode *p = (LNode*)malloc(sizeof(LNode)); //生成新结点
scanf("%d",&p->data); //用新申请的结点来接收scanf得到的元素
/* 以下两条语句是头插法的关键步骤,与本工程"Insert"函数原理一样 */
p->next = temp->next; //新结点的next指针指向开始结点
temp->next = p; //头结点的next指针指向新结点
}

return (LNode*)L;
}

程序运行结果如下:



?


(2)尾插法创建单链表(生成的链表是顺序的)的代码如下:


LNode *TailCreateList(int len)
{
LNode *L = (LNode*)malloc(sizeof(LNode)); //创建一个头结点
LNode *temp = L;//声明一个中间变量,指向头结点,用于遍历链表(曾因没有这个中间变量而出错)
temp->next = NULL;//该链表此刻只带头结点

for(int i=1;i<=len;i++) //循环申请len个结点来接收scanf得到的元素
{
LNode *p = (LNode*)malloc(sizeof(LNode)); //生成新结点
scanf("%d",&p->data); //用新申请的结点来接收scanf得到的元素
/* 以下两条语句是尾插法的关键步骤 */
temp->next = p; //用来接纳新结点
temp = p; //指向终端结点,以便于接纳下一个到来的结点,此语句也可以改为"L = L->next"
}
temp->next = NULL; //此刻所有元素已经全装入链表L中,L的终端结点的指针域置为NULL

return (LNode*)L;
}

程序运行结果如下:



?


2、链表中查找某结点


因为链表不支持随机访问,即链表的存取方式是顺序存取的(注意“存储”与“存取”是两个不一样的概念),所以要查找某结点,必须通过遍历的方式查找。例如:如果想查找第5个结点,必须先遍历走过第1~4个结点,才能得到第5个结点。代码如下:


int Serch(LNode *L, int elem)
{
LNode *temp = L;
int pos = 0;
int i = 1;

while(temp->next)
{
temp = temp->next;
if(elem==temp->data)
{
pos = i;
printf("The %d position in the list is %d
",elem,pos);
return pos; //返回elem元素在顺序表中的位置
}
i++;
}
printf("Serch error!
");

return ERROR; //查找失败
}

程序运行结果如下:



?


3、修改某结点的数据域


要修改某结点的数据域,首先通过遍历的方法找到该结点,然后直接修改该结点的数据域的值。代码如下:


LNode *Replace(LNode *L, int pos, int elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
temp = temp->next; //在遍历之前,temp指向开始结点
for(int i=1;i {
temp = temp->next;
}
temp->data = elem; //找到要替换的结点并替换其数据域的值为elem

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

程序运行结果如下:



?


4、往链表中插入结点


插入结点的位置有三种:


(1)插入到链表的首部,也就是头结点和开始结点之间;


(2)插入到链表中间的某个位置;


(3)插入到链表的末端。



? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 图4 链表中插入结点5


虽然插入的位置有区别,都使用相同的插入手法。分为两步,如图4所示:


(1)将新结点的next指针指向插入位置的后一个结点;


(2)将插入位置的前一个结点的next指针指向插入结点。


代码如下:


LNode *Insert(LNode *L, int pos, int elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
int i = 0;
/* 首先找到插入结点的上一结点,即第pos-1个结点 */
while( (temp!=NULL)&&(i {
temp = temp->next;
++i;
}
/* 错误处理:链表为空或插入位置不存在 */
if( (temp==NULL)||(i>pos-1) )
{
printf("%s:Insert false!
",__FUNCTION__);
return (LNode*)temp;
}
LNode *new = (LNode*)malloc(sizeof(LNode)); //创建新结点new
new->data = elem; //插入的新结点的数据域
new->next = temp->next; //新结点的next指针指向插入位置后的结点
temp->next = new; //插入位置前的结点的next指针指向新结点

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

程序运行结果如下:



?


5、删除链表结点



? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图5 删除结点


当需要从链表中删除某结点时,需要进行两部操作:


(1)将结点从链表中摘下来,即修改指针指向为:被删除结点的前一个结点的next指针指向被删除结点之后的结点。


(2)手动释放掉被删除结点所占用的内存。


代码如下:


LNode *Delete(LNode *L, int pos, int *elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
int i = 0;
/* 首先找到删除结点的上一结点,即第pos-1个结点 */
while( (temp!=NULL)&&(i {
temp = temp->next;
++i;
}
/* 错误处理:链表为空或删除位置不存在 */
if( (temp==NULL)||(i>pos-1) )
{
printf("%s:Delete false!
",__FUNCTION__);
return (LNode*)temp;
}
LNode *del = temp->next; //定义一个del指针指向被删除结点
*elem = del->data; //保存被删除的结点的数据域
temp->next = del->next; /*删除结点的上一个结点的指针域指向删除结点的下一个结点,
也可写为“temp->next = temp->next->next”*/
free(del); //手动释放该结点,防止内存泄露
del = NULL; //防止出现野指针

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

程序运行结果如下:



?


以下是完整的代码:


/*----------------------------------------------------------------------------------------

Program Explain:单链表的基本操作
Create Date:2018.2.13 by lzn

----------------------------------------------------------------------------------------*/

#include
#include

#define ERROR 1
#define OK 0

/* 单链表结点定义 */
typedef struct LNode
{
int data; //data中存放结点数据域(默认是int型)
struct LNode *next; //指向后继结点的指针
}LNode;

//操作函数的声明
LNode *HeadCreateList(int len); //头插法建立单链表
LNode *TailCreateList(int len); //尾插法建立单链表
int Serch(LNode *L, int elem); //在表中寻找元素的位置
LNode *Replace(LNode *L, int pos, int elem); //替换第pos个位置的元素成elem
LNode *Insert(LNode *L, int pos, int elem); //在表中插入新结点
LNode *Delete(LNode *L, int pos, int *elem); //删除表中的结点
void PrintfList(LNode *L); //打印链表
int MenuSelect(void); //菜单
//测试函数的声明
void Test1(LNode *L); //测试"Serch"函数
void Test2(LNode *L); //测试"Replace"函数
void Test3(LNode *L); //测试"Insert"函数
void Test4(LNode *L); //测试"Delete"函数
LNode *Test5(void); //测试"TailCreateList"函数
LNode *Test6(void); //测试"HeadCreateList"函数

/*********************************************************************************
* Function Name : main主函数
* Parameter : NULL
* Return Value : 0
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
int main(void)
{
int len = 0;
int cmd;
LNode *L;

/* 初始默认为尾插法建立单链表 */
printf("Please input list length:");
scanf("%d",&len);
L = TailCreateList(len);
PrintfList(L);
while(1)
{
cmd = MenuSelect();
switch(cmd)
{
case 1: Test1(L); break; //测试"Serch"函数
case 2: Test2(L); break; //测试"Replace"函数
case 3: Test3(L); break; //测试"Insert"函数
case 4: Test4(L); break; //测试"Delete"函数
case 5: L=Test5(); break; //测试"TailCreateList"函数
case 6: L=Test6(); break; //测试"HeadCreateList"函数
case 7: system("cls"); break; //清屏
case 8: exit(0); break; //退出
}
}
return 0;
}

/*********************************************************************************
* Function Name : HeadCreateList, 头插法建立单链表(逆序)
* Parameter : len:链表长度
* Return Value : 创建好的链表
* Function Explain : 从一个空表开始,不断读入数据,生成新结点,将读入数据存放到新
结点的数据域中,然后将新结点插入到当前链表的表头结点之后。
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *HeadCreateList(int len)
{
LNode *L = (LNode*)malloc(sizeof(LNode)); //创建一个头结点
LNode *temp = L;//声明一个中间变量,指向头结点,用于遍历链表(曾因没有这个中间变量而出错)
temp->next = NULL; //该链表此刻只带头结点

for(int i=1;i<=len;i++) //循环申请len个结点来接收scanf得到的元素
{
LNode *p = (LNode*)malloc(sizeof(LNode)); //生成新结点
scanf("%d",&p->data); //用新申请的结点来接收scanf得到的元素
/* 以下两条语句是头插法的关键步骤,与本工程"Insert"函数原理一样 */
p->next = temp->next; //新结点的next指针指向开始结点
temp->next = p; //头结点的next指针指向新结点
}

return (LNode*)L;
}

/*********************************************************************************
* Function Name : TailCreateList, 尾插法建立单链表(顺序)
* Parameter : len:链表长度
* Return Value : 创建好的链表
* Function Explain : 从一个空表开始,不断读入数据,生成新结点,将读入数据存放到新
结点的数据域中,然后将新结点插入到当前链表的表尾结点之后。
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *TailCreateList(int len)
{
LNode *L = (LNode*)malloc(sizeof(LNode)); //创建一个头结点
LNode *temp = L;//声明一个中间变量,指向头结点,用于遍历链表(曾因没有这个中间变量而出错)
temp->next = NULL;//该链表此刻只带头结点

for(int i=1;i<=len;i++) //循环申请len个结点来接收scanf得到的元素
{
LNode *p = (LNode*)malloc(sizeof(LNode)); //生成新结点
scanf("%d",&p->data); //用新申请的结点来接收scanf得到的元素
/* 以下两条语句是尾插法的关键步骤 */
temp->next = p; //用来接纳新结点
temp = p; //指向终端结点,以便于接纳下一个到来的结点,此语句也可以改为"L = L->next"
}
temp->next = NULL; //此刻所有元素已经全装入链表L中,L的终端结点的指针域置为NULL

return (LNode*)L;
}

/*********************************************************************************
* Function Name : Serch, 查找结点
* Parameter : L:链表 elem:所查找的结点的数据域
* Return Value : pos:搜索到的元素的位置 ERROR:elem不在顺序表L中
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
int Serch(LNode *L, int elem)
{
LNode *temp = L;
int pos = 0;
int i = 1;

while(temp->next)
{
temp = temp->next;
if(elem==temp->data)
{
pos = i;
printf("The %d position in the list is %d
",elem,pos);
return pos; //返回elem元素在顺序表中的位置
}
i++;
}
printf("Serch error!
");

return ERROR; //查找失败
}

/*********************************************************************************
* Function Name : Replace, 替换第pos个位置的元素成elem
* Parameter : L:链表 pos:要替换的位置 elem:要替换的元素
* Return Value : 替换某结点之后生成的新链表
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *Replace(LNode *L, int pos, int elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
temp = temp->next; //在遍历之前,temp指向开始结点
for(int i=1;i {
temp = temp->next;
}
temp->data = elem; //找到要替换的结点并替换其数据域的值为elem

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

/*********************************************************************************
* Function Name : Insert, 向链表中插入结点
* Parameter : L:链表 pos:要插入的位置 elem:要插入的结点的数据域
* Return Value : 插入新结点之后生成的新链表
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *Insert(LNode *L, int pos, int elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
int i = 0;
/* 首先找到插入结点的上一结点,即第pos-1个结点 */
while( (temp!=NULL)&&(i {
temp = temp->next;
++i;
}
/* 错误处理:链表为空或插入位置不存在 */
if( (temp==NULL)||(i>pos-1) )
{
printf("%s:Insert false!
",__FUNCTION__);
return (LNode*)temp;
}
LNode *new = (LNode*)malloc(sizeof(LNode)); //创建新结点new
new->data = elem; //插入的新结点的数据域
new->next = temp->next; //新结点的next指针指向插入位置后的结点
temp->next = new; //插入位置前的结点的next指针指向新结点

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

/*********************************************************************************
* Function Name : Delete, 删除链表中的结点
* Parameter : L:链表 pos:要删除的位置 elem:被删除的结点的数据域
* Return Value : 删除结点之后生成的新链表
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *Delete(LNode *L, int pos, int *elem)
{
LNode *temp = L; //引入一个中间变量,用于循环变量链表
int i = 0;
/* 首先找到删除结点的上一结点,即第pos-1个结点 */
while( (temp!=NULL)&&(i {
temp = temp->next;
++i;
}
/* 错误处理:链表为空或删除位置不存在 */
if( (temp==NULL)||(i>pos-1) )
{
printf("%s:Delete false!
",__FUNCTION__);
return (LNode*)temp;
}
LNode *del = temp->next; //定义一个del指针指向被删除结点
*elem = del->data; //保存被删除的结点的数据域
temp->next = del->next; /*删除结点的上一个结点的指针域指向删除结点的下一个结点,
也可写为“temp->next = temp->next->next”*/
free(del); //手动释放该结点,防止内存泄露
del = NULL; //防止出现野指针

return (LNode*)L; //注意!!不能写为 "return (LNode*)temp;"
}

/*********************************************************************************
* Function Name : PrintfList,打印链表
* Parameter : L:要打印的链表
* Return Value : NULL
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
void PrintfList(LNode *L)
{
LNode *temp = L;
int count = 0; //计数器
printf("List:
");
while(temp->next)
{
temp = temp->next;
printf("%d ",temp->data);
count++;
if(count%5==0) //每5个元素作为一行
{
printf("
");
}
}
printf("
");
}

/*********************************************************************************
* Function Name : MenuSelect,菜单
* Parameter : void
* Return Value : cmd
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
int MenuSelect(void)
{
int cmd;

printf("1.Serch test
");
printf("2.Replace test
");
printf("3.Insert test
");
printf("4.Delete test
");
printf("5.TailCreateList test
");
printf("6.HeadCreateList test
");
printf("7.Clear
");
printf("8.Exit
");
do
{
printf("Enter your choice: ");
scanf("%d",&cmd);
}while(cmd<0||cmd>8);

return cmd;
}
/* ====================================以下是测试函数============================== */
/*********************************************************************************
* Function Name : Test1, 测试"Serch"函数
* Parameter : L:链表
* Return Value : void
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
void Test1(LNode *L)
{
int serchElem = 0; //存储要搜索的元素

printf("--------------------%s start!--------------------
",__FUNCTION__);
PrintfList(L);
printf("Please input the element you want to serch:");
scanf("%d",&serchElem);
Serch(L,serchElem);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");
}

/*********************************************************************************
* Function Name : Test2, 测试"Replace"函数
* Parameter : L:链表
* Return Value : void
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
void Test2(LNode *L)
{
int replacePos = 0, replaceElem = 0; //存储替换的位置,替换的元素

printf("--------------------%s start!--------------------
",__FUNCTION__);
PrintfList(L);
printf("Please input the position and the element you want replace(example:10,33):");
scanf("%d,%d",&replacePos,&replaceElem);
L = Replace(L,replacePos,replaceElem);
printf("After replace by position,list is:
");
PrintfList(L);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");
}

/*********************************************************************************
* Function Name : Test3, 测试"Insert"函数
* Parameter : L:链表
* Return Value : void
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
void Test3(LNode *L)
{
int insertPos = 0, insertElem = 0; //存储插入的位置,插入的元素

printf("--------------------%s start!--------------------
",__FUNCTION__);
PrintfList(L);
printf("Please input the position and the element you want insert(example:10,33):");
scanf("%d,%d",&insertPos,&insertElem);
L = Insert(L,insertPos,insertElem);
printf("After insert,list is:
");
PrintfList(L);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");
}

/*********************************************************************************
* Function Name : Test4, 测试"Delete"函数
* Parameter : L:链表
* Return Value : void
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
void Test4(LNode *L)
{
int deletePos = 0; //存储要删除的位置
int elem = NULL;

printf("--------------------%s start!--------------------
",__FUNCTION__);
PrintfList(L);
printf("Please input the position of the element you want to delete(example:10):");
scanf("%d",&deletePos);
L = Delete(L,deletePos,&elem);
printf("Delete node data is:%d
",elem);
printf("After delete,list is:
");
PrintfList(L);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");
}

/*********************************************************************************
* Function Name : Test5, 测试"TailCreateList"函数
* Parameter : void
* Return Value : 初始化成功的链表
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *Test5(void)
{
LNode *L;
int len = 0;

printf("--------------------%s start!--------------------
",__FUNCTION__);
printf("Please input list length:");
scanf("%d",&len);
L = TailCreateList(len);
PrintfList(L);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");

return (LNode*)L;
}

/*********************************************************************************
* Function Name : Test6, 测试"HeadCreateList"函数
* Parameter : void
* Return Value : 初始化成功的链表
* Function Explain :
* Create Date : 2018.2.13 by lzn
**********************************************************************************/
LNode *Test6(void)
{
LNode *L;
int len = 0;

printf("--------------------%s start!--------------------
",__FUNCTION__);
printf("Please input list length:");
scanf("%d",&len);
L = HeadCreateList(len);
PrintfList(L);
printf("--------------------%s end!--------------------
",__FUNCTION__);
printf("
");

return (LNode*)L;
}

三、参考资料

1、头插法与尾插法


2、C语言中文网数据结构教程


3、链表的操作


?

相关推荐

最新更新

猜你喜欢