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

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

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

  第九章 查找

  

  int Search_Sq(SSTable STint key)//在有序表上順序查找的算法監視哨設在高下標端

  {

  STelem[STlength+]key=key;

  for(i=;STelem[i]key>key;i++);

  if(i>STlength||STelem[i]key

  return i;

  }//Search_Sq

  分析:本算法查找成功情況下的平均查找長度為ST.length/2,不成功情況下為ST.length.

  9.26

  int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的遞歸算法

  {

  if(low>high) return 0; //查找不到時返回0

  mid=(low+high)/2;

  if(ST.elem[mid].key==key) return mid;

  else if(ST.elem[mid].key>key)

  return Search_Bin_Recursive(ST,key,low,mid-1);

  else return Search_Bin_Recursive(ST,key,mid+1,high);

  }

  }//Search_Bin_Recursive

  9.27

  int Locate_Bin(SSTable ST,int key)//折半查找,返回小於或等於待查元素的最後一個結點號

  {

  int *r;

  r=ST.elem;

  if(key

  else if(key>=r[ST.length].key) return ST.length;

  low=1;high=ST.length;

  while(low<=high)

  {

  mid=(low+high)/2;

  if(key>=r[mid].key&&key

  return mid;

  else if(key

  else low=mid;

  } //本算法不存在查找失敗的情況,不需要return 0;

  }//Locate_Bin

  9.28

  typedef struct {

  int maxkey;

  int firstloc;

  } Index;

  typedef struct {

  int *elem;

  int length;

  Index idx[MAXBLOCK]; //每塊起始位置和最大元素,其中idx[0]不利用,其內容初始化為{0,0}以利於折半查找

  int blknum; //塊的數目

  } IdxSqList; //索引順序表類型

  int Search_IdxSeq(IdxSqList L,int key)//分塊查找,用折半查找法確定記錄所在塊,塊內采用順序查找法

  {

  if(key>L.idx[L.blknum].maxkey) return ERROR; //超過最大元素

  low=1;high=L.blknum;

  found=0;

  while(low<=high&&!found) //折半查找記錄所在塊號mid

  {

  mid=(low+high)/2;

  if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)

  found=1;

  else if(key>L.idx[mid].maxkey)

  low=mid+1;

  else high=mid-1;

  }

  i=L.idx[mid].firstloc; //塊的下界

  j=i+blksize-1; //塊的上界

  temp=L.elem[i-1]; //保存相鄰元素

  L.elem[i-1]=key; //設置監視哨

  for(k=j;L.elem[k]!=key;k--); //順序查找

  L.elem[i-1]=temp; //恢復元素

  if(k

  return k;

  }//Search_IdxSeq

  分析:在塊內進行順序查找時,如果需要設置監視哨,則必須先保存相鄰塊的相鄰元素,以免數據丟失.

  9.29

  typedef struct {

  LNode *h; //h指向最小元素

  LNode *t; //t指向上次查找的結點

  } CSList;

  LNode *Search_CSList(CSList &L,int key)//在有序單循環鏈表存儲結構上的查找算法,假定每次查找都成功

  {

  if(L.t->data==key) return L.t;

  else if(L.t->data>key)

  for(p=L.h,i=1;p->data!=key;p=p->next,i++);

  else

  for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);

  L.t=p; //更新t指針

  return p;

  }//Search_CSList

  分析:由於題目中假定每次查找都是成功的,所以本算法中沒有關於查找失敗的處理.由微積分可得,在等概率情況下,平均查找長度約為n/3.

  9.30

  typedef struct {

  DLNode *pre;

  int data;

  DLNode *next;

  } DLNode;

  typedef struct {

  DLNode *sp;

  int length;

  } DSList; //供查找的雙向循環鏈表類型

  DLNode *Search_DSList(DSList &L,int key)//在有序雙向循環鏈表存儲結構上的查找算法,假定每次查找都成功

  {

  p=L.sp;

  if(p->data>key)

  {

  while(p->data>key) p=p->pre;

  L.sp=p;

  }

  else if(p->data

  {

  while(p->datanext;

  L.sp=p;

  }

  return p;

  }//Search_DSList

  分析:本題的平均查找長度與上一題相同,也是n/3.

  9.31

  int last=0,flag=1;

  int Is_BSTree(Bitree T)//判斷二叉樹T是否二叉排序樹,是則返回1,否則返回0

  {

  if(T->lchild&&flag) Is_BSTree(T->lchild);

  if(T->data

  last=T->data;

  if(T->rchild&&flag) Is_BSTree(T->rchild);

  return flag;

  }//Is_BSTree

  9.32

  int last=0;

  void MaxLT_MinGT(BiTree T,int x)//找到二叉排序樹T中小於x的最大元素和大於x的最小元素

  {

  if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍歷來實現

  if(lastdata>=x) //找到了小於x的最大元素

  printf("a=%d\n",last);

  if(last<=x&&T->data>x) //找到了大於x的最小元素

  printf("b=%d\n",T->data);

  last=T->data;

  if(T->rchild) MaxLT_MinGT(T->rchild,x);

  }//MaxLT_MinGT

  9.33

  void Print_NLT(BiTree T,int x)//從大到小輸出二叉排序樹T中所有不小於x的元素

  {

  if(T->rchild) Print_NLT(T->rchild,x);

  if(T->data

  printf("%d\n",T->data);

  if(T->lchild) Print_NLT(T->lchild,x); //先右後左的中序遍歷

  }//Print_NLT

  9.34

  void Delete_NLT(BiTree &T,int x)//刪除二叉排序樹T中所有不小於x元素結點,並釋放空間

  {

  if(T->rchild) Delete_NLT(T->rchild,x);

  if(T->data

  q=T;

  T=T->lchild;

  free(q); //如果樹根不小於x,則刪除樹根,並以左子樹的根作為新的樹根

  if(T) Delete_NLT(T,x); //繼續在左子樹中執行算法

  }//Delete_NLT

  9.35

  void Print_Between(BiThrTree T,int a,int b)//打印輸出後繼線索二叉排序樹T中所有大於a且小於b的元素

  {

  p=T;

  while(!p->ltag) p=p->lchild; //找到最小元素

  while(p&&p->data

  {

  if(p->data>a) printf("%d\n",p->data); //輸出符合條件的元素

  if(p->rtag) p=p->rtag;

  else

  {

  p=p->rchild;

  while(!p->ltag) p=p->lchild;

  } //轉到中序後繼

  }//while

  }//Print_Between

  9.36

  void BSTree_Insert_Key(BiThrTree &T,int x)//在後繼線索二叉排序樹T中插入元素x

  {

  if(T->data

  {

  if(T->rtag) //T沒有右子樹時,作為右孩子插入

  {

  p=T->rchild;

  q=(BiThrNode*)malloc(sizeof(BiThrNode));

  q->data=x;

  T->rchild=q;T->rtag=0;

  q->rtag=1;q->rchild=p; //修改原線索

  }

  else BSTree_Insert_Key(T->rchild,x);//T有右子樹時,插入右子樹中

  }//if

  else if(T->data>x) //插入到左子樹中

  {

  if(!T->lchild) //T沒有左子樹時,作為左孩子插入

  {

  q=(BiThrNode*)malloc(sizeof(BiThrNode));

  q->data=x;

  T->lchild=q;

  q->rtag=1;q->rchild=T; //修改自身的線索

  }

  else BSTree_Insert_Key(T->lchild,x);//T有左子樹時,插入左子樹中

  }//if

  }//BSTree_Insert_Key

  9.37

  Status BSTree_Delete_key(BiThrTree &T,int x)//<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23551.html

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