企业官网建设流程全解析

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结构描述

创建：创建空白结点

插入：申请结点，并按照循环链表插入（插入的链表结点首地址即数据结点首地址）

访问结点：通过遍历找到每个结点的首地址，强制类型转换获得对应数据空间首地址