查找算法锦集(课程设计)
发布网友
发布时间：2022-04-24 08:53
共4个回答
热心网友
时间：2022-05-03 03:48
题目：对记录序列：{55，13，23，72，109，67，2，78,13}分别使用顺序查找和折半查找算法实现特定关键字值记录的查找。然后建立该记录序列的二叉排序树，并在其上实现特定关键字值结点的查找和删除。-
#include <stdio.h>
#include <stdlib.h>
#define LIST_SIZE 20
#define ENDKEY 0
typedef int KeyType;
typedef struct
{
KeyType key;
}RecordType;
typedef struct
{
RecordType r[LIST_SIZE+1]; /* r[0]为工作单元 */
int length;
}RecordList;
typedef struct node
{
KeyType key ; /*关键字的值*/
struct node *lchild,*rchild;/*左右指针*/
}BSTNode, *BSTree;
int SeqSearch(RecordList l, KeyType k)
/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/
{
int i;
l.r[0].key=k;
i=l.length;
while (l.r[i].key!=k) i--;
return(i);
}
int BinSrch(RecordList l, KeyType k)
/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/
{
int low,high,mid;
low=1;
high=l.length;/*置区间初值*/
while( low <= high)
{
mid=(low+high) / 2;
if (k==l.r[mid]. key)
return (mid);/*找到待查元素*/
else
if (k<l.r[mid]. key)
high=mid-1;/*未找到，则继续在前半区间进行查找*/
else
low=mid+1;/*继续在后半区间进行查找*/
}
return (0);
}
void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/
{
BSTree s;
if (*bst == NULL)/*递归结束条件*/
{
s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
s-> key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
}
void CreateBST(BSTree *bst)
/*从键盘输入元素的值，创建相应的二叉排序树*/
{
KeyType key;
*bst=NULL;
printf("请建立记录序列的二叉排序树:\n");
scanf("%d", &key);
while (key!=ENDKEY) /*ENDKEY为自定义常量*/
{
InsertBST(bst, key);
scanf("%d", &key);
}
}
int SearchBST(BSTree bst, KeyType key)
/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针*/
{
if (!bst)
return NULL;
else
if (bst->key == key)
return 1;/*查找成功*/
else
if (bst->key > key)
return SearchBST(bst->lchild, key);/*在左子树继续查找*/
else
return SearchBST(bst->rchild, key);/*在右子树继续查找*/
}
BSTNode * DelBST(BSTree t, KeyType k) /*在二叉排序树t中删去关键字为k的结点*/
{
BSTNode *p, *f,*s ,*q;
p=t;
f=NULL;
while(p) /*查找关键字为k的待删结点p*/
{
if(p->key==k ) break; /*找到则跳出循环*/
f=p; /*f指向p结点的双亲结点*/
if(p->key>k)
p=p->lchild;
else
p=p->rchild;
}
if(p==NULL) return t; /*若找不到，返回原来的二叉排序树*/
if(p->lchild==NULL) /*p无左子树*/
{
if(f==NULL)
t=p->rchild; /*p是原二叉排序树的根*/
else
if(f->lchild==p) /*p是f的左孩子*/
f->lchild=p->rchild ; /*将p的右子树链到f的左链上*/
else /*p是f的右孩子*/
f->rchild=p->rchild ; /*将p的右子树链到f的右链上*/
free(p); /*释放被删除的结点p*/
}
else /*p有左子树*/
{
q=p;
s=p->lchild;
while(s->rchild) /*在p的左子树中查找最右下结点*/
{
q=s;
s=s->rchild;
}
if(q==p)
q->lchild=s->lchild ; /*将s的左子树链到q上*/
else
q->rchild=s->lchild;
p->key=s->key; /*将s的值赋给p*/
free(s);
}
return t;
} /*DelBST*/
void Visit(int ch)
{
printf("%d ",ch);
}
void InOrder(BSTree root)
{
if (root!=NULL)
{
InOrder(root ->lchild);
Visit(root ->key);
InOrder(root ->rchild);
}
}
void InitRecord(RecordList *l)
{
l->length=0;
}
int CreatRecord(RecordList *L)
{
int i;
for(i=0;i<9;i++)
{
printf("输入%d号记录:",i+1);
scanf("%d",&L->r[i+1].key);
L->length++;
}
printf("输入完毕!\n");
return(1);
}
void main()
{ int result,a,k;
RecordList l;
BSTree bst;
InitRecord(&l);
CreatRecord(&l);
printf("请输入要查找的记录:");
scanf("%d",&k);
printf("顺序查找结果为:\n");
result=SeqSearch(l,k);
if(result!=0)
printf("该关键字在表中位置为%d\n",result);
else
printf("查找失败!\n");
printf("折半查找结果为:\n");
result=BinSrch(l,k);
if(result!=0)
printf("该关键字在表中位置为%d\n",result);
else
printf("查找失败!\n");
CreateBST(&bst);
printf("请输入要查找的记录:");
scanf("%d",&k);
a=SearchBST(bst,k);
printf("利用二叉排序树查找结果为:\n");
if(a==1)
printf("查找成功!\n");
else
printf("查找失败!\n");
printf("请输入要删除的记录:");
scanf("%d",&k);
DelBST(bst,k);
printf("遍历删除记录后的二叉排序树:\n");
InOrder(bst);
printf("\n");
}
热心网友
时间：2022-05-03 05:06
热心网友
时间：2022-05-03 06:41
热心网友
时间：2022-05-03 08:32
