参考：1.网课：数据结构与算法基础（青岛大学-王卓）2.教材：数据结构（c语言版）第二版，严蔚敏，李冬梅等著非科班自学，如有错误望不吝赐教。顺序栈0.基本操作#include <stdio.h>
#include <malloc.h>
#define Max 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int SElemType;
//0.顺序栈的储存结构
typedef struct{
SElemType* base;//栈底指针
SElemType* top;//栈顶指针
int stacksize;//栈可用的最大容量
}SqStack;
//1.顺序栈的初始化
Status InitStack(SqStack* S){
S->base=(SElemType*)malloc(Max*sizeof(SElemType));//给栈底指针分配内存空间，栈底指针表示了一个数组
//
if(!S->base) exit(OVERFLOW);
S->top=S->base;
S->stacksize=Max;
return OK;
}
//2.进栈
Status Push(SqStack* S,SElemType a){
if(S->top-S->base==S->stacksize) return ERROR;//判断是否满栈
*(S->top)=a;
printf("push%d /n",*(S->top));
S->top++;
}
//3.出栈
Status Pop(SqStack* S,SElemType* e){
if(S->top==S->base) return ERROR;//判断是否空栈
*e=*(S->top-1);printf("pop %d \n",*e);//*e是存储出栈元素的值,e是指针
S->top--;//顺序栈中指针划过去就表示空间的销毁释放（实际上还在）
return OK;
}
//4.打印栈（注意：不能直接用S->top,否则打印完了整个栈也没了(也不是没了，仍然可以用base[n]去访问栈里面的元素，就是S->top指针没用了)）
//先进先出
Status PrintStack(SqStack* S){
SElemType* p=S->top;
printf("\n print the stack:");
while(p!=S->base){
printf("%d " ,*(p-1));
p--;
}
}
//简单的调试
int main(){
int i,j;i=0;
SElemType a;
printf("请输入原始栈的长度：");
scanf("%d",&j);
SqStack S;//不能定义指针 因为定义指针不意味着定义了指针所指向的东西，所以在函数里面用到S->base都会报错
InitStack(&S);
while(i<j){
printf("please input data:");
scanf("%d",&a);
Push(&S,a);
i++;
}
PrintStack(&S);
}
这里犯过两个错误：定义某个数据类型的时候不能只直接定义指向它的指针，定义了指针不意味着是定义了它指向的数据类型，比如我一开始初始化栈的时候是这样做的，就会报错：
SqStack* S;
InitStack(S);
打印栈的时候，要重新定义一个指针p，来指向每次要打印的数据元素，如果用头指针S->top的话，栈打印完毕，整个栈就“空了”:Status PrintStack(SqStack* S){
printf("\n print the stack:");
while(S->top!=S->base){
printf("%d " ,*(S->top-1));
S->top--;
}
}
关于scanf：scanf()在读取数字时会跳过空格、制表符和换行符！scanf遇到 回车(enter)，空格，TAB 就会结束一次输入，空格不会接;并且， scanf在一次输入结束后，不会舍弃最后的回车符（即回车符会残留在数据缓冲区中）fflush(stdin)：清空缓冲区\qquad
查找这方面的资料是因为想实现如下的功能：每次都向栈中压入一个数据，直到连续敲两次(或更多)回车停止循环，不过最后还是没有能实现，本来打算在每个循环中加入getchar()作为判断是否跳出循环的标记，但它似乎每次都会吃掉scanf留在缓冲区的回车。补充资料：C语言中scanf函数输入回车符的问题;scanf语句吃掉回车或者空格问题详解;1. 用栈判断是否是回文Input:字符序列与之长度Output:（Not）palindrome想法：把字符序列的前一半入栈，然后逐一出栈，由于先进后出，所以先出来的是原字符序列更靠近中间的;字符的后一半顺序就从左到右即可。\qquad
两部分相应比较，如果出现不等的字符对则不是回文
//试写一个算法判定给定的字符序列是否为回文
int main(){
SElemType a;
SElemType e;//定义指针不意味着分配了相应的空间
int flag=0;
char s[30]= {0};
int m,mm,i=0;
printf("Please enter a string :");
scanf("%s",&s);
//m=con_str(s);//可以自定义一个函数计算字符串的长度
printf("Please enter length of the string :");
scanf("%d",&m);
mm=(int) m/2;
SqStack S;//不能定义指针 因为定义指针不意味着定义了指针所指向的东西，所以在函数里面用到S->base都会报错
InitStack(&S);
while(i<mm){//将前一半的字符压入栈中
a=s[i];
Push(&S,a);
i++;
}
while(i>0){
a=s[m-i];
Pop(&S,&e);//将栈中的字符串逐一出栈，注意到先进后出，所以先出来是的更靠近中间，后半段的字符串从左往右逐次输出即可
if(a!=e){
flag=1;
break;
};
i--;
}
if(flag==1){
printf("Not palindrome");
}
else{
printf("Palindrome");}
return 0;
}
链栈0.基本操作#include <stdio.h>
#include <malloc.h>
#define Max 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int SElemType;
//0.链栈的存储结构
typedef struct StackNode
{
SElemType data;
struct StackNode* next;
}StackNode,*LinkStack;
//1.链栈的初始化 (链栈不需要头结点,S始终为栈顶指针)
Status InitStack2(LinkStack* SS){
*SS=NULL;
return OK;
}
//2.链栈的入栈
Status Push2(LinkStack* SS,SElemType a){
LinkStack p=(LinkStack)malloc(sizeof(SElemType));//申请一个结点的内存用于存放新元素
p->data=a;
p->next=*SS;
*SS=p;
printf("Push %d ",a);
return OK;
}
//3.链栈的出栈
Status Pop2(LinkStack* SS,SElemType* e){
if(*SS==NULL) return ERROR;
*e=(*SS)->data;//存放出栈的元素
LinkStack p=*SS;
*SS=(*SS)->next;
printf("Pop %d ",*e);
free(p);
return OK;
}
//4.打印链栈
Status PrintStack2(LinkStack S){
LinkStack p=S;//需要另外定义一个指针指向打印的结点
printf("\n print the stack:");
while(p!=NULL){
printf("%d " ,(p->data));
p=p->next;
}
}
//简单的调试
int main(){
int j,i=0;LinkStack S;SElemType a;
InitStack2(&S);
printf("请输入原始栈的的长度");
scanf("%d",&j);
while (i<j){
printf("please input data:");
scanf("%d",&a);
Push2(&S,a);
i++;
}
PrintStack2(S);
}
注意：链栈不需要头结点,S始终为栈顶指针，指针方向指向栈底用c语言实现链栈的操作时候（初始化/入栈/出栈）需要对书上的内容稍稍修改，书本上的内容如下（书本上用的是c++的引用是没有问题的）：//1.链栈的初始化 (链栈不需要头结点,S始终为栈顶指针)
Status InitStack2(LinkStack S){
S=NULL;
return OK;
}
//2.链栈的入栈
Status Push2(LinkStack S,SElemType a){
LinkStack p=(LinkStack)malloc(sizeof(SElemType));//申请一个结点的内存用于存放新元素
p->data=a;
p->next=S;
S=p;
printf("Push %d ",a);
return OK;
}
//3.链栈的出栈
Status Pop2(LinkStack S,SElemType* e){
if(S==NULL) return ERROR;
*e=S->data;//存放出栈的元素
LinkStack p=S;
S=S->next;
printf("Pop %d ",*e);
free(p);
return OK;
}
//简单的调试
int main(){
int j,i=0;LinkStack S;SElemType a;
InitStack2(S);
printf("请输入原始栈的的长度");
scanf("%d",&j);
while (i<j){
printf("please input data:");
scanf("%d",&a);
Push2(S,a);
i++;
}
//PrintStack2(S);
}
由于自定义函数无法改变实参的内容，所以在自定义函数里面定义的那些对S的操作都是传不到主函数里的；希望用函数修改实参可以通过传入这个实参的指针，所以定义了LinkStack* SS，它是指向LinkStack S的指针。想知道除了定义二级指针，还有其他方法嘛？1.计算后缀表达式Input:后缀表达式（下面的代码暂时只能处理操作数是整数，小数需要修改占位符和定义的相关数据类型等等）output:计算结果idea: 定义一个栈OPTD用于存放操作数和运算结果，输入表达式\qquad
用scanf扫描表达式，读入并处理得到第一个字符ch（具体处理方法见代码）\qquad
若ch为操作数则压入OPTD\qquad
若ch为操作符 ，从OPTD出栈两个数，结合这个操作符进行运算，把运算结果再压入栈中\qquad
读入下一个字符，直到遇到回车为止\qquad
最后将OPTD中元素出栈，即为所求结果这里代码参考了C语言 后缀表达式;#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define Max 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int SElemType;
typedef struct{//顺序栈的储存结构
SElemType* base;//栈底指针
SElemType* top;//栈顶指针
int stacksize;//栈可用的最大容量
}SqStack;
Status InitStack(SqStack* S){//顺序栈的初始化
S->base=(SElemType*)malloc(Max*sizeof(SElemType));//给栈底指针分配内存空间，栈底指针表示了一个数组
//
if(!S->base) exit(OVERFLOW);
S->top=S->base;
S->stacksize=Max;
return OK;
}
//进栈
Status Push(SqStack* S,SElemType a){
if(S->top-S->base==S->stacksize) return ERROR;//判断是否满栈
*(S->top)=a;
printf("push%d /n",*(S->top));
S->top++;
}
//出栈
Status Pop(SqStack* S,SElemType* e){
if(S->top==S->base) return ERROR;//判断是否空栈
*e=*(S->top-1);printf("pop %d \n",*e);//*e是存储出栈元素的值,e是指针
S->top--;//顺序栈中指针划过去就表示空间的销毁释放（实际上还在）
return OK;
}
//打印顺序栈（注意：不能直接用S->top,否则打印完了整个栈也没了(也不是没了，仍然可以用base[n]去访问栈里面的元素，就是S->top指针没用了)）
//先进先出
Status PrintStack(SqStack* S){
SElemType* p=S->top;
printf("\n print the stack:");
while(p!=S->base){
printf("%d " ,*(p-1));
p--;
}
}
//链栈的存储结构
typedef struct StackNode
{
SElemType data;
struct StackNode* next;
}StackNode,*LinkStack;
//链栈的初始化(链栈不需要头结点,S始终为栈顶指针)
Status InitStack2(LinkStack* SS){
*SS=NULL;
return OK;
}
//链栈的入栈
Status Push2(LinkStack* SS,SElemType a){
LinkStack p=(LinkStack)malloc(sizeof(SElemType));//申请一个结点的内存用于存放新元素
p->data=a;
p->next=*SS;
*SS=p;
printf("Push %d ",a);
return OK;
}
//链栈的出栈
Status Pop2(LinkStack* SS,SElemType* e){
if(*SS==NULL) return ERROR;
*e=(*SS)->data;//存放出栈的元素
LinkStack p=*SS;
*SS=(*SS)->next;
printf("Pop %d ",*e);
free(p);
return OK;
}
//打印链栈
Status PrintStack2(LinkStack S){
LinkStack p=S;//需要另外定义一个指针指向打印的结点
printf("\n print the stack:");
while(p!=NULL){
printf("%d " ,(p->data));
p=p->next;
}
}
从键盘上输入一个后缀表达式，试编写算法计算表达式的值
int main(){
LinkStack OPTD;
InitStack2(&OPTD);//初始化栈
char str[10];
char data;
SElemType store;
int i=0;
SElemType e1;
SElemType e2;
printf("请输入一串后缀表达式, 以Enter结束: \n");
scanf("%c", &data);
while(data != '\n'){//直到遇到回车停止扫描
while(isdigit(data)
'.' == data){//当data是操作数时，暂时先一个一个存到数组str中，当遇到空格时，把数组转换成浮点数
str[i++] = data;
str[i] = '\0';
if (i >= 10){
printf("输入的单个数据过大\n");
return -1;
}
scanf("%c", &data);
if(' ' == data){
store = atof(str);//把str中的数字序列转化为浮点数（需要头文件#include <stdlib.h>）
Push2(&OPTD, store);//将操作数压入栈
i = 0;
break;
}
}
switch(data){//当data是运算符时
case '+':
Pop2(&OPTD, &e2);
Pop2(&OPTD, &e1);//将OPTD最上面的两个操作数出栈
Push2(&OPTD, e1 + e2);//将其相加再入栈
break;
case '-':
Pop2(&OPTD, &e2);
Pop2(&OPTD, &e1);//将OPTD最上面的两个操作数出栈
Push2(&OPTD, e1 - e2);//将其相减再入栈
break;
case '*':
Pop2(&OPTD, &e2);
Pop2(&OPTD, &e1);//将OPTD最上面的两个操作数出栈
Push2(&OPTD, e1 * e2);//将其相乘再入栈
break;
case '/':
Pop2(&OPTD, &e2);
Pop2(&OPTD, &e1);//将OPTD最上面的两个操作数出栈
if(e2 == 0){
printf("输入错误,除数不能为0\n");
return -1;
}
Push2(&OPTD, e1 / e2);//将其相除再入栈
break;
}
scanf("%c", &data);
}
PrintStack2(OPTD);
}
注意：scanf的扫描原理2.判断入栈/出栈的序列是否合法Input:1或0的序列，1表示入栈，0表示出栈Output:true/falseidea:每次操作后记录栈中元素个数，小于0则break循环，返回false//
#include <stdio.h>
int main(){
char seq[10];
int i=0;
int j=0;//用来记录每次操作后还有几个元素
int m=0;
int flag =0;
char data;
do{
scanf("%c",&data);
seq[m]=data;//输入10110100[enter]后m是9
m++;
}while(data!='\n');
for(i=0;i<m-1;i++){
if(seq[i]=='1'){
j++;
}
else{
j--;
}
if(j<0){
flag=1;
break;
}
}
if(flag==1){
printf("false");
}
else{
printf("true");
}
}