当前位置：首页 > news >正文

C语言--day20

news 2026/5/28 0:14:42

补充：单向链表

查找：根据数据查找，返回找到的节点

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; }

查看全文

http://www.jsqmd.com/news/899821/