搜索
1/27浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验十索引查找的实现实验成绩指导老师（签名）日期2013-6-5一.实验目的和要求1.掌握常用的查找算法。2.能实现并应用某一种查找算法-----索引查找算法。二.实验内容1、假设有一张职工表，每个职工包含职工号与部门两项内容，现准备使用索引存储结构，其中主表及索引表均采用顺序存储，且主表的记录类型定义为：typedefstruct{intkey;/*职工号，作为关键字域*/chardepart[13];/*部门名称，作为索引值域*/intnext;/*链接同一部门的职工记录*/}ElemType;要求编写以下几个函数：①实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B，并同时把主表A中同一部门的记录依次链接起来的功能的函数：voidCreateIndexList(mainlistA,intn,indexlistB,intm)②查找记录worker的函数：intSearchIndexList(mainlistA,intn,indexlistB,intm,ElemTypeworker)其中A为存储n个记录的主表，B为m个索引项的索引表，查找成功返回A中的位置值，否则返回-1。③插入记录worker的函数：voidInsertIndexList(mainlistA,int&n,indexlistB,int&m,ElemTypeworker)其中A为存储n个记录的主表，B为m个索引项的索引表。④输出主表与索引表信息的函数：voidOutputIndexList(mainlistA,intn,indexlistB,intm)其中A为存储n个记录的主表，B为m个索引项的索引表。⑤选做：删除记录worker（做删除标记）的函数：voidDeleteIndexList(mainlistA,int&n,indexlistB,int&m,ElemTypeworker)2/27其中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服务器上自己的文件夹下。三.函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路【结构说明】//主表最大记录数constintMaxSize=100;//索引表最大索引数constintILMaxSize=100;//缺省值定义constintDefaultNum=-1;//删除标记constintDeleteNum=-2;//索引表索引值定义typedefcharIndexKeyType[13];//索引项的记录类型typedefstruct{IndexKeyTypeindex;//唯一标识一个子表的索引值intstart;//子表中第一个元素所在的存储位置intlength;//子表的长度}IndexItem;//主表的记录类型typedefstruct{intkey;/*职工号，作为关键字域*/chardepart[13];/*部门名称，作为索引值域*/intnext;/*链接同一部门的职工记录*/}ElemType;typedefElemTypemainlist[MaxSize];//主表类型typedefIndexItemindexlist[ILMaxSize];//索引表类型【函数说明】3/27①voidInitList(mainlistA,indexlistB)功能：初始化主表A与索引表B思路：根据定义的最大记录数与最大索引数，使用缺省值等初始化两张表②voidCreateIndexList(mainlistA,intn,indexlistB,intm)功能：实现在已经包含n个记录的顺序存储的主表A上建立具有m个索引项的索引表B，并同时把主表A中同一部门的记录依次链接起来思路：通过对主表A中记录的一次扫描完成功能要求。对每次遍历到的元素，先尝试从索引表中寻找判断索引项是否已经被创建，如果没有创建则新建该项索引，项目的next值标记为缺省；如果能够从索引表中找到索引，则项目的next值链接至索引中对应项，并更新对应索引项的start值，从而保证A表中的连接方向是从下标小的元素链接到下标大的元素③intSearchIndexList(mainlistA,intn,indexlistB,intm,ElemTypeworker)功能：查找记录worker的函数思路：首先在索引表B中查找worker所属的部门，索引表中未找到对应索引，则查找失败返回；索引表中找到对应索引，则根据索引值在主表中查找，从start标记的值开始沿着next给出的位置依次查找，找到key值相同的元素表示查找成功，返回其位置即可；若查找到最后下标变为缺省值，则说明表中没有该元素，返回查找失败④voidInsertIndexList(mainlistA,int&n,indexlistB,int&m,ElemTypeworker)功能：插入记录worker的函数思路：首先在索引表B中查找对应索引项，如果未找到索引表记录，则新建该项索引；如果已找到索引，更新索引项length和主表中元素next值。最后将worker元素插入主表末尾即可⑤voidDeleteIndexList(mainlistA,int&n,indexlistB,int&m,ElemTypeworker)功能：选做：删除记录worker（做删除标记）的函数思路：删除的实现是在查询算法的基础上扩展得出的，依据从索引表中找到的索引值在主表A中进行查找时，需要设置一个变量保存当前比较元素的“先驱”，这样在成功查找到元素时，可以将该元素的next值赋给先驱的next，从而链接前后二者，再将该元素标记成删除状态，即可完成所要求的功能。当要删除的是该索引对应的头元素，应当直接标记，并修改对应索引的start值。另外，如果该元素原来就只有一个元素，则标记索引同样需要被删除四.实验结果与分析包括运行结果截图等【测试数据①】职工人数：12部门数：44/27表1主表序号部门名称职工号下一记录1JS122JS233JS344JS4-5DZ166DZ277DZ3-8JJ199JJ2-10HG11111HG21212HG3-表2索引表序号索引值首元素位置长度1HG1032JJ823DZ534JS145/27【第(1)次操作】·操作类型：查找·输入：DZ3·正确结果：位置7·特性说明：普通查找【第(2)次操作】·操作类型：插入6/27·输入：BAKA25·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：插入不属于原来索引范围内的元素职工人数：13部门数：5表2主表序号部门名称职工号下一记录1JS122JS233JS344JS4-5DZ166DZ277DZ3-8JJ199JJ2-10HG11111HG21212HG3-13BAKA25-表2索引表序号索引值首元素位置长度1HG1032JJ823DZ534JS145BAKA1317/27【第(3)次操作】·操作类型：插入·输入：BAKA100·正确结果：主表、索引表改变（具体见下表），总人数改变·特性说明：插入属于前一次操作新建的索引的元素职工人数：14部门数：58/27表3主表序号部门名称职工号下一记录1JS122JS233JS344JS4-5DZ166DZ277DZ3-8JJ199JJ2-10HG11111HG21212HG3-13BAKA251414BAKA100-表2索引表序号索引值首元素位置长度1HG1032JJ823DZ534JS145BAKA1329/27【第(4)次操作】·操作类型：删除·输入：JS1·正确结果：主表、索引表改变（具体见下表），总人数改变·特性说明：删除属于索引表某一索引项头元素、整个主表头元素职工人数：13部门数：5表4主表序号部门名称职工号下一记录2JS233JS344JS4-5DZ166DZ277DZ3-8JJ199JJ2-10HG11110/2711HG21212HG3-13BAKA251414BAKA100-表2索引表序号索引值首元素位置长度1HG1032JJ823DZ534JS235BAKA132【第(5)次操作】11/27·操作类型：查询·输入：JS1·正确结果：找不到该员工信息·特性说明：查找之前操作中删除的元素，验证是否正确删除【测试数据②】职工人数：14部门数：10表5主表序号部门名称职工号下一记录1Saturn83352Uranus924-3Venus18764Earth772145Saturn264-6Venus18677Venus166-8Neptune815-9Mercury173-10Jupiter713-11Sun213-12Mars487-13Pluto300-14Earth221-12/27表2索引表序号索引值首元素位置长度1Earth422Pluto1313Mars1214Sun1115Jupiter1016Mercury917Neptune818Venus339Saturn1210Uranus2113/27【第(1)次操作】·操作类型：查询·输入：Halley76·正确结果：找不到该员工信息·特性说明：查询一个表中没有的元素14/27【第(2)次操作】·操作类型：插入·输入：Halley76·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：插入刚才查询的表中没有的元素职工人数：15部门数：11表6主表序号部门名称职工号下一记录1Saturn83352Uranus924-3Venus18764Earth772145Saturn264-6Venus18677Venus166-8Neptune815-9Mercury173-10Jupiter713-11Sun213-12Mars487-13Pluto300-14Earth221-15Halley76-15/27表2索引表序号索引值首元素位置长度1Earth422Pluto1313Mars1214Sun1115Jupiter1016Mercury917Neptune818Venus339Saturn1210Uranus2111Halley15116/27【第(3)次操作】·操作类型：删除·输入：Jupiter5·正确结果：主表、索引表改变（具体见下表），总人数、总部门数改变·特性说明：删除索引项长度为1的元素，使得索引表中的项目也需要删除职工人数：14部门数：11表7主表序号部门名称职工号下一记录1Saturn83352Uranus924-3Venus18764Earth772145Saturn264-6Venus18677Venus166-8Neptune815-9Mercury173-11Sun213-12Mars487-13Pluto300-14Earth221-15Halley76-17/27表2索引表序号索引值首元素位置长度1Earth422Pluto1313Mars1214Sun1116Mercury917Neptune818Venus339Saturn1210Uranus2111Halley151【第(4)次操作】·操作类型：删除·输入：Jupiter10·正确结果：找不到该员工信息·特性说明：尝试删除一个曾经在表中有对应索引的元素，来验证前面步骤中索引项的删除是否正确【第(5)次操作】·操作类型：删除·输入：Pluto118/27·正确结果：找不到该员工信息·特性说明：尝试删