第9章查找
第2章至第7章中已经介绍了各种线性或非线性的数据结构，在这一章将讨论另一种在实际应用中大量使用的数据结构——查找表。
查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。
对查找表经常进行的操作有：
(1)查询某个“特定的”数据元素是否在查找表中；
(2)检索某个“特定的”数据元素的各种属性；
(3)在查找表中插入一个数据元素；
(4)从查找表中删去某个数据元素。
若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(Static Search Table)。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)。
所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。
关键字(Key)是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(Secondary Key)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。
查找(Searching)根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。
如何进行查找?
显然，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系(这个关系是人为地加上的)组织在一起的。
[例如]，查电号码时，由于电话号码簿是按用户(集体或个人)的名称(或姓名)分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。[又如]，查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。
同样，在计算机中进行查找的方法也随数据结构不同而不同。正如前所述，本章讨论的查找表是一种非常灵便的数据结构。但也正是由于表中数据元素之间仅存在着“同属一个集合”的松散
关系，给查找带来不便。为此，需在数据元素之间人为地加上一些关系，以便按某种规则进行查找，即以另一种数据结构来表示查找表。
本章将分别就静态查找表和动态查找表两种抽象数据类型讨论其表示和操作实现的方法。
9.1 静态查找表
9.2 动态查找表
9.3 哈希表
9.1 静态查找表（学时）
抽象数据类型静态查找表的定义为：
ADT StaticSearchTable{
数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。
数据关系R：数据元素同属一个集合。
基本操作P：
Create(&ST，n)；
操作结果：构造一个含n个数据元素的静态查找表ST。
Destroy(&ST)；
初始条件：静态查找表ST存在。操作结果：销毁表ST。
Search(ST，key)；
初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。
操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中位置，否则为“空”。
Traverse(ST，visit( ))；
初始条件：静态查找表ST存在，visit是对元素操作的应用函数。
操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次，一旦visit()失败，则操作失败。
} ADT StaticSearchTable
静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。9.1.1 顺序表的查找
以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。本节中只讨论它在顺序存储结构模块中的实现，在线性链表模块中实现的情况类似。
//————静态查找表的顺序存储结构———
typdef struct{
ElemType * elem; //数据元素存储空间基址
int length; //建表时按实际长度分配，0号单元留空表长度
}SSTable；
下面讨论顺序查找的实现。
顺序查找(Sequential Search)的查找过程为：
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。此查找过程可用算法9.1描述之。
int Search_Seq(SSTable ST，KeyType key){
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。
ST.elem[0].key = key; //0号单元作为监视哨
for ( i=ST.length; !EQ (ST.elem[i].key , key); --i ); //从后往前找
return i；//找不到时，i为0
} // Search_Seq
算法9.1
分析顺序查找演示过程参见（板书走程序）
】。
查找操作的性能分析:
衡量一个算法好坏的量度有三条：
时间复杂度(衡量算法执行的时间量级)；
空间复杂度(衡量算法的数据结构所占存储以及大量的附加存储)；
算法的其它性能。
对于查找算法来说，通常只需要一个或几个辅助空间。又，查找算法中的基本操作是“将记录的关键字和给定值进行比较”，因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。
定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。
对于含有n个记录的表，查找成功时的平均查找长度为
(9-1)
9.1.2 有序表的查找
以有序表表示静态查找表时，Search 函数可用折半查找来实现。
折半查找(BinarySearch)的查找过程是：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。
[例如]：已知如下11个数据元素的有序表(关键字即为数据元素的值)：
现要查找关键字为21和85的数据元素。
其中：Pi 为查找表中第i
个记录的概率，且；
Ci 为找到表中其关键字与给定值相等的第i 个记录时，和给定值已进行过比较的关键字个数。显然，Ci 随查找过程不同而不同。
假设n=ST.length ，则顺序查找的平均查找长度为
ASL=nP l +(n-1)P 2+…+2P n-1+P n (9-2)
假设每个记录的查找概率相等，即Pi=1/n ，则在等概率情况下顺序查找的平均查找长度为
有时，表中各个记录的查找概率并不相等。[例如]：将全校学生的病历档案建立一张表存放在计算机中，则体弱多病同学的病历记录的查找概率必定高于健康同学的病历记录。由于式(9—2)中的ASL 在Pn ≥Pn-1≥…≥P2≥P1时达到极小值。因此，对记录的查找概率不等的查找表若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列，以便提高查找效率。
然而，在一般情况下，记录的查找概率预先无法测定。为了提高查找效率，我们可以在每个记录中附设一个访问频度域，并使顺序表中的记录始终保持按访问频度非递减有序的次序排列，使得查找概率大的记录在查找过程中不断往后移，以便在以后的逐次查找中减少比较次数。或者在每次查找之后都将刚查找到的记录直接移至表尾。
顺序查找和我们后面将要讨论到的其它查找算法相比，其缺点是平均查找长度较大，特别是当n 很大时，查找效率较低。然而，它有很大的优点是：算法简单且适应面广。
假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即mid=(low+high)／2。在此例中，low和high的初值分别为1和11，即[1，11]为待查范围。
先看给定值key=21的查找过程：
ST.elem[mid].key与给定值key相比较，因为ST.elem[mid].key>key，说明待查元素若存在，必在区间[low，mid-1]的范围内，则令指针high指向第mid-1个元素，重新求得mid=(1+5)／2=3
仍以ST.elem[mid].key和key相比，因为ST.elem[mid].key 再看key=85的查找过程。 此时因为下界low>上界high，则说明表中没有关键字等于key的元素，查找不成功。 折半查找算法如下： int Search_Bin(SSTable ST，KeyType key){ //在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 low=1; high=ST.lenqth；//置区间初值 while (low<=high){ mid = (low+high)/2 if EQ(key, ST.elem[mid].key) return mid; //找到待查元素 else if LT(key, ST.elem.[mid].key) high = mid - 1; //继续在前半区间进行查找 else low = mid + 1; //继续在后半区间进行查找 } return 0; //顺序表中不存在待查元素 } //Search_Bin 9.1.3 静态树表的查找 上一小节对有序表的查找性能的讨论是在“等概率”的前提下进行的，即当有序表中各记录的查找概率相等时，按图9.2所示判定树描述的查找过程来进行折半查找，其性能最优。如果有序表中各记录的查找概率不等，情况又如何呢? 先看一个具体例子。假设有序表中含5个记录，并且已知各记录的查找概率不等，分别为p1=0.1，p2=0.2，p3=0.1，p4=0.4和p5=0.2。则按式(9-1)的定义，对此有序表进行折半查找，查 折半查找的性能分析: 先看上述11个元素的表的具体例子。 从上述查找过程可知：找到第⑥个元素仅需比较1次；找到第③和第⑨个元素需比较2次；找到第①、④、⑦和⑩个元素需比较3次；找到第②、⑤、⑧…需比较4次。这个查找过程可用图9.2所示的二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树，从判定树上可见，查找21的过程恰好是走了一条从根到结点④的路径，和给定值进行比较的关键字个数为该路径上的结点数或结点④在判定树上的层次数。 图9.2 描述查找过程的判定树 折半查找的平均查找长度是多少呢? 为讨论方便起见，假定有序表的长度，n=2k-1(反之，k=log2(n+1))，则描述折半查找的判定树是深度为k 的满二叉树。树中层次为1的结点有1个，层次为2的结点有 2个，…，层次为k 的结点有2k-1个。假设表中每个记录的查找概率相等(Pi=1/n)，则查找成功时折半查找的平均查找长度 对任意的n ，当n 较大(n>50)时，可有下列近似结果 ASL=log 2(n+1)-1 (9—6) 可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构(对线性链表无法进行折半查找)。以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有斐波那契查找和插值查找。 找成功时的平均查找长度为： 5 ∑PiCi = 0.1* 2+0.2* 3+0.1*1+0.4* 2+0.2* 3 = 2.3 i=1 但是，如果在查找时令给定值先和第4个记录的关键字 进行比较，比较不相等时再继续在左子序列或右子序列中 进行折半查找，则查找成功时的平均查找长度为： 5 ∑PiCi=0.1* 3+0.2* 2+0.1* 3+0.4*1+0.2* 2=1.8 i=1 这就说明，当有序表中各记录的查找概率不等时，按图9.2所示判定树进行折半查找，其性能未必是优的。那末此时应如何进行查找呢?换句话说，描述查找过程的判定树为何类二叉树时，其查找性能最佳? 如果只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和PH值 n PH=∑wihi (9-7) i=1 取最小值的二叉树。其中：n为二叉树上结点的个数(即有序表的长度)；hi为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1，2，…，n)，其中pi为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。由于构造静态最优查找树花费的时间代价较高，因此在此介绍一种构造近似最优查找树的有效算法。 已知一个按关键字有序的记录序列 (rl, rl+1, …, rh) (9-8) 其中 rl.key 与每个记录相应的权值为 wl, wl+1, …, wh (9-9) 现构造一棵二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树(Nearly Optimal Search Tree)。 构造次优查找树的方法是：首先在式(9—8)所示的记录序列中取第i(l≤i≤h)个记录构造根结点ri，使得 h i-1 △Pi=|∑wj-∑wj| (9-10) j=i+1 j=l 取最小值(△Pi=Min{△Pj})，然后分别对子序列{rl, rl+1,…ri-1}和{ri+1,..,rh} 两棵次优查找树，并分别设为根结点ri的左子树和右子树。 由于在构造次优查找树的过程中，没有考察单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与它相邻的关键字的权值小。此时应作适当调整：选取邻近的权值较大的关键字作次优查找树的根结点。 大量的实验研究表明，次优查找树和最优查找树的查找性能之差仅为1％~2％，很少超过3％，而且构造次优查找树的算法的时间复杂度为O (nlogn)，因此它是构造近似最优二叉查找树的有效算法。 9.1.4 索引顺序表的查找 若以索引顺序表表示静态查找表，则Search函数可用分块查找来实现。分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建守一个“索引表”。 [例如]，图8.6所示为一个表及其索引表，表中含有18个记录，可分成三个子表(Rl，R2，…，R6)、(R7，R8，…，R12)、(Rl3，Rl4，…R18)，对每个子表(或称块)建立一个索引项， 图9.6 其中包括两项内容：关键字项(其值为该子表内的最大关键字)和指针项(指示该子表的第一个记录在表中位置)。索引表按关键字有序，则表或者有序或者分块有序。 所谓“分块有序”指的是第i个子表中所有记录的关键字均大于第i-1个子表中的最大关键字。 因此，分块查找过程需分两步进行。先确定待查记录所在的块(子表)，然后在块中顺序查找。假设给定值key=38，则先将key依次和索引表中各最大关键字进行比较，因为22 由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找的算法即为这两种查找算法的简单合成。 分块查找的平均查找长度为ASL bs=Lb+Lw (9-14)，其中：Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的平均查找长度。 一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含有s个记录，即b=ceil(n/s) ；又假定表中每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。若用顺序查找确定所在块，此时的平均查找长度不仅和表长n有关，而且和每一块中的记录个数s有关。在给定n的前提下，s是可以选择的。容易证明，ASL比顺序查找有了很大改进，但远不及折半查找。若用折半查找确定所在块，则分块查找的平均查找长度可以得到提高。 9.2 动态查找表（2学时） 我们将讨论动态查找表的表示和实现。动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以下是动态查找表的定义。 抽象数据类型动态查找表的定义如下： ADT DynamicSearchTable { 数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(&DT)； 操作结果：构造—个空的动态查找表DT。 DestroyDSTable(&DT)； 初始条件：动态查找表DT 存在。操作结果：销毁动态查找表DT。 SearchDSTable(DT，key)； 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在关键字等于key的数据元素，则函数值为该元素值或在表中位置，否则为“空”。 InsertDSTable(&DT，e)； 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。 DeleteDSTable(&DT，key)； 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 TraverseDSTable(DT，Visit())； 初始条件：动态查找表DT存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦visit()败，则操作失败。 } ADT DynamicSearchTable 9.2.1 二叉排序树和平衡二叉树 一、二叉排序树及其查找过程 什么是二叉排序树? 二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。 二叉排序树又称二叉查找树，根据上述定义的结构特点可见，它的查找过程和次优二叉树类似。即当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。 通常，可取二叉链表作为二叉排序树的存储结构，则上述查找 过程如算法9.5(a)所描述。 BiTree SearchBST (BiTree T，KeyType key){ //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素 //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if( (!T)||EQ(key，T—>data.key)) return (T)；//查找结束 else if LT(key，T—>data.key) return(SearchBST(T—>lchild，key))；//在左子树中继续查找 else return(SearchBST(T —>rchild，key))；// 在右子树中继续查找 }//SearchBST 算法9．5(a ) 图9.7 二叉排序树示例 [例如]：在图9.7所示的二叉排序树中查找关键字等于100的记录（树中结点内的数均为记录的关键字）。首先以key=100和根结点的关键字比较，因为key>45，则查找以45为根的右子树，此时右子树不空，且key>53，则继续查找以53为根的右子树，由于key和53的右子树根的关键字100相等，则查找成功，返回指向结点100的指针值。 二、二叉排序树的插入和删除 和次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此，需将上一小节的二叉排序树的查找算法改写成算法9.5(b)，以便能在查找不成功时返回插入位置。插入算法如算法9.6所示。 Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree &p){ //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素， //若查找成功，则指针p指向该数据元素结点，并返回TRUE， //否则指针p指向查找路径上访问的最后一个结点并返回FALSE， //指针f指向T的双亲，其初始调用值为NULL if(!T) {p=f；return FALSE；} //查找不成功 else if EQ(key, T—>data.key) {p=T；return TRUE；} //查找成功 else if LT(key，T—>data.key) SearchBST(T—>lchild，key，T，p)；//在左子树中继续查找 else SearchBST(T—>rchild，key，T，p)；//在右子树中继续查找 }//SearchBST 算法9.5(b) Status Insert BST(BiTree &T，ElemType e){ //当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE，否则返回FALSE if(!SearchBST(T，e.key，NULL，p){ //查找不成功 s=(BiTree)malloc(sizeof(BiTNode))； s—>data=e；s—>lchild= s—>rchild=NULL； if (!p) T = s；//被插结点*s为新的根结点，原树为空 else if LT(e.key，p—>data.key) p—>lchild=s；//被插结点*s为左孩子 else p—>rchild=s //被插结点*s为右孩子 return TRUE； } else return FALSE; //树中已有关键字相同的结点，不再插入 }// Insert BST 算法9.6 若从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为{45，24，53，45，12，24，9}，则生成的二叉排序树如图9.8所示。 图9.8 二义排序树的构造过程 容易看出，中序遍历二叉排序树可得到一个关键字的有序序列(这个性质是由二叉排序树的定义决定的)。这就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。不仅如此，从上面的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其它记录。它表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。 同样，在二叉排序树上删去一个结点也很方便。删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。 那末，如何在二叉排序树上删去一个结点呢? 假设在二叉排序树上被删结点为*p(指向结点的指针为p)，其双亲结点为*f(结点指针为f)，且不失一般性，可设*p是*f的左孩子。 下面分三种情况进行讨论： (1)若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。 (2)若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。 (3)若*p结点的左子树和右子树均不空。显然，此时不能如上简单处理。从图9.9 (b)可知，在删去*p 结点之前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，在删去*p之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图9.9(c)所示；其二是令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。如图9.9(d)所示，当以直接前驱*s替代*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。 图9.9 在二叉排序树中删除*p (a)*f为根的子树；(b)删除*p之前；(c)删除*p之后，PR作为*s右子树的情形；(d)删除*p之后， *s替代的情形 三、二叉排序树的查找分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1(或结点所在层次数)，因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。 [例如]：图9.10中(a)和(b)的两棵二叉排序树中结点的值都相同，但前者由关键字序列(45，24，53，12，37，93)构成，而后者由关键字序列(12，24，37，45，53，93)构成。(a)树的深度为3，而(b)树的深度为6。 因此，含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉树蜕变为单枝树。树的深度为n，其平均查找长度和顺序查找相同，这是最差的情况。显然，最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n 成正比。 四、平衡二叉树 平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称A VL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的有子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。如图9.11(a)为两棵平衡二叉树，而图9.11(b)为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。 图9.11 平衡与不平衡的二叉树及结点的平衡因子 我们希望由任何初始序列构成的二叉排序树都是A VL树。因为A VL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(其中N为结点个数)。由此，它的平均查找长度也和logN同数量级。 如何使构成的二叉排序树成为平衡树呢?先看一个具体例子(参见图9.12)。假设表中关键字序列为(13，24，37，90，53)。 图8.12 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小根结点的指针为a(即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为下列四种情况： (1)单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。 (2)单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作。 (3)双向旋转(先左后右)平衡处理：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先左旋后右旋)操作。 (4)双向旋转(先右后左)子衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。 上述四种情况中，(1)和(3)对称，(2)和(4)对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序”证明之。无论哪一种情况，在经过平衡旋转处理之后，以*b或*c为根的新子树为平衡二叉树，而且它的深度和插入之前以*a为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。 在平衡二叉树上插入一个新的元素的递归算法描述及实现见课本P235~238。 9.2.2 B-树和B+树 一、B-树及其查找 B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍这种树的结构及其查找算法。 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树： (1)树中每个结点至多有m棵子树； (2)若根结点不是叶子结点，则至少有两棵子树； (3)除根之外的所有非终端结点至少有ceil(m／2)棵子树； (4)所有的非终端结点中包含下列信息数据(n, A0, K1, A1, K2, A2, …, Kn, An)； (5)所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。 例如图9.14所示为一棵4阶的B-树，其深度为4。 图9.14 一棵4阶的B-树 由此可见，在B-树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。 二、B-树的插入和删除 B-树的生成也是从空树起，逐个插入关键字而得。但由于B-树结点中的关键字个数必须≥ceil(m ／2)-1，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非 终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点 的“分裂”，如图9.16所示, 为3阶的B-树(图中略去F结点(即叶子结点))，假设需依次插入关键 字30，26，85和7。 图9.16 反之，若在B-树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除之，若该结点为最下层的非终端结点，且其中的关键字数目不少于ceil(m/2)，则删除完成，否则要进行“合并”结点的操作。假若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y替代Ki，然后在相应的结点中删去Y。例如，在图9.16(a)的B-树上删去45，可以*f结点中的50替代45，然后在*f结点中删去50。因此，下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下列三种可能： (1)被删关键字所在结点中的关键字数目不小于ceil(m/2)，则只需从该结点中删去该关键字Ki 和相应指针Ai，树的其它部分不变，例如，从图9.16(a)所示B-树中删去关键字12，删除后的B-树如图9.17(a)所示。 《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 数据结构 判断题 天涯古巷 出品 ( × ) 1. 数据元素是数据的最小单位。 ( × ) 2. 记录是数据处理的最小单位。 ( × ) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 ( × ) 4．算法的优劣与算法描述语言无关，但与所用计算机有关。 ( √ ) 5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 ( √ ) 6．数据的物理结构是指数据在计算机内的实际存储形式。 ( × ) 7. 数据结构的抽象操作的定义与具体实现有关。 第二章 ( × ) 1. 链表的每个结点中都恰好包含一个指针。 答：错，链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 ( × ) 2. 链表的物理存储结构具有同链表一样的顺序。 答：错，链表的存储结构特点是无序，而链表的示意图有序。 ( × ) 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 答：错，链表的结点不会移动，只是指针内容改变。 ( × ) 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 答：错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。( × ) 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 答：错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” ( × ) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 答：错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 ( × ) 7. 线性表在物理存储空间中也一定是连续的。 答：错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 ( × ) 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 答：错误。线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 ( × ) 9. 顺序存储方式只能用于存储线性结构。 答：错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） ( × ) 10. 线性表的逻辑顺序与存储顺序总是一致的。 答：错，理由同7。链式存储就无需一致。 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 树 一、填空题 1.不考虑顺序的3个结点可构成 2 种不同形态的树， 5 种不同形态的二叉树。 2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为： 6 。 3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是10 。 4.已知一棵完全二叉树中共有768个结点，则该树中共有384 个叶子结点。 5.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是27 ；结点i 的左孩子结点的编号是108 ，结点i的右孩子结点的编号是109 。 6.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是__10____；结点i 的左孩子结点编号是__40____，右孩子结点编号是__41____。 7.***一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中 所对应的结点一定。 8.***已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则 该树中含有的叶子结点的数目为n - (n-1)/k 。 9.在有n个叶子结点的Huffman树中，总的结点数是：__2N-1____。 10.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是 p->Lchild=NULL&&p->Rchild=NULL 。 11.具有n个结点的二叉树，采用二叉链表存储，共有__n-1___个空链域。 12.已知一棵二叉树的中序遍历结果为EFBCGHIDA，后序遍历结果为FEIHGDCBA，则该 二叉树的先序遍历序列结果为________________。 13.如果根的层次为1，具有61个结点的完全二叉树的高度为___6__。 14.深度为5的二叉树至多有__31__个结点。 15.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编 号，根结点编号为1，则编号最大的非叶结点的编号为：__50___。 16.在一棵深度为5的完全二叉树中，结点总数最少为___31__。 17.在树中，一个结点的直接孩子结点的个数称为该结点的___度_。 18.如果对于给定的一组权值，若构造出的二叉树的带权路径长度为最小，则该二叉树被称 为_____霍夫曼树或最有二叉树___。 19.一棵二叉树的结点数为33，则其最大的深度为_33最小深度为6___。 20.在树型结构中，树根结点没有__前驱_结点，其余每个结点有且仅有__一个前驱____； 叶子结点没有___后续___结点，其余每个结点的___后续___结点数不受限制。 二、单项选择题 1.树型结构的特点是：任意一个结点：（B ）。 A、可以有多个直接前趋 B、可以有多个直接后继 C、至少有1个前趋 D、只有一个后继 2.如下图所示的4棵二叉树中，（C ）不是完全二叉树。 A B C D 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node （A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点 数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打r 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是 ,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n) 堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout< 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 目录 第1章绪论............................................. 错误!未定义书签。第2章线性表........................................... 错误!未定义书签。第3章栈和队列......................................... 错误!未定义书签。第4章串、数组和广义表................................. 错误!未定义书签。第5章树和二叉树....................................... 错误!未定义书签。第6章图................................................ 错误!未定义书签。第7章查找............................................. 错误!未定义书签。第8章排序............................................. 错误!未定义书签。 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 学 《数据结构》课程 实验报告 实验名称：线性表基本操作的实现实验室(中心)： 学生信息： 专业班级： 指导教师： 实验完成时间： 2016 实验一线性表基本操作的实现 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件 计算机、Microsoft Visual C++ 6.0软件 四、设计方案（算法设计） ㈠采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 ㈡设计的主要思路 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 4.对前面建立的链表进行插入、删除及连个链表的连接操作； ㈢算法描述 1、顺序表 void Init(sqlist &);//初始化顺序表 BOOL Inse(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int Loc(sqlist,char); //在线性表中定位元素 void print(sqlist); //输出顺序表 void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并 2、链表 void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 五、程序代码 1、顺序表 #include 第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B 实验报告 实验一线性表 实验目的： 1.理解线性表的逻辑结构特性； 2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。 实验原理： 线性表顺序存储结构下的基本算法； 线性表链式存储结构下的基本算法； 实验内容： 2－21设计单循环链表，要求： （1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 （2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2－22 .设计一个有序顺序表，要求： （1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 （2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 （3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。 程序代码： 2－21（1）头文件LinList.h如下： typedef struct node { DataType data; struct node *next; }SLNode; /*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);《数据结构》第二章习题参考答案 殷人昆版
数据结构线性表实验报告
北林 数据结构期末考试(二) 判断题
数据结构第二章课后习题题解
数据结构_实验1_线性表的基本操作
19 非线性数据结构复习题
(完整版)数据结构课后习题及解析第二章
数据结构实验一题目一线性表实验报告
《数据结构》实验一 线性表及其应用
(完整版)数据结构第二章线性表1答案
数据结构考试试题
数据结构实验一题目一线性表实验报告
数据结构线性表的应用实验报告
数据结构第2版习题答案解析-严蔚敏
数据结构实验线性表基本操作
数据结构 线性表 课后答案
数据结构线性表实验报告
相关主题
文本预览