数据结构-复习与习题解析(1)

数据结构与算法复习与习题解析(第1-5讲）第一讲绪论了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）13/12/20192数据结构的定义按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。基本概念和术语【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个子集。13/12/20194【数据结构】相互之间存在一种或多种特定关系的数据元素的集合计算机如何解决问题13/12/20195问题机外表示处理要求逻辑结构基本运算数学模型存储结构编程实现实现建模求精研究数据结构是为了帮计算机解决问题！数据结构的研究内容13/12/20196【数据结构的三个方面研究内容】具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）。数据的逻辑结构（面向人类）数据的存储结构（面向计算机）数据的运算（操作）：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构散列存储索引存储串及数组四种基本逻辑结构13/12/20197【集合】——数据元素间除了“同属于一个集合”外，无其他关系。【线性结构】——1对1的关系比如线性表、栈、队列。【树形结构】——1对多的关系比如树。【图形结构】——多对多的关系比如图。算法与数据结构算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。“算法+数据结构=程序”算法!=程序算法是供人阅读的，程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性算法的概念算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。13/12/20199（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。算法的性质算法设计的要求正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低13/12/201911算法效率的度量方法事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进行估算。m=f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件13/12/201912算法时间复杂度13/12/201913在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，用“大O记法”记作：T(n)=O(f(n))。由此得到的T(n)的数量级叫“大O阶”。它表示随问题规模n的增大，算法执行时间增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。一般情况下，T(n)增长越慢，算法越优。大O阶的数学定义当n→∞时，有f(n)/g(n)=常数≠0，则称函数f(n)与g(n)同阶,或者说，f(n)与g(n)同一个数量级，记作f(n)=O(g(n))称上式为算法的时间复杂度,或称该算法的时间复杂度为O(g(n))。其中,n为问题的规模(大小)的量度。若lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)=2n→∞n→∞则算法的时间复杂度为O(n3)算法空间复杂度13/12/201915算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。我们主要讨论时间复杂度问题。例题解析【例1】数据元素之间的关系在计算机中有几种表示方法？各有什么特点？答：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。13/12/201916例题解析【例2】有下列运行时间函数：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间答：(1)O(1)(2)O(n2)(3)O(n3)13/12/201917例题解析【例3】已知如下程序段for(i=n;i0;i--){{语句1}x=x+1;{语句2}for(j=n;j=i;j--){语句3}y=y+1;{语句4}}语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。答：（1）n+1（2）n（3）n(n+3)/2（4）n(n+1)/2第二讲线性表线性结构的定义和特点在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是线性表。线性表的存储方法顺序存储：逻辑上相邻物理上一定相邻链式存储：逻辑上相邻物理上不一定相邻顺序表顺序表——线性表的顺序存储表示顺序存储——用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。（逻辑上相邻物理上一定相邻）LOC(ai)=LOC(a1)+(i-1)len（a1为首元素，len为单个元素占用空间长度）顺序存储的优点可以随机存取表中任一元素O(1)；存储空间使用紧凑顺序存储的缺点在插入元素时平均需要移动n/2个元素，删除某一元素时，平均需要移动n-1/2个元素。算法的平均时间复杂度为O(n)预先分配空间需按最大空间分配，利用不充分;表容量难以扩充13/12/201920链表链式存储结构特点用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。链式存储结构的缺点：每个结点的指针域需额外占用存储空间。当数据域所占字节不多时，指针域所占存储空间的比重显得很大。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度O（n）不便于在表尾插入元素：需遍历整个表才能找到位置。13/12/201921例题解析【例1】说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。13/12/201922例题解析【例2】设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/{inti;if(va.lengthMAXSIZE)return;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/13/12/2019231.#defineMAXSIZE1002.typedefstruct{3.ElemType*elem;4.intlength;5.}SqList；例题解析【例3】设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。答：q=p-next;p-next=q-next;free(q);13/12/201924例题解析【例4】设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作。答：设单链表的头结点的头指针为head,且pre=head；while(pre-next!=p)pre=pre-next;s-next=p;pre-next=s;13/12/201925例题解析【例5】试编写在带头结点的单链表中删除（一个）最小值结点的算法。voiddelete（Linklist&L）答：[题目分析]本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。voiddelete（LinkedList&L）{∥L是带头结点的单链表p=L-next；∥p为工作指针。指向待处理的结点。假定链表非空。pre=L；∥pre指向最小值结点的前驱。q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。while（p-next!=null）{if（p-next-dataq-data）{pre=p；q=p-next；}∥查最小值结点p=p-next；∥指针后移。}pre-next=q-next；∥从链表上删除最小值结点free（q）；∥释放最小值结点空间}∥结束算法delete。13/12/201926例题解析【例6】一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为–1。voidderiv