《第三次数据结构上机实验报告》由会员分享，可在线阅读，更多相关《第三次数据结构上机实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、南 京 航 空 航 天 大 学第 1 页 （共 8 页）数据结构上机实验报告年第 学期 第 次上机 上机日期： 年 月 日班号 学号 姓名 一、调试成功程序及说明1、题目： 1编程实现书 P45 ADT Stack 基本操作 9 个，用顺序存储结构实现；算法思想：实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列 abc#de#，则建立如下图所示的二叉树。 abdce 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 源程序：#define MAXQSIZE 100#include#includeusing namespace std;typedef
2、 struct QElemTypeint iterm;QElemType;typedef struct SqQueueQElemType* base;/base 存储 QElemType 类型元素int front;int rear;SqQueue; 第 2 页（共 8 页）typedef int Status;Status InitQueue(SqQueue& Q)/构造一个空队列 QQ.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType);if(!Q.base)exit(-2);Q.front = Q.rear = 0;printf(
3、Been created!n);return 1;Status DestroyQueue(SqQueue& Q)Q.rear = Q.front;free(Q.base);printf(Been destroyed!n);return 1;Status QueueEmpty(SqQueue Q)if(Q.rear = Q.front) return 1;else return 0;int QueueLength(SqQueue Q)/返回 Q 的元素个数，即队列的长度 第 3 页（共 8 页）return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);St
4、atus EnQueue(SqQueue& Q,QElemType e)/插入元素 e 为 Q 的新队尾元素if(Q.rear + 1) % MAXQSIZE = Q.front)return 0;Q.baseQ.rear = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return 1;Status DeQueue(SqQueue& Q,QElemType& e)/若队列不空，则删除 Q 的队头元素，用 e 返回其值/否则返回 ERRORif(Q.front = Q.rear) return 0;e = Q.baseQ.front;Q.front = (Q.fron
5、t + 1) % MAXQSIZE;return 1;int main()SqQueue Q;InitQueue(Q);DestroyQueue(Q);return 0; 第 4 页（共 8 页）运行结果：2、题目：2编程实现书 P59 ADT Queue 基本操作 9 个，用链式存储结构实现；算法思想：在输入二叉树时，并不是随便乱输的，输入的数据必须组成一个二叉树才行。源程序：#include#includeusing namespace std;typedef struct QNodeint data;QNode *next; 第 5 页（共 8 页）QNode,*QueuePtr;typ
6、edef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue& Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(-2);Q.front-next = NULL;return 1;int DestroyQueue(LinkQueue& Q)while(Q.front)Q.rear = Q.front-next;free(Q.front);Q.front = Q.rear;/均指向 NULLreturn 1;int Clea
7、rQueue(LinkQueue& Q)if(Q.rear = Q.front)return 0; 第 6 页（共 8 页）QueuePtr p = Q.front-next;free(p);Q.rear = Q.front;return 1;int QueueLength(LinkQueue Q)int i = 0;QueuePtr p;p = Q.front-next;while(p)i+;p = p-next;return i;int QueueEmpty(LinkQueue Q)if(Q.front = Q.rear)return 1;else return 0;int GetHead
8、(LinkQueue Q,int &e)if(Q.front = Q.rear) 第 7 页（共 8 页）return 0;e = Q.front-next-data;return 1;int EnQueue(LinkQueue& Q,int e)QueuePtr p = (QueuePtr)malloc(sizeof(QNode);if(!p) exit(-2);p-data = e;p-next = NULL;/p 应该指向 null，不能少Q.rear-next = p;Q.rear = p;return 1;int DeQueue(LinkQueue& Q,int& e)if(Q.re
9、ar = Q.front)return 0;QueuePtr p = Q.front - next;e = Q.front -next-data;Q.front-next = p-next;if(Q.rear = p)Q.rear = Q.front;free(p);return 1;int main() 第 8 页（共 8 页）int i;LinkQueue Q;InitQueue(Q);for(i=0;i10;i+)EnQueue(Q,i);if(!QueueEmpty(Q)cout QueueLength(Q) endl;DeQueue(Q,i);cout 被删除的队头元素为： i endl;DestroyQueue(Q);return 0;运行结果：
