20、数据结构笔记之二十双向列表.docx

20、蛤 蟆 的 数据结构笔记之十九双向链表本篇名言：“ 人的生命，似洪水奔流，不遇着岛屿和暗礁，难以激 起美丽的浪花 ”之前实现的都是单向列表，那么我们来看下双向链表1.双向链表双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点一般我们都构造双向循环链表2.定义结构体typedef struct DoubleLinkedList { int data; struct DoubleLinkedList *pre; struct DoubleLinkedList *next; }DlinkedList_Node;一个节点需要指向前面节点同时指向后面节点，需要二个指针3.创建链表具体过程是输入一个值，如果不是 65535，则创建一个节点，前向指针指向 head,head 指向该节点如果是 65535 则打印输入结束Head->pre=NULL创建链表最后返回一个指向双向链表的指针头DlinkedList_Node* createDLink() { DlinkedList_Node *head,*p,*s; int x; head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); p = head; while(1) { printf("please input the data: \n"); scanf("%d",&x); if(x != 65535) { s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); s ->data = x; s-> pre = p; p->next = s; p=s; } else { printf("\n数据输入结束\n"); break; } } p->next = NULL; head = head ->next; head->pre = NULL; return head; } 4.插入节点DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head,int i) { DlinkedList_Node *p,*temp; p = head; temp = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); temp ->data = i; if(i data)//比头结点数据小，插入到链表头部 { head = temp; head->next = p;//此处p为原来的head head->pre = NULL; p->pre = head;//此处p为原来的head return head; } while(p != NULL && i > p->data)//寻找合适的插入位置 { if(p->next)p = p->next; elsebreak;} if( p && i data)//在链表中间某处找到合适插入位置 { temp ->next = p; temp ->pre = p->pre; p ->pre->next = temp; p ->pre = temp; return head; } else//没有找到合适的位置，只有将数据插入到链表尾部 { p->next = temp; //遍历到链表尾部，p==NULL temp ->pre = p; temp ->next = NULL; return head; } } 5.删除节点DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head,int i) { DlinkedList_Node *p; p = head; if(p->data == i) { head = p->next; head->pre = NULL; free(p); return head; } while(p) { if(p->data == i) { p->pre->next = p->next; p->next->pre = p->pre; free(p); return head; } p = p->next; } printf("没有找到想要删除的数据\n"); return head; } 6.Main 函数插入相等的数字会出乱子的，大家自己可以去运行查看。

创建链表，然后插入 2 个数，接着删除 2 个数字，一个在链表中，一个不在，每次都输出一下，最后释放节点int main() { DlinkedList_Node *head; head = createDLink(); printDLink(head); head = insertDlinkedList_Node(head,1012); printDLink(head); head = insertDlinkedList_Node(head,10); printDLink(head); head = deleteDlinkedList_Node(head,1991);printDLink(head); head = deleteDlinkedList_Node(head,2); printDLink(head); freelink(head);} 7.源码#include #include typedef struct DoubleLinkedList { int data; struct DoubleLinkedList *pre; struct DoubleLinkedList *next; }DlinkedList_Node; //建立链表 DlinkedList_Node* createDLink() { DlinkedList_Node *head,*p,*s; int x; head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); p = head; while(1) { printf("please input the data: \n"); scanf("%d",&x); if(x != 65535) { s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); s ->data = x; s-> pre = p; p->next = s; p=s; } else { printf("\n数据输入结束\n"); break; } } p->next = NULL; p = head;head = head ->next; head->pre = NULL; free(p);return head; } //顺序、反序打印链表 void printDLink(DlinkedList_Node *head) { DlinkedList_Node *p,*s; p = head; printf("正序输出双向链表：\n"); while(p) { printf("%d ",p->data); s = p; p = p->next; } printf("\n 逆序输出双向链表: \n"); while(s) { printf("%d ",s->data); s = s->pre; } printf("\n \n"); } //删除一个结点 DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head,int i) { DlinkedList_Node *p; p = head; if(p->data == i) { head = p->next; head->pre = NULL; free(p); return head; } while(p) { if(p->data == i) { p->pre->next = p->next; p->next->pre = p->pre; free(p); return head; } p = p->next; } printf("没有找到想要删除的数据\n"); return head; } //插入一个结点 DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head,int i) { DlinkedList_Node *p,*temp; p = head; temp = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); temp ->data = i; if(i data)//比头结点数据小，插入到链表头部 { head = temp; head->next = p;//此处p为原来的head head->pre = NULL; p->pre = head;//此处p为原来的head return head; } while(p != NULL && i > p->data)//寻找合适的插入位置 { if(p->next)p = p->next; elsebreak;} if( p && i data)//在链表中间某处找到合适插入位置 { temp ->next = p; temp ->pre = p->pre; p ->pre->next = temp; p ->pre = temp; return head; } else//没有找到合适的位置，只有将数据插入到链表尾部 { p->next = temp; //遍历到链表尾部，p==NULL temp ->pre = p; temp ->next = NULL; return head; } } void freelink(DlinkedList_Node *head) {DlinkedList_Node *p,*temp;p = head; while(p)//寻找合适的插入位置 { temp = p;p = p->next;free(temp);} }int main() { DlinkedList_Node *head; head = createDLink(); printDLink(head); head = insertDlinkedList_Node(head,1012); printDLink(head); head = insertDlinkedList_Node(head,10); printDLink(head); head = deleteDlinkedList_Node(head,1991);printDLink(head); head = deleteDlinkedList_Node(head,2); printDLink(head); freelink(head);} 。