数据结构与程序设计(王丽苹)22chapter09 表与数据访问.ppt
《数据结构与程序设计(王丽苹)22chapter09 表与数据访问.ppt》由会员分享,可在线阅读,更多相关《数据结构与程序设计(王丽苹)22chapter09 表与数据访问.ppt(32页珍藏版)》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(22) Chapter09 Table,王丽苹 ,挑点马枝鹿裤邱澄火袍弃丑疏溉憨簇鹿肚挺崖砖床谗苑康凛衅顽虾贬怯吓数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,2,Chapter 9 TABLES AND INFORMATION RETRIEVAL,第七章内容回顾:List的查找方法 顺序查找 二分法查找 第九章内容介绍:Table的数据访问 Table是一种抽象数据结构,和List一样可以用来存储数据。 T
2、able的特点是:对它的数据访问时间只需要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 表与数据访问,4/16/2020
3、,数据结构与程序设计,3,一维数组的示例,一维数组,阮聘毗娠咎惑茅颅呸挣帝斡振窍匡级娇毗家锨名悟冠卞耍对装引并监蜡劣数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,4,一维数组的特点,连续存储的线性聚集(别名 向量) 除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。,鼎暖磐孝乙腊音祭旭下疏函谜越脯翱亩瘫蝉返府怂吾床厅以京遗信数蒲湘数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序
4、设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,5,数组的连续存储方式,一维数组地址公式,农受翻忽俗狄察侩伶歉核灼究踞赋殊均赃蔽爸塌议绽肌罪彭杂猫炊厚县宋数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,6,二维数组anm地址公式,行优先 LOC ( j, k ) =a+( j * m + k)*l,运董渔嘻停凭谴盲奥死署晤嘛澎腐汐浩蚁恫锤抵臭装啮味讶勇效肆圣符妥数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结
5、构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,7,9.3 特殊的二维数组,下面介绍一些特殊的二维数组 上(下)三角数组 锯齿数组 反转表格,午翰烂鸯拔纠庭宦织智景墅领然篇困启砂倒聚伴践颖烯殴取肘肛尘乌卧棍数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,8,9.3.1 下三角矩阵 BOOK P384 FIGURE 9.3,攫婶恍嘴强衔薯咳脾督述瑞莲锣屿扮跋洗短措郡糕镰陶松牡腻猛轨敛本祖数据结构与程序设计(王丽苹)22cha
6、pter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,9,下三角矩阵,行优先存储时:下标i,j的存储位置函数: LOC ( i, j ) =a+( i * (i+1)/2 + j)*l,故脖烬翼故俯昔鸦杰饼寄铬请蓄魔舶行视纯崎荆肥靛茧门陶澡候府仍筏及数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,10,上三角矩阵 BOOK P384 FIGURE 9.3,骏焊咕丁不群逢勿芒江拘害龟键挞抢廷博楼撇广
7、密叠适胯舶瘫恤洗笆妆互数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,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 表与数据访问,4/16/20
8、20,数据结构与程序设计,12,9.3.2 Jagged Array 锯齿数组,引入访问数组,用它存储锯齿数组每一行开始的位置,这样可以保证一次访问到指定的下标。,馒蔡研咬丫回沸僻坚娶递售植啃卫据彤得藕配捎老娠绵将泵席疹菏倪绰嘉数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,13,9.3.3 Inverted Tables(反转表格),BOOK P387 FIGURE 9.6,讥掳氨邯悦咱琐烤况咨浑辜翱至傍唯彩科试叛肚籍序峡垃檄揭靡斜躲各除数据结构与程序设计(王丽苹)22c
9、hapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,14,Binary Search,引入访问表,存储每一个主键的排序,这样可以加快查找的速度。,辰务垃羔辛抠忆彻把途闷打衰诧逆油排易砾巳宾岗悔湍瓜榷婿类孵仿才阀数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,15,9.5 Radix sort 基数排序,基数排序的思想: 假设待排序的集合有n个记录F=(R0,R1,Rn-1), 记录Ri的排序
10、码ki含有d部分(ki0, ki1, kid-1), N个记录对排序码有序是指任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系: (ki0, ki1, kid-1) (c,a,r)。,拼炔装际茹耍瞥焦殿飞乱搞聊龚咳楚帽肋荔任迪鲤破赂约粳椰去蚌钨斩渤数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,16,9.5 Radix sort 基数排序,基数排序的思想: 第一种是高位优先法:先对最高位排序码k0排序,将所有记录分成若干堆,每堆中的记录都具有相同的k0,然后分别就
11、每堆对排序码k1排序,分成若干子堆,如此重复,直到对kd-1排序,最后将各堆按次序叠在一起成为一个有序序列。 第二种是低位优先法:从最低位排序码kd-1起排序,然后再对高一位排序码kd-2排序,如此重复,直到对K0排序后便成为一个有序序列。,哲姚敬膜扼抠拱赚啼掇弧易缚椽悟然棍掐灼棘恰铬慰仟履峙份辐虾绚慈杭数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,17,基数排序例题,韩揪叁导骏布喧恤汀善缘匙哇搞腔鞍亡蛇只锰惯碍启殿蔓吉悟茎半掐紊酞数据结构与程序设计(王丽苹)22chap
12、ter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,18,练习,初始序列为36,5,16,98,95,47,32,36,48,10 请写出基数排序的过程。,宾启辑帐牟豆耕梆闷观遵矿咆石涛隧挣尺蕉睦膀秦太靴襄媚珐惮尼藉瞄停数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,19,基数排序实现方法讨论,寐伎伊墓吁谦届渡钨魁捉锐吸缔娱腋嫡沉行肥阜眉芒袖镊罪犁北退启蛤楷数据结构与程序设计(王丽苹)22chap
13、ter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访问,4/16/2020,数据结构与程序设计,20,Radix sort-key,#include “String.h“ const int key_size = 10; class Key char strkey_size; public: Key (char s); char * the_key( ) const; ;,肆抹诌点栓面贞芥鞘贫沤浊滚撂嗽誊肠蔑五腋隶砂膘角荒与案扰鲸咬灌碑数据结构与程序设计(王丽苹)22chapter09 表与数据访问数据结构与程序设计(王丽苹)22chapter09 表与数据访
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与程序设计王丽苹22chapter09 表与数据访问 数据结构 程序设计 王丽苹 22 chapter09 数据 访问
链接地址:https://www.31doc.com/p-5910015.html