1、第 1章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 排序ABCDEFG姓名 学号 成绩 班级李红 9761059 95 机 97.6 10 658651.2 线性表1. 线性表的定义1) 定义： 具有 相同数据类型 的 n(n0)个数据元素组成的 有限 序列。是最简单、最常用的数据结构。 2) 表示 : L=( a1， a2， a3， a i-1， ai ， ai+1， an ) 其中 : n为 线性表长度 (n=0称为空表 )，表中相邻元素之间存在着顺序关系。 a1 ： 表头 元素； an ： 表尾 元素； ai-1称为
2、 ai的直接 前驱 ； ai+1 称为 ai的直接 后继 。 1.2.1 线性表的基本概念 (P32)表头 表尾1.2 线性表1. 线性表的定义1) 定义： 具有 相同数据类型 的 n(n0)个数据元素组成的 有限 序列。是最简单、最常用的数据结构。 2) 表示 : L=( a1， a2， a3， a i-1， ai ， ai+1， an ) 1.2.1 线性表的基本概念 (P32)3) 线性结构特点 :(1)有且只有一个根结点 a1，无前驱 。(2)有且只有一个终端结点 an ，无后继 。(3)其他结点有且只有一个直接前驱和一个直接后继。1.2 线性表1. 线性表的定义1) 定义： 具有 相
3、同数据类型 的 n(n0)个数据元素组成的 有限 序列。是最简单、最常用的数据结构。 2) 表示 : L=( a1， a2， a3， a i-1， ai ， ai+1， an ) 1.2.1 线性表的基本概念 (P32)3) 线性结构特点 :4) 线性表的分类(1)简单线性表：数据元素是简单项 (数字、字母、季节名等 )。 如 :(12,34,4,67,8)(2)复杂线性表：数据元素由 若干个数据项 组成，此时数据元素称为 记录或节点 , 如学生成绩表 .例 2、一副扑克的点数（ 2， 3， 4， ， J， Q， K， A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结
4、点 a1，它没有直接前趋，而仅有一个直接后继 a2；有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋 a n-1；例 1、 26个英文字母组成的字母表（ A， B， C、 、 Z） 简单线性表例 3、学生健康情况登记表如下：姓 名 学 号 性 别 年 龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张 立立 790634 男 17 神 经 衰弱. . . . .复杂线性表1.顺序表基本概念1.2.2 线性表的顺序存储结构1) 顺序存储结构：用一 组地址连续的存储空间 依次存放线性表的各元素 。顺序表：采用顺序
5、存储结构的线性表称为顺序表 (一维数组 ) 表中的所有元素所占 存储空间连续表中各元素在存储空间中按 逻辑顺序存放 顺序存储结构特点1.2 线性表1.顺序表基本概念1.2.2 线性表的顺序存储结构1) 顺序存储结构：2) 第 i个元素地址1.2 线性表其中 :m： 每个元素占 m个存储单元Loc(a1)第一个元素地址 (基址 ) 对数组而言an.ai.a1a0bb+mb+i*mb+n*m存储地址 存储状态空闲数据元素在线性表中的位序12ni从存取方式看 ,线性表的顺序存储结构是可以 随机存储 的存储结构 .1.顺序表基本概念1.2.2 线性表的顺序存储结构1) 顺序存储结构：2) 第 i个元素地址1.2 线性表2.顺序表的基本运算 存取 : 访问线性表的第 i个元素，使用或改变数据元素的值。查找 : 在线性表中查找满足某种条件的数据元素。插入 : 在线性表的第 i个元素之前，插入一个同类型的元素。 (*)删除 : 删除线性表中第 i个元素。 (*)求表长 : 求出线性表中元素的个数。置空表 : 建立一个空表。清除表 : 将已有线性表变为空表，即删除表中所有元素。
