江苏网站建设yijuce,南阳市网站建设,给网站做推广,最好的 受欢迎的 免费的数据结构-栈#xff08;C语言版#xff09;
目录
数据结构-栈#xff08;C语言版#xff09;
1.栈的基础知识
1.入栈#xff0c;出栈的排列组合 情景二#xff1a;Catalan函数#xff08;计算不同出栈的总数#xff09;
2.栈的基本操作 1.顺序存储 (1)顺序栈-定义…数据结构-栈C语言版
目录
数据结构-栈C语言版
1.栈的基础知识
1.入栈出栈的排列组合 情景二Catalan函数计算不同出栈的总数
2.栈的基本操作 1.顺序存储 (1)顺序栈-定义 (2)顺序栈-栈空 (3)顺序栈-入栈 (4)顺序栈-出栈以及取值 (5)共享栈 2.链式存储 (1)链栈-定义 (2)链栈-入栈 (3)链栈-出栈 (4)链栈-打印栈
总代码如下可运行 1.栈的基础知识 简介 栈是后进先出逻辑上相当于一个桶只能从顶端操作。
1.入栈出栈的排列组合 情景一已知入栈序列求出栈序列的可能。 方法先看出栈序列最左边之后按个排序拿着这个出栈的数取入栈序列找它前面的可能之后再回到选择取对比。 例如a,b,c,d,e,f依次进栈求出栈的可能不是哪个一般为选择题从选项中的出栈序列最左边开始找如fedcba,若f先出栈则f后面的次序一定是...e..d..c..b..a,发现符合再看第二个fee出栈后后面出栈的可能为d..c..b..a..f符合再看第三个fedd出栈后可能出栈的有:c..b..a..符合直到最后都符合。所以这个出栈对。又例如出栈序列cabdef,先cc先出栈后面可能..b..a结果选项出栈为..a..b次序反了所以这个就不是 情景二Catalan函数计算不同出栈的总数 n个元素依次进栈可以得到多少种不同的出栈序列 Catalan函数公式,别问为啥问就是记着就行了。代入即可得到结果
2.栈的基本操作 简介按照不同存储方式分为顺序存储和链式存储。 1.顺序存储 简介顺序存储即定义一个结构体里面有一个存储数据的数组和一个记录栈顶的变量top。
如图 (1)顺序栈-定义
#define MaxSize 50 //最大容量
typedef struct
{int data[MaxSize];//存储栈数据的一维数组int top; //表示栈顶的变量top
}SqStack; (2)顺序栈-栈空 简介要看清楚栈空时top指向哪里,不同的指向进栈出栈的操作就不一样不过一般画图就明白了。 初始化InitStack(s) 即栈空
//初始化
//因为想要改变结构体内的值实参形参都变化,所以传栈s的地址进来栈*S指针接收
void InitStack(SqStack *s)
{s-top-1;
}
要看清top栈空的条件时什么再进行相应的初始化。
初始化之后便是验证是否栈空StackEmpty(s)
//判断是否栈空
void StackEmpty(SqStack s)
{if(s.top -1)return 1;
} (1)s.top-1表示栈空 此时我的数组要想赋值肯定需要top先加1定位到数组第一个元素随后再赋值。因此当top-1表示空时top先随后再赋值top始终指向栈顶位置 (2)s.top0表示栈空 此时我的数组要想赋值top已经指向数组第一个位置可以直接赋值之后再top。因此当top0表示空时先赋值再toptop始终指向栈顶位置的下一个位置 (3)顺序栈-入栈 入栈即从外边进桶里此时要考虑上溢情况避免数组容量不够。上溢可通过一定的策略优化减少上溢的情况 代码如下SqPush(s,x);
//入栈
void SqPush(SqStack *s,int x)
{if(s-top MaxSize-1){exit(-1);//栈满,退出 }s-top;s-data[s-top]x;
} (4)顺序栈-出栈以及取值 出栈则是从顶部出取只可操作一端。出栈时考虑下溢下溢时逻辑错误不取决于策略的优化
代码如下
//出栈
void Sqpush(SqStack *s,int *n)
{if(s-top-1)exit(-1); *ns-data[s-top];s-top--;
} (5)共享栈 简介当顺序栈一次性申请的数组空间太大时会造成空间浪费最后还有好多空间没有用。因此对于两个类型相同的栈我们可以让他们在同一个栈中进行存取。分别从左右两端进行入栈中间为栈底。 共享栈的好处节省存储空间降低发生上溢的可能 栈空top0-1,top1MaxSize 栈满他俩碰头了top01top1
共享栈了解思想即可。 2.链式存储 简介采取单链表形式实现的栈为栈的链式存储只不过这里的单链表只能从表头进行插入和删除。 采用链栈的优点便于多个栈共享存储空间提高效率不存在上溢情况插入删除更方便。 特殊约定采用单链表实现的栈默认没有头节点头指针直接指向第一个实际结点都在表头进行操作。 (1)链栈-定义
//栈的链式存储
typedef struct StackNode
{int data;struct StackNode *next; }StackNode; (2)链栈-入栈
思路插入结点插入结点先主动P结点的指针与存储原第一个结点的地址即头节点所存的地址。之后更新头指针把p结点地址赋值给头指针phead 代码如下
//入栈
StackNode* StackNodepush(StackNode *phead,int x)
{StackNode* p(StackNode*)malloc(sizeof(StackNode));p-datax;p-nextNULL;if(pheadNULL){pheadp;}else{p-nextphead;pheadp; }return phead;
} (3)链栈-出栈 出栈即用一个变量接收出栈的值随后再定义一个临时指针指向需要出的结点用来最后释放掉之后移动头指针更新头指针为第二个结点地址最后释放掉出栈结点即可。
代码如下
//出栈
StackNode* StackNodepop(StackNode* phead,int x)
{ //单链表可能为空所以需要先判断非法情况 if(pheadNULL)return NULL;//取第一结点的值 xphead-data;//另外赋值第一个结点 为了后面找到它并释放 StackNode *pphead;//直接更新头节点 pheadp-next;free(p);return phead;
} (4)链栈-打印栈
void StackPrint(StackNode* phead)
{StackNode* pos phead;while(pos!NULL){printf(%d-,pos-data);pos pos-next;}printf(NULL\n);}
总代码如下可运行
#include stdio.h
#include string.h
#include stdlib.h
//顺序栈
#define MaxSize 50
typedef struct
{int data[MaxSize];int top;
}SqStack;
//初始化
void InitStack(SqStack *s)
{s-top-1;
}
//判断是否栈空
int StackEmpty(SqStack s)
{if(s.top -1)return 1;
}
//入栈
void SqPush(SqStack *s,int x)
{if(s-top MaxSize-1){exit(-1);//栈满,退出 }s-top;s-data[s-top]x;
}
//出栈
void Sqpush(SqStack *s,int *n)
{if(s-top-1)exit(-1); *ns-data[s-top];s-top--;
}
//栈的链式存储
typedef struct StackNode
{int data;struct StackNode *next; }StackNode;
//入栈
StackNode* StackNodepush(StackNode *phead,int x)
{StackNode* p(StackNode*)malloc(sizeof(StackNode));p-datax;p-nextNULL;if(pheadNULL){pheadp;}else{p-nextphead;pheadp; }return phead;
}
//出栈
StackNode* StackNodepop(StackNode* phead,int x)
{ //单链表可能为空所以需要先判断非法情况 if(pheadNULL)return NULL;//取第一结点的值 xphead-data;//另外赋值第一个结点 为了后面找到它并释放 StackNode *pphead;//直接更新头节点 pheadp-next;free(p);return phead;
}
void StackPrint(StackNode* phead)
{StackNode* pos phead;while(pos!NULL){printf(%d-,pos-data);pos pos-next;}printf(NULL\n);}
int main()
{StackNode *phead;pheadStackNodepush(phead,0);pheadStackNodepush(phead,1);pheadStackNodepush(phead,2);pheadStackNodepush(phead,3);StackPrint(phead);return 0;
}
