數(shù)據(jù)結(jié)構(gòu)-b抽象數(shù)據(jù)類型線性表的定義

1、2.1.2抽象數(shù)據(jù)類型線性表的定義ADJ List 數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,.n,n=0 數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,.n 基本操作： 1.IiniList(&L) /構(gòu)造空表L。 2.LengthList(L) /求表L的長(zhǎng)度 3.GetElem(L,i,&e) /取元素ai,由e返回ai 4.PriorElem(L,ce,&pre_e) /求ce的前驅(qū),由pre_e返回 5.InsertElem(&L,i,e) /在元素ai之前插入新元素e 6.DeleteElem(&L,i) /刪除第i個(gè)元素 7.E

2、mptyList(L) /判斷L是否為空表 8.ClearList(&L) /置L為空表 . ADJ List說(shuō) 明1.刪除表L中第i個(gè)數(shù)據(jù)元素,記作:DeleteElem(&L,i) L=(a1,a2,.,ai,a(i+1),.,an) 指定序號(hào)i,刪除ai L=(a1,a2,.,ai,.,a(n-1) 2.指定元素值x,刪除表L中的值為x的元素,記作: DeleteElem(&L,x)；3.在元素ai之前插入新元素e(1=i=n) L=(a1,a2,.,ai,.,an) 插入e L=(a1,a2,.,ai,a(i+1).,a(n+1) 4.查找-確定元素值(或數(shù)據(jù)項(xiàng)

3、的值)為e的元素。 給定:L=(a1,a2,.,ai,.,an)和元素e 若有一個(gè) ai=e，則稱“查找成功”,i=1,2,.,n 否則，稱“查找失敗”。5.排序-按元素值或某個(gè)數(shù)據(jù)項(xiàng)值的遞增（或遞減）次序 重新排列表中各元素的位置。 例.排序前: L=(90,60,80,10,20,30) 排序后: L=(10,20,30,60,80,90) L變?yōu)橛行虮?6.將表La和表Lb合并為表Lc 例.設(shè)有序表： La=(2,14,20,45,80) Lb=(8,10,19,20,22,85,90) 合并為表 Lc=(2,8,10,14,19,20,20,22,45,80,85,90)7.將表La復(fù)

4、制為表Lb La=(90,14,20,45) Lb=(90,14,20,45) 2.2 線性表的順序表示（順序存儲(chǔ)結(jié)構(gòu)） 2.2.1.順序分配將線性表中的數(shù)據(jù)元素依次存放到計(jì)算 機(jī)存儲(chǔ)器中一組地址連續(xù)的存儲(chǔ)單元中, 這種分配方式稱為 順序分配或順序映像。由此得到的存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié) 構(gòu)或向量(一維數(shù)組）。 例. a=(30,40,10,55,24,80,66) 內(nèi)存狀態(tài) C語(yǔ)言中靜態(tài)一維數(shù)組的定義： int a11； 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 1030401055248066 (a1,a1,a2,.an)順序存儲(chǔ)結(jié)構(gòu)的一般形式 序號(hào) 存

5、儲(chǔ)狀態(tài) 存儲(chǔ)地址 1 b 2 b+p i b+(i-1)*p n b+(n-1)*p 自由區(qū) maxleng b+(maxleng-1)*p其中: b-表的首地址/基地址/元素a1的地址。 p-1個(gè)數(shù)據(jù)元素所占存儲(chǔ)單元的數(shù)目。 maxleng-最大長(zhǎng)度,為某個(gè)常數(shù)。 a1 a2 . ai . an / / /2.2.2 線性表順序結(jié)構(gòu)在C語(yǔ)言中的定義例1.分別定義元素所占空間、表長(zhǎng)、尾元素的位置 #define maxleng 100 ElemType lamaxleng+1；/下標(biāo):0,1,maxleng int length； /當(dāng)前長(zhǎng)度 int last； /an的位置 或：a1a2.

6、ai. ana1a2. ai. an 0 1 i1 n-1 n maxleng 0 1 2 i n maxleng last=length=nlast=length-1=n-1線性表順序結(jié)構(gòu)在C語(yǔ)言中的定義例2.元素所占空間和表長(zhǎng)合并為C語(yǔ)言的一個(gè)結(jié)構(gòu)類型： #define maxleng 100 typedef struct ElemType elemmaxleng；/下標(biāo):0,1,.,maxleng-1 int length； /表長(zhǎng) SqList； SqList La； . 其中：typedef-別名定義，SqList-結(jié)構(gòu)類型名 La-結(jié)構(gòu)類型變量名 La.length-表長(zhǎng) La.e

7、lem0-a1 La.elemLa.length-1-an 2.2.3 順序存儲(chǔ)結(jié)構(gòu)的尋址公式 i= 1 2 i n 地址= b b+p b+(i-1)p b+(n-1)p 假設(shè): 線性表的首地址為b,每個(gè)數(shù)據(jù)元素占p個(gè)存儲(chǔ) 單元,則表中任意元素ai(1in)的存儲(chǔ)地址是: LOC(i)=LOC(1)+(i-1)*p =b+(i-1)*p (1in) 例: 假設(shè) b=1024, p=4,i=35 LOC(i)=b+(i-1)*p =1024+(35-1)*4 =1024+34*4 =1160 a1a2. ai. an/ 2.2.4 插入算法實(shí)現(xiàn)舉例 設(shè) L.elem0.maxleng-1中有l(wèi)

8、egth個(gè)元素，在 L.elemi-1之前插入新元素e，1=i=length 例. i=3,e=6,length=6 插入6之前： 2 5 8 20 30 35 / / / 0 1 2 3 4 5 6 7 8 35,30,20,8 依次后移一個(gè)位置 插入6之后： 2 5 6 8 20 30 35 / / 0 1 2 3 4 5 6 7 8 a1 a2 . ai . an / / / 0 1 2 .i-1 . n-1 maxleng-1 插入操作“類C”算法： /設(shè) L.elem0.maxleng-1中有l(wèi)egth個(gè)元素，在 L.elemi-1之前插入新元素e，(1=i=length) Stat

9、us ListInsert_Sq(SqList &L,int i,ElemType e) if (iL.length+1)return ERROR /i值不合法 if (L.length=maxleng)exit(OVERFLOW) /溢出 for (j=L.length-1；j=i-1；j-；) L.elemj+1=L.elemj； /向后移動(dòng)元素 L.elemi-1=e； /插入新元素 L.length+； /長(zhǎng)度變量增1 return OK /插入成功 算法2。4的說(shuō)明（p.24） Status ListInsert_Sq(SqList &L,int i,ElemType

10、 e) if (iL.length+1)return ERROR /i值不合法 if (L.length=L.listsize) newbase =(ElemType * )realloc (L.elem, (L.listsize+LISTINCREMENT) * sizeof(ElemType)； if (! newbase) exit(OVERFLOW)；/分配失敗 L.elem = newbase； /新基址L.listsize += LISTINCREMENT；/增加存儲(chǔ)容量 2.2.5 插入操作移動(dòng)元素次數(shù)的分析 在（a1,a2,.,ai,.an)中ai之前插入新元素e ( 1=i=

11、n+1 ) 當(dāng)i=1 2 3 j n n+1移動(dòng)元素次數(shù)個(gè)數(shù): n n-1 n-2 n-i+1 1 0 假定pi是在各位置插入元素的概率相同，則插入一個(gè)元素時(shí)移動(dòng)元素的平均值是： n+1 Eis=pi(n-i+1)=1/(n+1)*(n+(n-1)+.+1+0)=n/2 i=1 其中：p1=p2=.=pn=p(n+1)=1/(n+1) a1 a2 . ai . an 1 2 i n n+1 2.2.6 刪除操作移動(dòng)元素次數(shù)的分析 當(dāng) i=1 2 3 . i . n 移動(dòng)元素次數(shù)個(gè)數(shù)= n-1 n-2 . n-i . 0 假定qi是在各位置插入元素的概率相同，則刪除一個(gè)元素時(shí)移動(dòng)元素的平均值是:

12、 n Edl=qi(n-i)=1/n*(n-1)+.+1+0)=(n-1)/2 i=1 其中：q1=q2=.=qn=1/n 2.2.5 插入操作移動(dòng)元素次數(shù)的分析 在（a1,a2,.,ai,.an)中ai之前插入新元素e ( 1=i=n+1 ) 當(dāng)i=1 2 3 j n n+1移動(dòng)元素次數(shù)個(gè)數(shù): n n-1 n-2 n-i+1 1 0 假定pi是在各位置插入元素的概率相同，則插入一個(gè)元素時(shí)移動(dòng)元素的平均值是： n+1 Eis=pi(n-i+1)=1/(n+1)*(n+(n-1)+.+1+0)=n/2 i=1 其中：p1=p2=.=pn=p(n+1)=1/(n+1) 2.2.7 順序存儲(chǔ)結(jié)構(gòu)的評(píng)價(jià) 1.優(yōu)點(diǎn)： (1)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù)，速度快； (2)結(jié)構(gòu)簡(jiǎn)單，邏輯上相鄰的元素在物理上也是相鄰的； (3)不使用指針，節(jié)省存儲(chǔ)空間。 2.缺點(diǎn)： (1)插入和刪除元素要移動(dòng)大量元素，消耗大量時(shí)間； (2)需要一個(gè)連續(xù)的存儲(chǔ)空間； (3)插入元素可能發(fā)生“溢出”； (4)自由區(qū)中的存儲(chǔ)空間不能被其它數(shù)據(jù)占用(共享)。內(nèi)存：2k 占用 5k 占用 3k 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1單鏈表 1 單鏈表的結(jié)點(diǎn)結(jié)構(gòu): data next 前一個(gè)結(jié)點(diǎn) 下一個(gè)結(jié)點(diǎn) 結(jié)點(diǎn)類型說(shuō)明: typedef struct Lnode ElemTyp