通常有两类方法处理冲突:开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是将互为同义词的结点链成一个单链表,而将此链表的头指针放在散列表T[0..m-1]中。
散列表上的运算有查找、插入和删除。其中主要是查找,这是因为散列表的目的主要是用于快速查找,且插入和删除均要用到查找操作。
文件(File)是性质相同的记录的集合。
顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。注意:一切存储在顺序存取存储器(如磁带)上的文件,都只能是顺序文件。
索引文件由主文件和索引表构成。主文件:文件本身。索引表:在文件本身外建立的一张表,它指明逻辑记录和物理记录之间的一一对应关系。
ISAM为Indexed Sequential Access Methed(索引顺序存取方法)的缩写,它是一种专为磁盘存取文件设计的文件组织方式,采用静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备,则可对磁盘上的数据文件建立盘组、柱面和磁道多级索引,下面只讨论在同一个盘组上建立的ISAM文件。
VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写,它也是一种索引顺序文件的组织方式,采用B+树作为动态索引结构。
散列文件是利用散列存储方式组织的文件,亦称直接存取文件。即根据文件中关键字的特点,设计一个散列函数和处理冲突的方法,将记录散列到存储设备上。
对每个需要查询的次关键字建立一个索引,同时将具有相同次关键字的记录链接成一个链表,并将此链表的头指针、链表长度及次关键字,作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。
倒排文件和多重表文件不同。在次关键字索引中,具有相同次关键字的记录之间不进行链接,而是列出具有该次关键字记录的物理地址。倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。
十个章节所附练习题及答案。
课程性质与设置目的、考试内容与考核目标、有关说明与实施要求、题型举例等相关信息。
[1]Knuth D E.The Art of Computer Programming,1:Fundamental Algrithms;3:Sorting and Searching.Addison Wesley,1973
[2]Horowitz E,Sahni S.Fundamentals of Data Structures.Computer Science Press,1976
[3]Wirth N.Algorithms+Data Structures=Programs.Prentice Hall,1978
[4]Gotlieb C C,Gotlieb L R.Data Types and Structures.Prentice Hall,1978
[5]Tenenbaum A M,Augensetein M J.Data Structures Using PASCAL.Prentice Hall,1981
[6]Aho A V,Hopcroft J E,Ullman J D.Data Structures and Algorithms.AddisonWesley,1983
[7]Horwitz E,Sahni S.Fundamentals of Computer Algorithms.Computer Science Press,1978
[8]Kochan S G.Programming in C.Hayden Book Company,1983
[9]Thomas H.Cormen et al.Introduction to Algorithms.The MIT Press,1995
[10]Williaw Ford et al.Data Structures with C++.Prentice Hall Inc.,1996
[11]Robert Kruse et al.Data Structures & Program Design in C.2nd Ed.Prentice Hall,1997
[12]黄刘生,唐策善:《数据结构》第二版,中国科学技术大学出版社,2000年
[13]严蔚敏,吴伟民:《数据结构》,第二版,清华大学出版社,1992年
[14]许卓群等:《数据结构》,高等教育出版社,1987年
[15]仲萃豪,冯玉琳:《程序设计方法学》,北京科学技术出版社,1985年
来源: http://www.bubuko.com/infodetail-2353808.html