数据结构 第一章概论

数据结构---------------------------------------------第一章绪论1.1数据结构研究什么？将现实世界中的数据描述及关系表示出来，并存储到计算机内，供用户程序操作。现实世界中的数据描述及关系：4种：离散型，线性结构，层次结构，网状结构。离散数学：研究离散型。数据结构：研究线性结构，层次结构和网状结构。线性结构：线性表表示。层次结构：树形结构表示。网状结构：图结构表示。数据结构研究：数据逻辑结构，存储结构及施加其上的运算。例1L=(20,-5,66,15,44)是一个线性表例2一张登记表DL序号姓名性别年龄1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将记录(record)定义为”结构”(struct)；登记表也是一个线性表。例3家族中父子关系是一种层次结构--树T张一张三张二一张三一张三小张三大张二张四层次结构：部门之间的隶属关系：学校-系-科-班领导和被领导之间领导关系：主席-部长-司长-处长-科长例4无向图GABDCEFG其中：A、B、C等是顶点(vertex),图中任意两个顶点之间都可能有关系。网络结构：电网，电信网，计算机通信网等。1.基本数据结构的定义、特性、运算与算法1.1线性结构：线性表；栈,队列,双队列；数组,串。1.2非线性结构：树,二叉树；图,网络。2.数据结构的存储结构与实现选择存储结构,设计算法3.查找算法：顺序,折半,分块,哈希,二叉排序树等4.排序算法：内部排序,外部排序5.文件6.基本应用与综合应用要求具备的知识：c语言及程序设计，具有一定的程序设计能力。本课程的内容和任务1.2基本概念和术语1.数据（data)----所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。2.数据元素(dataelement)---数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。3.数据项(dataitem)----是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。如:(姓名、年龄)4.数据对象(dataobject)——由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。例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.数据结构(datastructure)----数据之间的相互关系，即数据的组织形式。内容包括：数据逻辑结构、数据存储结构和数据运算。数据逻辑结构：数据元素之间的逻辑关系。数据存储结构：数据元素及其关系在存储器中的存储表示。数据运算：定义在数据逻辑结构上的操作。如：查询，插入，删除和修改，排序等。数据逻辑结构有两大类：线性结构：特征：若结构是非空集，则仅有一个开始结点和一个终止结点；其他结点都只有一个前趋结点和一个后继结点。非线性结构：特征：一个结点有多个前趋结点和后继结点。数据存储结构有4种：顺序存储结构，链接存储结构，索引存储结构和散列存储结构。数据逻辑结构和存储结构与运算三者之间有紧密的关系：如：给定一种数据的逻辑结构，可采取顺序存储结构或链接存储结构进行存储；按定义的运算和运算性质的不同，施加于同一数据结构上，则会导致有不同的种类的数据结构产生。如：限制在线性表的一端做插入和删除操作，称该线性表为栈；若限制在线性表的一端插入，另一端删除操作，称该线性表为队。其栈和队都有顺序存储结构或链接存储结构，则它们存储结构称为：顺序栈，链式栈，顺序队，链式队。1.线性表2.栈线性结构3.队列,双队列4.数组数据结构5.字符串非线性1.树,二叉树结构2.图数据逻辑结构分类数据顺序存储结构和链式存储结构（物理结构，存储表示,物理表示）数据结构在计算机存储器中的映象(mapping)。(1)顺序存储结构(向量,一维数组)例.chara[5]={'A','B','C','D'}；ABCDE01234a是一维数组(2)非顺序存储结构(链接表：指针类型和结构类型定义）例.单链表datanext┌─┬┐┌─┬┐┌─┬┐┌─┬─┐Head─→│A│┼→│B│┼→│C│┼→│D│^│└─┴┘└─┴┘└─┴┘└─┴─┘4个结点的单链表7.数据类型（datatype)---是一个值的集合和定义在这个值上的一组操作的总称。用数据类型定义数据结构。(1)原子类型(如：int,char,float等)(2)结构类型(如：数组,结构,联合体等）8.抽象数据类型(AbstractDataType)----与计算机的实现无关的数据类型。形式定义：ADT抽象数据类型名{1.数据对象；2.数据关系:一个或多个关系；3.一组基本操作/运算}ADT抽象数据类型名注意：常用DataType表示抽象元素类型。1.3算法和算法分析数据的运算是通过算法描述的。1.算法----求解一个特定任务的指令的有限序列。例.求a[0..n-1]中n个数的平均值(假定n0)。floataverage(floata[],intn){inti；floats=0.0；//累加器赋初值for(i=0；in；i++)s=s+a[i]；//a[i]累加到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；i1000000000000；++i)s++；？？？(4)输入：有0或多个输入量。(5)输出：至少有一个输出量。3.算法设计要求(1)正确性a.无语法错误；b.对n组输入产生正确结果；c.对特殊输入产生正确结果；d.对所有输入产生正确结果。(2)可读性：“算法主要是为了人的阅读与交流”。(3)健壮性：有出错处理的提示。(4)高效与低存储量下列描述不符合算法的什么特征和要求？例1voidsuanfa1(){inti,s=0；for(i=0；i=0；i++)//死循环s++；//不能终止}例2floatsuanfa2(){intx,y；scanf(“%d”,&x)；y=sqrt(x)；//当x0时,出错return(y)；}4.算法的时间复杂度衡量算法性能：a.算法正确性；b.执行算法所消耗的时间；c.执行算法所消耗的空间（主要考虑辅存空间）；d.算法易读易理解，易于编码，易于调试等。主要讨论算法执行时间。算法所消耗的时间：算法中每条语句执行时间之和。每条语句执行时间=语句的执行次数×一次执行该语句的时间。语句的频度：设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)。问题的规模n：指线性表的长度，多项式的项数，矩阵的阶数，树的结点数，图中的顶点或边数等。注：一次执行语句的时间是很难精确算出的：它与机器的执行速度，编译程序编译质量及运行环境等因素有关。算法所消耗的时间粗略地用算法中语句执行的最大次数来度量。//求两个n阶方阵的乘积：C=A*B#definen100intMultiply(inta[n][n],intb[n][n],intc[n][n]){intj,i,k；语句的频度f(n)(1)for(i=0；in；i++)n+1(2)for(j=0；jn；j++){n(n+1)(3)c[i][j]=0；n2(4)for(k=0；kn；k++)n2(n+1)(5)c[i][j]=c[i][j]+a[i][k]*b[k][j]；n3}}算法所消耗的时间就是所有语句频度之和T(n):T(n)=2n3+3n2+2n+1T(n)是矩阵的阶数n的函数。当n→∞，2n3+3n2+2n+1与n3同阶，即同一数量级。记为：T(n)=O(f(n))=O(n3)即与f(n)中最高的阶相同。例1{ints；语句的频度f(n)scanf(“%d”,&s)；1s++；1printf(“%d”,s)；1}其中：语句频度为：f(n)=f(1)=3与问题规模n无关的常数。时间复杂度为：T(n)=O(f(n))=O(3)=O(1）O(1)称成为常量阶/常量数量级只要算法的执行时间不随问题规模n增大而增长，即使算法中有上千条语句，其执行的时间只不过是一个较大的常数，算法的时间复杂度仍然是常数阶O(1)。例2分析下面的算法voidsum(inta[],intn)f(n）{ints=0,i；//1次for(i=0；in；i++)//n次s=s+a[i]；//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.voidsum(intm,intn)2.{inti,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+1T(n)=O(f(n))=O(2n2+2n+1)=O(n2)平方阶。对嵌套层次的循环结构，时间的复杂度T(n)由最内层循环体语句的频度f(n)决定。例4分析下面的算法1.voidsum(intn)2.{inti,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)/2f(n)=1+n+n(n+1)+n=n2+3n+1T(n)=O(f(n))=O(n2）平方阶例5有算法：在数组a[0..n-1]中查找k值：(1)i=n-1;(2)while(i=0&&(a[i]!=k))(3)i--;(4)returni;(3)语句的频度不仅问题规模n有关，而且与a数组各元素和k的取值有关。若a中没有要找的k值，(3)语句的频度为f(n)=n;若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.Voidbubble1(inta[],intn)2.{inti,j,temp；3.for(i=0；i=n-2；i++)//？次4.for(j=0；j=n-2-i；j++)//？次5.if(a[j]a[j+1])//？次6.{temp=a[j]；//？次7.a[j]=a[