数据结构实验三：顺序栈和链栈

栈的基本操作

1 实验目的

1. 掌握栈的顺序及链式存储结构
2. 验证顺序栈、链栈及其他们的基本操作实现
3. 验证栈的操作特性

2 实验内容

1. 建立一个空栈
2. 对已经建立的栈进行插入、删除、取栈顶元素等基本操作。

3 软件程序

3.1 顺序栈

main.cpp：

#include<stdio.h>  
#include<stdlib.h>  
#include<malloc.h>  
/*将顺序表或单链表的结构定义和顺序栈或链栈的各个函数定义放到这里*/  
#include "sqstack.cpp"  
  
  
int main()  
{  
    ElemType e;  
    SqStack *s;  
    printf("顺序栈s的基本运算如下:\n");  
    printf("  (1)初始化栈s\n");  
    InitStack(s);  
    printf("  (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (3)依次进栈元素a,b,c,d,e\n");  
    Push(s,'a');  
    Push(s,'b');  
    Push(s,'c');  
    Push(s,'d');  
    Push(s,'e');  
    printf("  (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (5)出栈序列:");  
    while (!StackEmpty(s))  
    {  
        Pop(s,e);  
        printf("%c ",e);  
    }  
    printf("\n");  
    printf("  (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (7)释放栈\n");  
    DestroyStack(s);  
    return 1;  
}  

sqstack.cpp：

#include<stdio.h>  
#include<malloc.h>  
  
#define Maxsize 100  
  
typedef char ElemType;  
typedef struct  
{  
    ElemType data[Maxsize];  
    int top;  
}SqStack;  
  
void InitStack(SqStack *&s)//初始化栈s  
{  
    s=(SqStack*)malloc(sizeof(SqStack));  
    s->top=-1;  
}  
  
void DestroyStack(SqStack *&s)//销毁栈s   
{  
    free(s);  
}  
  
bool StackEmpty(SqStack *s)//判断栈s是否为空   
{  
    return(s->top==-1);  
}  
  
bool Puch(SqStack *&s,ElemType e)//进栈   
{  
    if(s->top==Maxsize-1)  
        return false;  
    s->top++;  
    s->data[s->top]=e;  
    return true;  
}  
  
bool Pop(SqStack *&s,ElemType &e)//出栈   
{  
    if(s->top==-1)//栈为空时候的情况   
        return false;  
    e=s->data[s->top];  
    s->top--;  
    return true;  
}   
bool GetTop(SqStack *&s,ElemType &e)//取栈顶元素   
{  
    if(s->top==-1)//栈为空的情况   
        return false;  
    e=s->data[s->top];  
    return true;  
}  

3.2 链栈

main.cpp：

#include<stdio.h>  
#include<stdlib.h>  
#include<malloc.h>  
/*将顺序表或单链表的结构定义和顺序栈或链栈的各个函数定义放到这里*/  
#include "listtack.cpp"  
  
  
  
/*                                                              */  
int main()  
{  
ElemType e;  
    LinkStNode *s;  
    printf("链栈s的基本运算如下:\n");  
    printf("  (1)初始化栈s\n");  
    InitStack(s);  
    printf("  (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (3)依次进栈元素a,b,c,d,e\n");  
    Push(s,'a');  
    Push(s,'b');  
    Push(s,'c');  
    Push(s,'d');  
    Push(s,'e');  
    printf("  (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (5)出栈序列:");  
    while (!StackEmpty(s))  
    {  
        Pop(s,e);  
        printf("%c ",e);  
    }  
    printf("\n");  
    printf("  (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));  
    printf("  (7)释放栈\n");  
    DestroyStack(s);  
    return 1;  
}     

listtack.cpp：

#include<stdio.h>  
#include<malloc.h>  
  
typedef int ElemType;  
  
typedef struct linknode{  
    ElemType data;  
    struct linknode *next;  
}LinkStNode;  
  
void InitStack(LinkStNode * &s)//初始化栈  
{  
    s = (LinkStNode *)malloc(sizeof(LinkStNode));  
    s->next = NULL;  
}  
  
void DestroyStack(LinkStNode * &s)//销毁栈  
{  
    LinkStNode *pre = s,*p = s->next;  
    while (p!=NULL)  
    {  
        free(pre);  
        pre = p;  
        p = pre->next;  
    }  
    free(pre);  
}  
  
bool StackEmpty(LinkStNode * &s)//判断栈是否为空  
{  
    return (s->next == NULL);  
}  
  
  
  
  
void Push(LinkStNode * &s, ElemType e)//入栈   
{  
    LinkStNode *p;  
    p = (LinkStNode * )malloc(sizeof(LinkStNode));  
    p->data = e;  
    p->next = s->next;  
    s->next = p;  
}  
  
bool Pop(LinkStNode * &s, ElemType &e)//出栈  
{  
    LinkStNode *p;      //临时节点  
    if(s->next == NULL)  
        return false;  
    p = s->next;  
    e = p->data;  
    s->next = p->next;  
    free(p);  
    return true;  
}  
  
bool GetTop(LinkStNode * s, ElemType &e)//获取栈顶元素  
{  
    if(s->next==NULL)  
        return false;  
    e = s->next->data;  
    return true;  
}  

4 实验结果