严蔚敏数据结构题集(c语言版)史上最全答案（一题可有多解）.pdf

第1章 绪 论1.1 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合利定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3 解：(dT)-(d3)-(d4)1.4 解：A D T C o m p l e x 数据对象：D=r,i|r,i 为实数数据关系：R=基本操作：I n i t C o m p l e x(&C,r e,i m)操作结果：构造一个复数C,其实部和虚部分别为r e 和 i mD e s t r o y C m o p l e x(&C)操作结果：销毁复数CG e t (C,k,&e)操作结果：用 e 返回复数C的第k 元的值P u t (&C,k,e)操作结果：改变复数C的第k元的值为eI s A s c e n di n g(C)操作结果：如果复数C的两个元素按升序排列，则返回1,否则返回0I s D e s c e n di n g(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回0M a x (C,&e)操作结果：用 e 返回复数C的两个元素中值较大的一个M i n(C,&e)操作结果：用 e 返回复数C的两个元素中值较小的一个 A D T C o m p l e xA D T R a t i o n a l N u m b e r 数据对象：D=s,m|s,m 为自然数，且 m不为0 数据关系：R=基本操作：I n i t R a t i o n a l N u m b e r(&R,s,m)操作结果：构造一个有理数R,其分子和分母分别为s 和 mD e s t r o y R a t i o n a l N u m b e r(&R)操作结果：销毁有理数RG e t (R,k,&e)操作结果：用 e 返回有理数R的第k 元的值P u t (&R,k,e)操作结果：改变有理数R的第k 元的值为eI s A s c e n di n g(R)操作结果：若有理数R的两个元素按升序排列，则返回1,否则返回0I s D e s c e n di n g(R)操作结果：若有理数R的两个元素按降序排列，则返回1,否则返回0M a x (R,&e)操作结果：用 e 返回有理数R的两个元素中值较大的 个M i n(R,&e)操作结果：用 e 返回有理数R的两个元素中值较小的一个 A D T R a t i o n a l N u m b e r1.5 试画出与下列程序段等价的框图。(1)p r o du c t=l：i=l;w h i l e(i =n)p r o du c t *=i;i+；)(2)i=0;do i+；w h i l e(i!=n)&(a i !=x);(3)s w i t c h c a s e x 4 3 8 时,n2 5 0 n l o g2 n1.1 4 解:g(n)快 g(n)快(3)f(n)快(4)f(n)快1.1 5 试用数学归纳法证明：(1)/=(+欢2 +1)/6 (n 0)fx=(*l)/(x T)(x*l,N0)(3)2=2 1 (n 1)i=l(4)汽 1)=2 (n 1)1.1 6 试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值解：int max3(int x,int y,int z)(if(xy)i f(xz)return x;else return z;elsei f(yz)return y;else return z;解2：void print_descending(int x,int y,int z)按从大到小顺序输出三个数(scanf(n%d,%d,%dM,&x,&y,&z);if(xy;为表示交换的双目运算符,以下同if(yz)yz;if(xy;冒泡排序printf(%d%d%dn,x,y,z);/print_descending解3:(上机自实现)要求实现下列函数：void Descend(int&x,int&y,int&z);/*按从大到小顺序返回x,y 和 z 的 值*/void Descend(int&x,int&y,int&z)/*按从大到小顺序返回x,y 和 z 的 值*/(int temp;if(xy)temp=x;x=y;y=temp;if(y=temp)y=temp;elsey=x;x=temp;)1.1 7 解：k 0 为阶数，n 为数列的第n 项int Fibonacci(int k,int n)(if(kl)e x it(OVERFLOW);int*p,x;p=new intk+1;if(!p)e x it(OVERFLOW);int i,j;for(i=0;ik+l;i+)if(i k-l)pi=0;else p i=l;f o r (i=k+l;i n+l;i+)x=p 0;f o r(j=0;j k;j+)p j=p j+U;p k=2*p k-l-x;r e t u r n p k;)解 2：S t a t u s f i b(i n t k,i n t m,i n t&f)求k阶斐波那契序列的第m项的值f(i n t t e m p d;i f(k 2l l m 0)r e t u r n ERROR;i f(m k-l)f=0;e l s e i f (m=k-1)f=l;e l s e(f o r(i=0;i=k-2;i+)t e m p i=0;t e m p k.1 =1;初血化f o r(i=k;i v=m;i+)求出序歹U 第 k至第m个元素的值(s u m=0;f o r(j=i-k;j i;j+)s u m 4-=t e m p j;t e m p i=s u m;)f=t e m p m;)r e t u r n OK;/f i b分析:通过保存已经计算出来的结果，此方法的时间复杂度仅为O(m 八 2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k 八 m).解 3:(上机已实现)要求实现下列函数：S t a t u s Fi b o n a c c i(i n t k,i n t m,i n t&f);/*如果能求得k阶斐波那契序列的第m项的值f,则返回OK；*/*否则(比如，参数k 和 m不合理)返回ERROR*/S t a t u s Fi b o n a c c i(i n t k,i n t m,i n t&f)/*求 k阶斐波那契序列的第m项的值f */(i n t t e m p 200,i,j,s u m;i f(k 2|m 0)r e t u r n ERROR;i f(m k-l)f=0;e l s e i f(m=k-l)f=l;e l s e(f o r(i=0;i=k-2;i+)t e m p i=0;t e m p k-l=l;初始化f o r (i=k;i=m;i+)求出序列第k 至第m个元素的值(s u m=0;f o r (j=i-k;j=i-l;j+)s u m+=t e m p j;t e m p i=s u m;)f=t e m p m;)r e t u r n OK;1.18 解:typedef enum(A,B,C,I),E SchoolName;typedef enumFemale,Male SexType;typedef struct char event 3;项目SexType sex;SchoolName school;int score;Component;typedef struct(int Mal eSum;男团总分int Ferna 1 eSum;女团总分int TotalSum;团体总分 Sum;Sum SumScore(SchoolName sn,Component a,int n)(Sum temp;temp.MaleSum=O;temp.FemaleSum=O;temp.TotalSum=0;int i;for(i=0;in;i+)if(a i.school=sn)if(a ij.sex二 二 Male)temp.MaleSum+=aiJ.score;if(aij.sex二 二 Female)temp.FemaleSum+=ai.score;)temp.TotalSum=temp.MaleSum+temp.FemaleSum;return temp;)解二：typedef struct char*sport;enum male,female gender;char schoolname;校名为 或Echar*result;int score;)resulttype;typedef struct int malescore;int femalescore;int totalscore;scoretype;void summary(resulttype result)求各校的男女总分和团体总分,假设结果已经储存在resull数组中scoretype score;i=0;while(resulti.sport!=NULL)(switch(resulli.schoolname)(case A:score 0.totalscore+=resulti.score;if(resulti.gender=0)score 0.malescore+=resulti.score;else score 0.femalescore+=resulti.score;break;case B:score.totalscore+=resulti.score;if(resulti.gender=0)score.malescore+=resulti.score;else score.femalescore+=resulti.score;break;i+;for(i=0;i5;i+)(printf(nSchool%d:nu,i);printf(nTotaI score of male:%dnM,scorei.malescore);printf(Total score o f female:%dn,score i.femalescore);printf(Total score of all:%dnn,scorei.totalscore);)/summary解 3:(上机已实现)要求实现下列函数：void Scores(ResultType result,ScoreType*score);/*求各校的男、女总分和团体总分，并依次存入数组score*/*假设比赛结果已经储存在result数组中，*/*并 以 特 殊 记 录 male,1；,H,0 (scorce=0)*/*表示结束*/相关数据类型定义如下：typedef enum female,male Sex;typedef struct char*sport;/项目名称Sex gender;/性 别(女：female；男：male)char schoolname;/校名为A?B?C?D或Echar*result;/成绩int score;/得 分(7,5,4,3,2 或 1)ResultType;typedef struct int malescore;/男子总分int femalescore;/女子总分int totalscore;/男女团体总分 ScoreType;void Scores(ResultType result,ScoreType*score)/*求各校的男、女总分和团体总分，并依次存入数组score*/*假设比赛结果已经储存在result口数组中，*/*并以特殊记录T m ale,二”，0 (域 scorce=0)*/*表示结束*/(int i=0;while(resulti.sport!=NULL)(switch(resultij.schoolname)(case A:score0.totalscore+=resulti.score;if(resulti.gender=O)score0.femalescore+=resulti.score;else score0.malescore+=resulti.score;break;case B:score 1 J.totalscore+=resultliJ.score;if(resulti.gender=O)scorel.femalescore+=resulti.score;else score1.malescore+=resulti.score;break;case C:score2.totalscore+=resulti.score;if(resulti.gender=O)score2.femalescore+=resulti.score;else scorel2J.malescore+=resulti.score;break;case D:score3.totalscore+=resulti.score;if(resulti.gender=O)score3.femalescore+=resulti.score;else score3.malescore+=resulti.score;break;case E:score4.totalscore+=result i.score;if(resultliJ.gender=O)scorel4J.femalescore+=resultiJ.score;else score4J.malescore+=resultLi.score;break;)i+;for(i=0;i5;i+)(printfCchool%d:ni);printf(Total score of male:%dnn,scoreij.malescore);printf(nTotal score of female:%dnH,scorei.femalescore);printf(Total score of all:%dnn,scorei.totalscore);1.19 解：#include#include#define MAXINT 65535define ArrSize 100int fun(int i);int main()(int i,k;int aA rrSize;coutArrSize-l)exit(0);for(i=0;iMAXINT)exit(0);else ai=2*i*ai-l;)for(i=0;iMAXINT)exit(0);else coutai?z ；return 0;)解二：Status algol 19(int aARRSIZE)求 i!*2八 i 序列的值且不超过 maxint(last=1;for(i=1 ;i=ARRSIZE;i+)(ai-l=last*2*i;if(ai-l/last)!=(2*i)reurn OVERFLOW;last=ai-l;return OK;/algol 19分析:当某一项的结果超过了 maxint时,它除以前面一项的商会发生异常.1.20void polyvalue()f l o a t a d;f l o a t *p=a;p r i n t f(nI n p u t n u m b e r o f t e r m s:);s c a n f(%dn,&n);p r i n t f(nI n p u t t h e%d c o e f f i c i e n t s f r o m a O t o a%d:n ,n,n);f o r(i=0;i=n;i+)s c a n f(%f ,p+);p r i n t f(nI n p u t v a l u e o f x:n);s c a n f(M%f;&x);p=a;x p=1 ;s u m=0;/x p用于存放x的i次方f o r(i=0;i=n;i+)(s u m+=x p*(*p+);x p:i：=x;)p r i n t f(Va l u e i s:%f ,s u m);/p o l y v a l u e解3:(上机已实现)要求实现下列函数：S t a t u s S e r i e s(i n t ARRS I Z E,i n t a );/*求i!*2 T序列的值并依次存入长度为ARRS 1Z E的数组a；*/*若所有值均不超过MAX I NT,则返回O K,否则返回OVERFL OW */S t a t u s S e r i e s(i n t ARRS I Z E,i n t a )/*求i!*2 T序列的值并依次存入长度为ARRS I Z E的数组a；*/*若所有值均不超过MAX I NT,则返回0 K,否则返回OVERFL OW */(i n t s=l,i,t;f o r(i=l;i t)r e t u r n OVERFL OW;s=a i-l;r e t u r n OK;)1.20 解:#i n c l u d e#i n c l u d e d e f i n e N 10d o u b l e p o l y n o m a i l(i n t a ,i n t i,d o u b l e x,i n t n);i n t m a i n()(d o u b l e x;i n t n,i;i n t a N;c o u t 输入变量的值x:；c i n x;c o u t N-l)e x i t(0);c o u t 输入多项式的系数a 0-a n:；f o r (i=0;i=n;i+)c i n a i;c o u t，zT h e p o l y n o m a i l v a l u e i s ，p o l y n o m a i l (a,n,x,n)0)r e t u r n a n-i+p o l y n o m a i l(a,i-1,x,n)*x;e l s e r e t u r n a n;本算法的时间复杂度为o(n)。解 3:(上机已实现)要求实现下列函数：f l o a t Po l y n o m i a l(i n t n,i n t a ,f l o a t x O);/*求一元多项式的值P(x O)。*/*数组a的元素a i 为 i 次项的系数，*/f l o a t Po l y n o m i a l(i n t n,i n t a ,f l o a t x)/*求一元多项式的值P(x)。*/*数组a的元素a i 为 i 次项的系数，i=0,.,n */i n t i;f l o a t t=l,s,p=0;t 存放 x 的 i 次方f o r (i=0;i=n;i+)(i f(i!=0)t*二 x;s=a i*t;p+=s;r e t u r n p;第 2 章 线 性 表2.1 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统处理。2.2 填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表声一表元素,具体移动的元素个数与无素疹麦内物位关。-(2)顺序表中逻辑上相邻的元素的物理位置还紧邻。单链表中逻辑上相邻的元素的物理位置方二定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的整缄效虐指示。(4)在单链表中设置头结点的作用先插入和删除首元结点时不用进行特殊处理,2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4 解：)U(245sI/k7LLLLL2.5 解：L pL-1 -3-5-7 A丁pL 247TpJ2.6 解：abcd2.7 解：abc(4)(1)(7)(11)(8)(4)(1)(12)(6)(11)(3)(14)(10)(12)(8)(3)(14)(10)(12)(7)(3)(14)(11)(3)(14)(11)(3)(14)(3)(6)(12)(4)(5)(13)rN!/)z7vu-1781-z(z(xzz(z(xde.a.b.c.(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17)2.9 解：(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10 解：Status DeleteK(SqList&a,in t i,int k)(从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始in t j;if(ia.length-1|ka.length-i)return INFEASIBLE;for(j=0;j=k;j+)a.elem j+i=a.elem j+i+k;a.length=a.length-k;return OK;)解二：Status DeleteK(SqList&a,in t i,int k)删除线性表a中第i个元素起的k个元素if(i l|ka.length)return INFEASIBLE;for(count=l;i+count-K=a.length-k;count+)注意循环结束的条件a.elemi+count-1=a.elem i+count+k-l;a.length-=k;return OK:/D el et eK2.1 1 设顺序表v a 中的数据元素递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。解：S t a t u s I n s er t O r d er L i s t(S q L i s t&v a,E l em T y p e x)(在非递减的顺序表v a 中插入元素x并使其仍成为顺序表的算法i n t i;i f(v a.l en g t h=v a.l i s t s i z e)r et u r n(O V E R F L O W);f or(i=v a.l en g t h;i 0,x v a.l i s t s i z e)r et u r n E R R O R;v a.l en g t h+;f or(i=v a.l en g t h-1;v a.el em i x&i =0;i-)v a.el em i+l =v a.el em i ;v a.el em i+l =x;r et u r n O K;/I n s er t _ S q L i s t解 3:(上机已实现)要求实现下列函数：v oi d I n s er t O r d er L i s t (S q L i s t&L,E l em T y p e x)/*在有序的顺序表L中保序插入数据元素x */顺序表类型定义如下：t y p ed ef s t r u c t E l em T y p e*el em;i n t l en g t h;i n t l i s t s i z e;S q L i s t;v oi d I n s er t O r d er L i s t(S q L i s t&L,E l em T y p e x)/在有序的顺序表L中保序插入数据元素x(i n t i,j;i=L.l en g t h-1;w h i 1 e(i =0&x =i+l;j)L.el em j+l =L el em j ;L.el em i+l =x;L l en g t h+;)2.1 2 解：S t a t u s C om p a r eO r d er L i s t(S q L i s t&A,S q L i s t&B)(i n t i,k,j;k=A.l en g t h B.l en g t h?A.l en g t h:B.l en g t h;f or(i=0;i B.el em i )j=l;i f (A.el em i k)j=l;i f(B.l en g t h k)j=-l;i f(A.l en g t h=B.l en g t h)j=0;r et u r n j;)解二：i n t L i s t C om p(S q L i s t A,S q L i s t B)比较字符表A和 B,并用返回值表示结果，值为正，表示A B;值为负，表示A B*/顺序表类型定义如下：t yp e d e f s t r u c t (E le mT yp e *e le m;int le ng t h;int lis t s iz e;Sq Lis t;c h a r C o mp a r e(Sq Lis t A,Sq Lis t B)/比较顺序表A 和 B,/返回 B(int i;f o r (i=0;A.e le m i B.e le m i;i+)if (A.e le m i !=B.e le m i)if (A.e le m i-B.e le m i 0)r e t u r n ;e ls e r e t u r n ；r e t u r n =；)2.13试写一算法在带头结点的单链表结构上实现线性表操作Lo c a t e (L,x);解:int Lo c a t e E le m_ L(LinkLis t&.L,E le mT yp e x)(int i=0;LinkLis t p=L;wh ile(p&p-d a t a!=x)p=p-ne xt;i+；)if(!p)r e t u r n 0;e ls e r e t u r n i;解二:LNo d e*Lo c a t e(LinkLis t L,int x)链表上的元素查找，返回指针(f o r(p=l-ne xt;p&p-d a t a!=x;p=p-ne xt);r e t u r n p;/Lo c a t e解 3:(上机已实现)实现下列函数：LinkLis t Lo c a t e(LinkLis t L,E le mT yp e x);/If x in t h e linke d lis t wh o s e h e a d no d e is p o int e d/b y L,t h e n r e t u r n p o int e r p o int ing no d e x,/o t h e r wis e r e t u r n NULL单链表类型定义如下：t yp e d e f s t r u c t LNo d e E le mT yp e d a t a;s t r u c t LNo d e *ne xt;LNo d e,*LinkLis t;LinkLis t Lo c a t e(LinkLis t&L,E le mT yp e x)/If x in t h e linke d lis t wh o s e h e a d no d e is p o int e d/b y L,t h e n r e t u r n p o int e r h a p o int ing no d e x,/o t h e r wis e r e t u r n NULL(LinkLis t p;f o r(p=L-ne xt;p&p-d a t a!=x;p=p-ne xt);r e t u r n p;)2.1 4 试写一算法在带头结点的单链表结构上实现线性表操作Le ng t h (L)。解:返回单链表的长度int Lis t Le ng t h _ L(LinkLis t&L)(int i=0;LinkLis t p=L;i f (p)p=p-ne xt;wh ile(p)p=p-ne xt;i+；)r e t u r n i;)解二：int Le ng t h(LinkLis t L)求链表的长度(f o r (k=0,p=L;p-ne xt;p=p-ne xt,k+);r e t u r n k;/Le ng t h解 3:(上机已实现)实现下列函数：int Le ng t h(LinkLis t L);/R e t u r n t h e le ng t h o f t h e linke d lis t/wh o s e h e a d no d e is p o int e d b y L单链表类型定义如下：t yp e d e f s t r u c t LNo d e E le mT yp e d a t a;s t r u c t LNo d e *ne xt;LNo d e,*LinkLis t;int Le ng t h(LinkLis t L)/R e t u r n t h e le ng t h o f t h e linke d lis t/wh o s e h e a d no d e is p o int e d b y LLinkLis t p;int k;f o r (k=0,p=L;p-ne xt;p=p-ne xt,k+);r e t u r n k;)2.15 解：vo id Me r g e Lis t L(LinkLis t&h a,LinkLis t&h b,LinkLis t&h c)(LinkLis t p a,p b;p a 二 h a;p b=h b;wh ile(p a-ne xt&p b-ne xt)p a=p a-ne xt;p b=p b-ne xt;)if(!p a-ne xt)h c=h b;wh ile(p b-ne xt)p b=p b-ne xt;p b-ne xt=h a-ne xt;)e ls e h c=h a;wh ile(p a-ne xt)p a=p a-ne xt;p a-ne xt=h b-ne xt;)解二：vo id I.is t C o nc a t (LinkLis t h a,LinkLis t h b,LinkLis t&h c)把链表 h b 接在 h a 后面形成链表 h e(h c=h a;p=h a;wh ile(p-ne xt)p=p-ne xt;p-ne xt=h b;/Lis t C o nc a t2.16 解：St a t u s D e le t e And lns e r t Su b(LinkLis t&la,LinkLis t&lb,int i,int j,int le n)(LinkLis t p,q,s,p r e v=NULL;int k=l;if(i 0：j 0|le n 0)r e t u r n INF E ASIBLE;/在 la 表中查找第i 个结点P=la;wh ile(p&k ne xt;k+;)if(!p)r e t u r n INF E ASIBLE;/在 la 表中查找第i+le n-l个结点q=p;k=l;wh ile(q&k ne xt;k+;)if(!q)r e t u r n INF E ASIBLE;/完成删除，注意，i=l的情况需要特殊处理if(!p r e v)la=q-ne xt;e ls e p r e v-ne xt=q-ne xt;/将 从 la 中删除的结点插入到lb 中if(j=l)q-ne xt=lb;lb 二 p;)e ls e s=lb;k=l;wh ile(s&k ne xt;k+;)if(!s)r e t u r n INF E ASIBLE;q-ne xt=s-ne xt;s-ne xt=p;完成插入)r e t u r n OK;)解 3:(上机已实现)实现下列函数：St a t u s D e le t e And lns e r t Su b(LinkLis t&la,LinkLis t&lb,int i,int j,int le n);/la 和 lb 分别指向两个单链表中第一个结点，*/*本算法是从la 表中删去自第i 个元素起共le n个元素，*/*并将它们插入到1b 表中第j 个元素之前，*/*若 1b 表中只有j T个元素，则插在表尾。单链表类型定义如下：*/t yp e d e f s t r u c t LNo d e E le mT yp e d a t a;s t r u c t LNo d e *ne xt;LNo d e,LinkLis t;St a t u s D e le t e And lns e r t Su b(LinkLis t&la,LinkLis t&lb,int i,int j,int le n)/la 和 lb 分别指向两个单链表中第一个结点，*/*本算法是从la 表中删去自第i 个元素起共le n个元素，*/*并将它们插入到1b 表中第j 个元素之前，*/*若 1b 表中只有j-1个元素，则插在表尾。*/(LinkLis t p,q,s,p r e v;int k;if(i=0|j=0|le n=0)r e t u r n INF E ASIBLE;p=la;k=l;wh ile(p&k ne xt;k+;)if(!p)r e t u r n INF E ASIBLE;q=P；k=l；wh ile(q&k ne xt;k+;)if(!q)r e t u r n INF E ASIBLE;if(i=l)la=q-ne xt;e ls e p r e v-ne xt=q-ne xt;if (j=l)q-ne xt=lb;lb=p;e ls e s=lb;k=l;wh ile(s&k ne xt;k+;if(!s)r e t u r n INF E ASIBLE;q-ne xt=s-ne xt;s-ne xt=p;)r e t u r n OK;2.17 解：St a t u s Ins e r t (LinkLis t&L,int i,int b)在无头结点链表L 的第i 个元素之前插入元素b(p=L;q=(LinkLis t*)ma llo c(s iz e o f(LNo d e);q.d a t a=b;if(i=l)(q.ne xt=p;L=q;插入在链表头部)e ls e(wh ile(-i l)p=p-ne xt;q-ne xt=p-ne xt;p-ne xt=q;插入在第i 个元素的位置)/Ins e r t2.18 试写一算法，实现线性表操作D e le t e(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。解:St a t u s D e le t e(LinkLis t&L,int i)在无头结点链表L 中删除第i 个元素(if(i=l)L=L-ne xt;删除第一个元素e ls e(P二 L;wh ile(-i l)p=p-ne xt;p-ne xt=p-ne xt-ne xt;删除第 i 个元素)/D e le t e2.19 解：St a t u s Lis t D e le t e _ L(LinkLis t&L,E le mT