数据结构与数据库实验（数据结构部分）——实验2 ADT栈与队列的编程与实现

一、实验目的

加深对抽象数据类型ADT栈和队列的理解；

二、实验原理

参照课本p.64-66，及Figure3.39-3.44；

课本p.82-83，及Figure3.57-3.60.

三、实验内容

编写程序实现ADT栈的定义，及常用操作（数组或指针实现）：

生成栈；
Push
Pop

编写程序实现ADT队列的定义，及常用操作：

生成队列；
Enqueues入列；
IsEmpty判断是否队列为空。

四、实验要求

实现ADT栈的结构及操作；
实现ADT队列的结构及操作，并给出应用。

五、实验源程序

ADT栈实验代码

ADTStack.h 头文件

#ifndef _ADTStack_H
struct Node;
typedef struct Node *PtyToNode;
typedef PtyToNode Stack;

Stack CreatStack(); /*创建栈*/
void PushStack(int X, Stack S); /*入栈*/
void PopStack(Stack S); /*出栈*/
int GetTop(Stack S);    /*Top操作*/
void GetAll(Stack S);   /*遍历输出栈*/

#endif //

ADTStack.c 主程序文件

#include <stdio.h>
#include<stdlib.h>
#include <ADTStack.h>
#define MaxSize 100
struct Node 
{ 
     int *base; 
     int *top; 
     int stacksize; 
};

Stack CreatStack()
{
    Stack S = (Stack)malloc((sizeof(struct Node)));
    S->base = (int *)malloc(MaxSize);
    if(!S->base) printf("栈初始化失败！");
    S->top = S->base;
    printf("栈初始化成功！\n");
    return S;
}

void PushStack(int X,Stack S)
{
    if(S->top-S->base==S->stacksize)    printf("栈已满！");
    else{
    S->top++;
    *(S->top) = X;
    }
}

void PopStack(Stack S)
{
    if(S->top==S->base) printf("栈为空！");
    else
    {
        printf("栈顶值为%d，已取出\n", *(S->top));
        S->top--;
    }
}

int GetTop(Stack S)
{
    if(S->top==S->base) {
    printf("栈为空！\n");
    return 0;
    }
    return *(S->top);
}

void GetAll(Stack S)
{
    int i;
    if(S->top==S->base) printf("栈为空！\n");
    else
    {
        printf("栈内数据如下：\n");
        i = S->top-S->base;
        for(int j = 0; j < i; j++)
        {
            printf("%d\n",*(S->top-j));
        }
    }
}

int main(void)
{
    int temp,pushnum,popnum,value;
    Stack S = CreatStack();
    while (1) 
    {
        printf("请选择要进行的操作：1.压栈  2.出栈  3.读栈顶    4.读栈\n");
        scanf_s("%d", &temp);
        switch (temp)
        {
        case 1:
            printf("请输入要压入栈数据的个数：");
            scanf_s("%d", &pushnum);
            printf("\n");
            for (int n = 0; n < pushnum;n++)
            {
                printf("请输入要压入栈的数据：");
                scanf_s("%d", &value);
                PushStack(value, S);
                printf("\n");
            }
            break;
        case 2:
            printf("请输入要出栈数据的个数：");
            scanf_s("%d", &popnum);
            printf("\n");
            for (int n = 0; n < popnum; n++)
                PopStack(S);
            break;
        case 3:
            printf("当前栈顶数据为：%d\n", GetTop(S));
            break;
        case 4:
            GetAll(S);
            break;
        default:
            break;
        }
    }
}

ADT队列代码

ADTArray.h 头文件

#ifndef _ADTArray_H
struct Node;
typedef struct Node *PtyToNode;
typedef PtyToNode Array;

Array CreatArray();    //生成队列
int IsEmpty(Array A);       //判断队列是否为空
void EnterArray(Array A,int X);   //入队列


#endif // !1

ADTArray.c 主程序文件

#include <ADTArray.h>
#include <stdio.h>

struct Node
{
    int data[100];
    int front;
    int behind;
    int size;
};

Array CreatArray()
{
    Array A = (Array)malloc(sizeof(struct Node));
    A->front = 0;
    A->behind = 0;
    A->size = 0;
    printf("初始化队列成功！\n");
    return A;
}

int Isempty(Array A)
{
    return A->size == 0;
}

void EnterArray(Array A,int X)
{
    A->data[A->behind] = X;
    A->behind++;    
    A->front = A->behind-1;
    A->size++;  
}

void PrintArray(Array A)
{
    

    printf("当前队列为：\n");
    for(int i = 0; i < A->size; i++)
    printf("%d\n", A->data[i]);
}

int main(void)
{
    int i,temp,n,c;
    Array A = CreatArray();
    while (1)
    {
        printf("请选择要进行的操作：1.入列  2.显示队列  3.判断队列是否为空\n");
        scanf_s("%d", &temp);
        switch (temp)
        {
        case 1:
            printf("请输入需要入列的数据个数：");
            scanf_s("%d", &n);
            printf("\n");
            for (i = 0; i < n; i++)
            {
                printf("请输入需要入列的数据：");
                scanf_s("%d", &c);
                EnterArray(A, c);
                printf("\n");
            }
            printf("入列完成！\n");
            break;
        case 2:
            PrintArray(A);
            break;
        case 3:
            if (IsEmpty(A))
                printf("该队列为空队列！\n");
            else printf("该队列不是空队列！\n");
            break;
        }
    }
}