第2章專題3線性表的鏈接存儲

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社專題專題3：線性表的鏈接存儲結(jié)構(gòu)：線性表的鏈接存儲結(jié)構(gòu)123單鏈表的存儲方法單鏈表的存儲方法單鏈表的實現(xiàn)單鏈表的實現(xiàn)雙鏈表的存儲方法雙鏈表的存儲方法45雙鏈表基本操作雙鏈表基本操作的實現(xiàn)語句的實現(xiàn)語句循環(huán)鏈表的存儲方法循環(huán)鏈表的存儲方法6循環(huán)鏈表基本操作的實現(xiàn)語循環(huán)鏈表基本操作的實現(xiàn)語句句數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表：單鏈表：線性表的鏈接存儲結(jié)構(gòu)。線性表的鏈接存儲結(jié)構(gòu)。存儲思想：存儲思想：用一組用一組任意任意的存儲單元存放線性表的元素。的存儲單元存放線性表的元素。2.3 線性表

2、的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表靜態(tài)存儲分配靜態(tài)存儲分配 順序表順序表事先確定容量事先確定容量 鏈鏈 表表動態(tài)存儲分配動態(tài)存儲分配 運行時分配空間運行時分配空間 連續(xù)連續(xù)不連續(xù)不連續(xù)零散分布零散分布數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社0200020803000325存儲特點：存儲特點：1. 邏輯次序和物理次序邏輯次序和物理次序 不一定相同。不一定相同。 2.元素之間的邏輯關(guān)系元素之間的邏輯關(guān)系 用指針表示。用指針表示。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)例：例：(a1, a2 ,a3, a4)的存儲示意圖的存儲

3、示意圖單鏈表單鏈表 a10200 a20325 a30300 a4 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300 a4 結(jié)點結(jié)點數(shù)據(jù)域數(shù)據(jù)域指針域指針域單鏈表是由若干結(jié)點構(gòu)成的；單鏈表是由若干結(jié)點構(gòu)成的；單鏈表的結(jié)點只有一個指針域。單鏈表的結(jié)點只有一個指針域。data：存儲數(shù)據(jù)元素存儲數(shù)據(jù)元素next：存儲指向后繼結(jié)點的地址存儲指向后繼結(jié)點的地址 data next單鏈表的結(jié)點結(jié)構(gòu)：單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域數(shù)據(jù)域指針域指針域

4、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template struct Node DataType data; Node *next; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表 data next單鏈表的結(jié)點結(jié)構(gòu)：單鏈表的結(jié)點結(jié)構(gòu)：如何申請一個結(jié)點如何申請一個結(jié)點？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社s=new Node ;template struct Node DataType data; Node *next; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表 data

5、 next單鏈表的結(jié)點結(jié)構(gòu)：單鏈表的結(jié)點結(jié)構(gòu)： sNode數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社s=new Node ;2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表 data next sNode如何引用數(shù)據(jù)元素如何引用數(shù)據(jù)元素？s-data ;*s.data ;data如何引用指針域如何引用指針域？nexts-next;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300

6、 a4 firsta1a2an非空表非空表first=NULL空表空表重點重點是能夠表示是能夠表示數(shù)據(jù)元素之間的邏輯數(shù)據(jù)元素之間的邏輯關(guān)系，所以，將實際存儲地址抽象。關(guān)系，所以，將實際存儲地址抽象。什么是存儲結(jié)構(gòu)什么是存儲結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表頭指針：頭指針：指向第一個結(jié)點的地址。指向第一個結(jié)點的地址。尾標志：尾標志：終端結(jié)點的

7、指針域為空。終端結(jié)點的指針域為空。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不統(tǒng)一，缺點？空表和非空表不統(tǒng)一，缺點？如何將空表與非空表統(tǒng)一如何將空表與非空表統(tǒng)一？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社頭結(jié)點：頭結(jié)點：在在單鏈表的第以一個元素結(jié)點之前附設(shè)一個單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便

8、空表和非空表處理統(tǒng)一。類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表單鏈表非空表非空表firsta1a2an空表空表first數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template class LinkList public: LinkList( )( )； LinkList( (DataType a , int n) ); LinkList( )( ); int Length( )( ); DataType Get( (int i) ); int Locate( (DataType x) ); v

9、oid Insert( (int i, DataType x) ); DataType Delete( (int i) ); void PrintList( )( ); private: Node *first; ;單鏈表類的聲明單鏈表類的聲明2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)和線性表和線性表ADT定義的關(guān)系？定義的關(guān)系？和順序表的類定義的關(guān)系？和順序表的類定義的關(guān)系？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)遍歷操作遍歷操作操作接口：操作接口： void PrintList( ); v核心操作（關(guān)鍵操作）：核心操作

10、（關(guān)鍵操作）：工作指針后移工作指針后移。從頭結(jié)點。從頭結(jié)點（或開始結(jié)點）出發(fā)，通過工作指針的反復后移而將（或開始結(jié)點）出發(fā)，通過工作指針的反復后移而將整個單鏈表整個單鏈表“審視審視”一遍的方法稱為一遍的方法稱為掃描掃描（或遍歷）（或遍歷）。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1pa2panaippp數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)遍歷操作遍歷操作操作接口：操作接口： void PrintList( ); 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)template void Lin

11、kList : PrintList( ) p = first-next; while (p != NULL) cout data; p = p-next; p+能否完成指針后移？能否完成指針后移？a1a2pp+p-next數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)求長度求長度操作接口：操作接口： int Length( )2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1a2anaip1. 工作指針工作指針p初始化初始化; 累加器累加器count初始化初始化;2. 重復執(zhí)行下述操作，直到重復執(zhí)行下述操作，直到p為空：為

12、空： 2.1 工作指針工作指針p后移后移; 2.2 count+;3. 返回累加器返回累加器count的值；的值；pcount =1pcount =2pcount =ipcount =n數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template int LinkList : Length( ) p = first-next; count = 0; while (p != NULL) p = p-next; count+; return count; /注意注意count的初始化和返回值之間的關(guān)系的初始化和返回值之間的關(guān)系2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接

13、存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)求長度求長度算法描述算法描述C+描述描述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)按位查找按位查找操作接口：操作接口： DataType Get(int i);2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1a2anaipp查找失敗查找失敗pcount =1pcount =2p查找成功查找成功count =i數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)按位查找按位查找2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法

14、描述算法描述C+描述描述template DataType LinkList : Get(int i) p = first-next; count = 1; /初始化工作指針和累加器初始化工作指針和累加器 while (p != NULL & count next; /工作指針工作指針p后移后移 count+; if (p = NULL) throw 位置位置; else return p-data;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template int LinkList : Locate(DataType x) p = first-next;

15、count = 1; while (p != NULL) if (p-data = x) return count; /查找成功，返回序號查找成功，返回序號 p = p-next; count+; return 0; /退出循環(huán)表明查找失敗退出循環(huán)表明查找失敗2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)按值查找按值查找算法描述算法描述C+描述描述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)插入插入操作接口：操作接口： void Insert(int i, DataType x); 2.3 線性表的鏈接存儲

16、結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)如何實現(xiàn)結(jié)點如何實現(xiàn)結(jié)點ai-1、x和和ai之間邏輯關(guān)系的變化？之間邏輯關(guān)系的變化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社注意分析注意分析邊界邊界情況情況表頭、表尾。表頭、表尾。 單鏈表的實現(xiàn)單鏈表的實現(xiàn)插入插入2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1anaipxs算法描述：算法描述：s=new Node; s-data=x;s-next=p-nex

17、t; p-next=s;pxs由于單鏈表帶頭結(jié)點，由于單鏈表帶頭結(jié)點，表頭、表中、表尾三種表頭、表中、表尾三種情況的操作語句一致。情況的操作語句一致。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社算法描述算法描述偽代碼偽代碼 1. 工作指針工作指針p初始化；初始化； 2. 查找第查找第i-1個結(jié)點并使工作指針個結(jié)點并使工作指針p指向該結(jié)點；指向該結(jié)點； 3. 若查找不成功，則插入位置不合理，拋出插入位置異常；若查找不成功，則插入位置不合理，拋出插入位置異常； 否則，否則， 3.1 生成一個元素值為生成一個元素值為x的新結(jié)點的新結(jié)點s； 3.2 將新結(jié)點將新結(jié)點s插入到

18、結(jié)點插入到結(jié)點p之后；之后；2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)插入插入數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社 template void LinkList : Insert(int i, DataType x) p = first ; count = 0; /工作指針工作指針p應指向頭結(jié)點應指向頭結(jié)點 while (p != NULL & count next; count+; if (p = NULL) throw 位置位置; /沒有找到第沒有找到第i 1個結(jié)點個結(jié)點 else s = new Node

19、; s-data = x; /申請一個結(jié)點申請一個結(jié)點s s-next = p-next; p-next = s; /結(jié)點結(jié)點s插入結(jié)點插入結(jié)點p之后之后 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)插入插入基本語句？時間復雜度？基本語句？時間復雜度？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點插在頭結(jié)點的后面將待插入結(jié)點插在頭結(jié)點的后面 。算法描述：算法描述：first=new Nod

20、e; first-next=NULL; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組數(shù)組a3512243342初始化初始化first數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點插在頭結(jié)點的后面將待插入結(jié)點插在頭結(jié)點的后面 。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組數(shù)組a3512243342算法描述：算法描述：s=new Node; s-data=a0;s-next=first-nex

21、t;first-next=s; 插入第一個元素結(jié)點插入第一個元素結(jié)點first35s數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)頭插法：頭插法：將待插入結(jié)點插在頭結(jié)點的后面將待插入結(jié)點插在頭結(jié)點的后面 。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組數(shù)組a3512243342算法描述：算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s; 依次插入每一個結(jié)點依次插入每一個結(jié)點

22、12sfirst35數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template LinkList : LinkList(DataType a , int n) first = new Node; first-next = NULL; for (i = 0; i data = ai; s-next = first-next; first-next = s; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)頭插法的頭插法的C+描述：描述：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社尾插法：尾插

23、法：將待插入結(jié)點插在終端結(jié)點的后面。將待插入結(jié)點插在終端結(jié)點的后面。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：first=new Node; rear=first;數(shù)組數(shù)組a3512243342初始化初始化firstrear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社尾插法：尾插法：將待插入結(jié)點插在終端結(jié)點的后面。將待插入結(jié)點插在終端結(jié)點的后面。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的

24、實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;數(shù)組數(shù)組a3512243342插入第一個元素結(jié)點插入第一個元素結(jié)點firstrear35srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社尾插法：尾插法：將待插入結(jié)點插在終端結(jié)點的后面。將待插入結(jié)點插在終端結(jié)點的后面。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(D

25、ataType a , int n)算法描述：算法描述：s=new Node; s-data=a1;rear-next=s;rear=s;數(shù)組數(shù)組a3512243342依次插入每一個結(jié)點依次插入每一個結(jié)點first35rear12srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社尾插法：尾插法：將待插入結(jié)點插在終端結(jié)點的后面。將待插入結(jié)點插在終端結(jié)點的后面。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：rear-n

26、ext=NULL;數(shù)組數(shù)組a3512243342最后一個結(jié)點插入后最后一個結(jié)點插入后first3542srear數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template LinkList : LinkList(DataType a , int n) first = new Node; /生成頭結(jié)點生成頭結(jié)點 r = first; /尾指針初始化尾指針初始化 for (i = 0; i data = ai; r-next = s; r = s; r-next = NULL; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)構(gòu)造函數(shù)

27、構(gòu)造函數(shù)尾插法的尾插法的C+描述：描述：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)刪除刪除操作接口：操作接口： DataType Delete(int i); 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)p如何實現(xiàn)結(jié)點如何實現(xiàn)結(jié)點ai-1和和ai之間邏輯關(guān)系的變化？之間邏輯關(guān)系的變化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;q數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)刪除刪除2

28、.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;注意分析注意分析邊界邊界情況情況表頭、表尾。表頭、表尾。 pqpq表尾的特殊情況：表尾的特殊情況：雖然被刪結(jié)點不存在，雖然被刪結(jié)點不存在，但其前驅(qū)結(jié)點卻存在。但其前驅(qū)結(jié)點卻存在。 p-next=NULLfirsta1ana2數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社算法描述算法描述偽代碼偽代碼 1.工作指針工作指針p初始化；初始化； 2. 查找第查找第i-1個結(jié)點并使工作指針個結(jié)點并使工作指針p指向該結(jié)點

29、；指向該結(jié)點； 3. 若若p不存在或不存在或p不存在后繼結(jié)點，則拋出位置異常；不存在后繼結(jié)點，則拋出位置異常； 否則，否則， 3.1 暫存被刪結(jié)點和被刪元素值；暫存被刪結(jié)點和被刪元素值； 3.2 摘鏈，將結(jié)點摘鏈，將結(jié)點p的后繼結(jié)點從鏈表上摘下；的后繼結(jié)點從鏈表上摘下； 3.3 釋放被刪結(jié)點；釋放被刪結(jié)點； 3.4 返回被刪元素值；返回被刪元素值； 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)刪除刪除數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template DataType LinkList : Delete(int i)

30、p = first ; count = 0; while (p != NULL & count next; count+; if (p = NULL | p-next = NULL) throw 位置位置; else q = p-next; x = q-data; p-next = q-next; delete q; return x; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)單鏈表的實現(xiàn)刪除刪除數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)析構(gòu)函數(shù)析構(gòu)函數(shù)析構(gòu)函數(shù)將單鏈表中所有結(jié)點的存儲空間釋放。析構(gòu)函數(shù)

31、將單鏈表中所有結(jié)點的存儲空間釋放。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)操作接口：操作接口：LinkList( );firsta1a2anaiq算法描述：算法描述：q = first; first = first-next;delete q;first注意：保證鏈表未處理的部分不斷開注意：保證鏈表未處理的部分不斷開 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社單鏈表的實現(xiàn)單鏈表的實現(xiàn)析構(gòu)函數(shù)析構(gòu)函數(shù)template LinkList : LinkList( ) while (first != NULL) q = first; first = f

32、irst-next; delete q; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述：算法描述：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社啟示：算法設(shè)計的一般過程啟示：算法設(shè)計的一般過程算法設(shè)計的一般步驟：算法設(shè)計的一般步驟：第一步：確定第一步：確定入口入口（已知條件）、（已知條件）、出口出口（結(jié)果）；（結(jié)果）；第二步：根據(jù)一個小實例畫出第二步：根據(jù)一個小實例畫出示意圖示意圖；第三步：第三步： 正向思維正向思維：選定一個思考問題的起點，逐：選定一個思考問題的起點，逐步提出問題、解決問題；步提出問題、解決問題； 逆向思維逆向思維：從結(jié)論出發(fā)分

33、：從結(jié)論出發(fā)分析為達到這個結(jié)論應該先有什么；析為達到這個結(jié)論應該先有什么； 正逆結(jié)合正逆結(jié)合；第四步：寫出第四步：寫出頂層頂層較抽象算法，分析較抽象算法，分析邊界邊界情況；情況；第五步：第五步：驗證驗證第四步的算法；第四步的算法；第六步：寫出第六步：寫出具體具體算法；算法；第七步：第七步：進一步進一步驗證，手工運行。驗證，手工運行。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社循環(huán)鏈表循環(huán)鏈表firsta1ai-1anaip從單鏈表中某結(jié)點從單鏈表中某結(jié)點p出發(fā)如何找到其前驅(qū)？出發(fā)如何找到其前驅(qū)？將單鏈表的首尾相接，將終端結(jié)點的指針域由空指針將單鏈表的首尾相接，將終端結(jié)

34、點的指針域由空指針改為指向頭結(jié)點，構(gòu)成改為指向頭結(jié)點，構(gòu)成單循環(huán)鏈表單循環(huán)鏈表，簡稱，簡稱循環(huán)鏈表循環(huán)鏈表。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社循環(huán)鏈表循環(huán)鏈表空表和非空表的處理一致空表和非空表的處理一致附設(shè)頭結(jié)點附設(shè)頭結(jié)點first空循環(huán)鏈表空循環(huán)鏈表firsta1ai-1anai非空循環(huán)鏈表非空循環(huán)鏈表2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社firsta1ai-1anai循環(huán)鏈表循環(huán)鏈表插入插入xspxspx

35、sp算法描述：算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社 template void LinkList :Insert(int i, DataType x) p = first ; count = 0; while (p != first & count next; count+; if (p = NULL) throw 位置位置; else s = new Node; s-data = x; s-

36、next = p-next; p-next = s; 循環(huán)鏈表循環(huán)鏈表插入插入與單鏈表的插入操作的差別？與單鏈表的插入操作的差別？2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社循環(huán)條件：循環(huán)條件：p != NULLp != firstp-next != NULLp-next != first循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表中沒有明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán)2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社

37、如何查找開始結(jié)點和終端結(jié)點？如何查找開始結(jié)點和終端結(jié)點？循環(huán)鏈表循環(huán)鏈表firsta1ai-1anai開始結(jié)點：開始結(jié)點：first-next 終端結(jié)點：將單鏈表掃描一遍，時間為終端結(jié)點：將單鏈表掃描一遍，時間為O(n)2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社reara1ai-1anai開始結(jié)點：開始結(jié)點：rear-next-next終端結(jié)點：終端結(jié)點：rear循環(huán)鏈表循環(huán)鏈表帶尾指針的循環(huán)鏈表帶尾指針的循環(huán)鏈表一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲結(jié)構(gòu)的

38、運算是否方便，時間性能是否提高。結(jié)構(gòu)的運算是否方便，時間性能是否提高。 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社雙鏈表雙鏈表如何求結(jié)點如何求結(jié)點p的直接前驅(qū)，時間性能？的直接前驅(qū)，時間性能？firsta1ai-1anaip為什么可以快速求得結(jié)點為什么可以快速求得結(jié)點p的后繼？的后繼？如何快速求得結(jié)點如何快速求得結(jié)點p的前驅(qū)？的前驅(qū)？2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社雙鏈表：雙鏈表：在在單鏈表的每個結(jié)點中再設(shè)置一

39、個指向其前單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)結(jié)點的指針域驅(qū)結(jié)點的指針域。雙鏈表雙鏈表結(jié)點結(jié)構(gòu)：結(jié)點結(jié)構(gòu)：priordatanextdata：數(shù)據(jù)域，存儲數(shù)據(jù)元素；數(shù)據(jù)域，存儲數(shù)據(jù)元素；prior：指針域，存儲該結(jié)點的前趨結(jié)點地址；指針域，存儲該結(jié)點的前趨結(jié)點地址；next：指針域，存儲該結(jié)點的后繼結(jié)點地址。指針域，存儲該結(jié)點的后繼結(jié)點地址。2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社template struct DulNode DataType data; DulNode *prior, *next;

40、雙鏈表雙鏈表啟示？啟示？時空權(quán)衡時空權(quán)衡空間換取時間空間換取時間priordatanext定義結(jié)點結(jié)構(gòu)：定義結(jié)點結(jié)構(gòu)：2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社雙鏈表的操作雙鏈表的操作插入插入s-prior=p; s-next=p-next;p-next-prior=s;p-next=s; ai-1ai操作接口：操作接口： void Insert(DulNode *p, DataType x); pxs注意指針修改的注意指針修改的相對相對順序順序2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)

41、據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社雙鏈表的操作雙鏈表的操作刪除刪除( (p-prior) )-next=p-next; ( (p-next) )-prior=p-prior; 操作接口：操作接口： DataType Delete(DulNode *p); ai-1aipai結(jié)點結(jié)點p的指針是否需要修改？的指針是否需要修改？delete p; 2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社存儲分配方式比較存儲分配方式比較順序表采用順序存儲結(jié)構(gòu)，即用一段地址順序表采用順序存儲結(jié)構(gòu)，

42、即用一段地址連續(xù)連續(xù)的的存儲單元存儲單元依次依次存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過間的邏輯關(guān)系通過存儲位置存儲位置來實現(xiàn)。來實現(xiàn)。鏈表采用鏈接存儲結(jié)構(gòu)，即用一組鏈表采用鏈接存儲結(jié)構(gòu)，即用一組任意任意的存儲單的存儲單元存放線性表的元素，用元存放線性表的元素，用指針指針來反映數(shù)據(jù)元素之間來反映數(shù)據(jù)元素之間的邏輯關(guān)系。的邏輯關(guān)系。2.4 順序表和鏈表的比較順序表和鏈表的比較數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學出版社清華大學出版社2.4 順序表和鏈表的比較順序表和鏈表的比較時間性能比較時間性能比較 時間性能時間性能是指實現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作（即是指實現(xiàn)基于某種