嚴蔚敏《數據結構(c語言版)習題集》算法設計題第二章參考答案

　　第二章 線性表

　　

　　Status DeleteK(SqList &aint iint k)//刪除線性表a中第i個元素起的k個元素

　　{

　　if(i<||k<||i+k>alength) return INFEASIBLE;

　　for(count=;i+count<=alengthk;count++) //注意循環結束的條件

　　aelem[i+count]=aelem[i+count+k];

　　alength=k;

　　return OK;

　　}//DeleteK

　　

　　Status Insert_SqList(SqList &vaint x)//把x插入遞增有序表va中

　　{

　　if(valength+>valistsize) return ERROR;

　　valength++;

　　for(i=valength;vaelem[i]>x&&i>=;i)

　　vaelem[i+]=vaelem[i];

　　vaelem[i+]=x;

　　return OK;

　　}//Insert_SqList

　　

　　int ListComp(SqList ASqList B)//比較字符表A和B並用返回值表示結果值為正表示A>B;值為負表示A

　　{

　　for(i=;Aelem[i]||Belem[i];i++)

　　if(Aelem[i]!=Belem[i]) return Aelem[i]Belem[i];

　　return ;

　　}//ListComp

　　

　　LNode* Locate(LinkList Lint x)//鏈表上的元素查找返回指針

　　{

　　for(p=l>next;p&&p>data!=x;p=p>next);

　　return p;

　　}//Locate

　　

　　int Length(LinkList L)//求鏈表的長度

　　{

　　for(k=p=L;p>next;p=p>nextk++);

　　return k;

　　}//Length

　　

　　void ListConcat(LinkList haLinkList hbLinkList &hc)//把鏈表hb接在ha後面形成鏈表hc

　　{

　　hc=ha;p=ha;

　　while(p>next) p=p>next;

　　p>next=hb;

　　}//ListConcat

　　

　　見書後答案

　　

　　Status Insert(LinkList &Lint iint b)//在無頭結點鏈表L的第i個元素之前插入元素b

　　{

　　p=L;q=(LinkList*)malloc(sizeof(LNode));

　　qdata=b;

　　if(i==)

　　{

　　qnext=p;L=q; //插入在鏈表頭部

　　}

　　else

　　{

　　while(i>) p=p>next;

　　q>next=p>next;p>next=q; //插入在第i個元素的位置

　　}

　　}//Insert

　　

　　Status Delete(LinkList &Lint i)//在無頭結點鏈表L中刪除第i個元素

　　{

　　if(i==) L=L>next; //刪除第一個元素

　　else

　　{

　　p=L;

　　while(i>) p=p>next;

　　p>next=p>next>next; //刪除第i個元素

　　}

　　}//Delete

　　

　　Status Delete_Between(Linklist &Lint minkint maxk)//刪除元素遞增排列的鏈表L中值大於mink且小於maxk的所有元素

　　{

　　p=L;

　　while(p>next>data<=mink) p=p>next; //p是最後一個不大於mink的元素

　　if(p>next) //如果還有比mink更大的元素

　　{

　　q=p>next;

　　while(q>datanext; //q是第一個不小於maxk的元素

　　p>next=q;

　　}

　　}//Delete_Between

　　

　　Status Delete_Equal(Linklist &L)//刪除元素遞增排列的鏈表L中所有值相同的元素

　　{

　　p=L>next;q=p>next; //pq指向相鄰兩元素

　　while(p>next)

　　{

　　if(p>data!=q>data)

　　{

　　p=p>next;q=p>next; //當相鄰兩元素不相等時pq都向後推一步

　　}

　　else

　　{

　　while(q>data==p>data)

　　{

　　free(q);

　　q=q>next;

　　}

　　p>next=q;p=q;q=p>next; //當相鄰元素相等時刪除多余元素

　　}//else

　　}//while

　　}//Delete_Equal

　　

　　void reverse(SqList &A)//順序表的就地逆置

　　{

　　for(i=j=Alength;i

　　Aelem[i]<>Aelem[j];

　　}//reverse

　　

　　void LinkList_reverse(Linklist &L)//鏈表的就地逆置;為簡化算法假設表長大於

　　{

　　p=L>next;q=p>next;s=q>next;p>next=NULL;

　　while(s>next)

　　{

　　q>next=p;p=q;

　　q=s;s=s>next; //把L的元素逐個插入新表表頭

　　}

　　q>next=p;s>next=q;L>next=s;

　　}//LinkList_reverse

　　分析:本算法的思想是逐個地把L的當前元素q插入新的鏈表頭部p為新表表頭

　　

　　void merge(LinkList &ALinkList &BLinkList &C)//把鏈表A和B合並為CA和B的元素間隔排列且使用原存儲空間

　　{

　　p=A>next;q=B>next;C=A;

　　while(p&&q)

　　{

　　s=p>next;p>next=q; //將B的元素插入

　　if(s)

　　{

　　t=q>next;q>next=s; //如A非空將A的元素插入

　　}

　　p=s;q=t;

　　}//while

　　}//merge

　　

　　void reverse_merge(LinkList &ALinkList &BLinkList &C)//把元素遞增排列的鏈表A和B合並為C且C中元素遞減排列使用原空間

　　{

　　pa=A>next;pb=B>next;pre=NULL; //pa和pb分別指向AB的當前元素

　　while(pa||pb)

　　{

　　if(pa>datadata||!pb)

　　{

　　pc=pa;q=pa>next;pa>next=pre;pa=q; //將A的元素插入新表

　　}

　　else

　　{

　　pc=pb;q=pb>next;pb>next=pre;pb=q; //將B的元素插入新表

　　}

　　pre=pc;

　　}

　　C=A;A>next=pc; //構造新表頭

　　}//reverse_merge

　　分析:本算法的思想是按從小到大的順序依次把A和B的元素插入新表的頭部pc處最後處理A或B的剩余元素

　　

　　void SqList_Intersect(SqList ASqList BSqList &C)//求元素遞增排列的線性表A和B的元素的交集並存入C中

　　{

　　i=;j=;k=;

　　while(Aelem[i]&&Belem[j])

　　{

　　if(Aelem[i]

　　if(Aelem[i]>Belem[j]) j++;

　　if(Aelem[i]==Belem[j])

　　{

　　Celem[++k]=Aelem[i]; //當發現了一個在AB中都存在的元素

　　i++;j++; //就添加到C中

　　}

　　}//while

　　}//SqList_Intersect

　　

　　void LinkList_Intersect(LinkList ALinkList BLinkList &C)//在鏈表結構上重做上題

　　{

　　p=A>next;q=B>next;

　　pc=(LNode*)malloc(sizeof(LNode));

　　while(p&&q)

　　{

　　if(p>datadata) p=p>next;

　　else if(p>data>q>data) q=q>next;

　　else

　　{

　　s=(LNode*)malloc(sizeof(LNode));

　　s>data=p>data;

　　pc>next=s;pc=s;

　　p=p>next;q=q>next;

　　}

　　}//while

　　C=pc;

　　}//LinkList_Intersect

　　

　　void SqList_Intersect_True(SqList &ASqList B)//求元素遞增排列的線性表A和B的元素的交集並存回A中

　　{

　　i=;j=;k=;

　　while(Aelem[i]&&Belem[j])

　　{

　　if(Aelem[i]

　　else if(Aelem[i]>Belem[j]) j++;

　　else if(Aelem[i]!=Aelem[k])

　　{

　　Aelem[++k]=Aelem[i]; //當發現了一個在AB中都存在的元素

　　i++;j++; //且C中沒有就添加到C中

　　}

　　}//while

　　while(Aelem[k]) Aelem[k++]=;

　　}//SqList_Intersect_True

　　

　　void LinkList_Intersect_True(LinkList &ALinkList B)//在鏈表結構上重做上題

　　{

　　p=A>next;q=B>next;pc=A;

　　while(p&&q)

　　{

　　if(p>datadata) p=p>next;

　　else if(p>data>q>data) q=q>next;

　　else if(p>data!=pc>data)

　　{

　　pc=pc>next;

　　pc>data=p>data;

　　p=p>next;q=q>next;

　　}

　　}//while

　　}//LinkList_Intersect_True

　　

From:http://tw.wingwit.com/Article/program/sjjg/201311/23573.html