数据结构第一章概论.ppt

数 据 结 构-,第一章 绪 论,1.1 数据结构研究什么？将现实世界中的数据描述及关系表示出来，并存储到计算机内，供用户程序操作。现实世界中的数据描述及关系：4种：离散型，线性结构，层次结构，网状结构。离散数学：研究离散型。数据结构：研究线性结构，层次结构和网状结构。线性结构：线性表表示。层次结构：树形结构表示。网状结构：图结构表示。数据结构研究：数据逻辑结构，存储结构及施加其上的运算。,例1 L=(20,-5,66,15,44)是一个线性表例2 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将记录(record)定义为”结构”(struct)；登记表也是一个线性表。,例3 家族中父子关系是一种层次结构-树 T,张一,张三,张二一,张三一,张三小,张三大,张二,张四,层次结构：部门之间的隶属关系：学校-系-科-班 领导和被领导之间领导关系：主席-部长-司长-处长-科长,例4 无向图G,A,B,D,C,E,F,G,其中：A、B、C 等是顶点(vertex),图中任意两个顶点之间都可能有关系。,网络结构：电网，电信网，计算机通信网等。,1.基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈,队列,双队列；数组,串。1.2 非线性结构：树,二叉树；图,网络。2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法：顺序,折半,分块,哈希,二叉排序树等 4.排序算法：内部排序,外部排序 5.文件 6.基本应用与综合应用 要求具备的知识：c语言及程序设计，具有一定的程序设计能力。,本课程的内容和任务,1.2 基本概念和术语,1.数据（data)-所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。2.数据元素(data element)-数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。3.数据项(data item)-是数据的不可分割的最小单位。如：姓名、年龄等 一个数据元素可由一个或多个数据项组成。如:(姓名、年龄),4.数据对象(data object),由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。例1 由4个整数组成的数据对象 D1=20,-30,88,45 例2 由正整数组成的数据对象 D2=1,2,3,.例3 由26个字母组成的数据对象 D3=A,B,C,.,Z 其中：D1，D3是有穷集，D2是无穷集。5.抽象数据对象 ElemSet=某种同类型的数据元素,6.数据结构(data structure)-数据之间的相互关系，即数据的组织形式。内容包括：数据逻辑结构、数据存储结构和数据运算。,数据逻辑结构：数据元素之间的逻辑关系。数据存储结构：数据元素及其关系在存储器中的存储表示。数据运算：定义在数据逻辑结构上的操作。如：查询，插入，删除和修改，排序等。数据逻辑结构有两大类：线性结构：特征：若结构是非空集，则仅有一个开始结点和一个终止结点；其他结点都只有一个前趋结点和一个后继结点。非线性结构：特征：一个结点有多个前趋结点和后继结点。数据存储结构有4种：顺序存储结构，链接存储结构，索引存储结构和散列存储结构。,数据逻辑结构和存储结构与运算三者之间有紧密的关系：如：给定一种数据的逻辑结构，可采取顺序存储结构或 链接存储结构进行存储；按定义的运算和运算性质的不同，施加于同一数据结构 上，则会导致有不同的种类的数据结构产生。如：限制在线性表的一端做插入和删除操作，称该线 性表为栈；若限制在线性表的一端插入，另一端删除操作，称该 线性表为队。其栈和队都有顺序存储结构或链接存储结构，则它们存储结构称为：顺序栈，链式栈，顺序队，链式队。,1.线性表 2.栈 线性结构 3.队列,双队列 4.数组数据结构 5.字符串 非 线 性 1.树,二叉树 结 构 2.图,数据逻辑结构分类,数据顺序存储结构和链式存储结构（物理结构，存储表示,物理表示）,数据结构在计算机存储器中的映象(mapping)。(1)顺序存储结构(向量,一维数组)例.char a5=A,B,C,D；A B C D E 0 1 2 3 4 a是一维数组(2)非顺序存储结构(链接表：指针类型和结构类型定义）例.单链表 data next Head A B C D 4个结点的单链表,7.数据类型（data type)-是一个值的集合和定义在这个值上的一组操作的总称。用数据类型定义数据结构。(1)原子类型(如：int,char,float等)(2)结构类型(如：数组,结构,联合体等）8.抽象数据类型(Abstract Data Type)-与计算机的实现无关的数据类型。形式定义：ADT 抽象数据类型名 1.数据对象；2.数据关系:一个或多个关系；3.一组基本操作/运算 ADT 抽象数据类型名注意：常用DataType表示抽象元素类型。,1.3 算法和算法分析 数据的运算是通过算法描述的。,1.算法-求解一个特定任务的指令的有限序列。例.求a0.n-1中n个数的平均值(假定n0)。float average(float a,int n)int i；float s=0.0；/累加器赋初值 for(i=0；in；i+)s=s+ai；/ai累加到s中 s=s/n；/计算平均值 printf(“ave=%f”,s)；/输出 return(s)；/返回 其中：a,n为输入量；s为输出量。,2.算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。例.i=0；s=0；while(i10)s+；i+；(2)确定性：无二义性。例.x=5；y=10；z=x+y；printf(“%d,%d,%d”,x,y,z)；x+y 解释为：x+(+y)？(x+)+y？,(3)可行性：可以在计算机上实现。for(i=1,s=0；+i)s+；？(4)输入：有0或多个输入量。(5)输出：至少有一个输出量。3.算法设计要求(1)正确性 a.无语法错误；b.对n组输入产生正确结果；c.对特殊输入产生正确结果；d.对所有输入产生正确结果。(2)可读性：“算法主要是为了人的阅读与交流”。(3)健壮性：有出错处理的提示。(4)高效与低存储量,下列描述不符合算法的什么特征和要求？,例1 void suanfa1()int i,s=0；for(i=0；i=0；i+)/死循环 s+；/不能终止 例2 float suanfa2()int x,y；scanf(“%d”,&x)；y=sqrt(x)；/当x0时,出错 return(y)；,4.算法的时间复杂度,衡量算法性能：a.算法正确性；b.执行算法所消耗的时间；c.执行算法所消耗的空间（主要考虑辅存空间）；d.算法易读易理解，易于编码，易于调试等。主要讨论算法执行时间。算法所消耗的时间：算法中每条语句执行时间之和。每条语句执行时间=语句的执行次数一次执行该语句的时间。语句的频度：设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)。问题的规模n：指线性表的长度，多项式的项数，矩阵的阶数，树的结点数，图中的顶点或边数等。注：一次执行语句的时间是很难精确算出的：它与机器的执行速度，编译程序编译质量及运行环境等因素有关。算法所消耗的时间粗略地用算法中语句执行的最大次数来度量。,/求两个n阶方阵的乘积：C=A*B#define n 100int Multiply(int ann,int bnn,int cnn)int j,i,k；语句的频度f(n)(1)for(i=0；in；i+)n+1(2)for(j=0；jn；j+)n(n+1)(3)cij=0；n2(4)for(k=0；kn；k+)n2(n+1)(5)cij=cij+aik*bkj；n3 算法所消耗的时间就是所有语句频度之和T(n):T(n)=2n3+3n2+2n+1 T(n)是矩阵的阶数n的函数。当n，2n3+3n2+2n+1与n3 同阶，即同一数量级。记为：T(n)=O(f(n)=O(n3)即与f(n)中最高的阶相同。,例1 int s；语句的频度f(n)scanf(“%d”,&s)；1 s+；1 printf(“%d”,s)；1 其中：语句频度为：f(n)=f(1)=3 与问题规模n无关的常数。时间复杂度为：T(n)=O(f(n)=O(3)=O(1）O(1)称成为常量阶/常量数量级只要算法的执行时间不随问题规模n增大而增长，即使算法中有上千条语句，其执行的时间只不过是一个较大的常数，算法的时间复杂度仍然是常数阶O(1)。,例2 分析下面的算法,void sum(int a,int n)f(n）int s=0,i；/1次 for(i=0；in；i+)/n次 s=s+ai；/n次 printf(“%d”,s)；/1次 其中：语句频度为：f(n)=1+n+n+1 时间复杂度为：T(n)=O(f(n)=O(2n+2)=O(n）O(n)称成为线性阶/线性数量级一般情况下，对步进循环，只考虑循环体中的语句执行的次数，可忽略步长加1，终值判断，控制转移等成分。,例3 分析下面的算法,1.void sum(int m,int n)2.int i,j,s=0；/1次 3.for(i=1；i=m；i+)/m次 4.for(j=1；j=n；j+)/m*n次 5.s+；/m*n次 6.printf(“%d”,s)；/m次 7.8.其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1 当m=n时,f(n)=2n2+2n+1 T(n)=O(f(n)=O(2n2+2n+1)=O(n2)平方阶。对嵌套层次的循环结构，时间的复杂度T(n)由最内层循环体语句的频度f(n)决定。,例4 分析下面的算法,1.void sum(int n)2.int i,j,s=0；/1次 3.for(i=1；i=n；i+)/n次 4.for(j=1；j=i；j+)/?次 5.s+；/?次 6.printf(“%d”,s)；/n次 7.8.,其中：第4行的次数为 1+2+.+n=n(1+n)/2 第5行的次数为 1+2+.+n=n(1+n)/2 f(n)=1+n+n(n+1)+n=n2+3n+1 T(n)=O(f(n)=O(n2）平方阶例5 有算法：在数组a0.n-1中查找k值：(1)i=n-1;(2)while(i=0 若a中最前一个元素是要找的k，则(3)语句的频度为常数0。在这种情况下，采用最坏的时间复杂度作为算法的时间复杂度：T(n)=0(n),常用时间复杂度递增依次为：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3)K方阶O(nk)，指数阶O(2n)。O(1)算法效率最高，O(2n)算法效率最低。5.算法的空间复杂度 执行算法所需存储空间的大小。也是问题规模n的函数。6.算法的复杂度 包括：算法时间复杂度和算法空间复杂度。,低,高,例6 冒泡排序的C语言算法/对数组a中n个数按递增次序作冒泡排序 1.Void bubble1(int a,int n)2.int i,j,temp；3.for(i=0；iaj+1)/？次 6.temp=aj；/？次 7.aj=aj+1；/？次 8.aj+1=temp；/？次 9.10.for(i=0；in；i+)/n 次 11.printf(“%d”,ai)；/n 次 12.思考：在最好情况下，f(n)=?T(n)=O(f(n)=?在最坏情况下，f(n)=?T(n)=O(f(n)=?,例7 冒泡排序的“类C语言”算法/对数组a中n个数按递增次序作冒泡排序 1.void bubble2(int a,int n)2.for(i=n-1,change=TRUE；i1&change；i-)3.change=FALSE；/change为交换标志 4.for(j=0；jaj+1)6.aj aj+1；/交换元素 7.change=TRUE；/修改交换标志 8.9.10.思考：在最好情况下，f(n)=?T(n)=O(f(n)=?在最坏情况下，f(n)=?T(n)=O(f(n)=?,