typedef struct Lnode//二叉排序树的创建，采用二叉链表 {
struct Lnode *lchild,*rchild; char data[5]; }node;
int BSTsearch(node *h, char c[5]) {
if (h==NULL) {
return 0;
}//查找失败，返回0 else {
if(strcmp(c,h->data)==0) {
c=h->data; return 1; }
else if(strcmp(c , h->data)<0) {
return BSTsearch(h->lchild,c); } else {
return BSTsearch(h->rchild,c); } } }
void Insert(node *&h,char c[5]) {
if(h==NULL) {
node *s=(node *)malloc(sizeof(node));
strcpy(s->data,c);
s->lchild=s->rchild=NULL; h=s;
}
else if(strcmp(c,h->data)<0) {
Insert(h->lchild,c); }
else {
Insert(h->rchild,c); } }
void create(node *&h) {
int n;
printf(\输入关键字个数：\\n\ scanf(\ for(int i=0;i { printf(\输入节点的值：\\n\ scanf(\ Insert(h,y[i].y); } } void Print(node *h) { int k=0; if(h!=NULL) { Print(h->lchild); printf(\ Print(h->rchild); } } void main() { node *h=NULL; struct month m; create(h); printf(\输入查找的元素：\\n\ scanf(\ int k=BSTsearch(h,m.y); if(k) printf(\查找成功！有此元素！\\n\ else printf(\没有此元素！\\n\ printf(\输出二叉排序树元素:\\n\ Print(h); printf(\ } 实验十四 插入排序算法的实现 实验预备知识： 1．理解并掌握直接插入排序、折半插入排序、2-路插入排序的基本概念和方法。 2．掌握排序算法的基本思想。 一、实验目的 1．掌握排序算法基本思想的实现。 2．通过实验掌握直接插入排序、折半插入排序、2-路插入排序的具体实现。 二、实验环境 ⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C； 三、实验要求 1．对随机若干个数据进行直接插入排序、折半插入排序、2-路插入排序。 2．掌握这3种基本排序的算法思想和实现过程。 四、实验内容 1．在自己的U盘的“姓名+学号”文件夹中创建“实验14”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。 2．设计随机数来测试排序算法运行时间的程序，其中可以通过修改RANDNUM的值来更改测试的数据量。具体参考如下： #define RANDNUM 10000 //随机数的个数 for(i=0;i iRandNum[i]=rand()%RANDNUM; } 3．对随机数据进行进行直接插入排序、折半插入排序、2-路插入排序。 4．排序算法进行测试，记录运行时间；把需排序的数改为20000，进行同样测试，并比较测试结果。 #include typedef int InfoType; /* 定义其它数据项的类型 */ #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) #define MAXSIZE 10000 /* 一个用作示例的小顺序表的最大长度 */ #define RANDNUM 10000 /*随机数的个数*/ typedef int KeyType; /* 定义关键字类型为整型 */ struct timeb t1,t2; typedef struct { KeyType key; /* 关键字项 */ InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */ }RedType; /* 记录类型 */ typedef struct { RedType r[MAXSIZE+1]; /* r[0]闲置或用作哨兵单元 */ int length; /* 顺序表长度 */ }SqList; /* 顺序表类型 */ void print(SqList L) { int i; for(i=1;i<=L.length;i++) printf(\ printf(\ } /* bo10-1.c 顺序表插入排序的函数(3个) */ void InsertSort(SqList *L) { /* 对顺序表L作直接插入排序。算法10.1 */ ftime(&t1); int i,j,t; for(i=2;i<=(*L).length;++i) if LT((*L).r[i].key,(*L).r[i-1].key) /* \需将L.r[i]插入有序子表 */ { (*L).r[0]=(*L).r[i]; /* 复制为哨兵 */ for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j) (*L).r[j+1]=(*L).r[j]; /* 记录后移 */ (*L).r[j+1]=(*L).r[0]; /* 插入到正确位置 */ } ftime(&t2); t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); printf(\直接插入排序用时%d毫秒\\n\ } void BInsertSort(SqList *L) { /* 对顺序表L作折半插入排序。算法10.2 */ ftime(&t1); int i,j,m,low,high,t; for(i=2;i<=(*L).length;++i) { (*L).r[0]=(*L).r[i]; /* 将L.r[i]暂存到L.r[0] */ low=1; high=i-1; while(low<=high) { /* 在r[low..high]中折半查找有序插入的位置 */ m=(low+high)/2; /* 折半 */ if LT((*L).r[0].key,(*L).r[m].key) high=m-1; /* 插入点在低半区 */ else low=m+1; /* 插入点在高半区 */ } for(j=i-1;j>=high+1;--j) (*L).r[j+1]=(*L).r[j]; /* 记录后移 */ (*L).r[high+1]=(*L).r[0]; /* 插入 */ } ftime(&t2); t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); printf(\折半插入排序用时%d毫秒\\n\ }