数据结构习题库(c语言版).doc

第一章 绪 论一、基本内容 数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。 二、学习要点 1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2、了解抽象数据类型的定义、表示和实现方法。 3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4、理解算法五个要素的确切含义。1.1 基础知识一 、填空题 1、数据的逻辑结构包括 ， ， 和 四种类型，树型结构和图型结构合称为 ，数据的存储结构即物理结构包括： ， 等两种基本类型。 2、在线性结构中元素之间存在 关系，树形结构中元素间存在 关系，图形结构中元素间存在 关系。3、一个数据结构用二元组表示时，它包括 集合D和D上 的集合S。4、一个算法应具有 ， ， ， 和 这五个特性。 5、在图形结构中，每个节点的前驱节点和后继节点可以有 个。6、一个抽象数据类型用三元组（D，S，P）表示时，D是 ，S是 ，P是 。7、数据元素在计算机中的映象是 。8、算法的设计取决于 ，算法的实现取决于 。二、选择题1、数据元素是数据的 单位。(A)基本 (B)最小 2、使用指针表示数据元素之间逻辑关系的存储结构是 。(A)顺序结构 (B)链式结构 (C)树状结构 (D)图状结构3、以下_术语与数据的存储结构无关。 (A)线索二叉树 (B)双向链表 (C)栈 (D)哈希表4、以下_术语与数据的逻辑结构无关。 (A)线性结构 (B)链式结构 (C)树型结构 (D)网状结构5、指出下列叙述_不属于算法的特性。 (A)有穷性 (B)复杂性 (C)可行性 (D)确定性6、以下数据结构中_是线性结构。(A)队列 (B)有向图 (C)树 (D)哈夫曼树解答：一、 填空题1、线性 集合 树 图或网 非线性结构 顺序存储 链式存储 2、1：1 1：n m：n3、数据元素 关系4、有穷性 确定性 可行性 输入 输出5、多个6、数据对象 D上的关系集合 对D的基本操作集合7、元素或结点8、数据（逻辑）结构 采用的存储结构二、 选择题1、A 2、B 3、C 4、B 5、B 6、Al.2 应用知识 1、什么是算法？算法的特性是什么？算法设计的要求是什么? 解答: （略）2、设有数据结构USER_STRU表示如下： USER_STRU =（D，S） D = a1，a2，a9 S = ， 画出这个数据结构的图示，并确定其类型。 解答：该结构的图示如下，该结构为图形结构。a2a4a5a6a7a3a1a9a8 3、设有数据结构USER_STRU表示如下： USER_STRU =（D，S） D = a1，a2，a9 S = ， 画出这个数据结构的图示，并确定其类型。解答：该结构的图示如下，该结构为树形结构。a1a2a3a6a4a8a7a5a94、影响高级语言程序运行消耗时间的因素有哪些？解答：主要有以下因素： (1)算法选用的策略； (2)问题的规模； (3)书写程序的语言； (4)编译程序产生的机器代码质量； (5)机器执行指令的速度。5、选择解决某种问题的最佳数据结构的标准是什么?解答：一般有两条标准： (1)所需的存储空间量； (2)算法所需要的时间； 而算法所需要的时间又包括以下几点： (1)程序运行时所需要的数据总量； (2)源程序进行编译所需要的时间； (3)计算机执行每条指令所需要的时间； (4)程序中的指令重复执行的次数，而本条正是讨论算法中的重点内容。6、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn)解答：（1）成立；（2）成立；（3）成立；（4）不成立。7、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0;while(in) k=k+10*i;i+;(2) i=0; k=0;dok=k+10*i; i+;while(in);(3) i=1; j=0;while(i+jj) j+;else i+;(4)x=n; / n1while (x=(y+1)*(y+1)y+;(5) x=91; y=100; while(y0)if(x100)x=x-10;y-;else x+;解答：（1）为T(n)=O(n)；（2）为T(n)=O(n)；（3）为T(n)=O(n) （4）由x=n且x的值在程序中不变，又while的循环条件(x=(y+1)*(y+1)可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)n得：yn0.5-1所以，该程序段的执行时间为：向下取整(n0.5-1)（5）为T(n)=O(1)8、算法的时间复杂度仅与问题的规模相关吗?解答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。9、按增长率由小至大的顺序排列下列各函数：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 解答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n(3/2)指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn注意：(2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n 2100 lgn n0.5 n(3/2) nlgn (3/2)n 2n n! nn 10、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?解答：要使前者快于后者，即前者的时间消耗低于后者，即：100n2next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。 3、熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。2.1 基础知识 一、填空题 1、对于双向循环链表，在两个结点间插入一个新结点时需修改的指针共有 个，单链表为 个。 2、当向一个顺序表插入一个元素时，被插入元素之后的所有元素均需向 移动一个位置，元素的移动顺序是从 向 依次移动。3. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向 移动一个位置，元素的移动顺序是从 向 依次移动。4、在一个循环单链表中，表尾结点指针域与表头指针值 。 5、在线性表的顺序存储中，元素之间的逻辑关系是通过 表示的；在线性表的链接存储中，元素之间的逻辑关系是通过 表示的。 6、在双向链表中，每个结点含有两个指针域，一个指向 结点，另一个指向 结点。7、在一个单链表中删除p所指结点时，应执行下列操作: q=p-next; p-data=p-next-data; p-next= ; free(q);8、若要在一个不带表头结点的单链表的首结点*p之前插入一个*s结点时，可执行下列操作： s-next= ； p-next=S； t=p-data； p-data= ； s-data= ；9、根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为 和 ；而根据指针的联接方式，链表又可分为 和 。 10、单链表表示法的基本思想是利用 表示结点间的逻辑关系。 11、 当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用 存储结构为宜， 相反， 当经常进行的是插入和删除操作时， 则采用 存储结构为宜。 12、在单链表中设置头结点的作用是 。 13、顺序表中逻辑上相邻的元素，物理位置 紧邻，单链表中逻辑上相邻的元素，物理位置 紧邻。 14、一个采用了顺序存储结构的线性表，其长度为30，若在第7个元素前插入一个元素，需要移动 个元素，若接着又将第12个元素删除，那么需要移动 个元素。二、选择题 1、在一个长度为n的顺序表中删除第i个元素(1in)时，需向前移动 个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i2、用链表表示线性结构的优点在于 。 (A)便于随机存取 (B)便于插入和删除(C)节省空间 (D)元素的物理顺序和逻辑顺序一致3. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是 。 (A) p-next=s； s-prior=p； (p-next)-prior=s； s-next=p-next； (B) s-prior=p； s-next=p-next； p-next=s； p-next-prior=s； (C) p-next=s； p-next-prior=s； s-prior=p； s-next=p-next； (D) s-prior=p； s-next=p-next； p-next-prior=s； p-next=s；4、 设单链表中指针p指向结点m，若要删除m之后的结点 ( 假定存在 )， 则需修改指针的操作为 。 (A) p-next=p-next-next； (B) p=p-next； (C) p=p-next-next； (D) p-next=p； 5、 线性表采用链式存储时，其存储单元的地址 。 (A) 必须是连续的； (B) 一定是不连续的； (C) 部分地址必须是连续的； (D) 连续与否均可以； 6、在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则须执行 。 (A) s-next=p-next； p-next=s； (B) q-next=s； s-next=p； (C) p-next=s-next； s-next=p； (D) p-next=s； s-next=q；7、线性表是 。(A) 一个有限序列，可以为空；(B) 一个有限序列，不可以为空；(C) 一个无限序列，可以为空；(D) 一个无限序列，不可以为空；8、在一个长度为n的顺序表中向第i个元素 ( 0next8、 p-next s-data t9、 单链表 双链表 非循环链表 循环链表10、 （后继）指针域的取值11、 顺序 链接12、使空表和非空表统一；算法处理一致。13、 一定 不一定14、 24 19二、选择题1、A 2、B 3、D 4、A 5、D 6、B 7、A 8、B 9、B 10、C 11、D三、判断题1、错 2、错 3、对 4、错 5、对2.2 应用知识 1、描述以下三个概念的区别：头指针、头结点、表头结点。 解答：头指针是指向链表中第一个结点(即表头结点)的指针，在表头结点之前附设的一个结点称为头结点，表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)，否则表示空表的链表的头指针为空。 2、在单链表和双向链表中，能否从当前结点出发访问任一结点? 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?解答：在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前趋结点的指针。而在双向链表中既有指向其后继结点的指针又有指向其前趋结点的指针，故可由当前结点出发访问链表中的任一结点。下面分别讨论三种链表的情况。1. 单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。3、线性表的两种存储结构各有哪些优缺点? 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?解答：线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。4、对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变， 在此情况下， 应选用哪一种存储结构? 为什么? 解答：应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的，这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 5、对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应选用何种存储结构? 试说明理由。 解答：应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。6、为什么在单循环链表中设置尾指针比设置头指针更好?解答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。7、假设单链表的表头指针用head表示，其类型为linklist，写出将其所有结点按相反次序链接的算法。contray(head) /*将head单链表中所有结点按相反次序链接*/ linklist *head；/*head为单链表类型，含有数据域和指针域等*/ linklist *p，*q： p=head； /*p指向未被逆序的第一个结点，初始时指向原表头结点*/ head=Null： while(p!=Null) q=P； /*q指向将被逆序链接的结点*/ P=p-next； q-next=head； head=q； /*contray*/8、设计产生一个有两个结点的链表的算法，且第一个结点中放数值x ， 第二个结点中放数值y，head为头指针。 解答：先分别生成两个结点，然后将这两个结点链接起来，最后对这两个结点的数据域赋值。 linklist *createlist() /*产生一个有两个结点的链表*/ linklist *head，*s；int x，y；head=malloc(sizeof(linklist)；s=malloc(sizeof(linklist)；head-next=s；s-next=Null；head-data=x；s-data=y；return head； /*createlist*/9、设计在无头结点的单链表中删除第i个结点的算法。解答：算法的思想为：(1)应判断删除位置的合法性，当in-1时，不允许进行删除操作； (2)当i=0时，删除第一个结点； (3)当0in时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。 从而将算法描述为： delete (q，i) /*在无头结点的单链表中删除第i个结点*/ linklist *q；int i； linklist *p， *S； int j； if(inext； free(s)； else j=0；s=q； while(jnext； j+ if(s= =Null)printf(“cantt deleten”)； else p-next=s-next； free(s)； /*delete*/10、假设有一个带附加表头结点的链表，表头指针为head，每个结点含三个域：data、next 和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域(此域初值为Null)把所有结点按照其值从小到大的顺序链接起来。 解答： insert(head) /*将链表中所有结点利用prior域按照其值有序链接起来*/ linklist *head； /*linklist为一个具有三个域的结点类型，含data；next和prior*/ linklist *p，*s，*q； p=head-next； /*p指向待插入的结点，初始时指向第一个结点*/ while(p!=Null) s=head； /*s指向结点的前趋结点*/ q=head-prior；/*q指向由prior域构成的链表中待比较的结点*/ while(q!=Nu11)&(p-data q-data) /*查找插入结点*p的合适的插入位置*/ s=q； q=q-prior； s-prior=P； p-prior=q；/*q结点插入到*S和*q结点之间*/ p=p-next； /*insert*/ /*insert*/11、设有一个向量A=(a1，a2，.an)，试设计一个算法将向量膛，即使得元素排列次序颠倒，成为逆向量A=(an，an-1，a2，al)，要求不重新开辟空间，且用顺序表和单链表两种表示方法，设计不同的处理算法。解答：1. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：#define ListSize 100 / 假定表空间大小为100typedef int DataType;/假定DataType的类型为int型typedef struct DataType dataListSize;/ 向量data用于存放表结点 int length; / 当前的表长度 Seqlist; /以上为定义表结构void ReverseList( Seqlist *L)DataType temp ; /设置临时空间用于存放dataint i;for (i=0;ilength/2;i+)/L-length/2为整除运算 temp = L-datai; /交换数据L - data i = L - data L - length-1-i;L - data L - length - 1 - i = temp;2. 链表：可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：结点结构定义如下：typedef char DataType; /假设结点的数据域类型的字符typedef struct node /结点类型定义DataType data; /结点的数据域struct node *next;/结点的指针域ListNode;typedef ListNode *LinkList;ListNode *p;LinkList head;LinkList ReverseList( LinkList head )/ 将head 所指的单链表(带头结点)逆置ListNode *p ,*q ;/设置两个临时指针变量if( head-next & head-next-next)/当链表不是空表或单结点时p=head-next;q=p-next;p - next=NULL; /将开始结点变成终端结点while (q) /每次循环将后一个结点变成开始结点p=q;q=q-next ;p-next = head- next ;head-next = p;return head;return head; /如是空表或单结点表，直接返回head12、设计将单循环链表逆置的算法。 解答：设单循环链表的头指针为head， 类型为linklist， 则可得算法如下： invert(head) /*逆置head指针所指向的单循环链表*/linklist *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； /*invert*/ 13、设计将一个双向循环链表逆置的算法。 解答：设双向循环链表的结点类型为dblinklist，其中每个结点含三个域，分别为next、 data与prior域，双向链表的头指针为head，从而可得算法如下： invert(head) /*将head指针所指向的双向循环链表逆置*/ dblinklist *head； dblinklist *p， *q； p=head；do q=p-next；p-next=p-prior；p-prior=q； p=q； while(p= =head) / *invert*/ 14、用顺序存储结构实现将两个有序表合并成为一个有序表，合并后的结果不另设新表存储。 解答：设有序表为递增序列，则其算法思想为： (l) 设A，B均为有序表，且均为整型数组，合并后的结果仍存放在A表中。 (2) 设A表的长度为n，B表的长度为m，合并之后的长度为m+n； (3) 合成过程中需进行元素的比较，可以先从A和B的最后一个元素逐个向前进行比较，可以使得合并后的结果不影响A中原来存放的元素。 算法如下： int merge (A， B)/*将两个有序表A和B合并成为F一个有序表*/ sequenlist *A， *B； /*A；*B为指向sequenlist类型的指针变量，含last和vec域*/ int m， n； n=(*A).last；m=(*B).last；while(*B).last0) if(*A).last=0)|(*A).vec(*A).lastdataahead-data) t=ahead；ahead=ahead-next；else t=bhead： bhead=bhead-next： t-next=Null； if(p= =Null)p=t； else q-next=t； if (ahead= =Nul l)p=ahead； else q-next=ahead； q=ahead；ahead=p； /*merge*/ 16、已知两个循环链表a=(al， a2，an-1 ,an)和b=(b1，b2，bm-1，bm)，设计出将这两个表合并为循环链表c的算法。 解答：算法如下： dblinklist merge(ha， hb) *合并两个循环链表*/ dblinklist *ha， hb； /*ha，hb为指向循环链表类型dblinklist的指针变量*/ dblinklist *hc， *qa， *qb， *qc： if(ha= =Null) hc=hb； /*a表为空*/ if(hb= =Null) hc=ha； /*b表为空*/ if(ha!=Nul l)&(hb!=Nul l) qa=ha； qb=hb； hc=ha； qa=qa-next； hc-next=qb； qc=qb： qb=qb-next； while(ha!=qa) & (hb!=qb) qc-next=qa；qc=qa； qa=qa-next； qc-next=qb； qc=qb； qb=qb-next； if(ha= =qa) while(hb!=qb) qc-next=qb； qc=qb； qb=qb-next； if(hb= =qb) while(ha!=qa) qc-next=qb； qc=qa； qa=qa-next； qc-next=hc； return hc； /*merge*/ 17、假设有一个循环链表的长度大于1， 且表中既无头结点也无头指针， 己知p为指向链表中某结点的指针，设计出在链表中删除p所指结点的前趋结点的算法。 解答：可引入一个指针q，当p-next=q时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下： delete(p) /*在链表中删除p所指结点的前趋结点*/ linklist *p； linklist *q； q=p； while(q-next-next!=p) q=q-next； t=q-next； q-next=p； free(t)； /*delete*/ 18、已知线性表的元素按递增顺序排列， 并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。 解答：算法如下： delete(head， max， min) /*删除有序单链表中所有值大于min且小于max的元素*/ link1ist *head；int max ， 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； /*delete*/ 19、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。 解答：算法如下：delete(head， max， min) /*删除无序单链表中所有值大于min且小于max的元素*/ linklist *head；int min， max； 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； free(p)； q=q-next； /*delete*/ 20、设指针la，1b分别指向两个不带头结点的单链表a、b的第一个结点， 试设计一个从 表a中删除自第i个元素起共1en个元素，并将这len个元素插入到表b中第i个元素之前的算法。 解答：算法描述如下： deleteinsert( la， 1b， i， 1en) /*从表a中删除元素， 并将这些元素插入到表b中*/ linkfist *la， *lb /*la *la， * lb分别为linklist类型的指针变量 */ int i，1en； linklist *r， *p， *q， *s； int i， k； if (i0|len0) printf(“errorn”)；p=la；k=l；while (p!=Null)&(knext； k+； /*查找la表中第i个元素*/ if(p= =Null)printf(“ errorr”)； else q=p； k=1； while(q!=Null)&(knext； k+；if(q= =Null)printf(“errorn”)； else r-next=q-next；if (i= =1) q-next=b； 1b=P； /*在lb表中查找插入位置并插入*/ else s=lb； k=1； while(s!=Null)&(knext； k+； /*查找lb表中第i-1个元素*/ if(s= =Null)printf(“errorn”)； else q-next=s-next； s-next=p； *deleteinsert*/ 21、 设计一个在不带头结点的链表的第i个元素之前插入一个元素的算法。 解答：算法步骤为： (1) 当in时， n为链表中的结点个数， 此时不允许插入， 出错处理； (4) 当1i=n时，则可进行插入， 此时必须查找第i个结点， 但同时须记住它的前趋在点。 从而算法可描述如下： insert(q， x， i) /*在不带头结点的链表的第i个元素之前插入一个元素*/ linklist *q；int i； datatype x； link1ist *s， *p； int j； if(idata=x； if(i= =1) s-next=q； q=s；else j=1；p=q； while(jnext；j+；if(p= =Null) printf(“errorn”)； else s-next=p-next； p-next=s； /*insert*/ 22、 计一个算法，将一个用循环链表表示的稀疏多项式分解成两个多项式， 使这两个多项式中各自仅含奇数项或偶数项， 并要求利用原链表中的结点空间来构成这两个链表。 解答：此题解题思想为： (1) 首先建立奇数项循环链表的头结点， 偶数项的头结点仍用多项式循环链表的头结点； (2) 然后查找该多项式循环链表的各个结点， 依据结点的指数域进行处理； (3) 当查找的结点的指数域为偶数时， 则只修改查找指针及其前趋结点指针；