数据结构课程设计实习报告

1、数据结构课程设计实习报告班 级：地信11102班 学生姓名： 任亮 学 号： 201101252 长江大学2013.732 / 34文档可自由编辑打印 目 录一、需求分析1二、逻辑设计2三、详细设计5四、程序编码9五、程序调试与测试35六、结果分析391、 需求分析：1、程序一：单链表的应用（1）要求生成线性表时，可以键盘上读取元素。通过在键盘上输入的数据构造成单链表，进而对构造成的单链表进行插入、删除、遍历等操作的实现。（2）限制条件是要求在生成线性表的时候，线性表中的元素是从键盘上输入而不是自动生成，这样就可以对自己想要进行的元素序列进行各种操作。2、程序二：二叉排序树的操作（1）建立二叉

2、树，并输出二叉树的先序，中序和后序遍历序列，以及二叉树的叶子数。（2）要求根据读取的元素建立二叉树，能输出各种遍历。（3）可通过输入带空格的前序序列建立二叉链表。附加功能：输出了二叉树的深度。3、 程序三：哈夫曼编码器（未严格依照要求）从键盘接受一串电文字符，输出对应的Huffman编码。同时，能翻译由Huffman编码生成的代码串，输出对应的电文字符串。4、 程序四：停车场管理设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能

3、在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。一、二叉树的基本操作2、 逻辑设计：主函数二、单链表的基本操作三、哈夫曼编码器四、停车场管理图一、主函数总体设计1、功能一链表主函数头插法建立单链表尾插法建立单链表链表元素的删除单链表操作链表元素的插入输出链表取单链表结点求单链表长度图二、单链表的基本操作2、功能二求二叉树的叶子节点数求二叉树的深度二叉树操

4、作后序遍历先序遍历中序遍历图三、二叉树的基本操作3、功能三哈夫曼编码器编码译码建立哈夫曼树图四、哈夫曼树的基本操作4、功能四停车场管理系统车辆离开车辆进入列表显示记录信息打印发票返回上层车在车场车在车道图五、停车场管理系统3、 详细设计：1、单链表的操作（流程图）图六、单链表插入 图七、单链表的删除2、二叉树的基本操作（流程图）图八、二叉树的前序遍历 图九、二叉树的中序遍历图十、二叉树的后序遍历3、 哈夫曼树的详细设计(1) 、构造哈夫曼树。根据Huffman算法：若已知有n个叶子节点，则构造的huffman树有2n-1个结点。先输入字符集中的n个字符（叶子节点）和表示其概率分布的权值，存储在

5、HuffNode型数组的前n个数组元素中。然后将2n-1个结点的双亲和左右孩子均置为0。在所有的节点中，选取双亲为0，且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置。将根为htp1和htp2的两颗树合并，使其成为新节点hti的左右孩子，hti的权值为最小权值m1和次小权值m2之和；htp1和htp2的双亲指向i。重复上述过程，共进行n-1次合并就构造了一颗Huffman树。当进行n-1次合并时，产生n-1个结点，依次放在ht数组中，数组的下标从n到2n-2。（2） 、编码。基本思想：从Huffman树的叶子节点hti出发，通过双亲parent找到其双亲ht

6、f，通过htf的left和right域，可知hti是htf的左分支还是右分支，若是左分支，生成代码0；若是右分支，生成代码1，代码存放在数组cdstart中，然后把htf作为出发点，重复上述过程，直到找到根节点为止。（3） 、译码。基本思想：首先输入二进制代码串，存放在数组ch中，以“#”为结束标志。接下来，将代码与编码表比较，如果为0，转为左子树；若为1，转为右子树，直到叶子节点结束，此时输出叶子结点的数据域，即所对应的字符。继续译码，直到代码结束。4、 停车场管理系统的详细设计（1） 、模拟停车场车辆进出时需要输入车辆的信息，包括车牌号码以及进入和离开的时刻，因此可以定义一个时间节点类型和

7、一个车辆信息结点类型，在顺序栈及链式队列中定义结点类型为车辆信息结点类型。（2） 、当车辆离开后，需要打印输出车辆离开后的信息，如离开时间、离开时的所在位置和应缴纳的费用等，定义函数Print实现。（3） 、车辆到达时需要用户输入车辆的信息，接着要判断栈是否已满，如果当前站未满，则进行入栈操作，即车辆进入停车场；如果栈已满，则车辆必须进入便道等待。用函数Arrival实现。（4）、车辆的离开，则需要另设一个栈，给要离去的汽车让路而从停车场退出来的汽车临时停放，也用顺序栈实现，车辆离开后需检查便道内是否有车等待，如有等待的车辆则进行便道内的车辆进入停车场的操作，即将车辆信息结点进行入栈操作，输入

8、当前时间后开始计费，最后进行出栈操作，表示车辆离开便道以进入停车场。用函数Leave()实现。4、 程序编码：（源码）主函数#include #include#include#include#includeLinkedList.h#includeHuffman.h #includeParking.h#includeTree.hvoid main() int k;char ch=y;while(ch=y)printf(tt#*#*#*#*欢迎进入我的课设工程*#*#*#*#n);printf(ttn);printf(t如果碰到意外结束的情况或者排序不正确的情况nn);printf(tt 请及时联

9、系我 n n);printf(tt 请选择以下题目展示: n);printf(tt 1.二叉树简单操作() n);printf(tt 2.单链表简单操作() n);printf(tt 3.哈夫曼树编码器() n);printf(tt 4.停车场管理系统() n);printf(tt 0.退出程序 n);printf(nnn);printf(请选择(0-4)：);scanf(%d,&k);switch (k)case 1:printf(您选择的是二叉树操作系统n);Treemenu();break;case 2: printf(您选择进入的是单链表操作系统n);LListmenu();break

10、;case 3:printf(您选择进入的是哈夫曼树编码器n);Huffmanmenu();break;case 4:printf(您选择的是停车场管理系统n);Parkingmenu();break;case 0:exit(0);default:printf(您的输入有误，请重新输入！);功能函数1、 二叉树的操作头文件typedef char DataType;#define MAX 100typedef struct BiTNode/二叉链表数据结构定义DataType data;struct BiTNode *lchild,*rchild; BiTree;菜单函数#include#in

11、clude#includeTree.hint Treemenu()/(int argc,char *argv)BiTree *tree;int deep,sum; printf(tt欢迎进入二叉树基本操作系统nnn);tree=Create(); /* 建立二叉树 */ deep=DepthPost(tree);/* 求二叉树高度 */printf(n1:输出先序序列: );PreTra(tree);printf(n2:输出中序序列: );InTra(tree);printf(n3:输出后序序列: );PostTra(tree);printf(n4:输出二叉树的高度：%dn,deep);sum

12、=LeafCount(tree);printf(n5:输出二叉树的叶子节点：%dn,sum);printf(n操作结束！谢谢您的使用。n);return 0; 各个源文件子函数#include#include#includeTree.hBiTree *Create()/非递归方法建立二叉链表BiTree *QMAX;DataType ch;int front,rear;BiTree *s,*root; root=NULL;front=1;rear=0; /队列初始化 printf(t请按完全二叉树的编号顺序依次输入结点序列n);printf(t注：空结点用表示，输入序列以#结束nn);prin

13、tf(t输入的顺序为：);ch=getchar();while(ch!=#)s=NULL; if(ch!=) s=(BiTree *)malloc(sizeof(BiTree);/申请新结点 s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+;Qrear=s; /空结点和新结点都入队if(rear=1) root=s; /rear是1，是根结点，用root指向它elseif(s&Qfront) / 当前结点和双亲结点都非空 if(rear%2=0)/ rear是偶数，新结点为双亲的左孩子Qfront-lchild=s;else / rear是奇数，新结

14、点为双亲的右孩子 Qfront-rchild=s;if(rear%2=1) front+; / rear是奇数，头指针front指向下一个双亲ch=getchar(); return root; void PreTra(BiTree *t) /递归算法先序遍历二叉树if(t) / 初始条件：二叉树存在printf(%c,t-data); / 访问结点 PreTra(t-lchild); / 先序遍历左子树 PreTra(t-rchild); / 先序遍历右子树 void InTra(BiTree *t)/递归算法中序遍历二叉树if(t)InTra(t-lchild); / 中序遍历左子树 pr

15、intf(%c,t-data); / 访问根结点 InTra(t-rchild); / 中序遍历右子树 void PostTra(BiTree *t)/递归算法后序遍历二叉树if(t)PostTra(t-lchild); /后序遍历左子树 PostTra(t-rchild); / 后序遍历右子树 printf(%c,t-data); / 访问根结点 int DepthPost(BiTree *t) /递归算法后序遍历求二叉树的高度int hl,hr,max;if(t)hl= DepthPost(t-lchild); / 求左子树的深度 hr= DepthPost(t-rchild); / 求右

16、子树的深度 max=hlhr?hl:hr; / 得到左、右子树深度较大者return max+1; / 返回树的深度 elsereturn 0; / 如果是空树，则返回0 int LeafCount(BiTree *t) /遍历求叶子结点的个数int sum=0,m,n;if(t) if(!t-lchild)&(!t-rchild) sum+; m=LeafCount(t-lchild); sum+=m; n=LeafCount(t-rchild); sum+=n; return sum; 2、 单链表的操作头文件typedef char DataType; #define OK 1#defi

17、ne ERROR -1typedef struct node/结点类型定义 DataType data;struct node *next;LinkedList;void InitLList(LinkedList *L);int GetLListLength(LinkedList *L);LinkedList *GetLListElem(LinkedList *L, int i);LinkedList *LocateLListElem( LinkedList *L,DataType key);int InsertLList(LinkedList *L,int i,DataType x);int

18、 DeleteLList(LinkedList *L,int i,DataType *e);LinkedList *CreateLList();/ 建立不带头结点的单链表（头插法建表)LinkedList *CreateLListR();/建立带头结点的单链表（尾插法建表）PrintLList(LinkedList *q);菜单函数#include #include#include#include#includeLinkedList.h int LListmenu()LinkedList *a,*p;int length,node,i,j,k;char value,q;char ch=y;wh

19、ile(ch=y)printf(tt#*#*#*#*欢迎进入单链表操作系统*#*#*#*#n);printf(ttn);printf(nnn);printf(t 如果碰到意外结束的情况或者操作不正确的情况nn);printf(tt 请及时联系 n);printf(tt 注意： 功能使用中应该先建表 n); printf(tt 然后进行各个操作，最后初始化链表 n);printf(tt 请选择所需功能: n);printf(tt 1.头插法建表 n);printf(tt 2.尾插法建表 n);printf(tt 3.求表的长度 n);printf(tt 4.取结点(遍历) n);printf(t

20、t 5.插入运算 n);printf(tt 6.删除运算 n);printf(tt 7.输出带头结点的单链表 n);printf(tt 8.链表的初始化 n);printf(tt 0.返回主菜单 n);printf(nnn);printf(请选择(1-8)：);scanf(%d,&k);switch (k)case 1: printf(t您的选择是头插法建表n);printf(t输入字符串,如: abcdef 以结束后回车n);a=CreateLList();PrintLList(a);break;case 2: printf(t你的选择是尾插法建表n);printf(t输入字符串,如: ab

21、cdef 以结束后回车n); a=CreateLListR();PrintLList(a);break;case 3: printf(t您选择的是计算表的长度n);length=GetLListLength(a);printf(该表的长度为：%dn,length);break;case 4: printf(t您的选择是取结点n);printf(请输入取第几个节点：n);scanf(%d,&node);p=GetLListElem(a,node);if(p=NULL)printf(表中没有该节点!n);elseprintf(该节点的数据域为：%cn,p-data);break;case 5: p

22、rintf(您的选择是插入运算n);printf(请输入要插入的位置：n);scanf(%d,&i);printf(请输入插入的字符);getchar();scanf(%c,&value);InsertLList(a,i,value);PrintLList(a);break;case 6: printf(t您选择的是删除运算n);printf(请输入要删除的位置 n);scanf(%d,&j);DeleteLList(a,j,&q);PrintLList(a);break;case 7: printf(t输出链表为：);PrintLList(a);break;case 8:printf(t您选

23、择的是链表的初始化n);InitLList(a);PrintLList(a);break;case 0:printf(t您的选择是返回主菜单n);main();default:printf(tt输入错误！请重新输入！ntt);return 0;各个子函数源文件#include #include#include#include #includeLinkedList.hvoid InitLList(LinkedList *L)/ 对单链表进行初始化 L-next=NULL;/ 置为空表 int GetLListLength(LinkedList *L)/ 求表的长度 LinkedList *p;i

24、nt j;p=L-next;j=0;while(p!=NULL)p=p-next;j+;return j; LinkedList *GetLListElem(LinkedList *L, int i)/在带头结点的单链表L中查找第i个结点 int j;LinkedList *p;p=L;j=0; while (p-next!=NULL)&(jnext; j+; if(i = j)return p; else return NULL; LinkedList *LocateLListElem( LinkedList *L,DataType key)/在带头结点的单链表L中查找其 LinkedLis

25、t *p;p=L-next; while (p!=NULL)if (p-data!=key)p=p-next; elsebreak; return p; int InsertLList(LinkedList *L,int i,DataType x)/在带头结点的单链表L中第i个位置插入值为e的新结点sLinkedList *pre,*s;int k;pre=L; k=0; while(pre!=NULL&knext;k=k+1; if(!pre) printf(插入位置不合理!);return ERROR;s=(LinkedList*)malloc(sizeof(LinkedList); s-

26、data=x; s-next=pre-next; pre-next=s;return OK; int DeleteLList(LinkedList *L,int i,DataType *e)/在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中LinkedList *pre,*r;int k;pre=L;k=0;while(pre-next!=NULL & knext; k=k+1; if(!(pre-next) printf(删除结点的位置i不合理!);return ERROR;r=pre-next;pre-next=pre-next-next; *e = r-data;fr

27、ee(r); printf(成功删除结点!);return OK;LinkedList *CreateLList()/ 建立不带头结点的单链表（头插法建表)char ch;LinkedList *l,*s;l=(LinkedList *)malloc(sizeof(LinkedList);l-next=NULL;ch=getchar();while(ch!=) s=(LinkedList *)malloc(sizeof(LinkedList);s-data=ch;s-next=l-next;l-next=s;ch=getchar();return l;LinkedList *CreateLLi

28、stR()/建立带头结点的单链表（尾插法建表） char ch;LinkedList *head,*s,*r;head=(LinkedList *)malloc(sizeof(LinkedList);r=head;ch=getchar();while(ch!=) s=(LinkedList *)malloc(sizeof(LinkedList);s-data=ch;r-next=s;r=s;ch=getchar(); r-next=NULL; return head;PrintLList(LinkedList *q)/输出带头结点的单链表LinkedList *p;p=q-next;print

29、f(字符单链表结果是: n();while(p!=NULL)printf(%5c,p-data);p=p-next; printf(b);3、 哈夫曼编码器头文件#include typedef char DataType;#define MAXNUM 50typedef struct/ 哈夫曼树结点的结构 DataType data; / 数据用字符表示 int weight; / 权值 int parent; / 双亲 int left; / 左孩子 int right; / 右孩子 HuffNode;typedef struct/ 哈夫曼编码的存储结构 DataType cdMAXNUM

30、;/ 存放编码位串 int start; / 编码的起始位置 HuffCode;菜单函数#includeHuffman.hint Huffmanmenu()int n,select,flag=0; / flag为0时标记第一次选择功能 HuffNode ht2*MAXNUM; / 定义存放哈夫曼树的数组 HuffCode hcdMAXNUM; / 定义存放编码的数组 while(1)printf(t 请选择您所要实现的功能：n);printf(t1-建立哈夫曼树n);printf(t2-编码n);printf(t3-译码n);printf(t4-退出系统n);printf(（请输入1-4数字）

31、n);scanf(%d,&select);if(select!=1&select!=4&flag=0) / 提示先建立哈夫曼树或退出 printf(请先建立哈夫曼树再选择其他功能！n);continue;flag=1;switch(select) / 选择功能 case 1:n=HuffmanCreate(ht); break;case 2: Encoding(ht,hcd,n); break;case 3:Decoding(ht,hcd,n); break;case 4: return 1;return 0; 各个子函数模块#includeHuffman.hint HuffmanCreate

32、(HuffNode *ht)/建立哈夫曼树 int i,k,n,m1,m2,p1,p2;printf(请输入元素个数：);scanf(%d,&n);for(i=1;int结点值：,i);scanf(%c,&hti.data);printf(t权 重：);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) / 对数组初始化 hti.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+) m1=m2=32767; / 初始化，令m1、m2为整数最大值 p1=p2=1;for(k=1;k=i-1;k+) / 从数组ht1到h

33、ti-1中找出 if(htk.parent=0) / parent为0并且权值最小的两个结点 if(htk.weightm1) m2=m1; / m1为最小权值 p2=p1; / p1为最小权值的位置 m1=htk.weight; / m1存放最小权值 p1=k;else if(htk.weightm2)m2=htk.weight; / m2为次小权值 p2=k; / p2为次小权值的位置 htp1.parent=i; / i分别赋给下标为p1、p2的数组中 htp2.parent=i;hti.weight=m1+m2; / 新结点的的权值为最小权值和次小权值的和 hti.left=p1; /

34、 p1为新结点的左孩子 hti.right=p2; / p2为新结点的右孩子 printf(哈夫曼树已成功建立！n);return n; void Encoding(HuffNode ht,HuffCode hcd,int n)/ 哈夫曼编码 HuffCode d;int i,k,f,c; for(i=1;i=n;i+) / 对所有结点循环 d.start=n+1; / 起始位置 c=i; / 从叶结点开始向上 f=hti.parent;while(f!=0) / 直到树根为止 if(htf.left=c)d.cd-d.start=0;/ 规定左树为代码0 elsed.cd-d.start=1

35、;/ 规定右树为代码1 c=f; / c指孩子的位置 f=htf.parent; / f指双亲的位置 hcdi=d;printf(输出哈夫曼编码：n);for(i=1;i=n;i+) / 输出哈夫曼编码 printf(%c:,hti.data); / 先输出结点 for(k=hcdi.start;k=n;k+)/ 再输出其对应的编码 printf(%c,hcdi.cdk);printf(n);void Decoding(HuffNode ht,HuffCode hcd,int n)/ 哈夫曼译码 int f,m,k;DataType c,ch200; / c接收输入电文，ch存储 printf

36、(请输入电文(0 or 1)，以#为结束标志：n);c=getchar();k=1;while(c!=#) / 单个字符循环输入，以#结束 chk=c; / 将单个字符依次存入ch字符串中 c=getchar();k=k+1; / ch数组下标后移 m=k; / 标记数组存储末尾位置 f=2*n-1;k=1; / k记录电文字符的个数 printf(输出哈夫曼译码：n);while(km) /k循环到数组末尾结束 while(htf.left!=0)/ 直到左孩子结点为0结束 if(chk=0) / 若接收的字符为0，则存为左孩子 f=htf.left;if(chk=1) / 若接收的字符为1

37、，则存为右孩子 f=htf.right;k+; / ch数组下标后移 printf(%c,htf.data);f=2*n-1; / 每次都从根结点开始查找 printf(n);4、停车场管理系统头文件#define True 1#define Max 2 /停车场车容量，最多停两辆#define Price 0.1 /每车每分钟收费标准typedef struct int hour; int min;Time; /定义时间信息typedef struct char num10; Time reach; Time leave;CarNode; /车辆信息typedef struct CarNod

38、e *stackMax+1; int top;SeqStackCar; /模拟车站(栈)typedef struct CarNode *data; struct car *next;QueueNode;/队列typedef struct QueueNode *head; QueueNode *rear;LinkQueueCar; /模拟通道 菜单函数#include#include #includeParking.hvoid Parkingmenu() SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; StackInit(&Enter); /

39、初始化车站 StackInit(&Temp); /初始化让路的临时栈 QueueInit(&Wait); /初始化通道 while(True) printf(nn);printf(tt欢迎使用停车管理系统n);printf(tt 1.车辆到达 n);printf(tt 2.车辆离开 n);printf(tt 3.列表显示 n);printf(tt 4.退出系统 n);printf(tt 0.返回主菜单 n);printf(tt欢迎使用停车管理系统n);printf(nnt请选择菜单号（0-4）:); while(True) scanf(%d,&ch); if(ch=0&ch=4)break;

40、else printf(nt您的输入有错误！);printf(nt请选择菜单号（0-4）:); switch(ch) case 1: Arrival(&Enter,&Wait);break; case 2: Leave(&Enter,&Temp,&Wait);break; case 3: List(Enter,Wait);break; case 4: exit(0); case 0:main();break; default: break; 各个子函数模块#include#include #includeParking.hvoid StackInit(SeqStackCar *s) /初始化栈 int i; s-top=0; for(i=0;istacks-top=NULL;int QueueInit(LinkQueueCar *Q) /初始