数据结构----双向链表

        存储结构：链式存储
        操作：增删改查

2.函数的操作

创空

双链表从中间插入

双向链表尾插

删除中间节点

删除尾节点

#include <stdio.h>
#include <stdlib.h>
typedef int datatype; // 重定义数据类型
typedef struct linklist
{datatype data;           // 数据域struct linklist *next;   // 指针域，指向下一个地址struct linklist *perior; // 指针域，指向前一个地址
} node_t, *node_p;
typedef struct
{node_p head; // 指向头结点node_p tail; // 指向尾节点int len;     // 记录链的长度
} node;
node *CreateEmpty() // 创建一个空的双向链表
{node *p = (node *)malloc(sizeof(node)); // 开辟一个存放头尾指针的空间if (NULL == p){printf("Cteate err");return 0;}p->len = 0;                                         // 初始化链表长度p->head = p->tail = (node_p)malloc(sizeof(node_t)); // 开辟一个链表头结点if (NULL == p->head){printf("p->head err");return NULL;}p->head->next = p->head->perior = NULL; // 初始化return p;
}
int Insert(node *p, int post, int data) // 插入数据，post为要插入的位置，data为要插入的数据
{node_p temp = NULL;            // 定义一个指针，用来存放头/尾指针if (post < 0 || post > p->len) // 判断插入位置是否超出范围{printf("Post err");return -1;}node_p p_new = (node_p)malloc(sizeof(node_t)); // 对插入的数据开辟空间if (NULL == p_new)                             // 判断是否开辟成功{printf("P_new err");return -1;}p_new->data = data; // 初始化新节点p_new->next = NULL;p_new->perior = NULL;if (post == p->len) // 如果插入位置在最后，使用尾插法{p->tail->next = p_new;p_new->perior = p->tail;p->tail = p_new;}else{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 = p->len - 1; i > post; i--)temp = temp->perior;}temp->perior->next = p_new; // 将新节点连接到链表中p_new->perior = temp->perior;temp->perior = p_new;p_new->next = temp;}p->len++;return 0;
}
int IsEmpty(node *p) // 判空
{return p->len == 0;
}
int show(node *p) // 输出数据
{if (IsEmpty(p)) // 判空{printf("show err");return -1;}// 顺序遍历，从头节点向后遍历printf("正序遍历\n");node_p temp = p->head->next;while (temp){printf("%d ", temp->data);temp = temp->next;}printf("\n");// 逆序遍历，从尾节点向前遍历printf("逆序遍历\n");temp = p->tail;while (temp != p->head){printf("%d ", temp->data);temp = temp->perior;}printf("\n");
}
int Delete(node *p, int post) // 根据位置删除数据。post为要删除的位置
{node_p temp = NULL;if (IsEmpty(p) || post < 0 || post >= p->len) // 判断删除数据位置是否合理{printf("del err");return -1;}if (post == p->len - 1) // 如果要删除尾节点，使用以下方法{node_p p_del = p->tail;p->tail = p->tail->perior;p->tail->next = NULL;free(p_del);p_del = NULL;}else // 删除中间节点{if (post < p->len / 2) // 当删除位置在前半段时，从头开始向后遍历{temp = p->head->next;for (int i = 0; i < post; i++)temp = temp->next;}else // 当删除位置在后半段时，从后向前遍历{temp = p->tail;for (int i = p->len - 1; i > post; i--)temp = temp->perior;}temp->perior->next = temp->next; // 删除后将删除节点的前后节点相连temp->next->perior = temp->perior;free(temp); // 将被删除节点释放temp = NULL;}p->len--;return 0;
}
int DeleteData(node *p, int data)//删除所有出现的该数据的节点，data为要删除节点的数据
{if (IsEmpty(p))//判空{printf("del data err");return -1;}node_p temp = NULL;temp = p->head->next;//跳过头节点node_p p_del = NULL;while (temp)//循环遍历链表{if (temp->data == data)//数据域等于data时进入判断{if (temp == p->tail)//如果为尾节点时{p_del = temp;temp = temp->perior;free(p_del);p_del = NULL;}else//如果是中间节点{p_del = temp;p_del->perior->next = p_del->next;p_del->next->perior = p_del->perior;temp = temp->next;free(p_del);p_del = NULL;}}elsetemp = temp->next;//更新temp}return 0;
}
int Modify(node *p, int post, int data) // 修改数据，post为修改位置，data为要修改的数据
{if (IsEmpty(p) || post < 0 || post >= p->len) // 判断修改位置是否合理{printf("Modify err");return -1;}node_p temp = NULL;if (post < p->len / 2) // 当修改位置在前半段时，从头开始向后遍历{temp = p->head->next;for (int i = 0; i < post; i++)temp = temp->next;}else // 当修改位置在后半段时，从后向前遍历{temp = p->tail;for (int i = p->len - 1; i > post; i--)temp = temp->perior;}temp->data = data; // 修改数据return 0;
}
int Search(node *p, int data) // 根据数据查找数据第一次出现的下标
{node_p temp = p->head->next;int post = 0;//记录下标while (temp)//循环遍历链表{if (temp->data == data)//返回第一次出现data的下标return post;temp = temp->next;post++;}return -1;
}
int main(int argc, char const *argv[])
{node *p = CreateEmpty();Insert(p, 0, 1);Insert(p, 1, 2);Insert(p, 2, 3);Insert(p, 3, 4);Insert(p, 4, 5);Insert(p, 5, 6);printf("最初的链表\n");show(p);printf("删除指定位置后的链表\n");Delete(p, 1);show(p);printf("修改指定位置后的链表\n");Modify(p, 1, 4);show(p);printf("删除指定数据后的链表\n");DeleteData(p, 4);show(p);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 0while(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;
}