第二章線性表(2)

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

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

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

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

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

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

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

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

9、類是類是包含（具包含（具體講是聚合）的關(guān)系體講是聚合）的關(guān)系。 uListNode中的數(shù)據(jù)域和鏈域是中的數(shù)據(jù)域和鏈域是public成員，成員，List類可以通過對象類可以通過對象直接訪問它們。直接訪問它們。u鏈表中的結(jié)點屬于鏈表私有，別鏈表中的結(jié)點屬于鏈表私有，別人無法訪問。人無法訪問。2.3.3單鏈表的實現(xiàn)策略單鏈表的實現(xiàn)策略n單鏈表分為單鏈表分為不帶頭結(jié)點單鏈表不帶頭結(jié)點單鏈表和和帶頭結(jié)點帶頭結(jié)點單鏈表單鏈表兩種，兩種，本課件先介紹不帶頭結(jié)點單本課件先介紹不帶頭結(jié)點單鏈表鏈表。2.3.4單鏈表模板的定義單鏈表模板的定義n結(jié)點模板的定義結(jié)點模板的定義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單鏈表模板的定義單鏈表模板的定義構(gòu)造函數(shù)，拷貝構(gòu)構(gòu)造函數(shù)，拷貝構(gòu)造函數(shù)，賦值運算造函數(shù)，賦值運算符函數(shù)，析構(gòu)函數(shù)符函數(shù)，析構(gòu)函數(shù)單鏈表的增刪查改單鏈表的增刪查改清空復(fù)制鏈表節(jié)點清空復(fù)制鏈表節(jié)點鏈表自身狀態(tài)鏈表自身狀態(tài)2.3.5 單鏈表的操作單鏈表的操作n創(chuàng)建空鏈表創(chuàng)建空鏈表L

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

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

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

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

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

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

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

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

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

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

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

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

25、NodenewNode-next=pre-next;pre-next=newNode;2.3.5單鏈表的操作單鏈表的操作n單鏈表中插入節(jié)點單鏈表中插入節(jié)點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; 在鏈表的中間和尾部插入結(jié)點時，在鏈表的中間和尾部插入結(jié)點時，具體步驟

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

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

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

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

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

31、體在鏈表的中間和尾部刪除結(jié)點時，具體步驟為：步驟為：定位當(dāng)前位置的前驅(qū)節(jié)點定位當(dāng)前位置的前驅(qū)節(jié)點pre。將被刪除節(jié)點的將被刪除節(jié)點的next域賦值給域賦值給pre所指結(jié)點的所指結(jié)點的next的域。的域。1. 將被刪除節(jié)點的數(shù)據(jù)域賦值給將被刪除節(jié)點的數(shù)據(jù)域賦值給elem，釋放被刪除節(jié)點。釋放被刪除節(jié)點。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單鏈表中刪除節(jié)點：特殊情況單鏈表中刪除節(jié)點：特殊情況u鏈表為空鏈表為空 提示鏈表為空的信息提示鏈表為空的信息u刪除位置非法刪除位置非法 刪除位置小于刪除位置小于1； 刪除位置大于鏈表長度。刪除位置大于鏈表長度。2.3.5單鏈表的操作單鏈表的操作n單鏈表中查找某個元素單鏈表中查找某個元素LinkNode* Search(const T& x);34first255716Search(57);34first255716iterIter-data=57 ?不成立，訪問下一個結(jié)點不成立，訪問下一個結(jié)點34first255716iter Iter-d

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

34、元素單鏈表中查找某個元素LinkNode* Search(const T& x);34first255716Search(17);34first255716iter Iter-data=17 ?不成立，訪不成立，訪問下一個結(jié)點問下一個結(jié)點34first255716iterIter-data=17 ?不成立，訪不成立，訪問下一個結(jié)點問下一個結(jié)點在找不到在找不到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個結(jié)點的位置個結(jié)點的位置LinkNode* Locate(int i);如果單鏈表中存在第如果單鏈表中存在第i個結(jié)點，返回第個結(jié)點，返回第i個結(jié)點的地址，個結(jié)點的地址，否則返回空。否則返回空。34first255716設(shè)計一個計數(shù)器設(shè)計一個計數(shù)器j；遍歷鏈表，每訪問一個節(jié)點，；遍歷鏈表，每訪問一個節(jié)點，j+，直到，直到j(luò)=i或或鏈表遍歷完畢。鏈表遍歷完畢。2.3.5 單鏈表的操作單鏈表的操作n返回第返回

36、第i個結(jié)點的位置個結(jié)點的位置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個結(jié)點存在，將它的數(shù)據(jù)域設(shè)置為個結(jié)點存在，將它的數(shù)據(jù)域設(shè)置為x。 LinkNode* nd=Locate(i); if(NULL=nd) return; nd-data=x

37、;2.3.5 單鏈表的操作單鏈表的操作n返回某個位置的元素返回某個位置的元素如果第如果第i個結(jié)點存在，將它的數(shù)據(jù)域的值放到個結(jié)點存在，將它的數(shù)據(jù)域的值放到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();調(diào)用調(diào)用MakeEmpty()函數(shù)釋放單鏈表所占用的空間。函數(shù)釋

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

41、55716iternum=4；2.3.5 單鏈表的操作單鏈表的操作n求單鏈表的長度求單鏈表的長度int Length() const;設(shè)計一個計數(shù)器，遍歷單鏈表，訪問一個結(jié)點，計數(shù)器加設(shè)計一個計數(shù)器，遍歷單鏈表，訪問一個結(jié)點，計數(shù)器加一。一。 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復(fù)制單鏈表中結(jié)

42、點復(fù)制單鏈表中結(jié)點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拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)

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

44、單鏈表的操作n對鏈表中的節(jié)點進(jìn)行排序?qū)︽湵碇械墓?jié)點進(jìn)行排序34first25571625first163457同學(xué)們想想怎么辦？同學(xué)們想想怎么辦？2.3.6 帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表25first163457不帶頭結(jié)點的單鏈表：不帶頭結(jié)點的單鏈表：帶頭結(jié)點的單鏈表：帶頭結(jié)點的單鏈表：25first163457頭結(jié)點頭結(jié)點表頭表頭表尾表尾表頭表頭表尾表尾頭結(jié)點的頭結(jié)點的data域可以不存儲任何信息，也可以存放一個特殊域可以不存儲任何信息，也可以存放一個特殊標(biāo)記或表長。標(biāo)記或表長。2.3.6 帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表：帶頭結(jié)點的單鏈表：25first163457頭結(jié)

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

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

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

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

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

50、節(jié)點處插入節(jié)點的情形。表頭插入節(jié)點：表頭插入節(jié)點：Insert(1,34);帶頭結(jié)點鏈表插入算法帶頭結(jié)點鏈表插入算法當(dāng)前表：當(dāng)前表：25first插入新節(jié)點后：插入新節(jié)點后： 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; 當(dāng)前表：當(dāng)前表：34刪除節(jié)點后：刪除節(jié)點后：first2534first2557刪除表頭節(jié)點刪除表頭節(jié)點:Remove(1,elem);

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