数据结构之双向链表

1.定义结点类型typedef struct dnode { DataType_t data; struct dnode* ppre; struct dnode* pnext; }Dnode_t;双向链表在单向链表的基础上多一个头指针指向前一个节点的地址//双向链表对象类型 typedef struct dlink { Dnode_t* phead; int clen; }Dlink_t;2.创建链表2.1创建空链表Dlink_t* create_doulink() { Dlink_t* pdlink malloc(sizeof(Dlink_t)); if (NULL pdlink) { printf(malloc error\n); return NULL; } pdlink-phead NULL; pdlink-clen 0; return pdlink; }2.2创建结点Dnode_t* create_node(DataType_t data) { Dnode_t* pnode malloc(sizeof(Dnode_t)); if (NULL pnode) { printf(malloc error); return NULL; } pnode-data data; pnode-pnext NULL; pnode-ppre NULL; return pnode; }malloc 申请空节点空间data 不需要赋值最好赋值空白节点不存放数据主要为了保证链表操作的便利性pnext 赋值为 NULL表示该节点为最后一个节点尾结点ppre 赋值为 NULL,表示指向上一个节点地址的指针返回节点地址3.双向链表的相关操作3.1判断链表是否为空int is_empty_dlink(Dlink_t* pdlink) { if (NULL pdlink-phead) { return 1; } return 0; }3.2插入数据头插法插入数据int insert_doulink_head(Dlink_t* pdlink, DataType_t data) { Dnode_t* pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { pnode-pnext pdlink-phead; pdlink-phead-ppre pnode; pdlink-phead pnode; } pdlink-clen; return 0; }尾插法插入数据int insert_doulink_tail(Dlink_t* pdlink, DataType_t data) { Dnode_t* pnode create_node(data); Dnode_t* ptmp pdlink-phead; if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext pnode; pnode-ppre ptmp; } pdlink-clen; return 0; }3.3删除数据头删法删除数据int delete_doulink_head(Dlink_t* pdlink) { if (is_empty_dlink(pdlink)) { return -1; } Dnode_t* ptmp pdlink-phead; pdlink-phead ptmp-pnext; if (ptmp-pnext ! NULL) { ptmp-pnext-ppre NULL; } free(ptmp); pdlink-clen--; return 0; }尾删法删除数据int delete_doulink_tail(Dlink_t* pdlink) { Dnode_t* ptmp pdlink-phead; if (NULL ptmp) { return -1; } if (is_empty_dlink(pdlink)) { return -1; } while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } if (ptmp-ppre ! NULL) { ptmp-ppre-pnext NULL; } else { pdlink-phead NULL; } free(ptmp); pdlink-clen--; return 0; }3.4遍历双向链表void show_doulink(Dlink_t* pdlink, int dir) { if (is_empty_dlink(pdlink)) { return; } Dnode_t* ptmp pdlink-phead; if (dir) { while (ptmp) { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-pnext; } } else { while (ptmp-pnext) { ptmp ptmp-pnext; } while (ptmp) { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-ppre; } } printf(\n); }3.5查询链表中某个结点此处示例是用名字查找Dnode_t* find_doulink_node(Dlink_t* pdlink, char* name) { if (is_empty_dlink(pdlink)) { return NULL; } Dnode_t* ptmp pdlink-phead; while (ptmp ! NULL) { if (0 strcmp(ptmp-data.name, name)) { return ptmp; } ptmp ptmp-pnext; } return NULL; }3.6修改链表中某一结点的数据int change_doulink_score(Dlink_t* pdlink, char* name, int score) { Dnode_t* ptmp NULL; ptmp find_doulink_node(pdlink, name); if (ptmp ! NULL) { ptmp-data.score score; return 0; } return -1; }3.7删除链表中某一结点int delete_doulink_node(Dlink_t* pdlink, char* name) { if (is_empty_dlink(pdlink)) { return -1; } Dnode_t* ptmp NULL; ptmp find_doulink_node(pdlink, name); if (NULL ptmp) { return -1; } if (NULL ptmp-ppre) { delete_doulink_head(pdlink); } else if (NULL ptmp-pnext) { delete_doulink_tail(pdlink); } else { ptmp-ppre-pnext ptmp-pnext; ptmp-pnext-ppre ptmp-ppre; pdlink-clen--; } free(ptmp); return 0; }3.8删除链表void destroy_doulink(Dlink_t* pdlink) { while (!is_empty_dlink(pdlink)) { delete_doulink_head(pdlink); } free(pdlink); }4.内核链表4.1定义Linux内核中所使用到的一种链表结构使用同一种结构可以存储不同类型的链表普通链表链表结点中包含数据内核链表数据中包含链表结点4.2结构描述创建创建空白结点插入申请结点并按照循环链表插入插入的链表结点首地址即数据结点首地址访问结点通过遍历找到每个结点的首地址强制类型转换获得对应数据空间首地址