数据结构作业-线性表2.docVIP

1?简述以下算法的功能：（1）Status?A(LinkedList?L)???{//L是无表头结点的单链表??????if(LLnext){???????Q=L;L=L-next;P=L;???????While（Pnext）P=Pnext；Pnext=Q；Qnext=NULL;}return?OK;}//A（2）void?BB(LNode*s,LNode*q)?{???????p=s;???????While(pnext!=q)?p=p-next;???????p-next=s;???????}//BBVoid?AA(LNode*pa,LNode*pb)?{???????//pa和pb分别指向单循环链表中的两个节点???????BB(pa,pb);???????BB(pb,pa);???????}//AA2?指出以下算法中的错误和低效（既费时）之处，并将它改写为一个即正确又高效的算法。Status?DeleteK(SqLista,int?i,int?k){//本过程从顺序存储结构的线性表a中删除第i个元素起的K元素If?(i1||k0||i+ka.length)?return??INFEASIBLE;?//参数不合法else{???for(count=1;count?k;count++){?????//删除一个元素?????For(j=a.length;j=i+1;j-?-)?a.elem[j-?1]=a.elem[j];a. length-?-;}Return?OK;}//DeleteKTypedef struct{ ElemType *elem； //存储空间基址 int length； //当前的长度 int listsize； //当前分配的存储容量 ｝SqList； //顺序表类型 Typedef struct LNode{ ElemType data； struct LNode *next； ｝LNode，*LinkList； //线性链表类型 2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 …，an）逆置为（an，an-1，…，a1）。 试写一算法，对单链表实现就地逆置。 参考答案 2.10 Status DeleteK(SqList a,int i,int k)//删除线性表a中第i个元素起的k个元素{??if(i1||k0||i+k-1a.length) return INFEASIBLE;??for(count=1;i+count-1=a.length-k;count++) //注意循环结束的条件????a.elem[i+count-1]=a.elem[i+count+k-1];??a.length-=k;??return OK;}//DeleteK 2.11 Status Insert_SqList(SqList va,int x)//把x插入递增有序表va中{??if(va.length+1va.listsize) return ERROR;??va.length++;??for(i=va.length-1;va.elem[i]xi=0;i--)????va.elem[i+1]=va.elem[i];??va.elem[i+1]=x;??return OK;}//Insert_SqList 2.12 int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示AB;值为负,表示AB;值为零,表示A=B{??for(i=1;A.elem[i]||B.elem[i];i++)????if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];??return 0;}//ListComp 2.13 LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针{??for(p=l-next;pp-data!=x;p=p-next);??return p;}//Locate 2.14 int Length(LinkList L)//求链表的长度{??for(k=0,p=L;p-next;p=p-next,k++);??return k;}//Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList hc)//把链表hb接在ha后面形成链表hc{??hc=ha;p=ha