数据结构——双向链表

双向链表的结构：

双向链表由链表对象，头结点，中间结点以及尾结点组成每一部分结点结构或是指针内容存在差异，需要牢记双向链表的结构，双向链表的结构使我们能够通过一个中间节点找到它前后的结点，这是与单向链表的最大区别。

需要熟练掌握的基本操作：

让我们在记牢理解双向链表的结构以后直接上代码练习

封装双向链表：1：头文件定义双向链表的结构

#ifndef __DOULINK_H__
#define __DOULINK_H__
//双向链表存储的数据类型
typedef struct stu
{int id;char name[32];int score;
}Data_type_t;/*双向链表的结点类型*/
typedef struct dounode
{Data_type_t data;struct dounode *ppre;  //指向前驱结点的指针struct dounode *pnext; //指向后继结点的指针
}DNode_t;/*双向链表对象类型*/
typedef struct doulink
{DNode_t *phead;   //双向链表头结点地址int clen;         //双向链表结点个数
}DLink_t;
extern DLink_t *create_doulink();
extern int insert_doulink_head(DLink_t *pdlink, Data_type_t data);
extern int is_empty_doulink(DLink_t *pdlink);
extern void doulink_for_each(DLink_t *pdlink, int dir);
extern int insert_doulink_tail(DLink_t *pdlink, Data_type_t data);
extern int delete_doulink_head(DLink_t *pdlink);
extern int delete_doulink_tail(DLink_t *pdlink);

使用头插法构建双向链表：头插法是重点

#include "doulink.h"
#include <stdio.h>
#include <stdlib.h>DLink_t *create_doulink()
{DLink_t *pdlink= malloc(sizeof(DLink_t));if (NULL == pdlink){printf("malloc error");return NULL;}pdlink->phead = NULL;pdlink->clen = 0;return pdlink;
}int is_empty_doulink(DLink_t *pdlink)
{return NULL == pdlink->phead;}int insert_doulink_head(DLink_t *pdlink, Data_type_t data)
{DNode_t *pnode = malloc(sizeof(DNode_t));if (NULL == pnode){printf("malloc error");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_doulink(pdlink)){pdlink->phead = pnode;}else{pnode->pnext = pdlink->phead;pdlink->phead->ppre = pnode;pdlink->phead = pnode;}pdlink->clen++;return 0;
}

主函数部分：

#include <stdio.h>
#include "doulink.h"int main(void)
{Data_type_t stus[5] = {{1, "zhangsan", 99},{2, "lisi", 100}, {3, "wangwu", 90}, {4, "maliu", 56}, {5, "tianqi", 66}};DLink_t *pdlink = create_doulink();if (NULL == pdlink){return -1;}insert_doulink_head(pdlink, stus[0]);insert_doulink_head(pdlink, stus[1]);insert_doulink_head(pdlink, stus[2]);insert_doulink_tail(pdlink, stus[3]);insert_doulink_tail(pdlink, stus[4]);

构建好双向链表后，对于双向链表的各种基本操作：

遍历打印：dir1顺序打印，direlse逆序打印

void doulink_for_each(DLink_t *pdlink, int dir)
{if (is_empty_doulink(pdlink)){return ;}DNode_t *ptmp = pdlink->phead;if (dir){while (ptmp != NULL){printf("%d %s %d\n", ptmp->data.id, ptmp->data.name, ptmp->data.score);ptmp = ptmp->pnext;}}else{while (ptmp->pnext != NULL){ptmp = ptmp->pnext;}while (ptmp != NULL){printf("%d %s %d\n", ptmp->data.id, ptmp->data.name, ptmp->data.score);ptmp = ptmp->ppre;}}printf("\n");
}

尾插法

int insert_doulink_tail(DLink_t *pdlink, Data_type_t data)
{DNode_t *pnode = malloc(sizeof(DNode_t));if (NULL == pnode){printf("malloc error\n");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_doulink(pdlink)) //空链表情况{pdlink->phead = pnode;}else //非空链表情况{DNode_t *ptmp = pdlink->phead;while (ptmp->pnext != NULL){ptmp = ptmp->pnext;}ptmp->pnext = pnode;pnode->ppre = ptmp;}pdlink->clen++;return 0;
}

删除头结点：

int delete_doulink_head(DLink_t *pdlink)
{if (is_empty_doulink(pdlink)){return -1;}DNode_t *pdel = pdlink->phead;pdlink->phead = pdel->pnext;if (pdlink->phead != NULL){pdlink->phead->ppre = NULL;}free(pdel);pdlink->clen--;return 0;
}

删除尾结点：

int delete_doulink_tail(DLink_t *pdlink)
{if (is_empty_doulink(pdlink)){return -1;}DNode_t *ptmp = pdlink->phead;if (1 == pdlink->clen){free(ptmp);pdlink->phead = NULL;}else{while (ptmp->pnext != NULL){ptmp = ptmp->pnext;}ptmp->ppre->pnext = NULL;free(ptmp);}pdlink->clen--;return 0;
}

销毁链表

int destory_dblink(dbLINK_T *plink)
{if(is_empty_doubleLink(plink)){printf("空结点");return -1;}dbNODE_T *p=plink->phead;while(p!=NULL){p=p->pnext;head_node_delet(plink);}free(plink);return 0;}

== 这个销毁方法无法销毁主函数里面创造的plink==，，这时我们使用二级指针销毁主函数以及封装函数里的双向链表

查找结点并返回其地址

dbNODE_T *findnode(dbLINK_T *plink,char name[20])
{if(is_empty_doubleLink(plink)){printf("空链表，无结点可查");return NULL;}dbNODE_T *p=plink->phead;while (p!=NULL){if(strcmp(p->data.name,name)==0){return p;}p=p->pnext;}printf("查找不到该学生");    return NULL;
}

根据名字修改学生分数

int findnodeAndChangeScore(dbLINK_T *plink,char name[20],int newscore)
{if(is_empty_doubleLink(plink)){printf("空链表，无结点可查");return -1;}dbNODE_T *p=plink->phead;while (p!=NULL){if(strcmp(p->data.name,name)==0){p->data.score=newscore;return 0;}p=p->pnext;}printf("查找不到该学生");    return -1;
}

查找结点并删除该结点：

int findnodeAndDELETnode(dbLINK_T *plink, char name[20])
{if(is_empty_doubleLink(plink)){printf("空链表，无结点可查\n");return -1;}dbNODE_T *p = plink->phead;// 遍历整个链表查找节点while (p != NULL){if(strcmp(p->data.name, name) == 0){// 情况1：删除头节点if(p->ppre == NULL){head_node_delet(plink);}// 情况2：删除尾节点else if(p->pnext == NULL){p->ppre->pnext = NULL;free(p);plink->clen--;}// 情况3：删除中间节点else{p->ppre->pnext = p->pnext;p->pnext->ppre = p->ppre;free(p);plink->clen--;}printf("找到并删除该学生节点\n");return 0;}p = p->pnext;}// 遍历完未找到节点printf("无法找到该同学，无法删除结点\n");return -1;
}

主函数

#include<stdio.h>
#include"doublelink.h"
int main(void)
{STUDENT_T stus[5]={{1,"zhangsan",99},{2,"lisi",100},{3,"wangwu",90},{4,"maliu",56},{5,"tianqi",66}};dbLINK_T *plink=creatlink(plink);if(plink==NULL){printf("mallol error");return -1;}creat_db_NODE(plink,stus[0]);creat_db_NODE(plink,stus[1]);creat_db_NODE(plink,stus[2]);creat_db_NODE(plink,stus[3]);creat_db_NODE(plink,stus[4]);/*  insert_dblink_tail(plink,stus[4]);leach_dblink(plink,1);head_node_delet(plink);deletLink_fromTheLastNODE(plink);*/leach_dblink(plink,1);/*  dbNODE_T *ret=findnode(plink,"wangwu");if(ret==NULL){return -1;}printf("学生名：%p\n",ret);*//*  findnodeAndChangeScore(plink,"lisi",50);leach_dblink(plink,1);*/findnodeAndDELETnode(plink,"wangwu");leach_dblink(plink,1);destory_dblink(plink);//  leach_dblink(plink,0);return 0;
}