数据结构c语言版 (1)

《数据结构c语言版 (1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章绪论1.1《数据结构》研究什么1.3基本概念和术语1.4数据类型和抽象数据类型1.5算法和算法分析1.1《数据结构》研究什么(1)、要对所加工的对象进行逻辑组织。(2)、如何把加工对象存储到计算机中去？(3)、数据运算。实际问题→数学模型→编程、调试当今计算机应用的特点：l所处理的数据量大且具有一定的关系；l对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。应用举例1——学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。特点：l每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；l表中每个学生的信息依据学号的大小存在

2、着一种前后关系，这就是我们所说的线性结构；l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。应用举例2——输出n个对象的全排列输出n个对象的全排列可以使用下图所示的形式描述。特点：l在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；l对它的操作有：建立树形结构，输出最低层结点内容等等。应用举例3——制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8

3、计算机专业必修课程开设先后关系特点:l课程之间的先后关系用图结构描述；l通过实施创建图结构，按要求将图结构中的顶点进行线性排序结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。1.3基本概念和术语数据：对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程

4、序处理的符号总称。数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。1.4数据类型和抽象数据类型数据类型：和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画操作对象的特征，是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型：由用户定义用以表示应用问题的数据类型。抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或操作）。特征：使用与实现分离，实行封装和信息隐蔽。1.5算法和算法分析算法：算法是解决某个特定问题的一

5、种方法或一个过程。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。设计算法的基本过程:l通过对问题进行详细地分析，抽象出相应的数学模型；l确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；l选用某种语言将算法转换成程序；l调试并运行这些程序。算法应该具有下列五个特性:（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4

6、）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。例:问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：（1）输入x，y，z三个数值；（2）从三个数值中挑选出最小者并换到x中；（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。算法的描述自然语言伪码流程图N-S图程序设计语言选择算法描述语言的准则:（1）该语言应该具有描述数据结构和算法的基本功能；（2）该语言应该尽可能地简捷，以便于掌握、理解；（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。算法分析标准：正确性

7、：对于一切合法的输入数据，该算法经过有限时间的运行都能够得到正确的结果。可读性：有助于设计者和他人阅读，理解，修改和引用。健壮性：当输入数据非法时，算法也能做出正确的反应或进行相应的处理，不致造成损失或产生错误的输出结果。时间效率和存储要求。时间效率：指算法对时间的需求，一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)。T(n)=O(f(n))空间需求：指算法执行过程中对计算机存储空间的要求，称为算法的空间复杂度。S(n)=O(f(n))一般法则