大一下-普通班银湖师兄数据结构第1章绪论hsh

1、1数据结构(C语言版) 严蔚敏、 吴伟民 清华大学出版社数据结构题集(C语言版) 严蔚敏、吴伟民、 米宁 清华大学出版社本课程的上机作业题目参考此书C程序设计（第四版），著，：。C程序设计（第四版）学习辅导，著，：常用C语言用法速查手册，常用C语言用法速查手册编写组编著，：龙门书局，1995年第1版2。参考书 教材数据结构侯识华(Hou Shi-hua)号: 168494498名: 2013d2教学内容总学时：48学时 ( 其中上机学时：10学时 )第1章绪论6第2章线性表8第3章栈和队列6第6章树和二叉树6第7章图4第9章查找4第10章 内部排序4 合计:38学时43单选题20道题，每题1.

2、5分，共30分主要考查基本概念填空题14或16分，每空2分，主要考查基本概念简答题考典型数据结构的遍历方法、存储结构或典型算法的输出结果20或24分算法分析题20分左右，给定若干个算法代码，要求添加注释，并写出算法功能算法描述题15分左右，2个典型算法，要求给出算法思想和具体实现步骤。6考试题型实验及平时成绩（考勤、上机、课堂、作业）占30%期末闭卷考试成绩占70%认真完成上机作业：B7-238上机时间:第5、7、9、11、13、15周的星期五（第1、2节）加强复习和编程练习上网查询5上机地点:注意事项考核方式4数据结构是一门1.1数据结构什么学科?计算机已深入到社会生活的各个领域，其应用已不

3、再仅仅局限于科学计算，而 地是用于控制，管理及数据处理等非数值计算领域。一般来讲，用计算机解决一个具体问题时，大致需要下列几个步骤：首先从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序、进试、调整直至得到最终。第一章绪论本章主要内容：数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析5特点：每一本书的书目信息占据一行，所有书的书目信息按登录号顺序依次排列构成一张表格（书目文件）；表中一本书的书目信息依据登录号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入、更新、删除、按条件检索某一本书的书目信息等等。由这四张表构成的文件便是书

4、目自动检索的数学模型，计算机的主要操作便是按照某个特定要求对书目文件进行查询。在这类文档管理的数学模型中，计算机处理的对象之间存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。10例1-1 图书馆的书目检索系统自动化问题按登录号编排按书名编排按作者编排按分类编排001,L002,003,S001,003,书004,图1.1目录文件示例高等数学001，003理论力学002,线性代数004,001高等数学S01002理论力学L01003高等数学S01004线性代数书S02.6计算机之所以能与人对弈是因为有人将对弈的规则和策略事先已存入计算机。对弈的过程是在一定规则下随机进行的，所以

5、就必须对对弈过程中所有可能发生的情况及 相应的策略都考虑周全，并且好的棋手在对弈时不仅要看棋盘当时的状态，还应能预测棋局发展的趋势，甚至最后结局。计算机操作的对象是对弈过程中可能出现的棋盘状态称为格局。格局之间的关系不是线性的，因为一个格局可派生出几个格局。从对弈开始到结束的过程中所有可能出现的格局构成一棵倒长的树。树根是对弈之前的的格局，叶子是可能出现的结局，对弈的过程就是从树根沿树叉到某个叶子的过程。树是某些非数值计算问题的数学模型，也是一种数据结构。模型：? 棋盘及棋盘的格局算法：? 对弈的规则和策略12例1-2 计算机和人对弈问题（井字棋） P.2.11.。7这类交通和道路问题的数学模

6、型是一种称为图的数据结构。圆圈表示一条通路，圆圈之间的连线表示两个圆圈表示的两条通路不能同时通行。设置交通灯的问题等价为对图的顶点的染色问题，要 求对图上的每个顶点染一种颜色，并且要求有线相连的两 个顶点不能具有相同颜色，而总的颜色种类应尽可能的少。 综上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构数据结构是研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作(例如：对数据进行查找,插入,删除,合并,排序,统计以及简单计算)等的一门学科。例1-3 多叉路口交通灯的管理问题（五叉路口）CABACADDBBABCBDEDADBDCA

7、EAEBECED模型：?各种图算法：?通路之间相互矛盾的关系8数据结构的研究不仅涉及计算机硬件的研究范围，而且和软件的研究有更密切的关系，无论编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题（由于数据必须在计算机中进行处理，因此，不仅考虑数据本身的数学性质，还需考虑数据的存储结构）。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序，操作系统，数据库系统及其他系统程序和大型应用程序的重要基

8、础。16数据结构的发展历史数据结构作为一门独立课程在国外是从1968年才开始设立的。1968年美国唐欧 教授开创了数据结构的最初体系。从20世纪70年代中期到80年代初，各种版本的数据结构著作就相继出现。认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。未来发展的两个方向：面向各专门领域中特殊问题的数据结构;从抽象数据类型的观点来讨论数据结构。9数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如:整数数据对象是集合N= 0, 1, 2, 字母字符数据对象是集合C=A，B，Z1.2 基本概念和术语数据（data)所有能输入到计算机中，且能被

9、计算机程序处理的符号的总称。如: 整数，实数，字符串等都是数据。数据元素（data element）是数据（集合）中的一个“”，是数据结构中的基本。可由若干个数据项组成。数据项（data item）：是数据结构中的最小。例如： 描述一个运动员的数据元素可以是:称之为组合数据项名称出生日期参加日期职务业绩年月日10根据数据元间关系的不同特性，数据的逻辑结构通常有下列四类基本结构:数据元素线性结构一个对一个，如 线性表、栈、队列树形结构一个对多个图状结构多个对多个集合结构数据元间除“同属于一个集合”外，不存在其它关系数据结构（data structure) ：是带结构的数据元素的集合。是相互之间存

10、在一种或多种特定关系的数据元素的集合。是相互之间存在着某种逻辑关系的数据元素的集合。是一组具有相同结构的值。P7数据元间的关系称为结构。数据元间不同的逻辑关系不同的“结构”。11例1-5 为课题小组设计一个数据结构。假设每个小组由1位教师、1-3名 及1-6名本科生组成，小组成员之间的关系是：教师指导 ，而由每位研究生指导一至两名本科生。则可如下定义数据结构： Group=(P, R)其中：P=T, G1,Gn, S11Snm 1n3，1m2 R=R1, R2R1=|1in, 1n3R2=|1in, 1jm, 1n3, 1m222数据结构的形式定义为:数据结构是一个二元组:Data_Struc

11、tures = (D, S)其中: D 是数据元素的有限集 S 是 D上关系的有限集下面举两个简单例子说明之:例1-4 复数可取如下定义：复数是一种数据结构Complex=(C, R)其中：C是含两个实数的集合c1,c2；R=P，而P是定义在集合C上的一种关系。有序偶表示c1是复数的实部，c2是复数的虚部12数据的物理结构又称为数据的结构是数据的逻辑结构用计算机语言的实现，依赖于计算机语言。是数据的逻辑结构在计算机中的表示（又称映像），指的是数据元素及其关系在计算机器中的表 示，它包括数据元素的表示和关系的表示。注意：逻辑上相邻的数据元素，在物理上未必相邻。24数据的逻辑结构上述数据结构的定义

12、仅仅是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元间的逻辑关系，因此又称为数据的逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，是从操作对象抽象出来的数学模型，与数据的 无关，是独立于计算机的。数据的逻辑结构的目的是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它。2313数据的存储结构数据元素之间的关系在计算机存储器中的表示有两种不同的表示方法：顺序表示和非顺序表示。 由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构的特点：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构关系)。链式存储结构的特点：在每一个数据元素中增加一个 (

13、存放另一个元素地址的)指针来表示数据元素之间的逻辑关系。26数据的存储结构数据元素在计算机存储器中的表示(在计算机中的映象)例如：用二进制位(bit)的位串表示数据元素整型数据元素 (321)10 =(00000000101000001)2字符型数据元素A = (001000001)2数据元素或结点是数据元素在计算机存储器中的表示14数据的逻辑结构与数据的存储结构密切相关。任何一个算法的设计取决于选定的数据的逻辑结 构，而算法的实现依赖于采用的存储结构。在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的 “数据类型” 描述存储结构。数据

14、元素地址数据元素地址Z1=3.0-2.3iZ2= - 0.7+4.8iZ1=3.0-2.3i顺序存储结构链式存储 结构复数存储结构示意图270415041515数据类型（da ype） P7在用高级程序语言编写程序中，必须对程序中出现的每个变量、常量或表达式，明确说明各自所属的确定的数据类型。数据类型规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上所允许进行的操作。方式不同数据类型的变量，其所能取的值的范围不同，所能进行的操作不同。第1次课完!【2014-02-27】2916结构类型。该类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是结构的，也可以是

15、非结构的。例如数组类型数据的值是由若干分量组成，每个分量可以是整数，也可以是数组等；在某种意义上结构类型（带结构的数据类型）可以看成是由一种数据结构和定义在其上的(即在这些带相同结构值上的)一组操作组成。在程序设计语言中，每一个数据都属于某种数据类型。数据类型规定数据的取值范围, 存储方式以及允许进行的操作。带结构的数据类型都对应着32特定的数据结构数据类型的分类按“值”的不同特性，高级程序语言中的数据类型可分为两类：原子类型和结构类型。原子类型。该类型的值是不可分解的。例如C语言中的基本类型（整型、实型、字符型和枚举类型），指针类型和空类型。因此，(原子)数据类型是一个值的集合和定义在这个值

16、集合上的一组操作的总称。例如：C语言的 型变量，其值集合为某个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。3117抽象数据类型 (Abstract Data Type 简称ADT)是指一个特定的数学模型以及定义在此数学模型上的一组操作。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象(即：性质相同的数据元素的集合)； S 是D 上的关系集；P 是对D 的基本操作集。本书采用以下格式定义抽象数据类型ADT 抽象数据类型名 数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT 抽象数据类型名P7抽象数据类型和数据

17、类型实质上是一个概念。高级程序设计语言中提供的数据类型，其操作需通过编译器或解释器转化成低层，即汇编语言或机器语言的数据类型(位,字节等)来实现。P7 引入“数据类型”的目的，从硬件的角度看，是作为解释计算机内存中信息含义的一种手段，而对使用数据类型的用户的角度来说，实现了信息的隐 蔽，即将一切用户不必了解的细节都封装在“数据类型”中。例如：用户在使用C语言的 类型时，既不需要了解 类型数据在计算机 是如何表示的，也不需要知道操作是如何实现的。如：“两整数求和”，程序设计者只需要注重其“数学上求和”的抽象特性，而不需要了解其硬件的“位”操作如何33进行。18引用运算符 & （C+语言的重要内容

18、之一）通过用一个目标对象(一个变量名)对作初始化来定义引用，从而让 和目标对象建立起联系。对 的操作就是对目标对象的操作。函数调用时，通过参数传递，此时对引用初始化。对 的操作实际上就是对其 的目标对象的操作，计算机不再为引用分配存储空间。变量的引用类型和非引用类型的区别分析#include void f1(int a) a=5;prf(f1 a=%dn , a); void f2(int &a) a=5;prf(f2 a=%dn, a); void main()x=10;f1(x);prf( x=%dn, x);f2(x);/根据定义, a为，在函数中改变a的值，实际就是改变x的值 prf(

19、 x=%dn, x);其中, 基本操作的定义格式为:基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述赋值参数引用参数只为操作提供输入值。以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。19Put(&T, i, e)初始条件：三元组已存在，i操作结果：改变的第i元的值为eIsAscending(T)初始条件：三元组已存在操作结果：如果的个元素按升序排列，则返回，否则返回IsDescending(T

20、)初始条件：三元组已存在操作结果：如果的个元素按降序排列，则返回，否则返回Max(T, &e)初始条件：三元组已存在操作结果：用e返回的个元素中的最大值Min(T, &e)初始条件：三元组已存在操作结果：用e返回的个元素中的最小值ADT Triplet例1-6 抽象数据类型三元组的定义：ADT Triplet 数据对象：D= e1,e2,e3|e1,e2,e3ElemSet (定义了关系运算的某个集合)数据关系：R1=,基本操作：InitTriplet(&T, v1, v2, v3)操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数 v1，v2 和 v3 的值。DestroyTrip

21、let( &T)操作结果：三元组T被销毁。Get(T, i, &e)初始条件：三元组已存在，1=i=1void main() Triplet T;void main()Status i; i=InitTriplet(T,调用InitTriplet()将T的值初始化,有确定值T0=v1*T= *(T+0)=v15,7,9);T1=v2*(T+1)=v2给T分配内存单元TTT2=v3*(T+2)=v3通过调用初始化函数 InitTriplet, 使T指向了动态分配的内存连续块(数据结构的储存表示), T0, T1,T2构成了数据结构，该存储结构准确表示了数据结构的数据对象和数据关系。typedef

22、 typedefElemType; Sus;/ 基本操作的实现 (函数定义)Status InitTriplet ( Triplet &T, ElemType v1, ElemType v2, ElemType v3) T=(ElemType *) malloc(3 *sizeof (ElemType );/分配三个元素的存储空间void main() Triplet T; Status i;i=InitTriplet(T, 5, 7, 9); 25Ttypedef ElemType *Triplet;Triplet T;未初始化,调用InitTrip et()将T的值初始化,有确定值26St

23、atus DestroyTriplet ( Triplet &T) /销毁三元组T。free ( T );T = NULL;return OK;Get (T , i , m) / InitTripletm= &eStatus Get ( Triplet T , int i , ElemType &e) /1=i=3, 用e返回的第i元的值 if ( i3 ) return ERROR;e = Ti-1;return OK; / GettypedefElemType; typedefSus;void main() Triplet T; ElemType m; Status i;i=InitTri

24、plet(T, 5, 7, 9);第2次课完!【2014-02-28】5127Status Max (Triplet T, ElemType &e)/ 用e返回的个元素中的最大值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1=T2)? T1 :T2);return OK; / MaxStatus Min (Triplet T, ElemType &e)/ 用e返回的个元素中的最小值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1=T2)? T1 :T2);return OK; / MinStatus Put (Triplet &T , int

25、i , ElemType e)/1=i=3, 置的第i元的值为e if ( i3 ) return ERROR; Ti-1 = e;return OK; / PutStatus IsAscending (Triplet T) / 如果的个元素按升序排列，则返回，否则返回 return ( T0 =T1)& T1 =T1)& T1 =T2); / IsDescending28有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何

26、条件下，算法都 只有一条执行路径，不允许有二义性。相同的输入只能得出相同的输出。算法和算法分析算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法必须具有以下五个重要特性：有穷性确定性可行性输入输出291.4.2 算法设计的要求设计算法时，通常应考虑达到以下目标： 1正确性可读性健壮性高效率与低量需求可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出 一个算法有零个或多个的输出，这些输出是同输入有着某些特定关系的量。它是一组与输入有确定

27、关系的量值，是算法进行信息加工后得到的结 果，这种确定关系即为算法的功能。30可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行。因此，算法应该易于人的理解，晦涩难读的程序易于隐藏较多错误，难以调试和修改。健壮性当输入的数据非法时，算法应当恰当地作出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而 应是返回一个表示错误或错误性质的值(例如， 输入出错)，以便在更高的抽象层次上进行处理。 4高效率与低存储量需求通常，效率指的是算法执行时间；存储量需求指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。正确性算法应当满足具体问题的需

28、求。 (通常一个大型问题的需求，要以特定的规格说明方式给出，而一般问题目前用自然语言描述需求。至少应当包括：对于 输入、输出和加工处理等问题的明确的无歧义性的描 述)对算法是否“正确”的理解可以有以下四个层次：程序不含语法错误；程序对于几组输入数据能够得出满足要求的结果； c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足规格说明要求的结果； d程序对于一切合法的输入数据都能得出满足规格说明要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。31撇开与计算机硬件、软件有关的因素，可以认为一个特定算法 “运行工作量”的大小，只依赖于问题的规模 （通常用整数

29、量n表示），或者说，它是问题规模的函数。运行工作量通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其增长的趋势为准则。一个算法是由控制结构(顺序、分支、和循环3种) 和原操作(指固有数据类型的操作)构成的，算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。62算法效率的度量算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。度量一个程序的执行时间通常有两种方法:事后统计法 P.14缺点：1必须先执行程序； 2依赖于计算

30、机的硬件、软件等环境因素容易掩盖算法本身的优劣。事前分析估算的放法 一个用高级程序语言编写的程序在计算机上运行时所消耗时间取决于下列因素：算法选用的策略问题的规模 (例如，求100以内还是1000以内的素数)编写程序的语言编译程序所产生的机器代码的质量计算机执行指令的速度32例如：两个nn矩阵相乘的算法基本操作: 乘法操作时间复杂度: T(n)= O(n3) 整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比(渐近) 。void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为a 和b 的乘积 for (i=1; i=n; +i)for (

31、j=1; j=n; +j) cij = 0;for (k=1; k=n; +k) cij += aik*bkj; /for /mult一般情况下，算法中基本操作重复执行的次数是关于 问题规模 n 的函数f(n)。随着问题规模 n 的增长，算法执行时间的增长率和f(n)的增长率相同。算法的(渐近)时间复杂度 ( 也称作:算法的时间度量)记作T(n) ，则有：T(n) = O(f(n)它表示随问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同。亦即T(n) = O(f(n)它表示存在一个正的常数M，使得当n n0时，有：Tn M fn关键是：求 f(n) 的具体表达式- 算法中基

32、本操作重复执行的次数是关于问题规模 n 的函数f(n)33例如: 程序段： for (i=1; i=n; +i)for (j=1; j=n; +j) +x; s+=x; 含有基本操作“x自增1”的语句的频度为n2，即时间复杂度为(n2)，即平方阶。一般情况下，对一个问题(或一类算法)只需选择一种 基本操作来算法的时间复杂度即可。在难以精确计算基本操作执行次数(或语句频度)的情况下，只需要求出它关于n的增长率或阶即可。66 被称作问题的基本操作的原操作应该是其重复执行的次数与算法的执行时间成正比的原操作，多数情况下它是最循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。语句的频度(frequency count)指的是该语句重复执行的次数。例如: 程序段： +x; s=0; 含有基本操作“x自增1”的语句的频度为1，即时间复杂度为(1)，即常量阶。例如: 程序段： for (i=1; i=n; +i) +x; s+=x; 含有基本操作“x自增1”的语句的频度为n，即时间复杂度为(n)，即线性阶。6534随