数据结构之顺序栈基本操作(c语言）

àì夳堔傛蜴生んèń 2022-11-18 01:16 223阅读 0赞

#### 栈 ####

栈是一种运算受限的线性表，是一种先进后出的数据结构，限定只能在一端进行插入和删除操作，允许操作的一端称为栈顶，不允许操作的称为栈底

--------------------

#### 顺序栈（顺序结构） ####

顺序栈：用一段连续的存储空间来存储栈中的数据元素，比较常见的是用数组来实现顺序栈

顺序存储结构：1.元素所占的存储空间必须连续（这里的连续是指的逻辑连续，而不是物理连续）

--------------------

#### 程序演示： ####

![在这里插入图片描述][20210415130214602.gif_pic_center]

#### 程序源代码： ####

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_SIZE 5 /* 栈最大容量 */
    #define Empty 0 /* 空 */
    #define Full 1 /* 满 */
    #define Avail -1 /* 可用 */
    typedef int ElemType;
    typedef struct stack
    { 
        int *top;            /* 栈顶指针 */
        int *bottom;        /* 栈底指针 */
        int stack_size;        /* 栈的最大容量 */
    }stack;
    
    stack Push(stack p);        /* 入栈 */
    void DisplyStack (stack p);    /* 遍历栈中元素 */
    stack Pop(stack p);        /* 出栈 */
    stack InitStack (stack p);    /* 初始化栈 */
    int StackEmpty (stack p);    /* 判断栈是否为空 */
    int StackFull (stack p);    /* 判断栈是否为满 */
    void menu01();          /*菜单*/ 
    
    void main()
    { 
        stack p;
        char ch;
        int n,x,x1;
        system("color f0\n" );
        menu01();
        scanf("%d",&n);
        while(n){ 
        if(n<1 || n>6){ 
        	printf("您输入的代码有误,请重新输入:\n");
        	scanf("%d",&n);
    	}else{ 
        switch(n){ 
        	case 1:	
        	  p=InitStack(p); break;
        	case 2: 
        	  p=Push(p); break;
        	case 3:
        	  p=Pop(p);  break;
        	case 4:
        	  DisplyStack(p); break;	
        	case 5:
        	  x1=StackEmpty(p);
        	  if(x1==0){ 
        	  	printf("栈为空！\n");
    		  }else if(x1==1){ 
    		  	printf("栈满！\n");
    		  }else{ 
    		  	printf("可用！\n");
    		  }
    		   break;
        	case 6:
        	  x=StackFull(p); 
    		   if(x==0){ 
        	  	printf("栈为空！\n");
    		  }else if(x==1){ 
    		  	printf("栈满！\n");
    		  }else{ 
    		  	printf("可用！\n");
    		  }
    		  break;
    	}
       }//else
       printf("----按任意键继续！"); 
        getch();
        menu01();
        scanf("%d",&n);
      }//while
    }
    
    void menu01(){ 
    	system("cls");
    	printf("-----------顺序栈------------\n");
    	printf("1-初始化栈\n");
    	printf("2-入栈\n");
    	printf("3-出栈\n");
    	printf("4-遍历栈中元素\n");
    	printf("5-判断栈中元素是否为空\n");
    	printf("6-判断栈中元素是否已满\n");
    	printf("0-退出\n");
    	printf("------------------------------\n");
    	printf("请选择操作代码:");
    	
    }
    
    /* Function：判断栈是否为空 */
    int StackEmpty (stack p)
    { 
        if (p.top == p.bottom)
        { 
            return Empty;
        }
        else
        { 
            return Avail;
        }
    }
    /* Function：判断栈是否为满 */
    int StackFull (stack p)
    { 
        if (p.top - p.bottom == p.stack_size)
        { 
            return Full;
        }
        else
        { 
            return Avail;
        }
    }
    /* Function：入栈 */
    stack Push(stack p)
    { 
        int data;
        if(p.stack_size!=MAX_SIZE){ 
        	printf("栈未初始化！\n");
        	return p;
    	}
        if (StackFull(p) == Full)
        { 
            printf("栈空间已满，无法入栈");
            return p;
        }
        printf("请输入int数据:");
        scanf("%d", &data);
           *p.top = data;
           p.top++;
           printf("入栈成功！\n");
           return p;
       }
    /* Function：出栈 */
    stack Pop(stack p)
    { 
    	if(p.stack_size!=MAX_SIZE){ 
        	printf("栈未初始化！\n");
        	return p;
    	}
        if (StackEmpty(p) == Empty)
        { 
            printf("栈为空栈，无法出栈 ");
            return p;
        }
        p.top--;
        printf("出栈元素为：%d\n", *p.top);
    
        return p;
    }
    /* Function：栈的初始化 */
    stack InitStack(stack p)
    { 
        p.bottom = (ElemType *)malloc(p.stack_size * sizeof(ElemType));
        if (p.bottom == NULL)
        { 
            printf("初始化失败\n");
            exit(0);
        }
        p.top = p.bottom;
        p.stack_size = MAX_SIZE;
        printf("初始化成功！\n"); 
        return p;
    }
    /* Function：遍历栈中元素，从栈顶到栈底*/
    void DisplyStack(stack p)
    { 
    	if(p.stack_size!=MAX_SIZE){ 
        	printf("栈未初始化！\n");
        	return;
    	}
        if ( p.top==p.bottom)
        { 
            printf("栈为空栈，无法遍历\n");
            return;
        }
        printf("栈中元素为：");
        printf("顶端[");
        while (p.top != p.bottom)
        { 
            p.top--;
            printf(" < %d", *p.top);
        }
        printf("]底端\n");
    }

#### 程序不再细细讲解，请大家参照注释自行理解 ####

[20210415130214602.gif_pic_center]: /images/20221022/bef04a14aa004f65a7ddf6be3a234425.png