淮海工学院数据结构第二次实验.doc

淮海工学院计算机科学系
实验报告书

课程名： 《数据结构》
题 目： 线性数据结构实验
（栈与队列及其应用）
班 级： 软嵌151
学 号： 2015123352
姓 名： 韩吉

评语：

成绩： 指导教师：

批阅时间： 年 月 日

线性表算法实现与应用报告要求
1目的与要求:
1）掌握栈与队列的数据类型描述及特点；
2）掌握栈的顺序和链式存储存表示与基本算法的实现；
3）掌握队列的链式和循环存储表示与基本操作算法实现;
4) 掌握栈与队列在实际问题中的应用和基本编程技巧;
5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例的运行过程抓获相关屏面验证程序设计的正确性；
7）希望大家过一个丰富多彩的国庆节，抽出一定时间圆满完成实验，并于第6周周二以前按时提交实验报告，逾期按照旷交处理。
2 实验内容或题目
（一）必做题：
1、实现顺序栈的创建（初始化）、压入（插入）操作（数据、弹出（删除）元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并给出栈的每次操作变化状态；
2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），要求给出栈的操作变化过程；
3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态；
4、实现链式队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态；
（注意：必做题需用一个主程序实现所有功能）
（二）选做题（视自己能力而定，数量不限）：任选下列一个或多个栈或队列应用源程序（已经发给学委），并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示；
1、实现表达式求值算法程序；
2、用递归算法实现汉诺塔问题算法程序；
3、使用循环队列实现打印杨辉三角形算法程序。

3 实验步骤与源程序
#include<stdio.h>
#include<stdlib.h>
#include <windows.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
#define MAXSIZE 5
void mainmenu();
/*********************************************/
/*顺序栈*/

typedef struct{
int elem[Stack_Size];
int top;
}SeqStack;

/*链栈*/
typedef struct node
{
int data;
struct node *next;
}LinkStackNode;

/*循环队列*/
typedef struct{
int element[MAXSIZE];
int front;
int rear;
}SeqQueue;

/*链式队列*/
typedef struct Node{
int data;
struct Node *next;
}LinkQueueNode;
typedef struct{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;

/*********************************************/

/********************顺序栈************************/
/*构造一个空栈S*/
void InitStack(SeqStack *S)
{
S->top = -1;
}

/*进栈*/
int Push(SeqStack *S,int x)
{
if(S->top==(Stack_Size-1))
return(FALSE); /*栈已满*/
S->top++;
S->elem[S->top]=x;
return(TRUE);
}

/*出栈*/
int Pop(SeqStack *S,int *x)
{
/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
if(S->top==-1) /*栈为空*/
return(FALSE);
else
{
*x=S->elem[S->top];
S->top--; /* 修改栈顶指针 */
return(TRUE);
}
}

/*取栈顶元素*/
int GetTop(SeqStack *S, int *x)
{
/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
if(S->top==-1) /*栈为空*/
return(FALSE);
else
{
*x = S->elem[S->top];
return(TRUE);
}
}

/**************************************************/

/********************链栈**************************/
/*初始化*/
void InitStack1(LinkStackNode *top)
{ //构造一个空栈
top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if(!top)
printf("OVERFLOW\n");
top = NULL;

}

/*进栈操作。*/
int Push1(LinkStackNode *top, int x)/* 将数据元素x压入栈top中 */
{
LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp==NULL)
return(FALSE); /* 申请空间失败 */
temp->data=x;
temp->next=top->next;
top->next=temp; /* 修改当前栈顶指针 */
return(TRUE);
}

/*出栈操作。*/
int Pop1(LinkStackNode *top, int *x)
{
/* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */
LinkStackNode * temp;
temp=top->next;
if(temp==NULL) /*栈为空*/
return(FALSE);
top->next=temp->next;
*x=temp->data;
free(temp); /* 释放存储空间 */
return(TRUE);
}

/**************************************************/
/******************循环队列*************************/
void InitQueue(SeqQueue *Q)
{
/* 将*Q初始化为一个空的循环队列 */
Q->front=Q->rear=0;
}

int EnterQueue(SeqQueue *Q,int x)
{
/*将元素x入队*/
if((Q->rear+1)%MAXSIZE==Q->front) /*队列已经满了*/
return(FALSE);
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE; /* 重新设置队尾指针 */
return(TRUE); /*操作成功*/
}

int DeleteQueue(SeqQueue *Q,int *x)
{
/*删除队列的队头元素，用x返回其值*/
if(Q->front==Q->rear) /*队列为空*/
return(FALSE);
*x=Q->element[Q->front];
Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/
return(TRUE); /*操作成功*/
}

/********************************************************/

/**********************链式队列**************************/

int InitQueue1(LinkQueue *O)
{
/* 将Q初始化为一个空的链队列 */
O->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(O->front!=NULL)
{
O->rear=O->front;
O->front->next=NULL;
return(TRUE);
}
else return(FALSE); /* 溢出！*/
}

int EnterQueue1(LinkQueue *O,int x)
{
/* 将数据元素x插入到队列Q中 */
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{
NewNode->data=x;
NewNode->next=NULL;
O->rear->next=NewNode;
O->rear=NewNode;
return(TRUE);
}
else
return(FALSE); /* 溢出！*/
}

int DeleteQueue1(LinkQueue *O, int *x)
{
/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
LinkQueueNode *p;
if(O->front==O->rear)
return(FALSE);
p=O->front->next;
O->front->next=p->next; /* 队头元素p出队 */
if(O->rear==p) /* 如果队中只有一个元素p，则p出队后成为空队 */
O->rear=O->front;
*x=p->data;
free(p); /* 释放存储空间 */
return(TRUE);
}

/********************************************************/

void mainmenu1(){

int chioce;
int m;
int x1, x2;
SeqStack s;
while(chioce)
{
printf(" ************** 请输入你的选择 **************\n");
printf(" ************** 1:初始化操作 **************\n");
printf(" ************** 2:进栈操作 **************\n");
printf(" ************** 3:出栈操作 **************\n");
printf(" ************** 4:取栈顶元素 **************\n");
printf(" ************** 5:返回主菜单 **************\n");

printf("请输入你的选择:");
scanf("%d", &chioce);
switch(chioce)
{
case 1:
InitStack(&s);
printf("初始化完成!\n");
break;
case 2:
printf("输入进栈元素:");
scanf("%d", &m);
if(Push(&s,m))
printf("进栈成功!\n");
else
printf("栈已满!\n");
break;
case 3:
if(Pop(&s,&x1))
printf("出栈元素:%d\n", x1);
else
printf("栈为空!\n");
break;
case 4:
if(GetTop(&s,&x2))
printf("栈顶元素:%d\n", x2);
else
printf("栈为空!\n");
break;
case 5:
printf("\n\n\n\n");
system("cls");
mainmenu();
break;
default:
printf("输入有误!\n");
for(int i = 2; i > 0; i--)
{
printf("请等待%d秒后重新输入!\n",i);
Sleep(1000);
}
system("cls");
mainmenu1();
break;
}
}
}

void mainmenu2(){
int chioce2;
int x;
int x1;
LinkStackNode top;

while(chioce2)
{
printf(" *************** 请输入你的选择 ***************\n");
printf(" *************** 1:初始化操作 ***************\n");
printf(" *************** 2:进栈操作 ***************\n");
printf(" *************** 3:出栈操作 ***************\n");
printf(" *************** 4:返回主菜单 ***************\n");

printf("请输入你的选择:");
scanf("%d", &chioce2);
switch(chioce2)
{
case 1:
InitStack1(&top);
printf("初始化完成!\n");
break;
case 2:
printf("输入进栈元素:");
scanf("%d", &x);
if(Push1(&top,x))
printf("进栈成功!\n");
else
printf("栈已满!\n");
break;
case 3:
if(Pop1(&top,&x1))
printf("出栈元素:%d\n", x1);
else
printf("栈为空!\n");
break;
case 4:
printf("\n\n\n\n");
system("cls");
mainmenu();
break;
default:
printf("输入有误!\n");
for(int i = 2; i > 0; i--)
{
printf("请等待%d秒后重新输入!\n",i);
Sleep(1000);
}
system("cls");
mainmenu2();
break;
}
}
}

void mainmenu3(){
int chioce3;
int x;
int x1;
SeqQueue Q;

while(chioce3)
{
printf(" *************** 请输入你的选择 ***************\n");
printf(" *************** 1:初始化操作 ***************\n");
printf(" *************** 2:进栈操作 ***************\n");
printf(" *************** 3:出栈操作 ***************\n");
printf(" *************** 4:返回主菜单 ***************\n");

printf("请输入你的选择:");
scanf("%d", &chioce3);
switch(chioce3)
{
case 1:
InitQueue(&Q);
printf("初始化完成!\n");
break;
case 2:
printf("输入进栈元素:");
scanf("%d", &x);
if(EnterQueue(&Q,x))
printf("进栈成功!\n");
else
printf("栈已满!\n");
break;
case 3:
if(DeleteQueue(&Q,&x1))
printf("出栈元素:%d\n", x1);
else
printf("栈为空!\n");
break;
case 4:
printf("\n\n\n\n");
system("cls");
mainmenu();
break;
default:
printf("输入有误!\n");
for(int i = 2; i > 0; i--)
{
printf("请等待%d秒后重新输入!\n",i);
Sleep(1000);
}
system("cls");
mainmenu3();
break;

}
}
}

void mainmenu4(){

int chioce4;
int x;
int x1;
LinkQueue O;

while(chioce4)
{
printf(" *************** 请输入你的选择***************\n");
printf(" *************** 1:初始化操作 ***************\n");
printf(" *************** 2:进栈操作 ***************\n");
printf(" *************** 3:出栈操作 ***************\n");
printf(" *************** 4:返回主菜单 ***************\n");

printf("请输入你的选择:");
scanf("%d", &chioce4);

switch(chioce4)
{
case 1:
InitQueue1(&O);
printf("初始化完成!\n");
break;
case 2:
printf("输入进栈元素:");
scanf("%d", &x);
if(EnterQueue1(&O,x))
printf("进栈成功!\n");
else
printf("栈已满!\n");
break;
case 3:
if(DeleteQueue1(&O,&x1))
printf("出栈元素:%d\n", x1);
else
printf("栈为空!\n");
break;
case 4:
printf("\n\n\n\n");
system("cls");
mainmenu();
break;
default:
printf("输入有误!\n");
for(int i = 2; i > 0; i--)
{
printf("请等待%d秒后重新输入!\n",i);
Sleep(1000);
}
system("cls");
mainmenu4();
break;
}
}
}

void mainmenu(){

int chioce1;
printf("************************************ 主菜单 ********************************* \n");
printf(" *************** 1:顺序栈操作 *************** \n");
printf(" *************** 2:链栈操作 *************** \n");
printf(" *************** 3:循环队列 *************** \n");
printf(" *************** 4:链式队列 *************** \n");
printf(" *************** 0:退出操作 *************** \n");

printf("请输入你的选择:");
scanf("%d", &chioce1);
switch(chioce1)
{
case 1:
mainmenu1();
break;
case 2:
mainmenu2();
break;
case 3:
mainmenu3();
break;
case 4:
mainmenu4();
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误!\n");
for(int i = 3; i > 0; i--)
{
printf("请等待%d秒后重新输入!\n",i);
Sleep(1000);
}
system("cls");
mainmenu();
break;
}
}
void main()
{
system("color 0");
system("color bc");
mainmenu();
}

杨辉三角:
#include "seqqueue1.h"
#include <stdio.h>

void YangHuiTriangle( )
{
int n;
int i;
int temp;
int x;
int N;
SeqQueue Q;
InitQueue(&Q);
EnterQueue(&Q,1); /* 第一行元素入队*/
printf("please input N:");
scanf("%d",&N);
for(n=2;n<=N;n++) /* 产生第n行元素并入队，同时打印第n-1行的元素*/
{
EnterQueue(&Q,1); /* 第n行的第一个元素入队*/
for(i=1;i<=n-2;i++) /* 利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/
{
DeleteQueue(&Q,&temp);
printf("%6d",temp); /* 打印第n-1行的元素*/
GetHead(&Q,&x);
temp=temp+x; /*利用队中第n-1行元素产生第n行元素*/
EnterQueue(&Q,temp);
}
DeleteQueue (&Q,&x);
printf("%6d",x); /* 打印第n-1行的最后一个元素*/
EnterQueue(&Q,1); /* 第n行的最后一个元素入队*/
printf("\n");
}
}

void main()
{
YangHuiTriangle( );
}
汉诺塔：
#include "stdio.h"

move(char a,char c,FILE **fp,int *count)
{
(*count)++;
printf("%6d:%c-->%c\n",*count,a,c);
fprintf(*fp,"%6d:%c-->%c\n",*count,a,c);
}

hanoi(int n, char a, char b, char c, FILE **fp, int *count)
{
if(n==1) move(a,c,fp,count);
else
{
hanoi(n-1,a,c,b,fp,count);
move(a,c,fp,count);
hanoi(n-1,b,a,c,fp,count);
}
}

main()
{
int n,count=0; /*count用来记录移动次数*/
FILE *fp;
fp=fopen("hanoi.txt","w");
printf("Input the number of disk:");
scanf("%d",&n);
fprintf(fp,"%d disks hanoi tower:\n",n);
hanoi(n,'A','B','C',&fp,&count);
fclose(fp);
}

4 测试数据与实验结果（可以抓图粘）
顺序栈操作

链栈操作

循环队列

链式队列

杨辉三角：

汉诺塔:

5 结果分析与实验体会
（1） 此次试验加深了对链表与栈的理解，能了解对栈的基本操作；
（2） 能实现顺序栈以及链栈的创建、压入、弹出操作