1、線 性 表,2,目 錄,線性表 順序表 單鏈表 線性鏈表的變形 循環(huán)鏈表 雙向鏈表,3,順序表的優(yōu)缺點,【特點】邏輯結構上相鄰的元素其物理結構也相鄰。,查找、刪除、插入算法：與表的大小呈線性的關系。,【缺點】空間的低效利用。（多個線性表公用）,【優(yōu)點】存取操作速度快。,4,1. 鏈表 (Linked List),1、定義,用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。 一種物理存儲單元上非連續(xù)、非順序的存儲結構。 數(shù)據(jù)元素的邏輯順序通過鏈表中指針鏈接次序實現(xiàn)的。,為了表示每個元素ai與其直接后繼ai+1之間的邏輯關系 存儲數(shù)據(jù)元素本身的信息； 存儲指示

2、其直接后繼的信息（即直接后繼的存儲位置）。,5,鏈表的應用,打開windows操作系統(tǒng)里的磁盤整理，看到了什么？ 操作系統(tǒng)存儲空間管理 已分配空間鏈表 空閑空間鏈表 大整數(shù)存儲 多項式存儲,6,鏈式存儲結構中每個數(shù)據(jù)元素占用一個節(jié)點（Node），一個節(jié)點由兩個域組成：,數(shù)據(jù)域（設域名為data）：存儲數(shù)據(jù)元素信息的域； 指針域（設域名為link）：存儲直接后繼存儲位置的域， 指針域中存儲的信息稱作指針或鏈。,鏈表節(jié)點結構,7,例：設有線性表（A,B,C,D,E,F），該線性表的鏈表形式如下：,first,last,鏈表邏輯結構示意圖,（1）數(shù)據(jù)域：存放數(shù)據(jù)元素A、B、C、D、E、F的域； （2

3、）指針域：存放指針的域； （3）節(jié)點：包含數(shù)據(jù)域值和指針域值； （4）第一個節(jié)點（首元節(jié)點）：節(jié)點A；尾節(jié)點：節(jié)點F; （5）A節(jié)點稱為B節(jié)點的直接前驅， B節(jié)點稱為A節(jié)點的直接后繼； （6）first稱為表頭指針；last稱為鏈尾指針； （7）最后一個節(jié)點的指針不指向任何節(jié)點，稱為空指針（NULL）,鏈表中常用的幾個概念,8,鏈表中每個節(jié)點可以包含若干個數(shù)據(jù)域和指針域。,根據(jù)指針的數(shù)量和性質的不同，可以將鏈表分為以下類型:,按指針數(shù)量分類,按指針性質分類,單鏈表只有一個指針域,多鏈表有多個指針域（多為雙向鏈表）,普通鏈表（非循環(huán)鏈表）,循環(huán)鏈表,鏈表的分類,9,1、定義：若鏈表中的每個節(jié)點只

4、有一個指針域。,2、單鏈表的邏輯狀態(tài)和物理狀態(tài),數(shù)據(jù)元素之間的相對關系是由鏈表中的指針域所指示的； 單鏈表中的節(jié)點之間由鏈建立起來的邏輯順序必須和線性表中相應的數(shù)據(jù)元素的順序相一致； 數(shù)據(jù)元素在內存中以任意次序存放。,單鏈表中必須指出第一個節(jié)點的存儲地址，所以需要設立一個特殊的指針，稱為頭指針。整個鏈表的存取都是從頭指針開始進行的。,2. 單鏈表（線性鏈表）,10,單鏈表的存儲映像,free,(a) 可利用存儲空間,a0,a2,a1,a3,free,first,(b) 經(jīng)過一段運行后的單鏈表結構,11,例：設有線性表（ a1，a2，a3，a4，a5 ，a6 ），采用單鏈表進行存儲，其物理狀態(tài)如

5、下圖所示:,58,first,單鏈表存儲狀態(tài)示例,12,單鏈表的邏輯結構示意圖,a,b,c,d,e,NULL,first,鏈表中每個節(jié)點代表一個元素； 每個節(jié)點包含一個指針，指向下一個節(jié)點； 最后一個節(jié)點的指針域是NULL。,13,3. 單鏈表的類定義,使用面向對象方法，要把數(shù)據(jù)與操作一起定義和封裝，用多個類表達一個單鏈表。 鏈表結點(ListNode)類 鏈表(List)類 書上前三種設計方法：P54-P55 復合類：利用friend 嵌套類 基類-派生類,14,struct ListNode /鏈表結點類 int data; ListNode * link; class List /鏈表類

6、, 直接使用鏈表結點類的數(shù)據(jù)和操作 private: ListNode *first; /表頭指針 /鏈表中的結點屬于鏈表私有，別人無法訪問,本書采用：結構方式,15,指針的基本操作,p=q,p=q-link,p=p-link,p-link=q,p-link=q-link,p,q,q,16,（1）單鏈表的插入,第一種情況：在鏈表最前端插入,（插入前） （插入后）,newnode-link = first ; first = newnode;,17,單鏈表的插入（續(xù)1）,第二種情況：在鏈表中間插入,(插入前) (插入后),newnode-link = current-link ; current

7、-link = newnode;,18,單鏈表的插入（續(xù)2）,第三種情況：在鏈表末尾插入,(插入前) (插入后),newnode-link = current-link ; current-link = newnode; 與中間插入相同！,19,單鏈表的插入算法,bool List:Insert(int i, int x) /將新元素 x 插入到第 i 個結點之后。i 從1開始， /i = 0 表示插入到首元結點之前。 if (first = NULL | i = 0) /空表或首元結點前 LinkNode *newNode = new LinkNode(x); if(newNode=NULL

8、) . /建立一個新結點 newNode-link = first; first = newNode; /新結點成為首結點 else /否則，尋找插入位置 LinkNode *current = first;,20,for(int k=1; klink; if (current = NULL) /無效位置 cerr link = current-link; current-link = newNode; return true; ,21,（2）單鏈表的刪除,第一種情況: 刪除表中第一個元素 第二種情況: 刪除表中或表尾元素,在單鏈表中刪除含ai的結點,ai-1,ai-1,ai,ai,ai+1,

9、ai+1,p,q,刪除前,刪除后,22,刪除節(jié)點：Remove(1, x),p = first; first = first-link; delete p;,p,刪除表頭節(jié)點,23,刪除節(jié)點：Remove (3, x),a,b,d,e,NULL,first,c,第1步，到達要刪除節(jié)點的前一個節(jié)點 。,c,c,q,刪除非表頭節(jié)點,24,刪除節(jié)點：Remove (3, x),第2步，保存指向待刪節(jié)點的指針。,p = q-link;,q,a,b,c,d,e,NULL,first,p,25,刪除節(jié)點：Remove (3, x),第3步，改變前節(jié)點的指針域，使其指向待刪節(jié)點的后一節(jié)點。,q-link =

10、 p-link; delete p;,q,a,b,c,d,e,NULL,first,p,?,26,單鏈表的刪除算法,bool List:Remove (int i, int ,27,del = current-link; /刪中間/尾結點 current-link = del-link; x = del-data; delete del; /取出被刪結點數(shù)據(jù) return true; 單鏈表的插入和刪除算法 優(yōu)點：不需要移動元素，只需修改結點指針，比順序表方便 缺點1：情況復雜，要專門討論空表和在表頭插入的特殊情形。 缺點2：尋找插入或刪除位置只能沿著鏈順序檢測。,28,解決方法：帶表頭結點的

11、單鏈表,表頭結點位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭。 設置表頭結點的目的：是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實現(xiàn)。 在鏈表頭部執(zhí)行插入和刪除元素的操作與在鏈表中部一樣，有助于簡化代碼。,非空表 空表,29,插入新結點的2種情況,newnode-link = p-link; p-link = newnode;,30,q = p-link; p-link = q-link; delete q;,刪除已有結點的2種情況,(非空表）,(空表）,31,4. 單鏈表的模板類,類模板將類的數(shù)據(jù)成員和成員函數(shù)設計得更完整、更靈活。 類模板更易于復用。 在單鏈表的類模板定義中，增加了表頭結點。,32

12、,單鏈表結點定義,template struct LinkNode T data; LinkNode *link; LinkNode(LinkNode *ptr = NULL) link = ptr; LinkNode(const T ,33,template class List /單鏈表類定義, 不用繼承也可實現(xiàn) protected: LinkNode * first; /表頭指針（頭結點） public: List() first = new LinkNode; /構造函數(shù) List(T x) first = new LinkNode(x); List( List/計算鏈表的長度,單鏈表

13、模板類定義,34,LinkNode *getHead() const return first; /返回頭結點的地址 LinkNode *Search(T x);/搜索含x元素 LinkNode *Locate(int i);/定位第i個元素 T *getData(int i, T/刪除第i個元素,單鏈表模板類定義（續(xù)1）,35,單鏈表模板類定義（續(xù)2）,bool IsEmpty() const /判表空否 return first-link = NULL ? true : false; bool IsFull() const return false; void Sort(); /排序 vo

14、id input(); void output(); List ,36,（1）復制構造函數(shù),template List:List(List ,37,（2）鏈表置空算法（保留表頭結點）,template void List:makeEmpty() LinkNode *q; while (first-link != NULL) q = first-link; /保存被刪結點 first-link = q-link; /從鏈上摘下該結點 delete q; /刪除 ,時間復雜度： (n),38,39,template int List : Length ( ) const ListNode *p =

15、 first-link; /檢測指針 p 指示第一號結點 int count = 0; while ( p != NULL ) /逐個結點檢測 p = p-link; count+; return count; ,（3）求單鏈表的長度,時間復雜度： (n),40,41,（4）單鏈表的搜索,template LinkNode * List:Search(T x) /在表中搜索含數(shù)據(jù)x的結點, 搜索成功時函數(shù)返 /該結點地址; 否則返回NULL。 LinkNode * current = first-link; while ( current != NULL ,時間復雜度： (n),42,（5）單

16、鏈表的定位,template LinkNode * List:Locate ( int i ) /函數(shù)返回表中第 i 個元素的地址。若i * current = first; int k = 0; while ( current != NULL ,時間復雜度： (i),43,（6）取結點數(shù)據(jù),template bool List:getData(int i, T ,44,設置結點數(shù)據(jù),template void List:setData(int i, T ,45,（7）單鏈表的輸出,template void List:output() LinkNode *current = first-li

17、nk; while (current) cout data link; ,時間復雜度： (n),46,（8）賦值操作重載,template List ,時間復雜度： (L.Length(),47,（9）單鏈表的插入算法,template bool List:Insert (int i, T x) /將新元素 x 插入在鏈表中第 i 個結點之后 LinkNode *current = Locate(i); if (current = NULL) return false;/無插入位置 LinkNode *newNode = new LinkNode(x); /創(chuàng)建新結點 if(newNode=N

18、ULL) .; return false; newNode-link = current-link; /鏈入 current-link = newNode; return true; /插入成功 ,時間復雜度： (i),48,（10）單鏈表的刪除算法,template bool List:Remove (int i, T ,時間復雜度： (i),49,（11）前插法建立單鏈表,從一個空表開始，重復讀入數(shù)據(jù)： 生成新結點 將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中 將該新結點插入到鏈表的前端 直到讀入結束符為止。,50,template void inputFront (T endTag) LinkNod

19、e *newNode ; T val; makeEmpty(); /先清空 cin val; while (val != endTag) newNode = new LinkNode(val); if(newNode=NULL) . newNode-link = first-link; /插在表前端 first-link = newNode; cin val; ,51,考慮：如何在(1)的時間完成插入,增加一個變量 LinkNode * last；用于跟蹤鏈表的最后一個元素,52,（12）后插法建立單鏈表,每次將新結點加在插到鏈表的表尾； 設置一個尾指針 last，總是指向表中最后一個結點，新

20、結點插在它的后面； 尾指針 last 初始時置為指向表頭結點地址。,53,template void inputRear ( T endTag, List /表收尾 ,54,單鏈表與順序表時間復雜度對比,55,1、 華中科技大學考研題：,【填空題】設單鏈表的節(jié)點結構為（data,next)，next為指針域。已知指針px指向單鏈表中data為x的節(jié)點，指針py指向data為y的節(jié)點，若將y插入節(jié)點x之后，則需執(zhí)行以下語句：,px-next=py;,課堂練習,56,2、武漢大學考研題：,【選擇題】非空循環(huán)鏈表head的尾節(jié)點p滿足： A、p-link=head B、p-link=NULL C、p=NULL D、p=head,3、 上海交大考研題：,【算法設計】假設有兩個按元素遞減有序排列的線性表A和B，均以單鏈表作存儲結構。請