大学院受験の第二次世界大戦の日記-第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;
}
データ構造の検索はこの部分のコードの問題が少ないので、あまり深く追究しなくてもいいです.