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

1、2.1.2抽象數(shù)據(jù)類型線性表的定義ADJ List 數(shù)據(jù)對象：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的長度 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個元素 7.E

2、mptyList(L) /判斷L是否為空表 8.ClearList(&L) /置L為空表 . ADJ List說 明1.刪除表L中第i個數(shù)據(jù)元素,記作:DeleteElem(&L,i) L=(a1,a2,.,ai,a(i+1),.,an) 指定序號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ù)項

3、的值)為e的元素。 給定:L=(a1,a2,.,ai,.,an)和元素e 若有一個 ai=e，則稱“查找成功”,i=1,2,.,n 否則，稱“查找失敗”。5.排序-按元素值或某個數(shù)據(jù)項值的遞增（或遞減）次序 重新排列表中各元素的位置。 例.排序前: 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 線性表的順序表示（順序存儲結(jié)構(gòu)） 2.2.1.順序分配將線性表中的數(shù)據(jù)元素依次存放到計算 機存儲器中一組地址連續(xù)的存儲單元中, 這種分配方式稱為 順序分配或順序映像。由此得到的存儲結(jié)構(gòu)稱為順序存儲結(jié) 構(gòu)或向量(一維數(shù)組）。 例. a=(30,40,10,55,24,80,66) 內(nèi)存狀態(tài) C語言中靜態(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)順序存儲結(jié)構(gòu)的一般形式 序號 存

5、儲狀態(tài) 存儲地址 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個數(shù)據(jù)元素所占存儲單元的數(shù)目。 maxleng-最大長度,為某個常數(shù)。 a1 a2 . ai . an / / /2.2.2 線性表順序結(jié)構(gòu)在C語言中的定義例1.分別定義元素所占空間、表長、尾元素的位置 #define maxleng 100 ElemType lamaxleng+1；/下標:0,1,maxleng int length； /當(dā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語言中的定義例2.元素所占空間和表長合并為C語言的一個結(jié)構(gòu)類型： #define maxleng 100 typedef struct ElemType elemmaxleng；/下標:0,1,.,maxleng-1 int length； /表長 SqList； SqList La； . 其中：typedef-別名定義，SqList-結(jié)構(gòu)類型名 La-結(jié)構(gòu)類型變量名 La.length-表長 La.e

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

8、egth個元素，在 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 依次后移一個位置 插入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個元素，在 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； /向后移動元素 L.elemi-1=e； /插入新元素 L.length+； /長度變量增1 return OK /插入成功 算法2。4的說明（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；/增加存儲容量 2.2.5 插入操作移動元素次數(shù)的分析 在（a1,a2,.,ai,.an)中ai之前插入新元素e ( 1=i=

11、n+1 ) 當(dāng)i=1 2 3 j n n+1移動元素次數(shù)個數(shù): n n-1 n-2 n-i+1 1 0 假定pi是在各位置插入元素的概率相同，則插入一個元素時移動元素的平均值是： 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 刪除操作移動元素次數(shù)的分析 當(dāng) i=1 2 3 . i . n 移動元素次數(shù)個數(shù)= n-1 n-2 . n-i . 0 假定qi是在各位置插入元素的概率相同，則刪除一個元素時移動元素的平均值是:

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