第2章 基本数据结构2.1

1、计算机系教研室软件技术基础软件技术基础青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础2 2第二章第二章 基本数据结构及其运算基本数据结构及其运算v 2.1 2.1 数据结构的基本概念数据结构的基本概念v 2.2 线性表及其顺序存储结构v 2.3 线性链表及其运算v 2.4 树与二叉树数据库应用基础青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础2.1 数据结构的基本概念本次课主要内容本次课主要内容v 2.1.1 2.1.1 两个例子两个例子v 2.1.2 什么是数据结构v 2.1.3 数据结构的图形表示v 2.1.4 线性数据结构与非线性数据结构第2章 基本数

2、据结构及其运算3青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 数据结构三个方面的问题：v(1)数据的逻辑结构v数据元素之间存在的固有的逻辑关系v(2)数据的存储结构v数据元素及其关系在计算机中的表示v(3)对各种数据结构进行的运算v在数据的逻辑结构上定义的操作算法，如插入、删除、查询等v 目的：提高数据处理的效率v提高数据处理的速度v尽量节省计算机存储空间 第2章 基本数据结构及其运算42.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 2.1.1 两个例子v 计算机已广泛应用于数据处理。实际问题中的各数据元素之间总是相互关联的。

3、v 所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，以包括对数据元素进行分析。第2章 基本数据结构及其运算52.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 重要的是知道数据集合中各数据元素之间存在什么关系，为了提高处理效率，应如何组织它们，即如何表示所需要处理的数据元素。v 数据v是用来描述现实世界的数字、字符、图像、声音，以及能够输入到计算机中并能被计算机处理的符号集合。第2章 基本数据结构及其运算62.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 例2.1

4、无序表的顺序查找v35 16 78 85 43 29 33 21 54 46v 有序表的对分查找v16 21 29 33 35 43 46 54 78 85v数据元素在表中的排列顺序对查找效率是有很大影响第2章 基本数据结构及其运算72.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础无序表的顺序查找无序表的顺序查找v 从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素都与被查数进行了比较且都不相等（即查找失败）为止。v 最少次数：被查元素刚好是表中第一个元素时。只需比较一次。v 最多次数：被查

5、元素刚好是表中最后一个元素时或表中不存在被查元素。在这种情况下顺序查找是很费时间的。第2章 基本数据结构及其运算82.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础有序表中的二分查找有序表中的二分查找v 将被查数与表中的中间这个元素进行比较：若相等，则表示查找成功，查找过程结束；若被查数大于表中的中间这个元素，则表示如果被查数在表中，只能在表的后半部，此时可以舍弃表中的前半部保留后半部；若被查数小于表中的中间元素，则表示如果被查数在表中，只能在表的前半部此时可以舍弃后半部而保留前半部。然后对剩下部分再按照上述方法进行查找，这个过程一直做到在某次的比较中相

6、等（查找成功）或剩下的部分已空（查找失败）为止。第2章 基本数据结构及其运算92.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有，都不需要与表中所有元素进行比较，并且只需要与表中很少的元素进行比较。但需要指出的是，对分查找只适用于有序表，而对于无序表是无法进行对分查找的。第2章 基本数据结构及其运算102.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础第2章 基本数据结构及其运算11例例2.2 2.2 学生情况登记表以学号为顺序排列学生情况登

7、记表以学号为顺序排列2.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础第2章 基本数据结构及其运算122.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础第2章 基本数据结构及其运算132.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 结论：v 在对数据进行处理时，v 可以根据所做的运算不同，v 将数据组织成不同的形式，v 以便于做该种运算，v 从而提高数据处理的效率。第2章 基本数据结构及其运算142.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术

8、基础软件技术基础v 2.1.2 什么是数据结构v v 数据结构是指相互有关联的数据元素集合。v v 现实世界中客观存在的一切个体都可以是数据元素。第2章 基本数据结构及其运算152.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 描述一年四季的季节名v 春，夏，秋，冬v 可以作为季节的数据元素；v 表示数值的各个数v 18，11，35，23，16，v 可以作为数值的数据元素；v 表示家庭成员的各成员名v 父亲，儿子，女儿v 可以作为家庭成员的数据元素。第2章 基本数据结构及其运算162.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件

9、技术基础软件技术基础v 前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。v 一般来说，数据元素之间的任何关系都可以用前后件关系来描述。v 例如：“春” 是“夏”的前件，“夏”是“春”的后件。v “父亲”是“儿子”，“女儿”的前件， “儿子”，“女儿”是“父亲”的后续。第2章 基本数据结构及其运算172.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 1.数据的逻辑结构v 是指反映数据元素之间逻辑关系的数据结构。v （1）表示数据元素的信息；v （2）表示各数据元素之间的前后件关系。第2章 基本数据结构及其运

10、算182.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 数据的逻辑结构有两个要素：v数据元素的集合D；v反映D中各数据元素之间的前后件关系R。v v 数据结构可以表示成v B（D，R）v 其中B表示数据结构。第2章 基本数据结构及其运算192.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。v 设a与b是D中的两个数据，则二元组v （a，b）v 表示a是b的前件，b是a的后件。v 例如v B（D，R）v D春，夏，秋，冬v R(春，夏)，(夏，秋)，

11、(秋，冬)第2章 基本数据结构及其运算202.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 家庭成员数据结构v B（D，R）v D父亲，儿子，女儿v R(父亲，儿子），(父亲，女儿）v n维向量 X（x1，x2，xn）v 也是一种数据结构。即v X（D，R）v Dx1，x2，xnv R(x1，x2)，(x2，x3)，(xn1，xn)第2章 基本数据结构及其运算212.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v mn的矩阵是一个数据结构。即v A（D，R）v DA1，A2，Amv R(A1，A2)，(A2，

12、A3)，(Ai，Ai1)，(Am1，Am)v 其中Ai=（ai1，ai2，ain），i1，2，mv Ai（Di，Ri）v Diai1，ai2，ainv Ri(ai1，ai2)，(ai2，ai3)，(aij，ai，j1)，(ai，n1，ain)第2章 基本数据结构及其运算222.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 2.数据的存储结构（数据的物理结构）v 数据的逻辑结构在计算机存储空间中的存放形式。v 常用的存储结构有：v 顺序、链接、索引等存储结构。v 采用不同的存储结构，其数据处理的效率是不同的。第2章 基本数据结构及其运算232.1 数据

13、结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 2.1.3 数据结构的图形表示v数据集合D中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点）v用一条有向线段从前件结点指向后件结点。第2章 基本数据结构及其运算242.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 一年四季数据结构的图形表示第2章 基本数据结构及其运算252.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v家庭成员间辈份关系数据结的图形表示第2章 基本数据结构及其运算262.1 数据结构的基本概念青海大

14、学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v DS1=(D1,R1)v D1=a,b,c,d,ev R1=(a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)第2章 基本数据结构及其运算27daebcDS1是个无向图是个无向图2.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v DS2=(D2,R2)v D2=a,b,c,d,ev R2=(a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)第2章 基本数据结构及其运算28daebcD

15、S2是一个有向图是一个有向图2.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础vDS2=(D2,R2)vD2=a1,a2,a3,akvR2=| 11ki第2章 基本数据结构及其运算29这说明这个关系这说明这个关系R2任何两递增下标的数据元任何两递增下标的数据元素都有相邻关系，如图所示素都有相邻关系，如图所示a1a2a3ak数组的数据结构数组的数据结构2.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 用图形表示数据结构B（D，R）vDdi |1i7d1，d2，d3，d4，d5，d6，d7vR(d1，d3)，(d1

16、，d7)，(d2，d4)，(d3 ，d6) ，(d4 ，d5 ) 第2章 基本数据结构及其运算302.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点（也称为叶子结点）；除了根结点与终端结点外的其他结点一般称为内部结点。v 数据结构中的相关运算：v 插入运算、删除运算。这两个运算是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。v 在一个数据结构中元素结点和数据元素之间的关系都可能是动态变化的。第2章 基本数据结构及其运算312.1 数据结构

17、的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v 2.1.4 线性数据结构与非线性数据结构v 线性表的逻辑结构是n个数据元素的有限序列(a1,a2,a3,an)v 其中n表示了线性表的长度（n=0）.n=0的表称为空表。v 线性结构：数据元素呈线性关系。隐含有序。v （1）有且只有一个根结点；v （2）每一个结点最多有一个前件，v 也最多有一个后件。v 线性结构又称线性表。第2章 基本数据结构及其运算322.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础特别说明特别说明v v 在一个线性结构中插入或删除任何一个结点后还应该是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。第2章 基本数据结构及其运算332.1 数据结构的基本概念青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础v不是线性结构的数据结构特例第2章 基本数据结构及其运算342.1 数据结构的基本概念v 如果一个数据结构不是线性结构，v 则称之为非线性结构青海大学课程建设项目青海大学课程建设项目软件技术基础软件技术基础实验二实验二