自考数据结构导论第一章概论

1、数据结构导论数据结构导论主讲：赖益强主讲：赖益强2 概述数据结构导论是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。 3第第1 1章章 概论概论1.11.1引言引言1.21.2基本概念和术语基本概念和术语1.31.3算法及描述算法及描述1.41.4算法分析算法分析4本章总述要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这

2、些概念之间的联系。本章重点本章重点逻辑结构和数据结构的概念。本章难点本章难点算法的时间复杂性分析。561.1 引言引言1.数据结构的概念数据结构的概念数据结构(Data structure）是计算机组织数据和存储数据的方式。是计算机组织数据和存储数据的方式。计算机解决问题的步骤：计算机解决问题的步骤：建立数学模型建立数学模型设计算法设计算法编程实现算法编程实现算法71.1 1.1 引言引言数据结构主要研究：数据结构主要研究：1 1）数据（计算机加工对象）的逻辑结构。）数据（计算机加工对象）的逻辑结构。2 2）实现各种基本操作的算法。）实现各种基本操作的算法。学习数据结构的目的：学习数据结构的目

3、的：掌握常用的数据结构及其应用。学会合理地组织数据， 有效地表示数据和处理数据。掌握算法设计技术和分析技术。掌握使用计算机解决问题的方法和技能，提高程序设计水平。8应用举例1学籍档案管理学号姓名性别年龄入学成绩1001王韬男205891002潘小欣女215801003张艳女195681004赵李军男185801005刘勇男225859数据特点：数据特点：l每个学生的信息占据一行，所有学生的信息按学号顺每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；序依次排列构成一张表格；l表中每个学生的信息依据学号的大小存在着一种前后表中每个学生的信息依据学号的大小存在着一种前后关系，这

4、就是我们所说的线性结构；关系，这就是我们所说的线性结构； 对它的操作通常是：对它的操作通常是：在学生档案中在学生档案中查找查找出某人的档出某人的档案案，读取读取某个学生的信息，某个学生的信息，插入插入某个学生的信息，某个学生的信息，删删除除某个学生的信息，某个学生的信息，更新更新某个学生的信息某个学生的信息等等。等等。 10应用举例应用举例2 2制定教学计划制定教学计划在制定教学计划时，需要考虑：在制定教学计划时，需要考虑： 各门课程的各门课程的开设顺序开设顺序，即有些课程需，即有些课程需要要先导课程先导课程，有些课程则不需要，而有些课，有些课程则不需要，而有些课程又是其他课程的先导课程。程又

5、是其他课程的先导课程。11 计 算 机 专 业 学 生 的 必 修 课 程课 程 编 号课 程 名 称需 要 的 先 导 课 程编 号C 1程 序 设 计 基 础无C 2离 散 数 学C 1C 3数 据 结 构C 1 ， C 2C 4汇 编 语 言C 1C 5算 法 分 析 与 设 计C 3 ， C 4C 6计 算 机 组 成 原 理C 1 1C 7编 译 原 理C 5 ， C 3C 8操 作 系 统C 3 ， C 6C 9高 等 数 学无C 1 0线 性 代 数C 9C 1 1普 通 物 理C 9C 1 2数 值 分 析C 9 ， C 1 0 ， C 1应用举例应用举例2 2制定教学计划制定

6、教学计划12数据结构主要研究：数据结构主要研究：131.2 1.2 基本概念和术语基本概念和术语14基本术语基本术语v数据数据（Data)Data)：所有能被所有能被计算机处理计算机处理的的符号符号的集合。的集合。v数据元素（数据元素（Data ElementData Element）：）：是数据这个集合中的是数据这个集合中的一个个体即数据的一个个体即数据的基本单位基本单位。v数据项（数据项（Data ItemData Item）：）：数据元素常常还可分为若干数据元素常常还可分为若干个数据项，数据项是数据具有意义的个数据项，数据项是数据具有意义的最小单位最小单位。15v逻辑结构（逻辑结构（Lo

7、gical StructureLogical Structure）：）：指数据元素之间的结构关系。指数据元素之间的结构关系。v物理结构（物理结构（Physical StructurePhysical Structure）也成为）也成为存储结构：存储结构：指数据结构在机内的表示，数据的逻辑结指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。构在计算机中的实现。16v数据的逻辑结构数据的逻辑结构(D, R) 可分为下列几种可分为下列几种: D = d1, d2, , dn 。v1. 集合集合: 数据元素同数据元素同“属于一个集合属于一个集合”。 R = 。v2. 线性结构线性结构: R= (

8、d1, d2), (d2, d3), , (dn-1, dn), 即除起始节点和终端结点即除起始节点和终端结点d1, dn外外,每个节点有一个每个节点有一个前驱和一个后继。前驱和一个后继。v3. 树状结构树状结构: (D, R) 构成树构成树, 即每个元素最多有一即每个元素最多有一个前驱个前驱, 可以有多个后继。可以有多个后继。v4. 图状结构图状结构: (D, R)构成一个图。构成一个图。逻辑结构的类型逻辑结构的类型17逻辑结构的种类：逻辑结构的种类： 数据的数据的四类逻辑结构示意图四类逻辑结构示意图: :线性线性结构结构树形树形结构结构图状图状结构结构集合集合结构结构18特别注意：特别注意

9、： 逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素的相对位置无关逻辑结构与数据元素的相对位置无关逻辑结构与所含结点个数无关逻辑结构与所含结点个数无关19数据在计算机内的表示形式称为数据在计算机内的表示形式称为数据的存储结构数据的存储结构存储结构的主要部分存储结构的主要部分v存储结点（每个存储结点存放一个数据元素）存储结点（每个存储结点存放一个数据元素）v数据元素之间关联方式的表示数据元素之间关联方式的表示数据的存储结构数据的存储结构20v数据结构的存储包含数据元素的存储及其逻辑关系的存储v存储结构可分为: 顺序存储结构、链式存储结构、索引存储方式和散

10、列存储方式等。v顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。数据的存储结构数据的存储结构21顺序存储结构：顺序存储结构：借助数据元素的借助数据元素的相对存储位置相对存储位置来表来表示数据的逻辑结构；示数据的逻辑结构；线性表的顺序存储方法：将表中的线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。结点一次存放在计算机内存中一组连续的存储单元中。链式存储结构：链式存储结构：借助数据元素借助数据元素地址的指针地址的指针表示数据表示数据的逻辑结构；的逻辑结构；索引存储结构：索引存储结构：借助索引表

11、中的借助索引表中的索引指示索引指示各存储节各存储节点的存储位置点的存储位置散列存储结构：散列存储结构：用用散列函数散列函数指示各节点的存储位置指示各节点的存储位置4 4种存储结构种存储结构22存储结构的分类: 顺序结构v顺序的方法: 将元素存储到一片连续的存储区. 姓名和电话号码数据23存储结构的分类: 链式结构 这种结构是给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两部分:特点：v1）动态分配，不需要预先确定内存分配；v2）插入和删除不需要移动其他元素；v3）非随机存取结构。24逻辑结构与存储结构的关系逻辑结构与存储结构的关系25运算运算运算就是指在某种逻辑结构

12、上施加的操作，即对逻辑运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。结构的加工。加工型运算：其操作改变原逻辑结构的值加工型运算：其操作改变原逻辑结构的值 如：结点个数，结点内容等如：结点个数，结点内容等 引用型运算：其操作引用型运算：其操作不改变不改变原逻辑结构的值原逻辑结构的值查找查找读取读取插入插入删除删除更新更新以上操作哪些是加工型操作，那些是引用型操作？以上操作哪些是加工型操作，那些是引用型操作？261.31.3算法及描述算法及描述( (运算的实现运算的实现) )算法算法规定了求解给定类型问题所需的规定了求解给定类型问题所需的所有所有“处理步骤处理步骤”及及执行顺序执行顺序

13、，使给定类型问题，使给定类型问题能在能在有限时间有限时间内被机械的求解。内被机械的求解。算法必须使用某种语言描述：算法必须使用某种语言描述：v程序程序v介于自然语言和程序设计语言的介于自然语言和程序设计语言的伪代码伪代码v非形式算法（自然语言）非形式算法（自然语言）v框图框图(N-S图图)本教材中使用了本教材中使用了类类C C语言描述算法语言描述算法27v一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列。v算法具有以下特性：v 1) 有穷性: 一个算法总是在执行有穷步后结束。v 2) 确定性: 算法的每一步都必须是明确地定义的。v 3) 可行性: 算法中的每一步都是可以通过已经实现的

14、操作来完成的。v 4) 输入: 一个算法有零个或者多个输入, 这些输入取自于特定的对象集合。v 5) 输出:一个算法有一个或者多个输出，它们是与输入有特定关系的量。28算法描述v我们教程主要用C语言描述。v以下简单复习下C语言的内容。 第第 29 页页C语言语言基本组成基本组成1. C语言的基本组成 第第 30 页页判断哪些是合法的标识符：C x1 1x x+y sum_5 sum-5 count _z3 $x_8 *Z3 第第 32 页页例如例如:变量名不能是变量名不能是int函数调用语句函数调用语句printfscanf输入输出语句输入输出语句字符字符输入输出语句输入输出语句格式格式输入输

15、出语句输入输出语句getcharputchar程序划分为三部分:数据输入,数据处理,数据输出。它们可以由赋值语句和输入输出语句来完成。注意：一定要严格区分赋值表达式和赋值语句的区别。printf(“%dn”,x=a*a+b*b+c*c);printf(“%dn”,x=a*a+b*b+c*c;);合法出错，输出语句的输出列表中不允许出现语句多分支if语句形式的格式：if(表达式1) 语句1； else if(条件表达式2)语句2； else if(条件表达式3)语句3； else if(条件表达式n)语句n； else 语句n+1； While 循环结构do-while 循环结构for循环结构

16、第第 38 页页printf(sum=%d,sum); main()int a=0; ff(a); printf(“this is a test); 第第 39 页页简单的简单的C语言程序介绍语言程序介绍思考: n的作用是什么?函数声明部分函数体C程序由函数组成对于一个C程序,至少有一个main函数,称为主函数,main是C语言中主函数的专用名，是程序执行的起点和终点。 第第 40 页页函数说明函数体思考：printf(a=%d,b=%d,sum=%d,a,b,sum);函数可分为函数说明部分和函数体注释:/*/ 不是程序有效部分a=1,b=2,sum=3 第第 41 页页C程序文件1（*.c

17、）文件n函数1main()函数n函数说明函数体变量说明部分执行部分语句1语句n 第第 42 页页431.41.4算法分析算法分析v算法的设计应满足：算法的设计应满足：v1）正确性：正确性：对于合法的输入产生符合要求的输出；对于合法的输入产生符合要求的输出；v2）可读性：可读性：算法应该易读、便于交流，算法应该易读、便于交流， 这也是保证算这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；法正确性的前提；添加注释也是一种增加可读性的办法；v3）健壮性：健壮性：当输入非法时，当输入非法时， 算法还能做出适当的反应算法还能做出适当的反应而不会崩溃，而不会崩溃， 如输出错误信息；算法中应该

18、考虑适当的如输出错误信息；算法中应该考虑适当的错误处理；错误处理；v4）效率高效率高且内存消耗小：效率高指运行时间短。存储且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。指算法执行过程中所需的最大存储空间。一个算法的时空性是指算法的一个算法的时空性是指算法的 时间复杂度时间复杂度和和空间复杂度空间复杂度算法分析主要算法分析主要分析算法分析算法的的 时间复杂度和空间复杂度，目的是提高算法的效率时间复杂度和空间复杂度，目的是提高算法的效率44 解决同一问题的算法可以有多种。解决同一问题的算法可以有多种。 我们希望我们希望从中选出最优的算法，效率高或者存储空间从中选出最优的

19、算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。小。为此，需要对算法进行评估，分析。通常考虑两个度量：通常考虑两个度量：v时间复杂度：时间复杂度：算法运行时需要的总步数，通算法运行时需要的总步数，通常是问题规模的函数。常是问题规模的函数。v空间复杂度：空间复杂度：算法执行时所占用的存储空间，算法执行时所占用的存储空间，通常是问题规模的函数。通常是问题规模的函数。45如何确定算法的计算量如何确定算法的计算量1.合理地选择一种或几种操作作为合理地选择一种或几种操作作为“标准操标准操作作”，无特殊说明，无特殊说明，默认以赋值语句作为默认以赋值语句作为标准操作。标准操作。2.确定每个算法共

20、确定每个算法共执行多少次标准操作执行多少次标准操作，并，并将此将此次数次数规定为该算法的规定为该算法的计算量。计算量。46如何确定算法的计算量如何确定算法的计算量v以算法在所有输入下的计算量的最大值作为以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的计算量，称为算法的最坏情况时间复算法的最坏情况时间复杂度杂度v以算法在所有输入下的计算量的加权平均值以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为作为算法的计算量，称为算法的平均情况时算法的平均情况时间复杂度间复杂度 最坏情况时间复杂度和平均情况时间复杂度通最坏情况时间复杂度和平均情况时间复杂度通称称为时间复杂度为时间复

21、杂度47void max1(int a,b,c,d)a*=d;b*=d;c*=d;if(ab) x=a;else x=b;if(cx) x=c;printf(“%dn”,x);void max2(int a,b,c,d)if(ab) x=a;else x=b;if(cx) x=c;x*=d;printf(“%dn”,x);算法算法max1max1和和max2max2的最坏情况时间复杂度分别为的最坏情况时间复杂度分别为5 5和和3 3例：例：设变量设变量a、b、c、d中各含一个整数。中各含一个整数。求求a、b、c中的最大值与中的最大值与d的乘积的乘积48例矩阵运算例矩阵运算矩阵乘法矩阵乘法Voi

22、d matrixmlt ( ) for(i=0;in;i+) for(j=0;jn;j+) Cij=0; for(k=0;kn;k+) Cij+=Aik*Bkj ; 49此算法的最坏时间复杂度和平均时间复杂度均为此算法的最坏时间复杂度和平均时间复杂度均为n n的的函数：函数：T(n)= nT(n)= n2 2 + n + n3 3T(n)T(n)与与 n n3 3的数量级相同的数量级相同称此算法的称此算法的时间复杂度量级为时间复杂度量级为O(nO(n3 3) )，记作，记作T(n)= O(nT(n)= O(n3 3) )一般我们将一般我们将O(nO(n3 3) )称作时间复杂度。称作时间复杂度。常见的时间复杂度按数量级递增排列依次为：常见的时间复杂度按数量级递增排列依次为：常数常数O(1),O(1),对数阶对数阶O(logO(log2n),n),线性阶线性阶O(n),O(n),线性对数阶线性对数阶O(nlogO(nlog2