第二章线性表 2.1线性表的类型定义 定义:线性表是一个有n(n>=0)个元素 的有限序列,各元素具有相同的数据类型 (同一数据对象)。例如(a,b,c,d,e)与 (23,45,67,89,90,.100)都称为线性表。 (a,b,c,d,e)也称为串。 术语:表长:表中元素的个教,为表的长度 空表:表中元素个数为零的表 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第二章 线性表 2.1 线性表的类型定义 定义：线性表是一个有n（n>=0）个元素 的有限序列，各元素具有相同的数据类型 （同一数据对象）。例如(a,b,c,d,e) 与 （23,45,67,89,90，….100 ）都称为线性表。 (a,b,c,d,e)也称为串。 术语：表长：表中元素的个数，称为表的长度。 空表：表中元素个数为零的表
·线性表的特点:表中元素存在着“序偶”关系 =即除首结点无前件,尾结点无后件以外的其余 结点都有且仅有一个前件也有且仅有一个后件 °存储线性表的方法:顺序存储和链式存储; °线性表的基本操作 1.初始化(置空表) 2.求表长 3取表中元素 4.定位 5.在表中插入新元素 6.删除表中某一个元素 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 • 线性表的特点：表中元素存在着“序偶”关系， 即除首结点无前件，尾结点无后件以外的其余 结点都有且仅有一个前件也有且仅有一个后件。 • 存储线性表的方法：顺序存储和链式存储； • 线性表的基本操作 1. 初始化（置空表） 2. 求表长 3. 取表中元素 4. 定位 5. 在表中插入新元素 6. 删除表中某一个元素
22线性表的顺序表示和实现 221定义用顺序存储方法存储的表称为顺序表 实现方法用一维数组作为顺序表的存储区域。 设线性表中的所有结点按前驱后继关系排成一个线性 序列:(1K2,K3…K)其中结点个数N称为表的 长度,当N=0时的线性表称为空表。又设数组v[N N<N)用来依次存储线性表中的N个元素vN+1] 到VN是为插入新元素准备的空单元,如图2-1所 下标1234 N 数组VvK1K2K3K4 K 132- TA MAXSIZE 系
武汉理工大学华夏学院-信息工程 系 2.2 线性表的顺序表示和实现 2.2.1 定义 用顺序存储方法存储的表称为顺序表 实现方法 用一维数组作为顺序表的存储区域。 设线性表中的所有结点按前驱后继关系排成一个线性 序列：(K1 ,K2 ,K3……KN) 其中结点个数N称为表的 长度，当N=0时的线性表称为空表。又设数组V[N0 ] (N<N0 )用来依次存储线性表中的N个元素,V[N+1] 到V[N0 ]是为插入新元素准备的空单元，如图2-1所 示： 下标 … 数组V … … 1 2 3 4 N … N0 K1 K2 K3 K4 KN 图2－1顺序表的存储结构示意 MAXSIZE
顺序存储的优点是: 顺序存储的缺点是: 1)节省存储空间 2)逻辑上相邻结点在物理次 不便于动态修改,即在对 序上也相邻,其存储地址可以 结点进行插入或删除操作 用计算公式表示为 时,要移动较多的结点。 LOC(=LOC(1)+(1-1)杜 其中的是结点的逻辑序号 即为第个结点; LOC(1)为首结点的地址; L为每一个结点占用的存 储单元数 3)可以实现对结点的随机访问。 学院信息工心
武汉理工大学华夏学院-信息工程 系 1）节省存储空间； 2） 逻辑上相邻结点在物理次 序上也相邻，其存储地址可以 用计算公式表示为： LOC(I)=LOC(1)+(I-1)*L 其中 I的是结点的逻辑序号 即为第I个结点 ； LOC(1)为首结点的地址； L为每一个结点占用的存 储单元数 3）可以实现对结点的随机访问。 顺序存储的优点是： 不便于动态修改，即在对 结点进行插入或删除操作 时，要移动较多的结点。 顺序存储的缺点是：
22.2顺序表的基本操作 顺序表的类型定义 # defile no100/用宏定义表的容量*/ Typedef struct char v[No];/v为字符数组,元素值是字符*/ int len 表的当前长度* 3 SQLIST 1,建表:定义一个数组及表长变量N,输入 数据。注意:毎输入一个值,其表长要加1。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 2.2.2 顺序表的基本操作 顺序表的类型定义： #defile N0 100 /*用宏定义表的容量*/ Typedef struct ｛char V[N0]； /*V为字符数组，元素值是字符*/ int len； /*表的当前长度*/ ｝SQLIST; 1.建表： 定义一个数组V及表长变量N，输入 数据。注意：每输入一个值，其表长要加1