1、 .1 簡述以下算法的功能：（1）Status A(LinkedList L)   /L是無表頭結(jié)點(diǎn)的單鏈表      if(L&&L->next)       Q=L;L=L->next;P=L;       While（P->next）P=P->next；P->next=Q；Q->n

2、ext=NULL;return OK;/A（2）void BB(LNode*s,LNode*q)        p=s;       While(p->next!=q) p=p->next;       p->next=s;       /BBVoid 

3、;AA(LNode*pa,LNode*pb)        /pa和pb分別指向單循環(huán)鏈表中的兩個節(jié)點(diǎn)       BB(pa,pb);       BB(pb,pa);       /AA2 指出以下算法中的錯誤和低效（既費(fèi)時）之處，并將它改寫為一個即正確又高效的算法。Status De

4、leteK(SqList&a,int i,int k)/本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的K個元素If (i<1|k<0|i+k>a.length) return  INFEASIBLE; /參數(shù)不合法else   for(count=1;count <k;count+)     /刪除一個元素     For(j=a.length;j&g

5、t;=i+1;j- -) a.elemj- 1=a.elemj;a. length- -;Return OK;/DeleteK下列算法設(shè)計題涉及的順序表和線性鏈表的類型定義如下：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10Typedef structElemType *elem； /存儲空間基址int length； /當(dāng)前的長度int listsize； /當(dāng)前分配的存儲容量SqList； /順序表類型Typedef struct LNodeElemType data；struct LN

6、ode *next；LNode，*LinkList； /線性鏈表類型2.11設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。2.13試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE（L，X）。2.14試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH(L)。2.15已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點(diǎn)，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點(diǎn)連在另一個表的最后一個結(jié)點(diǎn)之后），假設(shè)指針hc指向連接后的鏈表頭結(jié)點(diǎn)，并要求算法以盡可能短的時間完成連接運(yùn)算。請分析你的算法

7、的時間復(fù)雜度。2.17 試寫一算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作INSERT(L，i，b)，并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。2.18試寫一算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作DELETE(L，i)，并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。2.19 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于maxk的元素（若表中存在這樣的元素）同時釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時間復(fù)雜度（注意：mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。2.21 試寫一算

8、法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1，a2，an）逆置為（an，an-1，a1）。2.22 試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。參考答案2.10 Status DeleteK(SqList &a,int i,int k)/刪除線性表a中第i個元素起的k個元素  if(i<1|k<0|i+k-1>a.length) return INFEASIBLE;  for(count=1;i+count-1<=a.length-k;count+) /注意循環(huán)結(jié)束的條件    

9、;a.elemi+count-1=a.elemi+count+k-1;  a.length-=k;  return OK;/DeleteK 2.11Status Insert_SqList(SqList &va,int x)/把x插入遞增有序表va中  if(va.length+1>va.listsize) return ERROR;  va.length+;  for(i=va.length-1;va.elemi>x&&i>=0;i-) &#

10、160;  va.elemi+1=va.elemi;  va.elemi+1=x;  return OK;/Insert_SqList 2.12 int ListComp(SqList A,SqList B)/比較字符表A和B,并用返回值表示結(jié)果,值為正,表示A>B;值為負(fù),表示A<B;值為零,表示A=B  for(i=1;A.elemi|B.elemi;i+)    if(A.elemi!=B.elemi) return A.elemi-B.elemi;

11、0; return 0;/ListComp 2.13 LNode* Locate(LinkList L,int x)/鏈表上的元素查找,返回指針  for(p=l->next;p&&p->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 L

12、istConcat(LinkList ha,LinkList hb,LinkList &hc)/把鏈表hb接在ha后面形成鏈表hc  hc=ha;p=ha;  while(p->next) p=p->next;  p->next=hb;/ListConcat 2.16 見書后答案. 2.17 Status Insert(LinkList &L,int i,int b)/在無頭結(jié)點(diǎn)鏈表L的第i個元素之前插入元素b  p=L;q=(LinkList*)malloc(sizeof(LNo

13、de);  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個元素的位置  /Insert 2.18 Status De

14、lete(LinkList &L,int i)/在無頭結(jié)點(diǎn)鏈表L中刪除第i個元素  if(i=1) L=L->next; /刪除第一個元素  else      p=L;    while(-i>1) p=p->next;    p->next=p->next->next; /刪除第i個元素  /Delete 2.19 Status Delete_Bet

15、ween(Linklist &L,int mink,int maxk)/刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素  p=L;  while(p->next->data<=mink) p=p->next; /p是最后一個不大于mink的元素  if(p->next)    /如果還有比mink更大的元素      q=p->next;   &

16、#160;while(q->data<maxk) q=q->next; /q是第一個不小于maxk的元素    p->next=q;  /Delete_Between 2.20 Status Delete_Equal(Linklist &L)/刪除元素遞增排列的鏈表L中所有值相同的元素  p=L->next;q=p->next; /p,q指向相鄰兩元素  while(p->next)     &#

17、160;if(p->data!=q->data)          p=p->next;q=p->next; /當(dāng)相鄰兩元素不相等時,p,q都向后推一步        else          while(q->data=p->data) free(q); q=q->next

18、;       p->next=q;p=q;q=p->next; /當(dāng)相鄰元素相等時刪除多余元素    /else  /while/Delete_Equal 2.21 void reverse(SqList &A)/順序表的就地逆置  for(i=1,j=A.length;i<j;i+,j-)    A.elemi<->A.elemj;/reverse 2.22 void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2  p=L->next;q=p->next;s