|
教学目的： 练习顺序查找、折半查找及二叉排序树的实现
教学重点：
教学难点：
授课内容：
顺序查找
折半查找
顺序查找及折半查找示例 #include <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);
}
|
