数据结构课程设计,综合查找算法
发布网友
发布时间：2022-05-02 07:01
共4个回答
热心网友
时间：2023-10-10 13:12
typedef int KeyType;
typedef struct{
KeyType key;
int maths;
int english;
}ElemType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct {
ElemType *elem;
int length;
}SSTable;
int Search_Seq(SSTable ST,KeyType key)
{
int i;
ST.elem[0].key=key;
for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
return i;
}
int Search_Bin(SSTable ST,KeyType key)
{
int low,mid,high;
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1;
}
}
getdata(SSTable * t)
{
FILE *fp;
int i=1;
fp=fopen("stu.txt","r");
fscanf(fp,"%d",&(t->length));
while(i<=t->length)
{
fscanf(fp,"%d %d %d",&(t->elem[i].key),
&(t->elem[i].maths),&(t->elem[i].english) );
i++;
}
fclose(fp);
}
main()
{
ElemType stu[50];
SSTable class;
int i,j,k;
long time;
class.elem=stu;
getdata(&class);
printf("This class has %d students.\n",class.length);
printf("Input stuno you want search:\n");
scanf("%d",&k);
i=Search_Seq(class,k);
j=Search_Bin(class,k);
printf("Maths English\n");
printf("%d %d\n",class.elem[i].maths,class.elem[i].english);
printf("%d %d\n",class.elem[j].maths,class.elem[j].english);
for(i=1;i<=4;i++)
{j=stu[i].maths+stu[i].english;
printf("%d\n",j);
}
}
二叉排序树
示例
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}
热心网友
时间：2023-10-10 13:13
<stdio.h>
typedef
int
KeyType;
typedef
struct{
KeyType
key;
int
maths;
int
english;
}ElemType;
#define
EQ(a,b)
((a)==(b))
#define
LT(a,b)
((a)<
(b))
#define
LQ(a,b)
((a)<=(b))
typedef
struct
{
ElemType
*elem;
int
length;
}SSTable;
int
Search_Seq(SSTable
ST,KeyType
key)
{
int
i;
ST.elem[0].key=key;
for(i=ST.length;
!EQ(ST.elem[i].key,key);
--i);
return
i;
}
int
Search_Bin(SSTable
ST,KeyType
key)
{
int
low,mid,high;
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if
EQ(key,ST.elem[mid].key)
return
mid;
else
if
LT(key,ST.elem[mid].key)
high=mid
-1;
else
low=mid
+1;
}
}
getdata(SSTable
*
t)
{
FILE
*fp;
int
i=1;
fp=fopen("stu.txt","r");
fscanf(fp,"%d",&(t->length));
while(i<=t->length)
{
fscanf(fp,"%d
%d
%d",&(t->elem[i].key),
&(t->elem[i].maths),&(t->elem[i].english)
);
i++;
}
fclose(fp);
}
main()
{
ElemType
stu[50];
SSTable
class;
int
i,j,k;
long
time;
class.elem=stu;
getdata(&class);
printf("This
class
has
%d
students.\n",class.length);
printf("Input
stuno
you
want
search:\n");
scanf("%d",&k);
i=Search_Seq(class,k);
j=Search_Bin(class,k);
printf("Maths
English\n");
printf("%d
%d\n",class.elem[i].maths,class.elem[i].english);
printf("%d
%d\n",class.elem[j].maths,class.elem[j].english);
for(i=1;i<=4;i++)
{j=stu[i].maths+stu[i].english;
printf("%d\n",j);
}
}
二叉排序树
示例
#include
<alloc.h>
#define
ERROR
0;
#define
FALSE
0;
#define
TRUE
1;
#define
OK
1;
typedef
int
ElemType;
typedef
int
Status;
typedef
int
KeyType;
#define
EQ(a,b)
((a)==(b))
#define
LT(a,b)
((a)<
(b))
#define
LQ(a,b)
((a)<=(b))
typedef
struct
BinaryTree
{
ElemType
data;
struct
BinaryTree
*l;
struct
BinaryTree
*r;
}*BiTree,BiNode;
BiNode
*
new()
{
return(
(BiNode
*)malloc(sizeof(BiNode))
);
}
CreateSubTree(BiTree
*T,ElemType
*all,int
i)
{
if
((all[i]==0)||i>16)
{
*T=NULL;
return
OK;
}
*T=new();
if(*T==NULL)
return
ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree
*T)
{
ElemType
all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType
d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree
T,int
(*Visit)(ElemType
d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit))
return
OK;
return
ERROR;
}
else
return
OK;
}
InOrderTraverse(BiTree
T,int
(*Visit)(ElemType
d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit))
return
OK;
return
ERROR;
}else
return
OK;
}
Status
SearchBST(BiTree
T,KeyType
key,BiTree
f,BiTree
*p){
if(!T)
{*p=f;return
FALSE;}
else
if
EQ(key,T->data){
*p=T;return
TRUE;}
else
if
LT(key,T->data)
SearchBST(T->l,key,T,p);
else
SearchBST(T->r,key,T,p);
}
Status
InsertBST(BiTree
*T,ElemType
e){
BiTree
p;
BiTree
s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p)
*T=s;
else
if
(LT(e,p->data))
p->l=s;
else
p->r=s;
return
TRUE;
}
else
return
FALSE;
}
void
Delete(BiTree
*p){
BiTree
q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else
if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else
{
/*
q=(*p);
s=(*p)->l;
while(s->r)
{q=s;
s=s->r;}
(*p)->data=s->data;
if(q!=(*p)
)
q->r=s->l;
else
q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r)
s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status
DeleteBST(BiTree
*T,KeyType
key){
if
(!(*T)
)
{return
FALSE;}
else{
if
(
EQ(key,(*T)->data))
Delete(T);
else
if
(
LT(key,(*T)->data))
DeleteBST(
&((*T)->l),
key);
else
DeleteBST(
&((*T)->r),key);
return
TRUE;
}
}
main()
{
BiTree
root;
BiTree
sroot=NULL;
int
i;
int
a[10]={45,23,12,3,33,
27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now
sroot
has
nodes:\n");
InOrderTraverse(sroot,printelem);
}
热心网友
时间：2023-10-10 13:13
我写的有现成的 满足你二叉树构建、查找、插入、删除要求的程序 如果需要可以留下邮箱，但是仅仅是简陋的算法而已，刚刚能跑。
热心网友
时间：2023-10-10 13:14
