[C++知识库]数据结构之栈的相关实现（C语言）

参考：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的指针。
想知道除了定义二级指针，还有其他方法嘛？