大学院受験の第二次世界大戦の日記-第11日——データ構造:検索

2219 ワード

今日はよくある検索アルゴリズムをまとめます.
逐次検索テーブル
/*
    a , key      ,          
*/
int seqSearch(int a[],int n,int key)
{
  for(int i=0;i
半値検索表
/*
    a , key      ,       
*/
int binSearch(int a[],int n,int key)
{
  int low=0;
  int high=n-1;
  int mid;
  while(low<=high)
  {
    mid=(low+high)/2;
    if(a[mid]==key)
      return mid;
    else if(a[mid]
ツリーを並べ替える
typedef int DataType;
typedef struct BiTNode
{
  DataType data;
  struct BiTNode *left,*right;
}BiTNode;
挿入操作
void biTInsert(BiTNode **root,DataType data)
{
  if(*root==NULL)
  {
    BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
    p->data=data;
    p->left=p->right=NULL;
    *root=p;
  }
  else if((*root)->dataright),data);
  else
    biTInsert(&((*root)->left),data);
}
操作を削除
void biTDelete(BiTNode **root,DataType data)
 2 {
 3   if(*root==NULL)
 4     return;
 5   else if((*root)->data==data)
 6   {
 7     BiTNode *p=*root;
 8     if((*root)->left==NULL)
 9       *root=(*root)->right;
10     else if((*root)->right==NULL)
11       *root=(*root)->left;
12     else
13     {
14       BiTNode *q=p->left;
15       while(q->right)
16       {
17         p=q;
18         q=q->right;
19         (*root)->data=q->data;
20         if(*root==p)
21           p->left=q->left;
22         else
23           p->right=q->left;
24         p=q;
25       }
26       free(p);
27     }
28     else if((*root)->dataright),data);
30     else
31       biTInsert(&((*root)->left),data);
32   }
33 }
巡回操作
BiTNode *biTTraverse(BiTNode *root,void(*visitFunc)(DataType data))
{
  biTTraverse(root->left);
  visitFunc(root->data);
  biTTraverse(root->right);
}
作成操作
BiTNode *biTCreate()
{
  BiTNode *root;
  int data;
  do
  {
    printf("        :");
    scanf("%d",&data);
    biTInsert(&root,data);
  }while(data != -1);
  return root;
}
データ構造の検索はこの部分のコードの問題が少ないので、あまり深く追究しなくてもいいです.