双向链表
//双向链表的节点定义
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指向下一个节点的指针 next 下一个
struct node_t *prior;//指向前一个节点的指针 prior 先前的
}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;
操作函数
1）创建一个空的双向链表
2）双向链表中间插入
3)双向链表尾插
4）双线链表中间删除
5）双线链表删除最后一个节点
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data; // 数据域
struct node_t *next; // 指向下一个节点的指针 next 下一个
struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} 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;
// 1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{
// 1.开辟存放头尾指针结构体的空间
double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
if (p == NULL)
{
perror("createEmptyDoubleLinkList err");
return NULL;
}
// 2.初始化（开辟头节点的空间）
p->len = 0;
p->tail = p->head = (link_list_t)malloc(sizeof(link_node_t));
if (p->tail == NULL)
{
perror("p->tail malloc err");
return NULL;
}
// 3.初始化头节点
p->tail->next = NULL;
p->tail->prior = NULL;
return p;
}
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{
// 0.容错判断
if (post < 0 || post > p->len)
{
perror("insertIntoDoubleLinkList err");
return -1;
}
// 1.开辟一个新节点存放数据，初始化
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if (pnew == NULL)
{
perror("pnew malloc err");
return -1;
}
pnew->data = data;
pnew->prior = NULL;
pnew->next = NULL;
// 2.将新节点插入链表
// 分两种情况
// 尾插
if (post == p->len)
{
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew; // 移动尾指针
}
else // 中间插入
{
// 1)temp指针指向被插入位置
link_list_t temp = NULL;
if (post < p->len / 2) // 前半段(从前向后移动)
{
temp = p->head;
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段（从后向前移动）
{
temp = p->tail;
for (int i = 0; i < p->len - 1 - post; i++)
temp = temp->prior;
}
// 2)进行插入操作（先连前面，再连后面）
temp->prior->next = pnew;
pnew->prior = temp->prior;
temp->prior = pnew;
pnew->next = temp;
}
// 链表长度+1
p->len++;
return 0;
}
// 3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{
printf("正向遍历：");
link_list_t temp = p->head;
while (temp->next != NULL)
{
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n-------------------\n");
printf("反向遍历：");
temp = p->tail;
while (temp != p->head)
{
printf("%d ", temp->data);
temp = temp->prior;
}
printf("\n-------------------\n\n");
}
// 5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{
return p->len == 0;
}
// 4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{
// 1.容错判断
if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
{
perror("deletePostDoubleLinkList err");
return -1;
}
// 2.对删除位置进行判断
if (post == p->len - 1) // 尾删
{
p->tail = p->tail->prior; // 向前移动尾指针
free(p->tail->next); // 释放被删除节点
p->tail->next = NULL;
}
else // 中间删
{
// 1)将temp移动到被删除位置
link_list_t temp = NULL;
if (post < p->len / 2) // 前半段
{
temp = p->head;
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段
{
temp = p->tail;
for (int i = 0; i < p->len - 1 - post; i++)
temp = temp->prior;
}
// 2)进行删除操作
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
temp = NULL;
}
// 链表长度-1
p->len--;
return 0;
}
// 6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{
return p->len;
}
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p, datatype data)
{
link_list_t h = p->head;
int post = 0;
while (h->next != NULL)
{
h = h->next;
if (h->data == data)
return post;
post++;
}
return -1;
}
// 8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
{
// 1.容错判断
if (post < 0 || post >= p->len)
{
perror("changeDataDoubleLinkList err");
return -1;
}
// 2.将temp移动到被修改位置
link_list_t temp = NULL;
if (post < p->len / 2) // 前半段
{
temp = p->head;
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段
{
temp = p->tail;
for(int i=0;i<p->len-1-post;i++)
temp=temp->prior;
}
// 3.修改数据
temp->data = data;
return 0;
}
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{
link_list_t h = p->head->next;
link_list_t pdel = NULL;
//1.遍历无头单向链表
while (h!= NULL)
{
if(h->data == data) //删除
{
if(h == p->tail)//尾删
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next=NULL;
h = NULL;//结束遍历
}
else//中间删除
{
h->prior->next = h->next;
h->next->prior = h->prior;
pdel = h;
h = h->next;//继续遍历
free(pdel);
pdel = NULL;
}
p->len--;//长度-1
}
else//不删除
h=h->next;
}
return 0;
}
int main(int argc, char const *argv[])
{
double_list_t p = createEmptyDoubleLinkList();
for (int i = 1; i <= 5; i++)
insertIntoDoubleLinkList(p, i - 1, i);
showDoubleLinkList(p); // 1 2 3 4 5
insertIntoDoubleLinkList(p, 1, 200);
showDoubleLinkList(p); // 1 200 2 3 4 5
deletePostDoubleLinkList(p, 2);
showDoubleLinkList(p); // 1 200 3 4 5
printf("%d post is %d\n", 200, searchPostDoubleLinkList(p, 200)); // 1
changeDataDoubleLinkList(p,1,300);
showDoubleLinkList(p);//1 300 3 4 5
deleteDataDoubleLinkList(p,300);
showDoubleLinkList(p);//1 3 4 5
while (!isEmptyDoubleLinkList(p))
{
deletePostDoubleLinkList(p, 0);
}
free(p->head);
p->head = NULL;
free(p);
p = NULL;
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;
}