链栈的建立和基本操作-数据结构与算法-C语言

实验项目名称：栈的建立及操作

一、实验目的

1．掌握栈的存储结构的表示和实现方法。
2．掌握栈的入栈和出栈等基本操作算法实现。

二、 实验题

建立链栈，完成如下操作。

1. 初始化链栈
2. 插入元素
3. 删除栈顶元素
4. 取栈顶元素
5. 遍历链栈
6. 置空链栈

三、 实验过程及结果

基本思路：
建立一个没有头指针的链表，定义它的数据类型，它的结点由两部分组成，数据域和一个指向下一个结点的指针，头指针也就是它开辟的空间的首地址，头指针指向栈顶元素，入栈和 出栈操作只能在栈顶进行。
程序代码：

    #include<stdio.h>  
    #include<stdlib.h>  
    #define OK 1  
    #define ERROR 0  
    #define TRUE 1  
    #define FALSE 0  
    typedef int Status;  
    typedef int SElemType;  
    typedef struct Node  
    {  
        SElemType data;//数据域   
        struct Node *next;//定义一个指向下一结点的指针   
    }StackNode,*LinkStack;  
    LinkStack S;  
    //链栈的初始化   
    Status InitStack(LinkStack S)  
    {  
        //构造一个空栈，栈顶指针置为空   
        S=NULL;  
        return OK;  
    }  
    // 判断链栈是否为空  
    /*Status StackEmpty(LinkStack S) 
    { 
        if(S==NULL) 
        return TRUE; 
        else 
        return FALSE; 
    } 
    */  
    //入栈  
    Status Push(LinkStack &S,int n)  
    {  
        SElemType e;  
        LinkStack p;  
        //通过循环依次将输入的元素入栈   
        while(n)  
        {  
        scanf("%d",&e);  
        p=new StackNode; //生成新结点   
        p->data=e; //将p的数据域置为要插入的数据  
        p->next=S; //将新结点插入栈顶   
        S=p;  //修改栈顶指针   
        n--;//元素个数减一   
        }  
        return OK;  
     }   
    //出栈  
    Status Pop(LinkStack &S,int x)  
    {  
        SElemType e;  
        LinkStack p;  
        p=new StackNode;  
        if(!S)return ERROR;//判断栈是否为空  
        int bianliStack(LinkStack S);   
        int t=bianliStack(S);  
        if(x<0||x>t)//判断输入的出栈元素个数是否合理   
        return ERROR;  
        //通过循环依次将元素从栈顶出栈  
        else  
        {  
            while(x)  
          {  
            e=S->data;//将要出栈的元素的值保存在e中   
            p=S;  
            S=S->next;  
            printf("The element of pop is %d\n",e);  
            x--;  
            delete p;//释放结点   
          }  
          return OK;  
        }  
          
    }  
      
    //取栈顶元素  
    int GetTop(LinkStack S)  
    {  
        if(!S)return ERROR;//判断栈是否为空   
        else  
        return S->data;  
    }   
    //遍历链栈  
    int bianliStack(LinkStack S)  
    {  
        LinkStack p;  
        p=new StackNode;//生成一个新结点   
        p=S;//链栈从栈顶所指向的指针开始   
        int i=0;  
        while(p)  
        {  
            printf("%d ",p->data);//将此时指针所指向的元素的值输出   
            p=p->next;//指针指向下一个结点  
            i++;   
        }  
        printf("\n");  
        return i;  
    }  
    //置空链栈  
    Status ClearStack(LinkStack &S)  
    {  
        S=NULL;  
        return OK;  
    }  
    //主函数测试  
    int main()  
    {  
        SElemType e;  
        if(InitStack(S))  
        printf("InitStack success\n");  
        printf("请输入要插入的元素个数及元素：\n");  
        int n;  
        scanf("%d",&n);  
        if(Push(S,n))  
        printf("The Element of push success\n");  
        printf("栈顶元素是：%d\n",GetTop(S));  
        printf("此时遍历栈链的元素分别是：\n");  
        bianliStack(S);  
        printf("请输入要出栈的元素个数：\n");  
        int x;  
        scanf("%d",&x);  
        if(Pop(S,x))  
        printf("The Element of pop is success\n");  
        else  
        printf("Pop error\n");  
        printf("此时遍历栈链的元素分别是：\n");  
        bianliStack(S);  
        if(ClearStack(S))  
        printf("\nClearStack success\n");  
        return 0;  
     }   

运行结果：

四、 实验总结

1. 链栈的初始化只需将头结点指针指向NULL即可；
2. 链栈的数据类型：定义一个结构体类型，有两个成员，数据域和指针域；
3. 与顺序栈相比，链栈不存在栈满的情况；
4. 出栈需要判断栈是否为空；
5. 链栈没有设置头结点，头指针指向的 是栈顶元素；
6. 入栈和出栈操作只能在栈顶进行，在一头进行，有利于链表的插入和删除操作。