双向链表 PPT课件

图⽂详解双向链表原理
双向链表的主要优点是对于任意给的结点，都可以很轻易的获取其前结点和后结点，其主要缺点是每个结点需要保存next和prev两个属性，因此需要更多的空间开销，同时结点的插⼊与删除操作也将更加耗时，因为需要操作更多的指向操作。

双向链表单个节点结构：
双向链表节点
双向链表的数据结构：
双向链表数据结构
双向链表的插⼊操作
插⼊数据到链表尾部
链表尾部插⼊数据
插⼊数据到链表中间
链表中部插⼊数据
双向列表删除操作
删除链表尾部数据
删除尾部数据
删除链表中间数据
删除中间数据
循环双向列表设计
循环双向链表是在普通双向链表基础上进化得到的。

在普通的双向链表中，如果我们要获取最后⼀个节点的时候，我们只能从头开始遍历，⼀直遍历到最后才能够拿到最后⼀个节点的数据。

⽽循环双向链表会把header的prev指向最后⼀个节点，最后⼀个节点next指向header。

其数据结构如图所⽰：
循环双向链表
循环链表的添加、删除和普通的双向链表是⼀模⼀样的，这⾥就不再赘述。

第8讲 双向链表● 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前趋结点，但时间耗费是O (n) 。

● 如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域prior 。

这样形成的链表中就有两条方向不同的链，我们称之为双向链表。

● 双向链表的结构定义如下：typedef struct DNode{ ElemType data ；struct DNode *prior ，*next ；}DNode, * DoubleList ；● 双向链表的结点结构如图所示。

图：双链表的结点结构注：● 双向链表也是由头指针唯一确定的，● 增加头结点能使双链表的某些运算变得方便● 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。

● 设指针p 指向双链表中某一结点，则有下式成立：p->prior->next = p = p->next->prior●在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，● 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

1、 双向链表的前插操作【算法思想】欲在双向链表第i 个结点之前插入一个的新的结点，则指针的变化情况如图所示：… p …s->prior=p->prior; ①p->prior->next=s;②s->next=p; ③p->prior=s;④【算法描述】int DlinkIns(DoubleList L,int i,ElemType e){DNode *s,*p;… /*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/… /*若位置i合法，则找到第i个结点并让指针p指向它*/s=(DNode*)malloc(sizeof(DNode));if (s){ s->data=e;s->prior=p->prior; ①p->prior->next=s; ②s->next=p; ③p->prior=s; ④r eturn TRUE;}else return FALSE;}2、双向链表的删除操作【算法思想】欲删除双向链表中的第i个结点，则指针的变化情况如图所示：p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);【算法描述】int DlinkDel(DoubleList L,int i,ElemType *e){DNode *p;… /*先检查待插入的位置i 是否合法（实现方法同单链表的删除操作）*/… /*若位置i 合法，则找到第i 个结点并让指针p 指向它*/*e=p->data;p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);return TRUE;}3、 双向循环链表双向链表可以有循环表,称为双向循环链表。

双向链表的建立与释放
首先我们先通过例子来讨论双向链表的建立方法和释放方法。

1． 例子
例如有下列四个结点：
图3-16 双向链表结点示例
我们现在想要把它们链接成一个双向链表，其运行过程如下图所示。

NULL
图3-17 双向链表结点的链接示例
双向链表的释放和单链表的释放方式一样，从首结点开始一个一个的将结点释放，直到下一个结点的指针指向NULL （即到达尾端）为止。

2． 算法思想
（1） 双向链表的建立：
首先声明一个双向链表的首结点head ，并将head->next 和head->prior 设为NULL 。

每输入一个数据就申请一个结点的内存空间，并赋给指针变量new ，把new->next 和new->prior 设为NULL ，并且链接到之前链表的尾端，再将new->prior 指向原链表的尾端。

（2） 双向链表的输出：
和单链表相同。

（3） 双向链表的释放：
和单链表相同。

准备：动态内存分配一、为什么用动态内存分配但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。

比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组：float score[30];但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。

这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。

即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。

这种分配固定大小的内存分配方法称之为静态内存分配。

但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。

所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。

动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。

从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点：1、不需要预先分配存储空间；2、分配的空间可以根据程序的需要扩大或缩小。

二、如何实现动态内存分配及其管理要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数1、malloc函数malloc函数的原型为：void *malloc (unsigned int size)其作用是在内存的动态存储区中分配一个长度为size的连续空间。

其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。

还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。

双向链表的基本操作前⾯学习了如何创建⼀个，本节学习有关双向的⼀些基本操作，即如何在双向链表中添加、删除、查找或更改数据元素。

本节知识基于已熟练掌握双向链表创建过程的基础上，我们继续上节所创建的双向链表来学习本节内容，创建好的双向链表如图 1 所⽰：图 1 双向链表⽰意图双向链表添加节点根据数据添加到双向链表中的位置不同，可细分为以下 3 种情况：添加⾄表头将新数据元素添加到表头，只需要将该元素与表头元素建⽴双层逻辑关系即可。

换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：1. temp->next=head; head->prior=temp;2. 将 head 移⾄ temp，重新指向新的表头；例如，将新元素 7 添加⾄双链表的表头，则实现过程如图 2 所⽰：图 2 添加元素⾄双向链表的表头添加⾄表的中间位置同添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，如图 3 所⽰：1. 新节点先与其直接后继节点建⽴双层逻辑关系；2. 新节点的直接前驱节点与之建⽴双层逻辑关系；图 3 双向链表中间位置添加数据元素添加⾄表尾与添加到表头是⼀个道理，实现过程如下（如图 4 所⽰）：1. 找到双链表中最后⼀个节点；2. 让新节点与最后⼀个节点进⾏双层逻辑关系；图 4 双向链表尾部添加数据元素因此，我们可以试着编写双向链表添加数据的 C 语⾔代码，参考代码如下：1. line * insertLine(line * head,int data,int add){2. //新建数据域为data的结点3. line * temp=(line*)malloc(sizeof(line));4. temp->data=data;5. temp->prior=NULL;6. temp->next=NULL;7. //插⼊到链表头，要特殊考虑8. if (add==1) {9. temp->next=head;10. head->prior=temp;11. head=temp;12. }else{13. line * body=head;14. //找到要插⼊位置的前⼀个结点15. for (int i=1; i<add-1; i++) {16. body=body->next;17. }18. //判断条件为真，说明插⼊位置为链表尾19. if (body->next==NULL) {20. body->next=temp;21. temp->prior=body;22. }else{23. body->next->prior=temp;24. temp->next=body->next;25. body->next=temp;26. temp->prior=body;27. }28. }29. return head;30. }双向链表删除节点双链表删除结点时，只需遍历链表找到要删除的结点，然后将该节点从表中摘除即可。

线性表之双向链表⼀，双向链表的基础知识1.双向链表的概念 双向链表是在单链表的每个结点中，再设置⼀个指向其前驱结点的指针域。

所以在双向链表的每个结点中都有两个指针域，⼀个指向其前驱结点，⼀个指向其后继结点。

2.双向链表实现的难点每⼀个数据元素有两个指针域，⼀个指向其前驱结点，⼀个指向其后继结点。

第⼀个结点的前驱为NULL，最后⼀个节点的后继为NULL。

⼆，双向链表的实现1.双向链表的基本功能(DoubleLinkList.h)# ifndef DOUBLE_LINK_LIST# define DOUBLE_LINK_LIST/* 业务节点 */typedef void Node;/* 链表节点(被包含) */typedef struct DoubleNode{struct DoubleNode * prev;struct DoubleNode * next;}DoubleNode;/* 双向链表 */typedef struct DoubleLinkList{Node * ptr;DoubleNode header;DoubleNode slider;int length;}DoubleLinkList;/* 创建链表 */DoubleLinkList * createList();/* 清空链表 */void clear(DoubleLinkList * list);/* 销毁链表 */void destory(DoubleLinkList * list);/* 链表长度 */int length(DoubleLinkList * list);/* 链表是否为空 */int empty(DoubleLinkList * list);/* 插⼊链表 */void insert(DoubleLinkList * list, int pos, Node * node);/* 删除链表 */Node * del(DoubleLinkList * list, int pos);/* 删除某个元素 */Node * delNode(DoubleLinkList * list, Node * node);/* 获取链表 */Node * get(DoubleLinkList * list, int pos);/* 重置游标 */void resetSlider(DoubleLinkList * list);/* 游标下移 */Node * next(DoubleLinkList * list);/* 游标上移 */Node * prev(DoubleLinkList * list);/* 获取当前游标的结点 */Node * current(DoubleLinkList * list);# endif2.双向链表基本功能的实现(DoubleLinkList.c)# include<stdio.h># include<stdlib.h># include"DoubleLinkList.h"/* 创建链表 */DoubleLinkList * createList(){DoubleLinkList * list = (DoubleLinkList *)malloc(sizeof(DoubleLinkList)); /* 初始化头指针 */list->ptr = &(list->header);/* 初始化头结点 */list->header.next = NULL;list->header.prev = NULL;/* 初始化游标 */list->slider.next = NULL;/* 初始化链表长度 */list->length = 0;return list;}/* 清空链表 */void clear(DoubleLinkList * list){/* 置空头结点 */list->header.next = NULL;list->header.prev = NULL;/* 置空游标 */list->slider.next = NULL;/* 置空链表长度 */list->length = 0;}/* 销毁链表 */void destory(DoubleLinkList * list){if (list != NULL){free(list);list = NULL;}}/* 链表长度 */int length(DoubleLinkList * list){return list->length;}/* 链表是否为空 */int empty(DoubleLinkList * list){if (list->length <= 0){return1;}else {return0;}}/* 插⼊链表 */void insert(DoubleLinkList * list, int pos, Node * node){if (list == NULL){printf("链表为NULL\n");return;}/* 判断插⼊位置合法性 */pos = pos < 0 ? 0 : pos;pos = pos > length(list) ? length(list) : pos;/* 将业务结点转换为链表结点 */DoubleNode * _node = (DoubleNode *)node;/* 判断是否是第⼀次插⼊ */if (length(list) == 0){list->header.next = _node;_node->prev = NULL;_node->next = NULL;list->length++;return;}/* 判断是否是插⼊头部 */if (pos == 0){list->header.next->prev = _node;_node->next = list->header.next;list->header.next = _node;_node->prev = NULL;}else {DoubleNode * posNode = list->header.next; DoubleNode * previous = posNode;for (int i = 0; i < pos; i++){previous = posNode;posNode = posNode->next;}previous->next = _node;_node->prev = previous;posNode->prev = _node;_node->next = posNode;}list->length++;}/* 删除链表 */Node * del(DoubleLinkList * list, int pos){if (list == NULL){printf("链表为NULL\n");return NULL;}if (length(list) == 0){printf("链表长度为0,删除失败\n");return NULL;}/* 判断删除位置合法性 */pos = pos < 0 ? 0 : pos;pos = pos > length(list) ? length(list) : pos;/* 定义删除的返回结点 */DoubleNode * result = NULL;/* 判断是否删除第⼀个 */if (pos == 0){result = list->header.next;list->header.next = list->header.next->next; list->header.next->prev = NULL;}else {DoubleNode * posNode = list->header.next; DoubleNode * previous = posNode;for (int i = 0; i < pos; i++){previous = posNode;posNode = posNode->next;}result = posNode;previous->next = posNode->next;posNode->next->prev = previous;}list->length--;return result;}/* 删除某个元素 */Node * delNode(DoubleLinkList * list, Node * node) {/* 找出该元素位置 */int pos = -1;/* 遍历寻找 */for (int i = 0; i < length(list); i++){Node * tmp = get(list, i);if (tmp == node){pos = i;}}/* 如果未找到退出 */if (pos == -1){printf("未找到该元素\n");return NULL;}/* 找到后删除 */Node * result = del(list, pos);return result;}/* 获取链表 */Node * get(DoubleLinkList * list, int pos){DoubleNode * posNode = list->header.next; for (int i = 0; i < pos; i++){posNode = posNode->next;}return posNode;}/* 重置游标 */void resetSlider(DoubleLinkList * list){list->slider.next = list->header.next;}/* 游标下移 */Node * next(DoubleLinkList * list){if (list->slider.next->next != NULL){DoubleNode * result = list->slider.next; list->slider.next = list->slider.next->next;return result;}return NULL;}/* 游标上移 */Node * prev(DoubleLinkList * list){if (list->slider.next->prev != NULL){DoubleNode * result = list->slider.next; list->slider.next = list->slider.next->prev;return result;}return NULL;}/* 获取当前游标的结点 */Node * current(DoubleLinkList * list){return list->slider.next;}3.双向链表的测试# define _CRT_SECURE_NO_WARNINGS# include<stdio.h># include<string.h># include"DoubleLinkList.h"typedef struct Student{DoubleNode next;char name[64];int age;}Student;int main(){Student s1;strcpy(, "刘备");s1.age = 56;Student s2;strcpy(, "关⽻");s2.age = 40;Student s3;strcpy(, "张飞");s3.age = 38;/* 创建双向链表 */DoubleLinkList * list = createList();/* 插⼊数据 */insert(list, 0, &s1);insert(list, 0, &s2);insert(list, 0, &s3);/* 遍历 */printf("##############基本遍历##############\n");for (int i = 0; i < length(list); i++){Student * stu = (Student *)get(list,i);printf("name = %s,age = %d\n", stu->name, stu->age);}/* 删除 */del(list, 0);printf("##############删除0号位置后遍历##############\n"); for (int i = 0; i < length(list); i++){Student * stu = (Student *)get(list, i);printf("name = %s,age = %d\n", stu->name, stu->age);}/* 删除节点 */delNode(list,&s2);printf("##############删除s2后遍历##############\n");for (int i = 0; i < length(list); i++){Student * stu = (Student *)get(list, i);printf("name = %s,age = %d\n", stu->name, stu->age);}/* 重置游标 */resetSlider(list);Student * ss1 = (Student *)current(list);printf("##############重置游标##############\n");printf("name = %s,age = %d\n", ss1->name, ss1->age);/* 游标下移 */next(list);Student * ss2 = (Student *)current(list);printf("##############游标下移##############\n");printf("name = %s,age = %d\n", ss2->name, ss2->age);next(list);Student * ss3 = (Student *)current(list);printf("##############游标下移##############\n");printf("name = %s,age = %d\n", ss3->name, ss3->age);/* 游标上移 */prev(list);ss2 = (Student *)current(list);printf("##############游标上移##############\n");printf("name = %s,age = %d\n", ss2->name, ss2->age);}。