数据结构课程实验实训报告堆栈和队列的基本操作.doc

数据结构课程实验实训报告堆栈和队列的基本操作

13
2020年4月19日
文档仅供参考，不当之处，请联系改正。
《数据结构》课程实验实训报告
实验名称
栈与队列
实验序号
3
学 号
14302043
姓 名
陈前方
班 级
信管本二
实验日期
.11.15
指导教师
金照林
成 绩

一、实验目的和要求
目的：掌握堆栈和队列数据结构描述，学会针对堆栈和队列的基本操作。
要求：掌握C语言结构化程序设计思想，结构数据类型，指针数据类型。
二、实验具体内容及步骤
1. 实现课本中链式堆栈（p64-p66）的基本操作，并编制主函数实际运行验证其正确性。
2. 链式堆栈设计。要求：
（1） 用链式堆栈设计实现堆栈，堆栈的操作集合包括：初始化、非空否、入栈、出栈、取栈顶数据元素。
（2） 设计一个主函数对链式堆栈进行测试。测试方法为依次把数据元素1、2、3、4、5入栈，然后出栈并在屏幕上显示出栈的数据元素。
（3） 定义数据元素的数据类型为如下形式的结构体：
typedef struct{
char taskName[10]; //任务名
int taskNo; //任务号
}DataType;
首先设计一个包含5个数据的测试数据，然后设计一个主函数对链式堆栈进行测试。测试的方法为：依次把5个元素入栈，然后出栈并在屏幕上显示出栈的数据元素。
3. 实现课本中顺序循环队列（p75-p77）的基本操作，并编制主函数实际运行验证其正确性。
4. 对顺序循环队列，常规的方法是使用队尾指针和队头指针，队尾指针用于指示当前的队尾位置下标，队头指针用于指示当前的队头位置下标。现要求：
（1） 设计一个使用队头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化、入队列、出队列、取队头元素和判断队列是否为空。
（2） 设计一个测试主函数进行测试。
三、实验结果与分析（程序代码按序粘贴在下面，并将运行结果截图）
1．#include<stdio.h>
#include<stdlib.h>
typedef int DataType;

typedef struct snode
{
DataType data;
struct snode *next;
} LSNode; /*初始化操作：*/
void StackInitiate(LSNode **head)
/*初始化带头结点链式堆栈*/
{
if((*head = (LSNode *)malloc(sizeof(LSNode))) == NULL) exit(1);
(*head)->next = NULL;
} /*判非空操作：*/
int StackNotEmpty(LSNode *head) /*判堆栈是否非空，非空返回1；空返回0*/
{
if(head->next == NULL) return 0; else return 1;
} /*入栈操作：*/
int StackPush(LSNode *head, DataType x) /*把数据元素x插入链式堆栈head的栈顶作为新的栈顶 */ { LSNode *p; if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL) { printf("内存空间不足无法插入! \n"); return 0; } p->data = x; p->next = head->next; /*新结点链入栈顶*/ head->next = p; /*新结点成为新的栈顶*/ return 1; } /*出栈操作：*/
int StackPop(LSNode *head, DataType *d) /*出栈并把栈顶元素由参数d带回*/ { LSNode *p = head->next; if(p == NULL) {
printf("堆栈已空出错！");
return 0;
}
head->next = p->next; /*删除原栈顶结点*/
*d = p->data; /*原栈顶结点元素赋予d*/
free(p); /*释放原栈顶结点内存空间*/
return 1;
} /*取栈顶数据元素操作：*/
int StackTop(LSNode *head, DataType *d) /*取栈顶元素并把栈顶元素由参数d带回*/
{
LSNode *p = head->next;
if(p == NULL)
{
printf("堆栈已空出错！");
return 0;
}
*d = p->data;
return 1;
} /*撤销*/
void Destroy(LSNode *head)
{
LSNode *p, *p1;
p = head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
}

void main(void)
{
LSNode *myStack;
int i, x;
StackInitiate(&myStack);
for(i=0;i<5;i++)
{
if(StackPush(myStack,i+1)==0)
{
printf("error!\n");
return;
}
}
if(StackTop(myStack,&x)==0)
{
printf("error!\n");
return;
}
else
printf("The element of local top is :%d\n",x);
printf("The sequence of outing elements is:\n");
while(StackNotEmpty(myStack))
{
StackPop(myStack, &x);
printf("%d ", x);
}
printf("\n");
Destroy(myStack);
printf("This program is made by10273206\n");
}

2．#include<stdio.h>
#include<stdlib.h>
#define MaxStackSize 100
typedef int DataType;

typedef struct
{
DataType stack[MaxStackSize];;
int top;
} SeqStack; /*初始化操作：*/
void StackInitiate(SeqStack *S)
/*初始化带头结点链式堆栈*/
{
S->top=0;
}
int StackNotEmpty(SeqStack S)
{
if(S.top<=0)
return 0;
else
return 1;
} /*入栈操作：*/
int StackPush(SeqStack *S, DataType x) {
if(S->top>=MaxStackSize)
{
printf("堆栈已满无法插入!\n");
return 0;
}
else
{
S->stack[S->top]=x;
S->top++;
return 1;
}
}
int StackPop(SeqStack *S, DataType *d)
{
if(S->top<=0)
{
printf("堆栈已空无数据元素出栈!\n");
return 0;
}
else
{
S->top--;
*d=S->stack[S->top];
return 1;
}
}
int StackTop(SeqStack S, DataType *d)
{
if(S.top<=0)
{
printf("堆栈已空!\n");
return 0;
}
else
{
*d=S.stack[S.top-1];
return 1;
}
}

void main(void)
{
SeqStack myStack;
int i,x;
StackInitiate(&myStack);
for(i=0;i<5;i++)
{
if(StackPush(&myStack,i+1)==0)
{
printf("错误\n");
return;
}
}
if(StackTop(myStack,&x)==0)
{
printf("错误\n");
return;
}
else
printf("当前栈顶元素为：%d\n",x);
printf("依次出栈的数据元素序列如下：\n");
while(StackNotEmpty(myStack))
{
StackPop(&myStack,&x);
printf("%d ",x);
}
}

3．#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define MaxQueueSize 100

typedef int DataType;

typedef struct
{
DataType queue[MaxQueueSize];
int rear ;
int front;
int count;
} SeqCQueue ;

void QueueuInitiate(SeqCQueue *Q)
{
Q->rear=0;
Q->front=0;
Q->count=0;
}

int QueueNotEmpty(SeqCQueue Q)
{
if(Q.count!=0)
return 1;
else
return 0;
}
int QueueAppend(SeqCQueue *Q,DataType x)
{
if(Q->count>0&&Q->rear==Q->front)
{
printf("队列已满无法插入！\n");
return 0;
}
else
{
Q->queue[Q->rear]=x;
Q->rear=(Q->rear+1)%MaxQueueSize;
Q->count++;
return 1;
}
}

int QueueDelete(SeqCQueue *Q,DataType *d)
{
if(Q->count==0)
{
printf("队列已空无数据元素出队列!\n");
return 0;
}
else
{
*d=Q->queue[Q->front];
Q->front=(Q->front+1)%MaxQueueSize;
Q->count--;
return 1;
}
}
int QueueGet(SeqCQueue Q,DataType *d)
{
if(Q.count==0)
{
printf("队列已空无数据可取\n");
return 0;
}
else
{
*d=Q.queue[Q.front];
return 1;
}
}
void main(void)
{
SeqCQueue myQueue;
int i,x;
QueueuInitiate(&myQueue);
for(i=0;i<5;i++)
{
if(QueueAppend(&myQueue,i+1)==0)
{
printf("error!\n");
return;
}
}
if(QueueGet(myQueue,&x)==0)
{
printf("error!\n");
return;
}
else
printf("队头元素是 :%d\n",x);
printf("依次出栈数据元素顺序是:\n");
while(QueueNotEmpty(myQueue))
{
QueueDelete(&myQueue,&x);
printf("%d ",x);
}
}

4．#include "stdio.h"
#include "string.h"
#include "stdlib.h"

#define MaxQueueSize 100

typedef int DataType;

typedef struct
{
DataType queue[MaxQueueSize];
int rear ;
int front;
int count;
} SeqCQueue ;

void QueueuInitiate(SeqCQueue *Q)
{
Q->rear=0;
Q->front=0;
Q->count=0;
}

int QueueNotEmpty(SeqCQueue Q)
{
if(Q.front!=Q.rear)
return 1;
else
return 0;
}
int QueueAppend(SeqCQueue *Q,DataType x)
{
if(Q->front==(Q->rear+1)%MaxQueueSize)
{
printf("队列已满无法插入！\n");
return 0;
}
else
{
Q->queue[Q->rear]=x;
Q->rear=(Q->rear+1)%MaxQueueSize;
Q->count++;
return 1;
}
}

int QueueDelete(SeqCQueue *Q,DataType *d)
{
if(Q->front==Q->rear)
{
printf("队列已空无数据元素出队列!\n");
return 0;
}
else
{
*d=Q->queue[Q->front];
Q->front=(Q->front+1)%MaxQueueSize;
Q->count--;
return 1;
}
}
int QueueGet(SeqCQueue Q,DataType *d)
{
if(Q.front==Q.rear)
{
printf("队列已空无数据可取\n");
return 0;
}
else
{
*d=Q.queue[Q.front];
return 1;
}
}
void main(void)
{
SeqCQueue myQueue;
int i,x;
QueueuInitiate(&myQueue);
for(i=0;i<5;i++)
{
if(QueueAppend(&myQueue,i+1)==0)
{
printf("error!\n");
return;
}
}
if(QueueGet(myQueue,&x)==0)
{
printf("error!\n");
return;
}
else
printf("队头元素是 :%d\n",x);
printf("依次出栈数据元素顺序是:\n");
while(QueueNotEmpty(myQueue))
{
QueueDelete(&myQueue,&x);
printf("%d ",x);
}
}

四、指导老师评语

指导老师签名：