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

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

2013-11-15 15:31:21  來源: 數據結構 

  第九章 查找第十章 內部排序

  

  void Insert_Sort(SqList &L)//監視哨設在高下標端的插入排序算法

  {

  k=Llength;

  for(i=k;i;i) //從後向前逐個插入排序

  if(Lr[i]key>Lr[i+]key)

  {

  Lr[k+]key=Lr[i]key; //監視哨

  for(j=i+;Lr[j]key>Lr[i]key;++j)

  Lr[j]key=Lr[j]key; //前移

  Lr[j]key=Lr[k+]key; //插入

  }

  }//Insert_Sort

  

  void BiInsert_Sort(SqList &L)//二路插入排序的算法

  {

  int d[MAXSIZE]; //輔助存儲

  x=Lrkey;d=x;

  first=;final=;

  for(i=;i<=Llength;i++)

  {

  if(Lr[i]key>=x) //插入前部

  {

  for(j=final;d[j]>Lr[i]key;j)

  d[j+]=d[j];

  d[j+]=Lr[i]key;

  final++;

  }

  else //插入後部

  {

  for(j=first;d[j]

  d[j-1]=d[j];

  d[(j-2)%MAXSIZE+1]=L.r[i].key;

  first=(first-2)%MAXSIZE+1; //這種形式的表達式是為了兼顧first=1的情況

  }

  }//for

  for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//將序列復制回去

  L.r[j].key=d[i];

  }//BiInsert_Sort

  10.25

  void SLInsert_Sort(SLList &L)//靜態鏈表的插入排序算法

  {

  L.r[0].key=0;L.r[0].next=1;

  L.r[1].next=0; //建初始循環鏈表

  for(i=2;i<=L.length;i++) //逐個插入

  {

  p=0;x=L.r[i].key;

  while(L.r[L.r[p].next].key

  p=L.r[p].next;

  q=L.r[p].next;

  L.r[p].next=i;

  L.r[i].next=q;

  }//for

  p=L.r[0].next;

  for(i=1;i

  {

  while(p

  q=L.r[p].next;

  if(p!=i)

  {

  L.r[p]<->L.r[i];

  L.r[i].next=p;

  }

  p=q;

  }//for

  }//SLInsert_Sort

  10.26

  void Bubble_Sort1(int a[ ],int n)//對包含n個元素的數組a進行改進的冒泡排序

  {

  change=n-1; //change指示上一趟冒泡中最後發生交換的元素

  while(change)

  {

  for(c=0,i=0;i

  if(a[i]>a[i+1])

  {

  a[i]<->a[i+1];

  c=i+1; //c指示這一趟冒泡中發生交換的元素

  }

  change=c;

  }//while

  }//Bubble_Sort1

  10.27

  void Bubble_Sort2(int a[ ],int n)//相鄰兩趟是反方向起泡的冒泡排序算法

  {

  low=0;high=n-1; //冒泡的上下界

  change=1;

  while(low

  {

  change=0;

  for(i=low;i

  if(a[i]>a[i+1])

  {

  a[i]<->a[i+1];

  change=1;

  }

  high--; //修改上界

  for(i=high;i>low;i--) //從下向上起泡

  if(a[i]

  {

  a[i]<->a[i-1];

  change=1;

  }

  low++; //修改下界

  }//while

  }//Bubble_Sort2

  10.28

  void Bubble_Sort3(int a[ ],int n)//對上一題的算法進行化簡,循環體中只包含一次冒泡

  {

  int b[ 3 ]; //b[0]為冒泡的下界,b[ 2 ]為上界,b[1]無用

  d=1;b[0]=0;b[ 2 ]=n-1; //d為冒泡方向的標識,1為向上,-1為向下

  change=1;

  while(b[0]

  {

  change=0;

  for(i=b[1-d];i!=b[1+d];i+=d) //統一的冒泡算法

  if((a[i]-a[i+d])*d>0) //注意這個交換條件

  {

  a[i]<->a[i+d];

  change=1;

  }

  b[1+d]-=d; //修改邊界

  d*=-1; //換個方向

  }//while

  }//Bubble_Sort3

  10.29

  void OE_Sort(int a[ ],int n)//奇偶交換排序的算法

  {

  change=1;

  while(change)

  {

  change=0;

  for(i=1;i

  if(a[i]>a[i+1])

  {

  a[i]<->a[i+1];

  change=1;

  }

  for(i=0;i

  if(a[i]>a[i+1])

  {

  a[i]<->a[i+1];

  change=1;

  }

  }//while

  }//OE_Sort

  分析:本算法的結束條件是連續兩趟比較無交換發生

  10.30

  typedef struct {

  int low;

  int high;

  } boundary; //子序列的上下界類型

  void QSort_NotRecurve(int SQList &L)//快速排序的非遞歸算法

  {

  low=1;high=L.length;

  InitStack(S); //S的元素為boundary類型

  while(low

  {

  if(high-low>2) //如果當前子序列長度大於3且尚未排好序

  {

  pivot=Partition(L,low,high); //進行一趟劃分

  if(high-pivot>pivot-low)

  {

  Push(S,{pivot+1,high}); //把長的子序列邊界入棧

  high=pivot-1; //短的子序列留待下次排序

  }

  else

  {

  Push(S,{low,pivot-1});

  low=pivot+1;

  }

  }//if

  else if(low

  {

  Easy_Sort(L,low,high); //直接進行比較排序

  low=high; //當前子序列標志為已排好序

  }

  else //如果當前子序列已排好序但棧中還有未排序的子序列

  {

  Pop(S,a); //從棧中取出一個子序列

  low=a.low;

  high=a.high;

  }

  }//while

  }//QSort_NotRecurve

  int Partition(SQList &L,int low,int high)//一趟劃分的算法,與書上相同

  {

  L.r[0]=L.r[low];

  pivotkey=L.r[low].key;

  while(low

  {

  while(low=pivotkey)

  high--;

  L.r[low]=L.r[high];

  while(low

  low++;

  L.r[high]=L.r[low];

  }//while

  L.r[low]=L.r[0];

  return low;

  }//Partition

  void Easy_Sort(SQList &L,int low,int high)//對長度小於3的子序列進行比較排序

  {

  if(high-low==1) //子序列只含兩個元素

  if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];

  else //子序列含有三個元素

  {

  if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];

  if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];

  if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];

  }

  }//Easy_Sort

  10.31

  void Divide(int a[ ],int n)//把數組a中所有值為負的記錄調到非負的記錄之前

  {

  low=0;high=n-1;

  while(low

  {

  while(low=0) high--; //以0作為虛擬的樞軸記錄

  a[low]<->a[high];

  while(low

  a[low]<->a[high];

  }

  }//Divide

  10.32

  typedef enum {RED,WHITE,BLUE} color; //三種顏色

  void Flag_Arrange(color a[ ],int n)//把由三種顏色組成的序列重排為按照紅,白,藍的順序排列

  {

  i=0;j=0;k=n-1;

  while(j<=k)

  switch(a[j])

  {

  case RED:

  a[i]<->a[j];

  i++;

  j++;

  break;

  case WHITE:

  j++;

  break;

  case BLUE:

  a[j]<->a[k];

  k--; //這裡沒有j++;語句是為了防止交換後a[j]仍為藍色的情況

  }

  }//Flag_Arrange

  分析:這個算法
From:http://tw.wingwit.com/Article/program/sjjg/201311/23549.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.