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

数据结构导论,主讲：徐青香2013、4,2,概述,数据结构导论是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。,3,第1章概论,1.1引言1.2基本概念和术语1.3算法及描述1.4算法分析,4,本章总述,要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这些概念之间的联系。本章重点逻辑结构和数据结构的概念。本章难点算法的时间复杂性分析。,5,6,1.1引言,1.数据结构的概念,数据结构(Datastructure）是计算机组织数据和存储数据的方式。,计算机解决问题的步骤：建立数学模型设计算法编程实现算法,7,1.1引言,数据结构主要研究：1）数据（计算机加工对象）的逻辑结构。2）实现各种基本操作的算法。,学习数据结构的目的：,掌握常用的数据结构及其应用。学会合理地组织数据，有效地表示数据和处理数据。掌握算法设计技术和分析技术。掌握使用计算机解决问题的方法和技能，提高程序设计水平。,8,应用举例1学籍档案管理,9,数据特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个学生的信息，删除某个学生的信息，更新某个学生的信息等等。,10,应用举例2制定教学计划在制定教学计划时，需要考虑：各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。,11,应用举例2制定教学计划,12,数据结构主要研究：,13,1.2基本概念和术语,14,基本术语,数据（Data)：所有能被计算机处理的符号的集合。数据元素（DataElement）：是数据这个集合中的一个个体即数据的基本单位。数据项（DataItem）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。,15,逻辑结构（LogicalStructure）：指数据元素之间的结构关系。物理结构（PhysicalStructure）也成为存储结构：指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。,16,数据的逻辑结构(D,R)可分为下列几种:D=d1,d2,dn。1.集合:数据元素同“属于一个集合”。R=。2.线性结构:R=(d1,d2),(d2,d3),(dn-1,dn),即除起始节点和终端结点d1,dn外,每个节点有一个前驱和一个后继。3.树状结构:(D,R)构成树,即每个元素最多有一个前驱,可以有多个后继。4.图状结构:(D,R)构成一个图。,逻辑结构的类型,17,逻辑结构的种类：,数据的四类逻辑结构示意图:,线性结构,树形结构,图状结构,集合结构,18,特别注意：,逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素的相对位置无关逻辑结构与所含结点个数无关,19,数据在计算机内的表示形式称为数据的存储结构存储结构的主要部分存储结点（每个存储结点存放一个数据元素）数据元素之间关联方式的表示,数据的存储结构,20,数据结构的存储包含数据元素的存储及其逻辑关系的存储存储结构可分为:顺序存储结构、链式存储结构、索引存储方式和散列存储方式等。顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。,数据的存储结构,21,顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构；线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。链式存储结构：借助数据元素地址的指针表示数据的逻辑结构；索引存储结构：借助索引表中的索引指示各存储节点的存储位置散列存储结构：用散列函数指示各节点的存储位置,4种存储结构,22,存储结构的分类:顺序结构,顺序的方法:将元素存储到一片连续的存储区.,姓名和电话号码数据,23,存储结构的分类:链式结构,这种结构是给结点附加一个指针字段,指出其后继节点的位置,即存放结点的存储单元分为两部分:特点：1）动态分配，不需要预先确定内存分配；2）插入和删除不需要移动其他元素；3）非随机存取结构。,24,逻辑结构与存储结构的关系,25,运算,运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。加工型运算：其操作改变原逻辑结构的值如：结点个数，结点内容等引用型运算：其操作不改变原逻辑结构的值查找读取插入删除更新以上操作哪些是加工型操作，那些是引用型操作？,26,1.3算法及描述(运算的实现),算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解。算法必须使用某种语言描述：程序介于自然语言和程序设计语言的伪代码非形式算法（自然语言）框图(N-S图)本教材中使用了类C语言描述算法,27,一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列。算法具有以下特性：1)有穷性:一个算法总是在执行有穷步后结束。2)确定性:算法的每一步都必须是明确地定义的。3)可行性:算法中的每一步都是可以通过已经实现的操作来完成的。4)输入:一个算法有零个或者多个输入,这些输入取自于特定的对象集合。5)输出:一个算法有一个或者多个输出，它们是与输入有特定关系的量。,28,算法描述,我们教程主要用C语言描述。以下简单复习下C语言的内容。,29,第29页,小,大,1.C语言的基本组成,C语言概述,30,第30页,2、基本字符集C语言编程中可以使用的字符。ASCII字符集。数字：0123456789字母：abczABCZ运算符：+-*/%=!=特殊符号：_(下划线)空格回车(r)换行(n)制表符(t)其它转义字符,C语言概述,31,3、标识符字符组成的串，用来对各种用户自定义对象命名。例如：变量名、常量名、数组名、函数名、文件名、类型名等。合法的标识符：由字母或下划线开头,由字母、数字或下划线组成。字母:大小写的az,下划线:_,数字:09例如：a_rytest31string_1不能以数字开头不能包含除下划线外的运算符和其他符号大小写区分,判断哪些是合法的标识符：Cx11xx+ysum_5sum-5count_z3$x_8*Z3,C语言概述,32,第32页,4、关键字C语言中由系统特殊定义的32个具有特定含义的标识符，不能作为用户自定义对象的名字。autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile,例如:变量名不能是int,C语言概述,33,5、语句inta,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赋值*/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；elseif(条件表达式2)语句2；elseif(条件表达式3)语句3；elseif(条件表达式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(赋初值表达式序列；条件；修改表达式序列)语句；,5.4、循环语句,While循环结构,do-while循环结构,for循环结构,38,第38页,6、函数main()inta,b,sum;sum=a+b;printf(sum=%d,sum);,ff(intx)inta,b,sum;sum=a+b;main()inta=0;ff(a);printf(“thisisatest);,C语言概述,39,第39页,简单的C语言程序介绍,C语言程序例1:/*example1.c*/屏幕上显示一句话main()printf(ThisisaCprogram.n);运行结果是在屏幕上显示:ThisisaCprogram.,思考:n的作用是什么?,函数声明部分,函数体,C程序由函数组成对于一个C程序,至少有一个main函数,称为主函数,main是C语言中主函数的专用名，是程序执行的起点和终点。,C语言概述,40,第40页,例2:/*example2.c*/两个固定的数求和main()inta,b,sum;/*定义三个整型变量*/a=1;/*变量a赋值等于1*/b=2;/*变量b赋值等于2*/sum=a+b;/*计算变量a与b的和,赋值给sum*/printf(sum=%d,sum);/*输出运算结果*/运行结果是在屏幕上显示:sum=3,函数说明,思考：printf(a=%d,b=%d,sum=%d,a,b,sum);,函数可分为函数说明部分和函数体注释:/*/不是程序有效部分,a=1,b=2,sum=3,C语言概述,41,第41页,例3:/*example3.c*/根据用户输入，求和main()/*主函数*/inta,b,sum;/*定义变量类型*/printf(“pleaseinputn”);/*调用库函数printf，输出“pleaseinput”*/scanf(“%d,%d”,/*输出运算结果*/运行结果是在屏幕上显示:pleaseinput10,12a=10,b=12,sum=22,C语言概述,42,第42页,43,1.4算法分析,算法的设计应满足：1）正确性：对于合法的输入产生符合要求的输出；2）可读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；3）健壮性：当输入非法时，算法还能做出适当的反应而不会崩溃，如输出错误信息；算法中应该考虑适当的错误处理；4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。一个算法的时空性是指算法的时间复杂度和空间复杂度算法分析主要分析算法的时间复杂度和空间复杂度，目的是提高算法的效率,44,解决同一问题的算法可以有多种。我们希望从中选出最优的算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。通常考虑两个度量：时间复杂度：算法运行时需要的总步数，通常是问题规模的函数。空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数。,45,如何确定算法的计算量,合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作。确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。,46,如何确定算法的计算量,以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度最坏情况时间复杂度和平均情况时间复杂度通称为时间复杂度,47,voidmax1(inta,b,c,d)a*=d;b*=d;c*=d;if(ab)x=a;elsex=b;if(cx)x=c;printf(“%dn”,x);,voidmax2(inta,b,c,d)if(ab)x=a;elsex=b;if(cx)x=c;x*=d;printf(“%dn”,x);,算法max1和max2的最坏情况时间复杂度分别为5和3,例：设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积,48,例矩阵运算矩阵乘法,Voidmatrixmlt()for(i=0;in;i+)for(j=0;jn;j+)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),线性