1、21世纪高等院校规划教材数据结构（C语言描述）ISDN 7-5084-3301-7斯庆巴拉斯庆巴拉 主编主编中国水利水电出版社中国水利水电出版社第一章第一章 学习数据结构课程学习数据结构课程的意义学习重点学习重点n掌握学习本课程的意义n掌握本课程的主体框架和讨论范围n掌握如何对算法进行描述和分析引入：引入：一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。n1.1 实例：高校选修课程管理实例：高校选修课程管理n1.2 数据结构的主要内容数据结构的主要内容n1.3 算法和算法分析算法和算法分析n本章总结本章总结
2、1.1 实例：高校选修课程管理实例：高校选修课程管理n1.1.1 问题描述问题描述n1.1.2 问题的分析问题的分析n1.1.3 学习本课程的意义学习本课程的意义1.1.1 问题描述问题描述 表1-1是一所学校学生选修课程的选修情况登记表。要求用计算机来完成对学生选修课程的全程管理。通常必备的功能有登记登记，修改修改、查查询询和打印打印等。在本例中重点完成查询功重点完成查询功能能。学号学号姓名姓名系别系别选修课程名选修课程名学学分分成绩成绩课程名课程名课程代码课程代码等级等级分数分数0351103王杰王杰计算机计算机摄影技术摄影技术5013 0351212李丽李丽计算机计算机电脑音乐电脑音乐5
3、021 0351220商立商立计算机计算机摄影技术摄影技术5013 0432233赵燕赵燕机械机械三维动画三维动画3032 0432118张欣张欣机械机械三维动画三维动画3032 0322140王芳王芳材料材料证券投资证券投资2053 表表1-1 某某学校学生选修课程情况登记表学校学生选修课程情况登记表 1.1.2 问题的分析问题的分析 利用计算机解决实际问题的步骤：利用计算机解决实际问题的步骤：n第一步：从具体问题抽象出一个适当的数据模型。n第二步：进行算法设计。n第三步：实现抽象数据类型定义，即从编程语言的角度确定抽象数据类型的存储形式和确定抽象数据类型中每一种操作的具体实现算法。n第四步
4、：编制相应的程序代码并进行调试。第一步：抽象数据模型一般包括三部分三部分：处理的数据对象、对象间的关系和需要实现的操作。常用以下格式描述：常用以下格式描述：ADT 选修课程 数据对象：数据对象：D=ai|ai记录类型，i=1,2,n,n0 数据关系：数据关系：R=Ri|Ri记录间关系，i=1,2,m,m0 基本操作：基本操作：DengjiList(&L)完成功能：对学生选修情况进行登记 EditList(&L)完成功能：对选修情况登记表进行修改 LocateList(&L,查询条件)完成功能：根据给定的查询条件，从登记表中查找满足条件的记录 PrintList(L)完成功能：打印学生选修情况登
5、记表 ADT选修课程第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算法描述算法描述。下面以查询操作为例给出伪代码表示：int LocateList(选修课程&L,查询条件)对给定的查询条件进行分析，确定是对表中哪个数据项进行查询；对表中元素按给定的查询条件进行查询；若查询成功，返回记录的位置；否则返回0值，表示表中不存在满足给定条件的记录；第三步：确定表中的记录的类型记录的类型（结构体），表在内存中存储方式存储方式（按输入顺序存放）。具体定义如下：struct kechengsrtuct/选修课程名类型定义选修课程名类型定义char *kechengming;/课程名int kec
6、hengdaima;/课程代码;struct chengjistruct /成绩类型定义成绩类型定义char *dengji;/成绩等级int fenshu;/分数;struct student /表中学生记录类型定义表中学生记录类型定义long int num;/学号char*name;/姓名char*xibie;/系别kechengstruct kechent;int xuefen;/学分chengjistruct chengji;表在内存中的存储类型定义：表在内存中的存储类型定义：struct sqlist student *A;/将记录顺序存放在一个一维数组中将记录顺序存放在一个一维数
7、组中int len;/表中记录的个数表中记录的个数;结论：结论：数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的操作对象操作对象以及它们之间的关系关系和运算运算操作操作的一门学科。1.1.3 学习本课程的意义学习本课程的意义 n数据结构作为一门独立的课程在国外是从1968年开始设立的。n瑞士著名计算机科学家N.Wirth提出的著名公式“程序程序=算法算法+数据结构数据结构”。n数据结构是一门介于数学、计算机硬件和软件三者之间的核心课程。n用一句话概括用一句话概括：本课程就是从实际问题抽象出数据类型的手段。主要研究计算机所处理的数据对象、对象间存在的关系及进行的各种操作。1.2 数据
8、结构的主要内容数据结构的主要内容 n1.2.1 基本概念和术语 n1.2.2 数据结构定义 n1.2.3 逻辑结构的表示方法 1.2.1 基本概念和术语基本概念和术语 n数据数据是对客观事物的符号表示，是一种信息的载体，是所有能输入到计算机中并被识别、存储和加以处理的信息的总称。n数据元素数据元素是数据的基本单位。一个数据元素也可以由若干个数据项数据项组成。n数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。n数据类型数据类型是对计算机中表示的数据对象、对象特征及该数据对象上的一组操作的描述。n抽象数据类型抽象数据类型是指一个数学模型及定义在该数学模型上的一组操作。定义取决于它的逻
9、辑特性，与其在计算机内部如何表示（存储）和实现无关。1.2.2 数据结构定义数据结构定义 n数据结构数据结构是指相互间存在一种或多种特定关系的数据元素的集合。数据数据具有相同属性的数据元素的集合；结构结构数据元素间存在的一种或多种关系。n对一个给定的数据结构进行分析时，一般从它的逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论。（本课程的主要讨论（本课程的主要讨论点）点）逻辑结构逻辑结构是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。通常按元素间存在的逻辑关系的不同按元素间存在的逻辑关系的不同特征特征，将数据结构分为四类分为
10、四类：集合结构集合结构 线性结构线性结构 树型结构树型结构 图型结构图型结构集合结构：集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。组成集合的数据组成集合的数据元素之间不存在任元素之间不存在任何的关系何的关系线性结构：线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号学号姓名姓名系别系别学分学分0351103王杰王杰计算机计算机30351212李丽李丽计算机计算机1例：例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一
11、条和最后一条以外，每条记录都只有唯一的前驱和后继元素。元素之间是元素之间是1 1：1 1关系，关系，都只有唯一的前驱和都只有唯一的前驱和唯一的后继唯一的后继树型结构：树型结构：数据元素之间存在“一对多一对多”逻辑关系的数据结构。例：例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业 学 院 数 学 系 计 算 机 系 外 语 系 应 用 专 业 网 络 专 业 软 件 专 业 教 师 学 生 元素之间的关系是元素之间的关系是1 1：n n，每个元素都只有每个元素都只有唯一的前驱元素，但唯一的前驱元素，但可以有多个后继元素可以有
12、多个后继元素图型结构：图型结构：数据元素之间存在“多对多多对多”逻辑关系的数据结构。例：例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。1 2 3 4 5 元素之间的关元素之间的关系是系是m:nm:n，每个每个元素都可以有元素都可以有多个前驱元素多个前驱元素和多个后继元和多个后继元素素 存储结构又称物理结构，存储结构又称物理结构，就是数据结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。根据存储空间的不同分配方式存储空间的不同分配方式将数据结构分为两类：顺序存储顺序存储 链式存储链式存储第一方面第二方面 顺序
13、存储：顺序存储：所有元素存放在一片连续的连续的存储空间中，逻辑上相邻的元素在内存中的物理逻辑上相邻的元素在内存中的物理位置也是相邻的位置也是相邻的。注意：注意：元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。例：对一个由例：对一个由（1 1，2 2，3 3，4 4，5 5）五个元素组）五个元素组成的数据结构采成的数据结构采用顺序存储，则用顺序存储，则内存中的存储示内存中的存储示意图如下所示：意图如下所示：元素1元素2元素3元素4元素5起始地址 链式存储：链式存储：所有元素存放在可以不连续可以不连续的存储单元中，以结点的形式结点的形式存在，每个结点除了保存数据元素信息外
14、，还通过指针来保存元通过指针来保存元素之间的关系素之间的关系。注意：注意：既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。元素1 元素4 元素3 元素2 例：对一个由（例：对一个由（1 1，2 2，3 3，4 4）四个元素组成）四个元素组成的数据结构采用链式的数据结构采用链式存储，则内存中的存存储，则内存中的存储示意图如下所示：储示意图如下所示：1.2.3 逻辑结构的表示方法逻辑结构的表示方法 n二元组表示法二元组表示法表示形式为：D=（K，R）其中，K=a1,a2,an ，为数据元素的集合 R=r1,r2,r m ，为元素之间关系的集合 r1=|其中，其中，x,yK
15、K 序偶表示：元素x和元素y之间存在关系，并且称元素元素x为元素为元素y的前驱的前驱，元素元素y为元素为元素x的后继的后继。如果元素x既是元素y的前驱，也是元素y的后继，既且，则用（x,y）形式表示。n图形表示法图形表示法 用圆圈圆圈来代表数据元素，用带箭带箭头的连线头的连线来表示元素之间的关系，如图所示。a b c d e 二元组表示法：二元组表示法：D1=(K,R)D1=(K,R)其中，其中，K=a,b,c,d,e K=a,b,c,d,e R=r R=r r=,r=,1.3 算法和算法分析算法和算法分析 n1.3.1 算法定义 n1.3.2 算法分析 1.3.1 算法定义算法定义 n算法算
16、法是对特定问题求解步骤的一种描述，是一组指令的有限序列，其中每一条指令都代表解题过程中的一个或者多个操作。n算法特点算法特点：有穷性、确定性、可行性、输入、输出n算法描述算法描述可以有多种方式，如：用流程图描述、用自然语言描述、还可用数学语言或特定的符号进行描述。本书中所有算法都是用用C语言语言来进行描述。1.3.2 算法分析算法分析 算法的设计要求算法的设计要求如下：正确性正确性 可读性可读性 健壮性健壮性 效率与低存储量的需求效率与低存储量的需求 其中，效率指的是算法执行的时间。存储量需求指的是算法执行过程中所需要的最大存储空间，通常主要考虑算法所需的辅助存储空间。这四个设计要求中最主要的
17、是算法的执执行时间行时间和执行时所占的存储空间所占的存储空间大小。算法的执行时间算法的执行时间是指一个算法在计算机上运行时所花费的时间。=简单操作所需要的时间 简单操作的次数影响算法执行时间的两个因素：影响算法执行时间的两个因素：（1）每个简单操作执行时所需时间与机器有关，而与算法无关。讨论算法中包含的算法中包含的简单操作的执行次数简单操作的执行次数。（2）另外一个与算法的执行时间相关的是问题的规模问题的规模。通常算法的执行时间用时间复杂度时间复杂度表示：T(n)=O(f(n)T(n)=O(f(n)其中，n n为问题的规模为问题的规模 T T（n n）为时间复杂度为时间复杂度 此式子表示，随着
18、问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。所以只要求出简单操作的次数关于要求出简单操作的次数关于n n的增长的增长率即可，然后用率即可，然后用n n的最高数量级来表示算法的最高数量级来表示算法的时间复杂度的时间复杂度。例：例：for(j=1;j=n;j+)for(k=1;k=m;k+)+x;s+=x;分析：分析：各个简单操作的执行次数如下所示：for(j=1;j=n;j+)/次数为次数为1+（n+1）+nfor(k=1;k=n;k+)/执行次数为（执行次数为（1+（n+1）+n）n+x;/执行次数为执行次数为n*n s+=x;/执行次数为执行次数为n*n 简单操作的执行次数
19、之和为：4n2+4n+2，用用n n的最高数量级表示的最高数量级表示，时间复杂度为：O O（n n2）。衡量一个算法性能的另一个标准就是算法执行算法执行时所占的存储空间的大小时所占的存储空间的大小。一般一个算法所占的存储空间包括存储算法所占用的存储空间、算法的输入/输出数据所占用的存储空间和程序运行过程中临时占用的存储空间这三个方面。其中，只有算法执行过程中所占的临时空间与算法有着密切关系。通常一个算法在执行过程中所占用的临时存储空间的大小由空间复杂度来衡量，空间复杂度来衡量，记作：S（n n）=O=O（f f（n n）其中，n n为问题的规模为问题的规模；S S（n n）为空间复杂度为空间复
20、杂度。通常用n的最高数量级来表示。本章总结：本章总结：n本章介绍了学习数据结构课程的意义、本课程的主题框架及相关内容和如何对算法进行评价。n 数据结构主要研究计算机所处理的数据对象、研究计算机所处理的数据对象、对象之间存在的各种关系及进行的各种操作对象之间存在的各种关系及进行的各种操作，是用计算机来解决实际问题与编写相应程序两者之间的纽带。n数据结构从定义上可以理解为数据+结构。其中，数据指的是所要处理的若干个数据元素的数据指的是所要处理的若干个数据元素的集合集合；结构指的是数据元素之间的关系结构指的是数据元素之间的关系。按逻辑结构可分为集合结构、线性结构、树型结构和图型结构四种。按存储结构可分为顺序存储和链式存储两种。算法算法是解决问题步骤的一种描述，它有有有穷性、确定性、可行性、输入和输出穷性、确定性、可行性、输入和输出等五个特点。一个好的算法应该满足正确性、可读性、正确性、可读性、健壮性和效率与低存储量需求健壮性和效率与低存储量需求等四个要求，其中算法的执行效率和低存储量需求是衡量一个算法的最主要的标准。通常用时间复杂度来衡用时间复杂度来衡量算法的执行时间，用空间复杂度来衡量算法量算法的执行时间，用空间复杂度来衡量算法执行过程中所占用的临时存储空间的大小执行过程中所占用的临时存储空间的大小。它们都是问题的规模问题的规模n n的一个函数的一个函数，所以用n的最高数量级来表示。
