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

链式数据结构

news 2025/8/11 11:27:09

二级指针：
1. 在被调函数中，想要修改主调函数中的指针变量，需要传递该指针变量的地址，形参用二级指针接收。
2.指针数组的数组名是一个二级指针，指针数组的数组名作为参数传递时，可用二级指针接收。

内核链表：双向循环链表
不再将数据存储在链表节点中，而是将结点嵌入到存储的数据中。

offset_of : 获取内核链表中链表结点到结构体起始位置的偏移量。
container_of:通过偏移量，获取结构体的首地址（结点首地址-偏移量）。

数据结构：

栈：只允许从一端进行数据的插入和删除的线性存储结构，称之为栈结构

特点：先进后出: FILO

顺序表（数组）---》顺序栈

满增栈、满减栈、空增栈、空减栈

满栈、空栈：栈顶所在位置是否存在数据

增栈、减栈：按照栈的生长方向区分

链式结构-->链式栈

1.创建链式栈
2. 入栈（头插）
3. 出栈（头删）
4. 判断是否为空栈
5. 获取栈顶元素
6. 销毁栈

stack.h

#ifndef __STACK_H__
#define __STACK_H__typedef int Data_type_t;typedef struct stnode
{Data_type_t data;struct stnode *pnext;
}STNode_t;typedef struct stack
{STNode_t *ptop;int clen;
}Stack_t;extern Stack_t *create_stack();extern int is_empty_stack(Stack_t *pslink);extern int push_stack(Stack_t *pslink, Data_type_t data);extern int pop_stack(Stack_t *pslink,Data_type_t *pdata);extern int get_top_stack(Stack_t *pslink, Data_type_t *data);extern void destory_stack(Stack_t **pslink);extern void stack_for_each(Stack_t *pslink);
#endif

stack.c

#include<stdio.h>
#include<stdlib.h>
#include"stack.h"/*** @brief 创建一个空的链式栈* @return 成功返回栈的指针，失败返回NULL* @note 栈创建后需要调用destory_stack进行销毁，避免内存泄漏*/
Stack_t *create_stack()
{Stack_t *pstack = malloc(sizeof(Stack_t));  // 为栈结构体分配内存if(NULL == pstack){printf("创建链式栈失败\n");return NULL;}pstack->ptop = NULL;  // 栈顶指针初始化为NULL（空栈）pstack->clen = 0;     // 栈长度初始化为0return pstack;
}/*** @brief 判断链式栈是否为空* @param pstack 栈的指针* @return 1表示栈为空或指针无效，0表示栈非空* @note 当pstack为NULL时也视为空栈（无效栈）*/
int is_empty_stack(Stack_t *pstack)
{return (pstack == NULL) || (NULL == pstack->ptop);
}/*** @brief 向链式栈中压入元素（入栈操作）* @param pslink 栈的指针* @param data 要压入栈的数据* @return 0表示成功，-1表示失败（内存分配失败）* @note 入栈操作会在栈顶添加新元素，栈长度加1*/
int push_stack(Stack_t *pslink, Data_type_t data)
{// 创建新的栈节点并分配内存STNode_t *pnode = malloc(sizeof(STNode_t));if(NULL == pnode){printf("创建节点失败\n");return -1;}pnode->data = data;   // 存储数据pnode->pnext = NULL;  // 初始化指针// 将新节点插入到栈顶pnode->pnext = pslink->ptop;pslink->ptop = pnode;pslink->clen++;  // 栈长度递增return 0;
}

/*** @brief 从链式栈中弹出元素（出栈操作）* @param pslink 栈的指针* @param pdata 用于存储弹出数据的指针（若为NULL则仅弹出不保存数据）* @return 0表示成功，-1表示失败（栈为空或无效）* @note 出栈操作会移除栈顶元素，栈长度减1*/
int pop_stack(Stack_t *pslink, Data_type_t *pdata)
{// 检查栈是否为空if(is_empty_stack(pslink)){return -1;}STNode_t *pdel = pslink->ptop;  // 记录栈顶节点if(pdata != NULL)               // 若需要保存数据{*pdata = pdel->data;}pslink->ptop = pdel->pnext;  // 更新栈顶指针free(pdel);                  // 释放弹出节点的内存pslink->clen--;              // 栈长度递减return 0;
}

/*** @brief 获取链式栈的栈顶元素（不弹出）* @param pstack 栈的指针* @param pdata 用于存储栈顶数据的指针* @return 0表示成功，-1表示失败（栈为空、指针无效或pdata为NULL）* @note 此操作不会改变栈的结构和长度*/
int get_top_stack(Stack_t *pstack, Data_type_t *pdata)
{// 检查栈是否为空if(is_empty_stack(pstack)){return -1;}// 检查数据指针是否有效if(NULL == pdata){return -1;} *pdata = pstack->ptop->data;  // 获取栈顶元素数据return 0;
}/*** @brief 销毁链式栈，释放所有内存* @param pstack 栈指针的地址（二级指针）* @note 销毁后会将栈指针置为NULL，避免野指针*/
void destory_stack(Stack_t **pstack)
{// 弹出所有元素while(!is_empty_stack(*pstack)){pop_stack(*pstack, NULL);}free(*pstack);  // 释放栈结构体内存*pstack = NULL; // 指针置空
}/*** @brief 遍历并打印链式栈中的所有元素（从栈顶到栈底）* @param pslink 栈的指针* @note 打印格式为：元素1 元素2 ... 元素n（换行）*/
void stack_for_each(Stack_t *pslink)
{// 定义临时指针stmp，初始化为栈顶节点STNode_t *stmp = pslink->ptop;// 循环遍历栈，stmp为NULL时结束while(stmp != NULL){// 打印当前节点中存储的数据printf("%d ",stmp->data);// 将临时指针移动到下一个节点stmp = stmp->pnext;}printf("\n");
}