第二章线性表 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
222顺序表的基本操作 q申查线到,输出结束分析2第个 若l=1,表明是 首结点 若上=N,表明是 K不是顺序表中的元素尾结点 图2=2顺序表的定位操作学华夏学晓信息工程 系
武汉理工大学华夏学院-信息工程 系 2. 定位操作 顺序表的定位操作非常简单，由于顺序表的逻辑顺序 与存储顺序一致，则当1<=I<=N时，V[I]就是顺序表中的第I个元 素。其算法流程是： 输入K （被查值） I=1 V[I]=K? I=I+1 I<=N? 图2－2 顺序表的定位操作 查找到，输出V[I],结束 K不是顺序表中的元素 2.2.2 顺序表的基本操作 ＋ － － ＋ 思考： 查找第I个 结点的前驱 和后继应如 何实现？ 分析：第I个 结点的位置， 若I=1，表明是 首结点； 若I=N，表明是 尾结点；
3.插入操作 在顺序表中插入一个元素时,由于顺序表中 的元素是连续存放的,所以在插入前需要考虑以下几个问题: 其一,事先定义的存储区域(数组)是否还有空闲的 单元,若有,则可以插入,否则,表明表已经满了; 其二,要确定插入位置I,即在第I个元素后面插入, 确定插入位置I的方法有直接给出位置I或者给出元素值, 去确定位置I; 〓其三,插入方法是,若I>=N则直接将被插入的值送 往V[N1]单元就可以了,若I<N则表明数组元素V[I+1]不 是空单元,因此在插入新元素之前,要将顺序表中的 V[I+1]~V[N中的所有元素依次向后移动一个位置,空出 数组元素V[+1],再将被插入的值送往V[+1单元。 其四,插入元素厦:应改变将顺序表的长度N 即将原来的N加1取代N其算法流程是:
武汉理工大学华夏学院-信息工程 系 在顺序表中插入一个元素时，由于顺序表中 的元素是连续存放的，所以在插入前需要考虑以下几个问题： 3. 插入操作 其一，事先定义的存储区域（数组）是否还有空闲的 单元，若有，则可以插入，否则，表明表已经满了； 其二，要确定插入位置 I，即在第I个元素后面插入， 确定插入位置I的方法有直接给出位置I或者给出元素值， 去确定位置I； 其三，插入方法是，若I >= N 则直接将被插入的值送 往V[N+1]单元就可以了, 若I<N则表明数组元素V[I+1]不 是空单元，因此在插入新元素之前，要将顺序表中的 V[I+1]～V[N]中的所有元素依次向后移动一个位置，空出 数组元素V[I+1],再将被插入的值送往V[I+1]单元。 其四，插入一个元素后，应改变将顺序表的长度N， 即将原来的N加1取代N，其算法流程是：
图2-3顺序表的插入操作 输入被插入值K 和插入位置 NENO 表满返回 追加 K<=N 插入 VIN+1 V+1=K 移动数据 空出位置 J=J-1 N中改变表长 J=I+1 返回 理工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 输入被插入值K 和插入位置I I<=N J=I+1 J=N V[J+1]=V[J] J=J-1 V[I+1]=K N=N+1 返回 V[N+1]=K 表满返回 图2－3 顺序表的插入操作 否 否 追加 插入 N=N0 移动数据 空出位置 改变表长 插入
4.删除操作 ≥在顺序表中删除一个元素时,删除前需要考虑以下几个 问题 其一已建成的顺序表是否为空,若是则表明该线性 表中无结点,因此无元素删除,否则表明表中有结点; 其二,要确定被删结点的位置I,即要删除第个元素, 确定被删位置邛的方法有直接给出位置I者给出元素值, 去确定位置I; 其三,删除方法是,着I=N则表明将要删除的是终 端结点,因此直用N=N-1就可以了,若I<N则表明将 要删除的是非终端结点,因此要将顺序表中的 V[I+1]~VN]中的所有元素依次向前移动一个位置就 唭了;删除后,应修改顺序表的长度N(即N=N1 武汉理工大学华夏学院-信息工程 其算法流程是: 系
武汉理工大学华夏学院-信息工程 系 在顺序表中删除一个元素时，删除前需要考虑以下几个 问题： 4. 删除操作 其一 已建成的顺序表是否为空，若是则表明该线性 表中无结点，因此无元素删除，否则表明表中有结点； 其二，要确定被删结点的位置 I，即要删除第I个元素， 确定被删位置I的方法有直接给出位置I或者给出元素值， 去确定位置I； 其三，删除方法是，若I=N则表明将要删除的是终 端结点，因此直用N=N-1就可以了，若I<N则表明将 要删除的是非终端结点，因此要将顺序表中的 V[I+1]～V[N]中的所有元素依次向前移动一个位置就 可以了。 其四，删除后，应修改顺序表的长度N（即N=N-1)。 其算法流程是：
图2-4顺序表的删除操作 输入被删除值K 除最后一个结点 NN-I 表空返回 J=I+1 改变表 VU-1=VU] J=J+1 N=N-1 返回 武汉理工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 输入被删除值K 的位置I J=I+1 V[J-1]=V[J] J=J+1 表空返回 N=N-1 N=N-1 返回 图2－4 顺序表的删除操作 删除最后一个结点 ＋ － 改变表长 I=n N＝0 N＝j