数据结构 栈和堆
数据结构学习笔记
栈的类型定义
- 栈的特性: 先进后出, 后进先出 (最先放入栈的內容最后被拿岀来, 最后放入栈的内容最先被拿出来)
栈的插入
栈的删除
栈的基本操作
InitStack (&S) [构造空栈]
void Init(SqStack s) { s.base=( int *)malloc(size*sizeof( int )); s.top=s.base; s.stacksize=size; }
|
Push (&S, e) [插入元素]
void Push(SqStack s, int e) { if(s.top-s.base>s.stacksize) { s.base=( int *)malloc(size*sizeof( int )); s.top=s.base; s.stacksize=size; } *s.top++=e; }
|
Pop (&S, &e) [删除元素]
void Push(SqStack s, int e) { if(s.top-s.base>s.stacksize) { s.base=( int *)malloc(size*sizeof( int )); s.top=s.base; s.stacksize=size; } *s.top++=e; }
|
Print (*S) [打印函数]
void Print(SqStack *s) { int * temp; temp = s -> top; while ( temp != s -> base) { temp--; printf("%d",*temp); } }
|
栈的递归调用
递归函数: 一个直接调用直接或通过一系列的调用语句间接地调用自己的函数
# include <stdio.h> int f ( int m ) { if ( m==1 ) return 1; else { printd("m=%d\n",m); return f ( m - 1 ); }
int main() { int n; int f ( int m); printf("请输入一个大于1的数: "); scanf("%d",&n); printf("%d\n",f(n)); return 0; }
}
|
栈类型的实现
顺序栈
构造一个最大空机为 maxsize 的空顺序栈 S
# define STACK_INIT_SIZE 100
typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;
Status InitStack ( SqStack &S, int maxsize ) { S.base = new ElemType[maxsize]; if ( !S.base ) exit ( OVERFLOW ); S.top = S.base; S.stacksize = Maxsize; return OK; }
Status Push ( SqStack &S, SElemType e ) { if ( S.top - S.base >= S.stacksize ) return OVERFLOW; *S.top++ = e; return OK; }
Status Pop ( SqStack &S, SElemType &e ) { if ( S.top == S.base ) return ERROR; e = *--S.top; return OK; }
|
链栈
线性表有顺序存储结构和链式存储结构, 栈属于线性表的一种, 也具有顺序存储结构和链式存储结构
作者: 我叫史迪奇
本文来自于:
https://sdq3.link/DataStructure-Stack-Heap.html博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议