静态查找表adt

1、数据结构课程设计题 目 静态查找表 学 院 计算机学院 专 业 计算机科学与技术 年级班别 11计科七班 学 号 3111005984 学生姓名 梁永荣 指导教师 曾孜 2013 年 6月 25日一、题目：静态查找表的基本操作实现。ADT StataiSerachTable数据对象D:D是具有相同特性的数据元素集合，各个数据元素均含有类型相同，可惟一标识数据元素的关键的关键字。数据关系R：数据元素同属一个集合。基本操作P:Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destory(&ST)；初始条件:静态查找表ST存在。操作结果：销毁表ST；S

2、earch(ST,key);初始条件:静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse();初始条件；静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit（）一次且一次。一旦visit()失败，则操作失败。ADT StataiSerachTable二、存储结构的定义公用头文件#include "string.h"#include "stdio.h"#include "

3、string.h"#include "malloc.h"#define ERROR 0;#define TRUE 1;#define OK 1;两个存储结构typedef struct KeyType key;ElemType;typedef struct /顺序,有序存储结构 ElemType elem100; int length;SSTable;SSTable ST;三、算法设计#include "string.h"#include "stdio.h"#include "string.h"#incl

4、ude "malloc.h"#define ERROR 0;#define TRUE 1;#define OK 1;typedef char KeyType;typedef struct KeyType key;ElemType;typedef struct /顺序,有序存储结构 ElemType elem100; int length;SSTable;SSTable ST;void main() /主函数 int n; int flag; void menu1(); void menu2(); void goodbye(); void Creat_ST(); void D

5、estroy_ST(); void Search_ST(); void Sort_ST(); void Search_L(); void Travase(); void visit(); flag: system("cls"); printf("n"); printf("n"); printf(" 欢迎来到静态查找表系统n"); printf(" *n"); printf(" * 1.顺序查找 *n"); printf(" * 2.有序查找(折半查找) *n&quo

6、t;); printf(" * 3.离开系统 *n"); printf(" *n"); printf(" 请输入您的选择:"); scanf("%d",&n); switch(n) case 1: menu1();break; case 2: menu2();break; case 3: goodbye();break; default :goto flag; void menu1() /顺序查找表模块 int a; int flag1; flag1: system("cls"); pr

7、intf("n"); printf("n"); printf(" 欢迎来到顺序查找模块n"); printf(" *n"); printf(" * 1.构建查找表 *n"); printf(" * 2.销毁查找表 *n"); printf(" * 3.查找表中元素 *n"); printf(" * 4.遍历表中元素 *n"); printf(" * 5.返回上一层目录 *n"); printf(" * 6.

8、退出系统 *n"); printf(" *n"); printf(" 请输入您的选择:"); scanf("%d",&a); switch(a) case 1: Creat_ST();system("PAUSE");menu1();break; case 2: Destroy_ST();system("PAUSE");menu1();break; case 3: Search_ST();system("PAUSE");menu1();break; case

9、4: Travase();system("PAUSE");menu1();break; case 5: main();break; case 6:goodbye();break; default : goto flag1; void menu2()/有序表查找模块 int b; int flag2; flag2: system("cls"); printf("n");printf(" 11计科（7）班 梁永荣 3111005984 指导老师：曾孜n"); printf(" n");printf(

10、" 欢迎来到有序查找模块n"); printf(" *n"); printf(" * 1.构建查找表 *n"); printf(" * 2.销毁查找表 *n"); printf(" * 3.查找表中元素 *n"); printf(" * 4.遍历表中元素 *n"); printf(" * 5.返回上一层目录 *n"); printf(" * 6.退出系统 *n"); printf(" *n"); printf(&qu

11、ot; 请输入您的选择:"); scanf("%d",&b); switch(b) case 1: Creat_ST();system("PAUSE");Sort_ST();system("PAUSE");menu2();break; case 2: Destroy_ST();system("PAUSE");menu2();break; case 3: Search_L();system("PAUSE");menu2();break; case 4: Travase();sys

12、tem("PAUSE");menu2(); break; case 5: main();break; case 6: goodbye();break; default : goto flag2; void goodbye() /退出模块 system("cls"); printf("n"); printf("n"); printf("n"); printf(" *n"); printf(" * 感谢使用静态查找表系统 *n"); printf( * *n&

13、quot;); printf(" * 再见! *n"); printf(" *n"); 创建查找表void Creat_ST() /构造一个含n个数据元素的表态查找表ST int n,i,j=0; char s100; system("cls"); printf("你需要构造多少个数据？请输入："); scanf("%d",&n); printf("n"); while(n<0|n>100) printf("请输入1-100范围内的数字：n&qu

14、ot;); getchar(); scanf("%d",&n); printf("请输入%d个数据构造一个数据表n",n); getchar(); gets(s); for(;sj!='0'j+) ST.elemj.key=sj; ST.length=j; printf("你输入了%d个数据!它们是：n",j); for(i=0;i<j;i+) printf("%cn",ST.elemi.key); printf("n");销毁查找表：void Destroy_ST

15、() /销毁查找表 int i; system("cls"); printf("n"); if(!ST.elem0.key) printf("错误！原表为空,销毁失败。n"); else for(i=ST.length-1;i<0;i-) free(ST.elemi.key); /从表尾开始销毁 ST.length=0; printf("原表销毁成功！按任意键返回上一层目录。n"); 在查找表中查找元素:void Search_ST() /顺序查找 KeyType ky; int i; system(&quo

16、t;cls"); if(ST.length=0) printf("查找表为空，请先建表！n"); return ERROR; printf("要查找的数据:n"); getchar(); scanf("%c",&ky); ST.elemST.length+1.key=ky; /哨兵 for(i=0;ST.elemi.key!=ky;i+); /从前往后找 /i为要查找元素在表中位置，若失败，为0 if(i<=ST.length)printf("恭喜，查找成功！该数据在表的第%d个位置上。n"

17、,i+1); else printf("查找失败！n");有序查找的模块，在创建静态查找表之后排序，构成有序查找表：void Sort_ST() /将查找表的元素从小到大排序 int i,j; int c; for(j=0;j<ST.length-1;j+) for(i=0;i<ST.length-1-j;i+) if(ST.elemi.key>ST.elemi+1.key) c=ST.elemi.key; ST.elemi.key=ST.elemi+1.key; ST.elemi+1.key=c; printf("你输入的数据有序排列后为:n&

18、quot;); for(i=0;i<ST.length;i+) printf("%cn",ST.elemi.key); printf("n"); void Search_L() /有序查找 KeyType ky; int i; int high,mid; int low=0; system("cls"); if(ST.length=0) printf("查找表为空，请先建表！n"); return ERROR; high=ST.length; printf("要查找的数据:n"); get

19、char(); scanf("%c",&ky); while(low<=high) mid=(low+high)/2; if(ST.elemmid.key=ky) printf("恭喜，查找成功！该数据在表的第%d个位置上。n",mid+1); return; else if(ky<ST.elemmid.key) high=mid-1; else low=mid+1; printf("抱歉，查找失败！n");void Travase() /查找表的遍历 int i; system("cls");

20、 printf("n"); if(ST.length=0) printf("查找表为空，不能进行遍历n"); printf("现在将返回上层目录"); else visit(); void visit() /visit函数，被Travese函数调用 int i; printf("查找表的元素如下：n"); for(i=0;i<ST.length;i+) printf("%cn",ST.elemi.key); 四、程序测试以及使用手册：（1）主菜单界面（2）按“1”进入顺序查找模块 按“1”构建顺序查找表（注意输入以回车为结束标志）构建成功后按任意键返回上一层模块构建失败的出错处理、按“2“进入销毁查找表按“3“进入查找表中元素的操作查找成功的情况查找失败的情况： 查找表为空，不能进行查找、按“4”进入查找表的遍历操作 查找表为空，不能进行遍历、按“5”返回上一层模块、按“6”直接退出程序（3）按“2”进入到有序表的查找模块、按“1”构建有序查找表（注意输入以回车为结束标志）构建成功后按任意键返回上一层模块，再按一下，所有元素有序排列、按“2”进行对有序查找表