數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)(22)

Chapter09Table王麗蘋lipingwang@4/21/20231.Chapter9TABLESANDINFORMATIONRETRIEVAL

第七章內(nèi)容回顧：List的查找方法順序查找二分法查找第九章內(nèi)容介紹：Table的數(shù)據(jù)訪問(wèn)Table是一種抽象數(shù)據(jù)結(jié)構(gòu)，和List一樣可以用來(lái)存儲(chǔ)數(shù)據(jù)。Table的特點(diǎn)是：對(duì)它的數(shù)據(jù)訪問(wèn)時(shí)間只需要O(1).Bothtablelookupandsearchingalgorithmsprovidefunctionsfromasetofkeysorindicestolocationsinalistorarray.數(shù)組是表這種抽象數(shù)據(jù)類型的一種實(shí)現(xiàn)方式，本章將介紹一些特殊的數(shù)組，討論表的訪問(wèn)方式。4/21/20232.一維數(shù)組的示例一維數(shù)組4/21/20233.一維數(shù)組的特點(diǎn)連續(xù)存儲(chǔ)的線性聚集（別名向量）除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。4/21/20234.數(shù)組的連續(xù)存儲(chǔ)方式一維數(shù)組地址公式

4/21/20235.

二維數(shù)組a[n][m]地址公式行優(yōu)先LOC(j,k)=a+(j*m+k)*l4/21/20236.9.3特殊的二維數(shù)組下面介紹一些特殊的二維數(shù)組上（下）三角數(shù)組鋸齒數(shù)組反轉(zhuǎn)表格4/21/20

下三角矩陣BOOKP384FIGURE9.34/21/20238.下三角矩陣行優(yōu)先存儲(chǔ)時(shí)：下標(biāo)i，j的存儲(chǔ)位置函數(shù)：

LOC(i,j)=a+(i*(i+1)/2+j)*l4/21/20239.上三角矩陣BOOKP384FIGURE9.34/21/202310.上三角矩陣按照行優(yōu)先存儲(chǔ)，下標(biāo)i，j的位置函數(shù)：LOC(i,j)=a+(j-i+1/2*i*(n+(n-(i-1))))*l=a+(j-i+1/2*i*(2n-i+1))*l4/21/2023JaggedArray鋸齒數(shù)組引入訪問(wèn)數(shù)組，用它存儲(chǔ)鋸齒數(shù)組每一行開始的位置，這樣可以保證一次訪問(wèn)到指定的下標(biāo)。4/21/2023

InvertedTables（反轉(zhuǎn)表格）BOOKP387FIGURE9.64/21/202313.BinarySearch引入訪問(wèn)表，存儲(chǔ)每一個(gè)主鍵的排序，這樣可以加快查找的速度。4/21/202314.9.5Radixsort基數(shù)排序基數(shù)排序的思想：假設(shè)待排序的集合有n個(gè)記錄F=(R0，R1，…Rn-1)，

記錄Ri的排序碼ki含有d部分(ki0,ki1,…,kid-1)，N個(gè)記錄對(duì)排序碼有序是指∶任意兩個(gè)記錄Ri和Rj(0≤i≤j≤n-1)滿足詞典次序有序關(guān)系：

(ki0,ki1,…,kid-1)<(kj0,kj1,…,kjd-1)

其中k0稱為最高位排序碼，kd-1稱為最低位排序碼。例如關(guān)鍵碼dog和car分別包含(d,o,g)>(c,a,r)。4/21/202315.9.5Radixsort基數(shù)排序基數(shù)排序的思想：第一種是高位優(yōu)先法：先對(duì)最高位排序碼k0排序，將所有記錄分成若干堆，每堆中的記錄都具有相同的k0，然后分別就每堆對(duì)排序碼k1排序，分成若干子堆，如此重復(fù)，直到對(duì)kd-1排序，最后將各堆按次序疊在一起成為一個(gè)有序序列。第二種是低位優(yōu)先法：從最低位排序碼kd-1起排序，然后再對(duì)高一位排序碼kd-2排序，如此重復(fù)，直到對(duì)K0排序后便成為一個(gè)有序序列。4/21/202316.基數(shù)排序例題4/21/202317.練習(xí)初始序列為36，5，16，98，95，47，32，36’，48，10請(qǐng)寫出基數(shù)排序的過(guò)程。4/21/202318.基數(shù)排序?qū)崿F(xiàn)方法討論4/21/202319.Radixsort--key#include"String.h"constintkey_size=10;classKey{ charstr[key_size];public: Key(chars[]); char*the_key()const;};4/21/202320.Radixsort--key#include"Key.h"Key::Key(chars[]){ for(inti=0;i<=strlen(s);i++) str[i]=s[i];}char*Key::the_key()const{ return(char*)str;}4/21/202321.Radixsort--Record#include"Key.h"#include"iostream.h"classRecord{public: operatorKey();//implicitconversionfromRecordtoKey. Record(chars[]=""); char*the_key()const; charkey_letter(intposition)const;private: charstr[key_size];};ostream&operator<<(ostream&output,Record&x);4/21/202322.Radixsort--RecordRecord::Record(chars[]){ for(inti=0;i<=strlen(s);i++) str[i]=s[i];}Record::operatorKey(){ Keytmp(str);}4/21/202323.Radixsort--RecordcharRecord::key_letter(intposition)const{ if(position<strlen(str))returnstr[position]; elsereturn'\0';}char*Record::the_key()const{ return(char*)str;}4/21/202324.Radixsort--Sortable_listconstintmax_chars=28;classSortable_list:publicList<Record>{public://Addprototypesforsortingmethodshere. //forradix_sort(); voidradix_sort();private://Addprototypesforauxiliaryfunctionshere. //forradix_sort(); voidrethread(MyQueue<Record>queues[]);};intalphabetic_order(charc);4/21/202325.voidSortable_list::radix_sort()/*Post:TheentriesoftheSortablelisthavebeensortedsoalltheirkeysareinalphabeticalorder.Uses:MethodsfromclassesList,Queue,andRecord;functionspositionandrethread.*/{ Recorddata; MyQueue<Record>queues[max_chars]; for(intposition=key_size-1;position>=0;position--){ //Loopfromtheleasttothemostsignificantposition. while(remove(0,data)==success){ intqueue_number=alphabetic_order(data.key_letter(position)); queues[queue_number].append(data);//Queueoperation. } rethread(queues);//Reassemblethelist. }}4/21/202326.intalphabetic_order(charc)/*Post:Thefunctionreturnsthealphabeticpositionofcharacterc,oritreturns0ifthecharacterisblank.*/{ if(c==''||c=='\0')return0; if('a'<=c&&c<='z')returnc-'a'+1; if('A'<=c&&c<='Z')returnc-'A'+1; return27;}4/21/202327.voidSortable_list::rethread(MyQueue<Record>queues[])/*Post:AllthequeuesarecombinedbacktotheSortablelist,leavingallthequeuesempty.Uses:MethodsofclassesList,andQueue.*/{ Recorddata; for(inti=0;i<max_chars;i++) while(!queues[i].empty()){ queues[i].retrieve(data); insert(size(),data); queues[i].serve(); }}4/21/202328.outputtemplate<classList_entry>voidprint(List_entry&x){ cout<<x; }ostream&operator<<(ostream&output,Record&x){ output<<x.the_key(); output<<""; returnoutput;}4/21/202329.Radixsort--Mainvoidmain(){ Sortable_listmylist; mylist.insert(0,Record("rat")); mylist.insert(1,Record("mop")); mylist.insert(2,Record("cat")); mylist.insert(3,Record("map")); mylist.insert(4,Record("car")); mylist.insert(5,Record("top")); mylist.insert(6,Record("cot")); mylist.insert(7,Record("tar")); mylist.insert(8,Record("rap")); cout<<"Thelistis:"<<endl; mylist.traverse(print); cout<<endl<<"Useradix_sortMethod:"<<endl;