/*****************************************************************************************/
本人初学时作品有些粗糟，供大家学习交流！其中含有一些方法，如查找问题；关于数组，指针和指针数
组的使用；结构体一些用法，菜单选择方面；字符串函数，树的使用，分配空间等问题可以看看，希望能
对你有用。我想可以学习用最近看有不少初学者关于它们的问题，故就贴出我的初学作品，欢迎指教！
这是程序的一部分，我运行通过，也难免有隐藏的BUG。注意：折半查找要在已经排序的情况下进行。本程
序有删改，由于未排序，折半查找慎用！我觉得可以读读，也许有些问题上对你有用。
/*****************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*全局变量的定义*/
char *st1[8]={"99070101","99070102","99070103","99070104","99070105","99070106","99070107"};
char *st2[8]={"LiJun ","WangYanXia","SunTao ","SHanXiaoHong","ZHangHua","LiXiaoMing","CHenXiaoTing"};
char *st3[8]={"98.5","86","56","96","83","72","98"};/*已有的文件中学生：st1为学号；st2为姓名；st3为分数*/
char *str1[8],*str2[8],*str3[8];/*要输入的学生：*str1为学号；*str2为姓名；str3为分数*/
int nums;/*要输入的学生数*/
/**************************/
/*二叉排序树的数据结构*/
typedef char *KeyType;
typedef struct{
KeyType key;
}DataType;
typedef struct BinSTreeNode{
DataType elemt;
struct BinSTreeNode *lchild,*rchild;
}*BinSTree;
/**********************/
void studentinfo()/*已知的学生信息打印输出*/
{
int j;
printf("\nThe info is:\n");
printf("\t number \t name \t score\n");
for(j=0;j<7;j++)
printf("\t%s\t%s\t%s\n",st1[j],st2[j],st3[j]);
}
int menuselect()/*菜单的选择，确定是输入学生方式还是导入文件*/
{
int num,count,i;
char ch[9];
do{
printf("1.input your student number,name,score;\n");/*输入方式选择*/
printf("2.open file,open info!\n");/*导入文件方式选择*/
printf("0.exit system;\n");/*退出系统*/
printf("Please choose your select number:\n");/*选择方式*/
scanf("%d",&num);
switch(num)
{ case 1:/*方式一获得输入信息的程序段并将信息储存在指针数组里*/
printf("how many student your input?\n");
scanf("%d",&nums);
for(i=0;i<nums;i++)
{
str1[i]=(char *)malloc(sizeof(char)*9);
str2[i]=(char *)malloc(sizeof(char)*12);
str3[i]=(char *)malloc(sizeof(char)*5);
count=i+1;
system("cls");
printf(">>1.input your student %d number;\n",count);
scanf("%s",str1[i]);
printf(">>2.input your student %d name;\n",count);
scanf("%s",str2[i]);
printf(">>3.input your student %d score;\n",count);
scanf("%s",str3[i]);
}
printf("input over!\n");
printf("your input is:\n");
printf("\t number \t name \t score\n");/*输出你所输入的*/
for(i=0;i<nums;i++)
printf("\t %s \t %s \t %s\n",str1[i],str2[i],str3[i]);
return(num);
case 2:/*打开已有的文件*/
system("cls");
studentinfo();
return(num);
case 0: exit(0);/*退出系统*/
}
}while(num!=0||num!=1||num!=2);
}
int SeqSearch(char **p,char *k,int flag)/*顺序查找，**p为要查找的储存信息的数组，*k为要查找的学号，flag确定是输入方式还是已有文件的导入*/
{
int i;
if(flag==1) p=str1;
else p=st1;
for(i=0;i<7;i++)
if(!strcmp(*(p+i),k))
return (i);
return(-1);
}
int BinSearch(char **p,char *k,int flag)/*折半查找*/
{
int low,mid,high;
low=0;
if(flag==1)
{
p=str1;
high=nums-1;
}
else
{
p=st1;
high=strlen(*p)-1;
}
while(low<=high)
{
mid=(low+high)/2;
if(strcmp(*(p+mid),k)==0) return(mid);
else if(strcmp(*(p+mid),k)>0) high=mid-1;
else low=mid+1;
}
return(-1);
}
BinSTree BSTreeSearch(BinSTree t,KeyType k,BinSTree *p)/*在根指针为t的二差排序树中查找元素关键字为k的结点*/
{
BinSTree q,bt;
q=t;
bt=t;
while(bt)
{
if(strcmp(bt->elemt.key,k)==0)/*查找成功*/
{
*p=bt;
return(bt);
}
q=bt;
if(strcmp(bt->elemt.key,k)>0)/*在左子树中查找*/
{
bt=bt->lchild;
}
else/*在右子树中查找*/
{
bt=bt->rchild;
}
}
*p=q;
return(bt);
}
void BSTreeInsert(BinSTree bt,KeyType k)/*在二差排序树插入关键字为k的结点，bt根结点指针*/
{
BinSTree p,q,r;
q=bt;
if(BSTreeSearch(q,k,&p)==NULL)/*如果查找不成功*/
{
r=(BinSTree)malloc(sizeof(struct BinSTreeNode));
r->elemt.key=k;
r->lchild=r->rchild=NULL;
if(bt==NULL)/*若二叉排序树为空，被插结点作为根结点*/
bt=r;
if(strcmp(p->elemt.key,k)>0)/*被插结点插入p的左子树*/
p->lchild=r;
else/*被插结点插入p的右子树*/
p->rchild=r;
}
}
int UBSTreeSearch(char **p,char *k,int flag)/*用二叉排序树查找数组中的元素，并返回下标*/
{
BinSTree bt,q,s;
int length,i;
if(flag==1)
{
p=str1;
length=nums;
}
else
{
p=st1;
length=strlen(*p);
}
bt=(BinSTree)malloc(sizeof(struct BinSTreeNode));
bt->elemt.key=*p;/*数组第一个元素根结点*/
if(strcmp(bt->elemt.key,k)==0)/*如果查找元素为根结点，直接返回*/
return(0);
for(i=1;i<length;i++)
{
BSTreeInsert(bt,*(p+i));/*建树*/
s=BSTreeSearch(bt,k,&q);/*查找树*/
if(s)
return(i);
}
return(-1);
}
int main()
{
int num,num1,k;
char ch[9];
num=menuselect();
if(num==1)/*输入的情况查找*/
{
do{
printf("input your search number:\n");
scanf("%s",ch);
printf("1.SeqSearch;\n");
printf("2.BinSearch;\n");
printf("3.BinSTreeSearch;\n");
printf("0.cancle;\n");
printf("choose your selsect number:\n");
scanf("%d",&num1);
switch(num1)/*选择查找方式*/
{
case 0:exit(0);
case 1:
k=SeqSearch(str1,ch,1);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t%s\t%s\t%s\n",str1[k],str2[k],str3[k]);
}
else
printf("NOT FIND!\n");
break;
case 2:
k=BinSearch(str1,ch,1);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t %s \t %s \t %s\n",str1[k],str2[k],str3[k]);
}
else
printf("NOT FIND!\n");
break;
case 3:
k=BSTreeSearch(str1,ch,1);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t %s \t %s \t %s\n",str1[k],str2[k],str3[k]);
}
else
printf("NOT FIND!\n");
break;
}
}while(num1!=0||num1!=1||num1!=2||num1!=3);
}
if(num==2)/*导入信息的情况*/
{
do{
printf("input your search number:\n");
scanf("%s",ch);
printf("1.SeqSearch;\n");
printf("2.BinSearch;\n");
printf("3.BinSTreeSearch;\n");
printf("0.cancle;\n");
printf("choose your selsect number:\n");
scanf("%d",&num1);
switch(num1)/*选择查找方式*/
{
case 0:exit(0);
case 1:
k=SeqSearch(st1,ch,2);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t%s\t%s\t%s\n",st1[k],st2[k],st3[k]);
}
else
printf("NOT FIND!\n");
break;
case 2:
k=BinSearch(st1,ch,2);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t%s\t%s\t%s\n",st1[k],st2[k],st3[k]);
}
else
printf("NOT FIND!\n");
break;
case 3:
k=BSTreeSearch(str1,ch,2);
if(k+1)
{
printf("\t number \t name \t score\n");
printf("\t%s\t%s\t%s\n",st1[k],st2[k],st3[k]);
}
else
printf("NOT FIND!\n");
break;
}
}while(num1!=0||num1!=1||num1!=2||num1!=3);
}
return 0;
}
[此贴子已经被作者于2007-8-26 20:19:25编辑过]
原创慎用啊
