数据结构——栈

r囧r小猫 2022-12-23 06:57 4阅读 0赞

## 文章目录 ##

1.存储结构  
2.顺序栈的实现  
3.链栈的实现  
4.进制转换  
5.括号匹配  
6.行编辑程序  
7.迷宫求解  
8.表达式求值

###### 1.存储结构 ######

顺序结构  
typedef struct \{  
ElemType \*base; // 栈底指针  
ElemType \*top; // 栈顶指针  
int stacksize; // 栈空间大小  
\} SqStack;  
链式结构

typedef int ElemType;  
typedef struct node \{  
ElemType data;  
struct node \*next;  
\} LinkStack;

###### 2.顺序栈的实现（可执行程序） ######

#include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    #include<malloc.h>
    
    typedef int Status;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    
    // ------栈的顺序存储结构表示----------
    #define STACK_INIT_SIZE 100 	// 存储空间初始分配量
    #define STACK_INCREMENT 10 	// 存储空间分配增量
    typedef int  ElemType;
    typedef struct {
        
      ElemType *base; 	// 栈底指针
      ElemType *top; 	// 栈顶指针
      int stacksize; 	// 栈空间大小
    } SqStack;
    
    
    void InitStack(SqStack &S)
    {
        
        // 构造一个空栈S
        if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                      * sizeof(ElemType))))
            exit(OVERFLOW);     // 存储分配失败
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(SqStack &S)
    {
        
        // 销毁栈S，S不再存在
        free(S.base);
        S.base = NULL;
        S.top = NULL;
        S.stacksize = 0;
    }
    
    void Push(SqStack &S, ElemType e)
    {
        
        if(S.top - S.base >= S.stacksize) {
         // 栈满，追加存储空间
            S.base = (ElemType *)realloc(S.base, (S.stacksize 
                  + STACK_INCREMENT) * sizeof(ElemType));
            if(!S.base)
                exit(OVERFLOW);           // 存储分配失败
            S.top = S.base + S.stacksize;
            S.stacksize += STACK_INCREMENT;
        }
        *(S.top)++ = e;
    }
    
    Status Pop(SqStack &S, ElemType &e)
    {
        
        // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
        // 否则返回ERROR
        if(S.top == S.base)
            {
        
            	printf("此时栈为空，不可以再出栈\n");
    			return ERROR;
    		}
        e = *--S.top;
        printf("当前出栈的元素的值为：%d\n",e);
        
        return OK;
    }
    
    Status GetTop(SqStack S, ElemType &e)
    {
        
        // 若栈不空，则用e返回S的栈顶元素，并返回OK；
        // 否则返回ERROR
        if(S.top > S.base) {
        
            e = *(S.top - 1);
            printf("输出栈顶元素为 %d \n",e);
            return OK;
        }
        else
        {
        
        	printf("此时栈为空，得不到栈顶元素\n");
    		return ERROR;
    	}
            
    }
    
    Status StackEmpty(SqStack S)
    {
        
        // 若栈S为空栈，则返回TRUE，否则返回FALSE
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    
    
    
    
    int main ()
    {
        
    	int n=1;
    	ElemType e,q,temp;
    	int a;
    	SqStack P;
    	InitStack(P);
    	printf("[1]:入栈输入\n[2]:出栈输入\n[3]:得到栈顶元素输入\n[4]:判断栈是否为空\n[5]:销毁栈\n");
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入栈操作,输入要入栈的元素："); 
    					scanf("%d",&e);
    					Push(P, e);
    					break;
    			case 2: printf("出栈操作\n"); 
    				    Pop(P, q);
    				    
    					break;
    			case 3: GetTop(P, temp);
    				 	
    				 	break;
    			case 4: if(StackEmpty(P)) printf("当前栈为空\n");
    			 			else printf("当前栈不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁栈---\n");
    			 		DestroyStack(P);
    			 		break;
    			 		
    		}
    			
    	}
    	
     }

###### 3.链栈的实现 ######

#include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    #include<malloc.h>
    
    typedef int Status;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int ElemType;
    typedef struct node {
        
      ElemType data;
      struct node *next;
    } LinkStack;
    
    void InitStack(LinkStack *&top)
    {
        
    	top=NULL;
    }
    
    void DestroyStack(LinkStack *&top)
    {
          
    	LinkStack *pre=top,*p;
       if (pre==NULL) return;	//考虑空栈的情况
       p=pre->next;
       while (p!=NULL)
       {
          free(pre);		//释放pre结点
          pre=p;
          p=p->next;      	//pre、p同步后移
       }
       free(pre);			//释放尾结点
    }
    
    int Push(LinkStack *&top,ElemType x)	
    {
          
       LinkStack *p;
       p=(LinkStack *)malloc(sizeof(LinkStack));
       p->data=x;		//创建结点p用于存放x
       p->next=top;	//插入p结点作为栈顶结点
       top=p;
       return 1;
    }
    
    int Pop(LinkStack *&top,ElemType &x)	
    {
          
       LinkStack *p;
       if (top==NULL) //栈空,下溢出返回0
       {
        
       	printf("当前栈为空，不可以再出栈\n"); 
       	return 0;
       }		
          
       else				//栈不空时出栈元素x并返回1
       {
        	p=top;			//p指向栈顶结点
    	x=p->data;		//取栈顶元素x
    	 printf("当前出栈的元素的值为：%d\n",x);
    	top=p->next;		//删除结点p
    	free(p);		//释放p结点
    	return 1;
       }
    }
    
    int GetTop(LinkStack *top,ElemType &x)
    {
          
       if (top==NULL)	//栈空,下溢出时返回0
         {
        
         	printf("此时栈为空，得不到栈顶元素\n");
    		return 0;
    	 }
       else			//栈不空,取栈顶元素x并返回1
       {
          x=top->data;
       printf("输出栈顶元素为 %d \n",x);
          return 1;
       }
    }
    
    int StackEmpty(LinkStack *top)
    {
          
       if (top==NULL)
          return 1;
       else
          return 0;
    }
    
    int stack_traverse(LinkStack *&top)
    {
        
    	
    	LinkStack *p;
    	p=top;
    	int i=1; 
    	 while (p!=NULL)
       {
            printf("目前栈中第 %d 个元素为 %d\n",i++,p->data);		//释放pre结点
          
          p=p->next;      	//pre、p同步后移
       }
       return 0;
    	
     } 
    
    
    
    
    int main ()
    {
        
    	int n=1,e,q;
    	int temp;
    	int a;
    	int number,t;
    	
    	LinkStack *P;
    	LinkStack *help;//用于排序 
    	InitStack(P);
    	InitStack(help);
    	printf("----菜单-----\n"); 
    	printf("1：入栈输入\n2：出栈输入 \n3：得到栈顶元素输入 \n4：判断栈是否为空\n5：销毁栈  \n6：遍历栈中的元素\n");
    
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入栈操作,输入要入栈的元素："); 
    					scanf("%d",&e);
    					Push(P, e);
    					break;
    			case 2: printf("出栈操作\n"); 
    				    Pop(P, q);
    				   
    					break;
    			case 3: GetTop(P, temp);
    				 	printf("输出栈顶元素为 %d \n",temp);
    				 	break;
    			case 4: if(StackEmpty(P)) printf("当前栈为空\n");
    			 			else printf("当前栈不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁栈---\n");
    			 		DestroyStack(P);
    			 		break;
    			case 6: stack_traverse(P);
    			 		break;
    		
    		}
    			
    	}
    	
     }

###### 4.进制转换 ######

[栈的应用——进制转换][Link 1]

###### 5.括号匹配 ######

[栈的应用——括号匹配][Link 2]

###### 6.行编辑程序 ######

###### 7.迷宫求解 ######

###### 8.表达式求值 ######

[栈的应用——表达式求值][Link 3]

###### 9.回文字符串 ######

[栈的应用——回文字符串][Link 4]

[Link 1]: https://blog.csdn.net/qq_50675813/article/details/110000010
[Link 2]: https://blog.csdn.net/qq_50675813/article/details/109996090
[Link 3]: https://blog.csdn.net/qq_50675813/article/details/109967560
[Link 4]: https://blog.csdn.net/qq_50675813/article/details/109994899