概論線性表和數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)第1章 數(shù)據(jù)結(jié)構(gòu)概論 本章主要介紹以下內(nèi)容 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念 算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)1.1 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)： l 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 2 對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。 應(yīng)用舉例1學(xué)籍檔案管理 假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表1-1所示的學(xué)生信息。表1-1 特點(diǎn)： l 每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格； 2 表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說(shuō)的線性結(jié)構(gòu)； 3 對(duì)它的操作通常是插入某個(gè)學(xué)生的信

2、息，刪除某個(gè)學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。 應(yīng)用舉例2輸出n個(gè)對(duì)象的全排列 輸出n個(gè)對(duì)象的全排列可以使用下圖1-1所示的形式描述。圖 1-1 3個(gè)對(duì)象的全排列過(guò)程特點(diǎn)： l在求解過(guò)程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說(shuō)的樹形結(jié)構(gòu)； l對(duì)它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。應(yīng)用舉例3制定教學(xué)計(jì)劃 在制定教學(xué)計(jì)劃時(shí)，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開設(shè)情況如下表1-2所示：表1-2課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6

3、c7c8圖 1-2 計(jì)算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系 特點(diǎn) l課程之間的先后關(guān)系用圖結(jié)構(gòu)描述； 2通過(guò)實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。 結(jié)論 計(jì)算機(jī)的操作對(duì)象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理，我們將此稱為非數(shù)值性處理。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對(duì)象的特點(diǎn)，在計(jì)算機(jī)中的表示方式以及各個(gè)操作的具體實(shí)現(xiàn)手段。這些就是數(shù)據(jù)結(jié)構(gòu)這門課程研究的主要內(nèi)容。1.2 基本概念和術(shù)語(yǔ)數(shù)據(jù) 是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中其含義是指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)集合。數(shù)據(jù)元素 是

4、數(shù)據(jù)集合中的一個(gè)實(shí)體，是計(jì)算機(jī)程序中加工處理的基本單位。 數(shù)據(jù)元素按其組成可分為簡(jiǎn)單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。簡(jiǎn)單型數(shù)據(jù)元素由一個(gè)數(shù)據(jù)項(xiàng)組成，所謂數(shù)據(jù)項(xiàng)就是數(shù)據(jù)中不可再分割的最小單位；復(fù)雜型數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念的多方面信息。 數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單地說(shuō)，就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中所說(shuō)的“關(guān)系”實(shí)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)） 是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的具體實(shí)現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(nèi)容

5、，還要表示清楚數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。常見的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)：特點(diǎn)是借助于數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)； 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：特點(diǎn)是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。1.3 算法 1.3.1 算法的概念 算法是解決某個(gè)特定問(wèn)題的一種方法或一個(gè)過(guò)程。 計(jì)算機(jī)對(duì)數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。設(shè)計(jì)算法的基本過(guò)程 l通過(guò)對(duì)問(wèn)題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型； 2確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法； 3選用某種語(yǔ)言將

6、算法轉(zhuǎn)換成程序； 4調(diào)試并運(yùn)行這些程序。算法應(yīng)該具有下列五個(gè)特性（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過(guò)已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說(shuō)的輸出是指與輸入有某種特定關(guān)系的量。舉例問(wèn)題：按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容。算法： （1）輸入x，y，z三個(gè)數(shù)值； （2）從三個(gè)數(shù)值中挑選出最小者并換到x中； （3）從y，z中挑選出較小者并換到y(tǒng)中； （4）輸出排序后的結(jié)果

7、。 1.3.2 算法的描述 選擇算法描述語(yǔ)言的準(zhǔn)則（1）該語(yǔ)言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能；（2）該語(yǔ)言應(yīng)該盡可能地簡(jiǎn)捷，以便于掌握、理解；（3）使用該語(yǔ)言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計(jì)語(yǔ)言。 “類C”描述語(yǔ)言是通過(guò)對(duì)C語(yǔ)言進(jìn)行精心篩選保留的一個(gè)核心子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語(yǔ)言的描述功能。 1. 預(yù)定義常量及類型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 數(shù)據(jù)元素被約定為dateType 類型，用戶需要根據(jù)具體情況，自行

8、定義該數(shù)據(jù)類型。2. 算法描述為以下的函數(shù)形式： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 語(yǔ)句序列； 為了簡(jiǎn)化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說(shuō)明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說(shuō)明，必要時(shí)給出相應(yīng)的注釋即可。另外，在書寫算法時(shí)，應(yīng)該養(yǎng)成對(duì)重點(diǎn)語(yǔ)句段落添加注解的良好習(xí)慣。3. 在算法描述中可以使用的賦值語(yǔ)句形式有： 簡(jiǎn)單賦值 變量名 = 表達(dá)式； 串聯(lián)賦值 變量名1 = 變量名2 = . = 變量名n = 表達(dá)式； 成組賦值 （變量名1，.，變量名n）=（表達(dá)式1，.，表達(dá)式n）； 結(jié)構(gòu)賦值 結(jié)構(gòu)名1 = 結(jié)構(gòu)名2； 結(jié)構(gòu)名 =（值1，值2，.，值n）；

9、條件賦值 變量名 = 條件表達(dá)式 ? 表達(dá)式1：表達(dá)式2； 交換賦值 變量名1 變量名2；4. 在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有：條件語(yǔ)句1 if （表達(dá)式） 語(yǔ)句；條件語(yǔ)句2 if （表達(dá)式） 語(yǔ)句； else 語(yǔ)句；開關(guān)語(yǔ)句1 switch （表達(dá)式） case 值1：語(yǔ)句序列1；break； case 值2：語(yǔ)句序列2；break； . case 值n：語(yǔ)句序列n；break； default：語(yǔ)句序列n+1； 開關(guān)語(yǔ)句2 switch case 條件1：語(yǔ)句序列1；break； case 條件2：語(yǔ)句序列2；break； . case 條件n：語(yǔ)句序列n；break； defa

10、ult：語(yǔ)句序列n+1； 5. 在算法描述中可以使用的循環(huán)結(jié)構(gòu)語(yǔ)句形式有： for循環(huán)語(yǔ)句 for （表達(dá)式1；循環(huán)條件表達(dá)式； 表達(dá)式2） 語(yǔ)句； while循環(huán)語(yǔ)句 while （循環(huán)條件表達(dá)式） 語(yǔ)句； do-while循環(huán)語(yǔ)句 do 語(yǔ)句序列； while （循環(huán)條件表達(dá)式）；6. 在描述算法中可以使用的結(jié)束語(yǔ)句形式有： 函數(shù)結(jié)束語(yǔ)句 return 表達(dá)式； return; case或循環(huán)結(jié)束語(yǔ)句 break; 異常結(jié)束語(yǔ)句 exit（異常代碼）； 7. 在算法描述中可以使用的輸入輸出語(yǔ)句形式有： 輸入語(yǔ)句 scanf( 格式串，變量名1，.，變量名n)； 輸出語(yǔ)句 printf( 格

11、式串，表達(dá)式1，.，表達(dá)式n); /方括號(hào)（ ）中的內(nèi)容是可以省略的部分。8. 在算法描述中使用的注釋格式為： 單行注釋 /文字序列9. 在算法描述中可以使用的擴(kuò)展函數(shù)有： 求最大值 max（表達(dá)式1，.，表達(dá)式n）；這個(gè)函數(shù)返回參數(shù)表中n個(gè)表達(dá)式計(jì)算結(jié)果中的最大值。 求最小值 min（表達(dá)式1，.，表達(dá)式n）；這個(gè)函數(shù)返回參數(shù)表中n個(gè)表達(dá)式計(jì)算結(jié)果中的最小值?！舅惴?-1】用類C描述將三個(gè)數(shù)值排序的算法。 viod Three_Sort( int *x,int *y,int *z)/將x,y,z三個(gè)指針?biāo)甘镜膬?nèi)容按從小到大的順序重新排列 /挑選出最小的數(shù)值并換到 x指針?biāo)傅拇鎯?chǔ)單元中 i

12、f (*y*x&*y*z) *x*y; else if (*z*x&*z*y) *x*z; /在y和z所指示的存儲(chǔ)單元中挑選出較小者換到y(tǒng)中 if(*zlength=-1； /將當(dāng)前線性表長(zhǎng)度置0 return L； 2. 銷毀線性表Lvoid Destroy_List(SQ_LIST *L) if (L) free(L); /釋放線性表占據(jù)的所有存儲(chǔ)空間3. 清空線性表Lvoid Clear_List(SQ_LIST *L) L-length=-1; /將線性表的長(zhǎng)度置為04. 求線性表L的長(zhǎng)度int Length_List(SQ_LIST L) return (L.length+1); 5

13、. 判斷線性表L是否為空int IsEmpty(SQ_LIST L) if (L.length= =-1) return TRUE; else return FALSE;6. 獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容int Get _List(SQ_LIST L,int i,dataType *e) if (iL .length+1) return ERROR; /判斷i值是否合理，若不合理，返回ERROR *e=L .datai-1; /數(shù)組中第i-1的單元存儲(chǔ)著線性表中第i個(gè)數(shù)據(jù)元素的內(nèi)容 return OK;7. 在線性表L中檢索值為e的數(shù)據(jù)元素int Locate _List(SQ_LIST

14、 *L,dataType e) for (i=0;ilength;i+) if (L-datai= =e) return i+1; return 0;8. 在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int Insert_List (SQ_LIST *L,int i, dataType e) if (L-length=LIST_MAX_LENGTH-1) return ERROR; /檢查是否有剩余空間 if (iL-length+2) return ERROR; /檢查i值是否合理 for (j=L-length;j=i-1; j- -) /將線性表第i個(gè)元素之后的所有元素向后移動(dòng) L-d

15、ataj+1=L-dataj; L-datai-1=e; /將新元素的內(nèi)容放入線性表的第i個(gè)位置 L-length+; return OK;9. 將線性表L中第i個(gè)數(shù)據(jù)元素刪除int Delete_List (SQ_LIST *L,int i,dataType *e) if (IsEmpty(*L) return ERROR; /檢測(cè)線性表是否為空 if (iL-length+1) return ERROR; /檢查i值是否合理 *e=L-datai-1; /將欲刪除的數(shù)據(jù)元素內(nèi)容保留在e所指示的存儲(chǔ)單元中 for (j=i;jlength;j+) /將線性表第i+1個(gè)元素之后的所有元素向前移

16、動(dòng) L-dataj-1=L-dataj; L-length- -; return OK; 插入算法的分析 假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： 刪除算法的分析 在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： 分析結(jié)論 順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮。2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)： 它是一種簡(jiǎn)單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次

17、存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。 暴露的問(wèn)題： l 在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)； 2 對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用； 3 線性表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元（可以連續(xù)，也可以不連續(xù)）存儲(chǔ)線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲(chǔ)位置的信息。假設(shè)有一個(gè)線性表（a,b,c,d），可用下圖2-2所示的形式存儲(chǔ)：

18、圖2-2 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖 術(shù)語(yǔ)： 表示每個(gè)數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點(diǎn)；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）； 表示直接后繼元素存儲(chǔ)地址的部分被稱為指針或指針域（next）。 單鏈表簡(jiǎn)化的圖2-3描述形式headd cba圖 2-3 單鏈表結(jié)構(gòu)示意圖 其中，head是頭指針，它指向單鏈表中的第一個(gè)結(jié)點(diǎn)，這是單鏈表操作的入口點(diǎn)。由于最后一個(gè)結(jié)點(diǎn)沒(méi)有直接后繼結(jié)點(diǎn)，所以，它的指針域放入一個(gè)特殊的值NULL。NULL值在圖示中常用（ ）符號(hào)表示。 帶頭結(jié)點(diǎn)的單鏈表： 為了簡(jiǎn)化對(duì)鏈表的操作，人們經(jīng)常在鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱為頭結(jié)點(diǎn)。這樣可以免去對(duì)鏈表第

19、一個(gè)結(jié)點(diǎn)的特殊處理。如下圖2-4所示：d headcba圖 2-4 帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)示意圖鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)（1）線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致；（2）在對(duì)線性表操作時(shí)，只能通過(guò)頭指針進(jìn)入鏈表，并通過(guò)每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會(huì)造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等。在C語(yǔ)言中，實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義 typedef struct node /結(jié)點(diǎn)類型及表頭類型 datatype data; struct node *next; LNODE,* LINK_LIST;2.3.2 典型操作的算法實(shí)現(xiàn)1初始化鏈表L(在單鏈表的

20、頭部插入結(jié)點(diǎn))LINK_LIST Init_List1() LINK_LIST L=NULL； LNODE *s; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeof(LNODE); s-data=x; s-next=L; L=s; scanf(“%d”,&x); return L ; 2 初始化鏈表L(在單鏈表的尾部插入結(jié)點(diǎn))LINK_LIST Init_List2() LINK_LIST L=NULL； LNODE *s，*R=NULL; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeo

21、f(LNODE)； s-data=x； if (L= =NULL) L=s； else R-next=s； R=s； scanf(“%d”,&x)； if (R!=NULL) R-next=NULL； return L ; 2. 清空鏈表L void Destory_List(LINK_LIST L) LNODE *p; while (L-next) /依次刪除鏈表中的所有結(jié)點(diǎn) p=L-next; L-next=p-next; free(p); 3. 求鏈表L的長(zhǎng)度int Length_List (LINK_LIST L) LNODE *p； int len； for(p=L, len=0；p

22、-next!=NULL；len+,p=p-next); return(len)；4. 判鏈表L空否 int IsEmpty(LINK_LIST L) if (L-next=NULL) return TRUE; else return FALSE; 5. 在鏈表L中查找到第i個(gè)元素，并把元素內(nèi)容放到元素e中LNODE *Get_List(LINK_LIST L,int i, dataType *e) LNODE *p=L; int j; /檢測(cè)i值的合理性 if (iLength_List(L) return NULL; for (j=0;jnext,j+); *e=p-data; /將第i個(gè)結(jié)

23、點(diǎn)的內(nèi)容賦給e return p; /返回指針p6. 在鏈表L中檢索值為e的數(shù)據(jù)元素LNODE *LocateELem(LINK_LIST L,dataType e) LNODE *p; for (p=L-next;p!=NULL&p-data!=e;p=p-next); /尋找滿足條件的結(jié)點(diǎn) return(p);7. 返回鏈表L中結(jié)點(diǎn)e的直接前驅(qū)結(jié)點(diǎn)LNODE *PriorElem(LINK_LIST L,LNODE* e) LNODE *p; if (L-next-data=e) return NULL; /檢測(cè)第一個(gè)結(jié)點(diǎn) for (p=L-next;p-next!=NULL & p-ne

24、xt-data!=e;p=p-next); if (p-next-data=e) return p; else return NULL; 8. 返回鏈表L中結(jié)點(diǎn)e的直接后繼結(jié)點(diǎn)LNODE *NextElem(LINK_LIST L,LNODE *e) LNODE *p; for(p=L-next;p&p!=e;p=p-next); if (p) p=p-next; return p;9. 在鏈表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int Insert_List (LINK_LIST L,int i,dataType e) LNODE *p,*s; p=Get_List(L,i-1); if(

25、p= =NULL) printf(“參數(shù)錯(cuò)誤！”);return 0; else s=malloc(sizeof(LNODE); if (s=NULL) return ERROR; s-data=e; s-next=p-next; p-next=s; return OK;10. 將鏈表L中第i個(gè)數(shù)據(jù)元素刪除，并將其內(nèi)容保存在e中int Delete_List (LINK_LIST L,int i,dataType *e) LNODE *p，*s; p=Get_List(L,i-1); if(p= =NULL) printf(“第i-1個(gè)結(jié)點(diǎn)不存在！”);return -1; else if(p

26、-next= =NULL) printf(“第i個(gè)結(jié)點(diǎn)不存在！”);return 0; else s=p-next; /用s指向?qū)⒁獎(jiǎng)h除的結(jié)點(diǎn) *e=s-data; p-next=s-next; /刪除s指針?biāo)赶虻慕Y(jié)點(diǎn) free(s); return OK; 2.3.3 循環(huán)鏈表 若將鏈表中最后一個(gè)結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn) 實(shí)現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結(jié)束的條件有所不同。下面我們就列舉兩個(gè)循環(huán)鏈表操作的算法示例。head 圖2-7 帶頭結(jié)點(diǎn)的循環(huán)鏈表示意圖1. 初始化鏈表CLLINK_LIST InitList() LINK_LIST

27、CL; LNODE *s，*R=NULL; CL=(LNODE *)malloc(sizeof(LNODE)； CL-next=CL； int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)； s-data=x； if (CL-next= =CL) s-next=CL;CL-next=s； else s-next=CL;R-next=s； R=s； scanf(“%d”,&x)； return CL ; 2. 在循環(huán)鏈表CL中檢索值為e的數(shù)據(jù)元素LNODE *Locatedata(LINK_LIST CL,data

28、Type e) LNODE *p; for (p=CL-next;(p!=CL)&(p-data!=e);p=p-next); if (p!=CL) return p; else return NULL ; 2.3.4 雙向循環(huán)鏈表 在循環(huán)鏈表中，訪問(wèn)結(jié)點(diǎn)的特點(diǎn)：訪問(wèn)后繼結(jié)點(diǎn)，只需要向后走一步，而訪問(wèn)前驅(qū)結(jié)點(diǎn)，就需要轉(zhuǎn)一圈。 結(jié)論：循環(huán)鏈表并不適用于經(jīng)常訪問(wèn)前驅(qū)結(jié)點(diǎn)的情況。 解決方法：在需要頻繁地同時(shí)訪問(wèn)前驅(qū)和后繼結(jié)點(diǎn)的時(shí)候，使用雙向鏈表。所謂雙向鏈表。 雙向鏈表就是每個(gè)結(jié)點(diǎn)有兩個(gè)指針域。一個(gè)指向后繼結(jié)點(diǎn)，另一個(gè)指向前驅(qū)結(jié)點(diǎn)。圖 2-8headprioritemnext(a)(b)用C語(yǔ)言實(shí)現(xiàn)

29、雙向循環(huán)鏈表的類型定義typedef strcut du_node /雙向鏈表的結(jié)點(diǎn)類型 dataType item; struct du_node *prior,*next;LNODE,* LINK_LIST;（1）初始化雙向循環(huán)鏈表DLLINK_LIST InitDuList() LINK_LIST DL; LNODE *s，*R=NULL; DL=(LNODE *)malloc(sizeof(LNODE)； DL-next=CL；DL-prior=DL; int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)

30、； s-data=x； if (DL-next= =DL) s-next=DL;DL-next=s； s-prior=DL;DL-prior=s； else s-next=DL;R-next=s； s-prior=R;DL-prior=s； R=s； scanf(“%d”,&x)； return DL ; （2）在雙向循環(huán)鏈表DL中，第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e 在一個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)的過(guò)程。 在雙向循環(huán)鏈表中的p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)應(yīng)使用下列語(yǔ)句序列： s-next=p; s-prior=p-prior; p-prior-next=s; p-prior=s;圖 2-9ps2.4 線性表的應(yīng)用舉例 約瑟夫（Joseph）問(wèn)題：編號(hào)為1，2，n的n個(gè)人按順時(shí)針?lè)较驀谝粡垐A桌旁，每個(gè)人手中持有一個(gè)密碼（正整數(shù)）。首先輸入一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，然后，從第一個(gè)人開始按順時(shí)針?lè)较蜃?開始順序報(bào)數(shù)，報(bào)到m的人離開桌旁，并將他手中的密碼作為新的m值，從順時(shí)針?lè)较虻南乱粋€(gè)就坐在桌旁的人人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部離開桌旁為止。 假設(shè)有7個(gè)人，編號(hào)從1到7，他們手中的密碼分別是3，1，7，2，4，8，4，最初的m=2，通過(guò)報(bào)數(shù)，這7個(gè)人離開桌旁的順序應(yīng)該是：2，3，5，4，7，6，1。 數(shù)據(jù)結(jié)構(gòu)的分析 這個(gè)問(wèn)題的主角是n個(gè)人，每