数据结构实验报告(霍夫曼树,二叉排序树,车库问题)

数据结构实验报告实验一线性表操作与停车场管理方案设计一、需求分析1.输入的形式和输入值的范围本程序中，需输入的车库中车的总数n与出库车序m为正整数，由键盘输入，以回车结束2.输出的形式通过屏幕输出每辆车的调度结果，包括车辆出库及入库后库内库外车辆序列3.程序所能达到的功能用户从键盘输入需要的数据，从屏幕输出结果4.测试数据请输入车库中车辆的总数:10请输入出库车辆数量:3请输入第1辆出库的车辆序号:6请输入第2辆出库的车辆序号:7请输入第3辆出库的车辆序号:3车库的初始情况为:12345678910第6辆车可以开出停车场时车辆的情况为:车库中:123456待入库:10987第6辆车开出后停车场车辆的情况为:车库中:1234510987第7辆车可以开出停车场时车辆的情况为:车库中:1234510987待入库:第7辆车开出后停车场车辆的情况为:车库中:123451098第3辆车可以开出停车场时车辆的情况为:车库中:123待入库:891054第3辆车开出后停车场车辆的情况为:车库中:12891054二、概要设计以栈和队列结构实现该实验1.抽象数据类型定义ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…,n}约定其中ai端为队列头，an端为队列尾基本操作：InitQueue(&Q)操作结果：构造一个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue(&Q)初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty(Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEQueueLength(Q)初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列长度GetHead(Q,&e)初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新队尾元素DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值QueueTraverse(Q,visit())初始条件：Q已存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTQueueADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D，i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(s)初始条件:栈S已存在。操作结果：返回S的元素个数，既栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。}ADTStack2.主程序流程voidmain(){初始化；输入数据；执行功能；显示结果；}3.各程序模块间调用关系主程序↓各功能模块三、详细设计#includestdio.h#includestdlib.h//定义栈及操作typedefintStatus;typedefcharSElemType;#defineSTACK_INIT_SIZE100;//栈存储空间的初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//存储数据元素的数组SElemType*top;//栈顶指针intstacksize;//当前分配的栈空间大小}SqStack;StatusInitStack(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(sizeof(SElemType));if(!S.base)exit(-2);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}//InitStackStatusPush(SqStack&S,inte){//插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base,sizeof(SElemType));if(!S.base)exit(-2);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return1;}//PushStatusPop(SqStack&S,int&e){//若栈不空，则删除S的栈顶元素并用e返回其值if(S.top==S.base)return0;e=*--S.top;return1;}//Pop//定义队列及操作typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;intInitQueue(LinkQueue&Q){//构造空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-2);Q.front-next=NULL;return1;}intEnQueue(LinkQueue&Q,inte){//插入e为Q的队尾元素QueuePtrP=(QueuePtr)malloc(sizeof(QNode));if(!P)exit(-2);P-data=e;P-next=NULL;Q.rear-next=P;Q.rear=P;return1;}intDeQueue(LinkQueue&Q,int&e){//销毁Q的队头元素并用e返回其值if(Q.front==Q.rear)return0;QueuePtrP=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear==P)Q.rear=Q.front;free(P);return1;}//主函数voidmain(){inti,j,a,n,t;intx=0,y=0;intm[10];printf(请输入车库中车辆的总数:\n);scanf(%d,&n);printf(请输入出库车辆数量:\n);scanf(%d,&a);//确定系数SqStackS;InitStack(S);SqStackSS;InitStack(SS);for(i=1;i=n;i++)Push(S,i);//初始化栈for(i=1;i=a;i++){printf(请输入第%d辆出库的车辆序号:\n,i);scanf(%d,&m[i]);}LinkQueueQ;InitQueue(Q);printf(车库的初始情况为:\n);for(i=1;i=n;i++)printf(%d,i);for(i=1;i=a;i++){for(j=1;j=n;j++){Pop(S,t);if(t==m[i])break;else{EnQueue(Q,t);x=x+1;}}for(j=1;j=n-x;j++){Pop(S,t);Push(SS,t);y=y+1;}printf(\n第%d辆车可以开出停车场时车辆的情况为:\n,m[i]);printf(车库中:);for(j=1;j=y;j++){Pop(SS,t);if(j1)printf(%d,t);Push(S,t);}printf(%d,m[i]);printf(\n待入库:);for(j=1;j=x;j++){DeQueue(Q,t);printf(%d,t);Push(S,t);}n=n-1;x=0;y=0;for(j=1;j=n;j++){Pop(S,t);Push(SS,t);}printf(\n第%d辆车开出后停车场车辆的情况为:\n,m[i]);printf(车库中:);{for(j=1;j=n;j++){Pop(SS,t);printf(%d,t);Push(S,t);}}}printf(\n);}四、调试分析程序的编写及调试基本正常，开始时由于细节问题导致出库序列混乱，回库时多了一辆标号为一，经调试后确认是循环语句判断出错导致，及时排除五、用户使用说明根据提示输入所需所需模拟的车辆情况即可示例：请输入车库中车辆的总数:10请输入出库车辆数量:3请输入第1辆出库的车辆序号:6请输入第2辆出库的车辆序号:7请输入第3辆出库的车辆序号:3六、测试结果操作及输出流程详见如下截图实验二树的基本操作及基于霍夫曼树的编码/译码一、需求分析1.输入的形式和输入值的范围本程序中，需输入的原始文本为字符变量，由键盘按提示依次输入，以回车结束2.输出的形式从屏幕输出各字符的霍夫曼编码、文本的编译结果等3.程序所能达到的功能用户由键盘输入一段文本，由屏幕输出进行霍夫曼编码的结果4.测试数据输入：aabbbcdddd输出：各字符编码如下:a000b01c001d1文本编码结果如下:0000000101010011111解码结果如下:aabbbcdddd各叶子结点及其频数统计如下:a2b3c1d4二、概要设计以霍夫曼树实现该程序1.抽象数据类型的定义ADTHuffmanTree{数据对象D：D时具有相同特性的数据元素的集合,每个元素都有相应的权值。数据关系R：若D,则R=,称HuffmanTree为空二叉树；若D,则R={H},H是如下二元关系：在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；若D-{root},则存在D-{root}={},且=；若,则中存在唯一的元素,root,H,且存在上的关系H;若,则中存在唯一的元素,root,H,且存在上的关系H;H={root,,root,,};且有每一个非叶子节点的权值为其左右孩子的权值之和,且其左孩子的权值大于或等于右孩子的权值;(,{})是一颗符合本定义的二叉树，称为根的左子树,()是一颗符合本定义的二叉树，称为根的右子树。基本操作：InitHufTree(&T)操作结果：构造一个空Huffman树T。DestroyHufTree(&T)初始条件：Huffman树T已经存在。操作结果：销毁Huffman树T。CreatHufTree(&T,n)初始条件：Huffman树T已经存在。操作结果：建立一个具有n个节点的Huffman树。HuffmanCoding(&T,n)初始条件：具有n个节点的Huffman树T已经建立。操作结果：返回储存每个字符的HuffmanCodehc。HuffmanEncode(hc,intn)初始条件：具有n个节点的Huffman树T已经建立,且每个字符的HuffmanCode已得到。操作结果：返回对输入文本编码的结果a。HuffmanDecoding(T,a,n)初始条件：具有n个节点的Huffman树T已经建立,且输入文本已被编码为a。操作结果：输出原文本。}ADTHuffmanTree2.