数据结构课程设计汇总.docx

教学单位 信息工程系 学生学号 0143017541 数据结构课程设计汇总 题 目 课程设计汇总 学生姓名 专业名称 软件工程 指导教师 叶从欢 2016年5月31日目录数据结构课程设计汇总1课程设计一、多项式的基本运算3实验目的：3实验内容：3解题思路：3实验小结：8课程设计二、栈的应用逆波兰式求值8实验目的：8实验内容：9解题思路：9实验小结：12课程设计三、图的应用简易的社交网络图13实验目的：13实验内容：13解题思路：14实验小结：22课程设计四、哈夫曼编码23实验目的：23实验内容：23解题思路：23实验小结：28课程设计五、哈希表的相关运算29实验目的：29实验内容：29解题思路：29实验小结：33课程设计六、 广义表的创建与遍历33实验目的：33实验内容：33思路分析：34实验总结：40课程设计七、排序方法40实验目的：40实验内容：40解题思路：41实验小结：48课程设计一、多项式的基本运算实验目的：掌握线性表的链式存储结构和线性表的典型应用多项式求和、差运算，通过实验进一步加深对线性表的存储结构的理解与熟悉。实验内容：链式存储结构的实现：已知：f(x)=100x100+5x50-30x10+10, g(x)=150x90-5x50+40x20+20x10+3x,求和与差。解题思路：定义一个结构体数组，p存储系数,q存储指数。分别输出两次输入的多项式。将两次输入的多项式的指数按从大到小的顺序进行排列，同时相应的系数要进行交换。输出时如果进行如果当前该项与下一项的的系数相同，将两项系数相加后输出，并跳过下一项，如果不相等，直接输出。输出时需注意的问题：当系数为0时，该项不输出当系数为负数时，不要再在前面输出+。程序如下：结果验证：实验小结：课程设计二、栈的应用逆波兰式求值实验目的：1. 掌握栈的特点及其描述方法；2. 掌握栈的各种基本操作；3. 掌握栈的一个经典应用-逆波兰式求值问题。实验内容：从键盘敲入一个整数表达式，先将其转化为逆波兰表达式，再计算值。解题思路：逆波兰式又叫后缀表达式，规定把运算符号放在两个操作数的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号。后缀表达式求值的步骤：1.初始化一个空操作数栈: 2.从前到后读取后缀表达式字符。如果是操作数直接入栈。如果读到一个操作符，弹出栈顶元素a和新的栈顶元素b，执行b a，将结果压入栈中；3.最后栈中只剩下一个元素，即表达式的值。源代码如下：实验结果验证：实验小结：课程设计三、图的应用简易的社交网络图实验目的：（1） 掌握图的几种存储方法（邻接矩阵、邻接表等）；（2） 掌握图的连通和图中各节点的联系。实验内容：给出如图所示的简易社交连通图：ABCDEF要求：输入A,B,C,D,E,F处的人名，计算某两人之间的陌生度（即权值的大小之和）与连通两人的通路（权值在下面的代码中已给出）。解题思路：直接相连的两个节点间边的权值就是两节点间的亲密度（陌生度），权值越小，节点间越亲密；通过邻接矩阵给出的数值可以求出两节点间的亲密度；通过迪克斯特卡算法可以求出不相邻的两节点间的权值之和和经过的节点，从而达到解决问题的目的。程序代码如下： 运行结果：实验小结：课程设计四、哈夫曼编码实验目的：用所学的知识构造一棵哈夫曼树并以英文字母出现的次数做权值，遍历哈夫曼树同时输出每个字母的哈夫曼编码。 实验内容：从txt文件读入一段英文，统计其中每个字母出现的频率，并输出其哈夫曼编码。解题思路：构造哈夫曼编码的方法如下：第一步定义一个结点的结构体，包括结点的权值，结点的双亲结点，左孩子，右孩子。并定义两个HTNode,*HuffmanTree为该类型的名字。 第二步创建一个Select函数用来选择结点较小的结点权值和下标。实现方法主要利用两个for循环实现。首先判断是否是单个结点如果是跳出for循环如果不是定义p和s记录当前结点的权值和记录当前结点的下标。接着通过一个for循环进行选择把结点权值最小的1 4结点权值和下标记录分别记录在p和s中。第三步构造哈夫曼树和求每个字符的哈夫曼编码。先判断结点个数n是否小于等于1如果是则返回如果大于1则计算出哈夫曼树中共有m=2n-1个结点。然后创建一个HTNode类型的数组HT存储结点个数（结点的相关信息），再定义一个HuffmanTree类型的指针P用来指向数组HT。将HT中前n个单元保存输入的结点信息，后m-n个单元保存为空结点。接着构造哈夫曼树，其实现方法为首先利用Select函数选择权值最小的两个结点s1和s2再将将s1和s2合并从而得到这两个结点的双亲结点保存为i，且双亲结点的权值为s1,s2权值之和。接着从叶子到根逆向求每个字符的哈夫曼编码。其实现方法为：首先创建一个字符指针数组HC和一个字符型指针数组cd用来存储0和1。定义c表示结点序号，f表示c结点的双亲结点序号，接着通过一个for循环将建立好的哈夫曼树的左边赋值为0右边赋值1，再为每一个结点创建一个长度为n-start的字符数组用来存储哈夫曼编码。最后把从cd地址开始且含有NULL结束符的字符串赋值到以HC开始的地址空间。 第四步main函数的实现。首先定义一个HuffmanTree类型的HT初始化为空。接着输入哈夫曼权值的个数判断个数是否小于等于1如果小于等于1则输出输入错误,哈夫曼权值的个数要大于1。如果大于1则创建一个w指针数组用来存储结点权值，最后通过调用HuffmanCoding函数输出每个结点的哈夫曼编码。程序如下：结果验证：实验小结：课程设计五、哈希表的相关运算实验目的：建立一个哈希表，完成其插入、删除、查找等相关基本运算，在实验的过程中加深对相关知识点的理解和掌握。实验内容：建立16,74,60,43,54,90,46,31,29,88,77哈希表，哈希函数为：H（k）=key%p，并采用线性探查法解决冲突；在上述哈希表中查找关键字为29的记录；在上述哈希表中删除关键字为77的记录，然后再将其插入。解题思路：根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = akey + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）