数据结构(C语言描述)

1、数据结构（c+语言描述）教学演示文稿数据结构课程要研究的主要问题：数据结构课程要研究的主要问题： 现实世界中的实际问题必须经过抽象，得出反映实际事物本质的数据表示后，才能被计算机处理。 如何用计算机所能接受的形式来描述这些数据，如何将这些数据以及它们之间的关系存储在计算机中，以及如何用有效的方法去处理这些数据，是数据结构课程要研究的主要内容。 2.1 基本概念基本概念2.1.1 数据、数据元素、数据对象数据、数据元素、数据对象2.1.2 数据结构数据结构2.1.1 数据、数据元素、数据对象n数据数据 (data) 是对客观事物的符号表示，是对现是对客观事物的符号表示，是对现实世界的事物采用计算

2、机能够识别、存储和处实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。理的形式进行描述的符号的集合。n例如：科学计算软件处理的是数值数据；文字例如：科学计算软件处理的是数值数据；文字处理软件处理的是字符数据；多媒体软件处理处理软件处理的是字符数据；多媒体软件处理的是图象、声音等多媒体数据。的是图象、声音等多媒体数据。n数据元素数据元素 (data element) 是数据的基本是数据的基本单位，也称结点，在一个计算机程序中单位，也称结点，在一个计算机程序中通常作为一个整体进行考虑和处理。数通常作为一个整体进行考虑和处理。数据元素也称据元素也称结点结点。2.1.1 数据、数据

3、元素、数据对象数据、数据元素、数据对象n一个数据元素可以由若干个一个数据元素可以由若干个数据项数据项 (data item) 组成。组成。数据项包括两种：数据项包括两种：初等项初等项（是数据不可分割的最小单（是数据不可分割的最小单位）、位）、组合项组合项（由若干个数据项组成）。（由若干个数据项组成）。n在数据库语言中，数据项称为在数据库语言中，数据项称为“字段字段”，而数据元素，而数据元素称为称为“记录记录”。n数据对象数据对象 (data object) 是性质相同的数据元素的集合，是性质相同的数据元素的集合，是数据的一个子集。例如整数对象、实数对象、字符是数据的一个子集。例如整数对象、实数

4、对象、字符对象等。对象等。姓名姓名性别性别年龄年龄籍贯籍贯班别班别 成成 绩绩数学数学物理物理化学化学外语外语张三张三 女女 18北京北京 6003 80 90 70 75李四李四 男男 20上海上海6001 75 80 90 80王五王五 男男 19长沙长沙6002 85 80 75 90 表表2-1 学生情况表学生情况表一个数据元素一个数据元素一个初等数据项一个初等数据项一个组合数据项一个组合数据项整张表就是一个数据对象，其中每个学生的情况是其整张表就是一个数据对象，其中每个学生的情况是其中的一个数据元素。中的一个数据元素。2.1.2 数据结数据结构构n从数学意义上讲，数据结构从数学意义上

5、讲，数据结构是指数据的组织形是指数据的组织形式，由数据对象及该对象中数据元素之间的关式，由数据对象及该对象中数据元素之间的关系组成。数据结构可描述为一个二元组系组成。数据结构可描述为一个二元组ndata-structure=（d，r） 其中：其中：d是数据对象，为数据元素的有限集；是数据对象，为数据元素的有限集；r是该对象中数据元素之间关系的有限集。是该对象中数据元素之间关系的有限集。n这种意义上的数据结构称为数据的逻辑结构。这种意义上的数据结构称为数据的逻辑结构。除此之外，要将数据放在计算机内进行处理，除此之外，要将数据放在计算机内进行处理，还将涉及数据的存储结构。还将涉及数据的存储结构。2

6、.1.2 数据结构数据结构n涉及到涉及到计算机的数据结构计算机的数据结构概念，至今尚未有一个公认概念，至今尚未有一个公认的标准定义，但一般认为应包括以下三个方面：的标准定义，但一般认为应包括以下三个方面：（1）数据元素与数据元素之间的逻辑关系，也称为数据）数据元素与数据元素之间的逻辑关系，也称为数据的的逻辑结构逻辑结构，它独立于计算机；，它独立于计算机；（2）数据元素与数据元素之间的关系在计算机中的存储）数据元素与数据元素之间的关系在计算机中的存储表示，也称为数据的表示，也称为数据的存储结构或物理结构存储结构或物理结构，它依赖于，它依赖于计算机；计算机；（3）数据的）数据的运算运算，即对数据施

7、加的操作。，即对数据施加的操作。2.2 数据结构的分类：逻辑结构数据结构的分类：逻辑结构n如果一个数据结构中的两个结点如果一个数据结构中的两个结点k、k之间存在的关系之间存在的关系可用有序对可用有序对 表示，则称表示，则称 k是是 k的的后继后继，k是是k的的前驱前驱，k和和k互为互为相邻结点相邻结点。如果。如果k没有后继，则没有后继，则k称为称为终端结点终端结点。如果。如果k没有前驱，则称没有前驱，则称k为为开始结点开始结点。如果如果k既不是终端结点，也不是开始结点，则称既不是终端结点，也不是开始结点，则称k为为内内部结点部结点。n数据的数据的逻辑结构逻辑结构分为分为线性结构线性结构和和非线

8、性结构非线性结构两大类。两大类。非线性结构又分为非线性结构又分为树型结构树型结构和和图状结构图状结构。线性结构线性结构n 线性结构有且仅有一个开始结点和一个终端结点，并且所有的结点最线性结构有且仅有一个开始结点和一个终端结点，并且所有的结点最多只有一个前驱和一个后继。线性表是典型的线性结构。多只有一个前驱和一个后继。线性表是典型的线性结构。 线性表线性表n一个学校所有学生的各种特征可用以下表格来记录：一个学校所有学生的各种特征可用以下表格来记录：n学号学号姓名姓名 性别性别 出生年月出生年月 系系班级班级n030401张三张三男男1985.1计算机计算机 0304n030402李四李四女女19

9、84.12 计算机计算机 0304n030403王五王五男男1984.6计算机计算机 0304n030404赵六赵六男男1985.4计算机计算机 0304nn该表为一个数据结构，其中列称为该表为一个数据结构，其中列称为“字段字段”，行称为，行称为“记录记录”，记录之，记录之间有间有一对一一对一的线性关系，称为的线性关系，称为“线性结构线性结构”。 树状结构树状结构n树状结构中，一个结点最多只有一个前驱，而可以有多个树状结构中，一个结点最多只有一个前驱，而可以有多个后继。它是最重要的非线性结构。后继。它是最重要的非线性结构。n一个学校的组织机构可用以下数据结构来表示：一个学校的组织机构可用以下数

10、据结构来表示：n该数据结构的该数据结构的“结点结点”具有具有一对多一对多的逻辑关系，就象一棵的逻辑关系，就象一棵倒挂的树，故称为倒挂的树，故称为“树状结构树状结构”。学校学校保险系保险系金融系金融系会计系会计系计算机系计算机系基础教研室基础教研室电子商务教研室电子商务教研室教师甲教师甲教师乙教师乙教师丙教师丙. . . 图状结构图状结构n图状结构中，对结点的前驱和后继的个数没有限制，结点图状结构中，对结点的前驱和后继的个数没有限制，结点之间的关系是任意的。它是最一般的非线性结构。之间的关系是任意的。它是最一般的非线性结构。n在在 n 个城市间建立通信网络，要求在任意两个城市之间个城市间建立通信

11、网络，要求在任意两个城市之间都有直接或间接的通信线路，该通信线路可用以下图形来都有直接或间接的通信线路，该通信线路可用以下图形来表示：表示：n如果每个城市为一个结点，则结点之间的逻辑结构称为如果每个城市为一个结点，则结点之间的逻辑结构称为 “图状结构图状结构”，它是一种，它是一种多对多多对多的数据结构。的数据结构。abcdefg2.2 数据结构的分类：存储结构数据结构的分类：存储结构n数据的数据的存储结构存储结构（又称（又称物理结构物理结构）取决于四种基本的存储）取决于四种基本的存储方法：方法：顺序存储、链接存储、索引存储、散列存储顺序存储、链接存储、索引存储、散列存储。n顺序存储顺序存储是把

12、逻辑上相邻的结点存储在物理位置相邻的存是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。结点之间的逻辑关系用存储单元的邻接关系来储单元里。结点之间的逻辑关系用存储单元的邻接关系来体现。体现。n链接存储链接存储对逻辑上相邻的结点不要求在存储的物理位置上对逻辑上相邻的结点不要求在存储的物理位置上相邻，结点之间的逻辑关系由附加的指针来表示。相邻，结点之间的逻辑关系由附加的指针来表示。n索引存储索引存储是在存储结点数据的同时，还建立附加的索引表。是在存储结点数据的同时，还建立附加的索引表。索引表的每一项称为索引项。一般情况下索引项由关键字索引表的每一项称为索引项。一般情况下索引项由关键字和地址组成。

13、和地址组成。n散列存储散列存储是根据结点的关键字计算出该结点的存储地址。是根据结点的关键字计算出该结点的存储地址。n同一种逻辑结构采用不同的存储方法，可以得到不同的存同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。一种逻辑结构可采用一种方法存储，也可采用多储结构。一种逻辑结构可采用一种方法存储，也可采用多种方法组合起来进行存储。种方法组合起来进行存储。图图2.2 基本存储方基本存储方法法 k1 k2 k3 k4 k510011002100310041005 k2 1007 k1 1001 k5 k4 1004 k3 10051001100210031004100510061007ke

14、y11001key21005key31003key41002key51004 k1 k4 k3 k5 k21001100210031004100520012002200320042005 k2 k5 k1 k4 k3d2d5d1d4d3di=h(keyi)(a) 顺序存储顺序存储(b) 链接存储链接存储(c) 索引存储索引存储(d) 散列存储散列存储2.3 抽象数据类型抽象数据类型n2.3.1 两种软件设计方法两种软件设计方法n2.3.2 数据类型数据类型n2.3.3 抽象数据类型抽象数据类型2.3.1 两种软件设计方法两种软件设计方法n面向过程的程序设计：是传统的设计方法，它把软件面向过程的

15、程序设计：是传统的设计方法，它把软件看成一个处理过程，将软件分解成为若干个表示过程看成一个处理过程，将软件分解成为若干个表示过程步骤的模块，然后由编程语言的构件（子程序和函数）步骤的模块，然后由编程语言的构件（子程序和函数）来实现。来实现。n面向对象的程序设计：将软件看成由数据对象组成的面向对象的程序设计：将软件看成由数据对象组成的集合，这些对象是应用问题所涉及的物理实体的数据集合，这些对象是应用问题所涉及的物理实体的数据模型，它们之间的相互作用构成了一个软件系统。模型，它们之间的相互作用构成了一个软件系统。n面向对象的软件设计方法优于传统的软件设计方法，面向对象的软件设计方法优于传统的软件设

16、计方法，因为面向对象的软件设计方法采用了抽象数据类型的因为面向对象的软件设计方法采用了抽象数据类型的描述方式，实现了数据抽象和信息隐蔽。描述方式，实现了数据抽象和信息隐蔽。2.3.2 数据类型数据类型n数据类型数据类型 (data type) 是一组性质相同的值的集合以及定义在是一组性质相同的值的集合以及定义在这个集合上的一组操作的总称。这个集合上的一组操作的总称。n按值的不同特性，数据类型可以分为两类：按值的不同特性，数据类型可以分为两类：n(1) 基本类型：如整型、实型、字符型等，通常由程基本类型：如整型、实型、字符型等，通常由程 序语言直接提供。序语言直接提供。n(2) 组合类型：由一些

17、基本类型组合构造而成，如记组合类型：由一些基本类型组合构造而成，如记 录、数组、结构等，由用户借助程序录、数组、结构等，由用户借助程序 语言提供的描述机制自己定义。语言提供的描述机制自己定义。 2.3.3 抽象数据类型抽象数据类型n抽象抽象是指从特定的实例中抽取共同的性质以形成一般化是指从特定的实例中抽取共同的性质以形成一般化概念的过程。抽象是对某系统的简化描述，即强调该系概念的过程。抽象是对某系统的简化描述，即强调该系统中的某些特性，而忽略一部分细节。对系统进行的抽统中的某些特性，而忽略一部分细节。对系统进行的抽象描述称为对它的象描述称为对它的规范说明规范说明，对抽象的解释称为对它的，对抽象

18、的解释称为对它的实现实现。n数据抽象数据抽象是一种对数据和操作数据的算法的抽象。数据是一种对数据和操作数据的算法的抽象。数据抽象包含了抽象包含了模块化模块化和和信息隐蔽信息隐蔽两种抽象。模块化和信息两种抽象。模块化和信息隐蔽是面向对象方法的核心。隐蔽是面向对象方法的核心。2.3.3 抽象数据类型抽象数据类型n抽象数据类型抽象数据类型（abstract data type，简称，简称adt）是指）是指抽象数据的组织和与之相关的操作。可看做是数据的逻抽象数据的组织和与之相关的操作。可看做是数据的逻辑结构及在逻辑结构上定义的操作。辑结构及在逻辑结构上定义的操作。n在在c+中，用中，用类类的说明来表示

19、的说明来表示adt，用类的实现来实现，用类的实现来实现adt，c+中实现的类相当于数据的存储结构及其在存中实现的类相当于数据的存储结构及其在存储结构上实现的对数据的操作。储结构上实现的对数据的操作。adt和类的概念反映了和类的概念反映了软件设计的两次抽象：软件设计的两次抽象：adt相当于在概念层（抽象层）相当于在概念层（抽象层）上描述问题，而类相当于在实现上描述问题，而类相当于在实现 层上描述问题。层上描述问题。n封装的矩形数据和操作的抽象数据类型如下：封装的矩形数据和操作的抽象数据类型如下： adt rectangle data / 数据说明数据说明 非负实数，给出矩形的长和宽非负实数，给出

20、矩形的长和宽 operation / 操作说明操作说明 area / 操作操作1，求面积，求面积 input： 无无 preconditions： 无无 process： 计算矩形的面积计算矩形的面积 output： 返回面积值返回面积值 postconditions： 无无 perimeter /操作操作2，求周长，求周长 input： 无无 preconditions： 无无 process： 计算矩形的周长计算矩形的周长 output： 返回周长值返回周长值 postconditions：无：无 n封装的矩形数据和操作的抽象数据类型用封装的矩形数据和操作的抽象数据类型用c+中类（中类（c

21、lass）表示如下：）表示如下： class rectangle private : float length , width ; public : rectangle( float l , float w) ; float area(void) const ; float perimeter(void) const ; ; rectangle : rectangle(float l , float w ) : length(l) , width(w) float rectangle : area(void) const return length * width ; float rectan

22、gle : perimeter(void) const return 2.0*(length+width); 2.4 算法和算法分析算法和算法分析n2.4.1 算法概念算法概念n2.4.2 算法分析算法分析2.4.1 算法概念算法概念n算法是一个有穷的指令集，这些指令为解决某一特定算法是一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算系列。任务规定了一个运算系列。n一个算法应当具有以下的基本特性：一个算法应当具有以下的基本特性：n（1）输入）输入n（2）输出）输出n（3）确定性）确定性n（4）有穷性）有穷性n（5）可行性）可行性n算法的描述有多种方法，如自然语言方式、图形方式、算法的

23、描述有多种方法，如自然语言方式、图形方式、表格方式等。本教材采用表格方式等。本教材采用c+程序语言来描述算法。程序语言来描述算法。2.4.2 算法分析算法分析n人们常用以下几个标准来衡量一个算法的优劣：人们常用以下几个标准来衡量一个算法的优劣：n(1) 正确性正确性n(2) 可读性可读性n(3) 健壮性健壮性n(4) 时间效率和存储占用量时间效率和存储占用量1. 估计算法运行时间的方法估计算法运行时间的方法n基本考虑是：撇开所有与计算机硬件和软件有关基本考虑是：撇开所有与计算机硬件和软件有关的因素，只确定依赖于问题的的因素，只确定依赖于问题的“规模规模”(通常用通常用n表示表示) 和算法执行和

24、算法执行“基本操作基本操作”的次数。的次数。规模规模一一般指输入量的数目，如被排序元素的数目；般指输入量的数目，如被排序元素的数目；基本基本操作操作一般指定义在某个数据类型上的标准操作，一般指定义在某个数据类型上的标准操作，如整数相加、比较大小等。如整数相加、比较大小等。n一个算法是由控制结构一个算法是由控制结构 (顺序、选择、循环顺序、选择、循环) 和原和原操作操作 (加、减、乘、除等加、减、乘、除等) 构成的。算法的效率取构成的。算法的效率取决于二者的综合效果。一般以基本操作重复执行决于二者的综合效果。一般以基本操作重复执行的次数作为算法运行时间的度量。的次数作为算法运行时间的度量。2.

25、算法的时间复杂度算法的时间复杂度n一般情况下，算法中一般情况下，算法中“基本操作基本操作”重复执行的次数是问题重复执行的次数是问题规模规模 n 的某个函数的某个函数 f(n)，算法的时间度量记作，算法的时间度量记作n此式表示随时间规模此式表示随时间规模 n 的增大，算法执行时间的增长率与的增大，算法执行时间的增长率与 f(n) 的增长率相同，的增长率相同， 称为算法的时间复杂度。称为算法的时间复杂度。n由于算法的时间复杂度分析只考虑相对于问题规模由于算法的时间复杂度分析只考虑相对于问题规模 n 的增的增长率，因而在难以精确计算基本操作执行次数的情况下，长率，因而在难以精确计算基本操作执行次数的

26、情况下，只要求出它关于只要求出它关于 n 的增长率即可。我们可以在计算任何算的增长率即可。我们可以在计算任何算法运行时间代价时，忽略所有的常数和低次项，用法运行时间代价时，忽略所有的常数和低次项，用o表示表示法来表示算法的时间复杂度，它只是一个数量级概念。法来表示算法的时间复杂度，它只是一个数量级概念。 nfont nfo算法算法 2.2 计算两个计算两个nn矩阵的乘积矩阵的乘积nvoid matrixmultixmultiply ( int ann , int bnn , int cnn ) int i, j, k; for ( i=0; in; i+ ) / n+1次次 for ( j=0

27、; in; i+ ) /n(n+1)次次 c i j =0; /n2 次次 for ( k=0; k t(n) = o(n3)n定义：定义：t(n) = o(f(n) 当且仅当存在正整数当且仅当存在正整数 c和和 n0，对所有的，对所有的 n (nn0) 满足满足t(n)cf(n)。n换句话说，换句话说，o(f(n) 给出了函数给出了函数 f(n) 的上界。的上界。n由于上述定义中对所有由于上述定义中对所有 n(nn0)，只要，只要 n 比较大一般均比较大一般均成立，而我们考虑的算法的时间复杂度也主要是在问题成立，而我们考虑的算法的时间复杂度也主要是在问题规模规模 n 相当大时的情况。所以，在分析一个算法的时间相当大时的情况。所以，在分析一个算法的时间复杂度时，一般不考虑复杂度时，一般不考虑 n 为一个较小的数时为一个较小的数时 t(n)cf(n)不成立的情况。不成立的情况。n一般情况下，分析一个算法中基本语句执行次数及其与一般情况下，分析一个算法中基本语句执行次数及其与问题规模的关系，便可求出该算法的时间复杂度。问题规模的关系，便可求出该算法的时间复杂度。n有时，算法的时间复杂度不仅仅依赖于问题的规模，有时，算法的时间复杂度不仅仅依赖于问题的规模，