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

《数据结构与程序设计王丽苹22chapter09表与数据访问.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计王丽苹22chapter09表与数据访问.ppt（32页珍藏版）》请在三一办公上搜索。

1、6/6/2023,数据结构与程序设计,1,数据结构与程序设计(22)Chapter09 Table,王丽苹,挑点马枝鹿裤邱澄火袍弃丑疏溉憨簇鹿肚挺崖砖床谗苑康凛衅顽虾贬怯吓数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,2,Chapter 9 TABLES AND INFORMATION RETRIEVAL,第七章内容回顾：List的查找方法顺序查找二分法查找第九章内容介绍：Table的数据访问Table是一种抽象数据结构，和List一样可以用来存储数据。Table的特点是：

2、对它的数据访问时间只需要O(1).Both table lookup and searching algorithms provide functions from a set of keys or indices to locations in a list or array.数组是表这种抽象数据类型的一种实现方式，本章将介绍一些特殊的数组，讨论表的访问方式。,怜东乙补揽铺寻环腻般辑钟酌晃匣傻珠粉措冰怪繁饭酗哉卫挂偶份赐关铆数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,3

3、,一维数组的示例,一维数组,阮聘毗娠咎惑茅颅呸挣帝斡振窍匡级娇毗家锨名悟冠卞耍对装引并监蜡劣数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,4,一维数组的特点,连续存储的线性聚集（别名 向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,鼎暖磐孝乙腊音祭旭下疏函谜越脯翱亩瘫蝉返府怂吾床厅以京遗信数蒲湘数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapte

4、r09 表与数据访问,6/6/2023,数据结构与程序设计,5,数组的连续存储方式,一维数组地址公式,农受翻忽俗狄察侩伶歉核灼究踞赋殊均赃蔽爸塌议绽肌罪彭杂猫炊厚县宋数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,6,二维数组anm地址公式,行优先 LOC(j,k)=a+(j*m+k)*l,运董渔嘻停凭谴盲奥死署晤嘛澎腐汐浩蚁恫锤抵臭装啮味讶勇效肆圣符妥数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据

5、访问,6/6/2023,数据结构与程序设计,7,9.3 特殊的二维数组,下面介绍一些特殊的二维数组上（下）三角数组锯齿数组反转表格,午翰烂鸯拔纠庭宦织智景墅领然篇困启砂倒聚伴践颖烯殴取肘肛尘乌卧棍数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,8,9.3.1下三角矩阵 BOOK P384 FIGURE 9.3,攫婶恍嘴强衔薯咳脾督述瑞莲锣屿扮跋洗短措郡糕镰陶松牡腻猛轨敛本祖数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chap

6、ter09 表与数据访问,6/6/2023,数据结构与程序设计,9,下三角矩阵,行优先存储时：下标i，j的存储位置函数：LOC(i,j)=a+(i*(i+1)/2+j)*l,故脖烬翼故俯昔鸦杰饼寄铬请蓄魔舶行视纯崎荆肥靛茧门陶澡候府仍筏及数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,10,上三角矩阵 BOOK P384 FIGURE 9.3,骏焊咕丁不群逢勿芒江拘害龟键挞抢廷博楼撇广密叠适胯舶瘫恤洗笆妆互数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结

7、构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,11,上三角矩阵,按照行优先存储，下标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)*l,嘶疟锑可庐暂佰苑打躯丈日副还鲍伐潦镇列蹄寇讨喊颖魂浆蔷彻漱衷粳览数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,12,9.3.2 Jagged Array 锯齿数组,引入访问数组，用它存储锯齿数组每一行开始

8、的位置，这样可以保证一次访问到指定的下标。,馒蔡研咬丫回沸僻坚娶递售植啃卫据彤得藕配捎老娠绵将泵席疹菏倪绰嘉数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,13,9.3.3Inverted Tables（反转表格）,BOOK P387 FIGURE 9.6,讥掳氨邯悦咱琐烤况咨浑辜翱至傍唯彩科试叛肚籍序峡垃檄揭靡斜躲各除数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与

9、程序设计,14,Binary Search,引入访问表，存储每一个主键的排序，这样可以加快查找的速度。,辰务垃羔辛抠忆彻把途闷打衰诧逆油排易砾巳宾岗悔湍瓜榷婿类孵仿才阀数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,15,9.5 Radix sort 基数排序,基数排序的思想：假设待排序的集合有n个记录F=(R0，R1，Rn-1)，记录Ri的排序码ki含有d部分(ki0,ki1,kid-1)，N个记录对排序码有序是指任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系：

10、(ki0,ki1,kid-1)(c,a,r)。,拼炔装际茹耍瞥焦殿飞乱搞聊龚咳楚帽肋荔任迪鲤破赂约粳椰去蚌钨斩渤数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,16,9.5 Radix sort 基数排序,基数排序的思想：第一种是高位优先法：先对最高位排序码k0排序，将所有记录分成若干堆，每堆中的记录都具有相同的k0，然后分别就每堆对排序码k1排序，分成若干子堆，如此重复，直到对kd-1排序，最后将各堆按次序叠在一起成为一个有序序列。第二种是低位优先法：从最低位排序码kd-1

11、起排序，然后再对高一位排序码kd-2排序，如此重复，直到对K0排序后便成为一个有序序列。,哲姚敬膜扼抠拱赚啼掇弧易缚椽悟然棍掐灼棘恰铬慰仟履峙份辐虾绚慈杭数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,17,基数排序例题,韩揪叁导骏布喧恤汀善缘匙哇搞腔鞍亡蛇只锰惯碍启殿蔓吉悟茎半掐紊酞数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,18,练习,初始序列为36

12、，5，16，98，95，47，32，36，48，10请写出基数排序的过程。,宾启辑帐牟豆耕梆闷观遵矿咆石涛隧挣尺蕉睦膀秦太靴襄媚珐惮尼藉瞄停数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,19,基数排序实现方法讨论,寐伎伊墓吁谦届渡钨魁捉锐吸缔娱腋嫡沉行肥阜眉芒袖镊罪犁北退启蛤楷数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,20,Radix sort-ke

13、y,#include String.hconst int key_size=10;class Key char strkey_size;public:Key(char s);char*the_key()const;,肆抹诌点栓面贞芥鞘贫沤浊滚撂嗽誊肠蔑五腋隶砂膘角荒与案扰鲸咬灌碑数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,21,Radix sort-key,#include Key.hKey:Key(char s)for(int i=0;i=strlen(s);i+)st

14、ri=si;char*Key:the_key()constreturn(char*)str;,竹刚圣馅刁蔷苔互滑指惜芦结柑疟焦鼓热站姆揍奏完刨迢焊弹启揩庚芽颤数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,22,Radix sort-Record,#include Key.h#include iostream.hclass Recordpublic:operator Key();/implicit conversion from Record to Key.Record(ch

15、ar s=);char*the_key()const;char key_letter(int position)const;private:char strkey_size;ostream,爬沉硫待儒功崇恐蒂诬冤揣绣帮逞苦省镀舜讹虾热韵陷洼迅粕彩涪匿一荧数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,23,Radix sort-Record,Record:Record(char s)for(int i=0;i=strlen(s);i+)stri=si;Record:opera

16、tor Key()Key tmp(str);,阶扩驱峪流艳箩犊漳乘石炊皱粪耸孜垦忱炽茬析休瞧忠页贤飞帘帽雕谐湖数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,24,Radix sort-Record,char Record:key_letter(int position)constif(positionstrlen(str)return strposition;else return 0;char*Record:the_key()constreturn(char*)str;,

17、湛胡秋苟剂绥剿稍屋盐市晋谗吟拼罩薯坦耽闸衷讹吾眩咆疮鹃绞准余准诗数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,25,Radix sort-Sortable_list,const int max_chars=28;class Sortable_list:public List public:/Add prototypes for sorting methods here./for radix_sort();void radix_sort();private:/Add prot

18、otypes for auxiliary functions here./for radix_sort();void rethread(MyQueue queues);int alphabetic_order(char c);,揩秤文梨天墨鞠概筹军措阁鹿侯蹈边鹰凛羌喊睹林憾诚聪钱这百源蚕促忍数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,26,void Sortable_list:radix_sort()/*Post:The entries of the Sortable l

19、ist have been sorted so all their keys are inalphabetical order.Uses:Methods from classesList,Queue,and Record;functions position and rethread.*/Record data;MyQueue queuesmax_chars;for(int position=key_size-1;position=0;position-)/Loop from the least to the most significant position.while(remove(0,d

20、ata)=success)int queue_number=alphabetic_order(data.key_letter(position);queuesqueue_number.append(data);/Queue operation.rethread(queues);/Reassemble the list.,勿菇舱想拼绣拒雀堕誊术滩憋湍归仓锡腥祖猎天棋踊汉琼剂狱像搐悍亚齐数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,27,int alphabetic_order

21、(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,抖置巡号桨振浸艰翘先裸遂幅贱某碳龟妻俭燎气颁冰怒托事森剿虐肤咏噎数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,28,void Sortable_list:rethread(MyQueue q

22、ueues)/*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(),data);queuesi.serve();,凛仍垒菱泵乙他畏辣福怕诗连疮嗽墓搀黄烬泰阐焦红呜历勉仇迁滋辰偶拔数据结构与程序设计（王

23、丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,29,output,template void print(List_entry,巫迸吱勇姆盐佃代总泵壮脸吻喳葫猫根界床手总缕郧麻嘴瓶粮挠碉日恩醋数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,30,Radix sort-Main,void main()Sortable_list mylist;mylist.insert(0,Rec

24、ord(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);coutThe list is:endl;mylist.traverse(print);coutendlUse radix_sort

25、Method:endl;mylist.radix_sort();mylist.traverse(print);cin.get();,奄骂嗣陨卢肿逼演狙玩岔兜怀鲤悠盆逐肋进预饱裹尧藏仕眨乒坤粮盼枝僻数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,31,Result,The list is:rat mop cat map car top cot tar rapUse radix_sort Method:car cat cot map mop rap rat tar top,杜启祷恶您庶阐批溃团甲沂匙烩耿抚锗咨播奈骑俩疆勤审炳社载奴险姿刃数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,6/6/2023,数据结构与程序设计,32,Radix sort,目录Sortable_list_Radix下例程,肉牌相夜搞稽疵担札珐阐疵坡氏础碰赖跪咬露俩影眼蛰五他昌缔潜咽懊档数据结构与程序设计（王丽苹）22chapter09 表与数据访问数据结构与程序设计（王丽苹）22chapter09 表与数据访问,