数据结构 第2章 线性表

203-71-82

2. 1线性表类型定的义– 定：义一线个表是n性=>个数0元素据的有限列序 如a , 1 2a , ,ia , a n

例 英字母文表A,(B,,C.…Z.是一)线个表性例 号学 姓 年名龄00 1002 … 张…三李 四…… 18 9 ……1

数据元

素–

征： 特元 素个n数表—度长，n=空0表 1<i<时n ai直接的驱前是ai1-,a1直无前驱接 i的直a接后是继ai+1,na直无接后继

元 属素同数据对象一20317--82

线结性构特点

在数：元据素的空非限有中集 –存唯在的一个一称作“被一个”的第据元数 素–存 在唯的一一被个称“最作后一”的个数元 素 –据 除第一外，集个中合每个的据元素数均有只 一个前 – 驱除后最个外，集合一的每中数据元个素均有只一个 继后有序:表性线按某表个数项升据序降序排或列无序 表20137--82

线性表的DAT (P19) 子例(P2)

练01习利用线性：表基的运本，编写在算性表线中删除A线表B中出性的现元素算法。的

习练：利用线性2表的基本运算编，写将线性A表和中B公的共素元生线成表性的算法C。20137-28-

2. 线2性表的顺序存结储构–顺序表 ： 定义：用一组地 连续的存址储元存放一个单线表 性 元地素址计方算法: –LCO(a)iL=O(Ca)+(1i1-*) L –LOC(ia1)+LOC(ai=)L+– 中： » L—一个元其占素的用储单存个元 数»LO (aCi)—线表第i个性元的素址地 特点–: 实逻辑现上邻—物理地址相相 – 实邻现机存取随 实现可用C:语言一的数维实组现203-1-728

数V下组标

内 存a a12元素序号1 2 0 1

tpeyef dnt DiAATYPTE ;#edfneiM 1 000 DAATTYE Pada[M]t ; 例typdeef tsuct crar d {itnn mu c;ahrnam e20]; char [utaorh[01; cha]rpublish er30[] f;lao price;t} ADATYPET ;ATATYPED lirbay[M]r

n-1

;nan

M1

备 -用空 间

动态或请和释申放内存D TAATYPE* Dpta = a(DATAYPE T*)mllocaM(*szioefDAT(AYTP))E 数;元素据是简单不型时,类可定结构体数组 f义eerpD(ta)a;213-0-278

–

插入 定：线义性的表入插是指第i(1 在i +1)n个元之前插素入一 个的新据元素数，x长度为使的n线性变表为n+1 a

, 1 a , 2 , ai 1, ai , a n

变 长度成n为1的+线性表

a1 a,, , ai 21 x,, ai , an

需第将i至第n共n-(i1)+个元素后移 算

201法3-72-

in8 stbcx(rni iti,tn xin,t []v,in t*)p{ /*i要插入数据为的位置x,为插入的据数v,数组名，为示表 存储数据数的据结，构中p放存顺表序元的素数个。*/ int jn;, =n*p;if ((<i1) ||( >ni1))+r etun (0)r e;sl e for(j{=n;j=i;>-j)-v [j=]v[-1]j;v[ j=x] *;=p++n re;tun r1)( }; }20317-28-

数组下V 标0内存元 素序号 1aV数组下标 0

内存元 素号序a 11

2 211

2a1

a

i2-1i

iaa +1i

i +i1i-1

ixaaii1+i i+1

n1-a

nn

n-1

na-

n1n 1

+n

n+

1n

an

023-7128-

算法间时杂度T复n)(–设Pi 是第i个元在之素前插入个元素的一概率，则长在为度 的线性n表插入一个元素时中，所移需的元动次数的平均素次 数：为

Esi P ( n i 1 )i 1 in 1

认若为iP

1 n 1

1 1nn 则Eis ( n i 1 ) n 1 i 12 T n O n 023-7-281

–

除删 定义:性表的线删除是将指第i(1i n 个元素删除) ,使长为度n的性线表

a

a

1, a , 2 ai 1 ,, ai, a n 变成度长n为-的1性表线1

a ,2, a, i 1 ,ai 1 , a n

需将第+i至第1共(n-i)n元个前素 移 算法20137--82in

stbsx(inc i,inttv ],i[nt* ) {p*i/为要除的数删据素的位元，v为顺序表置数的结据构 ，中存放p顺序表素的个元。数/ *in t,nj;n *=p ;if((<1)i|| i>()) rnturne(0) ;e se l {fr(joi=;<j;n+j)+ v[-1j]v[j]; *=p=-n- re;trn (1); u }}023-7-281

数组V下标 10

内 存元素序

号数V组标 0 下

内1 存素序元号a1 a2 12a1

2a

12

-i1

aiia +1ii +1ii-1 ia+i1 i+a2ii+1

n- n1

nan n+1n- n-1

2n

na-1n

2130-7-82

法算评– 价Q设i删除第i是个素元的率概则在长度为n,线的表性删除 一中个元所素需动的元素移数次的平均数次为：E de

Qi 1 n

i

n( i )

1 认为若iQ n 1n n 1 则 Ed e ( n i ) n i 1 2 T n O n

故在序表中插入顺或删一个元除素时，平移均动表的一半 元，当素很大n时效，率低很2130-7-2

8– 顺序

存结储构的优点 缺点优– 逻相辑邻物理相邻， –可随存机任取元一素 –存空间储使用紧凑 缺– 插点入、除操删需要移动作大量的元素 –预 分先配空间需最大按空分间配利用，不充 分– 表容难以扩充量

023-71-82

练习

1设有两个：元按递素的增有表序A和B设计一，个法将A算和的全部元素B并为合个一元按递增素C表。 void Megr(SeqistL A,qLSis tB,qSLsi &C)

练t习：2有一设线性表按序存顺储且每，元个素不相等，互计设所把奇有数到所有偶移数前边算法。 的线性表述描为： ocns tnitM XAISZE=顺序容表；量 ypetdf etsuctr { EelmType atdaMAXSIZ[]E;in tlen;/ 线性表中/实元际素数个 Sq}Lit;s

01327-2-8

v