创建一个空链表:只有一个头节点,指针域赋值为空指针。
在指定位置插入:
在指定位置删除:
//创建一个空的有头单项链表
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;
}
}
#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;
}