实验报告实验报告 学生姓名： 黄家明 学号：6103115017 专业班级： 计科 151 班 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 2017.4.26 实验成绩： 一、实验目的一、实验目的 （1）掌握链接存储队列的进队和出队等基本操作 （2）掌握环行队列的进队和出队等基本操作 （3）加深对队列结构的理解，逐步培养解决实际问题的编程能力 二、问题描述二、问题描述 掌握链队以及循环队列 三三、实验要求、实验要求 (1)编写链接队列的基本操作函数 typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; ①进队操作 EnQueue(LinkQueue //初始化的动态分配存储空间 int front; //头指针，若队列不为空，指向队列头元素 int rear; //为指针，若队列不为空，指向队列尾元素的下一个位置 }SqQueue; ①进队操作，返回 1 为队满 EnQueue(SqQueue #define OVERFLOW -1 using namespace std; typedef struct QNode { int data; struct QNode *next; }QNode, *QueuePtr; typedef struct LinkQueue { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; int InitQueue(LinkQueue if (!Q.front) exit(OVERFLOW); Q.front -> next = NULL; return OK; } int EnQueue(LinkQueue if (!p) exit(OVERFLOW); p -> data = e; p -> next = NULL; Q.rear -> next = p; Q.rear = p; return OK; } int DeQueue(LinkQueue QNode *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 GetTop(LinkQueue Q) { return Q.front -> next -> data; } void OutputQueue(LinkQueue Q) { QueuePtr p; p = Q.front -> next; while (p) { cout data next; } } void printOp() { printf(“===========================================\n“); printf(“ 队列操作 \n“); printf(“===========================================\n“); printf(“ 1: 初始化链队\n“); printf(“ 2: 取队头元素\n“); printf(“ 3: 入队\n“); printf(“ 4: 出队\n“); printf(“ 5: 输出队列元素\n“); printf(“ 6: 退出程序\n“); printf(“===========================================\n“); printf(“ 选择需要进行的操作 \n“); } int main() { int e, n, op = 1; LinkQueue Q; printOp(); while (op) { scanf(“%d“, switch(op) { case 1: // 初始化一个链队 InitQueue(Q); printf(“请输入初始化数据，使用空格分开, 0 表示结束: “); while(scanf(“%d“, printf(“队列元素为：“); OutputQueue(Q); printf(“\n“); break; case 2: printf(“队头元素为：%d\n“, GetTop(Q)); printf(“队列元素为：“); OutputQueue(Q); printf(“\n“); break; case 3: printf(“请输入插入的元素：“); scanf(“%d“, EnQueue(Q, e); printf(“队列元素为：“); OutputQueue(Q); printf(“\n“); break; case 4: DeQueue(Q, e); printf(“出队元素为：%d\n“, e); printf(“队列元素为：“); OutputQueue(Q); printf(“\n“); break; case 5: printf(“队列元素为：“); OutputQueue(Q); printf(“\n“); break; case 6: op = 0; break; default: printf(“请输入正确的编号！\n“); break; } } return 0; } 实验结果：实验结果： 实验结果如下图所示： //循环队列的实现循环队列的实现 关键函数设计关键函数设计 定义循环定义循环队列数据结构队列数据结构 typedef struct { int *base; int front; // 定义头指针 int rear; // 定义尾指针 }SqQueue; //初始化队列 int InitQueue(SqQueue if (!Q.base) exit(OVERFLOW); // 内存分配失败 Q.front = Q.rear = 0; return OK; } //入队 int EnQueue(SqQueue Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXSIZE; return OK; } //出队 int DeQueue(SqQueue e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXSIZE; return OK; //获取对头元素 int GetTop(SqQueue Q) { if (Q.front == Q.rear) return ERROR; return Q.base[Q.front]; } //输出队列 void OutputQueue(SqQueue Q) { int s = Q.front; while (s != Q.rear) { printf(“%d “, Q.base[s]); s = (s + 1) % MAXSIZE; } } 实验结果如下图所示： 七七、、思考感悟思考感悟 这次的实验，除了复习巩固了队列的知识，还写了一个用户界 面，使得程序看起来更加友好。
程序的执行结果一目了然，看着 挺方便的，编写起来也不难 还体会到了循环队列的巧妙，为充分利用向量空间，克服“假 溢出“，将向量空间想象为一个首尾相接的圆环，并称这种向量为 循环向量，存储在其中的队列称为循环队列（来自网上资料） 但 是跟链队相比， 在我的代码实现中， 其长度不可变， 这是个遗憾 但仔细想想，其实循环队列应该也能改变长度，只是没有链队方 便。