數據結構作業-線性表2.頁腳.

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;

}//BB

Void

AA(LNode*pa,LNode*pb)

{

//pa和pb分別指向單循環鏈表中的兩個節點

BB(pa,pb);

BB(pb,pa);

}//AA

2

指出以下算法中的錯誤和低效（既費時）之處，并將它改寫為一個即正確又高效的算法。

Status

DeleteK(SqList&a,int

i,int

k){

//本過程從順序存儲結構的線性表a中刪除第i個元素起的K個元素

If

(i<1||k<0||i+k>a.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;

}//DeleteK

下列算法設計題涉及的順序表和線性鏈表的類型定義如下：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{數據結構作業-線性表2全文共6頁，當前為第1頁。ElemType*elem；//存儲空間基址數據結構作業-線性表2全文共6頁，當前為第1頁。intlength；//當前的長度intlistsize；//當前分配的存儲容量｝SqList；//順序表類型TypedefstructLNode{ElemTypedata；structLNode*next；｝LNode，*LinkList；//線性鏈表類型2.11設順序表va中的數據元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。2.13試寫一算法在帶頭結點的單鏈表結構上實現線性表操作LOCATE（L，X）。2.14試寫一算法在帶頭結點的單鏈表結構上實現線性表操作LENGTH(L)。2.15已知指針ha和hb分別指向兩個單鏈表的頭結點，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結點連在另一個表的最后一個結點之后），假設指針hc指向連接后的鏈表頭結點，并要求算法以盡可能短的時間完成連接運算。請分析你的算法的時間復雜度。2.17試寫一算法，在無頭結點的動態單鏈表結構上實現線性表操作INSERT(L，i，b)，并和在帶頭結點的動態單鏈表上實現相同操作的算法進行比較。2.18試寫一算法，在無頭結點的動態單鏈表結構上實現線性表操作DELETE(L，i)，并和在帶頭結點的動態單鏈表上實現相同操作的算法進行比較。2.19已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。試寫一高效算法，刪除表中所有值大于maxk的元素（若表中存在這樣的元素）同時釋放被刪結點空間，并分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。2.21試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表（a1，a2，…，an）逆置為（an，an-1，…，a1）。試寫一算法，對單鏈表實現就地逆置。參考答案數據結構作業-線性表2全文共6頁，當前為第2頁。數據結構作業-線性表2全文共6頁，當前為第2頁。StatusDeleteK(SqList&a,inti,intk)//刪除線性表a中第i個元素起的k個元素

{

if(i<1||k<0||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_SqList(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;

returnOK;

}//Insert_SqList2.12intListComp(SqListA,SqListB)//比較字符表A和B,并用返回值表示結果,值為正,表示A>B;值為負,表示A<B;值為零,表示A=B

{

for(i=1;A.elem[i]||B.elem[i];i++)

if(A.elem[i]!=B.elem[i])returnA.elem[i]-B.elem[i];

return0;

}//ListComp2.13LNode*Locate(LinkListL,intx)//鏈表上的元素查找,返回指針

{

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

returnp;

}//Locate2.14數據結構作業-線性表2全文共6頁，當前為第3頁。intLength(LinkListL)//求鏈表的長度

{

for(k=0,p=L;p->next;p=p->n數據結構作業-線性表2全文共6頁，當前為第3頁。2.15voidListConcat(LinkListha,LinkListhb,LinkList&hc)//把鏈表hb接在ha后面形成鏈表hc

{

hc=ha;p=ha;

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

p->next=hb;

}//ListConcat2.16見書后答案.2.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;//插入在鏈表頭部

}

else

{

while(--i>1)p=p->next;

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

}

}//Insert2.18數據結構作業-線性表2全文共6頁，當前為第4頁。StatusDelete(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個元素數據結構作業-線性表2全文共6頁，當前為第4頁。2.19StatusDelete_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;

while(q->data<maxk)q=q->next;//q是第一個不小于maxk的元素

p->next=q;

}

}//Delete_Between2.20StatusDelete_Equal(Linklist&L)//刪除元素遞增排列的鏈表L中所有值相同的元素

{

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

while(p->next)

{

if(p->data!=q->data)

{

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

}

else

{

while(q->data==p->data)

{

free(q);

q=q->next;

}

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

}//else

}//while

}//Delete_Equal數據結構作業-線性表2全文共6頁，當前為第5頁。數據結構作業-線性表2全文共6頁，當前為第5頁。voidreverse(SqList&A)//順序表的就地逆置

{

for(i=1,j=A.length;i<j;i++,j--)

A.elem[i]<->A.elem[j];

}//reverse2.22voidLinkList_reverse(Linklist&L)//鏈表的就地逆置;為簡化算法,假設表長大于2

{

p=L->next;q=p->next