線性表2

1、2．3 線性表的鏈式表示與實現,順序表示的優(yōu)點是隨機存取表中的任意元素；順序表示的弱點是在作插入或刪除操作時，需移動大量元素。鏈式表示 ---- 沒有順序表示的弱點，也失去了順序表示的優(yōu)點。,插入、刪除靈活方便，不需要移動結點，只要改變結點中指針域的值即可。 適合于線性表是動態(tài)變化的,不進行頻繁查找操作、但經常進行插入刪除時使用。   因為鏈表的查找只能從頭指

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

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

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

5、。,頭結點,,頭指針,頭指針L,,有時為了操作方便，在第一個結點之前虛加一個“頭結點”，以指向頭結點的指針為鏈表的頭指針。頭結點指針域為空則表為空。頭指針具有標識作用，因而，常用作鏈表的名字。,空指針,線性表為空表時，頭結點的指針域為空,,?,typedef struct LNode { ElemType data; // 數據域 struct LNode *next; // 指針域

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

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

8、據元素。,單鏈表存儲結構的操作1（算法2.8）,Status GetElem_L(LinkList &L, int i, ElemType &e){ // L為帶頭結點的單鏈表的頭指針;當第i個元素存在時，其值賦給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 時間復雜度為O（n）,,LinkList LinkListGet(LinkList L,int i);{//在單鏈表L中查找第i個元素結點，返回該結點指針，否則返回空 LinkList p; int j; if (inext;j=1;

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

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

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

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

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

15、刪除第i個元素，并由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) 在鏈表中的實現:,void ClearList(&L) { // 將單鏈表重新置為一個空表 while (L->next) { p=L->next; L->next=p->ne

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

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

19、 LinkListLocate(LinkList L,ElemType x) {//在單鏈表L中查找值為x的結點，找到后返回其指針，否則返回空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;},按值查找:,線性鏈表其他操作的實現(4),LinkList LinkListLocate(LinkList L, LNode *p) {//在單鏈表L中求p指向的結點(假定存在）的前驅 LinkList pre; if(L->next==p){printf(“p指向第一元素結點，無前驅”);exit(0)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、結點p插入到結點pa之后：p->next=pa->next;pa->next=p;2、將結點p插入到pa之前，可轉換為將p插在pa之后，方法為：先將結點p插入到結點pa之后，再交換二者的數據域。 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可轉換為刪除pa的后繼，方法為：先pa后繼的數據域覆蓋pa的數據域，再刪除pa的后繼。pa->data=pa->next->data;p=pa->next;pa->next=pa->next->next;free(p);,回顧 2.1 節(jié)中三個例子的算法，看一下當線性表分別以順序存儲結構和鏈表

43、存儲結構實現時，它們的時間復雜度為多少？,,,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,控制結構：基本操作：,for 循環(huán)GetElem, LocateElem 和 ListInsert,當以順序映像實現抽象數據類型線性表時為: O( ListLength(La)×ListLength(Lb) ),,當以鏈式映像實現抽象數據類型線性表時為: O( ListLength(La)&

45、#215;ListLength(Lb) ),例2-1,算法時間復雜度,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,控制結構：基本操作：,for 循環(huán)GetElem 和 ListInsert,當以順序映像實現抽象數據類型線性表時為: O( ListLength(Lb) ),當以鏈式映像實現抽象數據類型線性表時為: O( ListLength2

47、(Lb) ),例2-2,算法時間復雜度,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; } } … …,控制結構：基本操作：,三個并列的while循環(huán)GetElem, ListInsert,當以順序映像實現抽

49、象數據類型線性表時為: O( ListLength(La)+ListLength(Lb) ),當以鏈式映像實現抽象數據類型線性表時為: O( ListLength 2(La)+ListLength 2(Lb) ),例2-3,算法時間復雜度,算法2.12?,靜態(tài)單鏈表存儲結構,借用一維數組描述線性鏈表(不用指針)特點：插入/刪除時不需移動元素，只需修改指針#define MAXSIZE 1000Typedef s

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

51、ata為第一個數據元素。i=S[i].cur的操作為指針后移。,一般地，若第i個分量表示鏈表的第k個結點，則S[i].cur指示第k+1個結點位置。因此可以用游標i代替動態(tài)指針p。書P32算法2.13—2.17用全局整型變量av指出可利用空間的下標。,靜態(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; /*返回可利用空間表的下標 */ },靜態(tài)鏈表的申請結點空間,int GetNode() /* 取結點 */ {if (av!=-1) /* -1表示無空間 */

53、 {p=av; av=S[av].cur;} /* p為可利用空間的下標 */ return p; },靜態(tài)鏈表的釋放結點空間,int FreeNode(int p) /* 將p歸還到可利用空間表中 */ {S[p].cur=av; av=p; return av; },靜態(tài)鏈表的操作舉例（1）,（1）查找值為x的結點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第個結點ElemType Locate(SLinkList S, int i) {int j=1; if (

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

56、第i個結點void Insert(SLinkList SL, ElemType x, int i) /* 在靜態(tài)鏈表的第i個元素前插入元素x i>0 */ {pre=0; /* 前驅 */ 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(“參數錯誤 ”) ;exit(0);} /* 所給i值太大 */ } },靜態(tài)鏈表的操作舉例（4）,(4)刪除第i個結點 int Delete(SLinkL

59、ist S, int i) /* 在靜態(tài)鏈表中刪除第i個元素 i>0 */ {pre=0; /* 前驅 */ 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)鏈表的特點 ---- 表中的最后一個結點的指針域指向頭結點, 整個鏈表形成一個環(huán)。從表的任意結點出發(fā)可以找到表中其它結點。操作基本相同，只是循環(huán)

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

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

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

64、針域，使鏈表可以進行雙方向查找。用這種結點結構組成的鏈表稱為雙向鏈表。,雙向鏈表的操作特點：,“查詢” 和單鏈表相同。,“插入” 和“刪除”時需要同時修改兩個方向上的指針。,插入結點：指針p所指的結點前插入指針s所指的結點,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,,,,,,,,插入,插入結點程序,Status ListInsert_DuL(DuLinklist &L, int i, ElemType e){DuLinklist s,p; if (!(p=GetElemP_DuL(L,i))) // 在L中

66、確定第i個元素的位置指針p return ERROR; if(!(s = (DuLinklist)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; // 構造數據為e的結點s s->prior = p->prior; p-> prior ->next = s; s->next =

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

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

69、元素的位置指針p return ERROR; e = p->data; // 刪除的結點的值存入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）,假設一個單循

71、環(huán)鏈表，其結點含有三個域pre、data、link。其中data為數據域；pre為指針域，它的值為空指針（null）；link為指針域，它指向后繼結點。請設計算法，將此表改成雙向循環(huán)鏈表。,void SToDouble（LinkList la）// la是結點含有pre，data，link三個域的單循環(huán)鏈表。其中data為數據域； pre為空指針域，link是指向后繼的指針域。本算法將其改造成雙向循環(huán)鏈表。,{while（la-&