2-第二章 基本数据结构及其运算-线性表&线性链表.ppt

《2-第二章 基本数据结构及其运算-线性表&线性链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章基本数据结构及其运算线性表；线性链表；数组；树；图第二章基本数据结构第二章基本数据结构及运算1数据结构的基本概念2线性表及其顺序存储结构3线性链表及其运算4数组5树与二叉树6图第二章基本数据结构2.1数据结构基本概念数据结构：逻辑结构、存储结构、运算第二章基本数据结构1.数据结构举例无序表和有序表1621293335434654788535167885432933215446有序表无序表第二章基本数据结构1.数据结构举例学生成绩表：第二章基本数据结构1.数据结构举例树结构一层二层三层四层第二章基本数据结构图结构第二章基本数据结构1.数据结构举例2.什么是数据结构－－是

2、指相互有关联的数据元素的集合。定义理解数据结构＝数据元素＋前后件关系数据元素（dataelement）：是组成数据的基本单位。前后件关系：数据元素的任何关系都可以用前后件关系来描述举例：E.g.1一年四季数据结构；E.g.2家庭成员数据结构；第二章基本数据结构3.数据结构的内涵数据结构包含三个方面的内容：数据的逻辑结构；数据的存储结构;对数据所施加的运算。数据的逻辑结构独立于计算机，是数据本身固有的。是逻辑结构在计算机内存中的映像必须依赖于计算机。指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。第二章基本数据结构4.数据逻辑结构1.反映数

3、据元素之间逻辑关系的数据结构逻辑结构表示：B＝（D，R)其中D:数据元素集合；R:D中各数据元素之间的前后件关系。举例：E.g.1一年四季数据逻辑结构；E.g.2家庭成员数据逻辑结构；E.g.3mxn矩阵数据逻辑结构；第二章基本数据结构4.数据逻辑结构2.数据逻辑结构类型线性结构线性结构判定条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多一个后件。线性结构插入或删除任一结点后还是线性结构。非线性结构e.g.树结构和图结构第二章基本数据结构没有前件的结点4.数据逻辑结构E.g.用图形表示数据结构B＝（D，R）D＝{di

4、1≤i≤7}＝{d1，d2，d3，

5、d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}第二章基本数据结构d1d7d6d5d4d3d2根节点终端节点非线性结构4.数据逻辑结构第二章基本数据结构ACDB非线性结构若在数据结构中，插入或删除任何节点后就不满足线性结构的两个条件，则该结构为非线性结构。5.数据存储结构数据逻辑结构在计算机存储空间中的存放形式常用的存储结构包括：顺序存储：链接存储：索引存储：散列存储：一种逻辑结构可根据需要表示成多种存储结构第二章基本数据结构6.数据结构的运算基本运算：插入删除其它运算：查找分类合并复制修改空数据结构第二章基本数

6、据结构2.2线性表及其顺序存储结构线性表及其运算栈及其运算队列及其运算第二章基本数据结构2.2.1线性表及其运算第二章基本数据结构1.什么是线性表线性表：是由n(n≥0)个数据元素组成的有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。逻辑上为一个一维向量：(a1,a2,a3,……an)特征：有且只有一个根结点a1，其无前件；有且只有一个终结点an，其无后件；其它结点有且只有一个前件及后件。线性表的长度：n（n=0，定义为空表）第二章基本数据结构英文小写字母表(a，b，c，…，z)是一个长度为26的线性表矩阵是一个比较复杂的线

7、性表学生情况登记表是一个复杂的线性表由若干数据项组成的数据元素称为记录(record)由多个记录构成的线性表又称为文件(file)1.什么是线性表第二章基本数据结构2.线性表顺序存储结构对应到程序设计语言中的一维数组a1a2a3……aiai+1ai+2……an序号内容插入前第二章基本数据结构占k个字节占k个字节占k个字节占k个字节占k个字节占k个字节占k个字节存储地址ADR(a1)ADR(a1)+kADR(a1)+2kADR(a1)+(i-1)kADR(a1)+ikADR(a1)+(i+1)kADR(a1)+(n-1)k用来泛指某种数据类型3.线性表C语言描述#define

8、maxsizemaxlenstructsequenlist{Elemtypea[maxsize];intlen;}；表示线性表（a1，a2，….,an）len表示线性表的实际长度maxlen表示线性表允许的最大长度第二章基本数据结构线性表顺序存储结构下的运算：(1)在线性表的指定位置处加入一个新的元素（即线性表的插入）(2)在线性表中删除指定的元素（即线性表的删除）(3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）(4)对线性表中的元素进行整序（即线性表的排序）(5)按要求将一个线性表分解成多个线性表（