数据结构与程序设计王丽苹22chapter09表与数据访问

1、10/21/2021数据结构与程序设计 1数据结构与程序设计数据结构与程序设计(22)(22)chapter09 table chapter09 table 王丽苹 10/21/2021数据结构与程序设计 2chapter 9 tables and information retrievalchapter 9 tables and information retrievaln第七章内容回顾：第七章内容回顾：list的查找方法的查找方法n顺序查找顺序查找n二分法查找二分法查找n第九章内容介绍：第九章内容介绍：table的数据访问的数据访问ntable是一种抽象数据结构，和是一种抽象数据结构，和l

2、ist一样可以用来存储数据。一样可以用来存储数据。ntable的特点是：对它的数据访问时间只需要的特点是：对它的数据访问时间只需要o(1).nboth table lookup and searching algorithms provide functions from a set of keys or indices to locations in a list or array.n数组是表这种抽象数据类型的一种实现方式，本章数组是表这种抽象数据类型的一种实现方式，本章将介绍一些特殊的数组，讨论表的访问方式。将介绍一些特殊的数组，讨论表的访问方式。10/21/2021数据结构与程序设计 3

3、10/21/2021数据结构与程序设计 410/21/2021数据结构与程序设计 5 iloc ii, ,0 0 ( ( ) )+ +i i* *l l, ,0 0 10/21/2021数据结构与程序设计 611211101122212021121110110201000mnanananamaaaamaaaamaaaaa10/21/2021数据结构与程序设计 79.3 特殊的二维数组n下面介绍一些特殊的二维数组n上（下）三角数组n锯齿数组n反转表格10/21/2021数据结构与程序设计 89.3.1下三角矩阵下三角矩阵 book p384 figure 9.3a0,0 c c c c a1,0

4、 a1,1 c c an-2,0 an-2,n-2 c an-1,0 an-1,1 an-1,n-1 下三角矩阵 10/21/2021数据结构与程序设计 9下三角矩阵下三角矩阵10/21/2021数据结构与程序设计 10上三角矩阵上三角矩阵 book p384 figure 9.3a0,0 a0,1 a0,n-1 c a1,1 a1,n-1 c c c c c an-1,n-1 上三角矩阵 10/21/2021数据结构与程序设计 11上三角矩阵上三角矩阵按照行优先存储，下标按照行优先存储，下标i，j的位置函数：的位置函数：loc ( i, j )= a +(j-i+1/2*i*(n+(n-(i

5、-1)*l= a +( j-i+1/2*i*(2n-i+1)*l10/21/2021数据结构与程序设计 129.3.2 jagged array 锯齿数组引入访问数组，用它存储锯齿数组每一行开始的引入访问数组，用它存储锯齿数组每一行开始的位置，这样可以保证一次访问到指定的下标。位置，这样可以保证一次访问到指定的下标。10/21/2021数据结构与程序设计 139.3.3inverted tables（反转表格）（反转表格）nbook p387 figure 9.610/21/2021数据结构与程序设计 14binary search引入访问表，引入访问表，存储每一个主存储每一个主键的排序，这键

6、的排序，这样可以加快查样可以加快查找的速度。找的速度。10/21/2021数据结构与程序设计 159.5 radix sort 基数排序基数排序n基数排序的思想：基数排序的思想：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)。10/21/2021数据结构与程序设计 169.5 r

7、adix sort 基数排序基数排序n基数排序的思想：基数排序的思想：n第一种是第一种是高位优先法：高位优先法：先对最高位排序码先对最高位排序码k k0 0排序，排序，将所有记录分成若干堆，每堆中的记录都具有相将所有记录分成若干堆，每堆中的记录都具有相同的同的k k0 0，然后分别就每堆对排序码，然后分别就每堆对排序码k k1 1排序，分成若排序，分成若干子堆，如此重复，直到对干子堆，如此重复，直到对k kd-1d-1排序，最后将各堆排序，最后将各堆按次序叠在一起成为一个有序序列。按次序叠在一起成为一个有序序列。n第二种是第二种是低位优先法低位优先法：从最低位排序码：从最低位排序码k kd-1

8、d-1起排序，起排序，然后再对高一位排序码然后再对高一位排序码k kd-2d-2排序，如此重复，直到排序，如此重复，直到对对k k0 0排序后便成为一个有序序列。排序后便成为一个有序序列。10/21/2021数据结构与程序设计 17基数排序例题10/21/2021数据结构与程序设计 18练习n初始序列为36，5，16，98，95，47，32，36，48，10n请写出基数排序的过程。10/21/2021数据结构与程序设计 19基数排序实现方法讨论10/21/2021数据结构与程序设计 20radix sort-keyn#include string.hnconst int key_size =

9、10;nclass key nchar strkey_size;npublic:nkey (char s);nchar * the_key( ) const;n;10/21/2021数据结构与程序设计 21radix 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;n10/21/2021数据结构与程序设计 22radix sort-recordn#include key.hn#include

10、iostream.hnclass recordnpublic:noperator key( ); / implicit conversion from record to key .nrecord(char s=);nchar * the_key() const;nchar key_letter(int position) const;nprivate:nchar strkey_size;n;nostream & operator (ostream &output, record &x);10/21/2021数据结构与程序设计 23radix sort-recordnrecord:record

11、(char s)nfor(int i=0; i=strlen(s); i+)nstri=si;nnrecord:operator key( )nkey tmp(str);n10/21/2021数据结构与程序设计 24radix sort-recordnchar record:key_letter(int position) constnif(positionstrlen(str) return strposition;nelse return 0;nnchar * record:the_key() constnreturn (char *)str;n10/21/2021数据结构与程序设计 25

12、radix sort-sortable_listnconst int max_chars = 28;nclass sortable_list: public list npublic: / add 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_

13、order(char c);10/21/2021数据结构与程序设计 26nvoid sortable_list : radix_sort( )n/* post: the entries of the sortable 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_ch

14、ars;nfor (int position = key_size - 1; position = 0; position-) n/ loop from the least to the most significant 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); / reasse

15、mble the list.n n10/21/2021数据结构与程序设计 27int alphabetic_order(char c)/* post: the function returns the alphabetic 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;10/21/2021

16、数据结构与程序设计 28void sortable_list : rethread(myqueue queues)/* post: all the queues are combined back to the 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(

17、 ), data);queuesi.serve( ); 10/21/2021数据结构与程序设计 29outputntemplate nvoid print(list_entry &x)ncoutx;nnostream & operator (ostream &output, record &x)nnoutputx.the_key();noutput ;nreturn output;n10/21/2021数据结构与程序设计 30radix 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);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);ncoutend