快速排序和散列表,数据结构实验报告

1、数据结构实验报告HUNAN UNIVERSITY数据结构实验报告题 目： 散列表和快速排序 学生姓名 学生学号 专业班级 指导老师 夏艳 日 期 2016.05.24 实验7 快速排序背景 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。排序算法是计算机科学中最重要的研究问题之一。对于排序

2、的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。例1：有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支票的号码对支票排序；例2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。例3：在一个由n个数构成的集合上，求集合中第i小/大的数。例4：对一个含有n个元数的集合，求解中位数、k分位数。问题描述 在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要

3、一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。基本要求（1）数据的输入输出格式：输入：第一行是一个整数n，代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间。输出：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要

4、处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。（2）使用快速排序，轴值采用随机数确定。测试数据输入95 3 4 2 6 1 5 7 3输出123345567实验提示（1）将n个正整数排序后依次输出即可。（2）需调用srand()，才能让每次的随机数不一样。选做内容若采用并行操作系统，一次可同时处理两件任务，求让所有任务等待的时间和最小的任务处理顺序。课后题目给出一个能列出某一集合的k分位数的O(nlogk)的算法。一、需求分析本程序需要利用数组来存放操作数，需要一个比较关键码大小的函数和一个交换顺序的函数，和进行快排操作的快排函数。测试用例输入95 3 4 2 6 1 5 7

5、 3输出123345567二、概要设计抽象数据类型抽象数据类型算法的实质是对一个数组存储数据的关键码进行一个排序操作，任何一种排序算法都可以达到同样的效果，只不过是时间代价不一样，我们需要用时间开销相对较少的快速排序函数堆元素关键码进行排序；算法的基本思想1.利用随机数产生轴值。为保证轴值在相应的范围内可采用：rand()%(j-i+1)+i 进行处理，那么返回的结果就在i到j之间。2.将轴值的位置的数与末尾的数进行互换。3.进行数据的调整，l从左边开始，找到第一个比轴值处数大的元素，然后让r从右边开始找到第一个比轴值处数小的元素，将l和r对应的这两个数进行互换。如此进行，直到l >=

6、r。最后返回l的值，作为将轴值正确归位的下标索引。4.按照上述函数返回的索引交换l和末尾的数（轴值归位），则l左边的数比轴值小，右边的数比轴值大。5.l将整个数组分为左右两部分，两边再进行同样的快排操作。三、程序的流程：程序由三个模块组成：输入模块：读入任务数n，和每件任务所花的时间，存放在数组里面。处理模块：进行快排操作。输出模块：将排好序的数据输出。四、详细设计：物理数据类型bool comp(int a,int b) /比较函数，如果排序的关键码a >则返回，否则返回。void swap(int *a,int i,int j)/交换函数int findpivot(int i,int

7、 j) /在排序关键码范围内随机选取轴值int partition(int Array,int left,int right,int pivot)/将记录移动到合适的分组void qsort(int Array,int i,int j)/快排函数算法的时空分析快速排序算法在最差情况下算法时间开销并不比冒泡排序小，最佳情况则为，（）平均时间代价为（）)。四、调试分析本算法很好理解，就是通过递归将数据按照和轴值比较的结果分为大于轴值和小于轴值的两部分，在对这两部分按同样的方法递归到数组有序；五、测试结果实验8 散列表背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key valu

8、e)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了.

9、）。通过书名，来查询它是否存在。为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。基本要求（1） 根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。（2）数据的输入输出格式： 输入分为两部分第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存在的图书记录。第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查询的图书记录。输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。测试数据 输入： 4aans

10、andhellocpp 9aban as ans and ande hellocbb hellocpp 输出： YES NO NO NO YES YES NO NO YES实验提示（1）冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。（2）BKDE 字符串哈希unsigned int hash_BKDE(char *str) /* 初始种子seed 可取31 131 1313 13131 131313 etc. */ unsigned int seed = 131; unsigned int hash = 0; while (*str) hash = hash * seed + (*s

11、tr+); return (hash & 0x7FFFFFFF); 将字符串哈希到小于231的整数t，再将t用随机数哈希法映射到215以内的数。选做内容每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，采用折叠法构造一个四位数的哈希函数。课后题目实现文本LZW压缩和解压缩。一、需求分析1.本程序要求利用散列表存储和查找图书，查找成功则输出YES，否则输出NO。2.本程序使用给定的一个散列函数BKDE首先将字符串哈希到小于231的整数t散列地址，然后通过随机散列函数hash_rand将上述地址t再次哈希到2

12、15范围，我使用了取余法映射到了32768（215），虽然有点大，但是好像题目是这样要求的，不会是我理解错了吧 -；3.遇到冲突处理方法为：从发生冲突的地址顺次循环后移到下一个位置，寻找空位插入；4.搜索也是使用上述两个哈希映射找到对应地址，查看地址处的图书关键码是否是需要查找的图书关键码，如果不是则从那个地址往下搜索到一个匹配的关键码即可。测试用例输入： 4aans andhellocpp 9aban as ans and ande hellocbb hellocpp 输出： YES NO NO NO YES YES NO NO YES二、概要设计抽象数据类型1、抽象数据类型为实现数据的快速

13、查找功能，需要用散列表存储数据，并且将映射函数以及冲突处理方法作为查找的函数和方法；散列表的映射使用了给定的BKDE函数和用取余法映射的随机映射函数；主函数通过HashingLisst类的insert函数插入一个新元素，通过find函数查找需要查找的元素，没有找到返回NO,找到则返回YES.算法的基本思想通过编写两个映射函数来确定存储数据的地址，函数BKDE为实验要求给出，随机映射函数为自己选择合适的映射方法写出，散列表使用数组来实现吗，冲突解决机制为往后搜索一个空位置直接插入。三、程序的流程：程序由三个模块组成：（1）输入模块：通过键盘输入图书名存储图书，通过键盘输入图书名来查找图书；（2）

14、功能模块：存储图书调用insert函数，检索调用find函数；（3）输出模块：查找到相应图书则输出YES，否则输出NO。四、详细设计：物理数据类型unsigned int hash_BKDE(char *str)/散列函数unsigned int hash_rand(unsigned int value)/随机散列函数class HashingList/散列表类void HashingList:insert(char *str)/散列表类的插入数据成员函数bool HashingList:find(char *str)/ 散列表类的检索数据成员函数算法的时空分析如果不发生冲突，散列表的插入和查

15、找是通过映射直接找得到，如果发生冲突，也能快速从冲突位置向下检索得到，除非散列表里没有该元素则会检索到散列表尾部，时间代价跟散列表的均匀冲突程度有关，所以算法时间代价为（1)。四、调试分析本算法并没有什么特别难理解的地方，是很简单的一个算法，主要是理解散列表的检索机制。五、测试结果七、附录程序源代码（c+）快速排序/*快速排序*/#include<iostream>#include<time.h>using namespace std;bool comp(int a,int b) /比较函数 return a > b;void swap(int *a,int i,

16、int j)/交换函数 int temp; temp = ai; ai = aj; aj = temp;int findpivot(int i,int j) /随机产生轴值 srand(time(NULL); return rand()%(j-i+1)+i; int partition(int Array,int left,int right,int pivot)/将记录移动到合适的分组 dowhile( comp(pivot,Array+left) );/不断向后移动直到找到第一个大于pivot while( (left < right ) && comp(Array-

17、right,pivot) );/不断向前移动直到找到第一个小于pivot swap(Array,left,right);while(left < right); return left; /返回右分组的第一个位置void qsort(int Array,int i,int j)/快排函数 if(j <= i) return ; int pivotindex = findpivot(i,j); /找到轴值 swap(Array,pivotindex,j);/将轴值移到数组最后 int k = partition(Array ,i-1,j,Arrayj); /返回分组后的右边第一个位置

18、 swap(Array,k,j);/将轴值放到数组分组右边的第一个位置 qsort(Array,i,k-1);/对左半部分继续快排qsort(Array,k+1,j);/对右半部分继续快排int main()int i,n;cin >> n;int *Array = new int n;for(i = 0;i<n;i+) cin >> Arrayi;qsort(Array,0,n-1);for(i = 0;i < n;i+)cout << Arrayi << endl;return 0;散列表/*散列表*/#include<io

19、stream>#include<ctime> using namespace std;const int MAX = 32768;/散列表最大长度const int NAMESIZE = 100;/书名长度unsigned int hash_BKDE(char *str)/散列函数 unsigned int seed = 131; unsigned int hash = 0; while (*str) hash = hash * seed + (*str+); return (hash & 0x7FFFFFFF); unsigned int hash_rand(uns

20、igned int value)/随机散列函数 unsigned int address = value % MAX;/取余法将地址映射到MAX(215）内return address; unsigned int Hash(char *str)/生成通过BKDE散列函数和hash_rand随机散列函数的映射地址； return hash_rand(hash_BKDE(str); class HashingList/散列表类private: char* Array;/散列表数组int ArraySize;/散列表长度public: HashingList(); HashingList(); vo

21、id insert(char*); bool find(char*);HashingList:HashingList()/构造函数里初始化散列表 ArraySize =MAX; Array = new char* ArraySize; for(int i = 0;i < ArraySize;i+) Arrayi = new charNAMESIZE; Arrayi = NULL; HashingList:HashingList() void HashingList:insert(char *str)/插入一个数据 unsigned int pos = Hash(str); while(Arraypos != NULL)/往后寻找空位置插入 pos+; Arraypos = str; bool HashingList:find(char *str)/搜索函数，找到关键码 unsigned int pos = Hash(str); while(Arraypos != NULL) if(Arraypos = str) return t