链表Linklist操作
2023-12-20 08:39:39
单项链表操作
有头单向链表的函数操作
创建一个空链表：只有一个头节点，指针域赋值为空指针。
在指定位置插入：
在指定位置删除：
1）创建一个新的头节点
//创建一个空的有头单项链表
link_node_t *createEmptyLinkList()
{
//1.创建节点，作为连表的头节点。
link_list_t?h?= (link_list_t)malloc(sizeof(link_node_t));
if (NULL ==?h)
{
perror("createEmptyLinkList?malloc?err");
return NULL;
}
//2.初始化
????h->next?= NULL;
return?h;
}
2)计算链表长度
//计算链表长度
int lengthLinkList(link_node_t *p)
{
int?len?= 0;
while (p->next?!= NULL)
{
????????p?=?p->next;
????????len++;
}
return?len;
}
3)单项链表在指定位置插入数据
//单项链表在指定位置插入数据
//p是链表头指针，post是插入位置（从0开始），data插入的数据。
//思想：先记录插入位置的前一个节点。然后先连后面再连前面。
int insertIntoPostLinkList(link_node_t *p, int?post,?datatype?data)
{
int?i;
link_list_t?pnew?= NULL;
//1.容错处理
if (post?< 0 ||?post?> lengthLinkList(p))
{
printf("insertIntoPostLinkList?err");
return -1;
}
//2.将头指针p移动到插入得前一个位置
for (i?= 0;?i?<?post;?i++)
{
????????p?=?p->next;
}
//3.创建一个新节点，保存插入数据
????pnew?= (link_list_t)malloc(sizeof(link_node_t));
if (pnew?== NULL)//判断开辟成功
{
perror("insertIntoPostLinkList?pnew?malloc?err");
return -1;
}
????????pnew->data?=?data;
????????pnew->next?= NULL;
//4.将新节点插入到链表，先连后面，再连前面。
????????pnew->next?=?p->next;
????????p->next?=?pnew;
return 0;
}
4)遍历有头单项链表
//遍历单向链表
void showLinkList(link_node_t *p)
{
while (p->next?!= NULL)
{
????????p?=?p->next;
printf("%d?",?p->data);
}
printf("\n");
}
- 判断链表为空
//判断链表是否为空，为空返回1,非空返回0
int isEmptyLinkList(link_node_t *p)
{
return?p->next?== NULL;
}
6)删除单向链表中指定位置的数据?post?代表的是删除的位置
//?删除单向链表中指定位置的数据?post?代表的是删除的位置
int deletePostLinkList(link_node_t *p, int?post)
{
int?i;
link_list_t?pdel?= NULL;
//1.容错判断
if (post?< 0 ||?post?>= lengthLinkList(p) || isEmptyLinkList(p))
{
printf("deletePostLinkList?err");
return -1;
}
//2.将头指针移动到要删除节点的前一个位置
for (i?= 0;?i?<?post;?i++)
????????p?=?p->next;
//3.删除操作
//（1）用指针pdel记录要删除节点
????pdel?=?p->next;
//（2）跨过要删除节点
????p->next?=?pdel->next;
//（3）释放被删除节点
free(pdel);
????pdel?= NULL;
return 0;
}
7)清空链表
//清空链表
//思想：循环删除头节点得下一个节点，直到链表为空。
//?(1)定义一个pdel,指向被删除节点
//?(2)跨过被删除节点
//?(3)让p指向要被删除节点
//?(4)释放被删除节点
void clearLinkList(link_node_t *p)
{
link_list_t?pdel?= NULL;
while (p->next?!= NULL)
{
????????pdel?=?p->next; //每次删除得都是头节点的下一个节点
????????p->next?=?pdel->next;
free(pdel);
????????pdel?= NULL;
}
}
8)查找指定数据出现的位置?data被查找的数据
//查找指定数据出现的位置?data被查找的数据
int searchDataLinkList(link_node_t *p,?datatype?data)
{
int?post?= 0; //记录查找位置
while (p->next?!= NULL) //遍历有头链表
{
????????p?=?p->next;
if (p->data?==?data)
return?post;
????????post++;
}
return -1;
}
9)修改链表中指定位置的数据
//修改链表中指定位置的数据
int changePostLinkList(link_node_t *p, int?post,?datatype?data)
{
int?i;
//1.容错判断
if (post?< 0 ||?post?>= lengthLinkList(p))
{
printf("changePostLinkList?err\n");
return -1;
}
//2.将头指针移动到要修改的位置
for (i?= 0;?i?<=?post;?i++)
????????p?=?p->next;
//3.修改数据
????p->data?=?data;
return 0;
}
10)删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//思想：p始终指向被删除节点的前一个节点，q从头节点的下一个节点开始遍历，相当于遍历无头链表。pdel始终指向被删除的节点。
int deleteDataLinkList(link_node_t *p,?datatype?data)
{
link_list_t?pdel?= NULL; //用于指向被删除的节点
//1.定义一个指针q，指向头节点的下一个节点，此时q可以看作遍历无头链表。
link_list_t?q?=?p->next;
//2.让q来遍历无头链表，让每一个节点中数据域都与传进来的data做比较，如果相同就删除，如果不同就继续向后遍历
while (q?!= NULL)
{
if (q->data?==?data) //判断q所指节点中的数据域是否和data一致，如果一致就删除。否则向后移动。
{
//（1）将pdel指向被删除节点
????????????pdel?=?q;
//（2）跨过被删除节点
????????????p->next?=?pdel->next;
//（3）释放被删除节点
free(pdel);
????????????pdel?= NULL;
//（4）让q指向此时p的下一个节点，也就是之前删除的节点的下一个节点
????????????q?=?p->next;
}
else
{
????????????p?=?p->next; //将p指针向后移动一个单位
????????????q?=?p->next; //始终保持p指向q的前一个节点
}
}
}
11)链表转置
//?链表转置?
//?解题思想：
//?1)将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表。
//?2)遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)。
void reverseLinkList(link_node_t *p)
{
link_list_t?temp=NULL; //用来临时保存q节点的下一个节点
//1.断开前，用q保存头节点得下一个节点，用作遍历无头链表。
link_list_t?q?=?p->next;
//2.将头节点和链表断开
????p->next?= NULL;
//3.遍历无头链表，用头插法将遍历的节点插入头节点后面。
while (q?!= NULL)
{
//(1)提前将q所指节点得下一个节点用temp保存
????????temp?=?q->next;
//(2)先连后面，再连前面，插入头节点后面。
????????q->next?=?p->next;
????????p->next?=?q; //执行完这样代码后，q无法再找到下一个节点，所以需要在此行执行之前将q的下一个节点的地址提前保存起来
//(3）将q移动，指向temp保存得位置。
????????q?=?temp;
}
}
操作综合代码
#include?<stdio.h>
#include?<stdlib.h>
typedef int?datatype;
typedef struct node
{
????datatype?data; //数据域，用来存放数据。
struct node *next; //指针域，用来存放下一个节点的地址。
} link_node_t, *link_list_t;
//创建一个空的有头单项链表
link_node_t *createEmptyLinkList()
{
//1.创建节点，作为连表的头节点。
link_list_t?h?= (link_list_t)malloc(sizeof(link_node_t));
if (NULL ==?h)
{
perror("createEmptyLinkList?malloc?err");
return NULL;
}
//2.初始化
????h->next?= NULL;
return?h;
}
//计算链表长度
int lengthLinkList(link_node_t *p)
{
int?len?= 0;
while (p->next?!= NULL)
{
????????p?=?p->next;
????????len++;
}
return?len;
}
//单项链表在指定位置插入数据
//p是链表头指针，post是插入位置（从0开始），data插入的数据。
//思想：先记录插入位置的前一个节点。然后先连后面再连前面。
int insertIntoPostLinkList(link_node_t *p, int?post,?datatype?data)
{
int?i;
link_list_t?pnew?= NULL;
//1.容错处理
if (post?< 0 ||?post?> lengthLinkList(p))
{
printf("insertIntoPostLinkList?err");
return -1;
}
//2.将头指针p移动到插入得前一个位置
for (i?= 0;?i?<?post;?i++)
{
????????p?=?p->next;
}
//3.创建一个新节点，保存插入数据
????pnew?= (link_list_t)malloc(sizeof(link_node_t));
if (pnew?== NULL)//判断开辟成功
{
perror("insertIntoPostLinkList?pnew?malloc?err");
return -1;
}
????????pnew->data?=?data;
????????pnew->next?= NULL;
//4.将新节点插入到链表，先连后面，再连前面。
????????pnew->next?=?p->next;
????????p->next?=?pnew;
return 0;
}
//遍历单向链表
void showLinkList(link_node_t *p)
{
while (p->next?!= NULL)
{
????????p?=?p->next;
printf("%d?",?p->data);
}
printf("\n");
}
//判断链表是否为空，为空返回1,非空返回0
int isEmptyLinkList(link_node_t *p)
{
return?p->next?== NULL;
}
//?删除单向链表中指定位置的数据?post?代表的是删除的位置
int deletePostLinkList(link_node_t *p, int?post)
{
int?i;
link_list_t?pdel?= NULL;
//1.容错判断
if (post?< 0 ||?post?>= lengthLinkList(p) || isEmptyLinkList(p))
{
printf("deletePostLinkList?err");
return -1;
}
//2.将头指针移动到要删除节点的前一个位置
for (i?= 0;?i?<?post;?i++)
????????p?=?p->next;
//3.删除操作
//（1）用指针pdel记录要删除节点
????pdel?=?p->next;
//（2）跨过要删除节点
????p->next?=?pdel->next;
//（3）释放被删除节点
free(pdel);
????pdel?= NULL;
return 0;
}
//清空链表
//思想：循环删除头节点得下一个节点，直到链表为空。
//?(1)定义一个pdel,指向被删除节点
//?(2)跨过被删除节点
//?(3)让p指向要被删除节点
//?(4)释放被删除节点
void clearLinkList(link_node_t *p)
{
link_list_t?pdel?= NULL;
while (p->next?!= NULL)
{
????????pdel?=?p->next; //每次删除得都是头节点的下一个节点
????????p->next?=?pdel->next;
free(pdel);
????????pdel?= NULL;
}
}
//查找指定数据出现的位置?data被查找的数据
int searchDataLinkList(link_node_t *p,?datatype?data)
{
int?post?= 0; //记录查找位置
while (p->next?!= NULL) //遍历有头链表
{
????????p?=?p->next;
if (p->data?==?data)
return?post;
????????post++;
}
return -1;
}
//修改链表中指定位置的数据
int changePostLinkList(link_node_t *p, int?post,?datatype?data)
{
int?i;
//1.容错判断
if (post?< 0 ||?post?>= lengthLinkList(p))
{
printf("changePostLinkList?err\n");
return -1;
}
//2.将头指针移动到要修改的位置
for (i?= 0;?i?<=?post;?i++)
????????p?=?p->next;
//3.修改数据
????p->data?=?data;
return 0;
}
//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//思想：p始终指向被删除节点的前一个节点，q从头节点的下一个节点开始遍历，相当于遍历无头链表。pdel始终指向被删除的节点。
int deleteDataLinkList(link_node_t *p,?datatype?data)
{
link_list_t?pdel?= NULL; //用于指向被删除的节点
//1.定义一个指针q，指向头节点的下一个节点，此时q可以看作遍历无头链表。
link_list_t?q?=?p->next;
//2.让q来遍历无头链表，让每一个节点中数据域都与传进来的data做比较，如果相同就删除，如果不同就继续向后遍历
while (q?!= NULL)
{
if (q->data?==?data) //判断q所指节点中的数据域是否和data一致，如果一致就删除。否则向后移动。
{
//（1）将pdel指向被删除节点
????????????pdel?=?q;
//（2）跨过被删除节点
????????????p->next?=?pdel->next;
//（3）释放被删除节点
free(pdel);
????????????pdel?= NULL;
//（4）让q指向此时p的下一个节点，也就是之前删除的节点的下一个节点
????????????q?=?p->next;
}
else
{
????????????p?=?p->next; //将p指针向后移动一个单位
????????????q?=?p->next; //始终保持p指向q的前一个节点
}
}
}
//?链表转置?
//?解题思想：
//?1)将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表。
//?2)遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)。
void reverseLinkList(link_node_t *p)
{
link_list_t?temp=NULL; //用来临时保存q节点的下一个节点
//1.断开前，用q保存头节点得下一个节点，用作遍历无头链表。
link_list_t?q?=?p->next;
//2.将头节点和链表断开
????p->next?= NULL;
//3.遍历无头链表，用头插法将遍历的节点插入头节点后面。
while (q?!= NULL)
{
//(1)提前将q所指节点得下一个节点用temp保存
????????temp?=?q->next;
//(2)先连后面，再连前面，插入头节点后面。
????????q->next?=?p->next;
????????p->next?=?q; //执行完这样代码后，q无法再找到下一个节点，所以需要在此行执行之前将q的下一个节点的地址提前保存起来
//(3）将q移动，指向temp保存得位置。
????????q?=?temp;
}
}
int main(int?argc, char const *argv[])
{
link_list_t?p?= createEmptyLinkList();
insertIntoPostLinkList(p, 0, 1);
insertIntoPostLinkList(p, 1, 2);
insertIntoPostLinkList(p, 2, 3);
insertIntoPostLinkList(p, 3, 4);
insertIntoPostLinkList(p, 4, 2);
reverseLinkList(p);
showLinkList(p);
deletePostLinkList(p, 2);
showLinkList(p);
printf("len=%d\n", lengthLinkList(p));
deleteDataLinkList(p, 2);
showLinkList(p);
printf("1?post?is:%d\n", searchDataLinkList(p, 1));
return 0;
}
链表合并
递增有序的链表A 1 3 5 7 9 10
递增有序的链表B 2 4 5 8 11 15
新链表：1 2 3 4 5 5 7 8 9 10 11 15
将链表A和B合并，形成一个递增有序的新链表
link_list_t?ptail?=?pa;//将ptail永远指向新链表的尾巴，此时把pa头节点当做新链表的头
link_list_t?h?=?pa;//记录链表pa的头节点地址，用于查看每轮节点合并情况
pa?=?pa->next;//跨过头结点，pa相当于无头表的头指针
pb?=?pb->next;//跨过头结点，pb相当于无头表的头指针
//同时遍历pa和pb
while(pa?!= NULL &&?pb?!= NULL)//相当于遍历无头
{
//判断两个链表内节点数据的大小
if(pa->data?<?pb->data)
{
ptail->next?=?pa;//pa节点小，将pa节点链接到新链表尾
pa?=?pa->next;//继续遍历pa表，pa指向下一个节点，用于下一轮比较以及合并
ptail?=?ptail->next;//继续将尾指针指向新链表的尾巴
printf("A段\n");//确定输出的段
Show(pa);//输出合并后pa段剩余的节点
Show(ptail);//输出pa合并的节点及剩余的节点
Show(h);//输出新列表
puts("?");
}
else//pa->data?>=?pb->data
{
ptail->next?=?pb;//pb节点小，将pb节点链接到新表尾?
pb?=?pb->next; //继续遍历pb表，pb指向下一个节点，用于下一轮比较以及合并
ptail?=?ptail->next;//继续让ptail指向新表的尾
printf("B段\n");//确定输出的段
Show(pb);//输出合并后pb段剩余的节点
Show(ptail);//输出pb合并的节点及剩余的节点
Show(h);//输出新列表
puts("?");
}
}
//循环结束后，有可能pa先全部遍历完,也有可能是pb表,剩余的链表赋到新链表后面
//剩余链表可能没有排序
if(pa?== NULL)//pa遍历没了,pb有剩余
ptail->next?=?pb;//将剩余的pb接在新表的尾?
else
ptail->next?=?pa;//将圣墟的pa接在新表的尾
单向循环链表
单向循环链表:约瑟夫环问题，是一个经典的循环链表问题，题意是：已知?n?个人（分别用编号?1，2，3，…，n?表示）围坐在一张圆桌周围，从编号为?k?的人开始顺时针报数，数到?m?的那个人出列；他的下一个人又从?1?开始，还是顺时针开始报数，数到?m?的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
用解决约瑟夫环问题进行杀猴子：
思想：用头指针移动到要杀的猴子的前一个，然后跨过指向猴子的节点。
#include?<stdio.h>
#include?<stdlib.h>
#include?<unistd.h>
typedef struct node_t
{
int?data;
struct node_t *next;
}link_node_t,*link_list_t;
int main(int?argc, const char *argv[])
{
int?i;
link_list_t?pdel?= NULL;//用于指向被删除节点
link_list_t?ptail?= NULL;//永远指向当前链表的尾?
link_list_t?pnew?= NULL;//永远指向新创建的节点
link_list_t?h?= NULL;
int?all_num?= 7;//猴子总数?
int?start_num?= 2; //从几号猴子开始数
int?kill_num?= 3;//数到几杀死猴
printf("请您入猴子总数?起始号码?数到几杀死:\n");
scanf("%d%d%d",&all_num,&start_num,&kill_num);
//1.创建出一个单向循环链表
//(1)创建有all_num个节点的单向链表
h?= (link_list_t)malloc(sizeof(link_node_t));
if(NULL ==?h)
{
perror("malloc?failed");
return -1;
}
h->data?= 1;
h->next?= NULL;
ptail?=?h;//尾指针指向当前的第一个节点
for(i?= 2;?i?<=?all_num;?i++)
{
//创建新的节点
pnew?= (link_list_t)malloc(sizeof(link_node_t));
if(NULL ==?pnew)
{
perror("malloc?failed");
return -1;
}
//将新节点装上数据
pnew->data?=?i;
pnew->next?= NULL;
//将新节点链接到链表尾?
ptail->next?=?pnew;//链接到链表的尾
ptail?=?pnew;//尾指针继续指向当前链表的尾?
}
//(2)将头指针保存到链表的尾形成单向循环链表
ptail->next?=?h;//形成单向循环链表?
#if?0?//用于调试程序
while(1)
{
printf("%d\n",h->data);
h?=?h->next;
sleep(1);
}
#endif
//2.开始杀猴子?
//(1)将头指针移动到开始猴子的号码处?
for(i?= 1;?i?<?start_num;?i++)
h?=?h->next;
printf("start?:%d\n",h->data);
//(2)循环进行杀猴子
while(h?!=?h->next)//条件不成的时候，就剩一个猴子,只有一个节点
{
//将头指针移动到即将删除节点的前一个节点
for(i?= 1;?i?<?kill_num-1;?i++)
h?=?h->next;
pdel?=?h->next;
//跨过删除节点
h->next?=?pdel->next;
printf("kill?is?-------------%d\n",pdel->data);
free(pdel);
pdel?= NULL;
//杀死猴子猴，从下一个节点开始继续开始数,将头指针移动到开始数的地方
h?=?h->next;
}
printf("king?is===================?%d\n",h->data);
return 0;
}
结构体嵌套法杀猴子
#include?<stdio.h>
#include?<stdlib.h>
typedef int?datatype;
typedef struct node_t
{
datatype?data;
struct node_t *?prior;
struct node_t *?next;
}link_node_t,*link_list_t;
typedef struct doublelinklist
{
link_list_t?head;
link_list_t?tail;
}double_node_t,*double_list_t;
int main(int?argc, const char *argv[])
{
int?i;
int?all_num?= 8;//猴子总数
int?start_num?= 3;//从3号猴子开始数
int?kill_num?= 3;//数到几杀死猴子?
link_list_t?h?= NULL;
link_list_t?pdel?= NULL;//用来指向被杀死猴子的节点
printf("请您输入猴子的总数，开始号码，出局号码:\n");
scanf("%d%d%d",&all_num,&start_num,&kill_num);
//1.创建一个双向的循环链表
double_list_t?p?= (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针
if(NULL ==?p)
{
perror("malloc?failed");
return -1;
}
p->head?=?p->tail?= (link_list_t)malloc(sizeof(link_node_t));
if(NULL ==?p->tail)
{
perror("p->tail?malloc?failed");
return -1;
}
p->head->data?= 1;
p->head->prior?= NULL;
p->head->next?= NULL;
//将创建n个新的节点，链接到链表的尾
for(i?= 2;?i?<=?all_num;?i++)
{
link_list_t?pnew?= (link_list_t)malloc(sizeof(link_node_t));
if(NULL ==?pnew)
{
perror("pnew?malloc?failed");
return -1;
}
pnew->data?=?i;
pnew->prior?= NULL;
pnew->next?= NULL;
//(1)将新的节点链接到链表的尾
p->tail->next?=?pnew;
pnew->prior?=?p->tail;
//(2)尾指针向后移动，指向当前链表的尾
p->tail?=?pnew;
}
//(3)形成双向循环链表?
p->tail->next?=?p->head;
p->head->prior?=?p->tail;
//调试程序?
#if?0
while(1)
{
printf("%d\n",p->head->data);
p->head?=?p->head->next;
sleep(1);
}
#endif
//2.循环进行杀死猴子
h?=?p->head;
//(1)先将h移动到start_num处，也就是开始数数的猴子号码处
for(i?= 0;?i?<?start_num-1;?i++)
h?=?h->next;
while(h->next?!=?h)//当h->next?==?h?就剩一个节点了，循环结束
{
//(2)将h移动到即将杀死猴子号码的位置
for(i?= 0;?i?<?kill_num-1;?i++)
h?=?h->next;
//(3)进行杀死猴子，经过上面的循环后，此时的h指向即将杀死的猴子
h->prior->next?=?h->next;
h->next->prior?=?h->prior;
pdel?=?h;//pdel指向被杀死猴子的位置
printf("kill?is?-------%d\n",pdel->data);
h?=?h->next;//需要移动，从杀死猴子后的下一个位置开始数
free(pdel);
}
printf("猴王是%d\n",h->data);
return 0;
}
总结：顺序表和单向链表比较
- 顺序表在内存当中连续存储的(数组)，但是链表在内存当中是不连续存储的，通过指针将数据链接在一起。
- 顺序表的长度是固定的，但是链表长度不固定
- ?顺序表查找方便，但是插入和删除效率低，链表，插入和删除方便，查找效率低。
文章来源:https://blog.csdn.net/m0_74937538/article/details/132773183
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！