熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

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

2013-11-15 15:32:18  來源: 數據結構 

  第二章 線性表

  

  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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.