大学数据结构——用C语言描述（第二版）-宁正元-大学教学资料课件PPT
收藏
资源目录
压缩包内文档预览：(预览前20页/共30页)
编号：21835845
类型：共享资源
大小：19.19MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
数据结构
语言
描述
描写
第二
宁正元
教学
资料
课件
ppt
- 资源描述：
-
大学数据结构——用C语言描述（第二版）-宁正元-大学教学资料课件PPT,大学,数据结构,语言,描述,描写,第二,宁正元,教学,资料,课件,ppt
- 内容简介：
-
10.1 文件的基本概念 10.2 顺序文件 10.3 索引文件 10.4 散列文件 10.5 多关键字文件,第10章 文件,文件（Files）是大量记录的有序集合，它对应一个二维表，表的每一行为一个记录，每一列为一个数据项。一般称存储在内存中的记录集合称为表，而称存储在外存储器中的记录集合为文件。文件中的记录是按某一种确定的次序线性排列，所以文件的逻辑结构是线性结构。本章主要介绍文件的概念和几种基本的数据文件的构造方法及其使用讨论文件在外存储器中的表示及其操作的实现。,第10章 文件,1、文件的概念 文件是由大量性质相同的记录组成的集合；二者的区别在于线性表是把记录全部组织在内存储器中，而文件则是把大量记录都组织在外存储器中。 2、文件分类 按照记录的类型，可以把文件分为操作系统文件和数据库文件两大类。 按照记录的长度特性，可以把文件分为定长记录文件和不定长记录文件。定长记录文件中每个记录含有的信息长度相同，而不定长记录文件中每个记录含有的信息长度不等。 按照记录中关键字的多少，可以把文件分为单关键字文件和多关键字文件。单关键字文件中的记录只有一个惟一标识记录的主关键字；而多关键字文件中的记录除了主关键字外，还含有一个或多个次关键字，记录中所有非关键字的数据项称作记录的属性。,10.1 文件的基本概念,3、逻辑结构和物理结构 逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式；用户所读写的记录是指逻辑记录。记录的物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织方式。一个物理记录可以存放一个或多个逻辑记录，多个物理记录可以表示一个逻辑记录。用户读写的是逻辑记录，检索其对应的物理记录是操作系统的职责。 文件组织方式（即物理结构）有顺序组织、随机组织和链式组织等基本方式。,4、文件的操作 一般的，文件的操作有检索、修改和排序三类 。检索的方式有三种：顺序检索；按记录号检索；按关键字检索。修改操作包括插入、删除和更新一个记录这三种操作。排序操作则是为了检索方便高效对文件中记录的重新有序整理。 另外，文件的操作也可以有实时和批处理两种不同的方式。实时处理通常对应答时间要求严格，应在接收询问后立即完成相应的操作；而批处理则不同，可以根据需要对积累一段时间的记录进行成批处理。,顺序文件是把记录按建立文件时的逻辑顺序依次存放在外存储器中，文件中的物理记录顺序和逻辑记录顺序一致。若次序相继的两个物理记录在存储器上的存储位置是相邻的，则又称为连续文件；若物理记录之间的次序由指针链接，则称为串联文件。 顺序文件的优点是连续存取速度快，主要用于顺序存取和批量修改的情况。若对应答时间要求不严格时亦可进行直接存取。 在对顺序文件作修改时，可对原文件中的记录复制一遍，并在复制的过程中插入新的记录、跳过待删除的记录、或用修改过的新记录代替原记录。为了修改方便起见，要求待修改文件按关键字有序（对非数据库文件可将逻辑记录号作为关键字）。 磁带是一种典型的顺序存取设备，存储在磁带上的文件就是顺序文件。对磁盘上的顺序文件进行修改时，若不增加记录的长度，也可在原文件上直接修改而不必复制文件。 对顺序文件进行顺序检索的方法类似于静态表的顺序检索，也可以对磁盘文件进行分块检索或二分法检索。,10.2 顺序文件,索引文件是指具有索引存储结构的文件。简单的文件包含一个主文件和一个索引表，主文件是原有数据文件的顺序存储或链接存储的文件，而索引表是在主文件的基础上建立的顺序表，索引表中的每个索引项同文件中的每个记录一一对应，每个索引项由对应记录的关键字和存储该记录的首地址组成，而且无论主文件是否按关键字有序，索引表将组织成按关键字有序，即除了主文件（即数据文件）之外，再建立一张索引表来指示逻辑记录和物理记录之间的一一对应关系；索引表中的每一项称作索引项，由记录的关键字和记录的存放地址构成；把索引表和主文件总称为索引文件（Indexed File）。 在索引文件中，若主文件也按关键字升序排列，则构成的索引文件称作索引顺序文件；若主文件是无序的，则称所构造的索引文件为索引非顺序文件。索引文件只适用于直接存取的外存储器（如磁盘）。索引文件的存储分索引区和数据区来进行，索引区存放索引表，数据区存放主文件。在输入记录建立数据区的同时建立索引表，表中的索引项按记录输入的先后次序排列；待全部记录输入完毕后再对索引表按关键字排序，排序后的索引表和主文件一起构成了索引文件，如图10.1所示。,10.3 索引文件,索引文件的检索，应先在索引表中检索。若在索引表中检索到关键字值等于给定值的索引项，则按索引项指示从外部存储器读取该记录；否则，说明待检索记录不存在无需访问外存储器。当主文件中记录数目很大时，可对索引表再次建立二级索引；检索时先在二级索引中找，再检索索引表，然后读取记录。索引表和二级索引表都是有序表，在内存储器中可用检索效率较高的方法如二分法检索方法进行检索。 多级索引是一种静态索引，为顺序表结构，虽然结构简单，但修改很不方便，每次修改都要重组索引，所以，当主文件在使用过程中记录变动比较多时，应采用树表结构的动态索引，如二叉排序树、B-树、键树等，以便于插入、删除等。,ISAM（Indexed Sequential Access Method）即索引顺序存取方法，是一种专为磁盘存取设计的文件组织方式。如图10.2所示为存放在一个磁盘组上的ISAM文件。 在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。 由于ISAM文件中记录是按关键字顺序存放的，在插入一个记录时需要向后移动记录，并将同一磁道上的最后一个记录移至溢出区，同时修改磁道索引项。ISAM文件的插入和溢出处理如图10.3所示。 ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。,10.3.1 ISAM文件,VSAM（Virtual Storage Access Method）即虚拟存储存取方法。它使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。 VSAM文件的结构由索引集、顺序集和数据集三部分组成，如图10.4所示。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（Control Interval）。顺序集中的一个结点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（Control Range）。顺序集中的结点之间用指针相链接，在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。,10.3.2 VSAM文件,对VSAM文件中记录的检索，既可从最高层的索引逐层往下按关键字进行检索，又可在顺序集中沿着指针链顺序检索。 VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区间来插入记录（即在B+树上插入记录）。而在VSAM文件中删除记录时，也需移动记录。 VSAM文件占有较多的存储空间，然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。 VSAM文件通常作为组织大型索引顺序文件的标准形式。,散列文件（Hash File）也称作直接存取文件，它是利用哈希方法组织的数据文件；即根据某个哈希函数和一定的冲突消解策略而得到的存放在外存储器上的散列表。 磁盘上的文件的若干个记录组成一个存储单位，在散列文件中这个存储单位称作桶。一个桶能存放的逻辑记录的总数称作桶的容量。假如桶的容量为m，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词记录出现时则发生溢出。处理溢出也可采用哈希表中的各种处理冲突的方法，但对散列文件主要是采用链地址法消解冲突。 当发生溢出时，需要将第m+1个同义词存放到另一个桶中，通常称作“溢出桶”；相应地把存放前m个同义词的桶称作“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有检索到待查记录时，就顺指针所指到溢出桶中去检索。 例如，某一个文件有个记录，其关键字分别为28，19，13，93，89，14，55，69，8，9，16，21，33，81，62，l1，15，34，35，用除留余数法作哈希函数H（key）=key %7，桶的容量m=3，基本桶数=7，由此得到的散列文件如图10.5所示。,10.4 散列文件,在散列文件中检索时，先根据给定的关键字值k求得哈希地址即基桶号，然后将基桶的记录读入内存进行顺序检索，若找到关键字值为k的记录则检索成功；若基桶中虽无关键字值为k的记录但指针域非空，需要把溢出桶中的记录读入内存继续检索，直到检索成功或检索失败。若基桶内没有填满记录即虽有溢出桶但仍未找到关键字为k的记录或其指针域为空（即无溢出桶），则文件内不含有待检索记录，即检索失败。 在散列文件中，删除记录时仅需对被删除记录作一个删除标记即可。 散列文件具有插入、删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间等优点；但它也具有以下缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成溢出桶满而基桶内多数为被删除记录的不合理文件结构，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录，此时亦需对文件进行重新整理。,多关键字文件（Multiple Key File）的特点是，在对文件进行检索操作时不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。因此，对多关键字文件还需要建立一系列的次关键字索引。次关键字索引和主关键字索引所不同的是，每个索引项应包含次关键字和具有同一次关键字的多个记录的主关键字或物理记录号。多重表文件和倒排文件是常见的两种多关键字文件的组织方法。 多重表文件（Multilist File）的特点是，记录按主关键字的顺序构成一个串联文件，并建立主关键字索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，一组记录建立一个索引项；次索引为稠密索引，每个记录建立一个索引项，每个索引项包括次关键字、头指针和链表长度。,10.5 多关键字文件,例如，图10.6所示为一个多重表文件。对工号非稠密索引分成三个子链表，其索引如图10.6(b)所示，索引项中的主关键字为各组中关键字的最大值。职称和专业是两个次关键字项，其索引分别如图10.6(c)和(d)所示，具有相同次关键字值的记录链接在同一链表中。有了这些次关键字索引，根据关键字值找到链表头指针，然后从头指针出发可列出链表中所有记录。 在多重表文件中可以很容易地插入一个新记录是，只要修改指针，将记录插在链表的头指针之后即可。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。 倒排文件（inverted file）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表，在倒排表的索引项中没有头指针和链长度，而是直接用一个项存放具有同一关键字的所有记录的物理记录号或主关键字值。如图10.7所示为上例中的倒排表。,在倒排文件中可以较快地检索记录，特别是在检索多个次关键字的情况时。在处理各种次关键字的查询时，只要在次关键字索引中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去存取记录。 在插入和删除记录时，倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如ISAM文件），倒排表中应存放记录的主关键字而不是物理记录号。 倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难，而且倒排表需要额外存储空间。,10.1 文件的基本概念10.2 顺序文件10.3 索引文件10.4 散列文件10.5 多关键字文件第10章 文件 文件（Files）是大量记录的有序集合，它对应一个二维表，表的每一行为一个记录，每一列为一个数据项。一般称存储在内存中的记录集合称为表，而称存储在外存储器中的记录集合为文件。文件中的记录是按某一种确定的次序线性排列，所以文件的逻辑结构是线性结构。本章主要介绍文件的概念和几种基本的数据文件的构造方法及其使用讨论文件在外存储器中的表示及其操作的实现。第10章 文件 1、文件的概念 文件是由大量性质相同的记录组成的集合；二者的区别在于线性表是把记录全部组织在内存储器中，而文件则是把大量记录都组织在外存储器中。 2、文件分类 按照记录的类型，可以把文件分为操作系统文件和数据库文件两大类。 按照记录的长度特性，可以把文件分为定长记录文件和不定长记录文件。定长记录文件中每个记录含有的信息长度相同，而不定长记录文件中每个记录含有的信息长度不等。 按照记录中关键字的多少，可以把文件分为单关键字文件和多关键字文件。单关键字文件中的记录只有一个惟一标识记录的主关键字；而多关键字文件中的记录除了主关键字外，还含有一个或多个次关键字，记录中所有非关键字的数据项称作记录的属性。10.1 文件的基本概念 3、逻辑结构和物理结构 逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式；用户所读写的记录是指逻辑记录。记录的物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织方式。一个物理记录可以存放一个或多个逻辑记录，多个物理记录可以表示一个逻辑记录。用户读写的是逻辑记录，检索其对应的物理记录是操作系统的职责。 文件组织方式（即物理结构）有顺序组织、随机组织和链式组织等基本方式。 4、文件的操作 一般的，文件的操作有检索、修改和排序三类 。检索的方式有三种：顺序检索；按记录号检索；按关键字检索。修改操作包括插入、删除和更新一个记录这三种操作。排序操作则是为了检索方便高效对文件中记录的重新有序整理。 另外，文件的操作也可以有实时和批处理两种不同的方式。实时处理通常对应答时间要求严格，应在接收询问后立即完成相应的操作；而批处理则不同，可以根据需要对积累一段时间的记录进行成批处理。 顺序文件是把记录按建立文件时的逻辑顺序依次存放在外存储器中，文件中的物理记录顺序和逻辑记录顺序一致。若次序相继的两个物理记录在存储器上的存储位置是相邻的，则又称为连续文件；若物理记录之间的次序由指针链接，则称为串联文件。 顺序文件的优点是连续存取速度快，主要用于顺序存取和批量修改的情况。若对应答时间要求不严格时亦可进行直接存取。 在对顺序文件作修改时，可对原文件中的记录复制一遍，并在复制的过程中插入新的记录、跳过待删除的记录、或用修改过的新记录代替原记录。为了修改方便起见，要求待修改文件按关键字有序（对非数据库文件可将逻辑记录号作为关键字）。 磁带是一种典型的顺序存取设备，存储在磁带上的文件就是顺序文件。对磁盘上的顺序文件进行修改时，若不增加记录的长度，也可在原文件上直接修改而不必复制文件。 对顺序文件进行顺序检索的方法类似于静态表的顺序检索，也可以对磁盘文件进行分块检索或二分法检索。10.2 顺序文件 索引文件是指具有索引存储结构的文件。简单的文件包含一个主文件和一个索引表，主文件是原有数据文件的顺序存储或链接存储的文件，而索引表是在主文件的基础上建立的顺序表，索引表中的每个索引项同文件中的每个记录一一对应，每个索引项由对应记录的关键字和存储该记录的首地址组成，而且无论主文件是否按关键字有序，索引表将组织成按关键字有序，即除了主文件（即数据文件）之外，再建立一张索引表来指示逻辑记录和物理记录之间的一一对应关系；索引表中的每一项称作索引项，由记录的关键字和记录的存放地址构成；把索引表和主文件总称为索引文件（Indexed File）。 在索引文件中，若主文件也按关键字升序排列，则构成的索引文件称作索引顺序文件；若主文件是无序的，则称所构造的索引文件为索引非顺序文件。索引文件只适用于直接存取的外存储器（如磁盘）。索引文件的存储分索引区和数据区来进行，索引区存放索引表，数据区存放主文件。在输入记录建立数据区的同时建立索引表，表中的索引项按记录输入的先后次序排列；待全部记录输入完毕后再对索引表按关键字排序，排序后的索引表和主文件一起构成了索引文件，如图10.1所示。10.3 索引文件 索引文件的检索，应先在索引表中检索。若在索引表中检索到关键字值等于给定值的索引项，则按索引项指示从外部存储器读取该记录；否则，说明待检索记录不存在无需访问外存储器。当主文件中记录数目很大时，可对索引表再次建立二级索引；检索时先在二级索引中找，再检索索引表，然后读取记录。索引表和二级索引表都是有序表，在内存储器中可用检索效率较高的方法如二分法检索方法进行检索。 多级索引是一种静态索引，为顺序表结构，虽然结构简单，但修改很不方便，每次修改都要重组索引，所以，当主文件在使用过程中记录变动比较多时，应采用树表结构的动态索引，如二叉排序树、B-树、键树等，以便于插入、删除等。 ISAM（Indexed Sequential Access Method）即索引顺序存取方法，是一种专为磁盘存取设计的文件组织方式。如图10.2所示为存放在一个磁盘组上的ISAM文件。 在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。 由于ISAM文件中记录是按关键字顺序存放的，在插入一个记录时需要向后移动记录，并将同一磁道上的最后一个记录移至溢出区，同时修改磁道索引项。ISAM文件的插入和溢出处理如图10.3所示。 ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。10.3.1 ISAM文件 VSAM（Virtual Storage Access Method）即虚拟存储存取方法。它使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。 VSAM文件的结构由索引集、顺序集和数据集三部分组成，如图10.4所示。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（Control Interval）。顺序集中的一个结点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（Control Range）。顺序集中的结点之间用指针相链接，在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。10.3.2 VSAM文件 对VSAM文件中记录的检索，既可从最高层的索引逐层往下按关键字进行检索，又可在顺序集中沿着指针链顺序检索。 VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区间来插入记录（即在B+树上插入记录）。而在VSAM文件中删除记录时，也需移动记录。 VSAM文件占有较多的存储空间，然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。 VSAM文件通常作为组织大型索引顺序文件的标准形式。 散列文件（Hash File）也称作直接存取文件，它是利用哈希方法组织的数据文件；即根据某个哈希函数和一定的冲突消解策略而得到的存放在外存储器上的散列表。 磁盘上的文件的若干个记录组成一个存储单位，在散列文件中这个存储单位称作桶。一个桶能存放的逻辑记录的总数称作桶的容量。假如桶的容量为m，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词记录出现时则发生溢出。处理溢出也可采用哈希表中的各种处理冲突的方法，但对散列文件主要是采用链地址法消解冲突。 当发生溢出时，需要将第m+1个同义词存放到另一个桶中，通常称作“溢出桶”；相应地把存放前m个同义词的桶称作“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有检索到待查记录时，就顺指针所指到溢出桶中去检索。 例如，某一个文件有个记录，其关键字分别为28，19，13，93，89，14，55，69，8，9，16，21，33，81，62，l1，15，34，35，用除留余数法作哈希函数H（key）=key %7，桶的容量m=3，基本桶数=7，由此得到的散列文件如图10.5所示。10.4 散列文件 在散列文件中检索时，先根据给定的关键字值k求得哈希地址即基桶号，然后将基桶的记录读入内存进行顺序检索，若找到关键字值为k的记录则检索成功；若基桶中虽无关键字值为k的记录但指针域非空，需要把溢出桶中的记录读入内存继续检索，直到检索成功或检索失败。若基桶内没有填满记录即虽有溢出桶但仍未找到关键字为k的记录或其指针域为空（即无溢出桶），则文件内不含有待检索记录，即检索失败。 在散列文件中，删除记录时仅需对被删除记录作一个删除标记即可。 散列文件具有插入、删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间等优点；但它也具有以下缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成溢出桶满而基桶内多数为被删除记录的不合理文件结构，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录，此时亦需对文件进行重新整理。 多关键字文件（Multiple Key File）的特点是，在对文件进行检索操作时不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。因此，对多关键字文件还需要建立一系列的次关键字索引。次关键字索引和主关键字索引所不同的是，每个索引项应包含次关键字和具有同一次关键字的多个记录的主关键字或物理记录号。多重表文件和倒排文件是常见的两种多关键字文件的组织方法。 多重表文件（Multilist File）的特点是，记录按主关键字的顺序构成一个串联文件，并建立主关键字索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，一组记录建立一个索引项；次索引为稠密索引，每个记录建立一个索引项，每个索引项包括次关键字、头指针和链表长度。10.5 多关键字文件 例如，图10.6所示为一个多重表文件。对工号非稠密索引分成三个子链表，其索引如图10.6(b)所示，索引项中的主关键字为各组中关键字的最大值。职称和专业是两个次关键字项，其索引分别如图10.6(c)和(d)所示，具有相同次关键字值的记录链接在同一链表中。有了这些次关键字索引，根据关键字值找到链表头指针，然后从头指针出发可列出链表中所有记录。 在多重表文件中可以很容易地插入一个新记录是，只要修改指针，将记录插在链表的头指针之后即可。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。 倒排文件（inverted file）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表，在倒排表的索引项中没有头指针和链长度，而是直接用一个项存放具有同一关键字的所有记录的物理记录号或主关键字值。如图10.7所示为上例中的倒排表。 在倒排文件中可以较快地检索记录，特别是在检索多个次关键字的情况时。在处理各种次关键字的查询时，只要在次关键字索引中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去存取记录。 在插入和删除记录时，倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如ISAM文件），倒排表中应存放记录的主关键字而不是物理记录号。 倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难，而且倒排表需要额外存储空间。第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价,本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法（C语言描述）、数据类型以及抽象数据类型，并概述数据结构的发展概况及其在计算机科学中的地位。,第1章 绪 论,随着计算机应用领域的不断扩大，计算机处理的对象更多的是非数值计算问题，它们的数学模型无法用数学方程来进行描述，此时就必须建立相应的数据结构来进行描述，分析问题中所用到的数据是如何组织的，研究数据之间的关系如何，进而为解决这些问题设计出合适的数据结构。,1.1 什么是数据结构,例1 职工信息管理,图1.1 职工花名册表,将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成，占表的一行，表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时，就要考虑那些结点在计算机中的存储表示，即存储结构。另外，还必须考虑如何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算,例2 旅游交通网络图 如图1.2所示，为一个旅游交通网络咨询系统，可采用一种称之为图的结构来表示实际的交通网络， 此时，这个交通网络图就表示一个数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放入计算机中，这就要涉及到图的存储结构问题，以及图的运算。 从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，涉及到一些诸如表、图还有树之类的数据结构。 数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于数据项。,1.2 基本概念和术语,数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。 数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容： （1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。 （2）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。 （3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。,数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构： （1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。 （2）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。 （3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。 （4）集合：结构中的数据元素之间除了“同属于一个集合”的相互关系外，别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。,数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按以下四种基本存储方法而得到： （1）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。 （2）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。,（3）索引存储方法：该方法通常是在存储结点信息的同时，建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。 （4）散列存储方法：该方法是依据结点的关键字直接计算出该结点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。 数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。,数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。 在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如C语言中的整型、字符型、实型、指针类型等；而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分解的，如C语言中提供的结构体。 抽象数据类型（ADT）是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。,1.3 数据类型和抽象数据类型,算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列。一个算法必须具备以下五个重要特性： （1）输入：一个算法必须具有零个或多个的外界输入。 （2）输出：一个算法必须有一个或多个的输出。 （3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算法与程序。 （4）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。 （5）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现，而且算法必须在有限时间内完成。 一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计算机高级程序语言来描述，如PASCAl语言、C语言、C、Java或伪代码等。本书选用C语言作为描述算法的工具。,1.4.1 算法描述,1.4 算法描述与算法评价,1.4.2 算法的设计要求,设计一个好的算法可以从以下几个方面考虑： （1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。 （2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然也必须有效。 （3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处理。 （4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽可能地少，即做到既省时又节省空间。 要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较好较优的算法。,考虑算法的效率应从下几个方面考虑： （1）时间效率。考虑算法所耗费的运行时间。 （2）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算法所需的辅助存储空间。 （3）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确结果。 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。,1.4.3 算法的评价,例如，两个nn矩阵相乘的算法： for（i=1；i=n；i+） /* n+1次 */ for（j=1；j=n；j+） /* n（n+1）次*/ ci j = 0； /* nn次 */ for（k=1；k=n；k+） /* n2（n+1）次*/ ci j = ci j + i k * b k j；/* n*n*n次*/ 上述算法的时间耗费T(n)为： T（n）= 2n3 + 3n2 + 2n + 1 当n时，T(n)/n32，表示当n充分大时，T(n)与n3是同阶或者说同数量级，它是矩阵的阶数n的函数。 若引入大“O”记号，则T(n)可记作：T(n)= O(n3) ，此时称T(n)= O(n3)是求解矩阵相乘这个特定问题的渐近时间复杂度。有时将一个算法的渐近时间复杂度O(n)=O(f(n)认为就是时间复杂度。 常见的时间复杂度按数量级递增排列，依次为：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，指数阶O(2n)等等。,有时，可以依据算法转化为程序时各个语句的特点，利用一些简单的程序分析法则进行简单算法分析： （1）对于一些简单的输入、输出语句或赋值语句，它们执行时，近似认为需要O(1)时间； （2）对于顺序结构，需要依次执行一系列语句所用的时间可采用大O下的“求和法则”进行估计； （3）对于选择结构，如如果语句，它的主要时间耗费是在执行然后子句或别的子句所花费的时间，但须注意检验条件也还需要用O(1)的时间； （4）对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般地可用大O下的“乘法法则”进行估计； （5）对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O的求和法则和乘法法则计算整个算法的时间复杂度。,衡量一个算法好坏的另一个因素是程序运行时所占用的存贮空间大小。 度量一个算法在运行或执行过程中所占用的存储空间的大小类似于时间复杂度，可以用空间复杂度来度量。算法的空间复杂度一般也以相对于问题规模的数量级的形式给出，如O(1)，O(n)等。,第1章 绪论1.1 什么是数据结构1.2 基本概念和术语 1.3 数据类型和抽象数据类型1.4 算法描述与算法评价 本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法（C语言描述）、数据类型以及抽象数据类型，并概述数据结构的发展概况及其在计算机科学中的地位。第1章 绪 论 随着计算机应用领域的不断扩大，计算机处理的对象更多的是非数值计算问题，它们的数学模型无法用数学方程来进行描述，此时就必须建立相应的数据结构来进行描述，分析问题中所用到的数据是如何组织的，研究数据之间的关系如何，进而为解决这些问题设计出合适的数据结构。1.1 什么是数据结构例1 职工信息管理图1.1 职工花名册表 将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成，占表的一行，表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时，就要考虑那些结点在计算机中的存储表示，即存储结构。另外，还必须考虑如何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算 例2 旅游交通网络图 如图1.2所示，为一个旅游交通网络咨询系统，可采用一种称之为图的结构来表示实际的交通网络， 此时，这个交通网络图就表示一个数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放入计算机中，这就要涉及到图的存储结构问题，以及图的运算。 从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，涉及到一些诸如表、图还有树之类的数据结构。 数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。 数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于数据项。1.2 基本概念和术语 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。 数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容： （1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。 （2）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。 （3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。 数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构： （1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。 （2）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。 （3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。 （4）集合：结构中的数据元素之间除了“同属于一个集合”的相互关系外，别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。 数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按以下四种基本存储方法而得到： （1）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。 （2）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。 （3）索引存储方法：该方法通常是在存储结点信息的同时，建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。 （4）散列存储方法：该方法是依据结点的关键字直接计算出该结点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。 数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。 数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。 在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如C语言中
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号