数据结构实验报告 学号：xxxxxxxxxxx 知识范畴：线性表 姓名：xxxxxx 专业：计算机科学与技术 完成日期：2019 年 03 月 25 日 实验题目：队列基本操作算法 实验内容及要求： 评分 满分——5 分 编写程序，建立容量为 n(建议 n=8)的循环队列，完成以下程序功能。输入字符#，执行一 次出队操作，屏幕上显示出队字符；输入字符@，队列中所有字符依次出队并按出队次序在屏 幕上显示各字符；输入其它字符，则输入的字符入队。 要求采用队头/队尾间隔至少一个空闲元素的方法来实现循环队列；空队执行出队操作及 队满执行入队操作需显示提示信息。 注意：反复输入字符时，需正确处理好回车键（即输入缓冲区的’\n’字符）的读取问题。 实验目的：掌握循环队列的基本操作算法。 数据结构设计简要描述： 采用一个结构体结点；结构体结点包含整形类型的队列队头指针，队尾指针，最大容量和 一个字符型数组。 算法设计简要描述： 算法实现元素出队操作、入队操作和全部出队操作，出队和入队由队头和队尾指针记录。 输入/输出设计简要描述： 从键盘输入‘@’时队列元素全部出队，输入‘#’时队头元素出队，输入其他字符时该字 符入队，输入“回车”时结束队列操作。 编程语言说明： 使用 Code：：Blocks 编程。主要代码采用 C 语言实现 ；动态存储分配采用 C 语言的 malloc 实现；输入与输出采用 C 语言的 scanf 和 printf 函数实现；程序注释采用 C 规范。 主要函数说明： void initQueue(SqQueue* q,int n); // 初始化一个队列 int full(SqQueue *q); int empty(SqQueue *q); // 判断队列是否为满 // 判断队列是否为空 int popQueue(SqQueue *q, char *ch);// 元素出队操作 int pushQueue(SqQueue *q, char *ch);// 元素入队操作 程序测试简要报告： please input queue capacity:8 please choose operating(@ is pop all queue element, # is pop one queue element, others is push queue,until \n):a push queue success! please choose operating(@ is pop all queue element, # is pop one queue element, others is push queue,until \n):b push queue success! 1 / 4 

please choose operating(@ is pop all queue element, # is pop one queue element, others is push queue,until \n):c push queue success! please choose operating(@ is pop all queue element, # is pop one queue element, others is push queue,until \n):# pop queue element :a please choose operating(@ is pop all queue element, # is pop one queue element, others is push queue,until \n):@ all queue element :b c 源程序代码： // Predefine.h #include #include #include typedef struct{ char *elem; int n;// 队列容量 int f;// 队头指针 int r;//队尾指针 }SqQueue; // main.c #include #include #include "Predefine.h" extern void initQueue(SqQueue* q,int n); extern int full(SqQueue *q); extern int empty(SqQueue *q); extern int popQueue(SqQueue *q, char *ch); 2 / 4 

extern int pushQueue(SqQueue *q, char *ch); int main() { int n; char c1,c; SqQueue q; printf("please input queue capacity:"); scanf("%d",&n); // 输入队列最大容量 getchar(); initQueue(&q,n); while(n) { printf("please choose operating(@ is pop all queue element," " # is pop one queue element, others is push queue,until \\n):"); scanf("%c",&c1); getchar(); switch(c1) { case '#':if(popQueue(&q,&c)) // 输入‘#’的时候出队一次 {printf("pop queue element :");printf("%c\n",c);} else {printf("pop queue failed!\n");} break; case '@':if(!empty(&q))printf("all queue element :"); // 输入‘@’的时候全部元素出队 else {printf("pop queue failed!\n"); break;} while(popQueue(&q,&c)){printf("%c\t",c);} printf("\n"); break; case '\n':n=0;printf("exit operation !\n");break; // 输入回车操作结束 default: if(pushQueue(&q,&c1)) // 输入其他字符将该字符入队 {printf("push queue success!\n");} else {printf("push queue failed!\n");} break; } if(c1!='@' && c1!='#' && full(&q)==1) // 如果队列已满且不是出队操作的时候提示选择出队 printf("the queue is full!\n"); printf("you can choose pop one queue or pop all queue element!\n"); { } } return 0; } // Initalaze.c #include "Predefine.h" // 初始化队列 void initQueue(SqQueue *queue, int n){ queue->n = n; queue->r = queue->f = -1; // 队头。队尾同时指向同一个数据单元 queue->elem = (char *)malloc(sizeof(char)*n); } 3 / 4 

// CheckEmpty.c #include "Predefine.h" // 判断队列是否为空，为空返回 1 int empty(SqQueue *q) { return q->f==q->r; // 如果队满，返回 1，否则返回 0 } // CheckFull.c #include "Predefine.h" // 判断队列是否为空，为空返回 1 int empty(SqQueue *q) { return q->f==q->r; // 如果队满，返回 1，否则返回 0 } // PopQueue.c // 元素出队，出队成功返回 1，否则返回 0 #include "Predefine.h" extern int empty(SqQueue *q); int popQueue(SqQueue *q, char *ch) { if(empty(q)) return 0;// ¶Ó¿Õ£¬³ö¶Óʧ°Ü q->f = (q->f+1)%q->n; *ch = q->elem[q->f]; return 1; } // PushQueue.c #include "Predefine.h" extern int full(SqQueue *q); // 元素入队，入队成功返回 1，失败返回 0 int pushQueue(SqQueue *q, char *ch) { if(full(q)) return 0; // 队满，入队失败 q->r = (q->r+1)%q->n; q->elem[q->r] = *ch; return 1;// 入队成功，返回 1 } 4 / 4