第二章线性表 线性结构的特点是,在数据元素的非空有限集中, )存在唯一的一个被称作“第一个”的数据元素; 2)存在唯一的一个被称作“最后一个”的数据元素; 3)除第一个数据元素之外,集合中的每个数据元素均只有一个直 接前趋数据元素; 4)除最后一个数据元素之外,集合中的每个数据元素均只有一个 直接后继数据元素 2线性表及其基本操作 线性表属线性结构,是最常用且最简单的一种数据结构, 个线性表是n>=0个数据元素a1,a2,…,n的有限序列,表中 每个数据元素,除第一个和最后一个外,有且仅有一个直接前 趋和一个直接后继
第 二 章 线 性 表 线性结构的特点是, 在数据元素的非空有限集中, 1) 存在唯一的一个被称作“第一个”的数据元素; 2) 存在唯一的一个被称作“最后一个”的数据元素; 3) 除第一个数据元素之外, 集合中的每个数据元素均只有一个直 接前趋数据元素; 4) 除最后一个数据元素之外, 集合中的每个数据元素均只有一个 直接后继数据元素. 2 .1 线性表及其基本操作 线性表属线性结构, 是最常用且最简单的一种数据结构, 一 个线性表是n>=0个数据元素 a a a n , , , 1 2 的有限序列, 表中 每个数据元素, 除第一个和最后一个外, 有且仅有一个直接前 趋和一个直接后继
线性表的形式化定义:含有n个数据元素的线性表是一个 数据结构 Liner list=(DR),其中: Di=1 R 23. D为某个数据对象 解读线性表的形式化定义,可得如下注意点 1)同一个线性表中的数据元素必定具有相同特性,即应属于 同一数据对象; 2)关系N是一个序偶的集合,表示线性表中数据元素之间的 相邻关系,即a领先于a,4领先41+1,依此类推.称a1-1 是a的直接前趋元素,a1是a的直接后继元素 3)线性表中数据元素的个数n(n≥0)定义为线性表的长度,当 n=0时称为空表,n>0时,线性表通常记为
线性表的形式化定义: 含有n个数据元素的线性表是一个 数据结构 Liner _list = (D,R) , 其中: R N N a a a a D i n D a a D i n n i i i i i i , , , , 2,3, , , 1,2, , , 0 1 1 0 0 = = = = = − − D0 为某个数据对象. 解读线性表的形式化定义, 可得如下注意点: 1)同一个线性表中的数据元素必定具有相同特性, 即应属于 同一数据对象; 2)关系N是一个序偶的集合,表示线性表中数据元素之间的 相邻关系, 即 ai−1 领先于 ai ai , 领先 ai+1 ,依此类推. 称 ai−1 是 ai 的直接前趋元素, ai+1 是 ai 的直接后继元素. 3)线性表中数据元素的个数 n(n 0) 定义为线性表的长度,当 n = 0 时称为空表, n 0 时,线性表通常记为: ( , , , , , ) a1 a2 ai a n
4线性表中的每一个数据元素,视不同情况,可以是一个 数、一个符号,也可以是一页书,甚至为其它更复杂的 信息.当一个数据元素由若干项数据项组成时,可把数 据元素称为记录 (record)或结点(node),含有大量记录的 线性表又叫文件(file) 对线性表的常用操作可见教材P11,本章主要讨论插入和 删除这两种基本操作.为对线性表的操作而编制的具体程 序,随线性表存储结构的不同而不同 2.2线性表的顺序存储结构 221顺序存储结构 定义:用一组地址连续的存储单元对线性表中的数 据元素按照其逻辑次序依次存放的存储结构 叫顺序存储结构,此时的线性表叫顺序表
4)线性表中的每一个数据元素, 视不同情况, 可以是一个 数﹑一个符号, 也可以是一页书, 甚至为其它更复杂的 信息. 当一个数据元素由若干项数据项组成时, 可把数 据元素称为记录(record)或结点(node), 含有大量记录的 线性表又叫文件(file). 对线性表的常用操作可见教材P.11, 本章主要讨论插入和 删除这两种基本操作. 为对线性表的操作而编制的具体程 序, 随线性表存储结构的不同而不同. 2 .2 线性表的顺序存储结构 2.2.1顺序存储结构 定义: 用一组地址连续的存储单元对线性表中的数 据元素按照其逻辑次序依次存放的存储结构 叫顺序存储结构, 此时的线性表叫顺序表
如果线性表中各数据元素只占用一个存储单元,则顺序表 的存储形式可用下图表示,从下图可知,线性表的第i 存储地址内容结点序号个数据元素即结点)的存储地 址为: L+1 LOC(a)=lOC(a+(i-1) 上式中LOC(a1)为第一个数 L+(i-1) 据元素的存储地址,推广到 般情况,如每个数据元素 L+n-1 占用c个存储单元,则第i 个数据元素的存储地址为:OC(a1)=DOC(a1)+(t-1)×C 上式中LOC(a1)第一个数据元素所占用的C个存储单元 的第一个单元的存储地址.称上两式中的LOC(a1)为线性 表的基地址.如用C语言中的数组表示线性表 100 并假设表中所有元素均为整形,则在主程序中可作如下说明
如果线性表中各数据元素只占用一个存储单元, 则顺序表 的存储形式可用下图表示, 存储地址 1 ( 1) 1 + − + − + L n L i L L 结点序号 n i 2 1 n i a a a a 2 1 内容 从下图可知, 线性表的第 i 个数据元素(即结点) 的存储地 址为: ( ) ( ) ( 1) LOC ai = LOC a1 + i − 上式中 ( ) LOC a1 为第一个数 据元素的存储地址, 推广到 一般情况, 如每个数据元素 占用 c 个存储单元, 则第 i 个数据元素的存储地址为: LOC(ai ) = LOC(a1 ) + (i −1) c 上式中 ( ) LOC a1 为第一个数据元素所占用的 c 个存储单元 的第一个单元的存储地址. 称上两式中的 ( ) LOC a1 为线性 表的基地址. 如用C语言中的数组表示线性表 ( , , , , , ) a1 a2 ai a100 并假设表中所有元素均为整形, 则在主程序中可作如下说明:
#define maXsize 101 int VIMAXSIZEI; 因为C语言中数组下标的下界是0,有时为讨论问题方便起 见,下标为0的单元空置不用,数组长度为线性表实际长度 加1,故有上述说明 由前面给出的地址公式,一旦基地址和一个数据元素 占用存储单元的大小确定,就可求出任一个数据元素的起 始地址,因此,顺序表便于进行随机访问,是一种随机存 取结构 222顺序表的插入和删除 插入和删除是对顺序表的基本操作(运算) 顺序表的插入 线性表的插入运算是指在第i个数据元素和第i-1个数据 元素之间插入一个新的数据元素x,它的结果使线性表的长 度由n变为n+1,而根据线性表在顺序存储结构下的特点,在 插入一个新数据元素之后,线性表的逻辑关系发生了变化
#define MAXSIZE 101 int v[MAXSIZE]; 因为C语言中数组下标的下界是0, 有时为讨论问题方便起 见, 下标为0的单元空置不用, 数组长度为线性表实际长度 加1, 故有上述说明. 由前面给出的地址公式, 一旦基地址和一个数据元素 占用存储单元的大小确定, 就可求出任一个数据元素的起 始地址, 因此, 顺序表便于进行随机访问, 是一种随机存 取结构. 2.2.2 顺序表的插入和删除 插入和删除是对顺序表的基本操作(运算). 一﹑ 顺序表的插入 线性表的插入运算是指在第i个数据元素和第i -1个数据 元素之间插入一个新的数据元素x, 它的结果使线性表的长 度由n变为n+1, 而根据线性表在顺序存储结构下的特点,在 插入一个新数据元素之后, 线性表的逻辑关系发生了变化
其物理存储关系也要发生相应的变化因此,除非i=n+1, 否则必须将第i、i+1 n这些数据元素向后移动空 出第个位置并将新的数据元素存入.设有线性表 an)存储于数组(向量)vmkm>n+1) 中,则插入过程如下图所示 插入前ia 移动i 插入后1 +1 +1 +2 i+2 i+1 n+1 n+1
其物理存储关系也要发生相应的变化. 因此, 除非i = n+1, 否则必须将第i ﹑ i +1 ﹑… ﹑ n这些数据元素向后移动,空 出第i个位置并将新的数据元素存入. 设有线性表 ( , , , , , ) a1 a2 ai a n 存储于数组(向量) vm(m n +1) 中, 则插入过程如下图所示: n i i a a a a a 1 2 1 + 1 1 2 1 0 − + m n i i 插入前 移动 n i i a a a a a 1 2 1 + 1 1 2 1 2 1 0 − + + + m n i i i 插入后 1 1 2 1 2 1 0 − + + + m n i i i n i i a a a x a a 1 2 1 +
插入算法的框图请见教材P14,下面给出C函数 struct ist /结构类型 { int V MAXNE;/*整型数组,MAXN为预估数组容量* int n; /表长 typedef struct list LIST;/定义LNT为上述结构类型* int sqinsert(p,i, x) LIST *P; /指向结构类型的指针 int l, x; /i为插入位置,x为被插入元素* f int j if(p>n<=0) { printf(“表长错误Ⅷ”); return(-1)
插入算法的框图请见教材P.14, 下面给出C函数. struct list /* 结构类型*/ { int v[MAXN]; /* 整型数组, MAXN为预估数组容量*/ int n; /* 表长 */ }; typedef struct list LIST; /* 定义LIST为上述结构类型*/ int sqinsert(p,i,x) LIST *p; /* 指向结构类型的指针 */ int i,x; /* i为插入位置, x为被插入元素*/ { int j; if (p->n<=0) { printf(“表长错误\n ”); return(-1); }
if(ip->n+1) { printf(“插入位置i不恰当n”); return(1); for(i→p->n;j>=i:j-) p>v+1l=p->vjl;/移动 p->vFx; 将x存入第个位置 p->n++; /表长加1*/ printf(“插入成功n”); return(O); 对于顺序表的插入算法,主要操作是元素的移动,即 for循环语句中的循环体,它执行的后移元素次数为n-i+1 由此可见它不仅依赖于线性表的长度n,还与元素插入位置 i关.当i=1时,全部元素都被移动,移动n次;当i=n+1时
if (ip->n+1) { printf(“插入位置i不恰当\n ”）; return(-1); } for(j=p->n;j>=i;j--) p->v[j+1]=p->v[j]; /* 移动 */ p->v[i]=x; /* 将x存入第i个位置*/ p->n++; /* 表长加1 */ printf(“插入成功\n ”）; return(0); } 对于顺序表的插入算法, 主要操作是元素的移动, 即 for循环语句中的循环体, 它执行的后移元素次数为n- i +1 由此可见它不仅依赖于线性表的长度n, 还与元素插入位置 i有关. 当i =1时, 全部元素都被移动, 移动n次; 当i = n +1时
不需移动元素,可见算法的时间复杂度为O(n) 由于元素移动的次数直接影响算法的执行时间,下面 讨论平均移动次数 设P为在第个元素之前插入一个元素的概率,且设在 线性表的任何位置上的插入机会相等,即等概,则平均移动 次数(期望值为: En=∑n(m-i+1)=-∑(n-i+1) n+l i 顺序表的删除 删除运算是指将表中第i(1≤i≤m)个元素删除,使线 性表的长度由m变为n-1,且其逻辑结构和顺序存储结构也 发生相应的变化,除非i=n时可直接将第个元素删除,否 则需移动第i+1、i+2 n这些元素以填充由删除运算 而造成的间隔
不需移动元素, 可见算法的时间复杂度为O(n). 由于元素移动的次数直接影响算法的执行时间, 下面 讨论平均移动次数. 设 i p 为在第i个元素之前插入一个元素的概率, 且设在 线性表的任何位置上的插入机会相等, 即等概, 则平均移动 次数(期望值)为: 2 ( 1) 1 1 ( 1) 1 1 1 1 n n i n E p n i n i n i i n i − + = + = − + = + = + = 二﹑ 顺序表的删除 删除运算是指将表中第 i(1 i n) 个元素删除, 使线 性表的长度由n变为n-1, 且其逻辑结构和顺序存储结构也 发生相应的变化, 除非i = n时可直接将第i个元素删除, 否 则需移动第i +1﹑ i +2﹑… ﹑ n这些元素以填充由删除运算 而造成的间隔
删除过程如下图所示: 删除前ia 删除后i 移动 i+1 n 设有线性表(a12a2…a12…an)存储于数组vmkm≥m) 中,要求删除线性表中第f个元素并将其存入y中,描述上述 要求的算法框图请见教材P.16
删除过程如下图所示: 设有线性表 n i i a a a a a 1 2 1 + 1 1 2 1 0 − + m n i i 删除前 删除后 1 1 2 1 0 − + m n i i n i a a a a 1 2 1 + 移动 1 1 2 1 0 − − m n i n i a a a a 1 2 1 + ( , , , , , ) a1 a2 ai a n 存储于数组 vm(m n) 中, 要求删除线性表中第i个元素并将其存入y中, 描述上述 要求的算法框图请见教材P.16