線性表2

1、2．3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn),順序表示的優(yōu)點(diǎn)是隨機(jī)存取表中的任意元素；順序表示的弱點(diǎn)是在作插入或刪除操作時(shí)，需移動(dòng)大量元素。鏈?zhǔn)奖硎?---- 沒有順序表示的弱點(diǎn)，也失去了順序表示的優(yōu)點(diǎn)。,插入、刪除靈活方便，不需要移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。 適合于線性表是動(dòng)態(tài)變化的,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時(shí)使用。   因?yàn)殒湵淼牟檎抑荒軓念^指

2、針開始順序查找。,2．3．1 線性鏈表,線性表的鏈?zhǔn)奖硎?-----是可以用一組地址任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。以元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置) = 結(jié)點(diǎn) (表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表 ?? 稱作鏈表例： 線性表（趙，錢，孫，李，周，伍，鄭，王）的鏈?zhǔn)奖硎?（趙，錢，孫，李，

3、周，伍，張，王）的鏈?zhǔn)奖硎?1,13,19,25,31,37,43,7,頭指針：31(趙的地址),存儲(chǔ)地址:,,,,錢,,,,孫,,,,李,,,,周,,,,趙,,,,伍,,,,鄭,,,王,,,,H,^,邏輯上相鄰，物理上不要求相鄰。,,指示鏈表第一個(gè)結(jié)點(diǎn)的指針。整個(gè)鏈表存取必須從頭指針開始。,小結(jié)：,可以認(rèn)為利用小的零散空間“串”起來，表示線性表，即把線性表的元素分散插入到系統(tǒng)所控制的零散空間中，然后用“指針”串起來，組成一

4、個(gè)有序的線性表，用指針表示數(shù)據(jù)元素的邏輯關(guān)系。元素的存儲(chǔ)，可以是連續(xù)的，也可以不是連續(xù)的。結(jié)點(diǎn)至少包括數(shù)據(jù)元素和指針兩個(gè)區(qū)域。,鏈表相關(guān)的名稱,數(shù)據(jù)域、指針域：結(jié)點(diǎn)、頭結(jié)點(diǎn)指針(鏈):元素間邏輯關(guān)系映象鏈表、單鏈表(線性鏈表，只含一個(gè)指針域),,,,,a1,,,,a2,,,,a3,,L,,,,ai,,,,an,,,,^,以線性表中第一個(gè)數(shù)據(jù)元素 的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針。頭指針L為NULL，則為空表

5、。,頭結(jié)點(diǎn),,頭指針,頭指針L,,有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針。頭結(jié)點(diǎn)指針域?yàn)榭談t表為空。頭指針具有標(biāo)識(shí)作用，因而，常用作鏈表的名字。,空指針,線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?,?,typedef struct LNode { ElemType data; // 數(shù)據(jù)域 struct LNode *next; // 指針域

6、 } LNode, *LinkList;,二、結(jié)點(diǎn)和單鏈表的 C 語言描述,LinkList L； // L 為單鏈表的頭指針,單鏈表操作的實(shí)現(xiàn),GetElem(L, i, e) // 取第i個(gè)數(shù)據(jù)元素,ListInsert(&L, i, e) // 插入數(shù)據(jù)元素,ListDelete(&L, i, e) // 刪除數(shù)據(jù)元素,ClearList(&L) // 重置線性表為空表,Cr

7、eateList(&L, n) // 生成含 n 個(gè)數(shù)據(jù)元素的鏈表,線性表的操作 GetElem(L, i, &e)在單鏈表中的實(shí)現(xiàn):設(shè)i=3,j,1,2,3,,,,因此，查找第 i 個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較 j 和 i 。,單鏈表是一種順序存取的結(jié)構(gòu)，為找第 i 個(gè)數(shù)據(jù)元素，必須先找前 i-1 個(gè)數(shù)據(jù)元素。,令指針 p 始終指向線性表中第 j 個(gè)數(shù)

8、據(jù)元素。,單鏈表存儲(chǔ)結(jié)構(gòu)的操作1（算法2.8）,Status GetElem_L(LinkList &L, int i, ElemType &e){ // L為帶頭結(jié)點(diǎn)的單鏈表的頭指針;當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK, 否則返回ERROR. LinkList p; int j; p = L->next; j = 1; while (p && jnext; ++j;

9、} if(!p || j>i) return ERROR; e = p->data; return OK;} // GetElem_L 時(shí)間復(fù)雜度為O（n）,,LinkList LinkListGet(LinkList L,int i);{//在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，返回該結(jié)點(diǎn)指針，否則返回空 LinkList p; int j; if (inext;j=1;

10、while (p!=NULL && jnext; j++; }if (j==i) return p;else return NULL;},取第i個(gè)元素的程序2:,線性表的操作 ListInsert(&L, i, e) 在單鏈表中的實(shí)現(xiàn)：,有序?qū)?改變?yōu)?和,,LNode *p;p=（LNode *）malloc(sizeof(LNode))；則完成了申請(qǐng)一塊

11、LNode類型的存儲(chǔ)單元的操作，并將其地址賦值給變量p。 p?data=e;,因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為: 找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。,可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。若要在第 i 個(gè)結(jié)點(diǎn)之前插入元素，修改的是第 i-1 個(gè)結(jié)點(diǎn)的指針。,Status ListInsert_L(LinkList &L, int i, ElemType e) { //

12、L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 // 在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素 e } // LinstInsert_L,算法的時(shí)間復(fù)雜度為:,O(ListLength(L)),……,p = L; j = 0;while (p && j next; ++j; } // 尋找第 i-1 個(gè)結(jié)點(diǎn)if (!p || j > i-1) return ERR

13、OR; // i 大于表長(zhǎng)或者小于1,,s = (LinkList) malloc ( sizeof (LNode)); // 生成新結(jié)點(diǎn)s->data = e; s->next = p->next; p->next = s; // 插入return OK;,,s,p,,,,線性表的操作ListDelete (&L,

14、 i, &e)在鏈表中的實(shí)現(xiàn):,有序?qū)?和 改變?yōu)?,,,在單鏈表中刪除第 i 個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。,,,q = p->next; p->next = q->next; 或p->next=p->next->next e = q->data; free(q);,,p,,q,,,,刪除結(jié)點(diǎn)程序（算法2.10）

15、刪除第i個(gè)元素，并由e返回其值,Status ListDlete_L(LinkList L, int i, ElemType &e){ LinkList q,p; int j; p = L; j = 0; while(p->next && jnext;++j} if(!(p->next)||j>i-1) return ERROR; q = p->next;

16、 p->next = q->next; e = q->data; free(q); return OK;},,操作 ClearList(&L) 在鏈表中的實(shí)現(xiàn):,void ClearList(&L) { // 將單鏈表重新置為一個(gè)空表 while (L->next) { p=L->next; L->next=p->ne

17、xt; }} // ClearList,free(p);,算法時(shí)間復(fù)雜度：,O(ListLength(L)),線性鏈表其他操作的實(shí)現(xiàn)(1),LinkList LinkListInit(){//建立一個(gè)空的單鏈表 L=(LNode*)malloc(sizeof(LNode))； if (L==null) {printf(“無內(nèi)存空間可分配”);exit(0);} L->next=NULL;

18、 return L;},帶頭結(jié)點(diǎn)的單鏈表的初始化：,線性鏈表其他操作的實(shí)現(xiàn)(2),int LinkListLength(LinkList L){//求帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度 int j=0; p=L->next; //p指向第一結(jié)點(diǎn) while(p) {j++;p=p->next; } //移動(dòng)p指向下一結(jié)點(diǎn) return j;},求表長(zhǎng):,線性鏈表其他操作的實(shí)現(xiàn)(3),LinkList

19、 LinkListLocate(LinkList L,ElemType x) {//在單鏈表L中查找值為x的結(jié)點(diǎn)，找到后返回其指針，否則返回空LinkList p; int j; p=L->next; j=0; while(p!=NULL && p->data!=x) {p=p->next; j++;} if(p->data==x

20、) return p; else return null;},按值查找:,線性鏈表其他操作的實(shí)現(xiàn)(4),LinkList LinkListLocate(LinkList L, LNode *p) {//在單鏈表L中求p指向的結(jié)點(diǎn)(假定存在）的前驅(qū) LinkList pre; if(L->next==p){printf(“p指向第一元素結(jié)點(diǎn)，無前驅(qū)”);exit(0)

21、;} pre=L; while(pre!=NULL && pre->next!=p) pre=pre->next; if(pre) return pre; else return null;},查找結(jié)點(diǎn)的前驅(qū):,線性鏈表其他操作的實(shí)現(xiàn)(5),LinkList LinkListLocate(LinkList L, LNode *p) {//

22、在單鏈表L中求p指向的結(jié)點(diǎn)(假定存在）的后繼 LinkList pre; pre=L; while(pre!=NULL && pre->next!=p) pre=pre->next; if(p->next==null){printf(“p指向最后元素結(jié)點(diǎn)，無后繼”);exit(0);} else return p;},查找結(jié)點(diǎn)的后繼:,線性鏈表其他操作的實(shí)現(xiàn)(6),插入算法:

23、void LinkListInsert(LinkList L,LNode *p,ElemType x) {//在結(jié)點(diǎn)p之前插入元素為x的結(jié)點(diǎn)LinkList pre=L;while (pre!=NULL && pre->next!=p) pre=pre->next; //找p的直接前驅(qū) if(!pr

24、e) {printf(“不存在*p結(jié)點(diǎn)”)；exit(0);} s=(LNode*)malloc(sizeof(LNode)); //創(chuàng)建新結(jié)點(diǎn) s->data=x; //設(shè)置新結(jié)點(diǎn)的元素值 s->next=pre->next; pre->next=s; //插入新結(jié)點(diǎn)},線性鏈表其他操作的實(shí)現(xiàn)(7),刪除元素: void

25、 LinkListDel (LinkList L，int i) {//刪除單鏈表L上的第i個(gè)結(jié)點(diǎn) if (inext && jnext; j++}if(p->next==NULL || j>i) {printf(“刪除位置不正確”)；exit(0);} q=p->next; p->next=q->next; //從鏈表中刪除 free(q);

26、 //釋放被刪除結(jié)點(diǎn) },如何從線性表得到單鏈表？,鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入” 的過程。,例如：逆位序輸入 n 個(gè)數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。,操作步驟：,一、建立一個(gè)“空表”；,二、輸入數(shù)據(jù)元素an， 建立結(jié)點(diǎn)并插入；,三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；,,,,,,,,,,,,,,,,an,,,,,,,,,,an,,a

27、n-1,,,,,,四、依次類推，直至輸入a1為止。,,建立單鏈表－－頭插法:,void CreateList_L(LinkList &L, int n) { // 逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表} // CreateList_L,算法的時(shí)間復(fù)雜度為:,O(Listlength(L)),L = (LinkList) malloc (sizeof (LNode));L->next = N

28、ULL; // 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表,for (i = n; i > 0; --i) { p = (LinkList) malloc (sizeof (LNode)); scanf(&p->data); // 輸入元素值 p->next = L->next; L->next = p;}// 插入,LinkList LinkListCreat1( ){//

29、用頭插法建立帶頭結(jié)點(diǎn)的單鏈表 LinkList L; ElemType x; L=(LNode *)malloc(sizeof(LNode)); L->next=NULL; //初始化一個(gè)空鏈表，L為頭指針 scanf(&x); //x是和鏈表元素具有相同類型的變量 while (x!=flag) //flag為結(jié)束輸入的標(biāo)志 {//生成新結(jié)點(diǎn) p=(LNode *)malloc(

30、sizeof(LNode)); p->data=x; //輸入元素值 p->next=L->next; L->next=p; //插入到表頭 scanf(&x); //讀入下一個(gè)元素的值 } return L;},頭插法建立單鏈表另一算法:,建立單鏈表－－尾插法:,線性鏈表的插表尾建立算法,void CreateList_L(

31、LinkList &L, int n) { // 正序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表L = (LinkList) malloc (sizeof (LNode));q=L; // 先建立一個(gè)帶頭結(jié)點(diǎn)和尾指針的單鏈表for (i = 0; i data); // 輸入元素值 q->next = p;q = p;}// 插入 q->next=NULL; //

32、修改尾指針} // CreateList_L,LinkList LinkListCreat2( ){//用尾插法建立帶頭結(jié)點(diǎn)的單鏈表 LinkList L,q; L=(LNode*)malloc(sizeof(LNode)); L->next=NULL; q=L; scanf(&x); while (x!=flag) //設(shè)置結(jié)束標(biāo)志 {p=(LNode*)malloc(sizeo

33、f(LNode); p->data=x; //賦值元素值 q->next=p; //在尾部插入新結(jié)點(diǎn) q=p; //q 指向新的尾結(jié)點(diǎn) scanf(&x); } q->next=NULL; //最后結(jié)點(diǎn)的指針域放空指針 return L;},尾插法建立單鏈表算法2,鏈表的遍歷算法

34、:,void print(LinkList la) //非遞歸{LinkList p=la->next; while (p) {printf(“%c”,p->data); //假定數(shù)據(jù)為字符 p=p->next; } },void out(LinkList p) //遞歸{if(p) {out(p->next); printf(“%c”,p->d

35、ata); } },鏈表算法舉例1,請(qǐng)寫一個(gè)算法將單鏈表（a1,...,an）逆置為(an,...,a1)。LinkList invert1(LinkList head） /*逆置單鏈表*/ {LinkList p,r; p=head->next; //p為工作指針 head->next=null；//將頭結(jié)點(diǎn)的指針域置空 while（p!=null）

36、 {r=p->next； //暫存p的后繼 p->next=head->next； head->next=p； p=r； } return（head）； }//結(jié)束invert1函數(shù),鏈表算法舉例2,在一個(gè)非遞減有序的線性表中，有數(shù)值相同的元素存在。若存儲(chǔ)方式為單鏈表，設(shè)計(jì)算法去掉數(shù)值相同的元素，

37、使表中不再有重復(fù)的元素。分析算法的時(shí)間復(fù)雜度。LinkList DelSame(LinkList la） //la是非遞減有序的單鏈表，本算法去掉數(shù)值相同的元素 //使表中不再有重復(fù)的元素{LinkList p,pre,u; p=la->next->next； //p是工作指針。設(shè)鏈表中至少有一個(gè)結(jié)點(diǎn) pre=la->next； //pre是p所指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。

38、 while（p!=null） if（pre->data==p->data） //處理相同元素值的結(jié)點(diǎn) {u=p；p=p->next；free(u);} //釋放相同元素值的結(jié)點(diǎn) else //處理前驅(qū)，后繼元素值不同 {pre->next=p；pre=p；p=p->next；} pre->next

39、=p；//置鏈表尾 return (la); }算法時(shí)間復(fù)雜度為O(n),鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn),非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順序表。節(jié)約了大塊內(nèi)存適合于插入和刪除操作實(shí)際上用空間換取了時(shí)間，結(jié)點(diǎn)中加入了指針，使得這兩種操作轉(zhuǎn)換為指針操作;,線性表實(shí)現(xiàn)方法的比較,實(shí)現(xiàn)不同順序表方法簡(jiǎn)單，各種高級(jí)語言中都有數(shù)組類型，容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對(duì)來講復(fù)雜些。 存儲(chǔ)空間的占用和分配不同從存儲(chǔ)的角度考慮，順序

40、表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是說事先對(duì)“MAXSIZE”要有合適的設(shè)定，過大造成浪費(fèi)，過小造成溢出。當(dāng)然,可采用先分配一定大小的空間,若不夠再追加的方式。而鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的，不用事先估計(jì)存儲(chǔ)規(guī)模?？梢妼?duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，采用鏈表。線性表運(yùn)算的實(shí)現(xiàn)不同 按序號(hào)訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作 ，使用鏈表優(yōu)于順序表。,動(dòng)態(tài)線性鏈表插入/刪除操作小結(jié),1、將

41、結(jié)點(diǎn)p插入到結(jié)點(diǎn)pa之后：p->next=pa->next;pa->next=p;2、將結(jié)點(diǎn)p插入到pa之前，可轉(zhuǎn)換為將p插在pa之后，方法為：先將結(jié)點(diǎn)p插入到結(jié)點(diǎn)pa之后，再交換二者的數(shù)據(jù)域。 p->next=pa->next;pa->next=p;x=p->data;p->data=pa->data;pa-.data=x;3、刪除pa的后繼：p=pa->nex

42、t;pa->next=pa->next->next;free(p);4、刪除pa可轉(zhuǎn)換為刪除pa的后繼，方法為：先pa后繼的數(shù)據(jù)域覆蓋pa的數(shù)據(jù)域，再刪除pa的后繼。pa->data=pa->next->data;p=pa->next;pa->next=pa->next->next;free(p);,回顧 2.1 節(jié)中三個(gè)例子的算法，看一下當(dāng)線性表分別以順序存儲(chǔ)結(jié)構(gòu)和鏈表

43、存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)，它們的時(shí)間復(fù)雜度為多少？,,,void union(List &La, List Lb) { La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (!LocateElem(La, e, equal( ))

44、 ListInsert(La, ++La_len, e); }//for} // union,控制結(jié)構(gòu)：基本操作：,for 循環(huán)GetElem, LocateElem 和 ListInsert,當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength(La)×ListLength(Lb) ),,當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength(La)&

45、#215;ListLength(Lb) ),例2-1,算法時(shí)間復(fù)雜度,void purge(List &La, List Lb) { InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (ListEmpt

46、y(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } }//for} // purge,控制結(jié)構(gòu)：基本操作：,for 循環(huán)GetElem 和 ListInsert,當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength(Lb) ),當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength2

47、(Lb) ),例2-2,算法時(shí)間復(fù)雜度,void MergeList(List La, List Lb, List &Lc) { InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) {

48、 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } } … …,控制結(jié)構(gòu)：基本操作：,三個(gè)并列的while循環(huán)GetElem, ListInsert,當(dāng)以順序映像實(shí)現(xiàn)抽

49、象數(shù)據(jù)類型線性表時(shí)為: O( ListLength(La)+ListLength(Lb) ),當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength 2(La)+ListLength 2(Lb) ),例2-3,算法時(shí)間復(fù)雜度,算法2.12?,靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu),借用一維數(shù)組描述線性鏈表(不用指針)特點(diǎn)：插入/刪除時(shí)不需移動(dòng)元素，只需修改指針#define MAXSIZE 1000Typedef s

50、truct{ ElemType data; int cur;游標(biāo)，指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置}component,SLinkList[MAXSIZE];SLinkList[0]可看成頭結(jié)點(diǎn)，cur從1開始,靜態(tài)鏈表圖示,線性表L=（2，3，4，6，8，9）的靜態(tài)鏈表圖示,,設(shè)S為SLinkList型變量，則S[0].cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置，設(shè)i=S[0].cur,則S[i].d

51、ata為第一個(gè)數(shù)據(jù)元素。i=S[i].cur的操作為指針后移。,一般地，若第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則S[i].cur指示第k+1個(gè)結(jié)點(diǎn)位置。因此可以用游標(biāo)i代替動(dòng)態(tài)指針p。書P32算法2.13—2.17用全局整型變量av指出可利用空間的下標(biāo)。,靜態(tài)鏈表的初始化,int Initilize() /* 初始可利用空間表 */ { int i; for (i=0;i<maxsize-1;i++) // 鏈

52、成可利用空間表 S[i].cur=i+1; S[maxsize-1].cur=-1; /* 鏈表尾 */ av=1; return av; /*返回可利用空間表的下標(biāo) */ },靜態(tài)鏈表的申請(qǐng)結(jié)點(diǎn)空間,int GetNode() /* 取結(jié)點(diǎn) */ {if (av!=-1) /* -1表示無空間 */

53、 {p=av; av=S[av].cur;} /* p為可利用空間的下標(biāo) */ return p; },靜態(tài)鏈表的釋放結(jié)點(diǎn)空間,int FreeNode(int p) /* 將p歸還到可利用空間表中 */ {S[p].cur=av; av=p; return av; },靜態(tài)鏈表的操作舉例（1）,（1）查找值為x的結(jié)點(diǎn)int Loca

54、te(SLinkList S, ElemType x) {p=S[0].next; while(p!=-1 && S[p].data!=x) p=S[p].cur; return p; },靜態(tài)鏈表的操作舉例（2）,(2)查找i第個(gè)結(jié)點(diǎn)ElemType Locate(SLinkList S, int i) {int j=1; if (

55、i<0) {printf(“參數(shù)錯(cuò)誤 ”) ;exit(0);} p=S[0].cur; while(p!=-1 && j<i) {p=S[p].cur; j++;} if (p==-1) {printf(“參數(shù)錯(cuò)誤 ”) ;exit(0);} return S[i].data; },靜態(tài)鏈表的操作舉例（3）,(3)插入

56、第i個(gè)結(jié)點(diǎn)void Insert(SLinkList SL, ElemType x, int i) /* 在靜態(tài)鏈表的第i個(gè)元素前插入元素x i>0 */ {pre=0; /* 前驅(qū) */ j=1; s=GetNode(); if (s==-1) {printf(“overflow\n”); exit(0);} /* 無空間 */ else {p=S[0].cur;

57、 while(p!=-1 && j<i) /* 查找插入位置 */ { j++; pre=p; p=S[p].cur; } if (j==i) {S[s].data=x; /* 賦值x ,鏈入表中*/ S[pre

58、].cur=s; S[s].cur=p; } /* 插入 */ else {printf(“參數(shù)錯(cuò)誤 ”) ;exit(0);} /* 所給i值太大 */ } },靜態(tài)鏈表的操作舉例（4）,(4)刪除第i個(gè)結(jié)點(diǎn) int Delete(SLinkL

59、ist S, int i) /* 在靜態(tài)鏈表中刪除第i個(gè)元素 i>0 */ {pre=0; /* 前驅(qū) */ j=1; p=S[0].cur; /* 查找刪除元素 */ while(p!=-1 && j<i) { j++; pre=p; p=S[p].cur; } if (p==-1){printf(“

60、i is too big ”);exit(0);} /* i值太大 */ else {S[pre].cur=S[p].cur; av=FreeNode(p); } /* 刪除 */ return av; },循環(huán)鏈表的特點(diǎn) ---- 表中的最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn), 整個(gè)鏈表形成一個(gè)環(huán)。從表的任意結(jié)點(diǎn)出發(fā)可以找到表中其它結(jié)點(diǎn)。操作基本相同，只是循環(huán)

61、判定條件不同。判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”,2．3．2 循環(huán)鏈表,,,,a1,,,,a2,,,,a3,,,,,L,,,,ai,,,,an,,,,單循環(huán)鏈表:,循環(huán)鏈表往往只設(shè)尾指針,連接兩個(gè)只設(shè)尾指針的單循環(huán)鏈表L1和L2,操作如下：p= R1 –>next; //保存L1 的頭結(jié)點(diǎn)指針R1->next=R2->next->next; //頭尾連接

62、free(R2->next); //釋放第二個(gè)表的頭結(jié)點(diǎn) R2->next=p;,2．3．3 雙向鏈表,雙向鏈表的特點(diǎn) ---- 表中的每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向后繼結(jié)點(diǎn)，一個(gè)指向前趨結(jié)點(diǎn), 整個(gè)鏈表形成兩個(gè)環(huán)。從表的任意結(jié)點(diǎn)出發(fā)可以通過正向環(huán)（或反向環(huán)）找到表中其它結(jié)點(diǎn)。,,,prior,data,next,結(jié)點(diǎn)：,typedef struct DuLnode{ ElemType data;

63、 Struct DuLnode *prior; Struct DuLnode *next;}DuLnode, *DuLinklist;,雙向循環(huán)鏈表,空表,非空表,a1 a2 … ... an,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,希望查找前驅(qū)的時(shí)間復(fù)雜度達(dá)到O(1)，我們可以用空間換時(shí)間,每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指

64、針域，使鏈表可以進(jìn)行雙方向查找。用這種結(jié)點(diǎn)結(jié)構(gòu)組成的鏈表稱為雙向鏈表。,雙向鏈表的操作特點(diǎn)：,“查詢” 和單鏈表相同。,“插入” 和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。,插入結(jié)點(diǎn)：指針p所指的結(jié)點(diǎn)前插入指針s所指的結(jié)點(diǎn),s->prior = p->prior; p-> prior ->next = s; s->next = p; p->prior = s;,s->ne

65、xt = p->next; p->next = s;s->next->prior = s; s->prior = p;,p,s,,,,,,,,插入,插入結(jié)點(diǎn)程序,Status ListInsert_DuL(DuLinklist &L, int i, ElemType e){DuLinklist s,p; if (!(p=GetElemP_DuL(L,i))) // 在L中

66、確定第i個(gè)元素的位置指針p return ERROR; if(!(s = (DuLinklist)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; // 構(gòu)造數(shù)據(jù)為e的結(jié)點(diǎn)s s->prior = p->prior; p-> prior ->next = s; s->next =

67、p; p->prior = s; return OK;} // ListInsert_DuL,,刪除結(jié)點(diǎn)：刪除指針p所指的結(jié)點(diǎn),a1,a2,p,刪除前：,刪除后：,p->prior->next =p->next,a3,,,,,,,,,,,,,,,,a1,a2,p,a3,,,,,,,,,,,,,,,p->next->proir =p->prior,釋放結(jié)點(diǎn)： free(p

68、);,刪除,p->next = p->next->next;p->next->prior = p;,,,p,,,刪除結(jié)點(diǎn)程序刪除第i個(gè)元素，并由e返回其值,Status ListDelete_DuL(DuLinklist &L, int i, ElemType &e){DuLinklist p; if (!(p=GetElemP_DuL(L,i))) // 在L中確定第i個(gè)

69、元素的位置指針p return ERROR; e = p->data; // 刪除的結(jié)點(diǎn)的值存入e p-> prior ->next = p->next; p->next->prior = p->prior; free(p); return OK;} // ListDelete_DuL,,鞏固雙向鏈表的插入,,p,,,,,

70、,,s,,p->prior = s;,1,2,s->prior = p->prior;,p->prior->next = s;,s->next = p;,3,4,鞏固雙向鏈表的刪除,,,,,p,,1,2,p->prior->next = p->next;P->next->prior = p->prior;free( p );,循環(huán)鏈表算法舉例（1）,假設(shè)一個(gè)單循

71、環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre、data、link。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（null）；link為指針域，它指向后繼結(jié)點(diǎn)。請(qǐng)?jiān)O(shè)計(jì)算法，將此表改成雙向循環(huán)鏈表。,void SToDouble（LinkList la）// la是結(jié)點(diǎn)含有pre，data，link三個(gè)域的單循環(huán)鏈表。其中data為數(shù)據(jù)域； pre為空指針域，link是指向后繼的指針域。本算法將其改造成雙向循環(huán)鏈表。,{while（la-&