数据结构队列实验报告

数据结构实验

实验内容和目的：

掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。

实验教材：

数据结构题集（C语言版） 清华大学出版社 2007年

实验项目：

实验一、栈和循环队列

㈠、实验内容：

① 栈

掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

② 循环队列

掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码

① 栈

程序代码：

#include

#include

#define Stack_Size 6

#define ERROR 0

#define OK 1

typedef int SElemType;

typedef struct SNode

{

SElemType data;

struct SNode *next; }SNode,*LinkStack;

int CreatTwo(LinkStack &head,int n)

{

int i;

SNode *p;

head=(LinkStack)malloc(sizeof(SNode));

head->next=NULL;

printf("请输入数据(数字):\n");

for(i=n;i>0;--i)

{

p=(SNode *)malloc(sizeof(SNode));

scanf("%d",&p->data);

p->next=head->next;

* *

计算机科学与技术系

实 验 报 告

专业名称 计算机科学与技术

课程名称 数据结构与算法

项目名称 实验三队列实验

班 级

学 号 1

姓 名

同组人员 无

实验日期

* *

实验三 队列实验

实验题目：建立含有若干个元素的循环队列和链队列，并分别实现循环队列和链队列的入队和出对操作。

（1）先实现循环队列的入队和出队操作

1.问题分析

本程序要求实现建立含有若干个元素的循环队列，并实现循环队列的入队和出队操作。

完成该实验需要以下4个子任务：

○1定义一个循环队列的存储结构，定义队列的基本算法。

○2定义一个display（）函数实现队列元素的输出看入队是否成功

○3通过队列的基本算法实现队列的出队操作

○4在主函数中完成操作

测试数据设计如下：

1 2 3 4 5

6

2.概要设计

为了实现上述程序功能，需要：○1声明一个循环队列○2定义出队列的基本算法，○3通过键盘输入5个整数，入队，出队 ○4在主函数中先往队列里输入5个元素，然后入队，输出，看入队是否成功，然后出队，再调用display（）函数* *

看是否出队。

1） 本程序包含7个函数：

1主函数main()

2.置空队：InitQueue()

3.判对空: QueueEmpty()

4.判队满：QueueFull()

5.入队:Add()

6.出队:Delete()

7.display()

各函数关系如下：

InitQueue()

QueueEmpty()

Main () QueueFull()

/* SinearTabSe On Sequence Structure */

#include

#include

#include

/*---------page 10 on textbook ---------*/

#define TRUE 1

#define FAlSE 0

#define OK 1

#define ERROR 0

#define INFEASTABLE -1

#define OVERFLOW -2

typedefint status;

typedefintQElemType; //数据元素类型定义

/*-------page 22 on textbook -------*/

#define MAXQSIZE 100

typedefstruct { //顺序表（顺序结构）的定义

QElemType *base; //初始化的动态分配存储空间

int front; //头指针，若队列不为空，指向队列头元素

int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置

} SqQueue;

/* -----page 19 on text book -----*/

status InitQueue( SqQueue&Q );

status DestroyQueue( SqQueue&Q );

status ClearQueue( SqQueue&Q );

status QueueEmpty( SqQueue Q);

intQueuelength( SqQueue Q );

status GetHead( SqQueue Q, QElemType&e );

status EnQueue( SqQueue&Q, QElemType e );

status DeQueue( SqQueue&Q, QElemType&e );

status QueueTraverse( SqQueue Q );

实验报告（3）

实验名称 栈、队列实验

同组人姓名 ＸＸ 实验性质 □ 基本操作 □验证性

■ 综合性 □设计性

实验日期 2011.04.20 实验成绩

教师评价：

实验预习□ 实验操作□ 实验结果□ 实验报告□ 其它□

教师签名：

1.目的要求：

1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

2） 本实验训练的要点是“栈”和“队列”的观点；

2.实验内容：

1） 利用栈，实现任一个表达式中的语法检查（如括号的匹配）。

2） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；

三、主要设备及软件

PC机1台, VC 6.0 平台 四、实验流程、操作步骤或核心代码、算法片段

括号匹配

Status InitStack(SqStack &S)

{S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base) exit(OVERFLOW);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status POp(SqStack &S,SElemType &e)

{if(S.top==S.base) return ERROR;

e=*--S.top;

return OK;

}

Status Push(SqStack &S,SElemType e)

{if(S.top-S.base>=S.stacksize)

{S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));

if(!S.base) exit(OVERFLOW);

S.top=S.base+S.stacksize;