数据结构C语 言 版.ppt

《数据结构C语 言 版.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章绪论主讲：郑玉1.1数据结构讨论的范畴1.2与数据结构相关的概念1.3算法和算法的量度软件开发的过程:系统分析系统实现系统维护系统设计系统设计确定系统所要达到的目标确定实现方案并生成系统实地安装调试系统修整完善Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制的一组指令集处理问题的策略问题的数学模型NiklausWirth尼古拉斯·沃斯（NiklausWirth，1934年—）Pascal之父田长霖（1935—2002）他作为第一个华裔美国人从1990到1997年间出任美国一

2、流大学加州大学伯克利分校的校长，为华人争了光，在世界上也产生了广泛的影响。26岁就获得加利福尼亚大学伯克利分校“最年轻教授奖”，年仅40岁就当选为美国工程科学院院士波西米亚俱乐部当今计算机应用的特点：l所处理的数据量大且具有一定的关系；l对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。应用举例1——学籍档案管理假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对

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

4、1c9c4c2c12c10c11c5c3c6c7c8图1-2计算机专业必修课程开设先后关系特点课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。非数值计算的程序设计问题例一求一组(n个)整数中的最大值例

5、二交叉路口的交通管制问题例三煤气管道的铺设问题例四数据库中表格管理问题概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。一、基本概念和术语二、数据结构三、数据类型和抽象数据类型所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。数据是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素例如，整数“5”,字符“N”等。----数据项是不可

6、再分割的“原子”它是数据结构中讨论的最小单位。又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项”。称之为组合项年月日姓名学号班号性别出生日期入学成绩数据项关键字能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。数据对象具有相同特性的数据元素的集合。如:整数、实数等。数据结构带结构的数据元素的集合有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系例如，可用三个4位的十进制数表示一个含12位数的“长整数

7、”。3214,6587,9345─a1(3214),a2(6587),a3(9345)对长整数进行运算的程序中的操作对象是一个含三个数据元素{a1,a2,a3}的集合，且三者之间存在下列“次序”关系:{a1,a2、a2,a3}。又如，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在着两个关系:“行”的次序关系:row={,,,}col={,,}“列”的次序关系:a1a2a3a4a5a6在含6个数据元素{a1,a

8、2,a3,a4,a5,a6}的集合上存在如下的次序关系:{

9、i=1,2,3,4,5}“数据结构”是相互之间存在着某种逻辑关系的数据元素的集合。可见