数据结构实验七：自组织线性表

1、 HUNAN UNIVERSITY课程实验报告题 目： 自组织线性表 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日期 2 0 1 5年 12 月 31日 一需求分析1. 程序功能本程序可输入汉语句子和要查找的汉字，并用需查找的汉字与汉字句子中的汉字进行查找比较，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。2.输入形式用户输入句子，可以输入空格，不对非法输入做处理，假定输入的数据都合法汉字。用户输入要查找的字，用空格隔开。3.输出形式 输出要查找的汉字和查找结果及比较次数，并将输出保存到文件中。要查找的汉字为：“汉字A”查找成功，比较次数为。“汉字 B”查找失

2、败，比较次数为。4.测试数据数据1：请输入文字（文字间可输入空格）：我爱你 中国请输入查找的字们（中间用空格隔开）：你 你 你 你 中 国输出： 你 查找成功！查找次数为：3你 查找失败！查找次数为：2你 查找成功！查找次数为：1你 查找成功！查找次数为：1中 查找成功！查找次数为：4国 查找成功！查找次数为：5数据2： 请输入文字（文字间可输入空格）：隔壁老王买了个瓜 很甜请输入查找的字们（中间用空格隔开）：瓜 很 甜 老 王输出： 瓜 查找成功！查找次数为：3很 查找失败！查找次数为：2甜 查找成功！查找次数为：1老 查找成功！查找次数为：4王 查找成功！查找次数为：5数据3： 请输入文字

3、（文字间可输入空格）：一二三四五六七八请输入查找的字们（中间用空格隔开）： 六六二二输出： 六 查找成功！查找次数为：6六 查找成功！查找次数为：5二 查找成功！查找次数为：2二 查找成功！查找次数为：1数据4： 请输入文字（文字间可输入空格）：君不见黄河之水天上来 奔流到海请输入查找的字们（中间用空格隔开）：不 见 君输出： 不 查找成功！查找次数为：2见 查找失败！查找次数为：3君 查找成功！查找次数为：3输入： 请输入文字（文字间可输入空格）：小明 我真不知道该输入什么了请输入查找的字们（中间用空格隔开）：你 是 小 鸿 吗输出： 你 查找成功！查找次数为：2是 查找失败！查找次数为：3

4、小 查找成功！查找次数为：3鸿 查找失败！查找次数为：3吗 查找成功！查找次数为：3二概要设计 1.抽象数据类型将每一个元素储存在一个有序并且有限的序列中，每一个元素都有一个自己的位置，也都有一个数据类型，所以使用线性表来储存每一个文字。 2.线性表ADT数据对象：定义线性表的最大储存元素maxsize; 当前储存元素数listsize;数据关系：若listsize=0,则线性表没有元素，为空;基本操作：alist(int n)/构造函数 alist()/析构函数 bool append(int a)/增加元素 bool getValue(int& it) const /获得it位置线

5、性表的值 bool insert(int a)/插入元素 3.算法基本思想 自组织线性表根据估算的访问频率排列记录，先放置请求频率最高的记录，接下来是请求频率次高的记录，依此类推。自组织线性表根据实际的记录访问模式在线性表中修改记录顺序。自组织线性表使用启发式规则决定如何重新排列线性表。 转置方法的基本原理是，在一次查找过程中，一旦找到一个记录，则将它与前一个位置的记录交换位置。这样，随着时间的推移，经常访问的记录将移动到线性表的前端，而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后面 4.程序基本流程该程序主要分为输入模块，转置查找模块和输出模块（1） 读入模块：从文件中读入一组汉字集

6、合，并保存在自组织线性表中，读入要查找的汉字。（2） 转置查找模块：依次根据需查找的汉字对汉字线性表遍历一次进行查找，若查找到该汉字，调用转置函数，将该汉字与前一个位置的汉字转置，然后继续查找下一个汉字。（3） 输出模块：若查找到汉字，则输出到屏幕和文件中查找成功并显示查找次数；若没有查找到该汉字，输出到屏幕和文件中查找不成功并显示查找的次数。三详细设计1.物理数据类型本题中需要元素的交换，由于每个中文占用两个字节的函数，使用数组交换只需要交换数组的两个元素，较为便利，所以使用顺序表来实现线性表。顺序表的伪代码class AListprivate:int listsize;int maxsiz

7、e;int fence;Elem* listArray;public:AList(int size)maxsize = size;fence = listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setEnd() fence = listsize; void prev() if (fence != 0) fence-; void next() if (fence <= listsize)fence+;bool getValue(Elem&

8、it) const it = listArrayfence;return true;bool insert(Elem item) if (listsize = maxsize) return false;for (int i = listsize; i > fence; i-)listArrayi = listArrayi - 1;listArrayfence = item; listsize+;return true;bool append(Elem& item)if (listsize = maxsize)return false;listArraylistsize+ = i

9、tem;return true;2.算法的具体步骤顺序表的构建查找元素转置顺序表的构建：先将文字输入到一个string类的字符串中，再将字符串中每一个元素逐个赋值给顺序表，值得注意的是中文每个字占两个字符串，在赋值时需要跳过空格，即线性表中值存储文字。string a;getline(cin, a);/可输入空格for (int i = 0; i < a.length(); i+)if (ai = ' ')continue;listArraylistsize = ai;listsize+;maxsize = listsize;return true;查找元素：输入一组汉字

10、，在顺序表中比较查找，若为数组中的第一个即是要找的汉字，则不处理（在swap函数里进行判断），若不是第一个，则将该汉字与前一个汉字在数组中的位置进行交换,并输出查找成功和比较的次数；若没找到这个汉字，则输出查找不成功和查找的次数。并且注意跳过空格。void find()cout << "请输入查找的字们（每个字间输入空格）："<<endl;string b;getline(cin, b);int i;int size = 0;for (int j = 0; j < b.length(); j += 2)if (bj = ' ')

11、j-; continue;int judge = 0;for (i = 0; i <=listsize; i += 2)if (listArrayi = bj && listArrayi + 1 = bj + 1)judge = 1;swap(i);break;if (judge)cout<<"“" <<bj<<bj+1<<"”"<< " 查找成功 " << "查找次数为：" << i/2+1 <<

12、endl;elsecout << "“" << bj << bj + 1 << "”" << " 查找失败 " << "查找次数为：" << i / 2 << endl;转置：若果查找成功，则进行转置，因为中文占两个字符，所以需要将两个字符转置。如果需要转置的中午是开头，就不需要转置直接返回true。bool swap(int n)if (n <= 1)return true;Elem temp;temp = li

13、stArrayn;listArrayn = listArrayn - 2;listArrayn - 2 = temp;temp = listArrayn+1;listArrayn + 1 = listArrayn - 1;listArrayn - 1 = temp;return 0; 3.算法时空分析 n个汉字，查找n次，时间复杂度为O（n）。4. 输入输出格式输入 请输入文字（文字间可输入空格）：cout << "请输入文字（文字间可输入空格）：" << endl;string a;getline(cin, a);/可输入空格请输入查找的字们（中间

14、用空格隔开）：cout << "请输入查找的字们（每个字间输入空格）："<<endl;string b;getline(cin, b);输出查找成功，显示查找次数：if (judge)cout<<"“" <<bj<<bj+1<<"”"<< " 查找成功 " << "查找次数为：" << i/2+1 <<endl;查找失败，显示查找次数：elsecout << &qu

15、ot;“" << bj << bj + 1 << "”" << " 查找失败 " << "查找次数为：" << i / 2 << endl;4 测试结果测试1测试2测试3测试4测试55 实验心得书上顺序表定义完整，题目难度不大，较前几次试验，比较简单。六附录#include <fstream>#include<string>#include"iostream"using namespace std;

16、#define Elem charclass AListprivate:int listsize;int maxsize;int fence;Elem* listArray;public:AList(int size)maxsize = size;fence = listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setEnd() fence = listsize; void prev() if (fence != 0) fence-; void next

17、() if (fence <= listsize)fence+;bool getValue(Elem& it) const it = listArrayfence;return true;bool insert(Elem item) if (listsize = maxsize) return false;for (int i = listsize; i > fence; i-)listArrayi = listArrayi - 1;listArrayfence = item; listsize+;return true;bool append(Elem& item

18、)if (listsize = maxsize)return false;listArraylistsize+ = item;return true;bool star()cout << "请输入文字（文字间可输入空格）：" << endl;string a;getline(cin, a);/可输入空格for (int i = 0; i < a.length(); i+)if (ai = ' ')continue;listArraylistsize = ai;listsize+;maxsize = listsize;return

19、 true;void find()cout << "请输入查找的字们（每个字间输入空格）："<<endl;string b;getline(cin, b);int i;int size = 0;for (int j = 0; j < b.length(); j += 2)if (bj = ' ')j-; continue;int judge = 0;for (i = 0; i <=listsize; i += 2)if (listArrayi = bj && listArrayi + 1 = bj + 1)j