湖大數据结构实验7自组织线性表实验报告.docxVIP

HUNAN UNIVERSITY课程实验报告题目：自组织线性表学生姓名： 学生学号：专业班级：指导老师： 完成日期： 需求分析输入形式本程序可从文件中读入一个或多个汉字句子，并用自组织线性表保存，然后从另外一个文件中依次读入要查找的汉字。不对非法输入做处理，假定输入的数据都合法汉字。输出形式输出要查找的汉字和查找结果及比较次数，并将输出保存到文件中。具体格式如下：要查找的汉字为：查找成功，比较次数为——。查找失败，比较次数为——。程序功能本程序可读入保存在文件中的汉语句子和要查找的汉字，并用需查找的汉字与汉字句子中的汉字进行查找比较，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。测试数据①输入： 一二三四五六七八需要查找的汉字为：七九三四输出： 七 查找成功！查找次数为：8九 查找失败！查找次数为：9三 查找成功！查找次数为：3四 查找成功！查找次数为：4②输入： 一二三四五六七八需要查找的汉字为：五七四二输出： 五 查找成功！查找次数为：5七 查找失败！查找次数为：7四 查找成功！查找次数为：4二 查找成功！查找次数为：2③输入：一二三四五六七八需要查找的汉字为：六六二二输出： 六 查找成功！查找次数为：6六 查找失败！查找次数为：7二 查找成功！查找次数为：2二 查找成功！查找次数为：3④输入：一一二二三三四四需要查找的汉字为：一二三四输出： 一 查找成功！查找次数为：1二 查找失败！查找次数为：3三 查找成功！查找次数为：5四 查找成功！查找次数为：7⑤输入：￥%￥……概要设计抽象数据类型从文件中读入一组汉字集合，用自组织线性表保存。集合中必存在唯一一个第一元素和最后元素。除最后元素在外，元素间均有唯一的后继，除第一元素之外，元素间均有唯一的前驱，所以为数据元素建立一个线性数据关系，因此选用线性表来存储汉语句子。线性表ADT数据对象：D＝{ ai | ai ∈字符型, i=1,2,...,n, n≥0 }数据关系：R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n } 基本操作：void clear(); //初始化变量bool insert(); //从文件中读入汉字int getLength(); //获得汉字集合的长度void print(); //输出读入的记录到屏幕算法基本思想根据用户的输入构建相应的线性表，遍历线性表，依次用需查找的汉字与保存了读入汉字的自组织线性表中的每一个汉字作比较，如果相等那么查找到汉字，输出该汉字查找成功，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。没有查找到则输出查找失败，输出查找的次数。程序基本流程该程序主要分为输入模块，转置查找模块和输出模块读入模块：从文件中读入一组汉字集合，并保存在自组织线性表中，读入要查找的汉字。转置查找模块：依次根据需查找的汉字对汉字线性表遍历一次进行查找，若查找到该汉字，调用转置函数，将该汉字与前一个位置的汉字转置，然后继续查找下一个汉字。输出模块：若查找到汉字，则输出到屏幕和文件中查找成功并显示查找次数；若没有查找到该汉字，输出到屏幕和文件中查找不成功并显示查找的次数。详细设计 物理数据类型 查找函数：汉字占两个字节，所以在查找时要比较该两个字节是否都相同int?search(char?a[][2],int?size,char?c[2]){??//查找函数? int flag=0，i;???for(?i=0;isize;i++)???if(a[i][0]==c[0]??a[i][1]==c[1]){???//汉字所占的两位是否同?flag=1;? break;?}? if(flag){? if(i0)???Inverse(a,i,i-1);??? return?i+1;? }? else?? ?return?size;???//如果找不到则查找次数为以保存汉字的数??? }?倒置函数void?Inverse(char?a[][2],int?i,int?j){?char?temp=a[i][0];?a[i][0]=a[j][0];?a[j][0]=temp;?temp=a[i][1];? a[i][1]=a[j][1];?a[j][1]=temp;}线性表设计：class Alist{private: int maxsize; int fence; Elem *listArray;public:Alist(int max){maxsize=max;listArray=new Elem[maxsize];}void clear(){delete[]ListArray;}; //初始化变量bool insert(const Elem); //从文件中读入汉字int ge