数据结构C语言版 第1章 绪论.ppt

第1章 绪论 ; 历史 1968年美国Stanford University的DONALD E.KNUTH（高德纳）教授开创了“数据结构”的最初体系。所著经典著作《TheArt of Computer Programming》，已出三卷，准备出七卷。; 随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。;1.1.1 数据结构的定义;1.1.1 数据结构的定义;1.1.1 数据结构的定义;1.1.1 数据结构的定义; 数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。 ; 数据结构： 是指数据以及数据元素相互之间的联系。 可以看作是相互之间存在着某种特定关系的数据元素的集合。 数据（D）：数据元素的有限集。 结构（R）：数据元素相互之间的关系，如集合、线性结构、树形结构、图结构。数据上关系的有限集。 数据结构（B）=（D,R） 可以把数据结构看成是带结构的数据元素的集合。; 例 有一个学生表如表1.1所示。这个表中的数据元素是学生记录，每个数据元素由四个数据项(即学号、姓别、性别和班号) 组成。;;【数据结构描述方法】 一、二元组 采用二元组表示描述数据结构： B=( D,R) 其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中： D={di| 1≤i≤n,n≥0} R={rj| 1≤j≤m,m≥0} ; 其中di表示集合D中的第i个结点或数据元素，n为D中结点的个数。 特别地，若n=0，则D是一个空集，因而B也就无结构可言，有时也可以认为它具有任一结构。 rj表示集合R中的第j个二元关系(后面均简称关系)，m为R中关系的个数。 特别地，若m=0，则R是一个空集，表明集合D中的元结点间不存在任何关系，彼此是独立的。; D上的一个关系r是序偶。 x,y (x，y∈D) x叫做序偶的第一结点，y叫做序偶的第二结点。 又称序偶的第一结点为第二结点的直接前驱结点(通常简称前驱结点)，称第二结点为第一结点的直接后继结点(通常简称后继结点)。如在x,y的序偶中,x为y的前驱结点,而y为x的后继结点。 若某个结点没有前驱,则称该结点为开始结点；若某个结点没有后继,则称该结点为终端结点。; 学生表中共有7个结点,依次用d1～d7表示,则对应的二元组表示为B=(D,R),其中： D={d1,d2,d3,d4,d5,d6,d7} R={d1,d2,d2,d3,d3,d4,d4,d5,d5,d6, d6,d7};又例如,有如下数据即一个矩阵： ;【数据结构描述方法】 二、图形 一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。 上述“学生表”数据结构用下图的图形表示。; 该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为： 1,8,8,34,34,20,20,12, 12,26,26,5 其中尖括号“ai,ai+1”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。; 上面我们讨论的数据元素之间的关系是在逻辑层面进行的。这是数据结构的一方面，称为逻辑结构。;(1)集合 该结构中的结点之间不存在对应的关系（0对0）。;(2)线性结构 所谓线性结构,该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。; (3) 树形结构线 所谓树形结构,该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点。非线性结构树形结构简称为树。 ; (4) 图形结构 所谓图形结构,该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此,可能没有开始结点和终端结点,也可能有多个开始结点、多个终端结点。图形结构简称为图。;【思考】 逻辑结构的研究是在逻辑层面进行的。这仅是数据结构的一方面。 然而，