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

浙江大学城市学院实验报告

课程名称数据结构与算法

实验项目名称实验十索引查找的实现

实验成绩指导老师（签名）日期2013-6-5

一.实验目的和要求

1.掌握常用的查找算法。

2.能实现并应用某一种查找算法-----索引查找算法。

二. 实验内容

1、假设有一张职工表，每个职工包含职工号与部门两项内容，现准备使用

索引存储结构，其中主表及索引表均采用顺序存储，且主表的记录类型定义为：

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 中。

2、编写测试程序（即主函数），首先输入职工表（包括职工人数与部门数），

然后调用上述函数建立索引存储结构并进行查找、插入、删除等操作。

把主函数存放在文件test10_1.cpp中。

3、填写实验报告，实验报告文件取名为report10.doc。

4、上传实验报告文件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

思路：根据定义的最大记录数与最大索引数，使用缺省值等初始化两张表

②void CreateIndexList(mainlist A, int n, indexlist B, int m)

功能：实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B，并同时把主表A中同一部门的记录依次链接起来

思路：通过对主表A中记录的一次扫描完成功能要求。对每次遍历到的元素，先尝试从索引表中寻找判断索引项是否已经被创建，如果没有创建则新建该项索引，项目的next值标记为缺省；如果能够从索引表中找到索引，则项目的next 值链接至索引中对应项，并更新对应索引项的start值，从而保证A表中的连接方向是从下标小的元素链接到下标大的元素

③int SearchIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)

功能：查找记录worker的函数

思路：首先在索引表B中查找worker所属的部门，索引表中未找到对应索引，则查找失败返回；索引表中找到对应索引，则根据索引值在主表中查找，从start 标记的值开始沿着next给出的位置依次查找，找到key值相同的元素表示查找成功，返回其位置即可；若查找到最后下标变为缺省值，则说明表中没有该元素，返回查找失败

④void InsertIndexList(mainlist A, int &n, indexlist B, int &m, ElemType worker)

功能：插入记录worker的函数

思路：首先在索引表B中查找对应索引项，如果未找到索引表记录，则新建该项索引；如果已找到索引，更新索引项length和主表中元素next值。最后将worker 元素插入主表末尾即可

⑤void DeleteIndexList(mainlist A, int &n, indexlist B, int &m, ElemType worker)

功能：选做：删除记录worker（做删除标记）的函数

思路：删除的实现是在查询算法的基础上扩展得出的，依据从索引表中找到的索引值在主表A中进行查找时，需要设置一个变量保存当前比较元素的“先驱”，这样在成功查找到元素时，可以将该元素的next值赋给先驱的next，从而链接前后二者，再将该元素标记成删除状态，即可完成所要求的功能。当要删除的是该索引对应的头元素，应当直接标记，并修改对应索引的start值。另外，如果该元素原来就只有一个元素，则标记索引同样需要被删除

四. 实验结果与分析

包括运行结果截图等

【测试数据①】

职工人数：12

部门数：4

表1 主表

表2 索引表

【第(1)次操作】

·操作类型：查找·输入：DZ 3

·正确结果：位置7

·特性说明：普通查找

·操作类型：插入

·输入：BAKA 25

·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：插入不属于原来索引范围内的元素

职工人数：13

部门数：5

表2 主表

表2 索引表

【第(3)次操作】

·操作类型：插入

·输入：BAKA 100

·正确结果：主表、索引表改变（具体见下表），总人数改变·特性说明：插入属于前一次操作新建的索引的元素

职工人数：14

部门数：5

表3 主表

表2 索引表

【第(4)次操作】

·操作类型：删除

·输入：JS 1

·正确结果：主表、索引表改变（具体见下表），总人数改变·特性说明：删除属于索引表某一索引项头元素、整个主表头元素

职工人数：13

部门数：5

表4 主表

表2 索引表

【第(5)次操作】

·操作类型：查询

·输入：JS 1

·正确结果：找不到该员工信息

·特性说明：查找之前操作中删除的元素，验证是否正确删除

【测试数据②】

职工人数：14

部门数：10

表5 主表

表2 索引表

【第(1)次操作】

·操作类型：查询

·输入：Halley 76

·正确结果：找不到该员工信息

·特性说明：查询一个表中没有的元素

【第(2)次操作】

·操作类型：插入

·输入：Halley 76

·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：插入刚才查询的表中没有的元素

职工人数：15

部门数：11

表6 主表

表2 索引表

【第(3)次操作】

·操作类型：删除

·输入：Jupiter 5

·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：删除索引项长度为1的元素，使得索引表中的项目也需要删除

职工人数：14

部门数：11

表7 主表

表2 索引表

【第(4)次操作】

·操作类型：删除

·输入：Jupiter 10

·正确结果：找不到该员工信息

·特性说明：尝试删除一个曾经在表中有对应索引的元素，来验证前面步骤中索引项的删除是否正确

【第(5)次操作】

·操作类型：删除

·输入：Pluto 1

·正确结果：找不到该员工信息

·特性说明：尝试删除一个曾经在表中存在过的元素，验证之前的删除是否正确

【第(6)次操作】

·操作类型：删除

·输入：Halley 76

·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：删除手动添加的元素，并且该元素的索引项下仅包含该元素

职工人数：14

部门数：10

表8 主表

表2 索引表

【第(7)次操作】

·操作类型：查询

·输入：Pluto 1

·正确结果：找不到该员工信息

·特性说明：查询一个曾经存在过，被手动删除的元素

五. 心得体会

记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

创建索引表并链接主表元素的操作的思路主要如下：

·对于主表元素，从末尾到开头进行一次整体循环

·每次循环中，判断当前元素的索引项是否存在

·索引项存在，先将当前元素的next值置为索引的start值，再将索引的start更新为当前元素下标；

·索引项不存在，新建该项索引，并将next值置为缺省值

通过这样一个循环，最终得到的主表将按照“下标小的元素链接到下标大的元素”这样的规则来进行链接，而索引表中索引的顺序由于是从1开始计数，会对应索引项元素第一次出现在主表中的顺序正好相反。我对这个操作进行了一定的思考之后，认为保证主表中元素的正序链接是比较需要也相对比较符合实际逻辑的，而索引表则没有太大的必要维护这个顺序。

【附录----源程序】

[Test10_1.cpp]

#include

#include

#include

#include

#include"Index.h"