……接上文
6. 双向链表
6.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;
6.2 双向链表相关操作
需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点都要与其前驱节点建立两次联系，分别是：
(1) 将新节点的 prior 指针指向直接前驱节点。
(2) 将直接前驱节点的 next 指针指向新节点。
1) 创建空的双向链表
//1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList()
{// 1. 申请空间存放头尾指针结构体
double_list_p p = (double_list_p)malloc(sizeof(double_list_t));if(NULL == p){perror("createEmptyDoubleLinkList");return NULL;}
p->len = 0;//2.初始化，头尾指针分别指向开辟头节点，因为当前链表为空
p->head = p->tail = (link_node_p)malloc(sizeof(link_node_t));if(p->head == NULL){perror("p->head malloc failed!");return NULL;} p->head->next = NULL;
p->head->prior = NULL;return p;
}
2) 指定位置插入
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{
link_node_p temp = NULL; // 用来临时保存head或者tail的位置if (post < 0 || post > p->len){perror("insertIntoDoubleLinkList err");return -1;} link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if (pnew == NULL){perror("pnew malloc err");return -1;}// 初始化新节点
pnew->data = data;
pnew->prior = NULL;
pnew->next = NULL;// 插入链表的尾巴if (post == p->len){
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew; // 移动尾指针}// 中间差else{if (post < p->len / 2) // 前半段{// temp移动到插入位置
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;}// 2) 进行插入操作(先连前面，再练后面)
pnew->prior = temp->prior;
temp->prior->next = pnew;
pnew->next = temp;
temp->prior = pnew;}
p->len++; // 插入完成，链表长度+1return 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----------------\n");
}
4) 判断双向链表是否为空
//4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p)
{return p->len == 0;
}
5) 删除双向链表指定位置
//5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p,int post)
{
link_node_p temp = NULL;// 1. 容错判断if(isEmptyDoubleLinkList(p) || post >= p->len || post < 0){error("deletePostDoubleLinkList err\n");return -1;}//2.对删除位置进行分析，分为两种情况if(post == p->len-1) // //删除的是链表最后一个节点{// 1)将尾指针向前移动一个位置
p->tail = p->tail->prior;// 2)释放被删除节点，也就是最后一个节点free(p->tail->next);// 3)将最后一个节点与链表断开
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)
{if(isEmptyDoubleLinkList(p) || post >= p->len || post < 0){perror("changeDataDoubleLinkList err");return -1;}
link_node_p temp = NULL;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->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;
h = 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;}}
}
main函数代码：
int main(int argc, char const *argv[])
{// int i;
double_list_p p = createEmptyDoubleLinkList();for (int i = 0; i < 5; i++){insertIntoDoubleLinkList(p, i, i);}showDoubleLinkList(p);deletePostDoubleLinkList(p, 2);printf("len is %d\n", lengthDoubleLinkList(p));showDoubleLinkList(p);deletePostDoubleLinkList(p, 3);showDoubleLinkList(p);printf("1 post is: %d\n", searchPostDoubleLinkList(p, 1));int len = lengthDoubleLinkList(p);for (int i = 0; i < len; i++){deletePostDoubleLinkList(p, 0);}printf("len is %d\n", lengthDoubleLinkList(p));showDoubleLinkList(p);printf("is Empty? %d\n", isEmptyDoubleLinkList(p));free(p);
p = NULL;return 0;
}未完待续……
