T3-線性表(單鏈表)

單鏈表第二章：線性表

主講：周翔什么是鏈表什么是鏈表？鏈表的存儲原理是？鏈表的定義鏈式存儲結構：結點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰定義：采用鏈式存儲結構的線性表稱為鏈表?，F(xiàn)在我們從兩個角度來討論鏈表：從實現(xiàn)角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表；從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。線性表的鏈式存儲結點（node）：數(shù)據(jù)元素的存儲映像數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼結點的存儲位置鏈表的定義鏈表的定義n個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構單鏈表、雙鏈表、循環(huán)鏈表：結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表有兩個指針域的鏈表，稱為雙鏈表首尾相接的鏈表稱為循環(huán)鏈表結點可以連續(xù)存儲，也可以不連續(xù)存儲結點的邏輯順序與物理順序可以不一致單鏈表的定義單鏈表(‘A’,

’B’,

’C’,

’D’,

’E’)的示例圖頭指針H存儲地址數(shù)據(jù)域指針域1D 437B 1313C 119H NULL25F 3731A 737G 1943E 2531單鏈表的定義以下分別為單鏈表(‘A’,

’B’,

’C’,

’D’,

’E’)的邏輯結構與物理存儲結構：邏輯結構：物理結構：頭指針、頭結點和首元結點頭指針：是指向鏈表中第一個結點的指針首元結點：是指鏈表中存儲第一個數(shù)據(jù)元素a1的結點頭結點：是在鏈表的首元結點之前附設的一個結點；數(shù)據(jù)域內只放空表標志和表長等信息單鏈表的定義頭指針頭結點首元結點a1heada2…infoan^單鏈表的邏輯結構示意圖有以下兩種形式：無頭結點有頭結點單鏈表的定義ZHAOQIANLISUNZHOUWUZHENG/\WANGHZHAOQIANLISUNZHOUWUZHENG/\WANGH討論1、如何表示空表？單鏈表的定義有頭結點時，當頭結點的指針域為空時表示空表討論2、在鏈表中設置頭結點有什么好處？1、便于首元結點的處理：首元結點的地址保存在頭結點的指針域中,所以在鏈表的第一個位置上的操作和其它位置一致，無須進行特殊處理;2、便于空表和非空表的統(tǒng)一處理：無論鏈表是否為空，頭指針都是指向頭結點的非空指針，因此空表和非空表的處理也就統(tǒng)一了。討論3.頭結點的數(shù)據(jù)域內裝的是什么？單鏈表的定義頭結點的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結點不能計入鏈表長度值單鏈表的定義ADTNode{ //結點類型定義ElemTypedata //數(shù)據(jù)域Nodenext //指針域}ADTNode,LinkList單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的

名字來命名元素訪問方式：訪問數(shù)據(jù)元素A：head→next→data訪問數(shù)據(jù)元素B：head→next→next→data訪問數(shù)據(jù)元素D：p→data單鏈表的定義單鏈表的基本操作初始化0102030405取值查找

插入刪除基本操作的實現(xiàn)初始化單鏈表：對單鏈表進行所有操作之前，必須先進行初始化，即生成空表！算法步驟：1、生成新結點作頭結點，用頭指針head指向頭結點。2、頭結點的指針域置空。單鏈表的基本操作——初始化單鏈表的基本操作——獲取表長求單鏈表的長度：可以采用“數(shù)”結點的方法來求出單鏈表的長度算法步驟：1、指針p依次指向各個結點2、從第一個元素開始“數(shù)”3、一直“數(shù)”到最后一個結點單鏈表的基本操作——插入操作建立單鏈表：初始化單鏈表后，可采用結點插入的方式實現(xiàn)單鏈表頭插法尾插法單鏈表的基本操作——插入操作建立單鏈表——頭插法單鏈表的基本操作——插入操作建立單鏈表——頭插法算法描述：從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭結點之后，直至讀入結束標志為止。算法步驟：1、在單鏈表中找到要插入的位置；（因為每次都是在表頭插入，所以此時這個步驟可?。?、產生新結點3、在新結點中存儲數(shù)據(jù)元素；4、修改指針指向實現(xiàn)插入單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟1：在以下這張帶頭結點的空表中插入第一個結點，結點中存儲接收的字符（假設接收的字符為’A’）步驟2：產生新結點head0head0newNode單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟3：在新結點中存儲數(shù)據(jù)元素head0newNodeA單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟4：修改指針指向實現(xiàn)插入head0newNodeA0單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟5：繼續(xù)插入第二個結點，結點中存儲接收的字符（假設接收的字符為’B’）步驟6：產生新結點head0Ahead0AnewNode單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟7：在新結點中存儲數(shù)據(jù)元素newNodeBhead0A單鏈表的基本操作——插入操作建立單鏈表——頭插法步驟8：修改指針指向實現(xiàn)插入newNodeBhead0A單鏈表的基本操作——插入操作建立單鏈表——尾插法單鏈表的基本操作——插入操作建立單鏈表——尾插法算法描述：從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表尾，直至讀入結束標志為止。需增加一個尾指針算法步驟：1、在單鏈表中找到要插入的位置；（因為每次都是在表尾插入，表尾有標志，所以此時這個步驟可?。?、產生新結點3、在新結點中存儲數(shù)據(jù)元素；4、修改指針指向實現(xiàn)插入單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟1：在以下這張帶頭結點的空表中插入第一個結點，結點中存儲接收的字符（假設接收的字符為’A’）步驟2：產生新結點head0rearnewNoderearhead0單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟3：在新結點中存儲數(shù)據(jù)元素newNodeArearhead0單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟4：修改指針指向實現(xiàn)插入newNodeAhead0rearrear單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟5：繼續(xù)插入第二個結點，結點中存儲接收的字符（假設接收的字符為’B’）步驟6：產生新結點Ahead0rearnewNodeAhead0rear單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟7：在新結點中存儲數(shù)據(jù)元素newNodeBAhead0rear單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟8：修改指針指向實現(xiàn)插入newNodeBAhead0rearrear單鏈表的基本操作——插入操作建立單鏈表——尾插法步驟9：若接下來輸入結束符號$，則最后插入的結點’B’，就成為表尾結點，應將它的next設置為空！BAhead0rear0單鏈表的基本操作——插入操作插入操作：在帶頭結點的單鏈表L中第i個位置前插入一個數(shù)據(jù)元素算法步驟：1、在單鏈表中找到要插入的位置； 第i-1個結點，并由指針pre指示2、產生新結點3、在新結點中存儲數(shù)據(jù)元素；4、修改指針指向實現(xiàn)插入單鏈表的基本操作——插入操作在以下帶頭結點的單鏈表的第i個結點前插入新元素e，即在ai-1與ai之間插入新結點0ana1heada2ai-1ai單鏈表的基本操作——插入操作插入操作：步驟1：在單鏈表中找到要插入的位置0ana1heada2ai-1aipre單鏈表的基本操作——插入操作插入操作：步驟2：產生新結點0ana1heada2ai-1aiprenewNode單鏈表的基本操作——插入操作插入操作：步驟3：在新結點中存儲數(shù)據(jù)元素0ana1heada2ai-1aiprenewNodee單鏈表的基本操作——插入操作插入操作：步驟4：修改指針指向實現(xiàn)插入0ana1heada2ai-1aiprenewNodee順序可以對調嗎？單鏈表的基本操作——刪除操作刪除操作：在帶頭結點的單鏈表L中刪除第i個結點算法步驟：1、在單鏈表中找到要刪結點的前一個結點；由指針pre指示2、將要刪結點從鏈表中斷開；3、釋放結點單鏈表的基本操作——刪除操作刪除以下鏈表中的第i個結點0ana1headai+1ai-1ai單鏈表的基本操作——刪除操作刪除操作：步驟1：在單鏈表中找到要刪結點的前一個結點0ana1headai+1ai-1aipre單鏈表的基本操作——刪除操作刪除操作：步驟2：將要刪結點從鏈表中斷開0ana1headai+1ai-1aiprer單鏈表的基本操作——刪除操作刪除操作：步驟3：釋放結點0ana1headai+1ai-1aiprer順序表里如何找到第i個元素？單鏈表的基本操作——取值操作鏈表的查找：要從鏈表的頭指針出發(fā)，順著鏈域next逐個結點往下搜索，直至搜索到第i個結點為止。因此，鏈表不是隨機存取結構單鏈表的基本操作——取值操作分別取出表中i=3的元素

L211830754256∧pppj123i=3單鏈表的基本操作——取值操作算法步驟：根據(jù)位置i獲取相應位置數(shù)據(jù)元素的內容1、從第1個結點（head→next）順鏈掃描，用指針p指向當前掃描到的結點，p初值p

=

head→next。2、j做計數(shù)器，累計當前掃描過的結點數(shù)，j初值為1。3、當p指向掃描到的下一結點時，計數(shù)器j加1。4、當j

=

i時，p所指的結點就是要找的第i個結點。單鏈表的基本操作——取值操作分別找到表中值為30和51的元素位置

L211830753056∧pj1x=30p2p3找到，返回ix=51p1p6p7未找到，返回空單鏈表的基本操作——取值操作算法步驟：根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置1、從第一個結點起，依次和x相比較。2、如果找到一個其值與x相等的數(shù)據(jù)元素，則返回其在鏈表中

的“位置”或地址；3、如果查遍整個鏈表都沒有找到其值和x相等的元素，則返回“空”。單鏈表的基本操作——合并操作兩個有序單鏈表的合并有兩個單鏈表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個單鏈表LC，要求LC也是非遞減有序排列。要求：利用新表LC利用現(xiàn)有的表LA和LB中的元素結點空間，而不需要額外申請結點空間。例如：LA=(2,2,3),LB=(1,3,3,4),則LC=(1,2,2,3,3,3,4)。單鏈表的基本操作——合并操作兩個有序單鏈表的合并算法描述：可通過更改結點的next域來重建新的元素之間的線性關系為保證新表仍然遞增有序，可利用尾插入法建立單鏈表新建表中的結點不用malloc，只需要從表LA和LB中選擇合適的點插入到新表LC中即可單鏈表的基本操作——合并操作pa041LB332LA2

30pbLC0r單鏈表的基本操作——合并操作pa041LB332LA2

30pbLC0rr單鏈表的基本操作——合并操作pa041LB332LA2

30LCrpbr單鏈表的基本操作——合并操作pa041LB332LA2

30LCpbr單鏈表的基本操作——合并操作pa0