《第一章 数据结构----绪论》由会员分享，可在线阅读，更多相关《第一章 数据结构----绪论（14页珍藏版）》请在金锄头文库上搜索。
1、数学与软件科学学院信息与计算科学专业2006-2007年第1学期数据结构教案-详案-2004级6班课程导入课程性质：专业必修课总学时数：20*3=60学时上机学时：18*2=36学时假设前提：已有程序设计基础（C/C+基础，尤其是C语言程序设计基础）学习目标：培养数据抽象能力(Data Abstraction Ability) 。注：C程序设计课则是培养结构化程序设计的能力。具体涉及两个方面内容的学习和训练：1) 学会分析研究计算机加工数据结构的特征，以便学会针对不同的应用问题，选择合适的逻辑结构、存储结构及相应的算法描述。并做相应的时间复杂度和空间复杂度的分析。2) 复杂程序设计方法的训练过
2、程。学会将问题求解的程序设计成结构清楚、正确、符合软件工程规范的系统。 学习方法：勤奋练习，积极上机实践。(熟悉各种数据结构的基本思想和算法描述，并不断尝试结合教材内容和课外训练的数据抽象能力的培养)教学步骤：整体上分为两个部分内容，一是数据结构的基本思想、方法与应用技巧，二是上机实践。具体内容：第一章 绪论第二、三、四、五、六、七章 基础(强调从ADT的角度进行描述的思想)第八章 OS/Compiler中的动态存储管理技术()第九、十章 查找/内排序第十一章 外排序()第十二章 文件结构()注：由于学时数的限制，第八章、第十一章和第十二章暂时不做要求。其它章节中，带*号的章节不做要求或不做考
3、试要求。课程教材数据结构，严蔚敏，吴伟民 编著，北京：清华大学出版社，2003年3月参考书目(1) 计算机算法：设计和分析引论，美 S 巴斯, 朱洪 等译，上海：复旦大学出版社，1985(2) Data Structures with C+,美 William Ford, William Topp, 北京：清华大学出版社，Printice-Hall International, inc. 1998年4月，ISBN 7-302-02413-8(3) 数据结构、算法与应用-C+语言描述，美 Sartaj Sahni 著，汪诗林，孙小东 译，北京：机械工业出版社，2002年10月，ISBN 7-11
4、1-07654-1(4) 计算机程序设计艺术（第2版），第3卷，美Donald E.Knuth 著，北京：清华大学出版社，2002年9月，ISBN 7-302-05816-4(5) 算法设计技巧与分析，（沙特）M.H. Alsuwaiyel 著，北京：电子工业出版社，2004年8月，ISBN 7-121-00108-X注：其它很好的学习类参考书籍，请咨询高年级学长或光临书店！习题及实验参考书(1) 数据结构实验教程(C语言版)，王玲 主编，成都：四川大学出版社，2003年7月(2) 数据结构习题集(C语言版)，严蔚敏，吴伟民 编著，北京：清华大学出版社，2003年1月第一章 绪论需要对程序的处
5、理对象进行组织研究的两大主要原因：一是计算机领域的渗透早已使其应用不再局限于早期的科学计算领域其加工处理对象由纯粹的数值类发展到具有一定结构的数据类型，如字符、表、图形、图像、声音等，使得程序设计活动面临了许多新的问题需要解决。二是要编写出好的程序系统，人们发现，必须要对待处理对象的数据特性、各处理对象之间的关系进行分析、组织，使编写出的程序能够有效地处理和解决它们。它们构成了数据结构的研究动力和研究内容。1-1 什么是数据结构？Data Structure (DS):Data- (1) facts; (2) Information prepared for or stored by a co
6、mputer;Structure- way in which something is put together, organized, built, etc.1-1-1 不同问题的数据结构模型构建实例分析用计算机解决问题的步骤：抽象其数学模型求解该模型的算法编制程序测试或调试得解(1) 对数值计算问题例1-1 求解梁架结构中应力的数学模型；预报人口增长的微分方程模型。其关键在于分析问题，提取或寻找对象之间的结构关系，然后用数学语言加以描述。(2) 对无法用数学模型描述的非数值计算问题其数学模型集中在数据结构的建立中。例1-2 图书馆书目检索系统自动化问题。按书名的索引表、按作者名的索引表、按
7、分类号的索引表、按登录号排列的书目表表示结构就是其检索问题中的基本数据关系的数学模型(此为线性的结构关系模型)。(见教材P1-2)例1-3 人机对弈问题。其对弈策略、规则驱动、棋盘状态、前景预测方法等模型的建立，同时，棋盘状态描述模型是对弈问题的关键性数据描述模型，但棋局之间的关系往往不是线性的，需要用非数值型结构来描述。例如：#字游戏问题(见教材P2)。需要用到所谓“树结构”来描述这些棋盘状态之间转换过程。例1-4 多叉路口交通灯的管理问题(在多叉路口需要设多少颜色的灯，使得车辆之间互不碰撞，同时车流量最大) (见教材P2-3) 对图的顶点作图的问题。与此相关的还有如哥黎斯堡七桥问题、逻辑电
8、路设计问题等，用传统的数学模型是无法描述的。必须用新型的所谓“图结构”进行描述。1-1-2 DS课程的研究内容及课程历史DS研究内容：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的一门学科课程。DS作为一门独立课程的发展历史：1968年，DS与图论、表、树为“同义语”。后来，扩充到了网络、集合代数、格、关系等(它们又构成了“离散数学”的基础内容)。再后来，将大型数据库系统中的文件管理以及内存管理等技术也纳入了本课程中来。计算机程序设计艺术(第一卷) ，Donald Knuth (Turing 奖获得者)（开创了最初的DS体系，是第一本系统阐述数据的逻辑结构、存储结构及其
9、操作的著作）目前，DS是许多专业的选修或必修课。DS课程的地位(综合性非常强)(见教材P4图1.4)：界于数学、计算机软件和计算机硬件之间的核心课程。既是一般程序设计的基础，更是编译程序、OS、DBS及其它大型的系统程序和应用程序设计与实现的重要基础。发展方向：1) 向各专门领域中的特殊问题之数据结构研究发展；2) 从ADT观点来研究。1-2 数据结构中涉及的基本概念与术语1-2-1 基本概念和术语(1) Data-(facts/information)能被计算机处理的符号总称,是待加工的“原料”例如：求解代数方程组时的Data为integer/real型的系数或根等； 编译器的Data为：程
10、序代码或字符序列； 文字编辑器的Data为：字符、图形等。(2) Data Element-对数据进行处理的基本单位例如：前述的棋盘之格局；图中的顶点等。注：数据元素一般由若干数据项(Data Item)组成。又如：前述图书书目中的书卡数据由作者姓名、书名、书号等数据项构成。(3) Data Object-相同性质的数据元素之集合例如：整数数据对象即集合;字母字符对象即；计算机信息与计算科学专业2003级学生对象即全体该班的学生集合等。(4) Data Structure-相互之间存在某种特定关系的数据元素之集合(从操作对象抽象出来的数学模型)注1：DS中的数据元素不是孤立存在的；注2：数据元
11、素之间的关系即可称为“结构”；注3：数据元素之间的关系有4种基本结构：集合(set)关系-无序的松散关系；线性(linear)关系-一一对应关系(one-one)；树(tree)关系-一对多关系(one-many)；图(graph)关系或者网(net)关系-多对多关系(many-many)。（如教材P5图1.5所示）注4：DS的形式定义为：D_S=(D,S)。其中，D为数据对象有限集合，S为D上的关系有限集合。注5：一般而言，DS要表达的是一组具有相同结构的数据对象之值的集合。1-2-2 实例分析例1-4 复数关系的定义。数据结构：Complex=(C,R)。其中，C是两个实数集合c1,c2；
12、R是定义在C上的一种关系，即R=P=。其中，序偶中的c1表示复数的实部，c2表示复数的虚部。例1-5 事务管理程序中的课题小组信息的数据结构。假设1位老师带13名研究生，1位研究生带12位学生，则数据结构如下：Group=(P,R)。其中，P=T,G1,Gn,S11,Snm,1=n=3, 1= m=2 R=R1, R2 R1=|1=i=n,1=n=3 R2=|1=i=n, 1=j=m, 1=n=3, 1=m=21-2-3 其它概念与术语(1) 逻辑结构(Logical Structure)-描述数据元素之间的逻辑关系的结构。(2) 物理结构(Physical Structure)-描述数据元素
13、在计算机中的实际存储映射关系的结构，又称存储结构。存储结构一般包含两个部分的内容：一是数据元素的存储，二是数据元素之间关系的存储。(3) 容量单位问题Byte, bit, KB, MB, GB, TB(4) 数据域(Data Field)-当数据元素由若干个数据项组成时，各数据项位串被称为数据域。(5) 数据节点(Node)-数据元素。(6) 数据元素之间关系的两种映射方法顺序映射-顺序存储结构。借助元素在存储器中存储的相对位置关系来表示数据元素之间的逻辑关系。非顺序映射-链式存储结构。借助指示元素存储地址的指针来表示元素之间的逻辑关系。注：数据的逻辑结构与物理结构是紧密相关的。一般来讲，任何
14、一个算法的设计取决于其数据的逻辑结构，而算法的实现取决于其数据的存储结构。(7) 虚拟存储结构-存储结构的基于高级程序设计语言的描述方法 虚拟存储结构C语言OSHardwareDS 物理存储结构图1-3 数据结构的虚拟存储结构的系统层次定位通过高级语言的数据类型来描述。例如：一维数组用于描述顺序存储结构；指针用于描述链式存储结构；struct, union等用来表示复杂问题的数据结构。DS中的虚拟存储结构在计算机系统中的层次位置如图1-3所示。(8) 数据类型(Data Type)-用于刻画程序中的操作对象之值的集合及定义在其上的一组相应操作的抽象总称。注1：每个变量、常量或表达式都有一个属于它的数据类型。显式地或者隐含地规定了变量等在程序执行期间的所有可能取值，及其上允许的一组操作。注2：数据类型一般分为原子类型(Atom Data Type)和结构类型(Structure Data Type)。前者即基本数据类型，后者即复杂结构类型。注3：数据类型的作用：从硬件的角度，它是解释计算机内存信息含义的手段；从用户的角度，它实现的信息的隐藏，将用户不必了解的细节隐藏了起来。(9) 抽象数据类型(Abstract Data Type)-一个数学模型及定义在其上的一组操作。注1：其定义仅取决于其逻辑结构特性，与机器内部的表示与实现无关。只要其数学特性不变，则其外部的使用将不受
