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

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

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

  第五章 數組和廣義表

  

  void RSh(int A[n]int k)//把數組A的元素循環右移k位只用一個輔助存儲空間

  {

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

  if(n%i==&&k%i==) p=i;//求n和k的最大公約數p

  for(i=;i

  {

  j=i;l=(i+k)%n;temp=A[i];

  while(l!=i)

  {

  A[j]=temp;

  temp=A[l];

  A[l]=A[j];

  j=l;l=(j+k)%n;

  }// 循環右移一步

  A[i]=temp;

  }//for

  }//RSh

  分析:要把A的元素循環右移k位,則A[0]移至A[k],A[k]移至A[2k]......直到最終回到A[0].然而這並沒有全部解決問題,因為有可能有的元素在此過程中始終沒有被訪問過,而是被跳了過去.分析可知,當n和k的最大公約數為p時,只要分別以A[0],A[1],...A[p-1]為起點執行上述算法,就可以保證每一個元素都被且僅被右移一次,從而滿足題目要求.也就是說,A的所有元素分別處在p個"循環鏈"上面.舉例如下:

  n=15,k=6,則p=3.

  第一條鏈:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].

  第二條鏈:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].

  第三條鏈:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].

  恰好使所有元素都右移一次.

  雖然未經數學證明,但作者相信上述規律應該是正確的.

  5.19

  void Get_Saddle(int A[m][n])//求矩陣A中的馬鞍點

  {

  for(i=0;i

  {

  for(min=A[i][0],j=0;j

  if(A[i][j]

  for(j=0;j

  if(A[i][j]==min) //判斷這個(些)最小值是否鞍點

  {

  for(flag=1,k=0;k

  if(min

  if(flag)

  printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);

  }

  }//for

  }//Get_Saddle

  5.20

  本題難度極大,故僅探討一下思路.這一題的難點在於,在多項式的元數m未知的情況下,如何按照降冪次序輸出各項.可以考慮采取類似於層序遍歷的思想,從最高次的項開始,依次對其每一元的次數減一,入一個隊列.附設訪問標志visited以避免重復.

  5.21

  void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元組表示的稀疏矩陣加法

  {

  C.mu=A.mu;C.nu=A.nu;C.tu=0;

  pa=1;pb=1;pc=1;

  for(x=1;x<=A.mu;x++) //對矩陣的每一行進行加法

  {

  while(A.data[pa].i

  while(B.data[pb].i

  while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素

  {

  if(A.data[pa].j==B.data[pb].j)

  {

  ce=A.data[pa].e+B.data[pb].e;

  if(ce) //和不為0

  {

  C.data[pc].i=x;

  C.data[pc].j=A.data[pa].j;

  C.data[pc].e=ce;

  pa++;pb++;pc++;

  }

  }//if

  else if(A.data[pa].j>B.data[pb].j)

  {

  C.data[pc].i=x;

  C.data[pc].j=B.data[pb].j;

  C.data[pc].e=B.data[pb].e;

  pb++;pc++;

  }

  else

  {

  C.data[pc].i=x;

  C.data[pc].j=A.data[pa].j;

  C.data[pc].e=A.data[pa].e

  pa++;pc++;

  }

  }//while

  while(A.data[pa]==x) //插入A中剩余的元素(第x行)

  {

  C.data[pc].i=x;

  C.data[pc].j=A.data[pa].j;

  C.data[pc].e=A.data[pa].e

  pa++;pc++;

  }

  while(B.data[pb]==x) //插入B中剩余的元素(第x行)

  {

  C.data[pc].i=x;

  C.data[pc].j=B.data[pb].j;

  C.data[pc].e=B.data[pb].e;

  pb++;pc++;

  }

  }//for

  C.tu=pc;

  }//TSMatrix_Add

  5.22

  void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//將三元組矩陣B加到A上

  {

  for(i=1;i<=A.tu;i++)

  A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以騰出位置

  pa=MAXSIZE-A.tu+1;pb=1;pc=1;

  for(x=1;x<=A.mu;x++) //對矩陣的每一行進行加法

  {

  while(A.data[pa].i

  while(B.data[pb].i

  while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素

  {

  if(A.data[pa].j==B.data[pb].j)

  {

  ne=A.data[pa].e+B.data[pb].e;

  if(ne) //和不為0

  {

  A.data[pc].i=x;

  A.data[pc].j=A.data[pa].j;

  A.data[pc].e=ne;

  pa++;pb++;pc++;

  }

  }//if

  else if(A.data[pa].j>B.data[pb].j)

  {

  A.data[pc].i=x;

  A.data[pc].j=B.data[pb].j;

  A.data[pc].e=B.data[pb].e;

  pb++;pc++;

  }

  else

  {

  A.data[pc].i=x;

  A.data[pc].j=A.data[pa].j;

  A.data[pc].e=A.data[pa].e

  pa++;pc++;

  }

  }//while

  while(A.data[pa]==x) //插入A中剩余的元素(第x行)

  {

  A.data[pc].i=x;

  A.data[pc].j=A.data[pa].j;

  A.data[pc].e=A.data[pa].e

  pa++;pc++;

  }

  while(B.data[pb]==x) //插入B中剩余的元素(第x行)

  {

  A.data[pc].i=x;

  A.data[pc].j=B.data[pb].j;

  A.data[pc].e=B.data[pb].e;

  pb++;pc++;

  }

  }//for

  A.tu=pc;

  for(i=A.tu;i

  }//TSMatrix_Addto

  5.23

  typedef struct{

  int j;

  int e;

  } DSElem;

  typedef struct{

  DSElem data[MAXSIZE];

  int cpot[MAXROW];//這個向量存儲每一行在二元組中的起始位置

  int mu,nu,tu;

  } DSMatrix; //二元組矩陣類型

  Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元組矩陣的元素A[i][j]的值e

  {

  for(s=cpot[i];s

  if(A.data[s].i==i&&A.data[s].j==j) //找到了元素A[i][j]

  {

  e=A.data[s];

  return OK;

  }

  return ERROR;

  }//DSMatrix_Locate

  5.24

  typedef struct{

  int seq; //該元素在以行為主序排列時的序號

  int e;

  } SElem;

  typedef struct{

  SElem data[MAXSIZE];

  int mu,nu,tu;

  } SMatrix; //單下標二元組矩陣類型

  Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求單下標二元組矩陣的元素A[i][j]的值e

  {

  s=i*A.nu+j+1;p=1;

  while(A.data[p].seq

  if(A.data[p].seq==s) //找到了元素A[i][j]

  {

  e=A.data[p].e;

  return OK;

  }

  return ERROR;

  }//SMatrix_Locate

  5.25

  typedef enum{0,1} bool;

  typedef struct{

  int mu,nu;

  int elem[MAXSIZE];

  bool map[mu][nu];

  } BMMatrix; //用位圖表示的矩陣類型

  void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位圖矩陣的加法

  {

  C.mu=A.mu;C.nu=A.nu;

  pa=1;pb=1;pc=1;

  for(i=0;i

  for(j=0;j

  {

  if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//結果不為0

  {

  C.elem[pc]=A.elem[pa]+B.elem[pb];

  C.map[i][j]=1;

  pa++;pb++;pc++;

  }

  else if(A.map[i][j]&&!B.map[i][j])

  {

  C.elem[pc]=A.elem[pa];

  C.map[i][j]=1;

  pa++;pc++;

  }

  else if(!A.map[i][j]&&B.map[i][j])

  {

  C.elem[pc]=B.elem[pb];

  C.map[i][j]=1;

  pb++;pc++;

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