数据结构学习指导(每章习题).pdf

教据辂构学习捐导目录第 1章 概 述.4讲课提要.4学习指导.4习 题 1.7习 题 1参考答案.10第 2 章 线 性 表.11讲课提要.11学习指导.12习题2.16习题2 参考答案.20第 3 章 串.27讲课提要.27学习指导.27习题3.29习题3 参考答案.31第 4 章 数组和广义表.33讲课提要.33学习指导.33习题4.37习题4 参考答案.40第 5 章 树.41讲课提要.41学习指导.42习题5.51习题5 参考答案.55第 6 章 图.61讲课提要.61学习指导.62习题6.70习题6 参考答案.75第 7 章 查 找.81讲课提要.81学习指导.81习题7.89习题7 参考答案.91第 8 章 内 部 排 序.94-2-讲课提要.94学习指导.95习题8.103习题8 参考答案.106-3第 1 章 概 述讲课提要【主要内容】1.数据结构的研究目的和研究内容2.数据结构中的几个重要概念和术语3.算法设计的基本要求以及算法复杂度的分析和计算方法【教学目标】1.了解数据结构的研究目的和研究内容2.掌握数据结构中的重要概念和术语3.掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2 次课。第一次课1.数据结构的研究目的和研究内容2.数据结构中的重要概念和术语 第二次课3.算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1.概念和术语 数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的个子集。数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集4口。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。-4-算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。2.逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：(1)集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。(2)线性结构：结构中的数据元素之间存在一个对一个的关系。(3)树型结构：结构中的数据元素之间存在一个对多个的关系。(4)图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3 .数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。(1)顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。(2)链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储结构的基础h,又可延伸变化出另外两种存储结构，即索引存储和散列存储。(1)索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索弓I,可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。(2)散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一 对应的目的。这样，查找时同样可大大提高效率。4 .数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。5 .算法的五个重要特征(1)有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。(2)确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。(3)可行性：每一个操作步骤都必须在有限的时间内完成。(4)输入：一个算法可以有一个或多个输入，也可以没有输入。(5)输出：一个算法可以有个或多个输出。没有输出的算法是没有实际意义的。6 .算法的评价标准(1)正确性。(2)易读性。(3)高效性。(4)可维护性。7 .算法分析的目的算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间(内存)较为充足，所以把算法的时间复杂度分析作为重点。58.算法的时间复杂度分析(1)算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。(2)算法运行时间的分析规则通常把一个程序的运行时间定义为一个T (n),其中n是该程序输入数据的规模，而不是某一个具体的输入。T(n)的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：T(n)=O(f(n),其中f(n)表示数据输入规模。常见的算法时间复杂度的形式按性能降序的排列如下：0 O(l o g2)O (n)O(n*l o g2/?)O(n*2)O(/?3)O(2n)【例 1-1】分析以下程序段的时间复杂度。一 1 J1 +8 x=-2f b r(i=O;i n;i+)f b r(j=O;j m;j+)A i U =O；解：该程序段的时间复杂度为O(m*n)。【例 1-2】分析以下程序段的时间复杂度。i=s=O;w h i l e(s n)i+；s+=i;解：语句为赋值语句，其执行次数为1 次，所以其时间复杂度为0(1)。语句和语句构成w h i l e 循环语句的循环体，它们的执行次数由循环控制条件中s 与 n的值确定。假定循环重复执行x次后结束，则语句和语句各重复执行了 x次。其时间复杂度按线性累加规则为O(x)。此时s 与 n满足关系式：s n,而 s=l+2+3+x。所以有：1+2+3+x N n,可以推出：=31 +2 24X 与 n 之间满足x=f()，所以循环体的时间复杂度为0()，语句与循环体由线性累加规则得到该程序段的时间复杂度为0()。【例 1-3】分析以下程序段的时间复杂度。i=l;w hil c(i=n)i=2*i;解：其中语句的执行次数是1,设语句的执行次数为f(n),则有：-6-得：T(n)=O(log2n)【例 1-4】有如下递归函数fac t(n),分析其时间复杂度。fact(int n)if(n=l)retum(I);elseretum(n*fact(n-l);解：设 fact(n)的运行时间函数是T(n)。该函数中语句的运行时间是0(1),语句的运行时间是T(n-1)+O(1),其中0 为常量运行时间。由此可得fhct(n)的时间复杂度为0(n)。9.算法空间复杂度的含义空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间；算法输入输出数据所占用的存储空间；算法运行过程中临时占用的存储空间。考虑个算法的空间复杂度时，要综合分析这三个方面的因素。通常记作：S(n)=0(f(n),其中n 为问题的规模(或大小)。习题1一、单项选择题I.数据结构是指()。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称 之 为()。A.存储结构 B.逻辑结构C.链式存储结构 D.顺序存储结构3.树形结构是数据元素之间存在一种()A.一对一关系 B.多对多关系C.多对一关系 D.一对多关系4.设语句x+的时间是单位时间，则以下语句的时间复杂度为()for(i=l;i=n;i+)fbr(j=i;j=n;j+)x+;A.0(1)B.0(n2)C.0(n)D.0(n3)5.算法分析的目的是(I),算法分析的两个主要方面是(2)o(1)A.找H I 数据结构的合理性C.分析算法的效率以求改进(2)A.空间复杂度和时间复杂度C.可读性和文档性6.计算机算法指的是(1),它具备输入,(1)A.计算方法C.解决问题的有限运算序列(2)A.可行性，可移植性和可扩充性C.确定性，有穷性和稳定性B.研究算法中的输入和输出关系D.分析算法的易懂性和文档性B.正确性和简明性D.数据复杂性和程序复杂性输 出 和(2)等五个特性。B.排序方法D.调度方法B.可行性，确定性和有穷性D.易读性，稳定性和安全性7 .数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要()。A.低 B.高 C.相同 D.不好说8 .数据结构作为一门独立的课程出现是在()年。A.1 9 4 6 B.1 9 5 3 C.1 9 6 4 D.1 9 6 89 .数据结构只是研究数据的逻辑结构和物理结构，这种观点()oA.正确 B.错误C.前半句对，后半句错 D.前半句错，后半句对1 0 .计算机内部数据处理的基本单位是()。A.数据 B.数据元素 C.数据项 D.数据库二、填空题1 .数据结构按逻辑结构可分为两大类，分别是 和。2.数据的逻辑结构有四种基本形态，分别是、和。3 .线性结构反映结点间的逻辑关系是 的，非线性结构反映结点间的逻辑关系是 的。4 .一个算法的效率可分为 效率和 效率。5 .在树型结构中，树根结点没有 结点，其余每个结点的有且只有个前趋驱结点；叶子结点没有 结点；其余每个结点的后续结点可以 o6 .在图型结构中，每 个 结 点 的 前 趋 结 点 数 和 后 续 结 点 数 可 以。7 .线性结构中元素之间存在 关系；树型结构中元素之间存在关系；图型结构中元素之间存在 关系。8 .下面程序段的时间复杂度是。f b r(i=0;i n;i+)f o r(j=0;j n;j+)A i 皿=0;9 .下面程序段的时间复杂度是。-8-i=s=O;w h i l e(s n)i+；s+=i;10.下面程序段的时间复杂度是 os=0;f b r(i=O;i n;i+)f o r(j=O j n;j-H-)s+=B i U ；s u m=s;H.下面程序段的时间复杂度是 oi=l；w h i l e(i =n)i=i*3;1 2.衡量算法正确性的标准通常是。1 3 .算法时间复杂度的分析通常有两种方法，即 和 的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;f b r(i=l;i v n;i+)f b r(j=i+I i j =n;j-H-)x+;2.x=0;f b r(i=l;i n;i 4-+)f b r(j=l;j =n-i;j-H-)X+；3.i n t i j,k;f b r(i=O;i n;i-H-)f b r(j=O;j =n;j-H-)c i U =O;f o r(k=0;k =0)&A i !=k)j-；r e t u r n (i);5.fact(n)if(n B 7.B 8.D 9.B 10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4.时间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.0(n2)9.O(Vn)10.O(n2)11.O(log3n)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题l.O(n2)2.0(/)3.0(1?)4.0(n)5.O(n)-10-第 2 章 线 性 表讲课提要【主要内容】i .线性表的概念和基本运算2.顺 序 表（线性表的顺序存储结构）3 .链 表（线性表的链式存储结构）（1）单链表和循环单链表（2）双向链表和循环双链表4 .线性表应用（1）栈（2）队列【教学目标】1 .了解线性表的概念及其常用运算2.熟悉顺序表的结构及基本算法描述3 .掌握单链表的结构及基本算法描述，了解双向链表及循环链表4 .掌握栈和队列的结构特点及其插入和删除算法5 .了解栈在程序设计中的实际应用【所需课时】7次课。第一次课1 .线性表的定义及其运算2.顺序表的存储结构 第二次课3 .顺序表的基本运算4 .顺序表的算法描述及算法分析 第三次课5.单链表的结构及其算法实现6 .循环单链表的结构及其算法实现 第四次课7 .双向链表的结构及其算法实现8 .循环双链表的结构及其算法实现 第五次课9 .栈的定义及其结构特点-11-10.顺序栈的结构及其算法实现 第六次课11.链栈的结构及其算法实现12.栈的应用 第七次课13.队列的定义及顺序存储14.队列的链式存储学习指导1.线性表的定义线性表是n 个数据元素的有限序列，其中n(n 2 0)为线性表的长度。线性表中各个元素的类型相同。对于线性表(ap a?,，由，an)而言，数据元素药没有直接前趋，a”没有直接后继，表中的其它元素a(2W iW n-l)有且仅一个直接前趋如和直接后继ai+i。2.顺序表顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。在 C 语言中可用一维数组来表示。在顺序表中，以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。顺序表是一种随机存储结构，只要确定了存储顺序表的起始位置，则表中任一元素都可以随机存取。所以在顺序表中可以方便的进行数据元素的查找及存取。但是在进行插入和删除操作时，将会引起元素的大量移动，因而效率比较低，并且易产生空间浪费或“上溢”现象。顺序表的操作还应注意元素的存储位置，即数组下标(C 语言中下标从0 开始)。【例 2-1 试编写出将两个顺序存储的有序表A和 B合成一个有序表C 的算法。解：假设A、B 和 C 的类型为下述SqList类型：#define maxlen 1000typedef int elemtypetypedef struct elemtype elem maxlen;int len;SqList;设 A 和 B 的数据元素均为整数且为升序排列，设 A 的长度为m,B 的长度为n,则合并后C 的长度为m+n合并时进行A、B 元素的比较，将较小的链入C 中，算法描述如下:int merge(SqList*A,SqList*B,SqList*C)将两个有序表 A 和 B 合成一个有序表 C int m,n,i,j,k;m=(*A).len;n=(*B).1en;if(m+nmaxlen-1)-12-printfCoverflow*);exit(0);i=0;j=0;/i和j分别作为扫描顺序表A和B的指针k=0;/k指示顺序表C中当前位置while(i=m)&(j=n)if(*A).elemi=(*B).elemj)(*C).elemk=(*A)elemi;i+;k+;)else(*C).elemk=(*B)elemj;j+；k+;)while(i=m)表B已结束，表A没有结束，链入表A的剩余部分(*C).elemk=(A).elemi;i+;k+;)while(jnext;q-next=head;head=q;【例 2-3假设有一个循环链表的长度大于1,且表中既无头结点也无头指针，已知p 为指向链表中某结点的指针，设计在链表中删除p 所指结点的前趋结点的算法。解：可引入一个指针q 当 q-ncxt=p时，说明此时q 所指的结点为p 所指结点的前趋结点，从而可得算法如下：void delete(LinkList*p)(在链表中删除p 所指结点的前趋结点LinkList*q,*t;q=p；while(q-next-next!=p)/q-next 不是 p 的前趋结点-14-q=q-next;t=q-next;t 指向要删除结点q-next=p;删除t 结点free(t);)【例 2-4试设计实现删除单链表中值相同的多余结点的算法。解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。设单链表(其类型为LinkList)的头指针head指向头结点，则可按下列步骤执行：首先，用一个指针p 指向单链表中第一个表结点，然后用另一个指针q 查找链表中其余结点元素，由于是单链表，故结束条件为p=N U LL,同时让指针s 指向q 所指结点的前趋结点，当查找到结点具有q-data=p-data时删除q 所指的结点，然后再修改q,直到 q 为空；然后使p 指针后移(即p=p-next),重复进行，直到p 为空时为止。算法描述如下：del(LinkList*head)(删除单链表中值相同的多余结点LinkList*p,*s,*q;p=head-next;while(p!=NULL&p-next!=NULL)S=p;s 指向要删除结点的前趋q=p-next;while(q!=NULL)if(q-data=p-data)查找值相I司的结点并删除 s-next=q-next;free(q);q=s-next;else s=q;q=q-next;)p=p-ncxt;4.栈栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为栈顶(T o p),而另一端称为栈底(Bottom)。表为空时称为空栈。在栈-15-上的主要运算是入栈和出栈。栈中元素如果按a”a 2,，a”的顺序进栈，则出栈顺序为an,&n，,a i o 因此，栈又称为 后进先出（L a s t I n F i rs t O u t）的线性表,简称L I F O表。同线性表相似，栈也有顺序栈和链栈两种存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。另外，注意对栈的操作只能在栈顶进行。5.队列队 列（Q u e u e）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表通常把允许插入的一端称为队尾（re a r）,允许删除的一端称为队头（f ro n t）。队列中元素如果按a”a2,，a”的顺序进队，则出队的顺序仍为a”a2,-a”因此，队列又称为“先进先出”（F i rs t I n F i rs t O u t）的线性表,简称F I F O 表 队列也有顺序队列和链队列两种存储结构。在顺序队列中，为避免“假满”现象，一般采用循环队列（即首尾相接）。链队列会因为队满而产生“上溢”现象。习题2一、单项选择题1 .线性表是。A.一个有限序列，可以为空 B.一个有限序列，不可以为空C.一个无限序列，可以为空 D.一个无限序列，不可以为空2 .在一个长度为n的顺序表中删除第i 个元素（X=i =n）时，需向前移动一个元素。A.n-i B.n-i+1 C.n-i-1 D.i3 .线性表采用链式存储时，其地址 oA.必须是连续的 B.一定是不连续的C.部分地址必须是连续的 D.连续与否均可以4 .从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 个元素结点。A.n/2 B.n C.（n+1）/2 D.（n-1）/25 .在双向循环链表中，在 p所指的结点之后插入s 指针所指的结点，其操作是oA.p-n e x t=s;s-p r i o r=p;p-n e xt-p r i o r=s;s-n e xt=p-n e xt;B.s-p r i o r=p;s-n e xt=:p-n e xt;p-n e xt=s;p-n e xt-p r i o r=s;C.p-n e xt=s;p-n e xt-p r i o r=s;s-p r i o r=p;s-n e xt=p-n e xt;D.s-p r i o r=p;s-n e xt=p-n e xt;p-n e xt-p r i o r=s;p-n e xt=s;6 .设单链表中指针p指向结点m,若要删除m之后的结点（若存在），则需修改指针-16-的操作为 OA.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;7.在一个长度为n 的顺序表中向第i 个元素（Ov i n+l）之前插入一个新元素时，需向后移动 个元素。A.n-i B.n-i+l C.n-i-l D.i8.在一个单链表中，已知q 结点是p 结点的前趋结点，若在q 和 p 之间插入s 结点，则须执行A.s-next=p-next;p-next=sB.q-next=s;s-next=pC.p-next=s-next;s-next=pD.p-next=s;s-next=q9.以下关于线性表的说法不正确的是 oA.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。10.线性表的顺序存储结构是种 的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取11.在顺序表中，只要知道,就可在相同时间内求出任一结点的存储地址。A.基地址 B.结点大小C.向量大小 D.基地址和结点大小12.在等概率情况下，顺序表的插入操作要移动 结点。A.全部 B.一半C.三分之一 D.四分之一，13.在 运算中，使用顺序表比链表好。A.插入 B.删除C.根据序号查找 D.根据元素值查找14.在一个具有n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是。A.0（1）B.0（n）C.0（n2）D.O（log2n）15.设有一个栈，元 素 的 进 栈 次 序 为 A,B,C,D,E,下列是不可能的出栈序列A.A,B,C,D,E B.B,C,D,E,AC.E,A,B,C,D D.E,D,C,B,A16.在一个具有n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为。-17-A.top 不变 B.top=0 C.top-D.top+17.向一个栈顶指针为h s的链栈中插入个s 结点时，应执行 oA.hs-next=s;B.s-next=hs;hs=s;C.s-next=hs-next;hs-next=s;D.s-next=hs;hs=hs-next;18.在具有n 个单元的顺序存储的循环队列中，假定front和 rear分别为队头指针和队尾指针，则判断队满的条件为 oA.rear%n=front B.(front+1)%n=rearC.rear%n-1=front D.(rear+1)%n=front19.在具有n 个单元的顺序存储的循环队列中，假定front和 rear分别为队头指针和队尾指针，则 判 断 队 空 的 条 件 为。A.rear%n=front B.front+l=rearC.rear-=front D.(rear+1)%n=front20.在一个链队列中，假定front和 rear分别为队首和队尾指针，则删除一个结点的操作为A.front=front-next B.rear=rear-nextC.rear=front-nextD.front=rear-next二、填空题1.线性表是一种典型的 结构。2.在一个长度为n 的顺序表的第i 个元素之前插入一个元素，需要后移一个元素。3.顺 序 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置。4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 一个位置，移动过程是从 向 依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 决定的。6.在双向链表中，每个结点含有两个指针域，一个指向 结点，另一个指向_ _ _ _ _ _ _ 结点。三一当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置 相邻，单链表中逻辑上相邻的元素，物理位置 相邻。9.线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 位置插入和删除元素；对于队列只能在 位置插入元素和在位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为和;而根据指针的联接方式，链表又可分为 和。11.在 单 链 表 中 设 置 头 结 点 的 作 用 是。-18-12.对于一个具有n 个结点的单链表，在已知的结点p 后插入一个新结点的时间复杂度为,在给定值为x 的结点后插入一个新结 点 的 时 间 复 杂 度 为 13.对于一个栈作进栈运算时，应 先 判 别 栈 是 否 为,作退栈运算时，应先判别栈是否为,当栈中元素为m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为=为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样只有当时才产生上溢。14.设有一空栈,现有输入序列 1,2,3,4,5,经过 push,push,pop,push,pop,push,push后，输出序列是 o15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为。三、简答题1.描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n 个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么？6.假定有四个元素A,B,C,D 依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功能是什么？LinkList*Demo(LinkList*L)/L 是无头结点的单链表LinkList*q,*p;if(L&L-next)q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;)retum(L);四、算法设计题1.设计在无头结点的单链表中删除第i 个结点的算法。2 .在单链表上实现线性表的求表长L i s t L e n g t h(L)运算。3 .设计将带表头的链表逆置算法。4 .假设有一个带表头结点的链表，表头指针为h e a d,每个结点含三个域：d a t a,n e x t和 p r i o r 其中d a t a 为整型数域，n e x t 和 p r i o r 均为指针域。现在所有结点已经由n e x t 域连接起来，试编一个算法，利用p r i o r 域(此域初值为N U L L)把所有结点按照其值从小到大的顺序链接起来。5 .已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于m i n 且小于m a x 的元素(若表中存在这样的元素)的算法。6 .已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于m a x 但大于m i n 的元素的算法。7 .假定用一个单循环链表来表示队列(也称为循环队列)，该队列只设一个队尾指针,不设队首指针，试编写下列各种运算的算法：(1)向循环链队列插入一个元素值为x的结点：(2)从循环链队列中删除一个结点。8 .设顺序表L是一个递减有序表，试写一算法，将 x 插入其后仍保持L的有序性。习题2 参考答案一、单项选择题1.A 2.A 3.D 4.C 5.D 6.A 7.B 8.B 9.C 1 0.A 11.D 12.B13.C 14.B 15.C 16.C 17.B 18.D 19.C 2 0.A二、填空题1.线性2 .n-i+13 .相邻4 .前移，前，后5 .物理存储位置，链域的指针值6 .前趋，后继7 .顺 序,链接8 .一定，不一定9 .线性，任何，栈顶，队尾，队头10 .单链表，双链表，非循环链表，循环链表11.使空表和非空表统一；算法处理一致12 .0(1),0(n)13 .栈 满，栈空，m,栈底，两个栈的栈顶在栈空间的某一位置相遇14 .2、3-20-15.0(1)三、简答题1.头指针是指向链表中第一个结点(即表头结点)的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2.线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3.应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4.应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构,而链表则是一种顺序存取的存储结构。5.设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针 为 re a r,则开始结点和终端结点的位置分别是rear-next-next和 r e a r,查找时间都是 0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。6.共 有 14种可能的出栈序列，即为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA7.在队列的顺序存储结构中，设队头指针为fh)n t,队尾指针为re a r,队列的容量(即存储的空间大小)为maxnumo 当有元素要加入队列(即入队)时，若 rear=maxnum,则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。般地，要解决队列的上溢现象可有以下几种方法：(1)可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低,浪费存储空间。(2)要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是-个首尾相接的循环队列，即用循-21-环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8.该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1.算法思想为：(1)应判断删除位置的合法性，当in-l时，不允许进行删除操作；(2)当i=0时，删除第一个结点：(3)当0ivn时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：dclctc(LinkList*q,int i)(在无头结点的单链表中删除第i 个结点LinkList*p,*s;int j;if(inext;free(s);)else j=0；s=q;while(jnext;j+；)if(s=NULL)printffantt delete);else p-next=s-next;free(s);2.由于在单链表中只给出个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength(LinkList*L)-22-求带头结点的单链表的表长int len=O;ListList*p;P=L;while(p-next!=NULL)p=p-next;len+;)return(len);3.设单循环链表的头指针为head,类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q 结点的指针域时，设 s 指向其原前趋结点，p 指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：void invert(Link List*head)/逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head-next;while(p!=head)/当表不为空时，逐个结点逆置 s=q;q=p;p=p-next;q-next=s;p-next=q;)4.定义类型LinkList如下:typedef struct node int data;struct node*next,*prior;LinkList;此题可采用插入排序的方法，设 p 指向待插入的结点，用 q 搜索已由prior域链接的有序表找到合适位置将p 结点链入。算法描述如下：insert(LinkList*head)LinkList*p,*s,*q;p=head-next;/p指向待插入的结点，初始时指向第一个结点whilc(p!=NULL)s=head;/s 指向 q 结点的前趋结点-23-q=head-prior;/q指向由prior域构成的链表中待比较的结点while(q!=NULL)&(p-dataq-data)杳找插入结点p 的合适的插入位置 s=q;q=q-prior;)s-prior=p;p-prior=q;/结点p 插入到结点s 和结点q 之间p=p-next;|5.算法描述如下：delete(LinkList*head,int max,int min)linklist*p,*q;if(head!=NULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;)while(p!=NULL)&(p-datanext;q-next=p;6.算法描述如下：dclctc(LinkList*hcad,int max,int min)LinkList*p,*q;q=hcad;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;else q-ncxt=p-ncxt;free(p);-24-p=q-next;7.本题是对一个循环链队列做插入和删除运 算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：(1)插 入(即入 队)算 法：insert(LinkList*rear,elemtype x)(设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList);if(rear=NULL)/如为空队，建立循环链队列的第一个结点 rear=p;rear-next=p;链接成循环链表else 否则在队尾插入p 结点 p-next=rear-next;rear-next=p;rear=p;(2)删 除(即 出 队)算 法：delete(LinkList*rear)(设循环链队列的队尾指针为rearif(rear=NULL)/空队printfC，underflownn);ifl；rear-next=rear)队中只有一个结点rcar=NULL;elsercar-ncxt=rcar-ncxt-ncxt;/rcar-ncxt指向的结点为循环链队列的队头结点)8.只要从终端结点开始往前找到第一 个 比 x 大(或相等)的结