数据结构专升本复习

数据结构第一章•数据的三个层次：数据、数据元素、数据项•数据结构的概念：定义、逻辑结构、物理(存储)结构•理解数据类型、抽象数据类型的概念。•算法的概念(算法特性，算法设计要求)•理解时间复杂度、空间复杂度的概念。•数据是对客观事物的符号表示。数据结构相关的基本概念在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。基本概念和术语•数据元素•是数据集合中的一个实体，是计算机程序中加工处理的基本单位。•有两类数据元素：一类是不可分割的原子型数据元素，如：整数5，字符N等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列个数据项组成。•数据结构•简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。•数据结构的形式定义为：DataStructures=(D,S)•其中：D是数据元素的有限集，S是D上关系的有限集。逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构顺序存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。链式存储结构•常见的存储结构•顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；•链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。数据类型和抽象数据类型•数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。•例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。•抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。例如，矩阵的抽象数据类型定义为，矩阵是一个由mn个数排成m行n列的表，它可以进行初等变换、相加、相乘、求逆、……等运算。•抽象数据类型的形式描述为•ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是D的基本操作集。一、算法定义算法（Algorithm）：是对特定问题求解步骤的一种描述，是由若干条指令组成的有限序列，其中每一条指令表示一个或多个操作。它应该满足下列五个重要特性：1、有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。2、确定性算法中每一条指令必须有确切的含义，且执行路径唯一。即对于相同的输入只能得出相同的输出。3、可行性算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4、输入一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。5、输出一个算法有一个或多个的输出，这些输出同输入有着某些特定关系的量。1.2算法描述•二、算法设计的要求：1、正确性算法应满足具体问题的需求。通常算法的正确性可分为四个层次：a.程序不含语法错误;b.程序对于几组输入数据能够得出满足规格说明要求的结果;c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。•二、算法设计的要求：2、可读性算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，晦涩难懂的程序易于隐藏较多错误难以调试和修改。3、健壮性当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。4、效率与低存储需求举例问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：（1）输入x，y，z三个数值；（2）从三个数值中挑选出最小者并换到x中；（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。三、算法复杂性的概念确切地说，算法的复杂性是运行算法所需要的计算机资源的量。需要的时间资源的量称为时间复杂性需要的空间资源的量称为空间复杂性**在算法分析中，通常所说的找到了时间复杂性的级别，是指找到了同样级别的最简单的函数。如：307n2、n2/2、n2都是同一级别的函数，最简单的函数是n2。所以，307n2、n2/2、n2的级别都是O(n2)。f、g同级别：满足：f=O(g)且g=O(f)例１、for(i=1;i=n;++i)for(j=1;j=n;++j){c[i][j]=0;for(k=1;k=n;++k)c[i][j]+=a[i][k]*b[k][j];}•由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3•频度：是指该语句重复执行的次数例２、{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1);如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(i=1;i=n;++i){++x;s+=x;}。课堂练习：求该程序的语句频度及时间复杂度1、for(i=2;i=n;++i)for(j=2;j=i-1;++j){++x;a[i][j]=x;}解答：语句频度为：1+2+3+……+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2/2-3n/2+1∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶。第二章•1、理解ADT表的概念及基本运算。2、掌握表的顺序存储结构及其运算的实现。3、掌握表的链接存储结构及其运算的实现。4、理解单链表、循环链表、双向链表的特点。ADT表•线性结构：结构中的数据元素之间存在一个对一个的关系。–在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。•举例•La=（34，89，765，12，90，-34，22）数据元素类型为int。•Ls=(Hello,World,China,Welcome)数据元素类型为string。•Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：•structbookinfo{•intNo;//图书编号•char*name;//图书名称•char*author;//作者名称•...;•}–线性表的基本操作1.线性表初始化：Init_List(L)2.求线性表的长度：Length_List(L)3.取表元：Get_List(L,i)4.按值查找：Locate_List(L,x)5.插入操作：Insert_List(L,i,x)6.删除操作：Delete_List(L,i)线性表的顺序存储结构–线性表的顺序存储结构•线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：存储地址内存单元...da1d+La2d+2La3...d+(i-1)Lai...d+(n-1)Lan......图2-1线性表顺序存储结构示意图•其中，L为每个数据元素所占据的存储单元数目。•相邻两个数据元素的存储位置计算公式•LOC(ai+1)=LOC(ai)+L•线性表中任意一个数据元素的存储位置的计算公式为：•LOC(ai+1)=LOC(a1)+(i)*L•顺序存储结构的特点•（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；•（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。•在C语言中，实现线性表的顺序存储结构的类型定义•#defineMAXSIZE100//线性表的最大长度•typedefstruct•{datatypedata[MAXSIZE];•intlast;•}SeqList;–2.2.2典型操作的算法实现1.初始化线性表L2.SeqList*init_SeqList()3.{SeqList*L;4.L=malloc(sizeof(SeqList));5.L-last=-1;returnL;6.}•2.在线性表L中第i个数据元素之前插入数据元素X•intInsert_SeqList(SeqList*L，inti，datatypex)•{intj;•if(L-last==MAXSIZE－1)•{printf(＂表满＂);return(-1);}/*表空间已满，不能插入*/•if(i1||iL-last+2)/*检查插入位置的正确性*/•{printf(＂位置错＂);return(0);}•for(j=L-last;j=i-1;j--)•L-data[j+1]=L-data[j];/*结点移动*/•L-data[i-1]=x;/*新元素插入*/•L-last++;/*last仍指向最后元素*/•return(1);/*插入成功，返回*/•}•3.删除操作•intDelete_SeqList(SeqList*L;inti)•{intj;•if(i1||iL-last+1)/*检查空表及删除位置的合法性*/•{printf(＂不存在第i个元素＂);return(0);}•for(j=i;j=L-last;j++)•L-data[j-1]=L-data[j];/*向上移动*/•L-last--;•return(1);/*删除成功*/•}4.在线性表L中检索值为X的数据元素•intLocation_SeqList(SeqList*L,datatypex)•{inti=0;•while(i=L.last&&L-data[i]!=x)•i++;•if(iL-last)return-1;•elsereturni;/*返回的是存储位置*/•}•插入算法的分析•假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析•在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：•分析结论•顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1E线性表的链式存储结构•链表的结点定义•链表的建立•链表的常用的操作模式——指针搜索•链表插入、删除运算•一些特殊的链表线性表的链式存储结构线性表链式存储时结点结构有关结点数据后继结点位置信息数据域指针域线性表的链式存储结构（单链表）^^…..…headhead头结点首结点首结点链表结点的定义structnode{elemtpdata;structnode*next;};typedefstructnode*pointer,*lklist;lklist与pointer并无性质上的区别。通常用lklist来说明链表头指针的类型，而用pointer来说明定位指针或搜索指针的类型链表的基本操作算法单链表的初始化lklistinitiate(lklisth){malloc(h);h-next=0;returnh;}单链表的length函数length(lklisth){k=0;p=h-next;while(p!=0){k=k+1;p=p-next}returnk;}Setup1图解malloc(head);p=head;headpSetup1图解malloc(q);p-next=q;p=qheadqpSetup1图解malloc(q);p-next=q;p=qheadqp链表的建立（带表头结点）lklistsetup1(lklisthead){malloc(head);p=head;scanf(x);while(x!=somevalue){malloc(q);q-d