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

數據結構與算法線性表復習習題【5】[1]

2013-11-15 15:26:01  來源: 數據結構 

   試寫一算法對單鏈表實現就地逆置

  解

  // 帶頭結點的單鏈表的逆置

  Status ListOppose_L(LinkList &L)

  {

  LinkList pq;

  p=L;

  p=p>next;

  L>next=NULL;

  while(p){

  q=p;

  p=p>next;

  q>next=L>next;

  L>next=q;

  }

  return OK;

  }

   假設有兩個按元素值遞增有序排列的線性表A和B均以單鏈表作存儲結構請編寫算法將A表和B表歸並成一個按元素值遞減有序(即非遞增有序允許表中含有值相同的元素)排列的線性表C並要求利用原表(即A表和B表)的結點空間構造C表

  解

  // 將合並逆置後的結果放在C表中並刪除B表

  Status ListMergeOppose_L(LinkList &ALinkList &BLinkList &C)

  {

  LinkList papbqaqb;

  pa=A;

  pb=B;

  qa=pa;// 保存pa的前驅指針

  qb=pb;// 保存pb的前驅指針

  pa=pa>next;

  pb=pb>next;

  A>next=NULL;

  C=A;

  while(pa&&pb){

  if(pa>data<pb>data){

  qa=pa;

  pa=pa>next;

  qa>next=A>next;//將當前最小結點插入A表表頭

  A>next=qa;

  }

  else{

  qb=pb;

  pb=pb>next;

  qb>next=A>next;//將當前最小結點插入A表表頭

  A>next=qb;

  }

  }

  while(pa){

  qa=pa;

  pa=pa>next;

  qa>next=A>next;

  A>next=qa;

  }

  while(pb){

  qb=pb;

  pb=pb>next;

  qb>next=A>next;

  A>next=qb;

  }

  pb=B;

  free(pb);

  return OK;

  }

   假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合(即同一表中的元素值各不相同)現要求另辟空間構成一個線性表C其元素為A和B中元素的交集且表C中的元素有依值遞增有序排列試對順序表編寫求C的算法

  解

  // 將AB求交後的結果放在C表中

  Status ListCross_Sq(SqList &ASqList &BSqList &C)

  {

  int i=j=k=;

  while(i<Alength && j<Blength){

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

  else

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

  else{

  ListInsert_Sq(CkAelem[i]);

  i++;

  k++;

  }

  }

  return OK;

  }

[]  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23404.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.