口碑好的网站开发,邢台经济开发区,范县网站建设费用,沉默是金下一句怎么接代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、栈的定义2、创建一个栈3、入栈和出栈操作4、栈的清空、销毁、计算栈的当前容量5、实例分析前言
本章总结#xff1a;栈的定义、创建栈#xff0c;销毁栈#xff0c;入栈出栈操作等操作。 1、栈的定义
栈是一种重要的…代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、栈的定义2、创建一个栈3、入栈和出栈操作4、栈的清空、销毁、计算栈的当前容量5、实例分析前言
本章总结栈的定义、创建栈销毁栈入栈出栈操作等操作。 1、栈的定义
栈是一种重要的线性结构。是链表和顺序表的具体形式。
stack是一个后进先出的线性表。栈的操作只能限定在这个顺序表的表尾进行我们称这个地方为栈顶(top)相应的表头称为栈底(bottom) 最开始栈中不含有任何数据叫做空栈此时栈顶就是栈底。数据从栈顶进入栈顶栈底分离栈的容量变大。数据出栈时从栈顶弹出栈顶下移整个栈的当前容量变小。
用顺序表建立栈
typedef struct {ElemType *base; //指向栈底的指针ElemType *top; //指向栈顶的指针int stacksize; //当前可使用的最大容量
}sqStack;2、创建一个栈
1、在内存中开辟一段连续的空间用作栈的物理存储空间 2、将栈顶、栈底的地址赋值给top和base,并设置stacksize以便通过这个变量对栈进行各种操作
#define STACK_INIT_SIZE 100
void initStack(sqStack *s)
{//内存中开辟一段连续空间作为栈空间首地址赋值给s-bases-base (ElemType*)malloc(sizeof(ElemType) * STACK_INIT_SIZE);if (!s-base){printf(分配内存失败);exit(0);} //分配内存失败s-top s-base; //空栈栈顶和栈底重合s-stacksize STACK_INIT_SIZE; //设定最大容量
}
/*注意
要区分栈的最大容量和栈的当前容量两个概念。
对于此栈最大容量为100个ElemType 类型空间大小但是它是一个空栈因为它里面没有任何内容
*/3、入栈和出栈操作
入栈每向栈中压入一个数据top指针1直到栈满为止
//入栈
#define STACKINCREMENT 10
void PushStack(sqStack* s,ElemType elem)
{if (s-top - s-base s-stacksize) //判断栈是否满了{//如果栈满了追加空间s-base (ElemType*)realloc(s-base, (s-stacksize STACKINCREMENT) * sizeof(ElemType));if (!s-base) //内存分配失败{printf(内存分配失败);exit(0);}s-top s-base s-stacksize;s-stacksize s-stacksize STACKINCREMENT; //重置栈的最大容量}*(s-top) elem; //放入数据s-top; //top指针1
}出栈操作就是栈顶(指针先下移指向栈顶元素)取出元素栈顶指针随之下移的操作。可以重复出栈直道该栈变为空栈为止
//出栈操作
void PopStack(sqStack* s, ElemType *elem)
{if (s-top s-base) return; //栈空了程序返回s-top--; //top指针-1*elem *(s-top); //将栈顶元素取出给elem
}4、栈的清空、销毁、计算栈的当前容量
1、清空一个栈就是希望栈中的元素全部作废而栈本身的物理空间不一定发生变化。 因此只需要将s-top的内容赋值为s-base即可 2、销毁一个栈是要释放掉该栈所占据的物理内存空间因此销毁与清空栈是两个不同的操作。
//栈的一些操作清空一个栈、销毁一个栈、计算栈当前的容量
//清空一个栈
void ClearStack(sqStack* s)
{s-top s-base; //将栈底指针赋值给栈顶指针表示栈已变空
}
//销毁一个栈
void DestroyStack(sqStack* s)
{free(s-base); //释放掉内存空间s-base s-top NULL; //栈顶栈底指针置NULLs-stacksize 0; //栈的最大容量设置为0
}//计算栈当前容量
int GetStackLen(sqStack s)
{return (s.top - s.base); //这里不对栈中的数据进行修改所以不需要引用
}5、实例分析
利用栈的数据结构将二进制转换为十进制
已知公式为 思路将一串二进制的0/1码从高位到低位顺序入栈再逐一从栈顶取出元素取出的第i个元素乘上2的i-1次方并逐一累加最终得到十进制表达。
#include stdio.h
#include malloc.h
#include conio.h
#include stdlib.h
#include math.h
typedef char ElemType ;
typedef struct {ElemType *base; //指向栈底的指针ElemType *top; //指向栈顶的指针int stacksize; //当前可使用的最大容量
}sqStack;
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
void initStack(sqStack *s)
{//内存中开辟一段连续空间作为栈空间首地址赋值给s-bases-base (ElemType*)malloc(sizeof(ElemType) * STACK_INIT_SIZE);if (!s-base){printf(分配内存失败);exit(0);} //分配内存失败s-top s-base; //空栈栈顶和栈底重合s-stacksize STACK_INIT_SIZE; //设定最大容量
}
/*注意
要区分栈的最大容量和栈的当前容量两个概念。
对于此栈最大容量为100个ElemType 类型空间大小但是它是一个空栈因为它里面没有任何内容
*///入栈
void PushStack(sqStack* s,ElemType elem)
{if (s-top - s-base s-stacksize) //判断栈是否满了{//如果栈满了追加空间s-base (ElemType*)realloc(s-base, (s-stacksize STACKINCREMENT) * sizeof(ElemType));if (!s-base) //内存分配失败{printf(内存分配失败);exit(0);}s-top s-base s-stacksize;s-stacksize s-stacksize STACKINCREMENT; //重置栈的最大容量}*(s-top) elem; //放入数据s-top; //top指针1
}//出栈操作
void PopStack(sqStack* s, ElemType *elem)
{if (s-top s-base) return; //栈空了程序返回s-top--; //top指针-1*elem *(s-top); //将栈顶元素取出给elem
}//栈的一些操作清空一个栈、销毁一个栈、计算栈当前的容量
//清空一个栈
void ClearStack(sqStack* s)
{s-top s-base; //将栈底指针赋值给栈顶指针表示栈已变空
}
//销毁一个栈
void DestroyStack(sqStack* s)
{free(s-base); //释放掉内存空间s-base s-top NULL; //栈顶栈底指针置NULLs-stacksize 0; //栈的最大容量设置为0
}//计算栈当前容量
int GetStackLen(sqStack s)
{return (s.top - s.base); //这里不对栈中的数据进行修改所以不需要引用
}int main()
{ ElemType c;sqStack s;int len 0, i 0, sum 0;printf(请输入一个二进制数\n);initStack(s);/*输入01字符表示的二进制数以#结束*/scanf(%c,c);while (c ! #){PushStack(s,c);printf(将%c压入栈中\n,c);scanf(%c, c);}getchar();len GetStackLen(s);printf(len:%d\n, len);for(i0;ilen;i){PopStack(s,c);printf(%c , c);sum sum (c - 0) * pow(2, i); //转换成十进制}printf(十进制数是:%d\n,sum);DestroyStack(s); //释放栈空间_getche();return 0;
}reslut:
