数据结构课程设计论文

学年论文（课程论文、课程设计）题目：数据结构课程设计作者：阿拉腾达日所在学院：信息科学与工程学院专业年级：计算机14-3指导教师：阿孜古丽·牙会甫职称：副教授2016年06月24日摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。关键词：信息技术；线性表；二叉树；图；排序目录绪论................................................................51．文本文件的单词检索与计数.........................................61.1需求分析.....................................................61.2概要设计.....................................................61.2.1数据结构的设计.........................................61.2.2存储方式...............................................61.2.3基本操作的设计.........................................61.3详细设计.....................................................71.4关键代码.....................................................81.5测试及结果分析...............................................91.6总结........................................................102．哈夫曼树的建立..................................................112.1需求分析....................................................112.2概要设计....................................................112.2.1数据结构的设计........................................112.2.2存储方式..............................................112.2.3基本操作的设计........................................112.3详细设计....................................................122.4关键代码....................................................132.5测试及结构分析..............................................152.6总结........................................................153．图的应用........................................................173.1需求分析...................................................173.2概要设计...................................................173.2.1数据结构的设计........................................173.2.2存储方式..............................................173.2.3基本操作的设计........................................183.3详细设计...................................................183.4关键代码....................................................193.5测试及调试分析..............................................203.6总结.......................................................214.内部排序比较算法.................................................224.1需求分析....................................................224.2概要设计....................................................224.2.1数据结构的设计........................................224.2.2存储方式..............................................224.2.3基本操作的设计........................................224.3详细设计....................................................234.4关键代码....................................................244.5测试及结果分析..............................................264.6总结........................................................275.课程设计的总结...................................................29绪论在信息化社会的今天，计算机及其网络给人类社会、人们的生活和学习等方方面面带来了巨大的影响，随之而来的是社会对信息技术型人才的需求量也越来越大，而信息技术型人才的培养又是高等学校人才培养的重要组成部分。数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表现和实现。因此，数据结构不仅是计算机专业的一门核心课程，而且也是其他理工科专业的热门选修课。学会分析研究计算机加工的数据对象的特性，能够选择合适的数据结构、存储结构和相应的算法并加以实现，是计算机工作者和其他科技工作者不可缺少的知识和能力。数据结构课程内容抽象，知识丰富。要掌握各种算法及算法分析的方法与思路，因而使自身的编写能力提升。1．文本文件的单词检索与计数1．1需求分析要求编程建立一个文本文件，每个单词不包括空格且不垮行，单词由字符序列构成且区分分大小写，统计给定单词在文本文件中出现总次数，检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。1.2概要设计1.2.1数据结构的设计typedefstruct{charch[MAXSIZE];//ch是一个可容纳MAXSIZE个字符的字符数组intLength;}Sstring;//定义顺序串类型1.2.2存储方式本课题使用了串的顺序存储结构。顺序串是用一组地址连续的存储单元来依次存放串中的字符序列，串中相邻的字符顺序存放在相邻的存储单元重。1.2.3基本操作的设计1.2.3.1建立文本文件要建立一个文本文件并向其写入数据，应该先定义一个输出流指针，再将某文件打开，然后向其中输入文本，最后关闭文件。1.2.3.2给定单词计数由用户输入一个单词。打开一个输入文件从文件中的读取一个字符串放到一个则计数加1。然后继续从文件中读出一个字符串进行比较，直到文件读到末尾结束。1.2.3.3检索给定单词由用户输入一个单词。打开一个输入文件，从文件中读取数据。因为需要判断某个单词在文件中的哪一行，因此读取数据的时候每次只读取一个字符当读取的字符是换行符时，标记行数的值加1。当在某一行中查找到了该单词的时候，需然后还要再检查该行中是否还有与指定单词相同的单词也要记录下这些单词的位置，同时还需要记录该行中与指定单词相同的单词的个数，最后将这些信息一同输出。当读到文件尾时检索结束。1.3详细设计1.3.1函数设计流程文本文件的单词检索与计数的设计图（1.3.1-1）1.3.2串匹配函数intPartPosition(Sstrings1,Sstrings2,intk)首先扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1，然后再扫描s2的开始下标，对s1和s2进行比较，比较完若匹配成功则继续使下标移向下一个字符位置。这样重复步骤进行比较来进行匹配。1.3.3建立文件函数原型为voidCreatTextFile()，参数是将要建立的文本文件的文件名，该文件名由用户输入。1.3.4单词计数首先要求用户输入一个单词。接着定义变量，一个标记单词个数的整型变量i并初始化为0。用输入模式打开用户指定的文本文件(若用户没有指定文件，则打开默认的原有文件)以每次读取一个字符的方式将文件中的数据读到fname数组中，当文件中一个单词的计数已结束，此时应该将存放在字符数组中的字符串与用户指定单词进行比较，若相同，则计数i加1，同时将字符数组清空，若不相同，继续读取文件中下一个字符。当读完文件后，计数部分结束。关闭文件，main（）PartPosition（）SubStrInd()SubStrCount()CreatTextFile()输出计数结果即可。1.3.5单词检索首先由用户输入待检索单词。定义各个变量，整型变量，标记当前读取的字符在文件中的行数、次数、位置。读取字符时，以每次只读取一个字符的形式从文件中读取数据。主要由while循环来进行对文本文件的单词的扫描，及进行串的扫描。1.4关键代码1.4.1串的模式匹配算法IntPartP