C语言编写数据结构查找算法

实验五 查找的实现
一、 实验目的
1．通过实验掌握查找的基本概念；
2．掌握顺序查找算法与实现；
3．掌握折半查找算法与实现。
二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 保存程序的运行结果，并结合程序进行分析。
三、 实验内容
1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。
2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。
一、顺序查找
顺序查找代码：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("请输入您要输入的数据的个数:\n");
scanf("%d",&(s->length));
printf("请输入您想输入的%d个数据;\n\n",s->length);
for(i=0;ilength;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所输入的数据为:\n\n");
for(i=0;ilength;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{

i++;
}
if(i==s->length)
{
printf("该表中没有您要查找的数据！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("请输入您想要查找的数据的关键字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);
return2;
}
顺序查找的运行结果：
二、折半查找
折半查找代码：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("请输入您要输入的数据的个数:\n");
scanf("%d",&(s->length));
printf("请由大到小输入%d个您想输入的个数据;\n\n",s->length);
for(i=0;ilength;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所输入的数据为:\n\n");
for(i=0;ilength;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("该表中没有您要查找的数据!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("请输入您想要查找的数据的关键字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);
return2;
}
折半查找运行结果：
三、实验总结：
该实验使用了两种查找数据的方法（顺序查找和折半查找），这两种方法的不同之处在于查找方式和过程不同，线性表的创建完全相同，程序较短，结果也一目了然。

1、顺序查找
2、二分查找
3、分块查找

#include
#include
#include
typedef struct tree_node
{
int data;
struct tree_node *lchild;
struct tree_node *rchild;
}tree,*tlink;
int tree_init(struct tree_node **root);
void tree_construct(struct tree_node *root,int value);
tlink delet_tree_root(tree *root);
tlink delet_tree_value(struct tree_node *root,int value);
int tree_search(int value,tree *root);
int tree_height(struct tree_node *root);
void print_tree_node(struct tree_node *root);

int tree_init(struct tree_node **root)
{
if(((*root)=(struct tree_node *)malloc(sizeof(struct tree_node))) == NULL)
return -1;

(*root)->lchild = (*root)->rchild = NULL;
(*root)->data = 0;
return 0;
}

void tree_construct(struct tree_node *root,int value);
tlink delet_tree_root(tree *root);

{
p->data = value;
break;

}

if(value <= (p->data))
{
if(!(p->lchild))
{
tree_init(&(p->lchild));
p->lchild->data = value;
break;
}
else
{
p = p->lchild;
continue;
}
}
if(value >= (p->data))
{
if(!(p->rchild))
{
tree_init(&(p->rchild));
p->rchild->data = value;
break;
}
else
{
p = p->rchild;
continue;
}
}

}
return ;
}
tlink delet_tree_root(tree *root)
{
tlink tmp = root;
tlink p = root->rchild;
if(root->rchild == NULL)
{
root = root->lchild;
return root;
}
if(root->lchild == NULL)
{
root = root->rchild;
return root;
}
while(p->lchild != NULL)
p = p->lchild;
p->lchild = root->lchild;
root = root->rchild;
free(tmp);
return root;
}
tlink delet_tree_value(struct tree_node *root,int value)
{

struct tree_node *p = root;
struct tree_node *tmp;

if(root->data == value)
{
tmp = delet_tree_root(root);
return tmp;
}

while(p)
{

if((p->lchild!=NULL && (p->lchild->data)==value) || (p->rchild != NULL&&(p->rchild->data)==value))
break;
if(p->data > value)
{
p = p->lchild;
continue;
}
if(p->data < value)
{
p = p->rchild;
continue;
}

}
if(p == NULL)
{
printf("NO data record!\n");
return NULL;
}

if((p->lchild != NULL) && (p->lchild->data == value))
{
tmp = delet_tree_root(p->lchild);
p->lchild = tmp;
return root;
}
if((p->rchild != NULL) && (p->rchild->data == value))
{

tmp = delet_tree_root(p->rchild);
p->rchild = tmp;

return root;

}
}

int tree_search(int value,tree *root)
{
tlink p = root;
while(p != NULL)
{
if(p->data == value)
return 1;
if(value > (p->data))
p = p->rchild;
else
p = p->lchild;
}
if(p == NULL)
return 0;
}

int tree_height(struct tree_node *root)
{
struct tree_node *p1 = root;
struct tree_node *p2 = root;
int i=0,j=0;
if(p1->data == 0) return 1;

while(p1)
{
i++;
p1 = p1->lchild;
}

while(p2)
{
j ++;
p2 = p2->rchild;
}
return (i>j?(i):(j));
}

void print_tree_node(struct tree_node *root)
{
struct tree_node *p = root;

if(p == NULL)
return ;
print_tree_node(p->lchild);
printf("%d\t",p->data);
print_tree_node(p->rchild);

return;
}

int main(void)
{
int k,i,value;
struct tree_node *root;
struct tree_node *tmp;
if(tree_init(&root)<0)
{
printf("Iinit error!\n");
}
printf("Please input the number of the data:\n");
scanf("%d",&k);
int a[k];
printf("PLease put the data:\n");
for(i=0;i {
scanf("%d",&value);
a[i] = value;
}
for(i=0;i tree_construct(root,a[i]);
while(getchar() != '\n');
print_tree_node(root);
printf("\n");
printf("The tree height is:%d\n",tree_height(root));

while(root != NULL)
{
printf("input the data you want to delet:\n");
scanf("%d",&value);
if(tree_search(value,root) == 0)
{
printf("The data is not exist!\n");
continue;
}
else
{
root = delet_tree_value(root,value);
print_tree_node(root);
printf("\n");
while(getchar()!='\n');
}
}
printf("There is no data exist!\nByebye!\n");

return 0;

}

这是我自己辛辛苦苦写的，想了一天再把树的删除搞定。已经验证过。