单向链表
1. 概念
单向链表 单向循环链表 双向链表 双向循环链表
解决：长度固定的问题，插入和删除麻烦的问题
1、逻辑结构： 线性结构
2、存储结构： 链式存储
链表就是将 结点 用链串起来的线性表，链就是 结点 中的指针域。
(赵, 钱, 孙, 李, 周, 吴, 郑, 王)
存储地址 |
数据域 |
指针域 |
|
头指针
|
|
李 |
|
|
钱 |
|
|
|
孙 |
|
|
|
王 |
|
|
|
吴 |
|
|
|
赵 |
|
|
|
郑 |
|
|
|
周 |
|
|
|
|
2. 接口实现
用来操作顺序表的结构体定义
struct SeqList
{
int data[10]; // 顺序表
int last;
}；
用来操作有头单向链表的结构体定义
struct node_t
{
int data; //数据域
struct node_t *next;//指针域 ，指针指向自身结构体的类型(存放的下一个节点的地址)
}；链表 操作链表的结构体就是链表中结点的结构体。
顺序表 操作顺序表的结构体中就包含了顺序表数组。
3. 链表前言1
typedef struct node_t
{
char data; //数据域
struct node_t *next;//指针域 ，指针指向自身结构体的类型(存放的下一个节点的地址)
}link_node_t,* link_list_t;
struct node_t《-》link_node_t
link_list_t《-》struct node_t * 《-》link_node_t *
typedef struct node_t * -> link_list_t
#if 0
struct node_t *p;
link_node_t *p;
link_list_t p;
int a;
int *p;
#endif4. 链表前言2
4.1 遍历无头的单向链表
链表中的每一个节点的数据域和指针域都是有效的
while(p!= NULL)
{
printf("%c\n",p->data);
p = p->next;
} #include <stdio.h>
typedef struct node_t
{
char data;
struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, const char *argv[])
{
link_node_t A={'A',NULL};
link_node_t B={
.data = 'B',
.next = NULL,
};
link_node_t C = {'C',NULL};
link_node_t D = {'D',NULL};
A.next = &B;
B.next = &C;
C.next = &D;
link_list_t p = &A;
while(p != NULL)//无头单向链表的遍历条件
{
printf("%c\n",p->data);
p = p->next;//链表：指针往后走
}
return 0;
} 4.2 遍历有头的单向链表
while(p->next != NULL)
{
p = p->next;
printf("%c", p->data);
}#include <stdio.h>
//定义结构体类型
typedef struct node_t
{
char data;
struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, const char *argv[])
{
//定义结构体类型所对应的变量
link_node_t head;
link_node_t A;
A.data = 'A';
A.next = NULL;
link_node_t B = {'B',NULL};
link_node_t C = {'C',NULL};
link_node_t D = {'D',NULL};
head.next = &A;
A.next = &B;
B.next = &C;
C.next = &D;
link_list_t p = &head;
while(p->next!= NULL)
{
p = p->next;
printf("%c\n",p->data);
//'A'
//p = &B;
//'B'
//p =&C;
//'c'
//p = &D;
}
return 0;
}A B C D有头链表中的第一个头节点的数据域无效，但指针域有效
无头链表中的每一个节点的数据域和指针域都是有效的
在对有头单链表进行操作之前，需要对其进行初始化，即创建一个空的有头单链表。
初始化只需malloc开辟一个结点大小的空间存放有头单向链表头结点，然后让有头单链表中的头结点指针域指向NULL即可。
想要找到单向链表并对其进行操作就需要一个指针来指向单向链表的头结点，该指针就是头指针p
5. 有头单向链表操作函数
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;
//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.遍历单向链表
void ShowLinkList(link_node_t *p);
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
//6.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
//7.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
//8.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
//9.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
//10.转置链表
void ReverseLinkList(link_node_t *p);
//11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif开辟空间存放头结点，并返回指向头结点的指针，该指针称为该链表的头指针。
5.1. 长度
使用伪头指针遍历单向链表
有头单向链表的遍历条件：H->next != NULL
无头单向链表的遍历条件：H != NULL
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{
int len = 0;
while(p->next != NULL)
{
p = p->next;
len++;
}
return len;
}#include "linklist.h"
int main(int argc, const char *argv[])
{
link_list_t p = CreateEpLinkList();
//尾插
InsertIntoPostLinkList(p,0,996);
InsertIntoPostLinkList(p,1,520);
InsertIntoPostLinkList(p,2,666);
ShowLinkList(p);
//头插
InsertIntoPostLinkList(p,0,88);
ShowLinkList(p);
//中间插
InsertIntoPostLinkList(p,2,77);
ShowLinkList(p);
printf("led = %d\n",LengthLinkList(p));
return 0;
}led = 55.2. 插入
假设要在有头单向链表的post位置插入一个新的结点。
post类比下标，即从0开始。
解题思想：
1、先遍历找到要插入节点的前一个节点，假设这个节点为A；A的下一个节点为B；
将C插入A与B之间；
2、先让C的指针域指向B；
3、再让A的指针域指向C；
容错判断 [0, len]
post不能小于0post不能大于链表的长度
移动伪头指针，使其指向插入位置的前一个结点
for (int i = 0; i < post; i++)
p = p->next;
生成新结点
link_list_t pnew = malloc()
pnew->data = data;
pnew->next = NULL;
插入（先后再前）
pnew->next = p->next;
p->next = pnew;
#include "linklist.h"
link_node_t *CreateEpLinkList()
{
link_list_t p = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == p)
{
printf("malloc error\n");
return NULL;
}
//成员初始化
p->next = NULL;
return p;
}
//2.向单向链表的指定位置插入数据
p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data)
{
if(post < 0 || post > LengthLinkList(p))
{
printf("InsertIntoPostLinkList post error\n");
return -1;
}
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == pnew)
{
printf("InsertIntoPostLinkList malloc pnew error\n");
return -1;
}
//初始化pnew节点
pnew->data = data;
pnew->next = NULL;
//遍历到插入位置的前一个位置
int i;
for(i = 0; i < post; i++)
{
p = p->next;
}
//插入动作
pnew->next = p->next;
p->next = pnew;
return 0;
}
//3.遍历单向链表
void ShowLinkList(link_node_t *p)
{
while(p->next != NULL)
{
p = p->next;
printf("%d ",p->data);
}
printf("\n");
}
#if 1
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{
int len = 0;
while(p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
#endif#include "linklist.h"
int main(int argc, const char *argv[])
{
link_list_t p = CreateEpLinkList();
//尾插
InsertIntoPostLinkList(p,0,996);
InsertIntoPostLinkList(p,1,520);
InsertIntoPostLinkList(p,2,666);
ShowLinkList(p);
//头插
InsertIntoPostLinkList(p,0,88);
ShowLinkList(p);
//中间插
InsertIntoPostLinkList(p,2,77);
ShowLinkList(p);
printf("led = %d\n",LengthLinkList(p));
return 0;
}
996 520 666
88 996 520 666
88 996 77 520 666
led = 55.3. 查找
思路：
post = 0- 遍历
-
- 如果相等
return post - 不等
post++
- 如果相等
- 遍历结束没找到
return -1
//8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data)
{
if(IsEpLinkList(p))
{
printf("SearchDataLinkList failed\n");
return -1;
}
int i = 0;
while(p->next != NULL)
{
p = p->next;
if(p->data == data)
{
return i;
}
i++;
}
return -1;
}
修改修改指定位置数据
post类比下标，即从0开始。
//7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data)
{
if(post < 0 || post >=LengthLinkList(p) || IsEpLinkList(p))
{
printf("ChangePostLinkList failed\n");
return -1;
}
int i;
for(i = 0; i <= post; i++)
{
p = p->next;
}
p->data = data;
return 0;
}5.4. 删除
如果将伪头指针遍历指向删除结点，那么其前驱的指针域next无法访问。
虽然能够知道前驱指针域next的值，但无法对其进行修改。
前驱指针域next的值就是移动以后的H，虽能知道其值是H，但无法修改前驱的next。
删除结点会涉及三个结点：
- 删除位置结点
- 前驱
- 后继
因为是单向链表，故只能从前往后找，不能从后往前找。这三个结点，谁在最前面，就让头指针遍历指向它。
5.4.1. 删除指定位置
由于链表中的每个结点都是malloc开辟出来的，故需要一个PDel指针指向结点，将其释放掉。
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)//5(4)
{
//判断表是否为空||位置是否合理
if(IsEpLinkList(p) || post < 0 || post > LengthLinkList(p)-1)
{
printf("DeletePostLinkList error\n");
return -1;
}
//1)遍历到删除节点的前一个节点
int i;
for(i = 0; i < post; i++)
{
p = p->next;
}
//2)pdel指向要删除的节点
link_list_t pdel = p->next;
//3)将删除节点的前一个节点和删除节点的后一个节点链接到一起
p->next = pdel->next;
free(pdel);
pdel = NULL;
return 0;
}
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{
return p->next == NULL;
}#include "linklist.h"
int main(int argc, const char *argv[])
{
link_list_t p = CreateEpLinkList();
//尾插
InsertIntoPostLinkList(p,0,996);
InsertIntoPostLinkList(p,1,520);
InsertIntoPostLinkList(p,2,666);
ShowLinkList(p);
//头插
InsertIntoPostLinkList(p,0,88);
ShowLinkList(p);
//中间插
InsertIntoPostLinkList(p,2,77);
ShowLinkList(p);
//printf("led = %d\n",LengthLinkList(p));
DeletePostLinkList(p,2);
ShowLinkList(p);
return 0;
}996 520 666
88 996 520 666
88 996 77 520 666
88 996 520 666 5.4.2. 删除指定数据
与删除指定位置思想一致。一定要让伪头指针在删除结点前。故使用头指针指向结点的后继的数据域与指定数据进行比较。
在链表中插入或删除某个结点，不需要移动元素，仅修改指针即可。
//7.删除单向链表中出现的指定数据(节点free)
//data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
{
link_list_t pdel = NULL;
if(IsEpLinkList(p))
{
printf("DeletePostLinkList error\n");
return -1;
}
while(p->next != NULL)
{
if(p->next->data == data)
{
pdel = p->next;
p->next = pdel->next;
free(pdel);
pdel = NULL;
}
else
{
p = p->next;
}
}
return 0;
}#include "linklist.h"
int main(int argc, const char *argv[])
{
link_list_t p = CreateEpLinkList();
//尾插
InsertIntoPostLinkList(p,0,996);
InsertIntoPostLinkList(p,1,520);
InsertIntoPostLinkList(p,2,666);
ShowLinkList(p);
//头插
InsertIntoPostLinkList(p,0,88);
ShowLinkList(p);
//中间插
InsertIntoPostLinkList(p,2,77);
ShowLinkList(p);
//printf("led = %d\n",LengthLinkList(p));
DeletePostLinkList(p,2);
ShowLinkList(p);
DeleteDataLinkList(p,520);
ShowLinkList(p);
return 0;
}996 520 666
88 996 520 666
88 996 77 520 666
88 996 520 666
88 996 666 5.5. 清空
5.6. 转置
头-1-2-3-4-5 ---> 头-5-4-3-2-1
步骤：
头 1-2-3-4-5
头-1 2-3-4-5
头-2-1 3-4-5
头-3-2-1 4-5
思想：将链表拆成空的有头单向链表和一个无头单向链表
遍历无头单向链表，将每个结点头插进有头单向链表中
单向循环链表
约瑟夫问题
设编号为1，2，……n的n个人围坐一圈，约定编号为k (1≤k≤n)的人从1开始报数，数到m的那个人出列。它的下一位继续从1开始报数，数到m的人出列，依次类推，最后剩下一个为猴王。
假设n=6总共6人，k=1从第一个人开始，m=5，每次从1数到5。
第一轮报数：从1号开始，数5个数，数完5个数，5号被杀死，第一轮报数后，剩余人数如下。
第二轮报数：
第三轮：
第四轮：
第五轮：
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkListNode
{
int data;
struct LinkListNode *next;
} LLN, *LL;
int main(int argc, const char *argv[])
{
int i;
LL PDel = NULL; // 用于指向被删除节点
LL PTail = NULL; // 永远指向当前链表的尾
LL PNew = NULL; // 永远指向新创建的节点
LL H = NULL;
int all_num = 6; // 猴子总数
int start_num = 1; // 从几号猴子开始数
int kill_num = 5; // 数到几杀死猴
// 1.创建出一个单向循环链表
//(1)创建有all_num个节点的单向链表
H = (LL)malloc(sizeof(LLN));
if (NULL == H)
{
perror("H malloc failed");
return -1;
}
H->data = 1;
H->next = NULL;
PTail = H; // 尾指针指向当前的第一个结点
for (i = 2; i <= all_num; i++)
{
// 创建新的节点
PNew = (LL)malloc(sizeof(LLN));
if (NULL == PNew)
{
perror("PNew malloc failed");
return -1;
}
// 将新结点装上数据
PNew->data = i;
PNew->next = NULL;
// 将新结点链接到链表尾
PTail->next = PNew; // 链接到链表的尾
PTail = PNew; // 尾指针继续指向当前链表的尾
}
// 1 2 3 4 5 6
//(2)将头指针保存到链表的尾形成单向循环链表
PTail->next = H; // 形成单向循环链表
// 2.开始杀猴子
//(1)将头指针移动到开始猴子的号码处
for (i = 0; i < start_num - 1; i++)
H = H->next;
//(2)循环进行杀猴子
while (H != H->next) // 终止：就剩一个猴子,只有一个节点
{
// 将头指针移动到即将删除节点的前一个节点
for (i = 0; i < kill_num - 2; 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;
}双向链表
单向链表
有头
无头
单向循环链表
链式栈 （无头单向链表）
链式队列（有头单向链表）
以上链表均只能从头往后找。即结点只有数据域和一个指向后继结点的指针域next。
双向链表即可以从前往后或者从后往前找，这就意味着链表的结点就不能只有一个指针域next了，还需要一个指向前驱结点的指针域prior。
1. 概念
- 逻辑结构：线性结构
- 物理结构：链式存储结构
2. 接口实现
2.1. 定义操作双向链表的结构体
//双向链表的节点定义
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指向下一个节点的指针 prior 先前的
struct node_t *prior;//指向前一个节点的指针 next 下一个
}link_node_t,*link_list_t;
//将双向链表的头指针和尾指针封装到一个节点体里
//思想上有点像学的链式队列
typedef struct doublelinklist
{
link_list_t head; //指向双向链表的头指针
link_list_t tail; //指向双向链表的尾指针
int len; //用来保存当前双向链表的长度
}double_node_t,*double_list_t;假如链表有一百个结点那么长，想要删除第98个结点，如果结构体中有链表的长度，可以更加方便的使用尾指针进行操作。
2.2. 创建空的双向链表
- 开辟空间存放操作双向链表的结构体
- 对结构体成员初始化的同时开辟空间存放头结点
- 初始化头结点
- 返回结构体指针
//1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{
//1.申请保存头指针和尾指针的空间
double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
if(NULL == p)
{
perror("createEmptyDoubleLinkList malloc failed");
return NULL;
}
//2.将头指针和尾指针同时指向头节点，因为当前链表为空
p->len = 0;//当前链表的长度为0
p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == p->head)
{
perror("p->head malloc failed!!");
return NULL;
}
//3.对双向链表的头结点进行初始化
p->head->prior = NULL;
p->head->next = NULL;
//返回结构体指针
return p;
}2.3. 插入
PNew
|
post前驱====新结点====post结点
| |
PTemp->prior PTemp插入位置有以下情况：
- 尾插
- 中间插
-
- 中间插前半段（包括头插） 移动头指针
- 中间插后半段 移动尾指针
为什么将头插归类到中间插前半段中？
因为只有尾插涉及到的是终端结点和新结点这两个结点。
头插涉及到的是头结点、新结点、零号结点这三个节点。
步骤：
- 判错
- 创新
- 尾插
- 中间插
中间插前半段
中间插后半段
无论前半段还是后半段，伪指针指向插入位置post结点后，其插入代码都是一样的
中间插口诀
- 先前再后
temp->prior按兵不动
或
- 先新再旧
temp->prior按兵不动
//2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{
int i;
link_list_t temp = NULL;//用来临时保存head或tail的位置
//1.容错判断
if(post < 0 || post > p->len)
{
printf("insertIntoDoubleLinkList post failed!!");
return -1;
}
//2.创建一个新的节点，用来保存插入的数据
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == pnew)
{
perror("pnew malloc failed");
return -1;
}
pnew->data = data;//将参数上插入的数据装入节点
pnew->prior = NULL;
pnew->next = NULL;
//3.将节点链接到链表中
//先对插入位置进行判断，分两种情况
if(post == p->len)//说明插入的是链表的尾巴
{
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew;//将尾指针再次移动到当前链表的尾，永远指向尾
}
else//0-len-1
{
//(1)将temp移动到插入位置
if(post < p->len/2)//说明在前半段
{
temp = p->head;//用头向后移动
for(i = 0; i < post+1; i++)
temp = temp->next;
}
else//说明插入位置在后半部分
{
temp = p->tail;//用尾向前移动
for(i = 0; i < p->len-post-1; i++)
temp = temp->prior;
}
//(2)进行插入操作(先连前面，再连后面)
pnew->prior = temp->prior;
temp->prior->next = pnew;
pnew->next = temp;
temp->prior = pnew;
}
p->len++;//链表的长度+1
return 0;
}2.4. 打印
遍历双向链表
- 从前往后
- 从后往前
//3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{
link_list_t temp = NULL;
printf("正向遍历:");
temp = p->head;
while(temp->next != NULL)//类似于遍历有头单向链表
{
temp = temp->next;
printf("%d ",temp->data);
}
printf("\n");
printf("反向遍历:");
temp = p->tail;
while(temp != p->head)//类似于遍历无头单向链表
{
printf("%d ",temp->data);
temp = temp->prior;
}
printf("\n---------------------------------\n");
}
2.5. 删除
2.5.1. 删除指定位置
前驱 post 后继
| | |
PTemp->prior PTemp PTemp->next
1. 给前驱的next域赋值
2. 给后继的prior域赋值//4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{
int i;
link_list_t temp = NULL;//临时用来保存头或尾指针
//1.容错处理
if(post < 0 || post >= p->len)
{
printf("deletePostDoubleLinkList post failed!!\n");
return -1;
}
//2.对删除位置进行分析，分为两种情况
if(post == p->len-1)//删除的是链表最后一个节点
{
//(1)将尾指针向前移动一个位置
p->tail = p->tail->prior;
//(2)释放被删除节点，也就是最后一个节点
free(p->tail->next);
//(3)将最后一个节点与链表断开
p->tail->next = NULL;
}
else
{
//将temp移动到删除位置
if(post < p->len/2)//说明在前半段
{
temp = p->head;
for(i = 0; i < post+1; i++)
temp = temp->next;
}
else//说明在后半段
{
temp = p->tail;
for(i = 0; i < p->len-1-post; i++)
temp = temp->prior;
}
//进行删除操作
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
temp = NULL;
}
//3.双向链表的长度-1
p->len--;
return 0;
}
//5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{
return p->len == 0;
}
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{
return p->len;
}2.6. 修改
修改指定位置的数据
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p,int post, datatype data)
{
link_list_t temp = NULL;
int i;
//1.容错判断
if(post < 0 || post >= p->len)
{
printf("changeDataDoubleLinkList post is failed!!\n");
return -1;
}
//2.将temp移动到修改数据的位置
if(post < p->len/2)
{
temp = p->head;
for(i = 0; i < post+1; i++)
temp = temp->next;
}
else
{
temp = p->tail;
for(i = 0; i < p->len-post-1; i++)
temp = temp->prior;
}
//3. 修改数据
temp->data = data;
return 0;
}双向循环链表
思想和单向循环一样，只需要将双向链表尾的next和头的prior双向链接即可。
#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;
}