數(shù)據(jù)結(jié)構(gòu)-第3章-鏈表演示課件

.,第3章 鏈表,3.1 線性表的鏈式存儲結(jié)構(gòu)表示3.2 單鏈表的基本操作3.3 單鏈表應(yīng)用舉例3.4 循環(huán)鏈表3.5 雙向鏈表3.6 各種鏈式存儲結(jié)構(gòu)的比較3.7 順序表與鏈表的結(jié)構(gòu)和應(yīng)用比較 3.8 鏈表應(yīng)用舉例3.9 小結(jié)習(xí)題3,.,3.1 線性表的鏈式存儲結(jié)構(gòu)表示,圖3-1所示為結(jié)點結(jié)構(gòu)表示。從鏈表的整體結(jié)構(gòu)上看，鏈表可以是空鏈，也可以由一個或多個結(jié)點組成。每條鏈有一個入口的頭結(jié)點，該結(jié)點僅指示鏈中第一個結(jié)點的地址。如是空鏈，則可表示為“0”或“”，它類似于一個常量。每條鏈的最后一個結(jié)點的鏈指針為“0”，也可用“”作為鏈的結(jié)束標志。圖3-2給出了鏈表的示意形式。圖3-2(a)中有一個頭結(jié)點和具有A、B、C、D數(shù)據(jù)元素的鏈，圖3-2(b)所示為線性鏈表的一般表示，結(jié)點與結(jié)點之間用箭頭鏈接。,.,圖3-1 結(jié)點結(jié)構(gòu),.,圖3-2 線性鏈表圖示(a) 線性鏈表的圖示；(b) 線性鏈表的一般表示,.,在鏈表的實際應(yīng)用中，每個結(jié)點可以包含一個或若干個數(shù)據(jù)域或若干個指針域。多鏈結(jié)點的一般結(jié)構(gòu)如圖3-3(a)所示；圖3-3(b)所示為某工資管理程序中每個職工為一個結(jié)點的多數(shù)據(jù)項及鏈指針指向另一個職工結(jié)點的鏈地址項。,.,圖3-3 多鏈結(jié)點結(jié)構(gòu)多鏈結(jié)點的一般結(jié)構(gòu)；(b) 工資管理程序中每一結(jié)點的基本結(jié)構(gòu),.,從圖3-4中可以看出，鏈表中數(shù)據(jù)元素A、B、C、D的邏輯順序是依靠結(jié)點的鏈指針確定的。線性表的第一個元素A必定在存儲區(qū)域的第一個單元，而鏈表就不一定，其入口可根據(jù)實際需要而定，如圖3-4(b)中的鏈的入口Head為2008，最末一個結(jié)點2002的指針域為“”，表示鏈結(jié)束。,.,圖3-4 線性表和鏈表的存儲結(jié)構(gòu)(a) 線性表；(b) 單鏈表,.,在鏈表的實際應(yīng)用中，往往用數(shù)組的形式表示鏈表的存儲空間，圖3-5給出上例中5個數(shù)據(jù)元素的存儲和指針表示，該結(jié)構(gòu)可以在各種高級語言中實現(xiàn)。在圖3-5(a)中鏈的入口Head為6，DATA(6)表示6號結(jié)點的數(shù)據(jù)為A，LINK(6)為1，表示6號結(jié)點的后續(xù)結(jié)點為1，LINK(8)為0，表示該鏈結(jié)束。圖3-5(b)所示是以該數(shù)組的存儲方式為基礎(chǔ)畫出的鏈的一般表示，它更具有實用性和直觀性。對于涉及鏈結(jié)構(gòu)的程序設(shè)計，可根據(jù)要求畫出示意圖，這將有助于程序設(shè)計的實現(xiàn)。,.,圖3-5 用數(shù)組表示的鏈結(jié)構(gòu)(a) 數(shù)組表示的鏈表結(jié)構(gòu)；(b) 鏈的具體表示,.,3.2 單鏈表的基本操作,3.2.1 單鏈表的建立在用C語言編寫程序時，若線性鏈表中的結(jié)點有一個數(shù)據(jù)和一個鏈指針，且數(shù)據(jù)的類型為字符，則可以做以下類型說明：type def struct node char data； struct node * next； node；其中，next為指針變量；node為記錄。,.,若用函數(shù)建立有n個結(jié)點的鏈表，數(shù)據(jù)值在A(n)中，n1，那么，在鏈表的建立過程中，首先要把第一個結(jié)點作為鏈的入口，最末一個結(jié)點的指針設(shè)置結(jié)束標志。算法如下：struct node int data； struct node * next；GREATE(a,head)/* 建立一條有n個結(jié)點(n1)的鏈表，入口為head */p=malloc(size)；head=p；w=p；,.,/* 在系統(tǒng)空間中，取一個結(jié)點地址為p的空結(jié)點，并形成鏈的入口head */p-data=a1；for(i=2；inext= p； /* 前次結(jié)點與本次結(jié)點鏈接 */ p-data=ai； w= p； /* 逐個建立鏈中的結(jié)點 */ p-next=NULL； /* 建立鏈的結(jié)束標志 */,.,第二種建立鏈表的方法是用數(shù)組的形式，如圖3-6給出的數(shù)組的鏈表示意，其中鏈表入口為Head，AV是空間表的入口，鏈表有5個元素，順序表示為A、B、C、D、E。從圖中還可以看出，空間表還有4個可利用結(jié)點。圖3-7所示的是線性鏈表和空間表的邏輯狀態(tài)示意圖。圖3-7所示的是線性鏈表和空間表的邏輯狀態(tài)示意圖。,.,圖3-6 數(shù)組表示的鏈表,.,圖3-7 線性鏈表和空間表的邏輯狀態(tài),.,用數(shù)組形式建立鏈表時，只要按設(shè)計的數(shù)據(jù)域和指針域的數(shù)值，建立數(shù)組DATA(i)和LINK(i)，并建立鏈表和空間表的入口即可。建立鏈表的算法如下：GREATE(data , link , head , av)/* 以datan和linkn數(shù)組建立鏈表，鏈表入口為head，空間表入口是av */for(i=1；idatanext；if (i-data=key)&(i!=NULL) return(serach，true)；else return(search，false)；,.,例3.1 建立具有兩個結(jié)點的鏈表，使其第一個結(jié)點數(shù)據(jù)域的值大于第二個結(jié)點的值。設(shè)每個結(jié)點包含兩個域：DATA和NEXT，Head是入口。該算法首先從系統(tǒng)空間表中取一個結(jié)點x，并建立鏈表入口，把第一次讀入的數(shù)據(jù)存入該結(jié)點，然后再調(diào)用malloc(size)，取第二個結(jié)點，存入第二個數(shù)據(jù)，并比較兩個結(jié)點數(shù)據(jù)元素的值。若第二次讀入的數(shù)據(jù)值大于第一次讀入的數(shù)據(jù)值，則重新修正鏈表入口，同時第二個結(jié)點與第一個結(jié)點組成一條鏈，反之，第二個結(jié)點鏈接在第一個結(jié)點之后，最后建立鏈表的結(jié)束標志。實現(xiàn)算法如下：,.,GREATE2N(head)/* 建立具有2個結(jié)點的鏈表，head是鏈表入口 */x=malloc(size)；head=x； /* 建立鏈的入口 */scanf(%d，x-data=j；if(head-datax-data),., head-next=x； x-next=NULL；else x-next=head； head-next=NULL； head=x；,.,例3.2 設(shè)Head是鏈表入口，也即鏈的頭結(jié)點地址，請計算該鏈中結(jié)點的個數(shù)。在該算法設(shè)計中，可設(shè)置一計數(shù)器p，然后從鏈的入口即第一個結(jié)點的鏈指針讀出下一個結(jié)點，直至鏈結(jié)束。實現(xiàn)算法如下：COMPUTE(head，p)/* 計算以head為入口的鏈表中的結(jié)點個數(shù)，p是計數(shù)器 */ p=0；i=head； while(i!=NULL) p+； i=i-next；/* i是下一個結(jié)點的指針 */ printf(%dn，p)；,.,對上述算法略加改進就可以得到該鏈最末一個結(jié)點的存儲地址，方法是：在算法開頭和循環(huán)體內(nèi)各加一句保留前趨結(jié)點的語句w=i。其算法為：LG(head，w)/* head是鏈表入口，w存放鏈表最末一個結(jié)點地址 */ i=head；w=i；while(i!=NULL) w=i；i=i-next；printf(%LX n，w)；,.,在上述算法中若鏈為空，則w也為空。若Head為非空，則循環(huán)語句的判斷可改為while(i-nextNULL)算法中的w=i可以省略，i是最末結(jié)點的地址或指針，但不排除Head為空時該語句會出錯。,.,3.2.3 單鏈表元素插入操作在線性鏈表中插入一個結(jié)點是鏈表操作的基本運算之一，在應(yīng)用程序的設(shè)計中可根據(jù)實際操作的需要實施調(diào)用。設(shè)有一個數(shù)據(jù)序列a1，a2，ai，an，用線性鏈表的方式進行存儲，表頭入口為Head，要求在數(shù)據(jù)元素ai值的結(jié)點之前插入一個數(shù)據(jù)為x的元素。設(shè)存儲ai值的結(jié)點地址為p，由于鏈表結(jié)點的地址并非連續(xù)的，也就是說，結(jié)點p前趨結(jié)點地址并非為p?1，因此在p結(jié)點之前插入一個數(shù)值為x的結(jié)點必須已知p結(jié)點的前趨結(jié)點地址，設(shè)前趨結(jié)點的地址為q。,.,如圖3-9所示的是鏈表插入前、后的邏輯狀態(tài)。從圖3-9中可以看出，要插入一個結(jié)點，首先要從空間表中取一個空結(jié)點k，使得q結(jié)點的指針指向k，k結(jié)點的指針指向p，同時把數(shù)據(jù)x存入k，即q-next=k;k-next=p;,.,圖3-9 鏈表插入邏輯示意圖(a) 插入前；(b) 插入后,.,在鏈表的插入操作中，結(jié)點插入的位置可能有四種情況，下面分別加以介紹。設(shè)Head是鏈表入口或表頭，x是插入結(jié)點的存儲地址。(1) 原來鏈表為空表，即Head=NULL，則插入結(jié)點為表首結(jié)點，表示為Head=x；x-next=NULL；(2) 插入位置在表中第一個結(jié)點Head之前，則插入結(jié)點為新的表頭，表示為x-next=Head；Head=x；,.,(3) 插入位置在表的中間，為q結(jié)點之后，p結(jié)點之前，表示為q-next=x；x-next=p； (4) 插入位置在鏈尾，即新結(jié)點x作為原表尾結(jié)點p之后的新表尾，表示為x-next=p-next；p-next=x；或 p-next=x；x-next=NULL；,.,例3.3 設(shè)有一個鏈表，Head是鏈表入口，在結(jié)點p之后插入一個值為i的結(jié)點。實現(xiàn)算法如下：INS(head，p，i)x=malloc(size)；x-data=i；if(head=NULL) head=x；x-next=NULL;,.,else x-next= p-next；p-next=x；圖3-10給出了線性表插入算法的框圖。在插入算法框圖中可以看到在討論插入位置時的4種不同操作。,.,圖3-10 線性鏈表的插入算法框圖,.,以下給出插入算法。INSERTLINK(head，key，b)/* 在head為入口的鏈表中，在與key值相同結(jié)點之前插入數(shù)值b的結(jié)點 */ x=malloc(size)；x-data=b;if(head=NULL) head=x；x-next=NULL；/* 鏈空，插入結(jié)點為表頭 */else if(head-data=key) x-next=head；head=x；,.,/* 插入位置在第一個結(jié)點之前，插入結(jié)點為新的表頭 */else i=head； while(i-data!=key)&( i-next!=NULL) w=i； i= i-next； if(i-data=key) w-next=x；x-next=i； ,.,else /* 插入位置在表的中間 */ i-next=x；x-next=NULL； /* 插入位置在表末，新結(jié)點作為新的表尾 */ 該算法在循環(huán)查詢中設(shè)置變量w的目的是一旦訪問到i-data=key的存儲結(jié)點i的前趨結(jié)點地址后，就能實現(xiàn)在w和i之間的插入。,.,為了便于用C語言編寫程序，我們給出了如下用C程序編制的線性表的插入程序，其中鏈表中結(jié)點的數(shù)據(jù)值為整數(shù)。struct node int data； struct node * next；INSERTLINK(struct node * head，int key，int b)/* 在head為入口的鏈表中，在與key值相同結(jié)點之前插入數(shù)值b的結(jié)點 */,., struct node * w，* i，* x； x=(struct node * ) malloc (sizeof (struct node)； x-data=b； if (head= =NULL) head=x；x-next=NULL；/* 鏈空，插入結(jié)點為表頭 */ else if(head-data= =key) x-next=head；head=x；,.,/* 插入位置在第一個結(jié)點之前，插入結(jié)點為新的表頭 */ else i=head； while(i-data!=key)&(i-next!=NULL) w=i； i=i-next； if(i-data= =key) w-next=x； x-next=i； /* 插入結(jié)點在鏈中間 */,.,else i-next=x； x-next=NULL； /* 插入結(jié)點在鏈尾 */ ,.,現(xiàn)把改進后的插入算法描述如下：INSERTLINK(head，key，b) x=malloc(size)；x-data=b；if(head= =NULL) head=x；x-next= NULL；else i=head；w=i；while(i!= NULL) &(i-data!=key),., w=i； i= i-next；/* 循環(huán)查找插入結(jié)點的位置 */if(i= =w) x-next=head；head=x；/* 插入位置在第一個結(jié)點之前，插入結(jié)點為新的表頭 */else w-next=x；x-next=i；/* 插入位置在表中間和表尾 */,.,3.2.4 單鏈表元素刪除操作如果要在鏈表中刪除數(shù)據(jù)域中給定值為x的結(jié)點，但表中無此結(jié)點，則會給出“此刪除無法進行”的信息，否則，把被刪除的結(jié)點送還空間表，以備再次使用。圖3-11給出了鏈表刪除操作的邏輯狀態(tài)。,.,圖3-11 鏈表刪除的邏輯示意圖(a) 刪除前；(b) 刪除后,.,從圖3-11中可以看出，要刪除某一個結(jié)點，必須知道被刪除結(jié)點的前趨結(jié)點。設(shè)被刪除結(jié)點的地址為s，s的前趨結(jié)點為q，s的后繼結(jié)點為p，則被刪除的基本操作步驟為q-next=p；或q-next=s-next；同時為了充分利用被刪除結(jié)點的空間，除了函數(shù)回收外，用戶設(shè)計的空間表的回收方式如圖3-12所示。,.,圖3-12 空間表的回收,.,從圖3-12中可以看出，被刪除空間的回收均在表頭實現(xiàn)，即回收的結(jié)點都將成為新的入口，其回收算法如下：Free(x)/* 把地址為x的結(jié)點送入口為av的空間表 */ x-next=av； av=x；,.,刪除操作和插入操作相同，即在鏈表中搜索到被刪除的結(jié)點，修改相應(yīng)的指針，同時把被刪除的結(jié)點通過調(diào)用free(x)，將該結(jié)點的空間送空間表。根據(jù)被刪除結(jié)點在鏈表中的位置，刪除操作有如下四種情況：(1) 鏈表中只有一個結(jié)點，該結(jié)點就是被刪除的結(jié)點，其操作為Head=NULL；或 Head=Head-next；(2) 被刪除的結(jié)點是鏈中第一個結(jié)點，其操作為Head=Head-next；,.,(3) 被刪除的結(jié)點在鏈的中間，其中刪除結(jié)點的地址為p，前趨結(jié)點的地址為q，其操作為q-next=p-next；(4) 被刪除的結(jié)點在鏈尾，其中刪除結(jié)點的地址為p，前趨結(jié)點的地址為q，其操作為q-next=NULL；或 q-next=p-next；圖3-13給出了線性表刪除算法的框圖。,.,圖3-13 線性鏈表刪除算法框圖,.,以下給出刪除的算法。DELETE(head，key)/* 在head為入口的鏈表中刪除值為key的結(jié)點 */ i=head；w=i；/* 設(shè)置前趨結(jié)點的地址 */while(i!=NULL)&(i-data!=key) w=i； i= i-next；/* 查找刪除結(jié)點的位置 */,.,if(i=NULL) printf(無此結(jié)點)；return；else if(head= =i)head=i-next；/* 刪除頭結(jié)點 */ else w-next=i-next；/* 刪除鏈中間和鏈尾結(jié)點 */ free(i)；,.,3.3 單鏈表應(yīng)用舉例,在鏈表結(jié)構(gòu)中結(jié)點地址在內(nèi)存中是不連續(xù)的，也就是說，鏈表中結(jié)點的數(shù)據(jù)在內(nèi)存中不必連續(xù)存放，而可以通過結(jié)點的指針進行靈活操作。鏈表的這個特點在實際使用中得到了廣泛的應(yīng)用。多項式相加的算術(shù)運算，已成為鏈表結(jié)構(gòu)應(yīng)用的一個典型例子。設(shè)多項式為P(x)=anxn+an-1xn-1+a1x+a0其中ai是非零項的xi的系數(shù)，i=0, 1, 2, , n。,.,當用鏈表來表示多項式時，其每一個非零項用一個結(jié)點表示，每個結(jié)點定義三個域，即系數(shù)域(coef)、指數(shù)域(exp)和指針域(next)。每個結(jié)點的形式如圖3-14所示，其中i表示該結(jié)點的地址。,.,圖3-14 多項式鏈表的結(jié)點結(jié)構(gòu),.,當用鏈表來表示多項式時，其每一個非零項用一個結(jié)點表示，每個結(jié)點定義三個域，即系數(shù)域(coef)、指數(shù)域(exp)和指針域(next)。每個結(jié)點的形式如圖3-14所示，其中i表示該結(jié)點的地址。例如，多項式A(x)=3x14+2x8-1，B(x)=8x14-3x10+10x6的鏈表表示形式如圖3-15所示。其中以AH為入口的鏈表表示A(x)多項式，以BH為入口的鏈表表示B(x)多項式。,.,圖3-15 多項式的鏈表表示,.,(1) Pa和Pb所指向的結(jié)點指數(shù)相等，即Pa-exp=Pb-exp，則兩相的系數(shù)相加。相加后系數(shù)不等于零，則在CH表中建立新項，鏈接在CH的鏈尾，同時修改Pa和Pb，使其指向AH和BH鏈的下一個結(jié)點。(2) 若Pa-expPb-exp，則復(fù)抄AH表中Pa所指向的結(jié)點到CH表中，同時修改Pa使其指向AH表中的下一個結(jié)點；反之，則復(fù)抄Pb所指向的結(jié)點到CH表中，同時修改Pb使其指向BH表中的下一個結(jié)點。 (3) 當AH或BH表中的結(jié)點比較完畢后，則將未搜索、比較完的另一個鏈表復(fù)抄到CH表中。圖3-16所示的是多項式A(x)和B(x)相加后生成CH表的操作過程。,.,圖3-16 多項式相加過程,.,在CH鏈表中建立一個新項的子程序ATTACH的算法如下：struct node int exp，coef；struct noed * next； ；ATTACH(struct node * d，int c，int e) struct node * p； p=malloc(size)； p-coef=c； p-exp=e； d-next=p；/* 新結(jié)點p與ch鏈中的尾結(jié)點鏈接 */ d=p；/* d成為ch鏈的新尾結(jié)點 */,.,兩多項式相加的算法PLOYADD如下：PLOYADD(struct node * ch，struct node * ah，struct node * bh) int x； struct node * pa，* pb，* pc； pa=ah； pb=bh； /* pa和pb分別指向ah鏈和bh鏈的第一個結(jié)點 */ ch=malloc(size)； pc=ch；,.,/* 產(chǎn)生一個ch鏈中無值的空結(jié)點，程序運行后將撤銷 */ while (pa!=NULL & pb!=NULL)if(pa-exp= =pb-exp) x= pa-coef+pb-coef； if(x!=0) ATTACH(pc，x，pa-exp)； pa=pa-next；/* ah取下一個結(jié)點 */ pb=pb-next；/* bh取下一個結(jié)點 */ ,.,else if(pa-exppb-exp) ATTACH(pc，pa-coef，pa-exp)； pa=pa-next； while(pa!=NULL) ATTACH(pc，pa-coef，pa-exp)；pa=pa-next； ,.,while(pb!=NULL) ATTACH(pc，pb-coef，pb-exp)； pb=pb-next；pc-next=NULL；/* ch鏈的尾結(jié)點值結(jié)束標志 */pc=ch；ch=ch-next；/* 撤銷ch鏈的空的頭結(jié)點 */free(pc)；/* pc結(jié)點送還空區(qū)鏈表 */,.,3.4 循環(huán)鏈表,圖3-17所示是循環(huán)鏈表的結(jié)構(gòu)示意圖。,.,圖3-17 循環(huán)鏈表的結(jié)構(gòu),.,圖3-18所示就是回收的操作過程。,圖3-18 循環(huán)鏈表的回收,.,以下給出回收循環(huán)鏈表的算法：CREASE(head，av)/* 把循環(huán)鏈表整個送到空區(qū)鏈表，head是環(huán)鏈表入口，av是空區(qū)鏈表入口 */ if(head!=NULL) i=head-next； head-next=av； av=i；,.,通過查詢，確定關(guān)鍵字值KEY不在鏈中，該結(jié)點插入的位置和插入的操作有如下幾種情況：(1) 若表空(Head=NULL)，則插入結(jié)點后是只有一個結(jié)點的環(huán)鏈表。(2) 若表非空，則分為三種情況： 插入的位置是在第一個結(jié)點，即原表的第一個結(jié)點成為結(jié)點插入后新表的第二個結(jié)點，同時為了保持循環(huán)鏈表的結(jié)構(gòu)特征，在形成新的入口后，鏈表中最末一個結(jié)點的鏈指針應(yīng)修正指向新的入口結(jié)點。,., 插入的位置是在最末一個結(jié)點之后，那么，最末一個結(jié)點的指針指向插入的結(jié)點，插入結(jié)點的指針仍指向首結(jié)點。 插入的位置是在鏈的中間，那么可通過插入位置的前趨結(jié)點的指針，完成新結(jié)點的插入。圖3-19所示為四種插入操作的示意圖。,.,圖3-19 循環(huán)有序鏈表的插入操作示意圖,.,圖3-20給出了循環(huán)鏈表刪除關(guān)鍵字值為KEY的結(jié)點的算法框圖。,.,圖3-20 循環(huán)鏈表刪除算法框圖,.,必須注意，在循環(huán)鏈表中，要充分考慮到可能出現(xiàn)被刪除結(jié)點位置不同的各個邊界條件。若被刪除結(jié)點在鏈首，則必須修改入口Head，而且還要考慮到鏈表中最末一個記錄的指針要指向結(jié)點刪除后的新入口，該情況的操作示意圖如圖3-21所示；特殊情況下，被刪除結(jié)點是第一個且僅只有這一個結(jié)點，那么循環(huán)鏈表入口因設(shè)置為空，Head=NULL；其他情況與單鏈表的刪除結(jié)點的算法相似。,.,圖3-21 循環(huán)鏈表刪除首結(jié)點(a) 刪除結(jié)點之前；(b) 刪除結(jié)點之后,.,3.5 雙向鏈表,圖3-22給出了雙向鏈表的結(jié)點示意圖。,圖3-22 雙向鏈表的結(jié)點結(jié)構(gòu),.,圖3-23 雙向鏈表的結(jié)構(gòu),.,雙向鏈表的結(jié)構(gòu)有以下特點：(1) 若Head為空(NULL)，則雙向鏈表為空。(2) 在雙向鏈表中，若結(jié)點i有i-Lnext=NULL則該結(jié)點是鏈的第一個結(jié)點；若結(jié)點i有i-Lnext=i-Rnext=NULL 則該結(jié)點i是鏈的第一個結(jié)點且該鏈僅有這個結(jié)點i。(3) 在雙鏈表中，若結(jié)點i有i-Rnext=NULL則該結(jié)點是鏈的最末一個結(jié)點。,.,(4) 在雙向鏈表中，若結(jié)點i是表中任意結(jié)點的地址，則該結(jié)點的前趨結(jié)點是iLnext，后繼結(jié)點的地址是iRnext，對結(jié)點i也可以表示為i= i-Rnext-Lnext= i-Lnext-Rnext這個表達式非常直觀地反映了雙向鏈表結(jié)構(gòu)的本質(zhì)特點，即無論是沿著表向前，還是向后都同樣方便。此外，雙向鏈表也可以構(gòu)成帶頭結(jié)點的循環(huán)雙向鏈表，往往稱作循環(huán)雙重鏈表。當一個循環(huán)雙重鏈表為空時，也總有一個空單元。對于雙向鏈表和循環(huán)雙重鏈表，僅作一般介紹。圖3-24給出了循環(huán)雙重鏈表的結(jié)構(gòu)示意圖。,.,圖3-24 循環(huán)雙重鏈表(a) 循環(huán)雙重鏈表的空表；(b) 循環(huán)雙重鏈表,.,3.6 各種鏈式存儲結(jié)構(gòu)的比較,鏈表在線性結(jié)構(gòu)中對于數(shù)據(jù)元素的存儲方式是一種比較靈活的結(jié)構(gòu)，鏈表中數(shù)據(jù)元素的邏輯順序在存儲空間中是通過指針鏈接的，鏈表中的數(shù)據(jù)元素可以存放在任意存儲單元中，不必為其分配一片連續(xù)的存儲空間。鏈表可以是空鏈，也可以由一個或多個結(jié)點組成。每個鏈表均有一個入口的頭結(jié)點，該結(jié)點僅指出鏈中的一個結(jié)點的地址或指針。每條鏈也有一個結(jié)束標志，單鏈表中最末一個結(jié)點的鏈指針為“”或“NULL”，循環(huán)鏈表中最末一個結(jié)點的鏈指針指向頭結(jié)點的地址或指針。,.,單鏈表和循環(huán)單鏈表均只有一個鏈指針next，指向后繼結(jié)點，而雙向鏈表有兩個指針，即向前指針Lnext和向后指針Rnext。單鏈表結(jié)構(gòu)的查詢只能從鏈表入口開始，按結(jié)點的鏈指針逐個查詢，直至結(jié)束；循環(huán)單鏈表可以從任意一個結(jié)點入口，按結(jié)點的指針循環(huán)查遍全表；雙向鏈表按其結(jié)構(gòu)特征可以同時向前和向后進行查詢而搜索全表。從存儲空間的占有量分析，單鏈表和循環(huán)單鏈表所需的存儲空間是相同的，而雙鏈表由于增加了一個向前指針Lnext，因此大約需要增加一倍的指針存儲空間。,.,3.7 順序表與鏈表的結(jié)構(gòu)和應(yīng)用比較,順序表是線性存儲結(jié)構(gòu)中的順序存儲，即順序表中所有元素的類型相同，每個元素在存儲介質(zhì)中占用的空間大小相同；在順序表中數(shù)據(jù)元素邏輯順序是相鄰的，而該元素在存儲空間中物理地址也是順序連續(xù)的。鏈表中存儲數(shù)據(jù)元素結(jié)點的邏輯順序是通過指針鏈接的，鏈表的數(shù)據(jù)元素可以存放在任意存儲單元，無需分配連續(xù)存儲空間，極大地提高了存儲空間的利用率。,.,3.8 鏈表應(yīng)用舉例,設(shè)飛機有120個座位，則可設(shè)計一個有121個結(jié)點的雙鏈表。變量說明：D(i)：結(jié)點關(guān)鍵字，用以存放乘客姓名；Lnext(i)：結(jié)點的左指針；Rnext(i)：結(jié)點的右指針；X：訂票的乘客姓名；Y：退票的乘客姓名；F1：乘客表的首指針；F2：空座位表的首指針；,.,Q：結(jié)點的地址；N：分支變量；N=0：結(jié)束；N=1：訂票；N=2：退票；N=3：輸出乘客表。 設(shè)表頭的數(shù)據(jù)域中存放的航次及日期格式為：A300B/2004.2.10。表3-1所示是僅有表頭的空乘客表。,.,表3-1 空乘客表,.,表3-2所示是依次有9名乘客已訂票的乘客表，表中的姓名以英文字母順序排列，以循環(huán)雙重鏈表實現(xiàn)。,.,表3-2 9名乘客的乘客表,.,表3-3所示是在建立了表3-2所示的雙鏈表后，若又有乘客DING前來退票，此時的乘客表和空座位表的情況。從表3-3中可以看出，當每次退票后，空座位表的首指針指向已退票的座位號，以便該座位在下次訂票時為可用。,.,表3-3 退票后的乘客表,.,若此時又有乘客LIU前來訂票，則結(jié)點的存儲情況如表3-4所示。,.,表3-4 再次訂票的乘客表,.,根據(jù)以上的訂票和退票的操作規(guī)則，算法在開始時建立一表頭和有121個存儲單元的可利用的空座位表，然后根據(jù)分支的選擇，完成訂票、退票和輸出乘客表。圖3-25是算法對應(yīng)的框圖。,.,圖3-25 自動訂票系統(tǒng)框圖,.,根據(jù)算法的框圖，以下給出自動訂票系統(tǒng)的算法：SAP(x, y )/* 在f1為乘客鏈表入口，f2為空座位表入口的循環(huán)鏈表中x是訂票者姓名，y是退票者的姓名*/ strcpy(d1，A300B/2004.2.10) lnext1=rnext1=1； /* 建立乘客循環(huán)鏈表的表頭 */ for (i=2；i=120；i+) rnexti= i +1； rnext121=0；,.,f1=1；f2=2；/* 建立空座位表鏈和入口 */do scanf(%d,&n)； switch(n) case 1：gets(x)；t=rnextf1；while (t!=1),.,if ( strcmp(dt，x)0) t=rnextt； elset=1；/* 查詢訂票乘客是否定過票及在乘客表中的位置 */if ( strcmp(dt，x)= =0)printf (已訂過票)；else if(f2= =0) printf (已滿座)； else q=f2；,.,f2=rnextq； dq=x； rnextq=t； lnextq=lnextt； rnextlnextt=q； lnextt=q；printf (已訂好票)；/* 訂票結(jié)點插入乘客鏈表，修正空座位表入口 */,.,break；case2： gets(y)；q=rnextf1；while ( q!=1)if (strcmp(dq，y)0) q=rnextq；else q=1；,.,/* 查詢退票乘客是否訂過票及在乘客表中的位置 */ if ( strcmp (dt，y)!=0) printf (沒訂過票)； else rnext=lnextq=rnextq； lnext=rnextq=lnextq； rnexta=f2；