数据结构C语言版严尉敏编 第1章绪论

1、 第一章第一章 绪绪 论论 上课前需要说明的几个问题：上课前需要说明的几个问题： 1.1.任课教师：王岁花任课教师：王岁花 联系电话：联系电话：1366390127313663901273 2. 2. 交流信箱：交流信箱： 3. 3. 公共信箱：公共信箱： 密码：密码： datasggxxdatasggxx 4.4.关于数据结构课程：关于数据结构课程： 教材、重要性、时间按排（教材、重要性、时间按排（54+3254+32）、）、 考试考试(=(=期末考试期末考试* *70%+70%+平时成绩平时成绩* *30%30%） 5.5.平时成绩主要是实验作业完成情况，实验每次平时成绩主要是实验作业完成

2、情况，实验每次 点名，随机抽查验收，查看程序运行。点名，随机抽查验收，查看程序运行。 第一章第一章 绪绪 论论 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语 1.4 1.4 算法和算法分析算法和算法分析 1.3 1.3 抽象数据类型抽象数据类型 本章小结、本章小结、教材、参考文献教材、参考文献 作作 业业 第一章第一章 绪绪 论论 1.1 1.1 什么是数据结构什么是数据结构 1) 1) 数据结构讨论的范畴。数据结构讨论的范畴。 NiklausNiklaus Wirth Wirth： 程序程序= =数据结构数据结构+ +算法算法 程序设计程序设计:

3、 : 算法算法: : 数据结构数据结构: : 为计算机处理问题编制为计算机处理问题编制 一组指令集一组指令集 处理问题的策略处理问题的策略 问题的数学模型问题的数学模型 第一章第一章 绪绪 论论 用计算机解决一个具体问题时，大致需要经过下列用计算机解决一个具体问题时，大致需要经过下列 几个步骤几个步骤: （1）抽象出一个适当的数学模型）抽象出一个适当的数学模型 （2）设计一个解此问题的算法）设计一个解此问题的算法 （3）编出程序进行测试、修改直至得到最终结果。）编出程序进行测试、修改直至得到最终结果。 第一章第一章 绪绪 论论 例例1. 1. 田径赛的时间安排问题田径赛的时间安排问题 设有设有

4、六个六个比赛项目，规定每个选手至多可参比赛项目，规定每个选手至多可参 加三个项目，有五人报名参加比赛（如下表所示）加三个项目，有五人报名参加比赛（如下表所示） 设计比赛日程表，使得在尽可能短的时间内完成设计比赛日程表，使得在尽可能短的时间内完成 比赛。比赛。 姓姓 名名项项 目目1项项 目目2项项 目目3 丁丁 一一 马马 二二 张张 三三 李李 四四 王王 五五 跳跳 高高 标标 枪枪 标标 枪枪 铅铅 球球 跳跳 远远 跳跳 远远100米米 铅铅 球球 100米米200米米 200米米跳跳 高高 200米米 用无向图的用无向图的 着色问题解着色问题解 决！决！ 第一章第一章 绪绪 论论 （

5、1 1）设用如下六个不同的代号代表不同的项目：）设用如下六个不同的代号代表不同的项目： 跳高跳高 跳远跳远 标枪标枪 铅球铅球 100100米米 200200米米 A A B B C D E C D E F F （2 2）用顶点代表比赛项目）用顶点代表比赛项目 （3 3）用边连接不能同时进行比赛的项目）用边连接不能同时进行比赛的项目 则可用如下图所示：则可用如下图所示： 姓姓 名名项目项目1项目项目2项目项目3 丁丁 一一 马马 二二 张张 三三 李李 四四 王王 五五 A C C D B BE D EF FA F 第一章第一章 绪绪 论论 韦尔奇韦尔奇. .鲍威尔（鲍威尔（Welch Pow

6、ell)Welch Powell)方法：方法： 1.1.将图将图G G中的结点按中的结点按度度递减的顺序排列。递减的顺序排列。 2.2.用没有用过的颜色对第一个点着色，并且按排列用没有用过的颜色对第一个点着色，并且按排列 次序，对与前面着色点不相邻的点着相同颜色。次序，对与前面着色点不相邻的点着相同颜色。 3.3.从序列中删除第从序列中删除第2 2步着过色的点。步着过色的点。 4.4.重复第重复第2 2、3 3步，直到序列为空。步，直到序列为空。 第一章第一章 绪绪 论论 例例: :对上例，执行算法第对上例，执行算法第1 1步结果为：步结果为： F ,A , E ,B , C ,D F ,A

7、, E ,B , C ,D 重复执行第重复执行第2,32,3步序列变化为：步序列变化为： A,E,B,C,D E,B,D B A,E,B,C,D E,B,D B 图的变化为：图的变化为： 第一章第一章 绪绪 论论 数据结构数据结构是一门讨论是一门讨论“描述现实世界实体的描述现实世界实体的 数学模型数学模型( (非数值计算非数值计算) )及其及其上的上的操作在计算机操作在计算机 中如何表示和实现中如何表示和实现”的学科。的学科。 2) 数据结构数据结构 对研究对研究对象对象及其之间及其之间关系关系的描述。的描述。 结构结构 数据结构的形式定义为数据结构的形式定义为: : 数据结构是一个二元组数据

8、结构是一个二元组 Data_Structures = (D, S)Data_Structures = (D, S) 其中其中:D :D ：是数据元素的有限集：是数据元素的有限集 S S ：是：是 D D上关系的有限集上关系的有限集。 （逻辑结构）（逻辑结构） 第一章第一章 绪绪 论论 1.2 1.2 基本概念和术语基本概念和术语 数据数据(Data):(Data):是对信息的一种符号表示。在计算机科是对信息的一种符号表示。在计算机科 学中是指所有能被输入到计算机中并被计算机程序处学中是指所有能被输入到计算机中并被计算机程序处 理的符号的总称。理的符号的总称。 数据元素数据元素(Data Ele

9、ment(Data Element):):是数据的基本单位，在计是数据的基本单位，在计 算机程序中通常作为一个整体进行考虑和处理。算机程序中通常作为一个整体进行考虑和处理。 数据项数据项(Data Item(Data Item）: :一个数据元素可由若干个数据一个数据元素可由若干个数据 项组成。数据项是数据的不可分割的最小单位。项组成。数据项是数据的不可分割的最小单位。 数据对象数据对象(Data Object)(Data Object)：是性质相同的数据元素的：是性质相同的数据元素的 集合。是数据的一个子集。集合。是数据的一个子集。 第一章第一章 绪绪 论论 数据结构数据结构: :是相互之间

10、存在一种或多种特定关系的数是相互之间存在一种或多种特定关系的数 据元素的集合。据元素的集合。 根据数据元素间关系的不同，数据结构或分为根据数据元素间关系的不同，数据结构或分为四种：四种： 线性结构：线性结构：结构中的数据元素之间结构中的数据元素之间 存在一对一的关系。存在一对一的关系。 树型结构（层次结构）树型结构（层次结构）：结构中的数：结构中的数 据元素之间存在一对多的关系。据元素之间存在一对多的关系。 图状结构图状结构（网状结构）：结构中的（网状结构）：结构中的 数据元素之间存在多对多的关系。数据元素之间存在多对多的关系。 集集 合：合：结构中的数据元素除了结构中的数据元素除了 同属于一

11、个集合外，别无其它关系。同属于一个集合外，别无其它关系。 Data_Structures = (D, S)Data_Structures = (D, S) （逻辑结构）（逻辑结构） 第一章第一章 绪绪 论论 数据的存储结构数据的存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象 “数据元素数据元素”的映象的映象 ？ “关系关系”的映象的映象 ？ 数据元素的映象方法：数据元素的映象方法： 用二进制位用二进制位(bit)(bit)的位串表示数据元素的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2 第一章第

12、一章 绪绪 论论 1 1. .顺序映象顺序映象 ：借助于元素在计算机存储器中的存借助于元素在计算机存储器中的存 储位置来描述元素之间的逻辑关系。储位置来描述元素之间的逻辑关系。 例：关系的映象方法（表示例：关系的映象方法（表示 的方法）的方法） xyz 2.2.链式映象链式映象 借助于指示元素存储地址的指针表示借助于指示元素存储地址的指针表示 元素之间的逻辑关系元素之间的逻辑关系 。 x yz 第一章第一章 绪绪 论论 在不同的编程环境中，在不同的编程环境中， 存储结构可有不同的描述方法。存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编当用高级程序设计语言进行编程时

13、，通常可用高级编 程语言中提供的数据类型描述之程语言中提供的数据类型描述之。 第一章第一章 绪绪 论论 数据类型：数据类型：数据类型是一个值的集合和定义在这组值数据类型是一个值的集合和定义在这组值 集上的一组操作的总称。集上的一组操作的总称。 例如：例如：C-语言中的语言中的int , float , char等等 抽象数据类型抽象数据类型(Abstract Data Type 简称简称ADT) ：是指一个是指一个 数学模型以及定义在此数学模型上的一组操作。数学模型以及定义在此数学模型上的一组操作。 第一章第一章 绪绪 论论 抽象数据类型的描述方法抽象数据类型的描述方法: 抽象数据类型可用（抽

14、象数据类型可用（D，S，P）三元组表）三元组表 示示,其中，其中，D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P 是对是对D的基本操作集。的基本操作集。 本门课采用下面格式表示抽象数据类型：本门课采用下面格式表示抽象数据类型： ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名 第一章第一章 绪绪 论论 其中，数据对象和数据关系的定义用伪码描述，基本其中，数据对象和数据关系的定义用伪码描述，基本 操作的定义格

15、式为：操作的定义格式为： 基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件描述初始条件：初始条件描述 操作结果：操作结果描述操作结果：操作结果描述 基本操作有两种参数基本操作有两种参数：赋值参数赋值参数只为操作提供输入值；只为操作提供输入值； 引用参数引用参数以以 return; void sum2(int a,int b,int return; void main( )void main( ) int int x=3,y=4,z=5; x=3,y=4,z=5; printf(“xprintf(“x=%d,y=%d,z=%dn”,x,y,z);=%d,y=%d,z=%dn”,x,y

16、,z); sum1(x,y,z); sum1(x,y,z); printf(“xprintf(“x=%d,y=%d,z=%dn”,x,y,z);=%d,y=%d,z=%dn”,x,y,z); sum2(x,y,z); sum2(x,y,z); printf(“xprintf(“x=%d,y=%d,z=%dn”,x,y,z); =%d,y=%d,z=%dn”,x,y,z); 运行结果运行结果 x=3,y=4,z=5 x=3,y=4,z=5 x=3,y=4,z=7 第一章第一章 绪绪 论论 1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 本书采用类本书采用类C-C-语言作为描述工

17、具，类语言作为描述工具，类C-C-精选精选 了了C C语言的一个核心子集，同时做了若干扩充修语言的一个核心子集，同时做了若干扩充修 改，增强了语言的描述功能。改，增强了语言的描述功能。P P10-11 10-11 例如：抽象数据类型三元组的定义：例如：抽象数据类型三元组的定义：P9 第一章第一章 绪绪 论论 / - / - 采用动态分配的顺序存储结构采用动态分配的顺序存储结构- typedef ElemType typedef ElemType * *Triplet;Triplet; / / 由由InitTripletInitTriplet分配三个元素存储空间分配三个元素存储空间 / Trip

18、let/ Triplet类型是类型是ElemTypeElemType类型的指针类型的指针 /存放存放ElemTypeElemType类型的地址类型的地址 第一章第一章 绪绪 论论 / bo1_1.cpp / bo1_1.cpp 抽象数据类型抽象数据类型TripletTriplet和和ElemTypeElemType /(/(由由c1_1.hc1_1.h定义定义) )的基本操作的基本操作(8(8个个) ) Status InitTriplet(Triplet T0=v1,T1=v2,T2=v3; return OK; 第一章第一章 绪绪 论论 Status Get(Triplet T,int i

19、, ElemType e=Ti-1; return OK; Status Put(Triplet T,int i,ElemType e) /初始条件：三元组初始条件：三元组T T已存在，已存在，1i31i3。 /操作结果：改变操作结果：改变T T的第的第i i元的值为元的值为e e if(i3) return ERROR; Ti-1=e; return OK; 第一章第一章 绪绪 论论 Status IsAscending(Triplet T) / / 初始条件：三元组初始条件：三元组T T已存在。操作结果：如果已存在。操作结果：如果 /T/T的三个元素按升序排列，返回的三个元素按升序排列，返

20、回1 1，否则返回，否则返回0 0 return(T0=T1 第一章第一章 绪绪 论论 Status Max(Triplet T,ElemTypeStatus Max(Triplet T,ElemType T1 =T2)?T1:T2); return OK; return OK; Status Min(Triplet T,ElemTypeStatus Min(Triplet T,ElemType T1=0)n=0)个初始数据的个初始数据的 输入。输入。 （5 5）输出：一个算法有一个或多个与输入有某）输出：一个算法有一个或多个与输入有某 种关系的有效信息的输出。种关系的有效信息的输出。 第一章

21、第一章 绪绪 论论 例例1.4 1.4 一个不超过一个不超过100100 次计数的算法次计数的算法 n=1;s=0;n=1;s=0; while(n=100) while(n0) while(n0) n=n+1; n=n+1; 输出输出n n的值；的值； 第一章第一章 绪绪 论论 3 3）算法设计的要求）算法设计的要求 正确性、可读性、健壮性和效率与存储量要求。正确性、可读性、健壮性和效率与存储量要求。 第一章第一章 绪绪 论论 程序正确性的四个层面：程序正确性的四个层面： （1 1）不含语法错误）不含语法错误 （2 2）程序对于）程序对于n n组输入数据能够得出满足规格组输入数据能够得出满足

22、规格 说明要求的结果。说明要求的结果。 （3 3）程序对于精心选择的典型、边界性的）程序对于精心选择的典型、边界性的n n组组 输入数据能得出满足规格说明要求的结果。输入数据能得出满足规格说明要求的结果。 （4 4）程序对于一切合适的输入数据都能得出）程序对于一切合适的输入数据都能得出 满足规格说明要求的结果（穷举）。满足规格说明要求的结果（穷举）。 第一章第一章 绪绪 论论 嫦娥一号：嫦娥一号：98.8万行源代码，万行源代码， 421万份文件，万份文件， 打印打印 出来有出来有23000页。用了页。用了160多万行程序证明它的正确多万行程序证明它的正确 性。性。 第一章第一章 绪绪 论论 4

23、 4）高效率与低存储量需求）高效率与低存储量需求 通常，效率指的是通常，效率指的是算法执行时间算法执行时间；存储量指的是；存储量指的是 算法执行过程中算法执行过程中所需的最大存储空间所需的最大存储空间，两者都与问题的，两者都与问题的 规模有关。规模有关。 算法效率的衡量方法和准则算法效率的衡量方法和准则 衡量算法效率的方法衡量算法效率的方法: : 缺点：缺点：1 1必须执行程序必须执行程序 2 2其它因素掩盖算法本质其它因素掩盖算法本质 事后统计法：事后统计法： 事前分析估算法事前分析估算法 第一章第一章 绪绪 论论 和算法执行时间相关的因素：和算法执行时间相关的因素： 1 1算法选用的策略算

24、法选用的策略 2 2问题的规模问题的规模 3 3编写程序的语言编写程序的语言 4 4编译程序产生的机器代码的质量编译程序产生的机器代码的质量 5 5计算机执行指令的速度计算机执行指令的速度 一个特定一个特定算法的算法的“运行工作量运行工作量” ” 的大小，只的大小，只 依赖于依赖于问题的规模问题的规模（通常用整数量（通常用整数量n表示），或表示），或 者说，者说，它是问题规模的函数。它是问题规模的函数。 第一章第一章 绪绪 论论 假如，随着问题规模假如，随着问题规模 n n 的增长，算法执行时间的的增长，算法执行时间的 增长率和增长率和 f(n) f(n) 的增长率相同，则可记作：的增长率相同

25、，则可记作： T (n) = O(f(n)T (n) = O(f(n) 称称T (n) T (n) 为算法的为算法的( (渐近渐近) )时间复杂度。时间复杂度。 = M n T(n) lim f(n) 如何估算算法的时间复杂度？如何估算算法的时间复杂度？ ( M M 是是00的常数的常数) ) 例：例：2n2n3 3+1000n+1000n2 2+1=O(n+1=O(n3 3) ) 1000n 1000n2 2+n+1000000= O(n+n+1000000= O(n2 2) ) 第一章第一章 绪绪 论论 算法算法 = = 控制结构控制结构 + + 原操作原操作 /基本操作基本操作 （固有数

26、据类型的操作）（固有数据类型的操作） 算法的执行时间算法的执行时间 = = 原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间 算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和 成正比成正比 从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是 基基 本操作本操作 的原操作，以该基本操作的原操作，以该基本操作 在算法中重复执在算法中重复执 行的次数行的次数 作为算法运行时间的衡量准则。作为算法运行时间的衡量准则。 第一章第一章 绪绪 论论 例例 一一 两两 个个 矩矩 阵阵 相相 乘乘 void mult(i

27、nt a, intvoid mult(int a, int b, int b, int c ) c ) / / 以二维数组存储矩阵元素，以二维数组存储矩阵元素，c c 为为 a a 和和 b b 的乘积的乘积 forfor (i=1; i=n; +i) (i=1; i=n; +i) forfor (j=1; j=n; +j) (j=1; j=n; +j) cij = 0; cij = 0; forfor (k=1; k=n; +k) (k=1; k=n; +k) cij += cij += aikaik* *bkj;bkj; /for /for /mult /mult基本操作基本操作: : 乘

28、法操作乘法操作 时间复杂度时间复杂度: : O(nO(n3 3) ) 第一章第一章 绪绪 论论 例例 二二 选选 择择 排排 序序 时间复杂度时间复杂度: : O(nO(n2 2) ) 基本操作基本操作: : 比较比较( (数据元素数据元素) )操作操作 void select_sort(int a, int void select_sort(int a, int n) n) / / 将将 a a 中整数序列重新排列成自小至大有序的整数序列。中整数序列重新排列成自小至大有序的整数序列。 / select_sort / select_sort / / 选择第选择第 i i 个最小元素个最小元素

29、forfor ( k = i+1; k n; +k ) ( k = i+1; k n; +k ) if if (ak ai(ak ai ) ) ai ak; ; for ( i = 0; i n-1; +i ) for ( i = 0; i=1 for (i=n-1, change=TRUE; i=1 -i)i) / bubble_sort / bubble_sort change = FALSE;change = FALSE;/ change / change 为元素进行交换标志为元素进行交换标志 forfor (j=0; ji; +j) (j=0; j aj+1) if (aj aj+1)

30、 aj aj+1;aj aj+1; change = TRUEchange = TRUE ; ; / / 一趟起泡一趟起泡 交换次数：交换次数：最好情况：最好情况：0 0 最坏情况：最坏情况：n(n-1)/2n(n-1)/2 第一章第一章 绪绪 论论 最坏情况下的时间复杂度最坏情况下的时间复杂度 平均时间复杂度平均时间复杂度 若不特别说明，以后我们所说的都是若不特别说明，以后我们所说的都是 最坏情况下的时间复杂度最坏情况下的时间复杂度 第一章第一章 绪绪 论论 常见函数的时间复杂度常见函数的时间复杂度 按数量递增排列及增长按数量递增排列及增长 率。率。 常数阶常数阶O(1)O(1) 对数阶对数

31、阶O(logO(log2 2n)n) 线性阶线性阶O(n)O(n) 线性对数阶线性对数阶O(nlogO(nlog2 2n)n) 平方阶平方阶O(nO(n2 2) ) 立方阶立方阶O(nO(n3 3) ) k k次方阶次方阶O(nO(nk k) ) 指数阶指数阶O(2O(2n n） 第一章第一章 绪绪 论论 1.10 按增长率由小到大的排列顺序是：按增长率由小到大的排列顺序是： （2/3）n , 2100, log2(log2n) , log2n , (log2n)2, , n2/3, n/log2n , n , nlog2n , n3/2, (4/3)n , (3/2)n , n log2n

32、, n! , nn 解题依据为：解题依据为： n 1 2 2 lim0 (1) m x x x m m 2 lim log x x x 第一章第一章 绪绪 论论 4) 4) 算法的存储空间需求算法的存储空间需求 算法的空间复杂度定义为算法的空间复杂度定义为: : 表示随着问题规模表示随着问题规模 n n 的增大，算法运行的增大，算法运行 所需存储量的增长率与所需存储量的增长率与 g(n) g(n) 的增长率相同。的增长率相同。 S(n) = O(g(n)S(n) = O(g(n) 算法的存储量包括算法的存储量包括: : 输入数据所占空间输入数据所占空间 程序本身所占空间程序本身所占空间 辅助变

33、量所占空间辅助变量所占空间 第一章第一章 绪绪 论论 若输入数据所占空间只取决于问题本身，和算若输入数据所占空间只取决于问题本身，和算 法无关，则只需要分析法无关，则只需要分析除输入和程序之外的辅助变除输入和程序之外的辅助变 量所占额外空间量所占额外空间。 若所需存储量依赖于特定的输入，则通常按最若所需存储量依赖于特定的输入，则通常按最 坏情况考虑。坏情况考虑。 若所需额外空间相对于输入数据量来说是常数，若所需额外空间相对于输入数据量来说是常数， 则称此算法为则称此算法为原地工作原地工作。 第一章第一章 绪绪 论论 本章小结本章小结 1.1.基本概念和术语基本概念和术语 数据、数据元素、数据项

34、、数据结构、数据对象、数据、数据元素、数据项、数据结构、数据对象、 数据结构（逻辑结构、存储结构、运算）、多形数数据结构（逻辑结构、存储结构、运算）、多形数 据类型、抽象数据类型（定义、表示和实现）据类型、抽象数据类型（定义、表示和实现） 2.2.抽象数据类型：抽象数据类型：描述、类描述、类-C-C中的基本语句和函数中的基本语句和函数 3.3.算法：算法：算法的时间复杂度（渐近时间复杂度、最坏算法的时间复杂度（渐近时间复杂度、最坏 情况下的时间复杂度和平均时间复杂度），算法的情况下的时间复杂度和平均时间复杂度），算法的 空间复杂度（原地工作、额外空间）。对空间复杂度（原地工作、额外空间）。对O

35、 O的理解的理解 第一章第一章 绪绪 论论 4.4.编程常用头文件：编程常用头文件： #include #include #include / malloc( ),alloc( ),realloc( )等等 #include / INT_MAX等等 #include / EOF(=Z或或F6),NULL #include / atoi( ) ,rand( ),exit(n) #include / eof( ) #include / floor(),ceil( ),abs( ) #include / exit(n) #include / cout,cin 第一章第一章 绪绪 论论 5. 5. 函

36、数结果状态代码函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; / Status是函数的类型是函数的类型, /其值是函数结果状态代码，如其值是函数结果状态代码，如OK等等 typedef int Boolean; / Boolean是布尔类型是布尔类型,其其 /值是值是TRUE或或FALSE 第一章第一章 绪绪 论论 6.6.上机环境及注意事项上机环境及注意事项 上机环境上机环境VC+6.0 ,VC+6.0 ,但我们不用面象对象的思想；除但我们不用面象对象的思想；除 了使用了使用VCVC中提供的中提供的引用参数引用参数的概念外，全用的是标准的概念外，全用的是标准C C 分析思想。分析思想。 所有用户定义的类型，必须先定义后使用！所有用户定义的类型，必须先定义后使用！ 例如：例如：ElemTypeElemType 在使用时，应根据情况定义它的具体在使用时，应根据情况定义它的具体 念义。念义。 第一章第一章 绪绪