实验三 栈和队列

《数据结构》课程实验 实验报告三

第三章 栈和队列的操作

实验题目: 实验三 栈和队列的操作 学号: 11416106 班级:计算机111 姓名: 张婷 指导教师: 游 静 实验完成时间: 2013.4.22 实验成绩:

实验三 栈和队列的操作

一、实验学时 2学时 二、背景知识

1.栈:

(1).入栈和进栈操作只能从栈顶一端进行; (2).LIFO(后进先出);

(3).栈的两种存储定义:顺序栈和链式栈。 2.队列:

(1).入队操作从队尾进行,出队操作从对头进行; (2).FIFO(先进先出);

(3).队列的两种存储定义:顺序队和链队。

三、目的要求

1. 掌握栈的顺序表示和实现。

Typedef struct{ SelemType *base; SelemType *base; Int stacksize; }sqstack;

2. 掌握队列的链式表示和实现以及顺序表示和实现。

链队列:

Typedef struct Qnode{ QelemType data; struct Qnode *next; } Qnode,*Queueptr; Typedef struct{ Queueptr front; Queueptr rear; }linkQueue; 顺序队列:

#define MAXQSIZE 100 Typedef struct{ Qelemtype *base; int front; int rear; }sqQueue;

四、实验内容

1. 顺序栈和循环队列的创建、入栈(队)、出栈(队)等基本操作。 2. 数制转换问题 【问题描述】

十进制数N和其它d进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求:对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数。 【基本要求】

首先初始化一个顺序栈,通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例:顺序队列的入队和出队操作。

【问题描述】

使有数组创建队列。程序使有选项运行队列的操作,如:输入1表示元素入队,输入2表示元素出队,输入3表示结束程序运行,并且将队列剩余元素输出。 【基本要求】

首先使有数组创建队列,然后编写入队函数和出队函数,最后编写主函数。 【测试数据】

如:输入队列的元素是:[2][3][4][5][6]

取出队列的元素是:[2]

剩余队列的元素是:[3][4][5][6]

【实现提示】

#define MAXQUEUE 10 /* 队列的最大容量 */

int queue[MAXQUEUE]; /* 队列的数组定义 */ int front = -1; /* 队头 */ int rear = -1; /* 队尾 */ /*―――――――――――入队―――――――――――*/ int enqueue(int value) {

if ( rear >= MAXQUEUE ) /* 检查队列是否全满 */ return -1; /* 无法存入 */ rear++; /* 队尾指针前移 */ queue[rear] = value; /* 存入队列 */ }

/*―――――――――――出队―――――――――――*/ int dequeue() {

if ( front == rear ) /* 检查队列是否为空 */ return -1; /* 无法取出 */ front++; /* 队头指针前移 */ return queue[front]; /* 队列取出 */ }

六、实验结果 1、第一题 顺序栈实现 #include

#define ElementType char #define maxsize 40 typedef struct {

ElementType data[maxsize]; int top;

} SqStackTp;

int InitStack(SqStackTp *sq) {

sq->top=0;

return(1); }

int Push(SqStackTp *sq,DataType x) {

if(sq->top== maxsize-1) {

printf(\栈满\}

else{

sq->top++;

sq->data[sq->top]=x; return(1); } }

int Pop(SqStackTp *sq,DataType *x){ if (sq->top==0) {

printf(\下溢\}

else {

*x=sq->data[sq->top]; sq->top--; return(1);} }

int EmptyStack(SqStackTp *sq){ if (sq->top==0) return(1); else return(0); }

/*主函数*/ void main(){ SqStackTp sq; ElementType ch; InitStack(&sq);

for (ch='A';ch<='A'+12;ch++){ Push(&sq,ch); printf(\}

printf(\

while(!EmptyStack(&sq)) {

Pop(&sq,&ch);printf(\}

printf(\

队列的实现

#include #include

#define MAX 5 /* 队列的最大容量 */

/*―――――――――――队列定义―――――――――――*/ Struct queue{ int *base; int front; int rear; };

Typedef struct queue Queue;

/*―――――――――――建队―――――――――――*/ queue* initqueue(Queue *q){

q->base-new int [MAX];

if(!Q->base){

cout<<”建队失败,内存申请不成功”<

q->front=q->rear=0; return q; }

/*―――――――――――入队―――――――――――*/ int enqueue(Queue *q,int value){

q->base[q->rear]=value;

if((q->rear+1)%MAX==q->front){ cout<<”队已满”; return -1; }

q->rear=(q->rear+1)%MAX; return value; }

/*―――――――――――出队―――――――――――*/ int dequeue(Queue *q){

if ( q->front ==q-> rear ) { /* 检查队列是否为空 */ cout<<”队已空”<

} /* 无法取出 */ int x;

x=q->base[(q->front)%=MAX];

q->front++; /* 队头指针前移 */ return x; /* 队列取出 */ }

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4