会计学第2章数据(shùjù)的线性结构②组织(zǔzhī)成一棵树例2、在n个城市(chéngshì)间建立通信网络从上面两个例子中可以看出：数据结构中元素之间存在着逻辑关系，上述例子中给出了三种逻辑结构－－线性表、树、图。数据结构主要解决：如何分析数据元素之间的关系，并确定合适的逻辑结构；如何在计算机中存储这些数据；为完成对数据的操作设计(shèjì)算法，并作出分析。二、概念和术语数据(data)：表示现实世界中的客观事物、能输入计算机并能被计算机程序处理的符号的总称。数据元素(dataelement)：数据集合中的一个个体，是数据的基本单位。(亦称为结点、记录等)数据项(dataitem)：数据的不可分割的、含有独立意义的最小单位。数据对象(dataobject)：性质(xìngzhì)相同的数据元素的集合。数据结构(datastructure)：相互之间存在着一种或多种关系的数据元素的集合。数据结构无公认定义，都认为(rènwéi)其研究涉及三个方面：数据元素间的逻辑关系(逻辑结构)数据元素的存储方式(物理结构)数据元素间的运算(操作)一般地，一个数据结构中的数据元素属于同一个数据对象。2.1.2数据的逻辑结构和存储方法一、数据的逻辑结构逻辑结构是指数据元素之间的特定(tèdìng)关系，它独立于计算机，是元素之间关系的抽象。1、定义数据结构是一个二元组B=(D，R)。其中D是数据元素(即结点)的有限集合；R是D上的关系的有限集合。一般R中只涉及一种关系。例如：有4个人，为别为a、b、c、d，其中a是b的父亲，b是c的父亲，c是d的父亲，如果只讨论他们(tāmen)所表达的父子关系，则可以用下面的二元组形式化地表示为：B＝(D，R)其中D={a，b，c，d}R={r}r={<a,b>，<b,c>，<c,d>}又如:另有4个人，分别为e,f,g,h；其中e是f和g的父亲，g是h的父亲，则可用下面(xiàmian)的二元组形式化地表示为：B＝(D，R)其中D={e，f，g，h}R={r}r={<e,f>，<e,g>，<g,h>}可以(kěyǐ)用图形方式分别表示为：2、几个概念设B=(D，R)是一个(yīɡè)逻辑结构，r∈R，di、dj∈D。如果<di,dj>∈r，则称di是dj的前驱，dj是di的后继。如果某个结点没有前驱，则称之为开始结点；如果某个结点没有后继，则称之为终端结点；既非开始结点，也非终端结点的结点称之为内部结点。3、结构分类①线性结构只有一个开始结点和一个终端结点，其它结点只有一个前驱结点和一个后继(hòujì)结点，称之为线性结构。即元素之间存在着一对一的关系。②非线性结构如果一个结构不是线性结构，则称之为非线性结构。一般地，结构中至少有一个结点存在不止一个前驱结点或后继(hòujì)结点。非线性结构有两类：a、树形结构：元素之间存在着一对多的关系。b、图形结构：元素之间存在着多对多的关系。二、数据的存储方法一般地，数据的存储方法有四种：顺序存储链式存储索引存储散列存储（后两种方法主要用于查找(cházhǎo)，本课程不作详述）1、顺序存储把逻辑上相邻的数据元素存储在物理位置相邻的存储单元之中。通常借助于程序设计语言中的数组来实现(shíxiàn)。2、链式存储逻辑上相邻的数据元素不要求其物理存储位置相邻，元素间的逻辑关系用附设的指针域来表示。通常借助于程序设计语言中的指针来实现(shíxiàn)。例如：有数据结构(jiégòu)B=(D，R)，其中D={d1,d2,d3,d4,d5}R={r}r={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>}则用上述两种存储结构(jiégòu)表示为：┊链式存储(cúnchǔ)图示为：2.2线性表的基本概念一、线性表的定义它是最常用且又最简单(jiǎndān)的线性结构。定义：线性表是n(n≥0)个性质相同的数据元素所构成的有限序列(a1,a2,a3,….,an)。n称为线性表的长度。当n=0时，称为空表。数据元素可以是很简单(jiǎndān)的整数、英文字母等，也可以是较复杂的元素。由复杂元素构成的线性表又称为文件，复杂数据元素称为记录。例如：（1，2，7，5，3，9）(A，D，C，B，E)二、线性表的基本运算线性表的初始化（构造一个空的线性表）求表长取第i个数据元素查找具有特定值的结点，确定其序号插入操作（在原表的第i个位置上插入新元素）删除操作（删除原表中第i个元素）┇随着线性表的存储方法不同，各种运算的实现(shíxiàn)方法也不一样。下面结合线性表的不同存储结构，讨论实现(shíxi