數(shù)據(jù)線性結(jié)構(gòu)、順序表及鏈表

1、數(shù)據(jù)線性結(jié)構(gòu)、數(shù)據(jù)線性結(jié)構(gòu)、順序表及鏈表順序表及鏈表數(shù)據(jù)的線性結(jié)構(gòu)數(shù)據(jù)的線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)特點(diǎn)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中：在數(shù)據(jù)元素的非空有限集中l(wèi)存在存在唯一唯一的一個(gè)被稱作的一個(gè)被稱作“第一個(gè)第一個(gè)”的數(shù)據(jù)元素的數(shù)據(jù)元素l存在存在唯一唯一的一個(gè)被稱作的一個(gè)被稱作“最后一個(gè)最后一個(gè)”的數(shù)據(jù)元素的數(shù)據(jù)元素l除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)只有一個(gè)前驅(qū)前驅(qū)l除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一只有一個(gè)后繼個(gè)后繼l1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)l定義：一個(gè)線性表是定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有

2、限序列個(gè)數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一個(gè)線性表例學(xué)號(hào)姓名年齡001張三18002李四19數(shù)據(jù)元素特征：v元素個(gè)數(shù)n表長(zhǎng)度，n=0空表v1idata表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp-link表示p指向結(jié)點(diǎn)的指針域生成一個(gè)JD型新結(jié)點(diǎn)：p=(JD *)malloc(sizeof(JD);系統(tǒng)回收p結(jié)點(diǎn)：free(p)線性鏈表v定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫，也叫單鏈表ha1a2頭結(jié)點(diǎn)an .h空表頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有

3、則返回指向X結(jié)點(diǎn)的指針；否則返回NULL 算法描述While循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為n nOnTpabxsu算法評(píng)價(jià)l插入：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法評(píng)價(jià) 算法描述pabc 1OnTu算法評(píng)價(jià)l刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap-link=p-link-link; nOnTl動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針u算法描述u算法評(píng)價(jià)h頭結(jié)點(diǎn)an 0h頭結(jié)點(diǎn)an-10an a2.h頭結(jié)點(diǎn)an-10an ha1a2頭結(jié)點(diǎn)an .0

4、h頭結(jié)點(diǎn)0單鏈表特點(diǎn)單鏈表特點(diǎn) 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 不需預(yù)先分配空間 指針占用額外存儲(chǔ)空間 不能隨機(jī)存取，查找速度慢l循環(huán)鏈表循環(huán)鏈表(circular linked list)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率，提高查找效率操作與單鏈表基本一致操作與單鏈表基本一致,循環(huán)條件不同循環(huán)條件不同 單鏈表p或p-link=NULL 循環(huán)鏈表p或p-link=Hhh空表l雙向鏈表（雙向鏈表（do

5、uble linked list）單鏈表具有單向性的缺點(diǎn)單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義結(jié)點(diǎn)定義typedef struct node datatype element; struct node *prior,*next;JD;prior element nextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);v刪除l算法描述l算法評(píng)價(jià)：T(n)=O(1)p-prior-next=p

6、-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法評(píng)價(jià)：T(n)=O(1)xSbaPv插入l4 線性表的應(yīng)用舉例線性表的應(yīng)用舉例 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加l一元多項(xiàng)式的表示：一元多項(xiàng)式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示200001000231)(xxxS但

7、對(duì)S(x)這樣的多項(xiàng)式浪費(fèi)空間一般emmnxPxPxPxPee2121)(其中為非零系數(shù)）（iPemee210用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示emPePePm，2121其存儲(chǔ)結(jié)構(gòu)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用單鏈表l單鏈表的結(jié)點(diǎn)定義單鏈表的結(jié)點(diǎn)定義coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多項(xiàng)式相加typedef struct node int coef,exp; struct node *ne

8、xt;JD;設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)比較p-exp與q-expp-exp exp: p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) p后移,q不動(dòng)p-exp q-exp: q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) 將q插在p之前,q后移,p不動(dòng)p-exp = q-exp: 系數(shù)相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數(shù)域, 釋放q，p,q后移直到p或q為NULL 若q=NULL，結(jié)束 若p=NULL，將B中剩余部分連到A上即可運(yùn)算規(guī)則q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8