数据结构作业-线性表2

《数据结构作业-线性表2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1 简述以下算法的功能：（1）Status A(LinkedList L)   {//L是无表头结点的单链表      if(L&&L->next){       Q=L;L=L->next;P=L;       While（P->next）P=P->next；P->next=Q；Q->next=NULL;}return OK;}//A（2）void BB(LNode*s,LNode*q) {       p=s;       While(p->next!=q) p=p->next;       p->next=s

2、;       }//BBVoid AA(LNode*pa,LNode*pb) {       //pa和pb分别指向单循环链表中的两个节点       BB(pa,pb);       BB(pb,pa);       }//AA2 指出以下算法中的错误和低效（既费时）之处，并将它改写为一个即正确又高效的算法。Status DeleteK(SqList&a,int i,int k){//本过程从顺序存储结构的线性表a中删除第i个元素起的K个元素If (i<1

3、

4、k<0

5、

6、i+k>a.length) return 

7、 INFEASIBLE; //参数不合法else{   for(count=1;count =i+1;j- -) a.elem[j- 1]=a.elem[j];a.length- -;}Return OK;}//DeleteK下列算法设计题涉及的顺序表和线性链表的类型定义如下：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{ElemType*elem；

8、//存储空间基址intlength；//当前的长度intlistsize；//当前分配的存储容量｝SqList；//顺序表类型TypedefstructLNode{ElemTypedata；structLNode*next；｝LNode，*LinkList；//线性链表类型2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.13试写一算法在带头结点的单链表结构上实现线性表操作LOCATE（L，X）。2.14试写一算法在带头结点的单链表结构上实现线性表操作LEN

9、GTH(L)。2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。2.17试写一算法，在无头结点的动态单链表结构上实现线性表操作INSERT(L，i，b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.18试写一算法，在无头结点的动态单链表结构上实现线性表操作DELETE

10、(L，i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，a2，…，an）逆置为（an，an-1，…，a1）。2.22试写一算法，对单链表实现就地逆置。参考

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

12、

13、k<0

14、

15、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.11StatusInsert_SqLi

16、st(SqList&va,intx)//把x插入递增有序表va中{  if(va.length+1>va.listsize)returnERROR;  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;  re