数据结构实验报告之静态查找表

数据结构实验报告 题目：静态查找表的实现 成 绩 _2014年6月10号静态查找表抽象数据类型的实现一、设计任务、要求及所用的软件环境或工具： 1.设计任务及要求：用C语言实现静态查找表的抽象数据类型 2.软件环境：win7 3.开发工具：C-Free 二、抽象数据类型的实现1. 题目 采用顺序存储和链式存储为存储结构，实现抽象数据类型StaticSearchTable。 ADT StaticSearchTable 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素 含有类型相同的关键字，可唯一标识元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： Create(&ST,n); 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(&ST); 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search(ST,key); 初始条件：静态查找表ST存在，key 为和关键字类型相同的 给定值。 操作结果：若 ST 中存在其关键字等于key的数据元素，则 函数值为其值或在表中的位置，否则为“空”。 Traverse(ST,Visit(); 初始条件：静态查找表ST存在，Visit是对元素操作的应用 函数。 操作结果：按某种次序对ST的每个元素调用函数Visit()一 次且仅一次。一旦Visit()失败，则操作失败。 ADT StaticSearchTable2存储结构定义 *公用头文件DS0.h:#include#include#include *预定义常量和类型 /函数结果状态代码#define TRUE 1#define FALSE 0 #define OK 1#define ERROR 0typedef int Status; typedef int KeyType; typedef float KeyType; typedef char KeyType; typedef int ElemType; typedef ElemType TElemType; 1)顺序存储结构typedef structElemType *elem; /数据元素存储空间基址，0号单元留空 int length; /表长 SSTable; 2)二叉链表存储结构typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针BiTNode,*BiTree;3. 算法设计 1)顺序表的查找void Creat_Seq(SSTable *ST,ElemType r,int n) int i; (*ST).elem = (ElemType*)calloc(n+1,sizeof(ElemType); /动态生成n+1个数据元素空间(0号单元不用) if(!(*ST).elem) exit(0); for(i=1;i=n;i+) (*ST).elemi=ri-1; /将数组r的值依次赋给ST (*ST).length=n;Status Destroy_Seq(SSTable &ST)free(ST.elem);ST.elem = NULL;ST.length = 0;return OK; int Search_Seq(SSTable ST,KeyType key) int i; ST.elem0.key=key; /哨兵 for(i=ST.length;!(ST.elemi.key=key);-i); /从后往前找 return i; /找不到时，i为0 void Traverse(SSTable ST,void(*Visit)(ElemType) ElemType *p; int i; p=+ST.elem; /p指向第一个元素 for(i=1;i=ST.length;i+) Visit(*p+); 2)有序表的查找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.elemmid) return mid; /找到待查元素 else if(keyST.elemmid) high = mid - 1; /*继续在前半区间查找*/ else low = mid + 1; /继续在后半区间查找 return 0; /查找失败 3)静态树表的查找Status Creat_Seq(SSTable *ST,int n) int i; (*ST).elem = (ElemType*)calloc(n+1,sizeof(ElemType); /动态生成n+1个数据元素空间(0号单元不用) if(!(*ST).elem) exit(0); for(i=1;i=n;i+) (*ST).elemi=ri-1; /将数组r的值依次赋给ST (*ST).length=n; return OK;void Ascend(SSTable *ST) / 重建静态查找表为按关键字非降序排序 int i,j,k; for(i=1;i(*ST).length;i+) k=i; (*ST).elem0=(*ST).elemi; /待比较值存0单元 for(j=i+1;j=(*ST).length;j+) if(*ST).elemj.key(*ST).elem0.key) k=j; (*ST).elem0=(*ST).elemj; if(k!=i) /有更小的值则交换 (*ST).elemk=(*ST).elemi; (*ST).elemi=(*ST).elem0; Status Creat_Ord(SSTable *ST,int n) Status f; f=Creat_Seq(ST,n); if(f) Ascend(ST); return f;Status SecondOptimal(BiTree *T, ElemType R,int sw,int low,int high) int i,j; double min,dw; i=low; min=fabs(swhigh-swlow); dw=swhigh+swlow-1; for(j=low+1;j=high;+j) /选择最小值 if(fabs(dw-swj-swj-1)data=Ri; /生成结点 if(i=low) (*T)-lchild=NULL; /左子树空 else SecondOptimal(&(*T)-lchild,R,sw,low,i-1); /构造左子树 if(i=high) (*T)-rchild=NULL; else SecondOptimal(&(*T)-rchild,R,sw,i+1,high); return OK;Status Traverse(SSTable ST,void(*Visit)(ElemType) ElemType *p; int i; p=+ST.elem; / p指向第一个元素 for(i=1;i=ST.length;i+) Visit(*p+); return OK;void FindSW(int sw,SSTable ST) int i; sw0=0; for(i=1;idata.key=key) return OK; else if(*T)-data.keykey) *T=(*T)-lchild; else *T=(*T)-rchild; return FALSE; 4 测试： 1）顺序表的查找typedef struct /数据元素 long number; /准考证号 char name9; int politics; int Chinese; int English; int math; int physics; int chemistry; int biology; int total; /总分 ElemType; /以教科书图9.1高考成绩为例 void print(ElemType c)printf(%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5dn,c.number,,c.politics,c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c.total);SSTable head;int main() ElemType rN=,陈红,85,86,88,100,92,90,45, ,陆华,78,75,90,80,95,88,37, ,张平,82,80,78,98,84,96,40; SSTable st; int i; long s; for(i=0;iN;i+) /计算总分 ri.total=ri.politics+ri.Chinese+ri.English+ri.math+ri.physics+ri.chemistry+ri.biology; Creat_Seq(&st,r,N); printf(准考证号 姓名 政治 语文 外语 数学 物理 化学 生物 总分n); Traverse(st,print); printf(请输入待查找人的考号: ); scanf(%ld,&s); i=Search_Seq(st,s); if(i) print(st.elemi); else printf(查找失败n);结果截图如下：查找成功：查找失败： 2）有序表的查找SSTbale head;int main()int j,k,t,w;SSTable ST;int i; ST.length=LENGTH; printf(请按大小顺序输入一个顺序表共%d个元素!n,ST.length);ST.elem=(ElemType*)malloc(ST.length+1)*sizeof(ElemType);for(i=1;i=ST.length;i+)scanf(%d,&ST.elemi);printf(请输入要查找的元素：);scanf(%d,&k);w=Search_Bin(ST,k);if(w)printf(您要查找的%d是第%d个元素n,k,w);else printf(查找失败n); 结果截图如下：查找成功：查找失败： 3）静态树链表的查找typedef struct /数据元素类型KeyType key; int weight;ElemType;ElemType rM=A,1,B,1,C,2,D,5,E,3, F,4,G,4,H,3,I,5; /以教科书例9-1为例void print(ElemType c) /* Traverse()调用的函数 */ printf(%c %d) ,c.key,c.weight);SSTbale head;int main() SSTable st; SOSTree t; Status i; KeyType s; Creat_Ord(&st,M); /* 由全局数组产生非降序静态查找表st */ Traverse(st,print); CreateSOSTree(&t,st); /* 由有序表构造一棵次优查找树 */ printf(n请输入待查找的字符: ); scanf(%c,&s); i=Search_SOSTree(&t,s); if(i) printf(%c的权值是%dn,s,t-data.weight); elseprintf(表中不存在此字符n);结果截图如下：查找成功：查找失败：三、实验总结和体会 1.几种存储结构的比较1)顺序查找： 优点：算法简单且适应面广；缺点：平均查找长度较大，特别是当n很