《数据结构与程序设计(22)chapter09 表与数据访问》由会员分享，可在线阅读，更多相关《数据结构与程序设计(22)chapter09 表与数据访问（31页珍藏版）》请在金锄头文库上搜索。
1、8/3/2024数据结构与程序设计 1Chapter 9 TABLES AND INFORMATION RETRIEVALChapter 9 TABLES AND INFORMATION RETRIEVALn第七章内容回顾：第七章内容回顾：List的查找方法的查找方法n顺序查找顺序查找n二分法查找二分法查找n第九章内容介绍：第九章内容介绍：Table的数据访问的数据访问nTable是一种抽象数据结构，和是一种抽象数据结构，和List一样可以用来存储数据。一样可以用来存储数据。nTable的特点是：对它的数据访问时间只需要的特点是：对它的数据访问时间只需要O(1).nBoth table loo
2、kup and searching algorithms provide functions from a set of keys or indices to locations in a list or array.n数组是表这种抽象数据类型的一种实现方式，本章数组是表这种抽象数据类型的一种实现方式，本章将介绍一些特殊的数组，讨论表的访问方式。将介绍一些特殊的数组，讨论表的访问方式。8/3/2024数据结构与程序设计 2n n一维数组的示例一维数组的示例一维数组一维数组8/3/2024数据结构与程序设计 3一维数组的特点n n连续存储的线性聚集（别名连续存储的线性聚集（别名连续存储的线性聚集
3、（别名连续存储的线性聚集（别名 向量向量向量向量）n n除第一个元素外，其他每一个元素有一个且仅有一个直除第一个元素外，其他每一个元素有一个且仅有一个直除第一个元素外，其他每一个元素有一个且仅有一个直除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。接前驱。接前驱。接前驱。n n除最后一个元素外，其他每一个元素有一个且仅有一个除最后一个元素外，其他每一个元素有一个且仅有一个除最后一个元素外，其他每一个元素有一个且仅有一个除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。直接后继。直接后继。直接后继。8/3/2024数据结构与程序设计 4数组的连续存储方式n n一维数组地址公式一维
4、数组地址公式 8/3/2024数据结构与程序设计 5二维数组二维数组anm地址公式地址公式 行优先行优先 LOC ( j, k ) =a+( j * m + k)*l8/3/2024数据结构与程序设计 69.3 特殊的二维数组n下面介绍一些特殊的二维数组n上（下）三角数组n锯齿数组n反转表格8/3/2024数据结构与程序设计 79.3.1下三角矩阵下三角矩阵 BOOK P384 FIGURE 9.38/3/2024数据结构与程序设计 8下三角矩阵下三角矩阵行优先存储时：下标行优先存储时：下标行优先存储时：下标行优先存储时：下标i i，j j的存储位置函数：的存储位置函数：的存储位置函数：的存储
5、位置函数： LOC LOC ( ( i, j i, j ) =a+( ) =a+( i * (i+1)/2 + j)*li * (i+1)/2 + j)*l8/3/2024数据结构与程序设计 9上三角矩阵上三角矩阵 BOOK P384 FIGURE 9.38/3/2024数据结构与程序设计 10上三角矩阵上三角矩阵按照行优先存储，下标按照行优先存储，下标i，j的位置函数：的位置函数：LOC ( i, j )= a +(j-i+1/2*i*(n+(n-(i-1)*l= a +( j-i+1/2*i*(2n-i+1)*l8/3/2024数据结构与程序设计 119.3.2 Jagged Array
6、锯齿数组引入访问数组，用它存储锯齿数组每一行开始的引入访问数组，用它存储锯齿数组每一行开始的位置，这样可以保证一次访问到指定的下标。位置，这样可以保证一次访问到指定的下标。8/3/2024数据结构与程序设计 129.3.3Inverted Tables（反转表格）（反转表格）nBOOK P387 FIGURE 9.68/3/2024数据结构与程序设计 13Binary Search引入访问表，引入访问表，存储每一个主存储每一个主键的排序，这键的排序，这样可以加快查样可以加快查找的速度。找的速度。8/3/2024数据结构与程序设计 149.5 Radix sort 基数排序基数排序n基数排序的思
7、想：基数排序的思想：n假设待排序的集合有假设待排序的集合有n个记录个记录F=(R0，R1，Rn-1)，记录记录Ri的排序码的排序码ki含有含有d部分部分(ki0, ki1, kid-1)，nN个记录对排序码有序是指个记录对排序码有序是指 任意两个记录任意两个记录Ri和和Rj(0ijn-1)满足词典次序有序关系：满足词典次序有序关系： (ki0, ki1, kid-1) (c,a,r)。8/3/2024数据结构与程序设计 159.5 Radix sort 基数排序基数排序n基数排序的思想：基数排序的思想：n第一种是第一种是高位优先法：高位优先法：先对最高位排序码先对最高位排序码k k0 0排序，
8、排序，将所有记录分成若干堆，每堆中的记录都具有相将所有记录分成若干堆，每堆中的记录都具有相同的同的k k0 0，然后分别就每堆对排序码，然后分别就每堆对排序码k k1 1排序，分成若排序，分成若干子堆，如此重复，直到对干子堆，如此重复，直到对k kd-1d-1排序，最后将各堆排序，最后将各堆按次序叠在一起成为一个有序序列。按次序叠在一起成为一个有序序列。n第二种是第二种是低位优先法低位优先法：从最低位排序码：从最低位排序码k kd-1d-1起排序，起排序，然后再对高一位排序码然后再对高一位排序码k kd-2d-2排序，如此重复，直到排序，如此重复，直到对对K K0 0排序后便成为一个有序序列。
9、排序后便成为一个有序序列。8/3/2024数据结构与程序设计 16基数排序例题8/3/2024数据结构与程序设计 17练习n初始序列为36，5，16，98，95，47，32，36，48，10n请写出基数排序的过程。8/3/2024数据结构与程序设计 18基数排序实现方法讨论8/3/2024数据结构与程序设计 19Radix sort-keyn#include String.hnconst int key_size = 10;nclass Key nchar strkey_size;npublic:nKey (char s);nchar * the_key( ) const;n;8/3/2024
10、数据结构与程序设计 20Radix sort-keyn#include Key.hnKey:Key(char s)nfor(int i=0; i=strlen(s); i+)nstri=si;nnchar * Key:the_key() constnreturn (char *)str;n8/3/2024数据结构与程序设计 21Radix sort-Recordn#include Key.hn#include iostream.hnclass Recordnpublic:noperator Key( ); / implicit conversion from Record to Key .nR
11、ecord(char s=);nchar * the_key() const;nchar key_letter(int position) const;nprivate:nchar strkey_size;n;nostream & operator (ostream &output, Record &x);8/3/2024数据结构与程序设计 22Radix sort-RecordnRecord:Record(char s)nfor(int i=0; i=strlen(s); i+)nstri=si;nnRecord:operator Key( )nKey tmp(str);n8/3/2024数
12、据结构与程序设计 23Radix sort-Recordnchar Record:key_letter(int position) constnif(positionstrlen(str) return strposition;nelse return 0;nnchar * Record:the_key() constnreturn (char *)str;n8/3/2024数据结构与程序设计 24Radix sort-Sortable_listnconst int max_chars = 28;nclass Sortable_list: public List npublic: / Add
13、prototypes for sorting methods here.n/for radix_sort( );nvoid radix_sort( );nprivate: / Add prototypes for auxiliary functions here.n/for radix_sort( );nvoid rethread(MyQueue queues);n;nint alphabetic_order(char c);8/3/2024数据结构与程序设计 25nvoid Sortable_list : radix_sort( )n/* Post: The entries of the S
14、ortable list have been sorted so all their keys are innalphabetical order.nUses: Methods from classesList ,Queue , and Record ;nfunctions position and rethread . */nnRecord data;nMyQueue queuesmax_chars;nfor (int position = key_size - 1; position = 0; position-) n/ Loop from the least to the most si
15、gnificant position.nwhile (remove(0, data) = success) n int queue_number = alphabetic_order(data.key_letter(position);nqueuesqueue_number.append(data); / Queue operation.n nrethread(queues); / Reassemble the list.n n8/3/2024数据结构与程序设计 26int alphabetic_order(char c)/* Post: The function returns the al
16、phabetic position of character c , or it returns 0if the character is blank. */if (c = | c = 0) return 0;if (a = c & c = z) return c - a + 1;if (A = c & c = Z) return c - A + 1;return 27;8/3/2024数据结构与程序设计 27void Sortable_list : rethread(MyQueue queues)/* Post: All the queues are combined back to the
17、 Sortable list , leaving all thequeues empty.Uses: Methods of classes List , and Queue . */Record data;for (int i = 0; i max_chars; i+)while (!queuesi.empty( ) queuesi.retrieve(data);insert(size( ), data);queuesi.serve( ); 8/3/2024数据结构与程序设计 28outputntemplate nvoid print(List_entry &x)ncoutx;nnostrea
18、m & operator (ostream &output, Record &x)nnoutputx.the_key();noutput ;nreturn output;n8/3/2024数据结构与程序设计 29Radix sort-Mainnvoid main()nSortable_list mylist;nmylist.insert(0,Record(rat);nmylist.insert(1,Record(mop);nmylist.insert(2,Record(cat);nmylist.insert(3,Record(map);nmylist.insert(4,Record(car);
19、nmylist.insert(5,Record(top);nmylist.insert(6,Record(cot);nmylist.insert(7,Record(tar);nmylist.insert(8,Record(rap);ncoutThe list is: endl;nmylist.traverse(print);ncoutendlUse radix_sort Method:endl; mylist.radix_sort();nmylist.traverse(print);ncin.get();n8/3/2024数据结构与程序设计 30ResultnThe list is:nrat mop cat map car top cot tar rapnUse radix_sort Method:ncar cat cot map mop rap rat tar top8/3/2024数据结构与程序设计 31Radix sortn目录目录Sortable_list_Radix下例程下例程
