第1章数据结构与算法 列的,在查找时可以利用这个特点,以便使比较次数大大减少。在有序表中查找一个数可以如 下进行: 16 6293 21 (a)无序表 (a)有序表 图1.1数据元素存放顺序不同的两个表 将被査数与表中的中间元素进行比较:若相等,则表示査找成功,查找过程结束;若被查 数大于表中的这个中间元素时,则表示如果被查数在表中的话,只能在表的后半部,此时可以 抛弃表的前半部而保留后半部;若被查数小于表中的这个中间元素,则表示如果被查数在表中 的话,只能在表的前半部,此时可以抛弃表的后半部而保留前半部。然后对剩下的部分(前半部 或后半部)再按照上述方法进行查找,这个过程一直做到在某一次的比较中相等(查找成功)或剩 下的部分已空(查找失败)为止。例如,如果要在图1.1(b)所示的有序表中查找54,则首先与中 间元素35进行比较,由于54大于35,再与后半部分的中间元素54进行比较,此时相等,共 比较了2次就查找成功。如果采用顺序查找法,在图1.1(a所示的无序表中查找54这个元素, 需要比较9次。这种查找方法称为有序表的对分查找。 显然,在有序表的对分查找中,不论查找的是什么数,也不论要查找的数在表中有没有 都不需要与表中所有的元素进行比较,只需要与表中很少的元素进行比较。但需要指出的是 对分查找只适用于有序表,而对于无序表是无法进行对分查找的 实际上,在日常工作和学习中也经常遇到对分查找。例如,当需要在词典中查找一个单词 时,一般不是从第一页开始一页一页的往后找,而是考虑到词典中的各单词是以英文字母为顺 序排列的,因此可以根据所査单词的第一个字母,直接翻到大概的位置,然后进行比较,根据 比较结果再向前或向后翻,直到找到该单词为止。这种在词典中查单词的方法类似于对分査找。 由这个例子可以看出,数据元素在表中的排列顺序对查找效率是有很大影响的。 例14设有一学生情况登记表如表1.1所示。在表1.1中,每个学生的情况是以学号为顺序 排列的。 显然,如果要在表1.1中查找给定学号的某学生的情况是很方便的,只要根据给定的学号 就可以立即找到该学生的情况。但是,如果要在该表中查找成绩在90分以上的所有学生的情况 则需要从头到尾扫描全表,才能将成绩在90分以上的所有学生找到。在这种情况下,为了找到 成绩在90分以上的学生情况,对于成绩在90分以下的所有学生情况也都要被扫描到。由此可 以看出,要在表1.1中查找给定学号的学生情况虽然很方便,但要查找成绩在某个分数段中的 学生情况时,实际上需要查看表中所有学生的成绩,其效率是很低的,尤其是当表很大时更为 突出
第 1 章 数据结构与算法 8 列的，在查找时可以利用这个特点，以便使比较次数大大减少。在有序表中查找一个数可以如 下进行： 35 16 78 85 43 29 33 21 54 46 16 21 29 33 35 43 46 54 78 85 (a)无序表 (a)有序表 图1.1 数据元素存放顺序不同的两个表 将被查数与表中的中间元素进行比较：若相等，则表示查找成功，查找过程结束；若被查 数大于表中的这个中间元素时，则表示如果被查数在表中的话，只能在表的后半部，此时可以 抛弃表的前半部而保留后半部；若被查数小于表中的这个中间元素，则表示如果被查数在表中 的话，只能在表的前半部，此时可以抛弃表的后半部而保留前半部。然后对剩下的部分(前半部 或后半部)再按照上述方法进行查找，这个过程一直做到在某一次的比较中相等(查找成功)或剩 下的部分已空(查找失败)为止。例如，如果要在图 1.1(b)所示的有序表中查找 54，则首先与中 间元素 35 进行比较，由于 54 大于 35，再与后半部分的中间元素 54 进行比较，此时相等，共 比较了 2 次就查找成功。如果采用顺序查找法，在图 1.1(a)所示的无序表中查找 54 这个元素， 需要比较 9 次。这种查找方法称为有序表的对分查找。 显然，在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有， 都不需要与表中所有的元素进行比较，只需要与表中很少的元素进行比较。但需要指出的是， 对分查找只适用于有序表，而对于无序表是无法进行对分查找的。 实际上，在日常工作和学习中也经常遇到对分查找。例如，当需要在词典中查找一个单词 时，一般不是从第一页开始一页一页的往后找，而是考虑到词典中的各单词是以英文字母为顺 序排列的，因此可以根据所查单词的第一个字母，直接翻到大概的位置，然后进行比较，根据 比较结果再向前或向后翻，直到找到该单词为止。这种在词典中查单词的方法类似于对分查找。 由这个例子可以看出，数据元素在表中的排列顺序对查找效率是有很大影响的。 例 1.4 设有一学生情况登记表如表 1.1 所示。在表 1.1 中，每个学生的情况是以学号为顺序 排列的。 显然，如果要在表 1.1 中查找给定学号的某学生的情况是很方便的，只要根据给定的学号 就可以立即找到该学生的情况。但是，如果要在该表中查找成绩在 90 分以上的所有学生的情况， 则需要从头到尾扫描全表，才能将成绩在 90 分以上的所有学生找到。在这种情况下，为了找到 成绩在 90 分以上的学生情况，对于成绩在 90 分以下的所有学生情况也都要被扫描到。由此可 以看出，要在表 1.1 中查找给定学号的学生情况虽然很方便，但要查找成绩在某个分数段中的 学生情况时，实际上需要查看表中所有学生的成绩，其效率是很低的，尤其是当表很大时更为 突出
第1章数据结构与算法 表1.1学生情况登记表 970156张小明男 6‖970163王伟男 970157李小青|女 19 83970164胡涛男 19 970158赵凯|男 19 70‖970165周敏女 20 87 970159李启明男 21 91‖970166杨雪辉|男 89 970160刘华女 18 781970167吕永华男 61 970161曾小波女 90‖970168梅玲女 970162张军男 8809069刘健男「2075 为了便于查找成绩在某个分数段中的学生情况,可以将表1.1中所登记的学生情况进行重 新组织。例如,将成绩在90分以上(包括90分,下同)、80~89分、70~79分、60~6分之间 的学生情况分别登记在四个独立的子表中,分别如表1.2、表1.3、表14与表1.5所示。现在如 果要查找90分以上的所有学生的情况,就可以直接在表12中进行查找,从而避免了对成绩在 90分以下的学生情况进行扫描,提高了查找效率 表1.2成绩在90分以上的学生情况登记表 号姓名性别年龄成绩 970159李 64胡涛男 19 95 97016 68梅玲 女 表1.3成绩在80~89分之间的学生情况登记表 姓名性别年龄成绩 970156张小明男 86970165周敏女 9015李小青女19 83970166杨雪辉|男 970162张军男 18 80 表14成绩在70~79分之间的学生情况登记表 学号姓名性别[年龄成绩|学号姓名性别年龄成绩 970158赵 男 19 70970169刘健 男 20 75 970160刘 女 1 8 表1.5成绩在60~69分之间的学生情况登记表 学号姓名性别年龄成绩[学号姓名性别年龄成 970163王伟男 497067吕永华男 由例1-4可以看出,在对数据进行处理时,可以根据所做的运算不同,将数据组织成不同 的形式,以便于做该种运算,从而提高数据处理的效率。 简单地说,数据结构是指相互有关联的数据元素的集合。例如,向量和矩阵就是数据结构
第 1 章 数据结构与算法 9 表 1.1 学生情况登记表 学 号 姓 名 性 别 年 龄 成 绩 学 号 姓 名 性 别 年 龄 成 绩 970156 张小明 男 20 86 970163 王 伟 男 20 65 970157 李小青 女 19 83 970164 胡 涛 男 19 95 970158 赵 凯 男 19 70 970165 周 敏 女 20 87 970159 李启明 男 21 91 970166 杨雪辉 男 22 89 970160 刘 华 女 18 78 970167 吕永华 男 18 61 970161 曾小波 女 19 90 970168 梅 玲 女 17 93 970162 张 军 男 18 80 970169 刘 健 男 20 75 为了便于查找成绩在某个分数段中的学生情况，可以将表 1.1 中所登记的学生情况进行重 新组织。例如，将成绩在 90 分以上(包括 90 分，下同)、80～89 分、70～79 分、60～69 分之间 的学生情况分别登记在四个独立的子表中，分别如表 1.2、表 1.3、表 1.4 与表 1.5 所示。现在如 果要查找 90 分以上的所有学生的情况，就可以直接在表 1.2 中进行查找，从而避免了对成绩在 90 分以下的学生情况进行扫描，提高了查找效率。 表 1.2 成绩在 90 分以上的学生情况登记表 学 号 姓 名 性 别 年 龄 成 绩 学 号 姓 名 性 别 年 龄 成 绩 970159 李启明 男 21 91 970164 胡涛 男 19 95 970161 曾小波 女 19 90 970168 梅玲 女 17 93 表 1.3 成绩在 80～89 分之间的学生情况登记表 学 号 姓 名 性 别 年 龄 成 绩 学 号 姓 名 性 别 年 龄 成 绩 970156 张小明 男 20 86 970165 周 敏 女 20 87 970157 李小青 女 19 83 970166 杨雪辉 男 22 89 970162 张 军 男 18 80 表 1.4 成绩在 70～79 分之间的学生情况登记表 学 号 姓 名 性 别 年 龄 成 绩 学 号 姓 名 性 别 年 龄 成 绩 970158 赵 凯 男 19 70 970169 刘健 男 20 75 970160 刘 华 女 18 78 表 1.5 成绩在 60～69 分之间的学生情况登记表 学 号 姓 名 性 别 年 龄 成 绩 学 号 姓 名 性 别 年 龄 成 绩 970163 王 伟 男 20 65 4970167 吕永华 男 18 61 由例 1-4 可以看出，在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同 的形式，以便于做该种运算，从而提高数据处理的效率。 简单地说，数据结构是指相互有关联的数据元素的集合。例如，向量和矩阵就是数据结构
第1章数据结构与算法 在这两个数据结构中,数据元素之间有着位置上的关系。又如,图书馆中的图书卡片目录,则 是一个较为复杂的数据结构,对于列在各卡片上的各种书之间,可能在主题、作者等问题上相 互关联,甚至一本书本身也有不同的相关成分 数据元素具有广泛的含义。一般来说,现实世界中客观存在的一切个体都可以是数据元素 例如 描述一年四季的季节名 春、夏、秋、冬 可以作为季节的数据元素 表示数值的各个数 18、11、35、23、16 可以作为数值的数据元素 表示家庭成员的各成员名 父亲、儿子、女儿 可以作为家庭成员的数据元素 甚至每一个客观存在的事件,如一次演出、一次借书、一次比赛等也可以作为数据元素。 总之,在数据处理领域中,每一个需要处理的对象都可以抽象成数据元素。数据元素一般 简称为元素 在实际应用中,被处理的数据元素一般有很多,而且,作为某种处理,其中的数据元素 般具有某种共同特征。例如,{春,夏,秋,冬)这四个数据元素有一个共同特征,即它们都是 季节名,分别表示了一年中的四个季节,从而这四个数据元素构成了季节名的集合。又如,{父 亲,儿子,女儿)这三个数据元素也有一个共同特征,即它们都是家庭的成员名,从而构成了家 庭成员名的集合。一般来说,人们不会同时处理特征完全不同且互相之间没有任何关系的各类 数据元素,对于具有不同特征的数据元素总是分别进行处理。 一般情况下,在具有相同特征的数据元素集合中,各个数据元素之间存在有某种关系(即联 系),这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中,通常把数据 元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。 例如,在考虑一年四个季节的顺序关系时,则“春”是“夏”的前件(即直接前驱,下 而“夏”是“春”的后件(即直接后继,下同)。同样,“夏”是“秋”的前件,“秋”是“ 的后件;“秋”是“冬”的前件,“冬”是“秋”的后件。 在考虑家庭成员间的辈分关系时,则“父亲”是“儿子”和“女儿”的前件,而“儿子” 与“女儿”都是“父亲”的后件 前后件关系是数据元素之间的一个基本关系,但前后件关系所表示的实际意义随具体对象 的不同而不同。一般来说,数据元素之间的任何关系都可以用前后件关系来描述 1数据的逻辑结构 前面提到,数据结构是指反映数据元素之间关系的数据元素集合的表示。更通俗地说,数 据结构是指带有结构的数据元素的集合。在此,所谓结构实际上就是指数据元素之间的前后件 关系 由上所述,一个数据结构应包含以下两方面的信息 ①表示数据元素的信息 ②表示各数据元素之间的前后件关系。 在以上所述的数据结构中,其中数据元素之间的前后件关系是指它们的逻辑关系,而与它
第 1 章 数据结构与算法 10 在这两个数据结构中，数据元素之间有着位置上的关系。又如，图书馆中的图书卡片目录，则 是一个较为复杂的数据结构，对于列在各卡片上的各种书之间，可能在主题、作者等问题上相 互关联，甚至一本书本身也有不同的相关成分。 数据元素具有广泛的含义。一般来说，现实世界中客观存在的一切个体都可以是数据元素。 例如： 描述一年四季的季节名 春、夏、秋、冬 可以作为季节的数据元素； 表示数值的各个数 18、11、35、23、16、… 可以作为数值的数据元素； 表示家庭成员的各成员名 父亲、儿子、女儿 可以作为家庭成员的数据元素。 甚至每一个客观存在的事件，如一次演出、一次借书、一次比赛等也可以作为数据元素。 总之，在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数据元素一般 简称为元素。 在实际应用中，被处理的数据元素一般有很多，而且，作为某种处理，其中的数据元素一 般具有某种共同特征。例如，{春，夏，秋，冬)这四个数据元素有一个共同特征，即它们都是 季节名，分别表示了一年中的四个季节，从而这四个数据元素构成了季节名的集合。又如，{父 亲，儿子，女儿)这三个数据元素也有一个共同特征，即它们都是家庭的成员名，从而构成了家 庭成员名的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类 数据元素，对于具有不同特征的数据元素总是分别进行处理。 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系(即联 系)，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据 元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。 例如，在考虑一年四个季节的顺序关系时，则“春”是“夏”的前件(即直接前驱，下同)， 而“夏”是“春”的后件(即直接后继，下同)。同样，“夏”是“秋”的前件，“秋”是“夏” 的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。 在考虑家庭成员间的辈分关系时，则“父亲”是“儿子”和“女儿”的前件，而“儿子” 与“女儿”都是“父亲”的后件。 前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象 的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。 1.数据的逻辑结构 前面提到，数据结构是指反映数据元素之间关系的数据元素集合的表示。更通俗地说，数 据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件 关系。 由上所述，一个数据结构应包含以下两方面的信息： ①表示数据元素的信息； ②表示各数据元素之间的前后件关系。 在以上所述的数据结构中，其中数据元素之间的前后件关系是指它们的逻辑关系，而与它
第1章数据结构与算法 们在计算机中的存储位置无关。因此,上面所述的数据结构实际上是数据的逻辑结构。 所谓数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构 由前面的叙述可以知道,数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D 二是D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R。即一个数据结构 可以表示成 B=(D, R) 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。 例如,假设a与b是D中的两个数据,则二元组(a,b)表示a是b的前件,b是a的后件。这样 在D中的每两个元素之间的关系都可以用这种二元组来表示。 例1.5一年四季的数据结构可以表示成 D={春,夏,秋,冬} (春,夏)夏,秋)(秋,冬) 例16家庭成员数据结构可以表示成 B=(D, R) D={父亲,儿子,女儿} R={父亲,儿子)(父亲,女儿 例1.7n维向量 X=( 也是一种数据结构。即X=(D,R),其中数据元素的集合为 D={x12x2;…,xn} 关系为 R={(x1,x2),(x2,x3),…(xn1,xn) 对于一些复杂的数据结构来说,它的数据元素可以是另一种数据结构。 例如,m×n的矩阵 au a A 是一个数据结构。在这个数据结构中,矩阵的每一行 可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为 D={A1,A2…,An} 11
第 1 章 数据结构与算法 11 们在计算机中的存储位置无关。因此，上面所述的数据结构实际上是数据的逻辑结构。 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。 由前面的叙述可以知道，数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D； 二是 D 上的关系，它反映了 D 中各数据元素之间的前后件关系，通常记为 R。即一个数据结构 可以表示成 B=(D，R) 其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系，一般用二元组来表示。 例如，假设 a 与 b 是 D 中的两个数据，则二元组(a，b)表示 a 是 b 的前件，b 是 a 的后件。这样， 在 D 中的每两个元素之间的关系都可以用这种二元组来表示。 例 1.5 一年四季的数据结构可以表示成 R {( ) ( ) ( )} D { B (D R) 春，夏 ，夏，秋 ，秋，冬 春，夏，秋，冬 ， = = = 例 1.6 家庭成员数据结构可以表示成 R {( ) ( )} D { B (D R) 父亲，儿子 ，父亲，女儿 父亲，儿子，女儿 ， = = = 例 1.7 n 维向量 ( , , , ) 1 2 n X = x x x 也是一种数据结构。即 X=(D，R)，其中数据元素的集合为 { , , , } 1 2 n D = x x x 关系为 {( , ),( , ), ,( , )} 1 2 2 3 n 1 n R x x x x x x = − 对于一些复杂的数据结构来说，它的数据元素可以是另一种数据结构。 例如，m×n 的矩阵 = m m mn n n a a a a a a a a a A 1 2 21 22 2 11 12 1 是一个数据结构。在这个数据结构中，矩阵的每一行 Ai = (ail ,ai2 , ,ain ),i =1,2, ,m 可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为 { , , , } D = A1 A2 Am
第1章数据结构与算法 D上的一个关系为 R={(A1,A2),(42,A3),…,(42,A1)…(An1,An)} 显然,数据结构A中的每一个数据元素A(=1,2,…,m)又是另一个数据结构,即数据 素的集合为 Di上的一个关系为 R={(an1,a12).(a2,a3)…(an3a,+1)…(a,n-1,an)} 2数据的存储结构 数据处理是计算机应用的一个重要领域,在实际进行数据处理时,被处理的各数据元素总 是被存放在计算机的存储空间中,并且,各数据元素在计算机存储空间中的位置关系与它们的 逻辑关系不一定是相同的,而且一般也不可能相同。例如,在前面提到的一年四个季节的数据 结构中,“春”是“夏”的前件,“夏”是“春”的后件,但在对它们进行处理时,在计算机存 储空间中,“春”这个数据元素的信息不一定被存储在“夏”这个数据元素信息的前面,而可能 在后面,也可能不是紧邻在前面,而是中间被其他的信息所隔开。又如,在家庭成员的数据结 构中,“儿子”和“女儿”都是“父亲”的后件,但在计算机存储空间中,根本不可能将“儿子” 和“女儿”这两个数据元素的信息都紧邻存放在“父亲”这个数据元素信息的后面,即在存储 空间中与“父亲”紧邻的只可能是其中的一个。由此可以看出,一个数据结构中的各数据元素 在计算机存储空间中的位置关系与逻辑关系是有可能不同的 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结 构)。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放 在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不 仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息 一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺 序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在 进行数据处理时,选择合适的存储结构是很重要的 122数据结构的图形表示 一个数据结构除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图形表示 中,对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点 并简称为结点:为了进一步表示各数据元素之间的前后件关系,对于关系R中的每一个二元组 用一条有向线段从前件结点指向后件结点。 父亲 春夏秋冬 儿子 女儿 图12一年四季数据结构的图形表示图1.3家庭成员间辈分关系数据结构的图形表示
第 1 章 数据结构与算法 12 D 上的一个关系为 {( , ),( , ), ,( , ), ,( , )} R = A1 A2 A2 A3 Ai Ai+1 Am−1 Am 显然，数据结构 A 中的每一个数据元素 A(i=1，2，…，m)又是另一个数据结构，即数据元 素的集合为 { , , , } Di = ai1 ai2 ain Di 上的一个关系为 {( , ),( , ), ,( , ), ,( , )} Ri = ai1 ai2 ai2 ai3 ai j ai, j+1 ai,n−1 ai n 2.数据的存储结构 数据处理是计算机应用的一个重要领域，在实际进行数据处理时，被处理的各数据元素总 是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置关系与它们的 逻辑关系不一定是相同的，而且一般也不可能相同。例如，在前面提到的一年四个季节的数据 结构中，“春”是“夏”的前件，“夏”是“春”的后件，但在对它们进行处理时，在计算机存 储空间中，“春”这个数据元素的信息不一定被存储在“夏”这个数据元素信息的前面，而可能 在后面，也可能不是紧邻在前面，而是中间被其他的信息所隔开。又如，在家庭成员的数据结 构中，“儿子”和“女儿”都是“父亲”的后件，但在计算机存储空间中，根本不可能将“儿子” 和“女儿”这两个数据元素的信息都紧邻存放在“父亲”这个数据元素信息的后面，即在存储 空间中与“父亲”紧邻的只可能是其中的一个。由此可以看出，一个数据结构中的各数据元素 在计算机存储空间中的位置关系与逻辑关系是有可能不同的。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结 构)。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放 在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系)，在数据的存储结构中，不 仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺 序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在 进行数据处理时，选择合适的存储结构是很重要的。 1.2.2 数据结构的图形表示 一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示 中，对于数据集合 D 中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点， 并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系 R 中的每一个二元组， 用一条有向线段从前件结点指向后件结点。 春 夏 秋 冬 图 1.2 一年四季数据结构的图形表示 父亲 儿子 女儿 图 1.3 家庭成员间辈分关系数据结构的图形表示