数据结构（双向链表）代码详细注释

双向链表

1》双向链表的定义

双向链表也叫双链表，与单向链表不同的是，每一个节点有三个区域组成：两个指针域，一个数据域。

前指针域：存储前驱节点的内存地址

后指针域：存储后继节点的内存地址

数据域：存储节点数据

单个双向链表节点：

完整的双向链表
2》特性

逻辑结构：线性结构

存储结构：链式存储

操作：增删改查
3》主要功能

创空：
插入：
删除：
按数据删除：
4》代码展示

#include <stdio.h>
#include <stdlib.h>typedef struct aouble // 重定义节点结构体
{int data;             // 数据域struct aouble *next;  // 存下一个节点地址的指针域struct aouble *prior; // 存上一个节点地址的指针域
} Double_t, *Double_p;typedef struct doubleLink // 重定义指针结构体
{Double_p head; // 指向链表头节点的指针Double_p tail; // 指向链表尾节点的指针int len;       // 链表的长度
} Doublelink_t, *Doublelink_p;
// 将头尾指针以及长度封装的一个结构体里面用来操作整个双向链表/*创空双向链表*/
Doublelink_p Create()
{Doublelink_p p = (Doublelink_p)malloc(sizeof(Doublelink_t)); // 定义一个指针指向开辟的指针结构体if (NULL == p)                                               // 容错判断{printf("malloc lost\n");return NULL;}p->len = 0;                                             // 初始化双向链表的长度为0p->head = p->tail = (Double_p)malloc(sizeof(Double_t)); // 初始化指针结构体的两个头尾指针指向新开辟的节点结构体if (NULL == p->head)                                    // 容错判断{printf("malloc lost\n");return NULL;}p->head->next = NULL;  // 通过指针结构体找到节点结构体，初始化节点结构体的后指针域为NULLp->head->prior = NULL; // 通过指针结构体找到节点结构体，初始化节点结构体的后指针域为NULLreturn p;              // 返回指针结构体
}/*入栈*/
int Push(Doublelink_p p, int post, int data) // post 是要插入的位置，data 是要插入的数据
{if (post < 0 || post > p->len) // 容错判断{printf("post error\n");return -1;}Double_p p_new = (Double_p)malloc(sizeof(Double_t)); // 开辟一个新的节点，定义一个新的节点指针取接受这块空间if (NULL == p_new)                                   // 容错判断{printf("malloc lost\n");return -1;}p_new->data = data;  // 初始化新节点的数据域p_new->next = NULL;  // 初始化新节点的后节点指针域p_new->prior = NULL; // 初始化新节点的前节点指针域// 1)从尾部插入if (post == p->len) // 插入的位置等于链表的长度，说明在尾部插入{p->tail->next = p_new;  // 让尾节点的后节点指针域等于新节点p_new->prior = p->tail; // 让新节点的前节点指针域等于尾节点    这两步的作用就是把新节点链接到尾节点上p->tail = p_new;        // 让尾节点移动到新节点处，使新节点成为尾节点}// 2)从中间插入else{Double_p temp = NULL; // 定义一个节点类型指针待用，用来遍历链表// 插入位置在前半段if (post < p->len / 2) // 判断要插入位置是否在前半段{temp = p->head;                 // 让temp指向头节点for (int i = 0; i <= post; i++) // for循环往后遍历，找到要插入的位置temp = temp->next;          // 向后移动}// 插入位置在后半段else{temp = p->tail;                         // 让temp指向尾节点for (int i = p->len - 1; i > post; i--) // for循环往前遍历，找到要插入的位置temp = temp->prior;                 // 向前移动}// 把新节点插入到temp和它前面节点之间    temp现在就是要插入位置的节点p_new->prior = temp->prior; // 让新节点的前指针域存temp的前一个节点地址temp->prior->next = p_new;  // 让temp的前一个节点的后指针域存新节点的地址      把前面两条线连起来p_new->next = temp;  // 新节点的后指针域存temp的地址temp->prior = p_new; // temp的前指针域存新节点的地址   把后面两条线连起来}p->len++; // 链表长度加一return 0;
}/*遍历*/
void show(Doublelink_p p)
{Double_p temp = NULL; // 定义一个节点类型指针待用，用来遍历链表printf("正向遍历： ");temp = p->head->next; // 让temp 指向头节点的下一个节点，即第一个有效节点while (temp != NULL)  //当temp 指向不是NULL 时，进入循环继续遍历{printf("%d ", temp->data);//打印当前temp节点的数据temp = temp->next;//temp向后移动}printf("\n");printf("反向遍历： ");temp = p->tail;//让temp指向链表的尾节点while (temp != p->head) // 相当于遍历无头链表{printf("%d ", temp->data);//打印当前temp节点的数据temp = temp->prior;//temp向前移动}printf("\n");
}/*判空*/
int Empty(Doublelink_p p)
{return p->len == 0;//p-> len为0 说明链表长度为空
}/*删除双向链表元素*/
int Delete(Doublelink_p p, int post)//post 要删除节点的位置
{if (Empty(p) || post < 0 || post >= p->len)//判空和位置容错判断{printf("Empty || post error\n");return -1;}Double_p p_del = NULL;//定义一个p_del置空待用，用于指向删除节点//1)删除尾节点if (post == p->len)//删除位置等于链表长度，说明要删除的时尾节点{p->tail = p->tail->prior;//让尾节点向前移动free(p->tail->next);//释放之前的尾节点p->tail->next = NULL;//把新的尾节点的后指针域置空}//2)删除中间节点else{if (post < p->len / 2)//要删除节点在前半段{p_del = p->head;//让p_del指向头节点for (int i = 0; i <= post; i++)//从头节点开始往后遍历到要删除的节点处p_del = p_del->next;//p_del向后移动}else//要删除的节点再在后半段{p_del = p->tail;//让p_del 指向尾节点for (int i = p->len - 1; i > post; i--)//从尾节点开始向前遍历到要删除的节点处p_del = p_del->prior;//p_del向前移动}//3)开始删除  p_del此时就是要删除的节点p_del->prior->next = p_del->next;//让p_del 的前一个节点的后指针域存p_del 的下一个节点p_del->next->prior = p_del->prior;//让p_del的后一个节点的前指针域存p_del的上一个节点    就是让他们跨过p_del连接在一起free(p_del);//然后把p_del给释放掉p_del = NULL;//将p_del置空}p->len--;//删除一个节点，链表长度减一return 0;
}/*删除指定数据的节点*/
int DeleteSame(Doublelink_p p, int data)//data 指定数据
{if (Empty(p))//先判空{printf("list is Empty\n");return -1;}Double_p p_del = NULL;//定义一个指针置空 待用   用于指向删除节点Double_p t = NULL;//定义一个指针置空  待用  用于遍历链表 t = p->head->next;//因为头节点的数据域无效，所以要先跳过头节点，让 t 指向头节点下一个节点while (t != NULL)//如果 t 所指向节点不为空，则进入循环进行判断，数据是否为指定数据，是否要删除{if (t->data == data)//如果 t 所指的数据是否是指定的数据{//1)尾部删除if (t == p->tail)//要删除的节点在链表的尾{//和删除尾部节点的操作相同p->tail = p->tail->prior;free(p->tail->next);p->tail->next = NULL;}//2)中间节点删除else{//和删除中间的节点的操作相同p_del = t;p_del->prior->next = p_del->next;p_del->next->prior = p_del->prior;t = p_del->next;free(p_del);}p->len--;//链表长度减一}else//如果 t 所指的数据不是指定的数据{t = t->next;// t 继续向后遍历}}
}/*查询*/
int Search(Doublelink_p p, int data)//data  查询的数据   查询数据，返回下标
{if (Empty(p))//先判空{printf("list is Empty\n");return -1;}Double_p q = p->head->next;//定义一个节点类型指针指向头节点下一个节点   因为头节点数据域无效int i = 0;//定义一个变量表示下标while (q != NULL)//当 q 指向节点不是NULL，进入循环，遍历链表，判断数据是否相等{if (q->data == data)// q 所指向节点数据和要查询数据相等return i;//返回当前下标q = q->next;// q 所指向节点数据和要查询数据不相等，则 q 继续向后遍历i++;//下标加一}return -1;
}/*修改*/
int Modify(Doublelink_p p, int post, int data)//post 修改的位置  data 要修改成的数据
{if (Empty(p) || post < 0 || post >= p->len)//判空和位置是否合理 ，容错判断{return -1;}Double_p t = NULL;//定义一个指针 t 置空待用  用于遍历链表if (post < p->len / 2)   //要修改数据在前半段{t = p->head;// t 指向头节点for (int i = 0; i <= post; i++)//循环向后遍历，找到要修改的位置节点{t = t->next;//向后移动}}else//要修改数据在后半段{t = p->tail;// t 指向尾节点for (int i = p->len - 1; i > post; i--)//循环向前遍历，找到要修改的位置节点{t = t->prior;//向前移动}}t->data = data;//修改 t 指向节点的数据return 0;
}int main(int argc, char const *argv[])
{Doublelink_p H = Create();//创建一个空双向链表Push(H, 0, 1);Push(H, 1, 2);Push(H, 2, 3);Push(H, 3, 50);Push(H, 3, 100);Push(H, 3, 100);Push(H, 3, 100);//插入数据printf("插入后\n");show(H);Modify(H, 2, 300);//修改数据printf("\n修改 2 位置 为 300\n");show(H);DeleteSame(H, 100);//删除指定数据节点printf("\n删除数据100的节点\n");show(H);Delete(H, 2);//删除指定位置节点printf("\n删除第 2 个数据后\n");show(H);printf("\n数据100 的下标 %d\n", Search(H, 100));//查询指定数据下标printf("\n数据50 的下标 %d\n", Search(H, 50));return 0;
}