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

《数据结构课程设计实习报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

5、字符集中的n个字符（叶子节点）和表示其概率分布的权值，存储在HuffNode型数组的前n个数组元素中。然后将2n-1个结点的双亲和左右孩子均置为0。在所有的节点中，选取双亲为0，且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置。将根为ht[p1]和ht[p2]的两颗树合并，使其成为新节点ht[i]的左右孩子，ht[i]的权值为最小权值m1和次小权值m2之和；ht[p1]和ht[p2]的双亲指向i。重复上述过程，共进行n-1次合并就构造了一颗Huffman树。当进行n-1次合并时，产生n-1个结点，依次放在ht数组中，数组的下标从n到

6、2n-2。（2）、编码。基本思想：从Huffman树的叶子节点ht[i]出发，通过双亲parent找到其双亲ht[f]，通过ht[f]的left和right域，可知ht[i]是ht[f]的左分支还是右分支，若是左分支，生成代码0；若是右分支，生成代码1，代码存放在数组cd[start]中，然后把ht[f]作为出发点，重复上述过程，直到找到根节点为止。（3）、译码。基本思想：首先输入二进制代码串，存放在数组ch中，以“#”为结束标志。接下来，将代码与编码表比较，如果为0，转为左子树；若为1，转为右子树，直到叶子节点结束，此时输出叶子结点的数据域，即所对应的字符。继续译码

7、，直到代码结束。4、停车场管理系统的详细设计32（1）、模拟停车场车辆进出时需要输入车辆的信息，包括车牌号码以及进入和离开的时刻，因此可以定义一个时间节点类型和一个车辆信息结点类型，在顺序栈及链式队列中定义结点类型为车辆信息结点类型。（2）、当车辆离开后，需要打印输出车辆离开后的信息，如离开时间、离开时的所在位置和应缴纳的费用等，定义函数Print实现。（3）、车辆到达时需要用户输入车辆的信息，接着要判断栈是否已满，如果当前站未满，则进行入栈操作，即车辆进入停车场；如果栈已满，则车辆必须进入便道等待。用函数Arrival实现。（4）、车辆的离开，则需