数据结构入门-栈
程序员文章站
2023-11-02 15:27:16
定义:一种可以实现“ 先进后出 ”的存储结构 分类: 1. 静态栈 2. 动态栈 算法: 1. 出栈 2. 压栈 代码实现: 多敲,多敲 ,后期改进 应用: 1. 函数调用 2. 中断 3. 表达式求值 4. 内存分配 5. 缓冲处理 6. 迷宫 ......
定义:一种可以实现“先进后出”的存储结构
分类:
- 静态栈
- 动态栈
算法:
- 出栈
- 压栈
代码实现:
多敲,多敲,后期改进
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node { int data; struct node * pnext; }node , * pnode; typedef struct stack { pnode ptop; pnode pbottom; }stack , * pstack; void init(pstack); void push(pstack , int); void traverse(pstack); bool pop(pstack , int *); void clear(pstack ps); int main(void) { stack s; // stack等价于 struct stack int val; init(&s); // 目的是造出一个空栈 push(&s , 1); // 压栈 push(&s , 8); push(&s , 23); push(&s , 26); push(&s , 34); push(&s , 45); push(&s , 76); push(&s , 88); traverse(&s); // 遍历输出 if(pop(&s , &val)) { printf("你删除的是%d\n", val ); traverse(&s); printf("清空数据\n"); clear(&s); traverse(&s); } else { printf("删除失败\n"); } } void init(pstack ps) { ps->ptop = (pnode)malloc(sizeof(node)); if (null == ps->ptop) { printf("动态内存分配失败\n"); exit(-1); } else { ps->pbottom = ps->ptop; ps->ptop->pnext = null; // ps->pbottom->pnext = null } } void push(pstack ps, int val) { pnode pnew = (pnode)malloc(sizeof(node)); pnew->data = val; pnew->pnext = ps->ptop; // 这里需要注意 ps->ptop = pnew; return; } void traverse(pstack ps) { pnode p = ps->ptop; while(p != ps->pbottom) { printf("%d ", p->data); p = p->pnext; } printf("\n"); return; } bool empty(pstack ps ) { if (ps->ptop == ps->pbottom) return true; else return false; } // 把ps所指向的栈出栈一次,并把出栈元素存下 bool pop(pstack ps , int *val) { if (empty(ps)) { return false; } else { pnode p = ps->ptop; *val = p->data; ps->ptop = p->pnext; free(p); p = null; return true; } } // 清空 void clear(pstack ps) { if (empty(ps)) { return; } else { pnode p = ps->ptop; pnode q = null; while(p != ps->pbottom) { q = p->pnext; free(p); p = q; } ps->ptop = ps->pbottom; } }
应用:
- 函数调用
- 中断
- 表达式求值
- 内存分配
- 缓冲处理
- 迷宫
上一篇: 逻辑卷LVM