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

第8页（共8页）一、调试成功程序及说明1、题目： 1编程实现书P45 ADT Stack 基本操作9个，用顺序存储结构实现；算法思想：实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc#de#，则建立如下图所示的二叉树。abdce并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda源程序：#define MAXQSIZE 100#include#includeusing namespace std;typedef struct QElemTypeint iterm;QElemType;typedef struct SqQueueQElemType* base;/base存储QElemType类型元素int front;int rear;SqQueue;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(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.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.front + 1) % MAXQSIZE;return 1;int main()SqQueue Q;InitQueue(Q);DestroyQueue(Q);return 0;运行结果：2、题目：2编程实现书P59 ADT Queue 基本操作9个，用链式存储结构实现；算法思想：在输入二叉树时，并不是随便乱输的，输入的数据必须组成一个二叉树才行。源程序：#include#includeusing namespace std;typedef struct QNodeint data;QNode *next;QNode,*QueuePtr;typedef 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 ClearQueue(LinkQueue& Q)if(Q.rear = Q.front)return 0;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(LinkQueue Q,int &e)if(Q.front = Q.rear)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.rear = 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()int i;LinkQueue Q;InitQueue(Q);for(i=0;i