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

1、数据结构实验报告实验一 线性表操作与停车场管理方案设计一、 需求分析1. 输入的形式和输入值的范围本程序中，需输入的车库中车的总数n与出库车序m为正整数，由键盘输入，以回车结束2. 输出的形式通过屏幕输出每辆车的调度结果，包括车辆出库及入库后库内库外车辆序列3. 程序所能达到的功能用户从键盘输入需要的数据，从屏幕输出结果4. 测试数据请输入车库中车辆的总数:10请输入出库车辆数量:3请输入第1辆出库的车辆序号:6请输入第2辆出库的车辆序号:7请输入第3辆出库的车辆序号:3车库的初始情况为:1 2 3 4 5 6 7 8 9 10第6辆车可以开出停车场时车辆的情况为:车库中: 1 2 3 4 5

2、 6待入库: 10 9 8 7第6辆车开出后停车场车辆的情况为:车库中: 1 2 3 4 5 10 9 8 7第7辆车可以开出停车场时车辆的情况为:车库中: 1 2 3 4 5 10 9 8 7待入库:第7辆车开出后停车场车辆的情况为:车库中: 1 2 3 4 5 10 9 8第3辆车可以开出停车场时车辆的情况为:车库中: 1 2 3待入库: 8 9 10 5 4第3辆车开出后停车场车辆的情况为:车库中: 1 2 8 9 10 5 4二、 概要设计以栈和队列结构实现该实验1. 抽象数据类型定义ADT Queue 数据对象：D = ai | aiElemSet , i = 1,2,n,n0 数据

3、关系：R1= | ai-1 , aiD, i=2,n 约定其中ai端为队列头，an端为队列尾基本操作： InitQueue ( &Q ) 操作结果：构造一个空队列Q DestroyQueue ( &Q ) 初始条件：队列Q已存在 操作结果：队列Q被销毁，不再存在 ClearQueue ( &Q ) 初始条件：队列Q已存在 操作结果：将Q清为空队列 QueueEmpty ( Q ) 初始条件：队列Q已存在 操作结果：若Q为空队列，则返回TRUE，否则FALSE QueueLength ( Q ) 初始条件：队列Q已存在 操作结果：返回Q的元素个数，即队列长度 GetHead ( Q , &e )

4、 初始条件：Q为非空队列 操作结果：用e返回Q的队头元素 EnQueue ( &Q , e ) 初始条件：队列Q已存在 操作结果：插入元素e为Q的新队尾元素 DeQueue ( &Q , &e ) 初始条件：Q为非空队列 操作结果：删除Q的队头元素，并用e返回其值 QueueTraverse ( Q , visit( ) ) 初始条件：Q已存在且非空 操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit( )。一旦visit( )失败，则操作失败。ADT QueueADT Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=|ai-1,aiD

5、，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) 初始条

6、件：栈S已存在。操作结果：插入元素e为新的栈顶元素。 Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse(S,visit() 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。ADT Stack2. 主程序流程void main ( )初始化；输入数据；执行功能；显示结果；3. 各程序模块间调用关系主程序 各功能模块三、 详细设计#include #include /定义栈及操作typedef int Status;typedef cha

7、r SElemType;#define STACK_INIT_SIZE 100; / 栈存储空间的初始分配量#define STACKINCREMENT 10; / 存储空间分配增量typedef struct SElemType *base; / 存储数据元素的数组 SElemType *top; / 栈顶指针 int stacksize; / 当前分配的栈空间大小SqStack;Status InitStack (SqStack &S) / 构造一个空栈S S.base=(SElemType*)malloc(sizeof(SElemType); if (!S.base) exit (-2)

8、; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1;/ InitStackStatus Push (SqStack &S, int e) / 插入元素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; re

9、turn 1;/ PushStatus Pop (SqStack &S, int &e)/ 若栈不空，则删除S的栈顶元素并用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/ Pop/定义队列及操作typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;int InitQueue(LinkQueue &Q)/构造空队列QQ.front=Q

10、.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(-2);Q.front-next=NULL;return 1;int EnQueue(LinkQueue &Q,int e)/插入e为Q的队尾元素QueuePtr P=(QueuePtr)malloc(sizeof(QNode);if(!P)exit(-2);P-data=e;P-next=NULL;Q.rear-next=P;Q.rear=P;return 1;int DeQueue(LinkQueue &Q,int &e)/销毁Q的队头元素并用e返回其值if(Q.front=Q.re

11、ar)return 0;QueuePtr P=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear=P)Q.rear=Q.front;free(P);return 1;/主函数void main()int i,j,a,n,t;int x=0,y=0;int m10; printf(请输入车库中车辆的总数:n);scanf(%d,&n);printf(请输入出库车辆数量:n);scanf(%d,&a); /确定系数 SqStack S;InitStack(S);SqStack SS;InitStack(SS); for(i=1;i=n;i+)Pu

12、sh(S,i); /初始化栈for(i=1;i=a;i+) printf(请输入第%d辆出库的车辆序号:n,i); scanf(%d,&mi); LinkQueue Q;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=mi)break;elseEnQueue(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,mi);

13、 printf(车库中: );for(j=1;j1)printf(%d ,t);Push(S,t);printf(%d ,mi);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,mi); printf(车库中: );for(j=1;j=n;j+)Pop(SS,t);printf(%d ,t);Push(S,t);printf(n);四、 调试分析程序的编写及

14、调试基本正常，开始时由于细节问题导致出库序列混乱，回库时多了一辆标号为一，经调试后确认是循环语句判断出错导致，及时排除五、 用户使用说明根据提示输入所需所需模拟的车辆情况即可示例：请输入车库中车辆的总数:10请输入出库车辆数量:3请输入第1辆出库的车辆序号:6请输入第2辆出库的车辆序号:7请输入第3辆出库的车辆序号:3六、 测试结果操作及输出流程详见如下截图实验二 树的基本操作及基于霍夫曼树的编码/译码一、 需求分析1. 输入的形式和输入值的范围本程序中，需输入的原始文本为字符变量，由键盘按提示依次输入，以回车结束2. 输出的形式从屏幕输出各字符的霍夫曼编码、文本的编译结果等3. 程序所能达到

15、的功能用户由键盘输入一段文本，由屏幕输出进行霍夫曼编码的结果4. 测试数据输入：aabbbcdddd输出：各字符编码如下: a 000 b 01 c 001 d 1文本编码结果如下:解码结果如下:aabbbcdddd各叶子结点及其频数统计如下: a 2 b 3 c 1 d 4二、 概要设计以霍夫曼树实现该程序1. 抽象数据类型的定义ADT HuffmanTree数据对象D：D时具有相同特性的数据元素的集合,每个元素都有相应的权值。数据关系R：若D=,则R=,称HuffmanTree为空二叉树；若D,则R=H,H是如下二元关系：在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；若D-

16、root,则存在D-root=Dl,Dr,且DlDr=；若Dl,则Dl中存在唯一的元素xl,H,且存在Dl上的关系HlH;若Dr, 则Dr中存在唯一的元素xr, H,且存在Dr上的关系HrH;H=, ,Hl,Hr;且有每一个非叶子节点的权值为其左右孩子的权值之和,且其左孩子的权值大于或等于右孩子的权值;(Dl, Hl)是一颗符合本定义的二叉树，称为根的左子树,( Dr,Hr)是一颗符合本定义的二叉树，称为根的右子树。基本操作： InitHufTree(&T) 操作结果：构造一个空Huffman树T。 DestroyHufTree(&T) 初始条件：Huffman树T已经存在。 操作结果：销毁H

17、uffman树T。 CreatHufTree(&T,n) 初始条件：Huffman树T已经存在。 操作结果：建立一个具有n个节点的Huffman树。 HuffmanCoding(&T,n) 初始条件：具有n个节点的Huffman树T已经建立。 操作结果：返回储存每个字符的HuffmanCode hc。 HuffmanEncode (hc, int n) 初始条件：具有n个节点的Huffman树T已经建立,且每个字符的Huffman Code已得到。 操作结果：返回对输入文本编码的结果a。 HuffmanDecoding(T, a, n) 初始条件：具有n个节点的Huffman树T已经建立,且输

18、入文本已被编码为a。 操作结果：输出原文本。ADT HuffmanTree2. 主程序流程 void main() 初始化； 输入数据； 执行功能；显示结果；3. 程序模块间调用关系 主程序 各功能模块三、 详细设计#include #include #include typedef struct HfTNode/定义结点int sum; int parent,lchild,rchild;HfTNode,*HuffmanTree;typedef char *HuffmanCode;static int a,b,Sum53;static char Letter53,Text100;/从前i个节点

19、中选择出权值最小的两个分别赋值a,bint Select(HuffmanTree HT,int i) int j=1; HuffmanTree ht=HT; if(i2)return 0; while(!(htj.sum) j+; b=a=j; for(j=1;j(htj.sum) a=j; if(b)!=(a) for(j=1;j(htj.sum)&j!=a) b=j; else j=a+1; while(!(htj.sum) j+; b=j; for(j=1;j(htj.sum) b=j; return 1;/建立具有2n-1个节点的霍夫曼树HuffmanTree CreatHuffman

20、Tree(HuffmanTree HT,int n) int i,m; HuffmanTree ht=HT; if(n=1)return NULL; m=2*n-1; ht=(HuffmanTree)malloc(m+1)*sizeof(HfTNode); for(i=1;i=n;+i) hti.sum=Sumi; hti.parent=hti.lchild=hti.rchild=0; for(i=n+1;i=m;+i) hti.sum=hti.parent=hti.lchild=hti.rchild=0; for(i=n+1;i=m;+i) /构造霍夫曼树 Select(ht,i-1); /

21、选择根结点权值最小的2个二叉树 hta.parent=i; htb.parent=i; hti.lchild=b; hti.rchild=a; (hti.sum)=(hta.sum)+(htb.sum); (hta.sum)=(htb.sum)=0; return ht;/获得字符的霍夫曼码HuffmanCode HuffmanCoding(HuffmanTree HT, int n) int i,start,c; int f; char *cd; HuffmanCode HC; HuffmanTree ht=HT; if(!HT)return NULL; HC=(HuffmanCode)ma

22、lloc(n + 1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i) /求每个字符的霍夫曼编码 start=n-1; for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) if (htf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi, &cdstart); free(cd); return HC;/对输入文本进行霍夫曼编码cha

23、r *HuffmanEncoding(HuffmanCode hc, int n) int i,j=0; char a400; for(i=0;i400;i+)ai=0; while(Textj) for(i=1;i=n;i+) if(Textj=Letteri) strcat(a,hci); break; j+; return a;/对输入文本进行霍夫曼解码void HuffmanDecoding(HuffmanTree HT, char a, int n) int i=0,m,count=0,location; char b100; HuffmanTree ht=HT; m=2*n-1;

24、for(i=0;i100;i+)bi=0; i=0; while(acount!=0) location=m; while(1) if(!(htlocation.lchild)&!(htlocation.rchild)break; if(acount=0)location=htlocation.lchild; else location=htlocation.rchild; count+; bi+=Letterlocation; printf(n解码结果如下:n%s,b);/统计文本频数，存入全局变量Text100,Letter53,Weight53int Stat() char a; int

25、 count=0,i,j=0,flag=0; for(i=1;i=52;i+)Letteri=Sumi=0; while(a=getchar()!=n) Textj+=a; for(i=1;i=count;i+) if(a=Letteri) Sumi+; flag=1; break; if(flag)flag=0;continue; else Lettercount+1=a; Sumcount+1+; count+; Textj=0; return count;void main()/主函数 HuffmanTree ht; HuffmanCode hc; int i,n; char *a,*b

26、; printf(输入原始文本:n); n=Stat(); ht=CreatHuffmanTree(ht,n); hc=HuffmanCoding(ht,n); printf(n各字符编码如下:n); for(i=1;i=n;i+)printf(%3c%5sn,Letteri,hci); a=HuffmanEncoding(hc,n); printf(n文本编码结果如下:n%sn,a); HuffmanDecoding(ht,a,n);printf(n); printf(n各叶子结点及其频数统计如下:n); for(i=1;i0)，对于任意jk(1j,km)有DjDk=NULL,且对任意的i(

27、1im)，唯一存在数据元素xiDi有H;(3) 相对应于上述的Droot的类型划分，H-,有唯一的一个划分H1，H2,Hm(m0)，对任意jk(1j,km)有HjHk=NULL，且对任意i(1im),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。 基本操作P：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T);初始条件：树T存

28、在。操作结果：将树T清为空树。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是

29、T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。InsertChild(&T,&p,I,c);初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。操作结果：插入c为中指结点的第棵子树。DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，

30、1ip指结点的度。操作结果：删除中所指结点的第棵子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADT Tree在双亲表存储结构中添加以下基本抽象数据类型：Status Print(PTree T)；附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。在双亲表存储结构中，TraverseTree(T,visit()函数是按层次次序对T的每个结点进行访问的。2.主程序流程 void main()

31、初始化； 输入数据； 执行功能；显示结果；3.程序模块间调用关系 主程序 各功能模块三、 详细设计1. 二叉排序树#include #include#include#define ARRAYLEN 100typedef struct node/定义二叉排序树结构int data;struct node *left;struct node *right;BSTree; void Insert(BSTree *t,int key) /在二叉排序树中插入新结点BSTree *p,*parent,*head;p=(BSTree*)malloc(sizeof(BSTree *);p-data=key;p

32、-left=p-right=NULL;head=t; while(head)parent=head;if(keydata)head=head-left;elsehead=head-right;if(keydata)parent-left=p;elseparent-right=p;void Create(BSTree *t,int data,int n) /建立二叉排序树int i;t-data=data0;t-left=t-right=NULL;for(i=1;idata); DLR(t-left); DLR(t-right);void LDR(BSTree *t) /中序遍历二叉排序树if(

33、t)LDR(t-left); printf(%5d,t-data); LDR(t-right);int main()BSTree tree;int n;int i,aARRAYLEN;printf(请指定输入的数串长度：);scanf(%d,&n); printf(n请输入相应长度的一串数值n);for(i=0;in;i+)scanf(%d,&ai);Create(&tree,a,n); printf(n先序遍历二叉排序树结果：n);DLR(&tree);printf(n);printf(n中序遍历二叉排序树结果：n);LDR(&tree);printf(nn);2. 排序#include#i

34、nclude#include#include#define ARRAYLEN 10int move1=0,move2=0,move3=0,compare1=0,compare2=0,compare3=0;int creatdata(int arr,int n,int min,int max)/生成不重复随机函数int i,j,flag;srand(time(NULL);if (max-min+1)n) return 0;for(i=0;in;i+)doarri=(max-min+1)*rand()/(RAND_MAX+1)+min;flag=0;for(j=0;ji;j+)if(arri=arrj)flag=1;while(flag);return 1;int division(int a,int left,int right)/分割函数int base=aleft;while(leftright)while(leftbase)-right;aleft=aright;while(leftright&aleftbase)+left;aright=aleft;compare2=compare2+5;move2=move2+2;aleft=base;return left;vo