2.3 單鏈表和循環單鏈表

線性表可以采用鏈式存儲結構進行存儲，鏈式存儲結構主要有單鏈表和雙鏈表等，本節主要介紹單鏈表和循環單鏈表。

2.3.1 單鏈表的定義

從2.2節看出，線性表順序存儲結構的空間是整體分配的，邏輯關系上相鄰的兩個元素在物理上也相鄰，因此存取表中任一元素十分簡單，但插入和刪除運算需要移動大量的元素。而線性表的鏈式存儲結構中每個元素的存儲空間作為一個結點單獨分配，因此邏輯上相鄰的元素對應的結點在物理上不一定是相鄰的，通過增加指針域表示邏輯關系，在插入和刪除操作時只需要修改相應的指針域，從而克服了順序表中插入和刪除操作需要移動大量的元素的弱點，但同時也失去了順序表可隨機存取的優點。

本節討論線性表的單鏈表存儲方法，它是一種最基本的鏈式存儲結構。單鏈表中每個結點存放一個數據元素，并用一個指針表示結點間的邏輯關系，即每個結點的指針域存放后繼結點的地址（線性表中每個元素有唯一的后繼元素）。因此單鏈表的一個存儲結點包含兩個部分，結點的基本形式如下：

其中，data部分稱為數據域，用于存儲線性表的一個數據元素，也就是說在單鏈表中一個結點存放一個數據元素；next部分稱為指針域或鏈域，用于指向后繼元素對應的結點。

單鏈表分為帶頭結點和不帶頭結點兩種類型。在許多情況下，帶頭結點的單鏈表能夠簡化運算的實現過程。因此本章討論的單鏈表除特別指出外均指帶頭結點的單鏈表。

另外，在單鏈表中尾結點之后不再有任何結點，那么它的next域設置為什么值呢？有以下兩種方式。

（1）將尾結點的next域用一個特殊值NULL（空指針，不指向任何結點，只起標志尾結點的作用）表示，這樣的單鏈表為非循環單鏈表。通常所說的單鏈表都是指這種類型的單鏈表。

（2）將尾結點的next域指向頭結點，這樣可以通過尾結點移動到頭結點，從而構成一個查找環，將這樣的單鏈表稱為循環單鏈表。

仍假設數據元素的類型為ElemType，單鏈表的結點類型聲明如下。

說明：上述SLinkNode類型聲明是合法的，實際上是給struct node結構體類型取了一個別名SLinkNode，這樣使算法書寫更簡潔。另外，如果其中next不是指針變量，如改為：

這樣就出錯了，這里SLinkNode1類型聲明是遞歸的，C/C++中不允許類型遞歸聲明。這是因為類型是用來定義變量的，如果類型聲明是遞歸的，則無法給變量分配空間。對于正確的SLinkNode類型，如果執行SLinkNode?p=（SLinkNode?）malloc（sizeof（SLinkNode））語句，其空間分配如圖2.12所示，其中，next只分配一個地址大小的空間，如32位機中，每個地址固定占用4B，所以能夠正確地為變量p分配所指向的內存空間，其大小為sizeof （ElemType）+4。

如果改為SLinkNode1?p1=（SLinkNode1?）malloc（sizeof（SLinkNode1））語句，p1指針變量分配的空間大小應該為sizeof（ElemType）+sizeof（SLinkNode1），而此時sizeof （SLinkNode1）是不能確定的，所以無法為p1分配指向的空間。

需要注意變量p的空間和p所指向的空間的區別，p變量本身僅占用一個地址空間，如4B，而它所指向的空間可能很大。可以這樣理解，前面定義指針變量p并分配所指空間的語句中，（SLinkNode?）malloc（sizeof（SLinkNode））部分由計算機分配一個沒有名字的內存空間，通過將其首地址放到變量p中，程序員就可以用變量p間接地操作這塊內存空間了，稱為p結點。為了簡化，通常不畫出p變量的空間，圖2.10可以用圖2.13的方式來簡化表示。

2.3.2 線性表基本運算在單鏈表上的實現

在帶頭結點的單鏈表中，頭結點的data域通常不存儲任何信息，頭結點的next域指向第一個數據結點，即存放第一個數據結點的地址。通過頭結點的指針L（稱為頭指針）來標識整個單鏈表。

如圖2.14所示是一個帶頭結點L的單鏈表，這樣的單鏈表中實際存放的數據元素為n個，即一個頭結點，n個數據結點。頭結點指針稱為頭指針，這里是通過頭指針標識單鏈表的。第一個數據結點稱為首結點，首結點指針稱為首指針（對于不帶頭結點的單鏈表，一般是通過首指針標識單鏈表）。最后一個結點稱為尾結點，尾結點指針稱為尾指針。

說明：盡管后面算法設計中使用的鏈表一般是帶頭結點的，有時根據實際需要也設計成不帶頭結點的鏈表，需要讀者在掌握帶頭結點鏈表算法設計的基礎上，領會不帶頭結點鏈表算法設計方法。

下面討論單鏈表中線性表基本運算算法的實現過程。

1．單鏈表的基本運算算法

1）初始化線性表運算算法

創建一個空的單鏈表，它只有一個頭結點，由L指向它。該結點的next域為空，data域未設定任何值，如圖2.15所示。對應的算法如下。

本算法的時間復雜度為O（1）。

說明：

（1）在單鏈表算法中，大量用到指針運算，讀者應充分理解指針運算的含義，如SLinkNode?p，?q，?r語句定義了三個相同類型的指針變量，它們可以指向同一個結點，也可以指向不同的結點（這些結點類型必須相同），但一個指針變量任何時刻只能指向一個結點。

如圖2.16所示，p、q指向不同的結點，當執行p—>next=q語句時，計算機先求出賦值符號右邊的表達式值（稱為右值），這里是結點值為b的結點的地址，存放在指針變量q中，賦值符號左邊的值（稱為左值，一定是有地址含義的表達式如變量名）p—>next被修改為q的值，也就是說，p所指結點的next域存放值為b的結點的地址。

（2）InitList算法中的形參L為引用類型，引用類型的含義在第1章中介紹過，這里再強調一下。任何算法都是用來被調用的（試想象一下，在C/C++程序中，除了main（）函數外，設計一個沒有被調用的函數，這個函數顯然是不會被執行的），例如以下主函數中調用了單鏈表中的幾個基本運算函數。

其中，h是實參，在執行SLinkNode?h語句時僅為指針變量h分配了一個地址空間，其值是沒有意義的，如果InitList（L）函數中形參L不是引用類型，當執行InitList（h）語句后，形參L的值不會回傳給實參h，也就是說h中還是先前沒有意義的值，再執行InsElem（h，x，1）語句（功能是在單鏈表h的第一個位置上插入一個值為x的結點）時一定出錯，因為希望初始化的單鏈表h實際上不存在。只有將InitList（L）函數中L設計為引用類型，執行InitList（h）語句后形參L的值才會回傳給實參h，h才真正指向一個單鏈表的頭結點，后面才會正確執行單鏈表的運算。

2）銷毀線性表運算算法

一個單鏈表L中的所有結點空間都是通過malloc函數分配的（即程序員自己手工分配的），在不再需要L時系統不會自動釋放這些結點空間，程序員必須通過調用free函數釋放所有結點的空間（即程序員自己手工分配的空間需要程序員自己手工釋放）。其實現過程是，先讓pre指向頭結點，p指向首結點（pre和p是一對相鄰結點指針），如圖2.17所示，當p不為NULL時循環：釋放pre所指結點空間，讓pre、p指針沿next域同步后移一個結點。當循環結束，p為NULL，此時再釋放pre所指的尾結點。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

3）求線性表的長度運算算法

不同于順序表，在單鏈表中沒有直接保存長度信息，需要通過掃描方式求長度。設置一個整型變量i作為計數器，i初值為0，p初始時指向首結點。然后沿next域逐個往后查找，每移動一次，i值增1。當p所指結點為空時，結束這個過程，i的值即為表長（數據結點個數，不計頭結點）。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

4）求線性表中第i個元素運算算法

用p從頭開始掃描單鏈表L中的結點，用計數器j累計掃描過的結點，其初值為0，在掃描中j等于i時，若p不為空，則p所指結點即為要找的結點，查找成功，算法返回1，如圖2.18所示；否則算法返回0表示未找到這樣的結點。

對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

說明：在順序表中該運算的時間復雜度為O（1），表明順序表具有隨機存取特性。而單鏈表中該運算的時間復雜度為O（n），表明單鏈表不具有隨機存取特性，這是兩種存儲結構的重要差別之一。

5）按值查找運算算法

在單鏈表L中從首結點開始查找第一個值域與e相等的結點，若存在這樣的結點，則返回其邏輯序號，如圖2.19所示；否則返回0。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

6）插入元素運算算法

先在單鏈表L中查找第i—1個結點，若未找到返回0；找到后由p指向該結點，創建一個以x為值的新結點s，將其插入到p結點之后。在p結點之后插入s結點的操作如下。

①將結點s的next域指向結點p的下一個結點（s—>next=p—>next）。

②將結點p的next域改為指向新結點s（p—> next=s）。

插入結點的過程如圖2.20所示，從中看到，在單鏈表中插入一個結點需找到其前驅結點，在插入一個新結點時只需修改前驅結點和新插入結點的next域，不像順序表那樣需要移動大量的元素。

注意：插入操作的①和②執行順序不能顛倒，否則若先執行p—>next=s，由于先修改p—>next值使原p結點的后繼結點的地址丟失了，會導致插入錯誤。

對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

7）刪除元素運算算法

先在單鏈表L中查找第i—1個結點，若未找到返回0，找到后由p指向該結點，然后讓q指向后繼結點（即要刪除的結點），若q所指結點為空則返回0；否則刪除q結點并釋放其占用的空間。

刪除p指結點的后繼結點的過程如圖2.21所示，其操作如下。

      p—>next=q—>next;

從中看到，在單鏈表中刪除一個結點和插入一個結點一樣，需要找到其前驅結點，而且刪除結點不像在順序表中刪除一個元素需要移動大量的元素。

對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

8）輸出線性表運算算法

從首結點開始，沿next域逐個往下掃描，輸出每個掃描到結點的data域，直到尾結點為止。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

提示：將單鏈表結點類型聲明及其基本運算函數存放在SLinkNode.cpp文件中。

當單鏈表的基本運算設計好后，給出以下主函數調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會單鏈表各種操作的實現過程。

上述程序的執行結果如圖2.9所示。

2．整體創建單鏈表的算法

可以通過調用基本運算算法來創建單鏈表，其過程是先初始化一個單鏈表然后向其中一個一個地插入元素。這里介紹的是快速整體創建單鏈表的算法也稱為整體建表。假設給定一個含有n個元素的數組，由它來整體創建單鏈表，這種建立單鏈表的常用方法有如下兩種。

1）頭插法建表

該方法從一個空單鏈表（含頭結點L，并且置L—>next為NULL）開始，讀取數組a（含有n個元素）中的一個元素，創建一個新結點s，將讀取的數據元素存放到該結點的數據域中，然后將其插入到當前鏈表的表頭上（操作語句是s—>next= L—>next；L—>next=s；），如圖2.22所示。

再讀取數組a的下一個元素，采用相同的操作建立新結點s并插入到單鏈表L中，直到數組a中所有元素讀完為止。

采用頭插法建表的算法如下。

本算法的時間復雜度為O（n）。

若數組a包含4個元素1、2、3和4，則調用CreateListF（L，a，4）建立的單鏈表如圖2.23所示，從中看到，單鏈表L中數據結點的次序與數組a的元素次序正好相反。

2）尾插法建表

該方法從一個空單鏈表（含頭結點L，L—>next不必置為NULL）開始，讀取數組a（含有n個元素）中的一個元素，生成一個新結點s，將讀取的數據元素存放到該結點的數據域中，然后將其鏈接到單鏈表L的表尾，如圖2.24所示。由于尾插法建表每次將新結點鏈接到表尾，而單鏈表L中并沒有保存尾結點的地址信息，為此增加一個尾指針tc，使其始終指向當前單鏈表的尾結點，初始時只有一個頭結點L，則置tc=L，這樣將新結點s鏈接到表尾的操作是：tc—>next=s，此時結點s變成新的尾結點，所以還需要置tc=s。

再讀取數組a的下一個元素，采用相同的操作建立新結點s并插入到單鏈表L中，直到數組a中所有元素讀完為止。與頭插法不同，尾插法最后還需要將尾結點的next域置為空，即tc—>next=NULL。

采用尾插法建表的算法如下。

本算法的時間復雜度為O（n）。

若數組a包含4個元素1、2、3和4，則調用CreateListR（L，a，4）建立的單鏈表如圖2.25所示，從中看到，單鏈表L中數據結點的次序與數組a的元素次序相同。

提示：將單鏈表的兩個整體建表函數也存放在SLinkNode.cpp文件中。

2.3.3 單鏈表的算法設計示例

1．基于單鏈表基本操作的算法設計

這類算法設計中包括單鏈表結點的查找、插入和刪除等。

【例2.11】設計一個算法，通過一趟掃描確定單鏈表L（至少含兩個數據結點）中第一個元素值最大的結點。

解：用p掃描單鏈表，在掃描時用maxp指向data域值最大的結點（maxp的初值為p）。當單鏈表掃描完畢，最后返回maxp。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

【例2.12】設計一個算法，通過一趟掃描求單鏈表L（至少含兩個數據結點）中第一個值最大結點的前驅結點，若存在這樣的結點，返回其指針（地址），否則返回NULL。

解：以p掃描單鏈表，pre指向p結點的前驅結點，在掃描時用maxp指向data域值最大的結點（maxp的初值為p），maxpre指向maxp結點的前驅結點（maxpre的初值為pre）。當單鏈表掃描完畢，最后返回maxpre。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

【例2.13】設計一個算法，刪除一個單鏈表L（至少含兩個數據結點）中第一個值最大的結點。

解：在單鏈表中刪除一個結點先要找到它的前驅結點。以p掃描單鏈表，pre指向p結點的前驅結點，在掃描時用maxp指向data域值最大的結點，maxpre指向maxp結點的前驅結點。當單鏈表掃描完畢，通過maxpre結點刪除其后的結點，即刪除了元素值最大的結點。對應的算法如下。

本算法的時間復雜度為O（n）。

2．基于整體建表的算法設計

這類算法設計中需要根據條件產生新的結果單鏈表，而創建結果單鏈表的方法有頭插法和尾插法。

【例2.14】設計一個算法，將一個單鏈表L（至少含兩個數據結點）中所有結點逆置。并分析算法的時間復雜度。

解：先將單鏈表L拆分成兩部分，一部分是只有頭結點L的空表（結果單鏈表），另一部分是由p指向首結點的單鏈表。然后掃描p，將p所指結點逐一采用頭插法插入到L單鏈表中，由于頭插法的特點是建成的單鏈表結點次序與插入次序正好相反，從而達到結點逆置的目的。對應的算法如下。

本算法正好掃描了L中所有數據結點一次，所以時間復雜度為O（n），其中，n為單鏈表L中的數據結點個數。

【例2.15】假設有一個單鏈表L，其中元素為整數且所有元素值均不相同。設計一個盡可能高效的算法將所有奇數移到所有偶數的前面。

解：先將單鏈表L拆分成兩部分，一部分是只有頭結點L的空表（結果單鏈表），另一部分是由p指向首結點的單鏈表。然后掃描p，將奇數結點p采用頭插法插入到L的開頭，將偶數結點p采用尾插法插入到L的末尾。為此設置一個尾結點指針tc，初始時tc指向頭結點，每次插入一個偶數結點時會移動tc，但插入一個奇數結點時不會移動tc，這會導致插入一個奇數結點后再插入一個偶數結點出現錯誤，所以在第一個插入的結點為奇數結點p時，除了頭插法插入結點p，還需要置tc=p（若此時后面插入連續若干奇數結點，tc指向的仍然是正確的尾結點）。對應的算法如下。

本算法正好掃描了單鏈表中每個結點一次，所以時間復雜度為O（n），算法中只定義了固定幾個臨時變量，所以算法的空間復雜度為O（1）。

3．有序單鏈表的二路歸并算法

有序單鏈表是有序表的單鏈表存儲結構，同樣可以利用有序表元素的有序性提高相關算法的效率。當數據采用單鏈表存儲時，對應的二路歸并就是單鏈表二路歸并算法。

【例2.16】設ha和hb分別是兩個帶頭結點的遞增有序單鏈表。設計一個算法，將這兩個有序鏈表的所有數據結點合并成一個遞增有序的單鏈表hc，并分析算法的時間和空間復雜度。要求hc單鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其他的存儲空間，ha和hb兩個表中允許有重復的數據結點。

解：采用二路歸并的思路，用pa掃描ha的數據結點，pb掃描hb的數據結點，將ha頭結點用作新單鏈表hc的頭結點，讓tc始終指向hc的尾結點（初始時指向hc）。當pa和pb均不為空時循環：比較pa與pb的data值，將較小者鏈接到單鏈表hc的末尾。如此重復直到ha或hb為空，再將余下的鏈表結點鏈接到單鏈表hc的末尾。對應的算法如下。

設兩個有序單鏈表中數據結點個數分別為m和n，算法中僅對兩個單鏈表中所有結點掃描一遍，所以算法的時間復雜度為O（m+n）。算法中僅定義固定個數的臨時變量，所以算法的空間復雜度為O（1）。

注意：本例是由ha和hb創建hc，而hc沒有另外分配存儲空間，而是利用ha和hb的所有結點重新鏈接產生hc的，所以算法的空間復雜度為O（1），但當hc建成后，ha和hb被破壞了，即調用本算法后，ha和hb不再存在。

【例2.17】設ha和hb分別是兩個帶頭結點的遞增有序單鏈表。設計一個算法，由表ha和表hb的所有公共結點（兩單鏈表中data值相同的結點）產生一個遞增有序單鏈表hc，分析算法的時間和空間復雜度。要求不破壞原來兩個鏈表ha和hb的存儲空間。

解：本算法仍采用二路歸并的思路，用pa、pb分別掃描單鏈表ha、hb，只不過僅僅將公共的結點復制并鏈接到單鏈表hc的末尾，結果單鏈表hc采用尾插法創建。對應的算法如下。

設兩個有序單鏈表中數據結點個數分別為m和n，算法中最多僅對兩個單鏈表中所有結點掃描一遍，所以算法的時間復雜度為O（m+n）。設ha和hb中公共結點個數為k，算法中新建了k+1結點（含hc的頭結點），k最大值為min（m，n），所以算法的空間復雜度為O（min（m，n））。

注意：本例是由ha和hb創建hc，示例要求不破壞ha和hb，這樣必須采用結點復制的方法，所以算法的空間復雜度不再為O（1）。

4．單鏈表的排序算法

在很多情況下，單鏈表中結點有序時可以提高相應算法的效率。這里通過一個示例討論單鏈表的遞減排序過程。

【例2.18】設計一個完整的程序，根據用戶輸入的學生人數n（n≥3）及每個學生姓名和成績建立一個單鏈表，并按學生成績遞減排序，然后按名次輸出所有學生的姓名和成績。

解：（1）設計存儲結構。

依題意，聲明學生單鏈表結點類型為StudList：

例如，有4個學生記錄，其姓名和成績分別為：（Mary，75），（John，90），（Smith，85），（Harry，95），其構建的帶頭結點的單鏈表如圖2.26所示。

（2）設計基本運算算法。

設計基本運算算法如下。

①void CreateStudent（StudList?&sl）：采用交互式方式創建學生單鏈表。

②void DestroyList（StudList?&L）：銷毀學生單鏈表。

③void DispList（StudList?L）：輸出學生單鏈表。

④void SortList（StudList?&L）：將學生單鏈表按成績遞減排序。

采用尾插法創建學生單鏈表的算法如下。

銷毀學生單鏈表的算法如下。

輸出學生單鏈表的算法如下。

對學生單鏈表按成績遞減排序是一個比較復雜的過程，先將該單鏈表拆分成兩部分，如圖2.27所示，一部分是只有一個數據結點的有序單鏈表，另一部分是余下的數據結點，由p所指向。

然后將p結點通過比較插入到有序單鏈表中，在插入時要找插入的前驅結點pre，pre開始時指向頭結點，通過pre—>next—>score與p—>score比較，當前者大于后者時，pre向后移一個結點，如此直到pre—>next為NULL或者pre—>next—>score <p—>score成立，最后將p結點插入到pre結點之后，如圖2.28所示是插入Smith結點的情況。

學生單鏈表按成績遞減排序的算法如下。

（3）設計主函數。

最后設計如下主函數。

（4）執行結果。

本程序的一次執行結果如下（下畫線部分表示用戶輸入，↙表示Enter鍵）。

2.3.4 循環單鏈表

循環單鏈表是由單鏈表改造而來的，將單鏈表中尾結點的next域由原來為NULL改為指向頭結點，這樣整個鏈表形成一個環。循環單鏈表的特點是從任一結點出發都可以找到表中其他結點。

循環單鏈表的結點類型與單鏈表的結點類型相同，也采用前面聲明的SLinkNode類型。如圖2.29所示是一個帶頭結點的有n個數據結點的循環單鏈表L。

從圖中看出，在循環單鏈表L中，p所指結點為尾結點的條件是p—>next==L。

循環單鏈表的整體建表算法也分為頭插法建表和尾插法建表，和單鏈表的相似，只需在建立后將尾結點next域指向頭結點即可，這里不再介紹。

在循環單鏈表中線性表基本運算算法的實現如下。

1．初始化線性表運算算法

創建一個空的循環單鏈表，它只有頭結點，由L指向它。該結點的next域指向該頭結點，data域未設定任何值，如圖2.30所示。對應的算法如下。

本算法的時間復雜度為O（1）。

2．銷毀線性表運算算法

一個循環單鏈表L中的所有結點空間都是通過malloc函數分配的，在不再需要時需通過free函數釋放所有結點的空間。其實現過程是，先讓pre指向頭結點，p指向首結點，當p不為頭結點時循環：釋放pre所指結點空間，讓pre、p指針沿next域同步后移一個結點。當循環結束，p指向頭結點，此時再釋放pre所指的尾結點。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為單鏈表L中數據結點的個數。

3．求線性表的長度運算算法

設置一個整型變量i作為計數器，i初值為0，p初始時指向第一個結點。然后沿next域逐個往后移動，每移動一次，i值增1。當p所指結點為頭結點時這一過程結束，i的值即為表長。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

4．求線性表中第i個元素運算算法

用p從頭開始掃描循環單鏈表L中的結點（初值指向首結點），用計數器j累計掃描過的結點，其初值為1。當p不為L且j＜i時循環，p后移一個結點，j增1。當循環結束時，若p指向頭結點時表示查找失敗返回0，否則p所指結點即為要找的結點，查找成功，算法返回1。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

5．按值查找運算算法

用i累計查找數據結點的個數，從首結點開始，由前往后依次比較單鏈表中各結點數據域的值，若某結點數據域的值等于給定值x，則返回i；否則繼續向后比較。若整個單鏈表中沒有這樣的結點，則返回0。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

6．插入元素運算算法

在循環單鏈表L中查找第i個結點p及其前驅結點pre，若沒有這樣的結點p返回0；否則創建一個以x為值的新結點s，將結點s插在pre結點之后，如圖2.31所示，返回1。

對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表中數據結點的個數。

說明：在循環單鏈表中，用p指針掃描所有結點時，方式有兩種：一是以p!=L作為循環條件，當p==L時循環結束，此時p回過來指向頭結點，所以p應該初始化指向首結點而不是頭結點，否則循環內的語句不會執行。二是掃描指針p的初始化為p=L，循環的條件應該為p—>next!=L，當p—>next==L時循環結束，此時p指向尾結點。上述插入元素運算算法中采用前一種方式查找第i—1個結點，后面刪除元素運算算法中采用后一種方式查找第i個結點。

7．刪除元素運算算法

在循環單鏈表L中查找第i—1個結點，若不存在這樣的結點返回0；否則讓p指向第i—1個結點，q指向后繼結點，當q為NULL時返回0，否則將q所指結點刪除并釋放其空間，返回1。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

8．輸出線性表運算算法

從首結點開始，沿next域逐個往下掃描，輸出每個掃描到結點的data域，直到頭結點為止。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

說明：將循環單鏈表結點類型聲明及其基本運算函數存放在CSLinkNode.cpp文件中。

從以上看到，單鏈表與循環單鏈表的結點類型完全相同，實現基本運算的算法也很相似。實際上，循環鏈表和對應的非循環鏈表的運算基本一致，差別僅在于算法中的循環條件不是判斷p或p—>next是否為空，而是判斷它們是否等于頭結點的指針。

當循環單鏈表的基本運算設計好后，給出主函數調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會循環單鏈表各種操作的實現過程。

上述程序的執行結果如圖2.9所示。

2.3.5 循環單鏈表的算法設計示例

【例2.19】設計一個算法求一個循環單鏈表L中所有值為x的結點個數。

解：用指針p掃描循環單鏈表L的所有結點，用i（初值為0）累加值為x的結點個數，最后返回i。對應的算法如下。

【例2.20】有一個遞增有序的循環單鏈表L，設計一個算法刪除其中所有值為x的結點，并分析算法的時間復雜度。

解：由于循環單鏈表L是遞增有序的，則所有值為x的結點必然是相鄰的。先找到第一個值為x的結點p，讓pre指向其前驅結點。然后通過pre結點刪除p結點及其后面連續值為x的結點。對應的算法如下。

本算法的時間復雜度為O（n），其中，n為循環單鏈表L中數據結點的個數。

【例2.21】編寫一個程序求解約瑟夫（Joseph）問題。有n個小孩圍成一圈，給他們從1開始依次編號，從編號為1的小孩開始報數，數到第m個小孩出列，然后從出列的下一個小孩重新開始報數，數到第m個小孩又出列，……，如此反復直到所有的小孩全部出列為止，求整個出列序列。如當n=6，m=5時的出列序列是5，4，6，2，3，1。

解：（1）設計存儲結構。

本題采用循環單鏈表存放小孩圈，其結點類型如下。

依本題操作，小孩圈構成一個循環單鏈表，例如，n=6時的初始循環單鏈表如圖2.32所示，L指向開始報數的小孩結點。

注意：前面介紹的循環單鏈表都是帶頭結點，而這里的循環單鏈表是不帶頭結點，因為本題中循環單鏈表帶頭結點會導致循環查找數據結點更復雜，為此在算法設計中需要針對不帶頭結點的情況做相應的修改。

（2）設計基本運算算法。

設計兩個基本運算算法。由指定的n采用尾插法創建不帶頭結點的小孩圈循環單鏈表L的算法如下。

由指定的n和m輸出約瑟夫序列的算法如下。

（3）設計主函數。

設計如下主函數求解n=6，m=5的約瑟夫序列。

      void main()
      {   int n=6,m=5;
          printf(＂n=%d,m=%d的約瑟夫序列：＂,n,m);
          Joseph(n,m);printf(＂\n＂);
      }

（4）執行結果。

本程序的執行結果如下。

      n=6,m=5的約瑟夫序列：5 4 6 2 3 1