补充单向链表查找根据数据查找返回找到的节点Node_t *find_link_node(Link_t *plink, Datatype_t data) { if (is_empty_link(plink)) { return NULL; } Node_t *ptmp plink-phead; while (ptmp ! NULL) { if (ptmp-data data) { return ptmp; } ptmp ptmp-pnext; } return NULL; }修改修改旧值为新值int change_link(Link_t *plink, Datatype_t new, Datatype_t old) { Node_t *ptmp NULL; ptmp find_link_node(plink, old); if (ptmp ! NULL) { ptmp-data new; return 0; } return -1; }查找链表中间结点返回中间结点的地址Node_t *find_mid_node(Link_t *plink) { if (is_empty_link(plink)) { return NULL; } Node_t *pfast plink-phead; Node_t *pslow pfast; while (pfast ! NULL) { pfast pfast-pnext; if (NULL pfast) { break; } pfast pfast-pnext; pslow pslow-pnext; } return pslow; }输出Node_t *ptmp NULL; ptmp find_link_node(plink, 4); //查找 if (ptmp ! NULL) { printf(find %d\n, ptmp-data); } change_link(plink, 100, 3); //修改 show_link(plink); ptmp find_mid_node(plink); //查找中间值 if (ptmp ! NULL) { printf(Mid node : %d\n, ptmp-data); }查找倒数第k个节点Node_t *find_last_k_node(Link_t *plink, int k) { if (is_empty_link(plink)) { return NULL; } Node_t *pfast plink-phead; Node_t *pslow pfast; for (int i 0; i k; i) { if (NULL pfast) { return NULL; } pfast pfast-pnext; } while (pfast ! NULL) { pfast pfast-pnext; pslow pslow-pnext; } return pslow; }ptmp find_last_k_node(plink, k); if (ptmp ! NULL) { printf(Last k %d\n, ptmp-data); }单向链表的倒置void reverse_link(Link_t *plink) { if (is_empty_link(plink)) { return ; } Node_t *pinset NULL; Node_t *ptmp plink-phead; plink-phead NULL; while (ptmp ! NULL) { pinset ptmp; ptmp ptmp-pnext; pinset-pnext plink-phead; plink-phead pinset; } return; }单向链表的插入排序void sort_link_insert(Link_t *plink) { if (is_empty_link(plink) || 1 plink-clen) { return; } Node_t *pinsert NULL; Node_t *ptmp plink-phead-pnext; plink-phead-pnext NULL; while (ptmp ! NULL) { pinsert ptmp; ptmp ptmp-pnext; if (pinsert-data plink-phead-data) { pinsert-pnext plink-phead; plink-phead pinsert; } else { Node_t *p plink-phead; while (p-pnext ! NULL p-pnext-data pinsert-data) { p p-pnext; } pinsert-pnext p-pnext; p-pnext pinsert; } } }循环链表单向链表int is_loop_link(Link_t *plink) { Node_t *pfast plink-phead; Node_t *pslow pfast; while (pfast ! NULL) { pfast pfast-pnext; if (NULL pfast) { return 0; } pfast pfast-pnext; pslow pslow-pnext; if (pslow pfast) { return 1; } } return 0; }ptmp plink-phead; while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext plink-phead-pnext-pnext; if (is_loop_link(plink)) { printf(Is a loop link\n); } else { printf(Is not a loop link\n); }单向链表无法通过当前结点访问前驱结点双向链表增加指向前驱结点的指针域即可从前向后遍历也可从后向前遍历双向链表双向链表的创建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; } DNode_t *create_node(DataType_t data) { DNode_t *pnode malloc(sizeof(DNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } pnode-data data; pnode-pnext NULL; pnode-ppre NULL; return pnode; } int is_empty_dlink(DLink_t *pdlink) { if (NULL pdlink-phead) { return 1; } return 0; }双向链表的遍历 void show_pdlink(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); } int main(int argc, const char *argv[]) { DLink_t *pdlink NULL; pdlink create_doulink(); if (NULL pdlink) { return -1; } DataType_t s[] {{1, 张三, 60}, {2, 王麻子, 100},{3, 萧火火, 100}, {4, 韩老魔, 95}}; insert_doulink_head(pdlink, s[0]); insert_doulink_head(pdlink, s[1]); insert_doulink_head(pdlink, s[2]); insert_doulink_head(pdlink, s[3]); show_pdlink(pdlink,1); }双向链表的头插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); if (NULL pnode) { return -1; } DNode_t *ptmp pdlink-phead; 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; }双向链表的头删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) { if (is_empty_dlink(pdlink)) { return -1; } DNode_t *ptmp pdlink-phead; 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; }双向链表--根据name查找到修改成绩int change_doulink(DLink_t *pdlink, char *name, int score) { DNode_t *ptmp NULL; ptmp find_doulink(pdlink, name); if (ptmp ! NULL) { ptmp-data.score score; return 0; } return -1; }段错误调式了解内核链表本质双向循环链表、有头链表不将数据存储在链表结点中而是将结点嵌入到要存储的数据中好处该链表可以用来存储任意类型的数据增强代码的复用性offsetof : 获取链表结点到结构体起始位置的偏移量container_of : 通过偏移量获取结构体首地址栈先进后出栈数据结构中的一种线性存储结构只允许从一端进行数据插入和删除的线性存储结构特点先进后出FILO顺序栈空间连续链式栈非连续空间顺序栈满增栈、空增栈、满减栈、空减栈满栈/空栈栈顶所在位置是否存有元素增栈/减栈根据栈的生长方向决定链式栈stack.h#ifndef __STACK_H__ #define __STACK_H__ typedef int DataType_t; typedef struct node { DataType_t data; struct node *pnext; }SNode_t; typedef struct stack { SNode_t *ptop; int clen; }Stack_t; extern Stack_t *create_link_stack(); extern int push_stack(Stack_t *pstack, DataType_t data); extern void show_stack(Stack_t *pstack); extern int pop_stack(Stack_t *pstack, DataType_t *pdata); extern int get_stack_top(Stack_t *pstack, DataType_t *pdata); extern void destroy_stack(Stack_t *pstack); #endif创建链式栈#include stack.h #include stdio.h #include stdlib.h Stack_t *create_link_stack() { Stack_t *pstack malloc(sizeof(Stack_t)); if (NULL pstack) { printf(malloc error\n); return NULL; } pstack-ptop NULL; pstack-clen 0; return pstack; } SNode_t *create_node(DataType_t data) { SNode_t *pnode malloc(sizeof(SNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } pnode-data data; pnode-pnext NULL; return pnode; }链式栈入队尾插int push_stack(Stack_t *pstack, DataType_t data) { SNode_t *pnode create_node(data); if (NULL pnode) { return -1; } pnode-pnext pstack-ptop; pstack-ptop pnode; pstack-clen; return 0; }链式栈出栈头删int pop_stack(Stack_t *pstack, DataType_t *pdata) { if (is_empty_stack(pstack)) { return -1; } SNode_t *ptmp pstack-ptop; pstack-ptop ptmp-pnext; if (pdata ! NULL) { *pdata ptmp-data; } free(ptmp); pstack-clen--; return 0; }链式栈获取队头元素int get_stack_top(Stack_t *pstack, DataType_t *pdata) { if (is_empty_stack(pstack)) { return -1; } if (pdata ! NULL) { *pdata pstack-ptop-data; } return 0; }链式栈销毁队列void destroy_stack(Stack_t *pstack) { while (!is_empty_stack(pstack)) { pop_stack(pstack, NULL); } free(pstack); }main.c(输出)#include stdio.h #include stack.h int main(int argc, const char *argv[]) { Stack_t *pstack NULL; DataType_t data; pstack create_link_stack(); if (NULL pstack) { return -1; } push_stack(pstack, 1); push_stack(pstack, 2); push_stack(pstack, 3); push_stack(pstack, 4); push_stack(pstack, 5); show_stack(pstack); int ret pop_stack(pstack, data); if (0 ret) { printf(data %d\n, data); } ret get_stack_top(pstack, data); if (0 ret) { printf(top %d\n, data); } destroy_stack(pstack); return 0; }
