实验内容：
基本内容：
算法1：采用顺序存储结构创建静态查找表，对查找表进行顺序查找和改进的顺序查找，并对其查找效率进行比较；
算法2：采用顺序存储结构创建静态查找表——有序表，对有序表进行二分查找；
选作内容：
编程实现按二叉排序树算法进行查找。
静态查找表算法（未改进）：
代码：
/
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; int info; }ElemType; typedef struct { ElemType elem[MAXSIZE]; int length; }Sstable; int Search_Seq(Sstable ST,keytype key) { int i=1; while(i<=ST.length) { if(key==ST.elem[i].key) { return i; } i++; } } void Create(Sstable &ST,int n) { int i; printf("输入元素："); for(i=1;i<=n;i++) scanf("%d",&ST.elem[i].key); } int main() { Sstable ST; keytype key; int i; printf("输入长度："); scanf("%d",&ST.length); Create(ST,ST.length); while(1) { printf("输入要查找的元素："); scanf("%d",&key); i=Search_Seq(ST,key); if(i) printf("元素位置在：%d\n",i); else printf("元素不存在\n"); } }
运行结果：
静态查找表算法（改进）：
代码：
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; int info; }ElemType; typedef struct { ElemType elem[MAXSIZE]; int length; }Sstable; int Search_Seq(Sstable ST,keytype key) { int i=ST.length; ST.elem[0].key=key; while(i>=0) { if(key==ST.elem[i].key) { return i; } i--; } } void Create(Sstable &ST,int n) { int i; printf("输入元素："); for(i=1;i<=n;i++) scanf("%d",&ST.elem[i].key); } int main() { Sstable ST; keytype key; int i; printf("输入长度："); scanf("%d",&ST.length); Create(ST,ST.length); while(1) { printf("输入要查找的元素："); scanf("%d",&key); i=Search_Seq(ST,key); if(i) printf("元素位置在%d\n",i); else printf("元素不存在\n"); } }
运行结果：
折半查找：
代码：
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; int info; }ElemType; typedef struct { ElemType elem[MAXSIZE]; int length; }Sstable; int Search_Bin(Sstable ST,keytype key) { int low,high,mid; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) high=mid-1; else low=mid+1; } return 0; } void Create(Sstable &ST,int n) { int i; printf("输入元素："); for(i=1;i<=n;i++) scanf("%d",&ST.elem[i].key); } int main() { Sstable ST; keytype key; int i; printf("输入长度："); scanf("%d",&ST.length); Create(ST,ST.length); while(1) { printf("输入要查找的元素："); scanf("%d",&key); i=Search_Bin(ST,key); if(i) printf("元素位置在：%d\n",i); else printf("元素不存在\n"); } }
运行结果：
选做（二叉排序树查找）：
#include<stdio.h> #include<stdlib.h> #define OVERFLOW -2 #define OK 1 #define TRUE 1 #define ERROR 0 #define FALSE 0 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) typedef int Status; typedef struct Volunteer { int key; char name[15]; char phoneNo[11]; }ElemType; typedef struct BiNode{ ElemType data; struct BiNode *lchild,*rchild; }BiNode, *BiTree; Status SearchBST(BiTree T,int key,BiTree f,BiTree &p) { if(!T) { p=f; return FALSE; } else if(EQ(key,T->data.key)) { p=T; return TRUE; } else if LT(key,T->data.key) { return SearchBST(T->lchild,key,T,p); } else return SearchBST(T->rchild,key,T,p); } Status InsertBST(BiTree &T,ElemType e) { BiTree s,p; if(!SearchBST(T,e.key,NULL,p)) { if(!(s=(BiTree)malloc(sizeof(BiNode)))) exit(OVERFLOW); s->data=e; s->lchild=s->rchild=NULL; if(!p) { T=s; } else if LT(e.key,p->data.key) { p->lchild=s; } else { p->rchild=s; } return TRUE; } else return FALSE; } Status Delete(BiTree &p) { BiTree q,s; if(!p->rchild) { q=p; p=p->lchild; free(q); } else if(!p->lchild) { q=p; p=p->rchild; free(q); } else { q=p; s=p->lchild; while(s->rchild) { q=s; s=s->rchild; } p->data=s->data; if(q!=p) { q->rchild=s->lchild; } else { q->lchild=s->lchild; } free(s); return TRUE; } } Status DeleteBST(BiTree &T,int key) { if(!T) { return ERROR; } else { if(EQ(key,T->data.key)) { Delete(T); } else if(LT(key,T->data.key)) { return DeleteBST(T->lchild,key); } else { return DeleteBST(T->rchild,key); } } } void InOrderTraverse(BiTree T) { if(T) { InOrderTraverse(T->lchild); printf("%d\t%s\t%s\n",T->data.key,T->data.name,T->data.phoneNo); InOrderTraverse(T->rchild); } } void showmenu() { printf("******欢迎进入志愿者信息管理系统******\n"); printf("* 1:我要报名 *\n"); printf("* 2:我要取消报名 *\n"); printf("* 3:我想知道关心的同伴是否也报名了 *\n"); printf("* 4:看看全部的报名信息 *\n"); printf("* 5:退出系统 *\n"); printf("* 请选择你所要执行的操作（1-5） *\n"); printf("**************************************\n"); } int main() { BiTree T=NULL,p=NULL; ElemType e; int no,flag,st; while(1) { showmenu(); scanf("%d",&flag); switch(flag) { case 1:printf("请输入你的学号，姓名和联系方式，用空格隔开！\n"); printf("\n"); scanf("%d%s%s",&e.key,e.name,e.phoneNo); InsertBST(T,e); printf("\n"); printf("报名成功，你是一个有爱心的同学，为你点赞！\n"); printf("\n"); break; case 2:if(!T) { printf("请先报名，再操作！\n"); break; } printf("请输入你的学号： "); scanf("%d",&no); DeleteBST(T,no); printf("\n"); printf("你的报名信息已删除，不过欢迎你随时加入我们志愿者团队哦！\n"); printf("\n"); break; case 3:if(!T) { printf("二叉排序树还未建立，请先建立后再操作！\n"); break; } printf("请输入你关心的同伴的学号："); scanf("%d",&no); st=SearchBST(T,no,NULL,p); if(st) { printf("\n"); printf("你关心的同学已经报名，快来报名加入我们的志愿者活动吧！\n"); printf("\n"); } else { printf("\n"); printf("你关心的同伴还未报名，快邀请同伴一起加入我们的志愿队伍吧！\n"); printf("\n"); } break; case 4:printf("已报名的志愿者信息为：\n"); printf("\n"); InOrderTraverse(T); printf("\n"); break; case 5:exit (0); default :printf("输入非法，请输入数字1-5！\n"); fflush(stdin); } } }
