第三次数据结构上机实验报告.doc

一、调试成功程序及说明 1、 题目： 1．编程实现书P45 ADT Stack 基本操作9个，用顺序存储结构实现； 算法思想：实现二叉树的建立，并实现先序、中序和后序遍历。? 如：输入先序序列abc###de###，则建立如下图所示的二叉树。? abdce? 并显示其先序序列为：abcde?中序序列为：cbaed?后序序列为：cbeda? 源程序：#define MAXQSIZE 100 #includestdlib.h #includeiostream using namespace std; typedef struct QElemType{ int iterm; }QElemType; typedef struct SqQueue{ QElemType* base;//base存储QElemType类型元素 int front; int rear; }SqQueue; typedef int Status; Status InitQueue(SqQueue Q){ //构造一个空队列Q Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType)); if(!Q.base)exit(-2); Q.front = Q.rear = 0; printf(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的元素个数，即队列的长度 return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); } Status EnQueue(SqQueue Q,QElemType e){ //插入元素e为Q的新队尾元素 if((Q.rear + 1) % MAXQSIZE == Q.front)return 0; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return 1; } Status DeQueue(SqQueue Q,QElemType e){ //若队列不空，则删除Q的队头元素，用e返回其值 //否则返回ERROR if(Q.front == Q.rear) return 0; e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return 1; } int main() { SqQueue Q; InitQueue(Q); DestroyQueue(Q); return 0; } 运行结果： 2、 题目：2．编程实现书P59 ADT Queue 基本操作9个，用链式存储结构实现； 算法思想：在输入二叉树时，并不是随便乱输的，输入的数据必须组成一个二叉树才行。 源程序：#includestdio.h #includeiostream using namespace std; typedef struct QNode{ int data; QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr 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;//均指向NULL } return 1; } int ClearQueue(LinkQueue Q){ if(Q.rear == Q.front) return 0; QueuePtr p = Q.front-next; free(p); Q.rear = Q.front; return