第1章_数据结构与算法.ppt

1.2.1 什么是数据结构（二） 结构：所谓“结构”，就是关系，是集合中各个数据元素之间存在的某种关系（或联系）。 “结构”是数据结构研究的重点。通常分为以下4类： 线性结构 树形结构 网状结构 集合 1.2.1 什么是数据结构（三） 前后件关系：是数据元素之间的最基本关系，即直接前驱与直接后继关系。 例如： 1.2.1 什么是数据结构（四） 综上所述，数据结构是指相互有关联的数据元素的集合，即数据的组织形式。 数据结构的两个要素——“数据”和“结构”是紧密联系在一起的，“数据”是有结构的数据，而不是无关的、松散的数据；而“结构”，就是数据元素间的关系，是由数据的特性所决定的。 1.2.1.1 数据的逻辑结构 数据的逻辑结构：指反映数据元素之间逻辑关系（即前后件关系）的数据结构。 数据的逻辑结构的数学形式定义是一个二元组,记为：B={D,R} 其中，B表示数据结构，D是是数据元素的集合，R是D上关系的集合，它反映了D中各数据元素之间的前后件关系。 例如，如果把一日三餐看做是一个数据结构，可表示为：B={D,R}D={早餐，午餐，晚餐}R={(早餐，午餐)，(午餐，晚餐)} 1.2.1.2 数据的存储结构 数据的存储结构：又称数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式。 * 数据元素在计算机存储空间中的位置关系可能与逻辑关系不同。 * 同一逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。 常用的存储结构有顺序、链接、索引等存储方式。 思考题：在哪一类存储结构中，数据的逻辑结构与数据的物理结构相一致？ 1.2.2 数据结构的图形表示(一) 用中间标有元素值的方框表示数据元素，称之为数据结点，简称结点。 用一条有向线段从前件指向后件，表示数据元素之间的前后件关系，即每一个二元组。 例如，一日三餐的数据结构用图形表示如下： 1.2.2 数据结构的图形表示(二) 例如，家庭成员的数据结构用图形表示如下： 1.2.3 线性结构与非线性结构 如果一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。 数据的逻辑结构分为线性结构和非线性结构两类。 线性结构的非空数据结构应满足以下两个条件： 有且只有一个根结点。 每一个结点最多有一个前件，也最多有一个后件。 常见的线性结构包括线性表、堆栈、队列和串。 1.2.3 线性结构与非线性结构(二) 如果一个数据结构不是线性结构,称之为非线性结构。 常见的非线性结构包括树、二叉树、 图（或网络）和广义表。 1.3 线性表及其顺序存储结构 1.3.1 线性表的基本概念 线性表是n(n≥0)个数据元素构成的有限序列,可记为：L=（a1，a2，…，an）。 例如，英文大写字母表(A,B,C,…X,Y,Z)是一个长度为26的线性表，每一个大写字母就是一个数据元素。 线性表具有如下的结构特征： 只有一个根结点，即a1，它无前件； 有且只有一个终端结点，即an ，它无后件； 除跟结点与终端结点外，其他所以结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，n=0时，称为空表。 线性表有两种存储方式：顺序存储和链式存储。 1.3.2 线性表的顺序存储结构 顺序存储是表示线性表最简单的方法，这种顺序存储的线性表也称顺序表。 顺序表具有以下两个基本特征： 线性表中所有元素所占的存储空间是连续的； 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 1.3.3 顺序表的插入操作 在第i（1≤i≤n）个元素之前插入一个新元素时 ，3个步骤： 从最后一个（即第n个）元素开始，直到第i个元素依次向后移动一个位置，移动结束后，第i个位置就被空出 ； 将新元素插入到第i项 ； 将线性表的长度增加1。 1.3.4 顺序表的删除操作 把第i（1≤i≤n）个元素删除 ，2个步骤： 从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置 ； 将线性表的长度减少1。 1.3.5 顺序表的优缺点 优点 无需为表示结点间的逻辑关系而增加额外的存储空间，因为逻辑上相邻的元素其存储的物理位置也是相邻的。 可方便地随机存取表中任何一个元素。 缺点 插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。 线性表的顺序存储结构下，线性表的存储空间不便于扩展。 线性表的顺序存储结构不便于对存储空间动态分配。 1.4 栈 和 队 列 1.4.1 栈及其基本运算 1.4.1.1 栈的定义 栈（stack）是限定在一端进行插入与删除运算的线性表。 栈中，允许插入和删除的一端称为栈顶，另一端称为栈底。 栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。 当表中