实验十一 索引查找的实现.doc

浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验十一 索引查找的实现 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1. 掌握常用的查找算法。2. 能实现并应用某一种查找算法-索引查找算法。二. 实验内容1、 假设有一张职工表，每个职工包含职工号与部门两项内容，现准备使用索引存储结构，其中主表及索引表均采用顺序存储，且主表的记录类型定义为:typedef struct int key; /职工号，作为关键字域char depart13; /部门名称，作为索引值域int next; /链接同一部门的职工记录 ElemType; 要求编写以下几个算法： 实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B,并同时把主表A中同一部门的记录依次链接起来的算法：void CreateIndexList(mainlist A, int n, indexlist B, int m) 在n个记录的主表A与m个索引项的索引表B中查找职工号为key、部门为depart的职工，并返回该职工记录在主表中的位置的算法：int SearchIndexList(mainlist A, int n, indexlist B, int m, int key, char *depart) （选做）插入记录worker的算法：void InsertIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)其中A为存储n个记录的主表，B为m个索引项的索引表。把主表及索引表的存储结构定义以及上述这些函数存放在头文件Index.h中。 2、 编写测试程序（即主函数），首先输入职工表（包括职工人数与部门数），然后调用上述函数建立索引存储结构并进行查找等操作。把主函数存放在文件test11.cpp中。3、 填写实验报告，实验报告文件取名为report11.doc。4、 上传实验报告文件report11.doc与源程序文件test11.cpp及Index.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路函数：void CreateIndexList(mainlist A,int n,indexlist B,int m)功能：实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B,并同时把主表A中同一部门的记录依次链接起来思路：定义一个变量k用于存放当前索引项的个数，定义一个数组c 用于存放每一个子表中最后一个元素所在的下标在索引表中顺序查找索引值为Ai.depart的索引项，若该索引项不存在，需新建一个索引项，k+；若该索引项已存在，将该子表中最后一个元素的next值指向下标i将该子表中最后一个元素所在的下标设置为i函数：int SearchIndexList(mainlist A,int n,indexlist B,int m,ElemType worker)功能：在n个记录的主表A与m个索引项的索引表B中查找职工号为key、部门为depart的职工，并返回该职工记录在主表中的位置思路：在索引表中顺序查找索引值为worker.depart的索引项若查找失败，返回-1 在已经查找到的第j个子表中顺序查找关键字为worker.key的记录若查找成功返回其下标，否则返回-1函数：void InsertIndexList(mainlist A,int &n,indexlist B,int &m,ElemType worker功能：插入worker记录思路：在索引表中顺序查找索引值为worker.depart的索引项若该索引项不存在，需新建该索引项，m+若该索引项已存在，查找该记录是否已经存在，若存在则插入失败，否则将该子表中最后一个元素的next值指向主表A的下标n，length+将记录worker插入主表A，n+函数：void OutputIndexList(mainlist A,int n,indexlist B,int m)功能：输出主表与索引表信息4. 实验结果与分析输入输出查找示例一（查找成功）查找示例二（worker.key不存在，查找失败）查找示例三（worker.depart不存在，查找失败）插入示例一（worker记录已存在，插入失败）插入示例二（worker.depart已存在，插入成功）插入示例三（worker.depart不存在，新建索引项，插入成功）输出（插入3条记录后的职工表、索引表）五. 心得体会【附录-源程序】test11.cpp#include#include#include#include#includeIndex.hvoid main()int n,m,i,t;ElemType worker;mainlist A;indexlist B;coutnm;coutendl输入职工表：endl;for(i=0;iAi.key;cinAi.depart;Ai.next=-1;CreateIndexList(A,n,B,m);while(1)coutendl*endl;couti;coutendl;switch(i)case 1:cout输入待查找的worker(key&depart)：worker.keyworker.depart;t=SearchIndexList(A,n,B,m,worker);if(t=-1)cout查找失败！endl;elsecout所要查找的worker在A中的下标：tendl;break;case 2:cout输入待插入的worker(key&depart)：worker.keyworker.depart;InsertIndexList(A,n,B,m,worker);break;case 3:OutputIndexList(A,n,B,m);break;case 0:exit(1);break;default:break;Index.h#define MaxSize 100#define ILMaxSize 100typedef structint key; /职工号，作为关键字域char depart13; /部门名称，作为索引值域int next; /链接同一部门的职工记录ElemType;typedef ElemType mainlistMaxSize; /主表类型typedef structchar index13; /唯一标识一个子表的索引值int start; /子表中第一个元素所在的存储位置 int length; /子表的长度，此处可省略IndexItem;typedef IndexItem indexlistILMaxSize; /索引表类型void CreateIndexList(mainlist A,int n,indexlist B,int m)int i,j,k=0; /k用于存放当前索引项的个数 int* c=new intm;/数组c用于存放每一个子表中最后一个元素所在的下标for(i=0;in;i+)/在索引表中顺序查找索引值为Ai.depart的索引项for(j=0;jk;j+)if(strcmp(Ai.depart,Bj.index)=0)break;/若j=k，则表明该索引项不存在，需新建一个索引项，k+if(j=k)strcpy(Bk+.index,Ai.depart);Bj.start=i;Bj.length=1;/若该索引项已存在，将该子表中最后一个元素的next值指向下标ielseAcj.next=i;Bj.length+;/将该子表中最后一个元素所在的下标设置为icj=i;delete c;/int SearchIndexList(mainlist A,int n,indexlist B,int m,ElemType worker)int i,j;/在索引表中顺序查找索引值为worker.depart的索引项for(j=0;jm;j+)if(strcmp(worker.depart,Bj.index)=0)break;/若j=m，则表明查找失败，返回-1if(j=m)return -1;/在已经查找到的第j个子表中顺序查找关键字为worker.key的记录for(i=Bj.start;i!=-1;i=Ai.next)if(worker.key=Ai.key)break;/若查找成功返回其下标，否则返回-1if(i!=-1)return i;elsereturn -1;void InsertIndexList(mainlist A,int &n,indexlist B,int &m,ElemType worker)int i,j;/在索引表中顺序查找索引值为worker.depart的索引项for(j=0;jm;j+)if(strcmp(worker.depart,Bj.index)=0)break;/若j=m，则表明该索引项不存在，需新建该索引项，m+if(j=m)strcpy(Bm.index,worker.depart);Bm.start=n;Bm.length=1;m+;/若该索引项已存在else/查找该记录是否已经存在，若存在则插入失败for(i=Bj.start;i!=-1;i=Ai.next)if(worker.key=Ai.key)cout该记录已存在，插入失败！endl;return;/将该子表中最后一个元素的next值指向主表A的下标n，length+Bj.length+;for(i=Bj.start;Ai.next!=-1;i=Ai.next);Ai.next=n;/将记录worker插入主表A，n+worker.next=-1;An+=worker;cout插入成功！endl;/void OutputIndexList(mainlist A,int n,indexlist B,int m)cout 职工表endl;cout NO key depart nextendl;cout*endl;for(int i=0;in;i+)cout