数据结构学习指导.pdf

《数据结构学习指导.pdf》由会员分享，可在线阅读，更多相关《数据结构学习指导.pdf（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据辂构学习相导主 编孙凌李丹副 主 编 王 桂 芝 周 琳 高 大 利前 言本书是与教材 数据结构配套的教学辅导书，共分8章，顺 序 与 数据结构教材前8章的顺序一致。内容包括各章的讲课提要、学习指导、习题及参考答案。编者根据多年的教学积累，对各章的知识要点进行归纳和总结，精心编写了近一百道例题和近四百道练习题，覆盖了本课程的全部教学内容。本书不仅可供学生进行学习辅导，也可供教师教学参考。通过阅读本书，将有助于学生加深对基础理论知识的理解，更可以通过大量的练习培养学生实际应用的能力.特别要提醒的是，本书每章练习均配有参考答案，希望读者合理使用参考答案，尽量不要在解题之前先看答案，以免干扰自己

2、的思考过程。对于每个算法设计题来说，解题方法往往有许多种，参考答案中给出的不一定是最好的。本书第1章、第3章和第4章由周琳编写；第2章由王桂芝编写；第5章由李丹编写;第6章由高大利编写：第7章和第8章由孙凌编写。李丹负责统编全稿。本书在编写过程中力求概念清晰，表述正确，通俗易懂，便于自学。由于时间仓促，且作者水平有限，书中可能会有一些错误，恳请读者批评指正。作者2005年7月-2-目 录第1章 概 述.5讲课提要.5学习指导.5习题1.8习 题1参考答案.11第2章 线 性 表.12讲课提要.12学习指导.13习题2.17习题2参考答案.21第3章 串.28讲课提要.28学习指导.28习题3.

3、30习题3参考答案.32第4章 数组和广义表.34讲课提要.34学习指导.34习题4.38习题4参考答案.41第5章 树.42讲课提要.42学习指导.43习题5.52习题5参考答案.56第6章 图.62讲课提要.62学习指导.63习题6.71习题6参考答案.76第7章 查 找.82讲课提要.82学习指导.82习题7.90习题7参考答案.92第8章 内 部 排 序.95-3-讲课提要.95学习指导.96习题8.104习题8 参考答案.107-4-第 1 章 概 述讲课提要【主要内容】1.数据结构的研究目的和研究内容2.数据结构中的几个重要概念和术语3.算法设计的基本要求以及算法复杂度的分析和计算

4、方法【教学目标】1.了解数据结构的研究目的和研究内容2.掌握数据结构中的重要概念和术语3.掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2 次课。第一次课1.数据结构的研究目的和研究内容2.数据结构中的重要概念和术语 第二次课3.算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1.概念和术语 数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。数据结构：是数据元素的组织形式，或数据元素相

5、互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，乂称物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。-5-算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。2 .逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：(1)集合：结构中的数据元素间除了“同属于个集合”的关系外，别无其它关系。(2)线性结构：结构中的数据元素之间存在一个对一个的关系。(3)树型结

6、构：结构中的数据元素之间存在一个对多个的关系。(4)图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3.数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。(1)顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。(2)链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。(1)索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索弓I，可以把一个顺序表分成几

7、个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。(2)散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可大大提高效率。4 .数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。5 .算法的五个重要特征(1)有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。(2)确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。(3)可行性：每一个操作步骤都必须在有限的时间内完成。(4)输入：一个算法可以有一个或多个输入，也可以没有输入

8、。(5)输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。6 .算法的评价标准(1)正确性。(2)易读性。(3)高效性。(4)可维护性。7 .算法分析的目的算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的H的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间(内存)较为充足，所以把算法的时间复杂度分析作为重点。-6-8.算法的时间复杂度分析(1)算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。(2)算法运行时间的分析规则通常把个程序的运行时间定义为一个T (n)

9、,其中n是该程序输入数据的规模，而不是某一个具体的输入。T(n)的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：T(n)=O(f(n),其中f(n)表示数据输入规模。常见的算法时间复杂度的形式按性能降序的排列如下：O(l)O(l o g2n)O(n)O(n*l o g27 i)O(n2)O(n3)O(2n)【例 1-1】分析以卜程序段的时间复杂度。f o r(i=0;i n;i+)f o r(j=0;j m;j+)A i j =O;解：该程序段的时间复杂度为O(m*n)。【例 1-2】分析以下程序段的时间复杂度。i=s=O;w h i l e(s n)i+；s+=i;

10、)解：语句为赋值语句，其执行次数为I 次，所以其时间复杂度为0(1)。语句和语句构成W h i l e 循环语句的循环体，它们的执行次数由循环控制条件中s 与 n的值确定。假定循环重复执行x次后结束，则语句和语句各重复执行了 x次。其时间复杂度按线性累加规则为0(x)。此时s 与 n满足关系式:s 与n,而 s=l+2+3+x。所以有：1+2+3+x n,可以推出：一1 J l +8 1 ,X=-=2 2X 与 n之间满足x=f()，所以循环体的时间复杂度为0(五)，语句与循环体由线性累加规则得到该程序段的时间复杂度为0()。【例 1-3】分析以下程序段的时间复杂度。i=l；w h i l e

11、(i =n)i=2*i;解：其中语句的执行次数是1，设语句的执行次数为f(n),则有：-7-得:T (n)=O(l o g2n)【例 1-4】有如下递归函数f act(n),分析其时间复杂度。fact(int n)if(n=l)retum(l);return(n*fact(n-l);)解：设 f act (n)的运行时间函数是T(n)。该函数中语句的运行时间是0(1),语句的运行时间是T(n-1)+O(l),其中0(1)为常量运行时间。由此可得f act (n)的时间复杂度为0(n)。9.算法空间复杂度的含义空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用

12、的存储空间主要分为三部分：算法源代码本身占用的存储空间；算法输入输出数据所占用的存储空间；算法运行过程中临时占用的存储空间。考虑一个算法的空间复杂度时，要综合分析这三个方面的因素。通常记作：S(n)=0(f(n),其中n为问题的规模(或大小)。习题1一、单项选择题1 .数据结构是指()。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义2 .数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称 之 为()。A.存储结构 B.逻辑结构C.链式存储结构 D.顺序存储结构3.树形结构是数据元素之间存在一种()。A.一对一-关系 B.多对多关系C.多对一关系 D.一对多关系4.设

13、语句x+的时间是单位时间，则以下语句的时间复杂度为()。for(i=l;i=n;i+)for(j=i;j=n;j+)A.0(1)B.0(n2)C.0(n)D.0(n3)-8-5.算法分析的目的是(1),算法分析的两个主要方面是(2)。(1)A.找出数据结构的合理性C.分析算法的效率以求改进(2)A.空间复杂度和时间复杂度C.可读性和文档性6.计 算机算法指的是(1),它具备输入,(1)A.计算方法C.解决问题的有限运算序列(2)A.可行性，可移植性和可扩充性C.确定性，有穷性和稳定性B.研究算法中的输入和输出关系D.分析算法的易懂性和文档性B.正确性和简明性D.数据复杂性和程序复杂性输 出 和

14、(2)等五个特性。B.排序方法D.调度方法B.可行性，确定性和有穷性D.易读性，稳定性和安全性7 .数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要()oA.低 B.高 C.相同 D.不好说8 .数据结构作为一门独立的课程出现是在()年。A.1 9 46 B.1 9 5 3 C.1 9 6 4 D.1 9 6 89 .数据结构只是研究数据的逻辑结构和物理结构，这种观点()。A.正确 B.错误C.前半句对，后半句错 D.前半句错，后半句对1 0 .计算机内部数据处理的基本单位是()。A.数据 B.数据元素 C.数据项 D.数据库二、填空题1 .数据结构按逻辑

15、结构可分为两大类，分别是 和。2 .数据的逻辑结构有四种基本形态，分别是、和。3.线性结构反映结点间的逻辑关系是 的，非线性结构反映结点间的逻辑关系是 的。4.一个算法的效率可分为 效率和 效率。5 .在树型结构中，树根结点没有 结点，其余每个结点的有且只有个前趋驱结点；叶子结点没有 结点；其余每个结点的后续结点可以。6 .在图型结构中，每个结点的前趋结点数和后续结点数可以 o7 .线性结构中元素之间存在 关系；树型结构中元素之间存在关系；图型结构中元素之间存在_ 关系。8 .下面程序段的时间复杂度是。f or(i=0;in:i+)f or(j=0;jn;j+)A i j=0;9 .下面程序段

16、的时间复杂度是 o-9-i=s=O;w h i l e(s n)i+；s+=i;11 0 .下面程序段的时间复杂度是。s=0;f o r(i=0;i n;i+)f o r(j=0;j n;j+)s+=B|i j ;s u m=s;1 1 .下面程序段的时间复杂度是 oi=l；w h i l e(i =n)i=i*3;1 2 .衡量算法正确性的标准通常是。1 3 .算法时间复杂度的分析通常有两种方法，即 和 的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;f o r(i=l;i n;i+)f o r(j=i+l ;j =n;j+)x+;2.x=0;

17、f o r(i=l;i n;i+)f o r(j=l;j =n-i;j+)x+;3.i n t i,j,k;f o r(i=0;i n;i+4-)f o r(j=0;j =n;j+)c i U =O;f o r(k=0;k=0)&A i !=k)j-:r e t u r n (i);-1 0-5.f act(n)if(nmaxlen-l)-13-printf(overf low);exit(0);)i=0;j=0;/i和j分别作为扫描顺序表A和B的指针k=0;k指示顺序表C中当前位置while(i=m)&(j=n)if(*A).elem i=(*B).elem j)(*C).elem k=(*

18、A)elem i;i+;k+;)else (*C).elem k=(*B)elem j;j+;k+;)while(i=m)表B已结束，表A没有结束，链入表A的剩余部分 (*C).elem k=(*A).elem i;i+;k+;whileGnext;q-next=head;head=q;)【例 2-3假设有一个循环链表的长度大于1,且表中既无头结点也无头指针，已知p 为指向链表中某结点的指针，设计在链表中删除p 所指结点的前趋结点的算法。解：可引入一个指针q,当 q-nexl=p时，说明此时q 所指的结点为p 所指结点的前趋结点，从而可得算法如下：void delete(LinkList*p)

19、在链表中删除p 所指结点的前趋结点LinkList*q,*t;q=p；whilc(q-next-next!=p)/q-next 不是 p 的前趋结点-15-q=q-next;t=q-next;t 指向要删除结点q-next=p;/删除 t 结点free(t);)【例2-4】试设计实现删除单链表中值相同的多余结点的算法。解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。设单链表(其类型为L i n k L i s t)的头指针h e ad指向头结点，则可按下列步骤执行：首先，用一个指针p指向单链表中第

20、个表结点，然后用另一个指针q查找链表中其余结点元素，由于是单链表，故结束条件为p=NULL,同时让指针s指向q所指结点的前趋结点，当查找到结点具有q-d at a=p-d at a时删除q所指的结点，然后再修改q,直到q为空；然后使p指针后移(即p=p-n e x t),重复进行，直到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-da

21、ta)查找值相同的结点并删除 s-next=q-next;free(q):q=s-next;)s=q;q=q-next;)p=p-next;)4.栈栈(S t ac k)是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为 栈 顶(T o p),而另一端称为栈底(B o t t o m)。表为空时称为空栈。在栈-16-上的主要运算是入栈和出栈。栈中元素如果按a”a2,，a”的顺序进栈，则出栈顺序为an an.i，a)o 因此，栈又称为 后进先出(L as t I n F i r s t O u t)的线性表，简称L I F O表。同线性表相似，栈也有顺序栈和链栈两种

22、存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。另外，注意对栈的操作只能在栈顶进行。5.队列队 列(Qu e u e)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。通常把允许插入的一端称为队尾(r e a r),允许删除的一端称为队头(f r o n t)。队列中元素如果按a i，a 2,，a。的顺序进队，则出队的顺序仍为a”a2,-ano因此，队列又称为“先进 先 出(F i r s t In F i r s t O u t)的线性表，简称F IF O 表。队列也有顺序队列和链队列两种存储结构。在顺序队列中，为避免“假满”现象，一般采用循环队列(即首尾相接)。链队列会因为

23、队满而产生“上溢”现象。习题2一、单项选择题i .线性表是。A.一个有限序列，可以为空 B.一个有限序列，不可以为空C.一个无限序列，可以为空 D.一个无限序列，不可以为空2 .在一个长度为n的顺序表中删除第i 个元素(0=i n e x t=s;s-p r i o r=p;p-n e x t-p r i o r=s;s-n e x t=p-n e x t;B.s-p r i o r=p;s-n e x t=p-n e x t;p-n e x t=s;p-n e x t-p r i o r=s;C.p-n e x t=s;p-n e x t-p r i o r=s;s-p r i o r=p;

24、s-n e x t=p-n e x t;D.s-p r i o r=p;s-n e x t=p-n e x t;p-n e x t-p r i o r=s;p-n e x t=s;6 .设单链表中指针p指向结点m,若要删除m之后的结点(若存在)，则需修改指针-17-的操作为。A.p-n e x t=p-n e x t-n e x t;B.p=p-n e x t;C.p=p-n e x t-n e x t;D.p-n e x t=p;7 .在一个长度为n的顺序表中向第i 个元素(0 i n e x t=p-n e x t;p-n e x t=sB.q-n e x t=s;s-n e x t=pC

25、.p-n e x t=s-n e x t;s-n e x t=pD.p-n e x t=s;s-n e x t=q9 .以 下 关 于 线 性 表 的 说 法 不 正 确 的 是。A.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。1 0 .线性表的顺序存储结构是一种 的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取1 1 .在顺序表中，只要知道,就可在相同时间内求出任一结点的存储地址。A.基地址 B.结点大小C.向量

26、大小 D.基地址和结点大小1 2 .在等概率情况下，顺序表的插入操作要移动 结点。A.全部 B.一半C.三分之一 D.四分之一1 3 .在_ _ _ _运算中，使用顺序表比链表好。A.插入 B.删除C.根据序号查找 D.根据元素值查找1 4.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是A.0(1)B.O(n)C.O(n2)D.O(l o g 2n)1 5.设有一个栈，元 素 的 进 栈 次 序 为 A,B,C,D,E,下列是不可能的出栈序列A.A,B,C,D,EC.E,A,B,C,DB.B,C,D,E,AD.E,D,C,B,A1 6.在一个具有n个单元的顺序栈中，

27、假定以地址低端(即0单元)作为栈底，以 t o p作为栈顶指针，当做出栈处理时，t o p 变化为。-18-A.top 不变 B.top=0 C.top-D.top+17.向一-个栈顶指针为h s的链栈中插入一个s 结点时，应执行。A.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 个单元的顺序存储的循环队列中，假定f ront和 rear分别为队头指针和队尾指针，则 判 断 队 满 的 条 件 为。A.rear%n=front B.(front+1)%n=rearC.re

28、ar%n-1=front D.(rear+1)%n=front19.在具有n 个单元的顺序存储的循环队列中，假定f ront和 rear分别为队头指针和队尾指针，则判断队空的条件为 eA.rear%n=front B.front+l=rearC.rear=front D.(rear+1)%n-front20.在一个链队列中，假定f ront和 rear分别为队首和队尾指针，则删除一个结点的操作为 oA.front=front-next B.rear=rear-nextC.rear=front-next D.front=rear-next二、填空题1.线性表是一种典型的 结构。2.在一个长度为n

29、 的顺序表的第i 个元素之前插入一个元素，需要后移一个元素。3.顺序表中逻辑上相邻的元素的物理位置_ _ _ _ _ _ o4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 一个位置，移动过程是从 向 依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的：在线性表的链接存储中，元素之间的逻辑关系是通过 决定的。6.在双向链表中，每个结点含有两个指针域，一个指向 结点，另一个指向_ _ _ _ _ _ _ 结点。7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 存储结构为宜。8

30、.顺序表中逻辑上相邻的元素，物理位置_ _ _ _ _ 相邻，单链表中逻辑上相邻的元素，物理位置_ _ _ _ _ _相邻。9.线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在_ _ _ _ _ _ _ 位置插入和删除元素；对于队列只能在_ _ _ _ _ _ _ 位置插入元素和在位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为和;而根据指针的联接方式，链表又可分为 和。11.在 单 链 表 中 设 置 头 结 点 的 作 用 是。-19-1 2.对于一个具有n个结点的单链表，在己知的结点p后插入一个新结点的时间复杂度为,在给定值为x

31、的 结 点 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为。1 3.对于一个栈作进栈运算时、应 先 判 别 栈 是 否 为,作退栈运算时,应先判别栈是否为,当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样只有当_ _ _ _ _ _ _时才产生上溢。1 4.设有一空栈，现有输入序列 1,2,3,4,5,经过 p u s h,p u s h,p o p,p u s h,p o p,p u s h,p u s h后，输出序列是 o1 5.无论对

32、于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为。三、简答题1 .描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪种存储结构？为什么？4 .对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5 .在单循环链表中设置尾指针比设置头指针好吗？为什么？6 .假定有四个元素A,B,C,D依次进栈，

33、进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8 .下述算法的功能是什么？L i n k L i s t *D e m o(L i n k L i s t *L)L是无头结点的单链表L i n k L i s t *q,*p;i f(L&L-n e x t)q=L;L=L-n e x t;p=L;w h i l e (p-n c x t)p=p-n e x l;p-n c x t=q;q-n e x t=N U L L;)r e t u r n (L);)四、算法设计题1.设计在无头结点的单链表中删除第i个结点的算法。-2 0-2 .在单

34、链表上实现线性表的求表长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 or o 其中d a t a 为整型数域，n e x t 和 p r i or 均为指针域。现在所有结点已经由n e x t 域连接起来，试编一个算法，利用p r i or 域（此域初值为N U L L）把所有结点按照其值从小到大的顺序链接起来。5 .已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于m i n 且小于m a

35、 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 1 1.D 1 2.B1

36、3.C 1 4.B 1 5.C 1 6.C 1 7.B 1 8.D 1 9.C 2 0.A二、填空题1 .线性2 .n-i+13 .相邻4 .前移，前，后5 .物理存储位置，链域的指针值6 .前趋，后继7 .顺序，链接8 .一定，不一定9 .线性，任何，栈顶，队尾，队头1 0 .单链表，双链表，非循环链表，循环链表1 1 .使空表和非空表统一；算法处理一致1 2 .0（1）,0（n）1 3 .栈满，栈空，m,栈底，两个栈的栈顶在栈空间的某一位置相遇1 4 .2、3-21-15.0(1)三、简答题1.头指针是指向链表中第一个结点(即表头结点)的指针；在表头结点之前附设的结点称为头结点；表头结点为

37、链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2.线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3.应选用链接存储结构，因为链式存储结构是用 组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删

38、除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4.应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任 个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构,而链表则是,种顺序存取的存储结构。5.设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为re a r,则开始结点和终端结点的位置分别是rear-next-next和 r e a r,查

39、找时间都是 0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。6.共 有 14种可能的出栈序列，即为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA.CBAD,CBDA,CDBA,DCBA7.在队列的顺序存储结构中，设队头指针为front,队尾指针为re a r,队列的容量(即存储的空间大小)为maxnum 当有元素要加入队列(即入队)时，若 rear=maxnum,则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式

40、的选择不当所致，可以用循环队列解决。一般地，要解决队列的上 溢现象可有以下儿种方法：(1)可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低,浪费存储空间。(2)要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使f ront指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循-22-环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8.该算法

41、的功能是：将开始结点摘卜链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1.算法思想为：(1)应判断删除位置的合法性，当 i n-l时，不允许进行删除操作：(2)当 i=0时，删除第一个结点：(3)当 0 i n时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：dclctc(LinkList*q,int i)在无头结点的单链表中删除第i个结点LinkList*p,*s;int j;if(incxt;f ree(s);)else j=0;s=q;while(jnext;j+；)if(s=NULL)pr

42、intf CCantt delete);else p-next=s-next;f ree(s);)2.由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：int ListLength(LinkList*L)-23-求带头结点的单链表的表长int len=O;ListList*p;p=L;while(p-next!=NULL)p=p-next;len+;)return(len);)3.设单循环链表的头指针为head,类型为LinkList。逆置时需将卷一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q 结点的指针域时，设 s 指向其原前趋结点，p

43、 指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：void invert(LinkList*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*nexl,*prior;LinkList;此题可采用插入排序的方法，设 p 指向待插入的结点，用 q 搜索已由prior域链接的

44、有序表找到合适位置将p 结点链入。算法描述如下：insert(LinkList*head)LinkList*p,*s,*q;p=head-ncxt;p 指向待插入的结点，初始时指向第个结点while(p!=NULL)(s=head;/s 指向q 结点的前趋结点-24-q=head-prior;/q指向由prior域构成的链表中待比较的结点whilc(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*

45、head,int max,int min)linklist*p,*q;if(head!=NULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;)whilc(p!=NULL)&(p-datanext;q-next=p;)6.算法描述如下：delete(LinkList*head,int max,int min)LinkList*p,*q;q=head;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;)else(q-next=p-next;f ree(p);-25-p=q-next;)

46、7 .本题是对一个循环链队列做插入和删除运 算，假设不需要保留被删结点的值和不需要回收结 点，算法描述如下：(1)插 入(即 入 队)算 法：insert(LinkList*rear,elemtype x)设循环链队列的队尾指针为rcar,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)删 除(即 出 队

47、)算 法：delete(LinkList*rear)设循环链队列的队尾指针为rearif(rear=NULL)空队printf(underf lown);if(rear-next=rear)队中只有个结点rear=NULL;elserear-next=rear-next-next;/rear-next指向的结点为循环链队列的队头结点)8 .只要从终端结点开始往前找到第一 个 比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：int InsertDecreaseList(SqList*L,elemtype x)int i;if (*L).len=maxlen)printf(ove

48、rf low)；return(O);1-26-f or(i=(*L).len;i0&(*L).elem i-1 x;i-)(*L).elcm i=(*L).elcm i-1;/比较并移动元素(*L).elem i =x;(*L).len+;return(l);-27-第 3 章 串讲课提要【主要内容】1.串的有关概念及基本操作2.串的存储结构3.串操作应用举例【教学目标】1.掌握串的有关概念及基本运算2.熟悉串的存储结构3.熟悉用操作应用举例【所需课时】一次课。1.串的有关概念及基本运算2.串的存储结构3.串操作应用举例学习指导1.概念和术语 串(S trin g)(或字符串)：是由零个或多个

49、字符组成的有限序列。一般记为s=a (n20)其中，s 是串的名，用双引号括起来的字符序列是串的值。串的长度：串中字符的个数n。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串：不包含任何字符的串，表示为“”。空格串：由一个或多个空格字符组成的串。例如：“2.串的基本操作(1)用串变量赋值assign t)和用串常量赋值create ss)(2)判等函数 equal(s,t)(3)求长函数 length(s)-28-(4)(5)(6)(7)(8)(9)连接函数求子串函数定位函数置换函数插入子串删除子串(1 0)串的复制concat(s,t)subst

50、ring(s,pos,len)index(s,t)replace(s,t,v)insert(s,pos,t)delete(s,pos,k)copy(s,t)【例 3-1】已知字符串:a=an apple”,b=t4other hero,c=her，求:(1)concat(substr(a,1,2),b)o(2)replace(a,substr(a,5,1 ),c)o(3)index(a,c)和 index(b,c)。解：(1)返回值为another hero”,其中 substr(a,1,2)的返回值为“an”。(2)返回值为“anaherherle，其中sub(a,5,l)的返回值为“p”。