【数据结构算法】实验10 索引查找的实现(大作业)(附源代码).doc

浙江大学城市学院实验报告 课程名称 数据结构与算法 实验项目名称 实验十 索引查找的实现 实验成绩 指导老师（签名 ） 日期 2013-6-5 实验目的和要求 掌握常用的查找算法。 能实现并应用某一种查找算法-----索引查找算法。 二. 实验内容 假设有一张职工表，每个职工包含职工号与部门两项内容，现准备使用索引存储结构，其中主表及索引表均采用顺序存储，且主表的记录类型定义为： typedef struct { int key; /*职工号，作为关键字域*/ char depart[13]; /*部门名称，作为索引值域*/ int next; /*链接同一部门的职工记录*/ } ElemType; 要求编写以下几个函数： 实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B，并同时把主表A中同一部门的记录依次链接起来的功能的函数： void CreateIndexList(mainlist A, int n, indexlist B, int m) 查找记录worker的函数： int SearchIndexList(mainlist A, int n, indexlist B, int m, ElemType worker) 其中A为存储n个记录的主表，B为m个索引项的索引表，查找成功返回A中的位置值，否则返回-1。 插入记录worker的函数： void InsertIndexList(mainlist A, int n, indexlist B, int m, ElemType worker) 其中A为存储n个记录的主表，B为m个索引项的索引表。 输出主表与索引表信息的函数： void OutputIndexList(mainlist A, int n, indexlist B, int m) 其中A为存储n个记录的主表，B为m个索引项的索引表。 选做：删除记录worker（做删除标记）的函数： void DeleteIndexList(mainlist A, int n, indexlist B, int m, ElemType worker) 其中A为存储n个记录的主表，B为m个索引项的索引表，需删除记录的职工号为worker.key、部门为worker.depart。 把主表及索引表的存储结构定义以及上述这些函数存放在头文件Index.h中。 编写测试程序（即主函数），首先输入职工表（包括职工人数与部门数），然后调用上述函数建立索引存储结构并进行查找、插入、删除等操作。 把主函数存放在文件test10_1.cpp中。 填写实验报告，实验报告文件取名为report10.doc。 上传实验报告文件report10.doc与源程序文件test10_1.cpp及Index.h到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路 【结构说明】 //主表最大记录数 const int MaxSize = 100; //索引表最大索引数 const int ILMaxSize = 100; //缺省值定义 const int DefaultNum = -1; //删除标记 const int DeleteNum = -2; //索引表索引值定义 typedef char IndexKeyType[13]; //索引项的记录类型 typedef struct { IndexKeyType index; // 唯一标识一个子表的索引值 int start; //子表中第一个元素所在的存储位置 int length; //子表的长度 } IndexItem; //主表的记录类型 typedef struct { int key; /*职工号，作为关键字域*/ char depart[13]; /*部门名称，作为索引值域*/ int next; /*链接同一部门的职工记录*/ } ElemType; typedef ElemType mainlist[MaxSize]; //主表类型 typedef IndexItem indexlist[ILMaxSize]; //索引表类型 【函数说明】 ① void InitList(mainlist A, indexlist B) 功能：初始化主表A与索引表B 思路：根据定义