线性表习题解答

《线性表习题解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.10StatusDeleteK(SqList&a,inti,intk)//删除线性表a中第i个元素起的k个元素{if(i<1

2、

3、k<0

4、

5、i+k-1>a.length)returnINFEASIBLE;for(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;returnOK;}//DeleteK2.11设顺序表Va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保证该表的有序性。vo

6、idInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1>va.listsize)printf(“满不能插入”);else{va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;}}//Insert_SqList2.12intListComp(SqListA,SqListB)//比较字符表A和B,并用返回值表示结果,值为1,表示A>B;值为-1,表示A

7、0,表示A=B{for(i=1;i<=A.length&&i<=B.length;i++)if(A.elem[i]!=B.elem[i])returnA.elem[i]>B.elem[i]?1:-1;if(A.length==B.length)return0;returnA.length>B.length?1:-1;//当两个字符表可以互相比较的部分完全相同时,哪个较长,哪个就较大}//ListComp2.13LNode*Locate(LinkListL,intx)//链表上的查找元素x,返回指针{for(p=l->next;p&&p->data!=x

8、;p=p->next);returnp;}//Locate2.14试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。intLength(LinkListL)//求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);returnk;}//Length2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知了两个链表的长度分别为m和n，试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算，

9、请分析你的算法的时间复杂度。voidListConcat(LinkListha,LinkListhb,LinkList&hc)//把链表hb接在ha后面形成链表hc{hc=ha;p=ha;while(p->next)p=p->next;p->next=hb;}//ListConcat2.17StatusInsert(LinkList&L,inti,intb)//在无头结点链表L的第i个元素之前插入元素b{p=L;q=(LinkList*)malloc(sizeof(LNode));q.data=b;if(i==1){q.next=p;L=q;//插入在

10、链表头部}else{while(--i>1)p=p->next;q->next=p->next;p->next=q;//插入在第i个元素的位置}}//Insert2.18StatusDelete(LinkList&L,inti)//在无头结点链表L中删除第i个元素{if(i==1)L=L->next;//删除第一个元素else{p=L;while(--i>1)p=p->next;p->next=p->next->next;//删除第i个元素}}//Delete2.19知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有

11、值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删除结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。voidDelete_Between(Linklist&L,intmink,intmaxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{p=L;while(p->next->data<=mink)p=p->next;//p是最后一个不大于mink的元素if(p->next)//如果还有比mink更大的元素{q=p->next;whi

12、le(q->datanext;//q是第一个不小于maxk的元素p->n