数据结构与算法（C语言） | 栈和队列——栈

栈是一种重要的线性结构，通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。（后进先出）

–栈的元素必须“后进先出”。

–栈的操作只能在这个线性表的表尾进行。

–注：对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

•因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。


•最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

 


//栈的顺序存储结构 typedef struct { ElemType *base; ElemType *top; int stackSize;
}sqStack;
                                                             顺序栈
//----- 栈的动态分配顺序存储结构 ----- #define STACK_INIT_SIZE 100 //顺序栈初始容量 #define
STACKINCREMENT 10 //顺序栈容量增量 typedef struct { SElemType *base; //顺序栈基地址(栈底指针)
SElemType *top; //栈顶指针 int stacksize; //顺序栈当前存储容量 }SqStack;
初始化
//----- 基本操作的算法描述 ----- Status InitStack( SqStack &S ) { // 构造一个空栈 S
S.base=(SElemType*)malloc (STACK_INIT_SIZE*sizeof(SElemType)); if (!S.base)
exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return
OK; }//InitStack
返回栈顶元素
Status GetTop( SqStack S, SElemType &e ) { // 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK; //
否则返回 ERROR if (S.top = = S.base) return ERROR; e = *(S.top-1); return OK;
}//GetTop
压入栈
Status Push( SqStack &S, SElemType e ) { // 在栈 S 中插入元素 e 为新的栈顶元素 if
(S.top-S.base>=S.stacksize) { // 栈满，追加存储空间 newbase=(SElemType*)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if (!newbase) exit(OVERFLOW);
// 存储分配失败 S.base = newbase; S.top = S.base+S.stacksize; S.stacksize +=
STACKINCREMENT; } *S.top++ = e; return OK; }//Push
弹出栈
Status Pop( SqStack S, SElemType &e ) { // 若栈不空，则删除 S 的栈顶元素，用 e 返回其值, // 并返回
OK; 否则返回 ERROR if (S.top = = S.base) return ERROR; e = *--S.top; return OK;
}//Pop
        

注：c语言中->和.的区别——->用于指针， .用于对象

"->"用于指向结构成员，它的左边应为指向该结构类型的指针（结构指针），而"."的左边应为该结构类型的变量（结构变量），如已定义了一个结构体struct
student，里面有一个int a；然后有一个结构体变量struct student stu及结构体变量指针struct student
*p；且有p=&stu，那么p->a和stu.a表示同一个意思。

 

                                                    

实例分析：

•题目：利用栈的数据结构特点，将二进制转换为十进制数。

•分析：地球人都知道，二进制数是计算机数据的存储形式，它是由一串0和1组成的，每个二进制数转换成相应的十进制数方法如下：

(XnXn-1……X3X2X1)2 = X1*2^0+X2*2^1+…+Xn*2^(n-1)

•一个二进制数要转换为相应的十进制数，就是从最低位起用每一位去乘以对应位的积，也就是说用第n位去乘以2^(n-1)，然后全部加起来。

由于栈具有后进先出的特性，例如我们输入11001001这样的二进制数



 
#include<stdio.h> #include<stdlib.h> #include<math.h> #define STACK_INIT_SIZE
20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct { ElemType
*base; ElemType *top; int stackSize; }sqStack; void InitStack(sqStack *s) {
s->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!s->base) {
exit(0); } s->top = s->base; s->stackSize = STACK_INIT_SIZE; } void
Push(sqStack *s,ElemType e) { if(s->top-s->base >= s->stackSize ) { s->base =
(ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT)*sizeof(ElemType));
if(!s->base) { exit(0); } s->top = s->base + s->stackSize; s->stackSize =
s->stackSize + STACKINCREMENT; } *(s->top) = e; s->top++; } void Pop(sqStack
*s,ElemType *e) { if(s->top == s->base) { return; } *e = *--(s->top); } int
StackLen(sqStack s) { return (s.top - s.base); //不是地址的相减而是内容 } int main() {
ElemType c; sqStack s; int len, i, sum = 0; InitStack(&s);
printf("请输入二进制书，输入#符号表示结束！\n"); scanf("%c",&c); while(c!= '#') { Push(&s, c);
scanf("%c",&c); } //清理键盘缓冲区 回车的ASCII=10 getchar(); len = StackLen(s);
printf("栈的当前容量是：%d\n",len); for(i=0; i<len ; i++) { Pop(&s,&c); sum = sum +
(c-48) * pow(2, i); } printf("转化为十进制为：%d \n",sum); return 0; }
二进制转化为八进制、二进制转化为十六进制：

二进制每三位转化为一个八进制

修改一下以上的主函数部分：
int main() { ElemType c; sqStack s1; sqStack s2; int len, i, j, sum = 0;
InitStack(&s1); // 初始化栈s1，用来存放二进制输入 printf("请输入二进制数，输入‘#’号表示结束！\n\n");
scanf("%c", &c); while( c != '#' ) { if( c=='0' || c=='1' ) // 检查输入是否二进制
Push(&s1, c); scanf("%c", &c); } getchar(); // 把'\n'从缓冲区去掉 len = StackLen(s1);
InitStack(&s2); // 初始化栈s2，用来存放转换的八进制 for( i=0; i < len; i+=3 ) { for( j=0; j <
3; j++ ) { Pop( &s1, &c ); // 取出栈顶元素 sum = sum + (c-48) * pow(2, j); if(
s1.base == s1.top ) { break; } } Push( &s2, sum+48 ); sum = 0; }
printf("\n转化为八进制数是: "); while( s2.base != s2.top ) { Pop( &s2, &c );
printf("%c", c); } printf("(O)\n"); return 0; }
二进制每四位有一个十六进制与之呼应
int main() { ElemType c; sqStack s1; sqStack s2; int len, i, j, sum = 0;
InitStack(&s1); // 初始化栈s1，用来存放二进制输入 printf("请输入二进制数，输入‘#’号表示结束！\n\n");
scanf("%c", &c); while( c != '#' ) { if( c=='0' || c=='1' ) // 检查输入是否二进制
Push(&s1, c); scanf("%c", &c); } getchar(); // 把'\n'从缓冲区去掉 len = StackLen(s1);
InitStack(&s2); // 初始化栈s2，用来存放转换的八进制 for( i=0; i < len; i+=4 ) { for( j=0; j <
4; j++ ) { Pop( &s1, &c ); // 取出栈顶元素 sum = sum + (c-48) * pow(2, j); if(
s1.base == s1.top ) { break; } } switch( sum ) { case 10: sum = 'A'; break;
case 11: sum = 'B'; break; case 12: sum = 'C'; break; case 13: sum = 'D';
break; case 14: sum = 'E'; break; case 15: sum = 'F'; break; default: sum +=
48; } Push( &s2, sum ); sum = 0; } printf("\n转化为十六进制数是: "); while( s2.base !=
s2.top ) { Pop( &s2, &c ); printf("%c", c); } printf("(H)\n"); return 0; }
                                                           链式栈



 


teypedef struct StackNode { ElemType data; // 存放栈的数据 struct StackNode *next; }
StackNode, *LinkStackPtr; teypedef struct LinkStack { LinkStackPrt top; //
top指针 int count; // 栈元素计数器 }
 

 

实践：计算数学表达式(1-2)*(4+5)

简介：逆波兰表达式


——后来，在20世纪三十年代，波兰逻辑学家Jan.Lukasiewicz不知道是像牛顿一样被苹果砸到脑袋而想到万有引力原理，或者还是像阿基米德泡在浴缸里突发奇想给皇冠是否纯金做验证，总之他也是灵感闪现了，然后发明了一种不需要括号的后缀表达式，我们通常把它称为逆波兰表达式(RPN)
。

•如果用逆波兰表示法，应该是这样：1 2 – 4 5 + *

实现对逆波兰输入的表达式进行计算，并且支持带小数点的数据。

 

 

• « 上一篇：Linux普通用户安装mysql-5.7.21
• » 下一篇：pyppeteer 绕过selenium检测，实现淘宝登陆