数据结构实验5 (1)

《数据结构》实验报告

实验序号：5 实验项目名称：队列的操作 学 号 实验地点 姓 名 指导教师 专业、班 实验时间 一、实验目的及要求 1. 熟悉队列的基本概念； 2. 掌握队列的链式表存储结构； 3．掌握队列的应用。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 1.C++的库函数中已经实现了队列，引用方法为#include ，请上网查阅资料，完成习题。 ①创建一个队列。 ②将a、b、c、d、e、f依次入队。 ③若队列不为空，将元素出队并打印输出。 2.以下的链式队列采用队头指针和队尾指针分别跟踪队列的头尾两端，请删除队尾指针，只使用队头指针实现队列的初始化、入队、出队和销毁队列。 #include #include #define ERROR 1 #define OK 0 #define OVERFLOW 1 typedef int QElemType; typedef int Status;

typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 }LinkQueue; Status InitQueue (LinkQueue &Q) { // 构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW);//存储分配失败 Q.front->next = NULL; return OK; } Status DestroyQueue (LinkQueue &Q) { // 销毁队列Q while (Q.front) { Q.rear = Q.front->next; free (Q.front) ; Q.front = Q.rear; } return OK; } Status EnQueue (LinkQueue &Q,QElemType e) { // 插入元素e为Q的新的队尾元素 QueuePtr p; p = (QueuePtr) malloc (sizeof (QNode)); if(!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } Status DeQueue (LinkQueue &Q,QElemType &e) { // 若队列不空，则删除Q的队头元素，

//用 e 返回其值，并返回OK；否则返回ERROR QueuePtr p; if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; } int main() { int i,n=10; QElemType e; LinkQueue Q; InitQueue(Q); //初始化队列 printf(\"元素入队\"); for(i=0;i #include #define ERROR 1 #define OK 0

#define OVERFLOW 1 typedef int QElemType; typedef int Status; #define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空， //指向队列尾元素 的下一个位置 }SqQueue; Status InitQueue (SqQueue &Q) { // 构造一个空队列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType)); if (!Q.base) exit (OVERFLOW); //存储分配失败 Q.front = Q.rear = 0; return OK; } Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } void main() { int i; QElemType j = 0; SqQueue S; InitQueue(S); //初始化队列

} printf(\"元素入队列\"); for(i=0 ; i<10; i++) { printf(\" %d \ EnQueue(S,j); //元素入队列 j++; } printf(\"\\n元素出队列\"); for(i=0 ; i<10; i++) { DeQueue(S,j); //元素出队列 printf(\" %d \} 以下题目为选做题： 4. 参考P61-62的代码用链式表实现队列，并在主函数中测试。 四、实验结果与数据处理 详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果（贴图）。 五、分析与讨论 对上机实践结果进行分析，上机的心得体会。 六、教师评语 签名： 日期： 附源程序清单：1 1

成绩

#include #include #include using namespace std; int main(){ queue q; int i;

char f[5],m; for(i=0;i<5;i++) { scanf(\"%c\ q.push(f[i]); } for(i=0;i<5;i++) { printf(\"%c \ q.pop(); } return 0; } 2

#include #include

#define ERROR 1 #define OK 0

#define OVERFLOW 1

typedef int QElemType; typedef int Status;

typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; }QNode,*QueuePtr;

typedef struct { // 链队列类型

QueuePtr front; // 队头指针 }LinkQueue;

Status InitQueue (LinkQueue &Q) { // 构造一个空队列Q

Q.front=(QueuePtr)malloc(sizeof(QNode)); if (!Q.front)

exit (OVERFLOW);//存储分配失败 Q.front->next = NULL; return OK; }

Status DestroyQueue (LinkQueue &Q) { // 销毁队列Q Q.front=NULL; return OK; }

Status EnQueue (LinkQueue &Q,QElemType e) {

// 如果是第一次进入队列，让队头指针跟他相等，之后每次入队在节点下一个为空前停住，让当前不为空节点等于新的产生的存储节点，完成入队 //这个是循环次数结果入队，所以少一个传进函数的形式参量（记录入队次数的） QueuePtr p,q; p = (QueuePtr) malloc (sizeof (QNode)); p->data = e;

p->next = NULL; if(e==0) { Q.front->next=p; } else { q=Q.front->next; while(q) { if(q->next==NULL) break; q=q->next; } q->next=p; }

if(!p) exit (OVERFLOW); //存储分配失败 return OK; }

Status DeQueue (LinkQueue &Q,QElemType &e) {

// 若队列不空，则删除Q的队头元素（删除队尾就两说了） //用 e 返回其值，并返回OK；否则返回ERROR QueuePtr p;

if (Q.front->next==NULL)//当队头不为空，队列合法 return ERROR; p=Q.front->next; e = p->data;

Q.front->next = p->next; free (p); return OK; }

int main() { int i,n=10; QElemType e; LinkQueue Q; InitQueue(Q); //初始化队列 printf(\"元素入队\"); for(i=0;i}//destory删除队列函数有问题从写 3

#include #include

#define ERROR 1 #define OK 0

#define OVERFLOW 1

typedef int QElemType; typedef int Status;

#define MAXQSIZE 100 //最大队列长度 typedef struct {

QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空， //指向队列尾元素 的下一个位置 }SqQueue;

Status InitQueue (SqQueue &Q) { // 构造一个空队列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType)); if (!Q.base) exit (OVERFLOW); //存储分配失败

Q.front = Q.rear = 0; return OK; }

Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e;

Q.rear = (Q.rear+1) % MAXQSIZE; return OK; }

Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front];

Q.front = (Q.front+1) % MAXQSIZE; return OK; }

int QueueLength(SqQueue &Q){ return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;//追踪空间书 }

void main() { int i,a; QElemType j = 0; SqQueue S; InitQueue(S); //初始化队列 printf(\"元素入队列\"); for(i=0 ; i<10; i++) { printf(\"%d \ EnQueue(S,j); //元素入队列 j++;

printf(\"空间:\"); a=QueueLength(S); printf(\"%d \ } printf(\"\\n元素出队列\"); for(i=0 ; i<10; i++) { DeQueue(S,j); //元素出队列 printf(\"%d \ printf(\"空间:\"); a=QueueLength(S); printf(\"%d \ } } 4

#include #include

#define ERROR 1 #define OK 0

#define MAXSIZE 100

typedef int QElemType; typedef int Status;

typedef struct QNode{ Status data; struct QNode *next; }*Queueptr; typedef struct{ Queueptr front; Queueptr rear ; Status *base; }Squeue;

Status Initqueue(Squeue &Q){ Q.front=Q.rear=(Queueptr)malloc(sizeof(QElemType)); if(!Q.front) exit(ERROR); Q.front->next=NULL; return OK; }

Status Enqueue(Squeue &Q,int e) {

Queueptr p; p=(Queueptr)malloc(sizeof(QNode)); if(!p) exit(ERROR); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

Status destoryQ(Squeue &Q) { Queueptr p; while(Q.front) { p=Q.front->next; Q.front->next=Q.front->next->next; free(p); } return OK; }

Status deQueue(Squeue &Q,QElemType &e) { Queueptr p; p=Q.front->next; e=p->data; Q.front->next=p->next; free(p); return OK; }

int main() { int i,j,k,o; Squeue Q; Initqueue(Q); scanf(\"%d\ for(j=0;j}

deQueue(Q,o); printf(\"%d \}

destoryQ(Q); return 1;