第二章線性表線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中·存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素·存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素·除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)·除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼2.1線性表的邏輯結(jié)構(gòu)·定義:一個線性表是n個數(shù)據(jù)元素的有限序列例英文字母表(A,B,C,…..Z)是一個線性表例數(shù)據(jù)元素·特征:·元素個數(shù)n—表長度，n=0空表·1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼·元素同構(gòu)，且不能出現(xiàn)缺項2.2線性表的順序存儲結(jié)構(gòu)·順序表:·定義:用一組地址連續(xù)的存儲單元存放一個線性表叫~·元素地址計算方法:LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中:L—一個元素占用的存儲單元個數(shù)LOC(ai)—線性表第i個元素的地址·特點(diǎn):實(shí)現(xiàn)邏輯上相鄰—物理地址相鄰實(shí)現(xiàn)隨機(jī)存取·實(shí)現(xiàn):可用C語言的一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1線性表的動態(tài)分配順序存儲結(jié)構(gòu)#define

LIST_SIZE

100#define

LISTINCREMENT

10typedef

struct

{ElemType

*elem;length;listsize;intint}Sqlist;備用空間·插入·定義：線性表的插入是指在第I（1 i n+1)個元素前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表變成長度為n+1的線性表需將第i至第n共(n-i+1)個元素后移·算法Ch2_1.ca1a2aiai+1an01i-1V數(shù)組下標(biāo)in-1n12i內(nèi)存 元素序號i+1nn+1a1a2ai+101i-1V數(shù)組下標(biāo)in-1n12i內(nèi)存 元素序號i+1nn+1an-1anxai·算法時間復(fù)雜度T(n)設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為:i n)個元素刪·刪除·定義：線性表的刪除是指將第i(1使長度為n的線性表變成長度為n-1的線性表需將第i+1至第n共(n-i)個元素前移·算法Ch2_2.ca1a2aiai+1an01i-1V數(shù)組下標(biāo)in-1n12i內(nèi)存 元素序號i+1nn+1a1a2ai+1V數(shù)組下標(biāo)01i-1in-2n-112i內(nèi)存 元素序號i+1n-1nanai+2·算法評價設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為:故在順序表中插入或刪除一個元素時,平均移動表的一半元素,當(dāng)n很大時,效率很低·順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)·優(yōu)點(diǎn)邏輯相鄰,物理相鄰可隨機(jī)存取任一元素存儲空間使用緊湊·缺點(diǎn)插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配,利用不充分表容量難以擴(kuò)充2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn):·用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素·利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素·每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息·結(jié)點(diǎn)數(shù)據(jù)域:元素本身信息指針域:指示直接后繼的存儲位置結(jié)點(diǎn)數(shù)據(jù)域指針域ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表

(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域

指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址17131925313743H31頭指針·實(shí)現(xiàn)typedef

struct

Lnode

{ElemType

data;struct

Lnode

*next;}Lnode,*LinkList;生成一個LinkList型新結(jié)點(diǎn):p=(LinkList)malloc(sizeof(Lnode));系統(tǒng)回收p結(jié)點(diǎn):free(p)·線性鏈表·定義:結(jié)點(diǎn)中只含一個指針域的鏈表叫~，也叫單鏈表頭結(jié)點(diǎn):在單鏈表第一個結(jié)點(diǎn)前附設(shè)一個結(jié)點(diǎn)叫~頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空ha1a2頭結(jié)點(diǎn)an

^…...h空表^·單鏈表的基本運(yùn)算px查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針;否則返回NULL算法描述算法評價若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號While循環(huán)中語句頻度為否則，為n插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向abs->next=p->next;ap->next=ss;算法描述算法評價算法描述算法評價刪除:單鏈表中刪除b，設(shè)p指向ap a b cp->next=p->next->next;動態(tài)建立單鏈表算法:設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu價anan-1a12

^ana…2

..^.an

^an…-1

...Ch2_3.ch頭結(jié)點(diǎn)0^·單鏈表特點(diǎn)它是一種動態(tài)結(jié)構(gòu),整個存儲空間為多個鏈表共用不需預(yù)先分配空間指針占用額外存儲空間不能隨機(jī)存取,查找速度慢·循環(huán)鏈表(circular

linked

list)·循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀·特點(diǎn):從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率·操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=Hhh空表·雙向鏈表（doublelinkedlist)單鏈表具有單向性的缺點(diǎn)·結(jié)點(diǎn)定義typedef

struct

Dulnode

{elemtype

data;struct

Dulnode

*prior,*next;}

Dulnode,*Dulinklist;priordatanextL空雙向循環(huán)鏈表:ABbc非空雙向循環(huán)鏈表a:Lpp->prior->next=

p=

p->next->proir;b

cavoid

del_dulist(Dulinklist

p){p->prior->next=p->next;p->next->prior=p->prior;free(p);}·刪除算法描述算法評價:T(n)=O(1)p->prior->next=p->next;p->next->prior=p->priorPvoid

ins_dulist(Dulinklist

p,int

x){Dulinklist

s;s=(Dulinklist)malloc(sizeof(Dulnode

s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;}算法描述算法評價:T(n)=O(1)xSbaP·插入2.4線性表的應(yīng)用舉例一元多項式的表示及相加·一元多項式的表示:可用線性表P表示但對S(x)這樣的多項式浪費(fèi)空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表·單鏈表的結(jié)點(diǎn)定義typedef

struct

node{

int

coef,exp;struct

node

*next;coefexpnextABC-1703198517^-181227-98^-170111227517^}JD;·一元多項式相加比較p->exp與q->exp設(shè)p,q分別指向A,B中某一結(jié)點(diǎn),p,q初值是第一結(jié)點(diǎn)p->exp<q->exp:p結(jié)點(diǎn)是和多項式中的一項p后移,q不動p->exp=q->exp:系數(shù)相加p->exp>q->exp:q結(jié)點(diǎn)是和多項式中的一項將q插在p之前,q后移,p不動0:從A表中刪去p,釋放p,q,p,q后移0:修改p系數(shù)域,釋放q，p,q后移若q==NULL,結(jié)束直到p或q為NULL若p==