課件數(shù)據(jù)結(jié)構(gòu)1

1、 第2章 線性表2.1 線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 應(yīng)用舉例 作業(yè)上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)： 僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2. 線性表邏輯結(jié)構(gòu)：“一對(duì)一” 或 1:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn) 算 ：修改、插入、刪除3.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快 O(1)缺點(diǎn)：插入、刪除慢 O(n)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1 鏈表的表示2.3.2 鏈表的實(shí)現(xiàn)線性鏈表，循環(huán)鏈表，雙向鏈表2.3.3 鏈表的運(yùn)算效率分析本節(jié)小結(jié)作 業(yè)(續(xù)上堂課）2.3.1

2、鏈表的表示鏈?zhǔn)酱鎯?chǔ)特點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語線性表的單鏈表存儲(chǔ)結(jié)構(gòu)1. 鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：邏輯上相鄰，物理上不一定相鄰鏈表存放示意圖如下： a1heada2/an討論1 ：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)和 。討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置 由 指示。 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)2. 與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語1）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表： n 個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為

3、雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)以教材P27 圖2.5和圖2.6內(nèi)容為例說明。何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。 單鏈表可由一個(gè)頭指針唯一確定。頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。 頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1L

4、I437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別： 無頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)Typedef struct Lnode ElemType data; /數(shù)據(jù)域 struct Lnode *next; /指針域Lnode, *LinkList; / *LinkList為L(zhǎng)n

5、ode類型的指針3. 線性表的單鏈表存儲(chǔ)結(jié)構(gòu)2.3.2 鏈表的實(shí)現(xiàn)1. 單鏈表的建立和輸出2. 單鏈表的修改3. 單鏈表的插入4. 單鏈表的刪除5. 應(yīng)用舉例6. 其它鏈表形式1. 單鏈表的建立和輸出實(shí)例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表（a，b，c，z）,請(qǐng)寫出C語言程序。難點(diǎn)分析：每個(gè)數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)數(shù)據(jù)元素開辟存儲(chǔ)空間并賦值，并及時(shí)將地址送給前面的指針。將全局變量及函數(shù)提前說明：#include#include#define TRUE 1#define FALSE 0#define OK

6、1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0/單鏈表的定義：typedef int DataType; /DataType可以是任何相應(yīng)的數(shù)據(jù)類型如int, float或chartypedef struct Node /結(jié)點(diǎn)類型定義DataType data; /結(jié)點(diǎn)的數(shù)據(jù)域 struct Node *next; /結(jié)點(diǎn)的指針域ListNode,*LinkList;void main()LinkList head;/ListNode * head;ListNode *p;LinkList Creat

7、eList(int n);LinkList CreateList(int n)ListNode *p;LinkList L;L=(LinkList)malloc(sizeof(ListNode);L-next =NULL;for(int i=n;i0;-i)p=(LinkList)malloc(sizeof(ListNode);scanf(%d,&p-data);p-next=L-next;L-next =p;return L;LinkList CreateList(int n)ListNode *p;LinkList L;L=(LinkList)malloc(sizeof(ListNode)

8、;L-next =NULL;ListNode * q;q=L;for(int i=1;idata);q-next=p; q=p; q-next=NULL; return L;討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？ /求單鏈表的表長(zhǎng)：int ListLength(LinkList head)ListNode *p;p=head-next ;int sum=0;while(p)sum+;p=p-next; return sum;/單鏈表的打?。簐oid PrintList(LinkList head) ListNode *p; p=head-next ; while(p) printf(

9、%d ,p-data); p=p-next; printf(n);2. 單鏈表的修改(或讀?。┧悸罚阂薷牡趇個(gè)數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié)點(diǎn)的指針p，然后用p-data=new_value 即可。難點(diǎn)：?jiǎn)捂湵碇邢肴〉玫趇個(gè)元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機(jī)存取 。核心語句：見教材P29的GetElem_L函數(shù)說明Status GetElem_L(LinkList L, int i, ElemType &e)P=L-next; j=1;while(p&jnext; +j;if(!p|ji)return ERROR;e=p-data;return OK;17LinkList Get

10、Node(LinkList head,int i)ListNode *p;p=head-next ;int j=1;while(p&jnext; return p;3. 單鏈表的插入在鏈表中插入一個(gè)元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step 1：s-next=p-next;Step 2：p-next=s ；p-nexts-next思考：步驟1和2能互換么？元素x結(jié)點(diǎn)應(yīng)預(yù)先生成：S=(test*)malloc(m);S-data=x;S-next=p-next19/單鏈表的插入：void InsertListAfterI(LinkList head,DataType x,

11、int i)ListNode *p,*s;p=head-next ;int j=1;while(p&jnext; s=(LinkList)malloc(sizeof(ListNode);s-data=x;s-next =p-next ;p-next=s; /單鏈表的插入：void InsertListBeforeI(LinkList head,DataType x,int i)ListNode *p,*s;p=head-next ;int j=1;while(p&jnext; s=(LinkList)malloc(sizeof(ListNode);s-data=x;s-next =p-next

12、 ;p-next=s; 4. 單鏈表的刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q = p-next; /保存b的指針，靠它才能指向cp-next=q-next; /a、c兩結(jié)點(diǎn)相連free(q) ； /刪除b結(jié)點(diǎn)，徹底釋放p-next思考： 省略free(q)語句行不行？(p-next) - next21/單鏈表的刪除：void DeleteList(LinkList head,int i)ListNode *p,*q;p=head-next ;int j=1;while(p&jnext; q=p-next ;p-next=q-next ;free(q);5.應(yīng)用舉

13、例：兩個(gè)鏈表的歸并（教材P31）算法要求：已知：線性表 A、B，分別由單鏈表 LA , LB 存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將 A ，B 歸并為一個(gè)新的線性表C , C 的數(shù)據(jù)元素仍按值非遞減排列 。設(shè)線性表 C 由單鏈表 LC 存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測(cè)：合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ）用鏈表可表示為： 3 511 / 8 La 2 611 / 8 Lb 9 2 3 6 5 Lc 8頭結(jié)點(diǎn)算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較

14、結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。25La3 5 8 11 Lb2 6 8 119 Pa、Pb用于搜索La和Lb， Pc指向新鏈表當(dāng)前結(jié)點(diǎn)LcPaPcif(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-nextPb算法實(shí)現(xiàn)： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的單鏈表LA,LB，歸并為L(zhǎng)C后也按值排序 free(Lb); /釋放Lb的頭結(jié)點(diǎn) /MergeList_L pc-

15、next = pa?pa:pb ; /插入剩余段 while(pa&pb) /將pa 、pb結(jié)點(diǎn)按大小依次插入C中 if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=La-next; pb=Lb-next; Lc=pc=La； /初始化 思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？6. 其它鏈表形式1) 循環(huán)鏈表：將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié) 點(diǎn)(P-next=head;)，整個(gè)鏈表形成一個(gè)

16、環(huán)。 （示例見課本P35 圖2.12）A.特點(diǎn)：從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。B. 與單鏈表的區(qū)別：循環(huán)條件 單鏈表 - p = NULL 或 p -next =NULL 循環(huán)鏈表- p= head 或 p-next = headC. 設(shè)立尾指針：可以使鏈表合并簡(jiǎn)化（課本P35-圖2.13）。2）雙向鏈表：有兩個(gè)指針域的鏈表，稱為雙鏈表。 (示例見課本P36圖2.14)A.結(jié)點(diǎn)結(jié)構(gòu)：B.特點(diǎn)：可以雙向查找表中結(jié)點(diǎn)。C.運(yùn)算： 插入課本P36算法2.18，圖2.16。 刪除課本P37算法2.19，圖2.15。 注：雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。 priordatanext2

17、.3.3 鏈表的運(yùn)算效率分析時(shí)間效率分析1. 查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。2. 插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為 O(n)。練：在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為 O(n) ?？臻g效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n 個(gè)整型變量，空間復(fù)雜度為 O(n)。本章小結(jié)（討論題形式）問1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么？答：線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一（1:1）的。 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。 鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。問2：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？答：順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(1)，存儲(chǔ)