一、双向链表1.1 特性逻辑结构线性结构存储结构链式存储操作增删改查//双向链表的节点定义 typedef int datatype; typedef struct node_t { datatype data;//数据域 struct node_t *next;//指向下一个节点的指针 next struct node_t *prior;//指向前一个节点的指针 prior }link_node_t,*link_node_p; //将双向链表的头指针和尾指针封装到一个结构体里 //思想上有点像学的链式队列 typedef struct doublelinklist { link_node_p head; //指向双向链表的头指针 link_node_p tail; //指向双向链表的尾指针 int len; //用来保存当前双向链表的长度 }double_list_t,*double_list_p;1.2 双向链表相关的操作需要注意的是与单链表不同双链表创建过程中每创建一个新节点都要与其前驱节点建立两次联系分别是将新节点的 prior 指针指向直接前驱节点。将直接前驱节点的 next 指针指向新节点。1.2.1 代码实现doublelinklist.h#ifndef __DOUBLELINKLIST_H__ #define __DOUBLELINKLIST_H__ // 双向链表的节点定义 typedef int datatype; typedef struct node_t { datatype data; // 数据域 struct node_t *next; // 指向下一个节点的指针 next 先前的 struct node_t *prior; // 指向前一个节点的指针 prior 下一个 } link_node_t, *link_node_p; // 将双向链表的头指针和尾指针封装到一个结构体里 // 思想上有点像学的链式队列 typedef struct doublelinklist { link_node_p head; // 指向双向链表的头指针 link_node_p tail; // 指向双向链表的尾指针 int len; // 用来保存当前双向链表的长度 } double_list_t, *double_list_p; // 1.创建一个空的双向链表 double_list_p createEmptyDoubleLinkList(); // 2.向双向链表的指定位置插入数据 post位置 data数据 int insertIntoDoubleLinkList(double_list_p p, int post, datatype data); // 3.遍历双向链表 void showDoubleLinkList(double_list_p p); // 4.判断双向链表是否为空 int isEmptyDoubleLinkList(double_list_p p); // 5.删除双向链表指定位置数据 int deletePostDoubleLinkList(double_list_p p, int post); //6.求双向链表的长度 int lengthDoubleLinkList(double_list_p p); //7.查找指定数据出现的位置 data被查找的数据 int searchPostDoubleLinkList(double_list_p p,datatype data); // 8.修改指定位置的数据,post修改的位置 data被修改的数据 int changeDataDoubleLinkList(double_list_p p, int post, datatype data); // 9.删除双向链表中的指定数据 data代表删除所有出现的data数据 /* 思想从头节点后节点开始用指针h遍历相当于遍历无头链表遇到需要删除节点的就用h指向它然后删除如果不需要删除则h继续往后走一个。这里因为是双向链表可以找到前驱所以不需要每次指向被删除节点的前一个然后跨过了。 */ void deleteDataDoubleLinkList(double_list_p p, datatype data); #endif1创建空双向链表// 1.创建一个空的双向链表 double_list_p createEmptyDoubleLinkList() { // 1. 申请空间存放头尾指针结构体 double_list_p p (double_list_p)malloc(sizeof(double_list_t)); if(NULL p) { printf(createEmptyDoubleLinkList p malloc err\n); return NULL; } // 2. 初始化申请开辟头节点让头尾指针指向头节点 p-len 0; p-head p-tail (link_node_p)malloc(sizeof(link_node_t)); if(NULL p-head) { printf(p-head malloc err\n); return NULL; } // 3. 初始化头节点 p-head-prior NULL; p-head-next NULL; return p; }2指定位置插入// 2.向双向链表的指定位置插入数据 post位置 data数据 int insertIntoDoubleLinkList(double_list_p p, int post, datatype data) { link_node_p pnew NULL; // 用于存放新创建节点的地址 link_node_p temp NULL; // 用来临时保存head或者tail的位置 // 1. 容错判断 if (post 0 || post p-len) { printf(insertIntoDoubleLinkList err\n); return -1; } pnew (link_node_p)malloc(sizeof(link_node_t)); if (NULL pnew) { printf(insertIntoDoubleLinkList pnew err\n); return -1; } pnew-data data; pnew-prior NULL; pnew-next NULL; // 2. 将新节点插入到链表中 if (post p-len) // 插入链表的尾巴 { pnew-prior p-tail; p-tail-next pnew; p-tail pnew; } 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-prior; } // 进行插入操作(先连前在连后) pnew-prior temp-prior; temp-prior-next pnew; pnew-next temp; temp-prior pnew; } p-len; // 插入完成链表长度1 return 0; }3双向链表遍历// 3.遍历双向链表 void showDoubleLinkList(double_list_p p) { link_node_p temp NULL; printf(正向遍历\n); temp p-head; while (temp-next ! NULL) { temp temp-next; printf(%d , temp-data); } printf(\n); printf(反向遍历:\n); temp p-tail; while(temp ! p-head) { printf(%d , temp-data); temp temp-prior; } printf(\n); }4判断双向链表是否为空// 4.判断双向链表是否为空 int isEmptyDoubleLinkList(double_list_p p) { // return p-head p-tail; // return p-head-next NULL; return p-len 0; }5删除双向链表指定位置的数据// 5.删除双向链表指定位置数据 int deletePostDoubleLinkList(double_list_p p, int post) { link_node_p temp NULL; // 1. 容错判断 if (isEmptyDoubleLinkList(p) || post 0 || post p-len) { printf(deletePostDoubleLinkList err\n); return -1; } // 2. 对删除位置进行分析, 分为两种情况 if (post p-len - 1) // 删除是链表中最后一个节点 { // 先将尾指针向前移动一个位置 p-tail p-tail-prior; // 释放最后一个节点 free(p-tail-next); // 将链表最后一个节点断开 p-tail-next NULL; } 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-prior; } // 进行删除操作 temp-prior-next temp-next; temp-next-prior temp-prior; free(temp); temp NULL; } // 3. 双向链表的长度-1 p-len--; return 0; }6求双向链表长度//6.求双向链表的长度 int lengthDoubleLinkList(double_list_p p) { return p-len; }7查找指定数据出现的位置//7.查找指定数据出现的位置 data被查找的数据 int searchPostDoubleLinkList(double_list_p p,datatype data) { link_node_p temp p-head; int post 0; // 记录的位置 while(temp-next ! NULL) { temp temp-next; if(temp-data data) return post; post; } return -1; }8修改指定位置的数据// 8.修改指定位置的数据,post修改的位置 data被修改的数据 int changeDataDoubleLinkList(double_list_p p, int post, datatype data) { link_node_p temp NULL; // 1. 容错判断 if (post 0 || post p-len || isEmptyDoubleLinkList(p)) { printf(changeDataDoubleLinkList err\n); return -1; } // 2. 将temp移动到修改的位置 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-prior; } // 3. 修改数据 temp-data data; return 0; }9删除双向链表中指定的所有数据// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据 /* 思想从头节点后节点开始用指针h遍历相当于遍历无头链表 遇到需要删除节点的就用h指向它然后删除如果不需要删除则h继续往后走一个。 这里因为是双向链表可以找到前驱所以不需要每次指向被删除节点的前一个然后跨过了。 */ void deleteDataDoubleLinkList(double_list_p p, datatype data) { link_node_p h p-head-next; link_node_p pdel NULL; while (h ! NULL) { if (h-data data) // 相等 { // 删除节点 if (h p-tail) // 尾节点 { // 先将尾指针向前移动一个位置 p-tail p-tail-prior; // 释放最后一个节点 free(p-tail-next); // 将链表最后一个节点断开 p-tail-next NULL; } else // 中间节点 { h-prior-next h-next; h-next-prior h-prior; pdel h; h h-next; free(pdel); pdel NULL; } p-len--; } else // 不相等 { h h-next; } } }二、双向循环链表#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_node_p; typedef struct doublelinklist { link_node_p head; link_node_p tail; }double_list_t,*double_list_p; int main(int argc, const char *argv[]) { int i; int all_num 8;//猴子总数 int start_num 3;//从3号猴子开始数 int kill_num 3;//数到几杀死猴子 link_node_p h NULL; link_node_p pdel NULL;//用来指向被杀死猴子的节点 printf(请您输入猴子的总数开始号码出局号码:\n); scanf(%d%d%d,all_num,start_num,kill_num); //1.创建一个双向的循环链表 double_list_p p (double_list_p)malloc(sizeof(double_list_t));//申请头指针和尾指针 if(NULL p) { perror(malloc failed); return -1; } p-head p-tail (link_node_p)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_node_p pnew (link_node_p)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 1; i start_num; i) h h-next; printf(start is:%d\n,h-data); while(h-next ! h)//当h-next h 就剩一个节点了循环结束 { //(2)将h移动到即将杀死猴子号码的位置 for(i 1; i kill_num; 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); pdel NULL; } printf(猴王是%d\n,h-data); return 0; }