文档介绍：数据结构设计报告 1 《数据结构》课程设计报告目录第一章:绪论…………………………… 3 第二章:需求分析……………………… 4 、输入与输出要求 、程序功能 、正确输入与正确结果第三章:概要设计……………………… 7 、设计思想 、设计流程图第四章:详细设计……………………… 9 、圆括号匹配的主要结构 、图的主要结构 、哈夫曼树的主要结构第五章:调试分析……………………… 11 、测试数据与测试结果 、存在问题与解决的方案 、算法的改进与设想第六章:课程设计总结……………………… 8 参考文献:《数据结构》(C语言版) 数据结构设计报告 2 第一章绪论课程设计的目的: 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用和作风。于信息学、系统工程等各种领域。学****数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的: 1 、了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3 、提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法 4 、通过此次课程设计能够很好地检查学生的学****情况,并能培养学生的动手能力课程设计主要内容: 1 、从键盘输入一个算术表达式字符串,判断其中园括号是否匹配,若匹配则返回 TRUE, 否则 FALSE 。 2 、创建图,并利用图的深度优先, 广度优先遍历算法对图进行遍历 3 、从键盘输入字符集大小 n,n 个字符和 n 个权植,建立哈夫曼树。数据结构设计报告 3 第二章、需求分析 、输入与输出要求: (1) 、从键盘输入一个算术表达式以字符串形式输入。输出结果为 TURE 或者 FALSE ,如果匹配则为 TRUE ,如果不匹配则为 FALSE 。(2)、从键盘输入一个图中相邻的顶点与一些附加信息( 如权值), 输出图的邻接表形式与图的广度或深度优先访问的结果。(3) 、从键盘输入 N 个字符的字符集,用表的形式打出哈夫曼树的结构关系,且把哈夫曼编码打出来。 、程序功能(1) 、在平时计算复杂时如式子很长且括号较多时不记得是否匹配,那么通过能此程序能够判断式子中是否匹配。(2) 、对图进行深度广度优先访问(3) 、哈夫曼树是最优二叉树,如在现化通信中传码希望总长最短所以常用哈夫曼树进行编码。在现化通信中进行传输中常哈夫曼编码来准确传输信号,此程序就是一个建立哈夫曼树和哈夫曼编码的程序。 、输入与输出结果(1) 、圆括号匹配正确:若输入( 1+2 ) -8* ( 2-6 )+( 3+4 )# ,安要求则输出 TRUE 错误:若输入( # ,安要求则要输出 FALSE (2) 、图的遍历若输入数据结构设计报告 4 则其结构图和按广度遍历结果应为则其结构图和按深度遍历结果应为(3) 、哈夫曼树权植双亲左孩子右孩子 123456789 10 11 12 13 14 15 59 29 14 7 10 8 10 14 12 23 13 39 11 11 8 1117 15 1244 19 1389 29 145 10 42 156 11 58 152 12 100 0 13 14 数据结构设计报告 5 哈夫曼编码 011010111011111********** 第三章概要设计 、设计思想(1) 、圆括号的匹配问题很明显的需要一个栈来存储待判断的字符串,当遇到左括号的时候就入栈如果不是则不需要的管它,如果是右括号则与栈顶元素进行比较若是匹配的则把栈顶元素出栈以便下一次的比较,一直到栈空则说明匹配成功返回 TRUE 。如果出现栈顶元素与右括号不匹配终止程序并返回 FALSAE (2) 、图的操作过程中先要对图的元素进行存储,这里采取邻接表的形式来存储(对每一个顶点建立一个单链表)。深度优先遍历和树的先根遍历一类似, 图的广度优先和树的层次遍历类似。(3) 、哈夫曼树的存储结构采取的是一维数组每一结点有权值,双亲,左孩,右孩等一些信息。创建过程为先找两个最小的相加后组成其中一部分,并删除参与运算了的两个值, 依此类推。哈夫曼编码则中从树叶子向上若为左孩则为‘0’右孩则为‘1’,