1、適莽蒼者，三飡而反，腹猶果然；適百里適莽蒼者，三飡而反，腹猶果然；適百里者，宿舂糧；適千里者，三月聚糧。者，宿舂糧；適千里者，三月聚糧。同學們，你打算為自己的將來準備多少資糧？同學們，你打算為自己的將來準備多少資糧？第二章 線性表主要內容主要內容n2.1 線性表的基礎知識線性表的基礎知識n2.2 順序表順序表n2.3 單鏈表單鏈表n2.4 線性鏈表的其它變形線性鏈表的其它變形n2.5 單鏈表的應用：多項式乘法單鏈表的應用：多項式乘法n2.6 靜態鏈表靜態鏈表2.1.2 線性結構線性結構n線性結構可以定義為二元組線性結構可以定義為二元組B=(K,R) , 其中其中K = a0, a1, an-1

2、,R= 前驅前驅/后繼關系后繼關系 u有一個唯一的開始節點有一個唯一的開始節點，它沒有前驅它沒有前驅，有一個唯一的直接有一個唯一的直接后繼后繼。u一個唯一的一個唯一的 終止節點終止節點，它有一個唯一的直接前驅它有一個唯一的直接前驅，而，而沒沒有后繼有后繼。u其它的結點皆稱為內部結點，其它的結點皆稱為內部結點，每一個內部結點都有且僅有每一個內部結點都有且僅有一個唯一的直接有前驅，也有一個唯一的直接后繼一個唯一的直接有前驅，也有一個唯一的直接后繼，如：，如：，ai是是ai+1的前驅，的前驅，ai+1是是ai的后繼。的后繼。u前驅前驅/后繼關系后繼關系r，具有，具有 反對稱性反對稱性 和和 傳遞性傳

3、遞性2.1.2 線性結構線性結構n線性結構的特點線性結構的特點均勻性：雖然不同線性表的數據元素可以是各種各樣的，均勻性：雖然不同線性表的數據元素可以是各種各樣的，但對于同一線性表的各數據元素必定具有相同的數據類型但對于同一線性表的各數據元素必定具有相同的數據類型和長度和長度 有序性：各數據元素在線性表中都有自己的位置，且數有序性：各數據元素在線性表中都有自己的位置，且數據元素之間的相對位置是線性的據元素之間的相對位置是線性的2.1.3 線性表的三個方面線性表的三個方面n線性表的邏輯結構線性表的邏輯結構n線性表的存儲結構線性表的存儲結構n線性表的操作線性表的操作存存儲儲邏邏輯輯操作操作線性線性表

4、表2.1.3 線性表的三個方面：邏輯結構線性表的三個方面：邏輯結構a0，a1，an-2，an-1u有一個唯一的開始節點有一個唯一的開始節點a0 ，它沒有前驅它沒有前驅，有一個唯一的直有一個唯一的直接后繼接后繼a1 。u一個唯一的一個唯一的 終止節點終止節點an-1 ，它有一個唯一的直接前驅它有一個唯一的直接前驅，而，而沒有后繼沒有后繼an-2 。u其它的結點皆稱為內部結點，其它的結點皆稱為內部結點，每一個內部結點都有且僅有每一個內部結點都有且僅有一個唯一的直接有前驅，也有一個唯一的直接后繼一個唯一的直接有前驅，也有一個唯一的直接后繼，如：，如：，ai是是ai+1的前驅，的前驅，ai+1是是ai

5、的后繼。的后繼。2.1.3 線性表的三個方面：存儲結構線性表的三個方面：存儲結構n 順序存儲表示：順序表順序存儲表示：順序表0123456789a1a2a3a4a5n鏈接存儲表示：鏈表鏈接存儲表示：鏈表*a1a7a6a5a4a3a2a10a9a82.1.3 線性表的三個方面：操作線性表的三個方面：操作u建立線性表建立線性表 u清除線性表清除線性表 u插入一個新元素插入一個新元素 u刪除某個元素刪除某個元素 u修改某個元素修改某個元素 u排序排序 u檢索（查找）檢索（查找）n線性表上的關鍵操作如下：線性表上的關鍵操作如下：2.3 單鏈表單鏈表n2.3.1 單鏈表的定義單鏈表的定義n2.3.2 單

6、鏈表的特點單鏈表的特點n2.3.3 單鏈表的實現策略單鏈表的實現策略n2.3.4 單鏈表模板的定義單鏈表模板的定義n2.3.5 單鏈表上的操作單鏈表上的操作n2.3.6 帶頭結點的單鏈表帶頭結點的單鏈表2.3.1 單鏈表的定義單鏈表的定義n單鏈表是包含單鏈表是包含0個或多個元素的線性結構個或多個元素的線性結構，其中每個元素（也稱為節點）包含兩個域：其中每個元素（也稱為節點）包含兩個域：數據域和鏈域數據域和鏈域。u數據域用于存儲線性表的一個數據元素，數據域用于存儲線性表的一個數據元素，其數據類型由其數據類型由應用問題決定應用問題決定。u鏈域用于存放一個指針，該指針指示鏈表中下一個結點鏈域用于存放

7、一個指針，該指針指示鏈表中下一個結點的開始存儲地址。的開始存儲地址。表頭表頭表尾表尾表尾沒有直接后繼，其鏈域設置為空。課件中用表尾沒有直接后繼，其鏈域設置為空。課件中用表示空。表示空。a1a2a3a4a5firstdata next元素：元素：2.3.1 單鏈表的特點單鏈表的特點u結點之間可以連續，可以不連續存儲。結點之間可以連續，可以不連續存儲。u結點的邏輯順序與物理順序可以不一致。結點的邏輯順序與物理順序可以不一致。u表的長度可以很方便的進行擴充。表的長度可以很方便的進行擴充。a1a2a3a4firsta1a3a2a4first2.3.3 單鏈表的實現策略單鏈表的實現策略n單鏈表單鏈表中有

8、中有0個或多個個或多個節點節點，支持節點的增，支持節點的增刪查改。刪查改。n節點包含數據域和鏈域。a1a2a3a4first如何定義結點？如何在結點的基礎上定義單鏈表？如何定義結點？如何在結點的基礎上定義單鏈表？2.3.3單鏈表的實現策略單鏈表的實現策略/結點的定義結點的定義struct ListNode /鏈表結點類鏈表結點類 int data; /結點數據域結點數據域 ListNode * next; /結點鏈接指針域結點鏈接指針域 ; /鏈表的定義鏈表的定義class List private: ListNode *first; /表頭指針表頭指針 ; uListNode類與類與List

9、類是類是包含（具包含（具體講是聚合）的關系體講是聚合）的關系。 uListNode中的數據域和鏈域是中的數據域和鏈域是public成員，成員，List類可以通過對象類可以通過對象直接訪問它們。直接訪問它們。u鏈表中的結點屬于鏈表私有，別鏈表中的結點屬于鏈表私有，別人無法訪問。人無法訪問。2.3.3單鏈表的實現策略單鏈表的實現策略n單鏈表分為單鏈表分為不帶頭結點單鏈表不帶頭結點單鏈表和和帶頭結點帶頭結點單鏈表單鏈表兩種，兩種，本課件先介紹不帶頭結點單本課件先介紹不帶頭結點單鏈表鏈表。2.3.4單鏈表模板的定義單鏈表模板的定義n結點模板的定義結點模板的定義templatestruct LinkNo

10、de T data; LinkNode* next; LinkNode(const T& item, LinkNode* ptr=NULL); LinkNode(LinkNode* ptr=NULL);templateclass Listprivate: LinkNode * first;public: List(); List(const List& L); List& operator=(const List& L); List(); void InputFront(const T& elem); void InputRear(const T&

11、; elem); bool Insert(int i, const T& x); bool Remove(int i, T& x); LinkNode* Search(const T& x); LinkNode* Locate(int i); bool GetData(int i, T& x)const; void SetData(int i, const T& x); void MakeEmpty(); void CopyList(const List& L); int Length() const; bool IsEmpty() const;

12、 bool IsFull() const; void Sort(); friend ostream& operator(ostream& out, const List& L); friend istream& operator(istream& in, List& L);n單鏈表模板的定義單鏈表模板的定義構造函數，拷貝構構造函數，拷貝構造函數，賦值運算造函數，賦值運算符函數，析構函數符函數，析構函數單鏈表的增刪查改單鏈表的增刪查改清空復制鏈表節點清空復制鏈表節點鏈表自身狀態鏈表自身狀態2.3.5 單鏈表的操作單鏈表的操作n創建空鏈表創建空鏈表L

13、ist();空鏈表即鏈表中沒有結點。空鏈表即鏈表中沒有結點。List() first=NULL;2.3.5 單鏈表的操作單鏈表的操作n新建鏈表：頭插法新建鏈表：頭插法頭插法是每次插入新節點總是在表的表頭位置，這頭插法是每次插入新節點總是在表的表頭位置，這樣插入的結果，鏈表中各節點中數據的邏輯順序與樣插入的結果，鏈表中各節點中數據的邏輯順序與輸入數據的順序正好相反。主要步驟為：輸入數據的順序正好相反。主要步驟為：u從一個空表開始，重復讀入數據，執行以下步驟：從一個空表開始，重復讀入數據，執行以下步驟： （1）. 生成新節點，將讀入數據存放到新節點的生成新節點，將讀入數據存放到新節點的data域中

14、；域中； （2）. 將該新節點插入到鏈表的表頭位置。將該新節點插入到鏈表的表頭位置。 void InputFront(const T& elem);2.3.5 單鏈表的操作單鏈表的操作n新建鏈表：頭插法（例子）新建鏈表：頭插法（例子）u從一個空表開始，重復讀入數據，執行以下步驟：從一個空表開始，重復讀入數據，執行以下步驟： （1）. 生成新節點，將讀入數據存放到新節點的生成新節點，將讀入數據存放到新節點的data域中；域中； （2）. 將該新節點插入到鏈表的表頭位置。將該新節點插入到鏈表的表頭位置。first空表：空表：輸入數據：輸入數據： 25,34,57,16,47,09,632.

15、3.5 單鏈表的操作單鏈表的操作:頭插法頭插法當前表：當前表：34插入新節點后：插入新節點后：first2534first255757newNode：first當前表：當前表：25first25插入新節點后：插入新節點后：newNode：當前表：當前表：34first25插入新節點后：插入新節點后：first2534newNode：newNode-next=first; first=newNode;2.3.5 單鏈表的操作單鏈表的操作n新建鏈表：尾插法新建鏈表：尾插法尾插法：指每次新節點總是插入到鏈表的表尾位置，尾插法：指每次新節點總是插入到鏈表的表尾位置，這樣插入的結果，鏈表中各節點中數據的

16、邏輯順序這樣插入的結果，鏈表中各節點中數據的邏輯順序與輸入數據的順序完全一致。與輸入數據的順序完全一致。u從一個空表開始，重復讀入數據，執行以下步驟：從一個空表開始，重復讀入數據，執行以下步驟： （1）. 生成新節點，將讀入數據存放到新節點的生成新節點，將讀入數據存放到新節點的data域中；域中； （2）. 將該新節點插入到鏈表的表尾位置。將該新節點插入到鏈表的表尾位置。void InputRear(const T& elem);2.3.5 單鏈表的操作單鏈表的操作n新建鏈表：尾插法（例子）新建鏈表：尾插法（例子）u從一個空表開始，重復讀入數據，執行以下步驟：從一個空表開始，重復讀入數

17、據，執行以下步驟： （1）. 生成新節點，將讀入數據存放到新節點的生成新節點，將讀入數據存放到新節點的data域中；域中； （2）. 將該新節點插入到鏈表的表尾位置。將該新節點插入到鏈表的表尾位置。first空表：空表：輸入數據：輸入數據： 25,34,57,16,47,09,63當前表：當前表：34first25插入新節點后：插入新節點后： first255734571616newNode：當前表：當前表：34first25插入新節點后：插入新節點后：first25573457newNode：當前表：當前表：34first25插入新節點后：插入新節點后： first2534newNode：f

18、irst當前表：當前表：first25插入新節點后：插入新節點后：25newNode：尾插法空表和非空表插入操作時的情況不一致。尾插法空表和非空表插入操作時的情況不一致。當前表：當前表：34first25插入新節點后：插入新節點后： first255734571616newNode：當前表：當前表：34first25插入新節點后：插入新節點后：first25573457newNode：當前表：當前表：34first25插入新節點后：插入新節點后： first2534newNode：first當前表：當前表：first25插入新節點后：插入新節點后：25newNode：原因：尾插法總是在表尾節點

19、的后面插入節原因：尾插法總是在表尾節點的后面插入節點，空表時沒有表尾節點。點，空表時沒有表尾節點。u當鏈表為空時：當鏈表為空時：first當前表：當前表：first25插入新節點后：插入新節點后：25newNode：first=newNode;u當鏈表非空時：當鏈表非空時：當前表：當前表：34first25插入新節點后：插入新節點后：first25573457newNode：首先找到表尾節點；然后修改表尾節點的首先找到表尾節點；然后修改表尾節點的next域，讓它指向新域，讓它指向新節點。節點。表尾節點的特點：表尾節點的特點：尾節點的尾節點的next域為空。域為空。rear=first;whil

20、e(rear-next) rear=rear-next;rear-next=newNode;2.3.5 單鏈表的操作單鏈表的操作n單鏈表中插入結點單鏈表中插入結點bool Insert(int i, const T& x);u在鏈表的表頭插入節點在鏈表的表頭插入節點u在鏈表的中間插入節點在鏈表的中間插入節點u在鏈表的表尾插入節點在鏈表的表尾插入節點當前表：當前表：34first25插入新節點后：插入新節點后：first2534newNode：表頭插入節點：表頭插入節點：Insert(1,34);當前表：當前表：57first25插入新節點后：插入新節點后：first25343457ne

21、wNode：表中插入節點：表中插入節點：Insert(2,57);表尾插入節點：表尾插入節點：Insert(4,16);當前表：當前表：34first25插入新節點后：插入新節點后： first255734571616newNode：在鏈表中插入元素時，需要找到插入位置的直接前驅節點，但在鏈表中插入元素時，需要找到插入位置的直接前驅節點，但單鏈單鏈表的表頭節點沒有直接前驅表的表頭節點沒有直接前驅，所以必須單獨處理。，所以必須單獨處理。2.3.5 單鏈表的操作單鏈表的操作n單鏈表中插入結點單鏈表中插入結點bool Insert(int i, const T& x);表頭插入節點：表頭插入

22、節點：Insert(1,34);當前表：當前表：34first25插入新節點后：插入新節點后：first2534newNode：在單鏈表的頭部插入結點時，具體步驟為：在單鏈表的頭部插入結點時，具體步驟為：修改修改newNode所指結點的所指結點的next域，使它的值與域，使它的值與first指針指針的指向相同；的指向相同；1. 修改修改first指針的指向，使它指向指針的指向，使它指向newNode所指結點。所指結點。2.3.5 單鏈表的操作單鏈表的操作n單鏈表中插入結點單鏈表中插入結點bool Insert(int i, const T& x);表頭插入節點：表頭插入節點：Inser

23、t(1,34);當前表：當前表：34first25插入新節點后：插入新節點后：first2534newNode：newNode-next=first;first=newNode;2.3.5單鏈表的操作單鏈表的操作n單鏈表中插入節點單鏈表中插入節點bool Insert(int i, const T& x);表中，表尾插入節點：表中，表尾插入節點：在鏈表的中間和尾部插入結點時，具體步驟為：在鏈表的中間和尾部插入結點時，具體步驟為： 定位當前位置的前驅節點定位當前位置的前驅節點pre； 將將pre所指結點的所指結點的next域賦值給域賦值給newNode所指結點的所指結點的next域；域；

24、1. 使使pre所指結點的所指結點的next域指向域指向newNode所指結點。所指結點。當前表：當前表：57first25插入新節點后：插入新節點后：first25343457newNode：表中插入節點：表中插入節點：Insert(2,57);2.3.5單鏈表的操作單鏈表的操作n單鏈表中插入節點單鏈表中插入節點bool Insert(int i, const T& x);表中，表尾插入節點：表中，表尾插入節點：當前表：當前表：57first25插入新節點后：插入新節點后：first25343457newNode：pre表中插入節點：表中插入節點：Insert(2,57);57new

25、NodenewNode-next=pre-next;pre-next=newNode;2.3.5單鏈表的操作單鏈表的操作n單鏈表中插入節點單鏈表中插入節點bool Insert(int i, const T& x); pre=first; for(int j=1; jnext; if(pre=NULL) cerr無效的插入位置無效的插入位置endl; return false; else newNode=new LinkNode(x); newNode-next=pre-next; pre-next=newNode; 在鏈表的中間和尾部插入結點時，在鏈表的中間和尾部插入結點時，具體步驟

26、為：具體步驟為：定位當前位置的前驅節點定位當前位置的前驅節點pre；將將pre所指結點的所指結點的next域賦值域賦值給給newNode所指結點的所指結點的next域；域；1. 使使pre所指結點的所指結點的next域指向域指向newNode所指結點。所指結點。2.3.5單鏈表的操作單鏈表的操作n單鏈表中插入節點：特殊情況單鏈表中插入節點：特殊情況u插入位置非法插入位置非法 插入位置小于插入位置小于1。 插入位置大于鏈表長度。插入位置大于鏈表長度。2.3.5 單鏈表的操作單鏈表的操作n單鏈表中刪除結點單鏈表中刪除結點bool Remove(int i, T& x);u在鏈表的表頭刪除節

27、點在鏈表的表頭刪除節點u在鏈表的中間刪除節點在鏈表的中間刪除節點u在鏈表的表尾刪除節點在鏈表的表尾刪除節點當前表：當前表：34刪除節點后：刪除節點后：first2534first2557刪除表頭節點刪除表頭節點:Remove(1,elem);刪除表頭節點刪除表頭節點:Remove(2,elem);當前表：當前表：57first25刪除節點后：刪除節點后：first253434當前表：當前表：34first25刪除節點后：刪除節點后：first2557345716刪除表尾節點刪除表尾節點:Remove(4,elem);在鏈表中刪除元素時，需要找到刪除位置的直接前驅節點，但在鏈表中刪除元素時，需要

28、找到刪除位置的直接前驅節點，但單鏈單鏈表的表頭節點沒有直接前驅表的表頭節點沒有直接前驅，所以必須單獨處理。，所以必須單獨處理。2.3.5 單鏈表的操作單鏈表的操作n單鏈表中刪除結點單鏈表中刪除結點表頭刪除節點：表頭刪除節點：Remove(1,elem);在單鏈表的頭部刪除結點時，具體步驟為：在單鏈表的頭部刪除結點時，具體步驟為：將表頭節點的數據域賦值給將表頭節點的數據域賦值給elem。使使first指向表頭節點的指向表頭節點的next域。域。1. 釋放原表頭節點的內存空間。釋放原表頭節點的內存空間。bool Remove(int i, T& x);當前表：當前表：34刪除節點后：刪除節

29、點后：first2534first25572.3.5 單鏈表的操作單鏈表的操作n單鏈表中刪除結點單鏈表中刪除結點表頭刪除節點：表頭刪除節點：Remove(1,elem);bool Remove(int i, T& x);當前表：當前表：34刪除節點后：刪除節點后：first2534first2557del=first; /del指向被刪除節點指向被刪除節點x=del-data;first=first-next;delete del;2.3.5單鏈表的操作單鏈表的操作n單鏈表中刪除節點單鏈表中刪除節點刪除表中，表尾節點：刪除表中，表尾節點：在鏈表的中間和尾部刪除結點時，具體步驟為：在鏈表

30、的中間和尾部刪除結點時，具體步驟為： 定位當前位置的前驅節點定位當前位置的前驅節點pre。 將被刪除節點的將被刪除節點的next域賦值給域賦值給pre所指結點的所指結點的next的域。的域。1. 將被刪除節點的數據域賦值給將被刪除節點的數據域賦值給elem，釋放被刪除節點。，釋放被刪除節點。bool Remove(int i, T& x);Remove(2,elem);當前表：當前表：57first25刪除節點后：刪除節點后：first2534342.3.5單鏈表的操作單鏈表的操作n單鏈表中刪除節點單鏈表中刪除節點刪除表中，表尾節點：刪除表中，表尾節點：在鏈表的中間和尾部刪除結點時，具

31、體在鏈表的中間和尾部刪除結點時，具體步驟為：步驟為：定位當前位置的前驅節點定位當前位置的前驅節點pre。將被刪除節點的將被刪除節點的next域賦值給域賦值給pre所指結點的所指結點的next的域。的域。1. 將被刪除節點的數據域賦值給將被刪除節點的數據域賦值給elem，釋放被刪除節點。釋放被刪除節點。bool Remove(int i, T& x); pre=del=first; for(int j=1; jnext; if(NULL=del) break; if(NULL=del) cerr無效的刪除位置無效的刪除位置next=del-next; x=del-data; delete

32、 del;2.3.5單鏈表的操作單鏈表的操作n單鏈表中刪除節點：特殊情況單鏈表中刪除節點：特殊情況u鏈表為空鏈表為空 提示鏈表為空的信息提示鏈表為空的信息u刪除位置非法刪除位置非法 刪除位置小于刪除位置小于1； 刪除位置大于鏈表長度。刪除位置大于鏈表長度。2.3.5單鏈表的操作單鏈表的操作n單鏈表中查找某個元素單鏈表中查找某個元素LinkNode* Search(const T& x);34first255716Search(57);34first255716iterIter-data=57 ?不成立，訪問下一個結點不成立，訪問下一個結點34first255716iter Iter-d

33、ata=57 ?不成立，訪問下一個結點不成立，訪問下一個結點34first255716iter Iter-data=57 ?，返回，返回iter2.3.5單鏈表的操作單鏈表的操作n單鏈表中查找某個元素單鏈表中查找某個元素LinkNode* Search(const T& x);34first255716Search(17);34first255716iterIter-data=17 ?不成立，訪問下一個結點不成立，訪問下一個結點34first255716iter Iter-data=17 ?不成立，訪問下一個結點不成立，訪問下一個結點2.3.5單鏈表的操作單鏈表的操作n單鏈表中查找某個

34、元素單鏈表中查找某個元素LinkNode* Search(const T& x);34first255716Search(17);34first255716iter Iter-data=17 ?不成立，訪不成立，訪問下一個結點問下一個結點34first255716iterIter-data=17 ?不成立，訪不成立，訪問下一個結點問下一個結點在找不到在找不到17的情況下，的情況下，iter指向空。指向空。2.3.5單鏈表的操作單鏈表的操作n單鏈表中查找某個元素單鏈表中查找某個元素LinkNode* Search(const T& x); LinkNode* iter=first

35、; while(iter) if(iter-data=x) return iter; iter=iter-next; return iter;2.3.5 單鏈表的操作單鏈表的操作n返回第返回第i個結點的位置個結點的位置LinkNode* Locate(int i);如果單鏈表中存在第如果單鏈表中存在第i個結點，返回第個結點，返回第i個結點的地址，個結點的地址，否則返回空。否則返回空。34first255716設計一個計數器設計一個計數器j；遍歷鏈表，每訪問一個節點，；遍歷鏈表，每訪問一個節點，j+，直到，直到j=i或或鏈表遍歷完畢。鏈表遍歷完畢。2.3.5 單鏈表的操作單鏈表的操作n返回第返回

36、第i個結點的位置個結點的位置LinkNode* Locate(int i); LinkNode * iter=first; int j=1; if(i1) return NULL; while(NULL!=iter&jnext; j+; return iter;2.3.5 單鏈表的操作單鏈表的操作n更新某個位置的元素更新某個位置的元素void SetData(int i, const T& x)如果第如果第i個結點存在，將它的數據域設置為個結點存在，將它的數據域設置為x。 LinkNode* nd=Locate(i); if(NULL=nd) return; nd-data=x

37、;2.3.5 單鏈表的操作單鏈表的操作n返回某個位置的元素返回某個位置的元素如果第如果第i個結點存在，將它的數據域的值放到個結點存在，將它的數據域的值放到x中，并返回中，并返回真，否則返回假。真，否則返回假。bool List:GetData(int i, T& x)const LinkNode* nd=Locate(i); if(NULL=nd) return false; x=nd-data; return true;2.3.5 單鏈表的操作單鏈表的操作n清空單鏈表清空單鏈表 void MakeEmpty();34first255716操作前：操作前：操作后：操作后：first2.

38、3.5 單鏈表的操作單鏈表的操作n清空單鏈表清空單鏈表 void MakeEmpty();34first255716如果如果first不空，令不空，令iter=first，first=first-next;delete iter;34first5716如果如果first不空，令不空，令iter=first，first=first-next;delete iter;first57162.3.5 單鏈表的操作單鏈表的操作n清空單鏈表清空單鏈表 void MakeEmpty();如果如果first不空，令不空，令iter=first，first=first-next;delete iter;firs

39、t5716first16如果如果first不空，令不空，令iter=first，first=first-next;delete iter;first2.3.5單鏈表的操作單鏈表的操作n清空單鏈表清空單鏈表 LinkNode* pnd=NULL; while(first!=NULL) pnd=first; first=first-next; delete pnd; void MakeEmpty();2.3.5 單鏈表的操作單鏈表的操作n銷毀單鏈表銷毀單鏈表List();templateList:List() MakeEmpty();調用調用MakeEmpty()函數釋放單鏈表所占用的空間。函數釋

40、放單鏈表所占用的空間。2.3.5 單鏈表的操作單鏈表的操作n求單鏈表的長度求單鏈表的長度int Length() const;設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加一。一。34first255716iternum=1；34first255716iternum=2；2.3.5 單鏈表的操作單鏈表的操作n求單鏈表的長度求單鏈表的長度int Length() const;設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加一。一。34first255716iternum=3；34first2

41、55716iternum=4；2.3.5 單鏈表的操作單鏈表的操作n求單鏈表的長度求單鏈表的長度int Length() const;設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加設計一個計數器，遍歷單鏈表，訪問一個結點，計數器加一。一。 LinkNode * iter=first; int num=0; while(iter) num+; iter=iter-next; return num;2.3.5 單鏈表的操作單鏈表的操作n判單鏈表是否為空判單鏈表是否為空bool IsEmpty() constreturn first=NULL;2.3.5 單鏈表的操作單鏈表的操作n復制單鏈表中結

42、點復制單鏈表中結點void CopyList(const List& L);參考單鏈表的尾插法。參考單鏈表的尾插法。 if(L.first=NULL) return; newNode=new LinkNode(L.first-data); first=newNode; iter=L.first-next; rear=newNode; while(iter) newNode=new LinkNode(iter-data); rear-next=newNode; iter=iter-next; rear=rear-next; 2.3.5 單鏈表的操作單鏈表的操作n拷貝構造函數拷貝構造函數

43、first=NULL; CopyList(L);調用調用CopyList函數完成鏈表的初始化。函數完成鏈表的初始化。List(const List& L);2.3.5 單鏈表的操作單鏈表的操作n賦值運算符函數賦值運算符函數首先判斷是否是自復制，如果不是，調用首先判斷是否是自復制，如果不是，調用CopyList函數函數完成鏈表的復制。完成鏈表的復制。 if(this=&L) return *this; MakeEmpty(); CopyList(L); return *this;List& operator=(const List& L);2.3.5 單鏈表的操作

44、單鏈表的操作n對鏈表中的節點進行排序對鏈表中的節點進行排序34first25571625first163457同學們想想怎么辦？同學們想想怎么辦？2.3.6 帶頭結點的單鏈表帶頭結點的單鏈表25first163457不帶頭結點的單鏈表：不帶頭結點的單鏈表：帶頭結點的單鏈表：帶頭結點的單鏈表：25first163457頭結點頭結點表頭表頭表尾表尾表頭表頭表尾表尾頭結點的頭結點的data域可以不存儲任何信息，也可以存放一個特殊域可以不存儲任何信息，也可以存放一個特殊標記或表長。標記或表長。2.3.6 帶頭結點的單鏈表帶頭結點的單鏈表帶頭結點的單鏈表：帶頭結點的單鏈表：25first163457頭結

45、點頭結點表頭表頭表尾表尾帶頭結點的單鏈表為空的情形帶頭結點的單鏈表為空的情形first頭結點頭結點2.3.6帶頭結點的單鏈表帶頭結點的單鏈表帶頭結點的單鏈表：帶頭結點的單鏈表：25first163457頭結點頭結點表頭表頭表尾表尾帶頭結點的單鏈表給表頭節點強加了一個帶頭結點的單鏈表給表頭節點強加了一個“直接前驅直接前驅”，這，這樣做的原因是什么？樣做的原因是什么？當前表：當前表：34first25插入新節點后：插入新節點后： first255734571616newNode：當前表：當前表：34first25插入新節點后：插入新節點后：first25573457newNode：當前表：當前表：

46、34first25插入新節點后：插入新節點后： first2534newNode：first當前表：當前表：first25插入新節點后：插入新節點后：25newNode：回顧：后插法為什么要分情況討論？回顧：后插法為什么要分情況討論？原因：尾插法總是在表尾節點的后面插入節點，空表時沒有表尾節原因：尾插法總是在表尾節點的后面插入節點，空表時沒有表尾節點。點。當前表：當前表：34first插入新節點后：插入新節點后： first34newNode：first當前表：當前表：first25插入新節點后：插入新節點后：25newNode：帶頭結點單鏈表后插法演示。帶頭結點單鏈表后插法演示。2525當前

47、表：當前表：34first插入新節點后：插入新節點后：first255757newNode：3425帶頭節點鏈表空時，頭結點可以看成帶頭節點鏈表空時，頭結點可以看成“表表尾尾”。rear=first;while(rear-next) rear=rear-next;rear-next=newNode;帶頭結點單鏈表后插法。帶頭結點單鏈表后插法。當前表：當前表：34first插入新節點后：插入新節點后：first255757newNode：3425first當前表：當前表：first25插入新節點后：插入新節點后：25newNode：當前表：當前表：34first25插入新節點后：插入新節點后：f

48、irst2534newNode：表頭插入節點：表頭插入節點：Insert(1,34);當前表：當前表：57first25插入新節點后：插入新節點后：first25343457newNode：表中插入節點：表中插入節點：Insert(2,57);表尾插入節點：表尾插入節點：Insert(4,16);當前表：當前表：34first25插入新節點后：插入新節點后： first255734571616newNode：在鏈表中插入元素時，需要找到插入位置的直接前驅節點，但在鏈表中插入元素時，需要找到插入位置的直接前驅節點，但單鏈單鏈表的表頭節點沒有直接前驅表的表頭節點沒有直接前驅，所以必須單獨處理。，所

49、以必須單獨處理。不帶頭結點鏈表插入算不帶頭結點鏈表插入算法回顧法回顧表頭插入節點：表頭插入節點：Insert(1,34);表中插入節點：表中插入節點：Insert(2,57);帶頭結點鏈表插入算法帶頭結點鏈表插入算法當前表：當前表：25first插入新節點后：插入新節點后： first34newNode：2534當前表：當前表：57first插入新節點后：插入新節點后：first253457newNode：3425帶頭節點單鏈表中的頭結點可以看成第一個節點的直接前驅，使得不必要單獨考慮帶頭節點單鏈表中的頭結點可以看成第一個節點的直接前驅，使得不必要單獨考慮在第一個節點處插入節點的情形。在第一個

50、節點處插入節點的情形。表頭插入節點：表頭插入節點：Insert(1,34);帶頭結點鏈表插入算法帶頭結點鏈表插入算法當前表：當前表：25first插入新節點后：插入新節點后： first34newNode：2534 pre=first; for(int j=1; jnext; if(pre=NULL) return false; newNode=new LinkNode(x); newNode-next=pre-next; pre-next=newNode; 當前表：當前表：34刪除節點后：刪除節點后：first2534first2557刪除表頭節點刪除表頭節點:Remove(1,elem);

51、刪除表頭節點刪除表頭節點:Remove(2,elem);當前表：當前表：57first25刪除節點后：刪除節點后：first253434當前表：當前表：34first25刪除節點后：刪除節點后：first2557345716刪除表尾節點刪除表尾節點:Remove(4,elem);在鏈表中刪除元素時，需要找到刪除位置的直接前驅節點，但在鏈表中刪除元素時，需要找到刪除位置的直接前驅節點，但單鏈單鏈表的表頭節點沒有直接前驅表的表頭節點沒有直接前驅，所以必須單獨處理。，所以必須單獨處理。不帶頭結點鏈表刪不帶頭結點鏈表刪除算法回顧除算法回顧當前表：當前表：34刪除節點后：刪除節點后：first2534first2557刪除表頭節點刪除表頭節點:Remove(1,elem);刪除表頭節點刪除表頭節點:Rem