数据结构与算法5-双向链表数据结构与算法5-双向链表

双向链表双向链表有一点不同于单向链表. 单向链表只能是一个顺序方向进行查找, 而双向链表可以对下一个以及上一个进行查找

文章图片
image.png
从上图中可以看到，双向链表中各节点包含以下 3 部分信息（如下图所示）：

指针域 prior：用于指向当前节点的直接前驱节点；
数据域 data：用于存储数据元素。
指针域 next：用于指向当前节点的直接后继节点；

文章图片
image.png

1.双链表的节点结构

typedef struct Node { struct Node *prior; //指向直接前驱节点 ElemType data; //数据域 struct Node *next; //指向直接后继节点 } Node;

2. 创建双向链表

//5.1 创建双向链表 Status createLinkList(LinkList *L){ //*L 指向头结点 *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) return ERROR; (*L)->prior = NULL; (*L)->next = NULL; (*L)->data = https://www.it610.com/article/-1; //新增数据 LinkList p = *L; for(int i=0; i < 10; i++){//1.创建1个临时的结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->prior = NULL; temp->next = NULL; temp->data = https://www.it610.com/article/i; //2.为新增的结点建立双向链表关系 //① temp 是p的后继 p->next = temp; //② temp 的前驱是p temp->prior = p; //③ p 要记录最后的结点的位置,方便下一次插入 p = p->next; }return OK; }

3.遍历双向链表

//2、遍历双向链表 void printfLinkLisk(LinkList list){printf("遍历链表：\n"); if (list == NULL || list->next == NULL) { printf("这是一个空链表\n"); return; } LinkList p = list; //判断next是否全部正确 printf("根据next从前往后遍历："); while (p->next) { printf("%d ",p->next->data); p = p->next; } printf("\n"); //判断prior是否全部正确 printf("根据prior从后往前遍历："); while (p != list) { printf("%d ",p->data); p = p->prior; } printf("\n"); }

4.双向链表插入元素因为我的双向链表有头节点，所以只有两种添加情况：

添加至表的中间位置

同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 4 个步骤(步骤中的顺序中 3 必须放到 1 和 2 后面，其它顺序可变)，如下图所示：

将priorNode->next节点的prior指向新节点；
将新节点->next指向原来的priorNode->next；
将priorNode->next指向新节点；
新节点的prior指向priorNode。

文章图片
image.png

添加至表尾

与添加到表中间的步骤只需要少掉步骤 1。因为priorNode->next是Null，不能用它执行操作，否则会崩溃。

//5.3 双向链表插入元素 Status ListInsert(LinkList *L, int i, ElemType data){//1. 插入的位置不合法为0或者为负数 if(i < 1) return ERROR; //2. 新建结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = https://www.it610.com/article/data; temp->prior = NULL; temp->next = NULL; //3.将p指向头结点! LinkList p = *L; //4. 找到插入位置i直接的结点 for(int j = 1; j < i && p; j++) p = p->next; //5. 如果插入的位置超过链表本身的长度 if(p == NULL){ returnERROR; }//6. 判断插入位置是否为链表尾部; if (p->next == NULL) {p->next = temp; temp->prior = p; }else { //1?? 将p->next 结点的前驱prior = temp p->next->prior = temp; //2?? 将temp->next 指向原来的p->next temp->next = p->next; //3?? p->next 更新成新创建的temp p->next = temp; //4?? 新创建的temp前驱 = p temp->prior = p; }returnOK; }

5.删除双向链表指定位置上的结点根据索引删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。

文章图片
image.png

//5.4 删除双向链表指定位置上的结点 Status ListDelete(LinkList *L, int i, ElemType *e){int k = 1; LinkList p = (*L); //1.判断双向链表是否为空,如果为空则返回ERROR; if (*L == NULL) { return ERROR; }//2. 将指针p移动到删除元素位置前一个 while (k < i && p != NULL) { p = p->next; k++; }//3.如果k>i 或者 p == NULL 则返回ERROR if (k>i || p == NULL) { returnERROR; }//4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数 LinkList delTemp = p->next; *e = delTemp->data; //5. p->next 等于要删除的结点的下一个结点 p->next = delTemp->next; //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p; if (delTemp->next != NULL) { delTemp->next->prior = p; }//7.删除delTemp结点 free(delTemp); return OK; }

6.删除双向链表指定的元素 【数据结构与算法5-双向链表】根据值删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。

//5.5 删除双向链表指定的元素 Status LinkListDeletVAL(LinkList *L, int data){LinkList p = *L; //1.遍历双向循环链表 while (p) {//2.判断当前结点的数据域和data是否相等,若相等则删除该结点 if (p->data =https://www.it610.com/article/= data) {//修改被删除结点的前驱结点的后继指针,参考图上步骤1?? p->prior->next = p->next; //修改被删除结点的后继结点的前驱指针,参考图上步骤2?? if(p->next != NULL){ p->next->prior = p->prior; } //释放被删除结点p free(p); //退出循环 break; }//没有找到该结点,则继续移动指针p p = p->next; }return OK; }

7.在双向链表中查找元素

//5.6.1 在双向链表中查找元素 int selectElem(LinkList L,ElemType elem){LinkList p = L->next; int i = 1; while (p) { if (p->data =https://www.it610.com/article/= elem) { return i; }i++; p = p->next; }return-1; }

8.在双向链表中更新结点

//5.6.2 在双向链表中更新结点 Status replaceLinkList(LinkList *L,int index,ElemType newElem){ LinkList p = (*L)->next; for (int i = 1; i < index; i++) { p = p->next; }p->data = https://www.it610.com/article/newElem; return OK; }