《自考数据结构导论第一章概论介绍ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构导论第一章概论介绍ppt课件.ppt（57页珍藏版）》请在三一办公上搜索。
1、数据结构导论,主讲：徐青香2013、4,2,概述,数据结构导论是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。,3,第1章 概论,1.1引言1.2基本概念和术语1.3算法及描述1.4算法分析,4,本章总述,要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这些概念之间的联系。本章重点逻辑结构和数据结构的概念。本章难点算法的时
2、间复杂性分析。,5,6,1.1 引言,1.数据结构的概念,数据结构(Data structure）是计算机组织数据和存储数据的方式。,计算机解决问题的步骤：建立数学模型设计算法编程实现算法,7,1.1 引言,数据结构主要研究：1）数据（计算机加工对象）的逻辑结构。2）实现各种基本操作的算法。,学习数据结构的目的：,掌握常用的数据结构及其应用。学会合理地组织数据， 有效地表示数据和处理数据。掌握算法设计技术和分析技术。掌握使用计算机解决问题的方法和技能，提高程序设计水平。,8,应用举例1学籍档案管理,9,数据特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生
3、的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个学生的信息，删除某个学生的信息，更新某个学生的信息等等。,10,应用举例2制定教学计划在制定教学计划时，需要考虑： 各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。,11,应用举例2制定教学计划,12,数据结构主要研究：,13,1.2 基本概念和术语,14,基本术语,数据（Data)：所有能被计算机处理的符号的集合。数据元素（Data Element）：是数据这个集合中的一个个体即数据的基本单位。数据项（
4、Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。,15,逻辑结构（Logical Structure）：指数据元素之间的结构关系。物理结构（Physical Structure）也成为存储结构：指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。,16,数据的逻辑结构(D, R) 可分为下列几种: D = d1, d2, , dn 。1. 集合: 数据元素同“属于一个集合”。 R = 。2. 线性结构: R= (d1, d2), (d2, d3), , (dn-1, dn), 即除起始节点和终端结点d1, dn外,每个节点有一个前驱和一个后继。3.
5、树状结构: (D, R) 构成树, 即每个元素最多有一个前驱, 可以有多个后继。4. 图状结构: (D, R)构成一个图。,逻辑结构的类型,17,逻辑结构的种类：,数据的四类逻辑结构示意图:,线性结构,树形结构,图状结构,集合结构,18,特别注意：,逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素的相对位置无关逻辑结构与所含结点个数无关,19,数据在计算机内的表示形式称为数据的存储结构存储结构的主要部分存储结点（每个存储结点存放一个数据元素）数据元素之间关联方式的表示,数据的存储结构,20,数据结构的存储包含数据元素的存储及其逻辑关系的存储存储结构可分为: 顺序存储结构、链式存储结构、索
6、引存储方式和散列存储方式等。顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。,数据的存储结构,21,顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构；线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。链式存储结构：借助数据元素地址的指针表示数据的逻辑结构；索引存储结构：借助索引表中的索引指示各存储节点的存储位置散列存储结构：用散列函数指示各节点的存储位置,4种存储结构,22,存储结构的分类: 顺序结构,顺序的方法: 将元素存储到一片连续的存储区.,姓名和电话号码数据,23,存储结构
7、的分类: 链式结构,这种结构是给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两部分:特点：1）动态分配，不需要预先确定内存分配；2）插入和删除不需要移动其他元素；3）非随机存取结构。,24,逻辑结构与存储结构的关系,25,运算,运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。加工型运算：其操作改变原逻辑结构的值 如：结点个数，结点内容等 引用型运算：其操作不改变原逻辑结构的值查找读取插入删除更新以上操作哪些是加工型操作，那些是引用型操作？,26,1.3算法及描述(运算的实现),算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有
8、限时间内被机械的求解。算法必须使用某种语言描述：程序介于自然语言和程序设计语言的伪代码非形式算法（自然语言）框图(N-S图)本教材中使用了类C语言描述算法,27,一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列。算法具有以下特性： 1) 有穷性: 一个算法总是在执行有穷步后结束。 2) 确定性: 算法的每一步都必须是明确地定义的。 3) 可行性: 算法中的每一步都是可以通过已经实现的操作来完成的。 4) 输入: 一个算法有零个或者多个输入, 这些输入取自于特定的对象集合。 5) 输出:一个算法有一个或者多个输出，它们是与输入有特定关系的量。,28,算法描述,我们教程主要用C语言描述。
9、以下简单复习下C语言的内容。,29,第 29 页,小,大,1. C语言的基本组成,C语言概述,30,第 30 页,2、基本字符集 C语言编程中可以使用的字符。ASCII字符集。 数 字：0 1 2 3 4 5 6 7 8 9 字 母：a b c z A B C Z 运算符：+ - * / % = = != = 特殊符号：_(下划线) 空格 回车(r) 换行(n) 制表符(t) 其它转义字符,C语言概述,31,3、标识符 字符组成的串，用来对各种用户自定义对象命名。例如：变量名、常量名、数组名、函数名、文件名、类型名等。 合法的标识符：由字母或下划线开头,由字母、数字或下划线组成。字母:大小写的
10、az ,下划线:_ ,数字:09例如： a _ry test31 string_1不能以数字开头不能包含除下划线外的运算符和其他符号大小写区分,判断哪些是合法的标识符：C x1 1x x+y sum_5 sum-5 count _z3 $x_8 *Z3,C语言概述,32,第 32 页,4、关键字 C语言中由系统特殊定义的32个具有特定含义的标识符，不能作为用户自定义对象的名字。auto breakcase char constcontinue defaultdo double elseenum externfloat for gotoif intlong register returnshor
11、t signedsizeof static structswitch typedefunion unsigned voidvolatile while,例如:变量名不能是int,C语言概述,33,5、语句 int a,b,sum; sum=a+b; printf(sum=%d,sum);5.1、输入输出语句,C语言概述,函数调用语句,printfscanf,输入输出语句,字符输入输出语句,格式输入输出语句,getcharputchar,34,5.2、赋值语句,赋值语句:由赋值表达式加上一个分号构成，它属于表达式语句类。实例:a=1;b=2;c=3; /*三个赋值语句，分别为变量a，b，c赋值*
12、/x=a*a+b*b+c*c; /*计算表达式a2+b2+c2的值，并赋值给变量x*/,程序划分为三部分:数据输入,数据处理,数据输出。它们可以由赋值语句和输入输出语句来完成。,注意：一定要严格区分赋值表达式和赋值语句的区别。,printf(“%dn”,x=a*a+b*b+c*c);printf(“%dn”,x=a*a+b*b+c*c;);,合法,出错，输出语句的输出列表中不允许出现语句,35,单分支选择if语句格式： if(条件表达式) 语句双分支选择if语句格式：if(条件表达式) 语句1； else 语句2；,5.3、选择语句,多分支if语句形式的格式：if(表达式1) 语句1； els
13、e if(条件表达式2)语句2； else if(条件表达式3)语句3； else if(条件表达式n)语句n； else 语句n+1；,36,switch语句的一般格式：switch(表达式) case 判断值1: 语句(组)1 ；break;case 判断值2: 语句(组)2； break； case 判断值n:语句(组) n； break；default : 语句(组) n+1 ；,C语言概述,37,While语句的一般形式为：While(表达式) 语句；do语句；while（表达式）;for循环是C语言最常用最灵活的循环控制语句.for(赋初值表达式序列；条件；修改表达式序列)语句；,
14、5.4、循环语句,While 循环结构,do-while 循环结构,for循环结构,38,第 38 页,6、函数main() int a,b,sum; sum=a+b; printf(sum=%d,sum);,ff(int x) int a,b,sum; sum=a+b; main()int a=0; ff(a); printf(“this is a test);,C语言概述,39,第 39 页,简单的C语言程序介绍,C语言程序例1:/*example1.c*/屏幕上显示一句话 main ( ) printf(This is a C program.n); 运行结果是在屏幕上显示: This
15、is a C program.,思考: n的作用是什么?,函数声明部分,函数体,C程序由函数组成对于一个C程序,至少有一个main函数,称为主函数,main是C语言中主函数的专用名，是程序执行的起点和终点。,C语言概述,40,第 40 页,例2:/* example2.c */两个固定的数求和main ( ) int a,b,sum; /*定义三个整型变量*/ a=1; /*变量a赋值等于1*/ b=2; /*变量b赋值等于2*/ sum=a+b; /*计算变量a与b的和,赋值给sum*/ printf(sum=%d,sum); /*输出运算结果*/ 运行结果是在屏幕上显示: sum=3,函数
16、说明,思考：printf(a=%d,b=%d,sum=%d,a,b,sum);,函数可分为函数说明部分和函数体注释:/*/ 不是程序有效部分,a=1,b=2,sum=3,C语言概述,41,第 41 页,例3:/* example3.c */根据用户输入，求和main ( ) /*主函数*/ int a,b,sum; /*定义变量类型*/ printf(“please inputn”); /*调用库函数printf，输出“please input”*/ scanf(“%d,%d”, /*输出运算结果*/ 运行结果是在屏幕上显示: please input 10,12 a=10,b=12,sum=
17、22,C语言概述,42,第 42 页,43,1.4算法分析,算法的设计应满足：1）正确性：对于合法的输入产生符合要求的输出；2）可读性：算法应该易读、便于交流， 这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；3）健壮性：当输入非法时， 算法还能做出适当的反应而不会崩溃， 如输出错误信息；算法中应该考虑适当的错误处理；4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。一个算法的时空性是指算法的 时间复杂度和空间复杂度算法分析主要分析算法的 时间复杂度和空间复杂度，目的是提高算法的效率,44,解决同一问题的算法可以有多种。 我们希望从中选出最优的算
18、法，效率高或者存储空间小。为此，需要对算法进行评估，分析。通常考虑两个度量：时间复杂度：算法运行时需要的总步数，通常是问题规模的函数。空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数。,45,如何确定算法的计算量,合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作。确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。,46,如何确定算法的计算量,以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度 最坏情况时间复杂度和平均情况时
19、间复杂度通称为时间复杂度,47,void 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);,算法max1和max2的最坏情况时间复杂度分别为5和3,例：设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积,48,例矩阵运算矩阵乘法,Void matrixmlt ( ) for(i=0;in;i+) for(j=0;jn;j
20、+) Cij=0; for(k=0;kn;k+) Cij+=Aik*Bkj ; ,此程序基本操作执行多少次？数据规模是多少？,49,此算法的最坏时间复杂度和平均时间复杂度均为n的函数：T(n)= n2 + n3T(n)与 n3的数量级相同称此算法的时间复杂度量级为O(n3)，记作T(n)= O(n3)一般我们将O(n3)称作时间复杂度。常见的时间复杂度按数量级递增排列依次为：常数O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),多项式阶O(nC),指数阶O(Cn),我们将时间复杂度记为输入数据规模n的函数，若求解问题需要执行n2次操作则，记作O(
21、n2),50,时间复杂度,对于给定规模的问题，计算算法运行的总“步数”：在算法中不依赖于输入规模的语句都可看作基本操作，基本操作的一次运行视为一步；统计算法从开始到运行终止时所需总操作步数T, 并将其视为问题规模n的函数T(n). T(n) 称为算法的时间复杂度。,51,例 迭代累加求和 float sum(int a, const int n) float s = 0.0; / 计一步 for (int i = 0; i n; i+ ) s += ai; / 每次循环计一步 return s; / 计1步 总计步数:n + 2问题的规模即数组的规模n 包含函数调用的赋值语句的程序步数：for
22、 (int i=0;jn;i+) Ai=i; x = sum (A, n);总步数：循环步数 + 调用的步数 + 1 即 T(n)= n+ (n + 2) + 1=2n+3,52,空间复杂度,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行期间所需要的存储空间量包括以下部分：程序代码所占用的空间；输入数据所占用的空间；辅助变量所占用的空间；估算算法空间复杂度时，一般只分析辅助变量所占用的空间。,53,本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。,本课程讲述的主要内容,54,1. 下列程序段的时间复杂度为_
23、。product = 1;for (i = n;i0; i-)for (j = 1; j=n; j+)product *=j;,时间复杂度量级为 O(n2),练习题,一个算法的时间复杂度是算法输入规模的函数,55,2. 下列程序段的时间复杂度为_。product = 1;for (i = n;i0; i-)for (j = i; j=n; j+)product *=j;,基本操作执行次数 T(n)=1+2+n= (n+1)n/2时间复杂度量级为 t(n)=O(n2),56,3. 下列程序段的时间复杂性量级是_。 for (i=1;in; i+) for (j=1; ji; j+)t=t+1;,基本操作执行次数 T(n)=0+1+2+(n-2)= (n-1)(n-2)/2时间复杂度量级为 t(n)=O(n2),57,练习：假设在数组An中存有数据，设计算法查找值为K的元素，若找到则输出其位置i(1i n)，否则输出0设计成一个search函数,
