基本数据结构修改

《基本数据结构修改》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4树与二叉树2.1数据结构的基本概念2.1.1两个例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构2第2章基本数据结构及其运算数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间3第2章基本数据结构及其运算2.1.1两个例子计算机已广泛应用于数据处

2、理。实际问题中的各数据元素之间总是相互关联的。所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，以包括对数据元素进行分析。4第2章基本数据结构及其运算重要的是知道数据集合中各数据元素之间存在什么关系，为了提高处理效率，应如何组织它们，即如何表示所需要处理的数据元素。5第2章基本数据结构及其运算例2.1无序表的顺序查找35167885432933215446有序表的对分查找16212933354346547885数据元素在表中的排列顺序对查找效率是有很大影响6

3、第2章基本数据结构及其运算无序表的顺序查找从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素都与被查数进行了比较且都不相等（即查找失败）为止。最少次数：被查元素刚好是表中第一个元素时。只需比较一次。最多次数：被查元素刚好是表中最后一个元素时或表中不存在被查元素。在这种情况下顺序查找是很费时间的。7第2章基本数据结构及其运算有序表中的二分查找将被查数与表中的中间这个元素进行比较：若相等，则表示查找成功，查找过程结束；若被查数大于表中的中间这

4、个元素，则表示如果被查数在表中，只能在表的后半部，此时可以舍弃表中的前半部保留后半部；若被查数小于表中的中间元素，则表示如果被查数在表中，只能在表的前半部此时可以舍弃后半部而保留前半部。然后对剩下部分再按照上述方法进行查找，这个过程一直做到在某次的比较中相等（查找成功）或剩下的部分已空（查找失败）为止。8第2章基本数据结构及其运算在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有，都不需要与表中所有元素进行比较，并且只需要与表中很少的元素进行比较。但需要指出的是，对分查找只适用于

5、有序表，而对于无序表是无法进行对分查找的。9第2章基本数据结构及其运算例2.2学生情况登记表以学号为顺序排列10第2章基本数据结构及其运算11第2章基本数据结构及其运算12第2章基本数据结构及其运算结论：在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同的形式，以便于做该种运算，从而提高数据处理的效率。13第2章基本数据结构及其运算2.1.2什么是数据结构数据结构是指相互有关联的数据元素集合。现实世界中客观存在的一切个体都可以是数据元素。14第2章基本数据结构及其运算描述一年四季的季节名春

6、，夏，秋，冬可以作为季节的数据元素；表示数值的各个数18，11，35，23，16，…可以作为数值的数据元素；表示家庭成员的各成员名父亲，儿子，女儿可以作为家庭成员的数据元素。15第2章基本数据结构及其运算前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。例如：“春”是“夏”的前件，“夏”是“春”的后件。“父亲”是“儿子”，“女儿”的前件，“儿子”，“女儿”是“父亲”的后续。16第2章基本数据结构及其

7、运算1.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。17第2章基本数据结构及其运算数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。数据结构可以表示成B＝（D，R）其中B表示数据结构。18第2章基本数据结构及其运算为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例如B＝（D，R）D＝{春，夏，秋，冬}R＝{(

8、春，夏)，(夏，秋)，(秋，冬)}19第2章基本数据结构及其运算家庭成员数据结构B＝（D，R）D＝{父亲，儿子，女儿}R＝{(父亲，儿子），(父亲，女儿）}n维向量X＝（x1，x2，…，xn）也是一种数据结构。即X＝（D，R）D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}20第2章基本数据结构及其运算m×n的矩阵是一个数据结构。即A＝（D，R）D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai