數據結構(c語言版)嚴蔚敏版第2章線性表信大(第2講)

1、緒論要點回顧數據結構定義數據結構定義指互相有關聯(lián)的數據元素的集合，用指互相有關聯(lián)的數據元素的集合，用D_S=( D, S )數據結構是相互之間存在著一種或多種特定關系的數據元素數據結構是相互之間存在著一種或多種特定關系的數據元素的集合。的集合。數據數據結構結構內容內容數據的數據的邏輯邏輯結構、結構、存儲存儲結構和結構和運算運算 算法效率指標算法效率指標時間效率和空間效率時間效率和空間效率 數據結構課程的內容邏輯結構唯一邏輯結構唯一存儲結構不唯一存儲結構不唯一運算的實現(xiàn)依賴運算的實現(xiàn)依賴于存儲結構于存儲結構近期上課內容第第2 2章章 線性表線性表第第3 3章章 棧和隊列棧和隊列第第4 4章章 串

2、串第第5 5章章 數組和廣義表數組和廣義表 線性結構(邏輯、存儲和運算)若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼?？杀硎緸椋?a1 , a2 , , an) 線性結構的定義：線性結構的特點： 只有一個首結點和尾結點；只有一個首結點和尾結點； 除首尾結點外，其他結點只有一個直接前驅和一除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。個直接后繼。線性結構包括線性表、堆棧、隊列、字符串、數組等等，其中，最典型、最常用的是-簡言之，線性結構反映結點間的邏輯關系是 一對一 的第二章線性表第第2章章 線性表線性表 2.1 線性表的類型

3、定義線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) 圖圖2.1 線性表的邏輯結構線性表的邏輯結構 2.1 線性表的類型定義線性表的類型定義2.1.1 線性表的邏輯結構線性表的邏輯結構 （a1, a2, ai-1，ai, ai1 ，, an）線性表的定義：線性表的定義：是是n個數據元素的個數據元素的有限序列有限序列n=0時稱為時稱為數據元素數據元素表頭表頭ai的直接的直接前趨前趨ai的直接的直接后繼后繼下標，下標，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總個為元素總個數，即表長數，即

4、表長空表空表表尾表尾例例1 1 分析分析26 26 個英文字母組成的英文表個英文字母組成的英文表 （ A, B, C, D, , Z）學號學號姓名姓名性別性別年齡年齡班級班級541407010126541407010126于春梅于春梅女女 18 1820142014級計科級計科1 1班班2626號號541407010127541407010127何仕鵬何仕鵬男男 18 1820142014級計科級計科1 1班班2727號號541407010128541407010128王王 爽爽女女 18 1820142014級計科級計科1 1班班2828號號541407010129541407010129王

5、亞武王亞武男男 18 1820142014級計科級計科1 1班班2929號號： ：例例2 分析學生情況登記表分析學生情況登記表數據元素都是記錄數據元素都是記錄; 元素間關系是線性元素間關系是線性數據元素都是字母數據元素都是字母; 元素間關系是線性元素間關系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性 線性表的特點可概括如下：線性表的特點可概括如下： 同一性同一性 有窮性有窮性 有序性有序性 線性表是最常見的數據結構，因為矩陣、數組、字符串、線性表是最常見的數據結構，因為矩陣、數組、字符串、堆棧、堆棧、 隊列等都符合線性條件。隊列等都符合線性條件。練：判斷下列敘述的

6、正誤：1. 數據的邏輯結構是指數據元素之間的邏輯關系，數據的邏輯結構是指數據元素之間的邏輯關系，是用戶按使用需要建立的。是用戶按使用需要建立的。2. 線性表的邏輯結構定義是唯一的，不依賴于計線性表的邏輯結構定義是唯一的，不依賴于計算機。算機。3. 數據結構是指相互之間存在一種或多種關系的數據結構是指相互之間存在一種或多種關系的數據元素的全體。數據元素的全體。4. 線性結構反映結點間的邏輯關系是一對一的。線性結構反映結點間的邏輯關系是一對一的。5. 一維向量是線性表，但二維或一維向量是線性表，但二維或N維數組不是。維數組不是。6. “同一數據邏輯結構中的所有數據元素都具有相同一數據邏輯結構中的所

7、有數據元素都具有相同的特性同的特性”是指數據元素所包含的數據項的個是指數據元素所包含的數據項的個數都相等。數都相等。例例2-1 兩個集合兩個集合La和和Lb的合并的合并假設兩個集合假設兩個集合La7,2,3Lb8,4,5,6怎樣將他們合并呢？怎樣將他們合并呢？1，首先知道，首先知道La的長度是的長度是3和和Lb的長度是的長度是42，之后把，之后把Lb集合中的元素依次和集合中的元素依次和La中的元素進行比對中的元素進行比對形成一個循環(huán)，首先形成一個循環(huán)，首先Lb中的中的8與與La的元素依次比對，的元素依次比對，8與所有與所有La中中元素不同，將元素不同，將8插入插入La中，中，3，2與與2相同進

8、入相同進入Lb的下一個元素，都不相同，的下一個元素，都不相同，之后將元素合并到之后將元素合并到La中，中，例例2-2 兩個非遞減有序的線性表兩個非遞減有序的線性表La和和Lb的合并的合并 如如La2,4,6Lb4,7,9,10合并合并1，定義，定義Lc,長度是長度是La長度長度+Lb長度長度2，La中中2與與Lb中中4，把小，把小La中的中的2的插入的插入Lc，La進入下一個進入下一個元素元素3, La中中4與與Lb中中4比較，把比較，把La的的4插入插入Lc,LaLb都下一個元素都下一個元素4,La中中6與與Lb中中7比較，把小的比較，把小的La中的中的6的插入的插入Lc，La進入下進入下一

9、個元素，無元素了一個元素，無元素了5，就將，就將Lb中剩余元素依次加入中剩余元素依次加入Lc中中47910246LaLbLc2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.2.1 線性表的順序存儲結構線性表的順序存儲結構 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過存儲線性表的元素，可通過數組數組來實現(xiàn)。來實現(xiàn)。把邏輯上相鄰的數據元素存儲在物把邏輯上相鄰的數據元素存儲在物理上理上相鄰相鄰的存儲單元中的存儲結構。的存儲單元中的存儲結構。順序存儲定義：順序存儲定義：順序存儲方法：順序存儲方法：簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也

10、相鄰線性表順序存儲特點：1. 邏輯上相鄰的數據元素，其物理上也相鄰；邏輯上相鄰的數據元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數組下標）。計算方法是：用數組下標）。計算方法是： 設首元素設首元素a1的存放地址為的存放地址為LOC(a1)（稱為首地址），設每個元素占用存儲空稱為首地址），設每個元素占用存儲空間（地址長度）為間（地址長度）為L字節(jié)，字節(jié)，則表中任一數據元素的則表中任一數據元素的存放地址存放地址為：為： LOC(ai) = LOC(a1) + L *(i-1) LOC(

11、ai+1) = LOC(ai)+L 它是一種它是一種隨機存取隨機存取的數據結構。的數據結構。 注意：C語言中的數組的下標從0開始， 即：Vn的有效范圍是V0Vn-1線性表的順序存儲結構示意圖線性表的順序存儲結構示意圖a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內容內容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L L一個一維數組，下標的范圍是到，每個數組一個一維數組，下標的范圍是到，每個數組元素用相鄰的元素用相鄰的個字節(jié)個字

12、節(jié)存儲。存儲器按字節(jié)編址，設存儲存儲。存儲器按字節(jié)編址，設存儲數組元素數組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9898，則，則 的第的第一個字節(jié)的地址是一個字節(jié)的地址是 113例1 1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址計算通式為：地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）用數組V V來存放2626個英文字母組成的線性表(a(a，b b，c c，z)z)，寫出在順序結構上生成和顯示該表的C C語言程序。 void build() /*字母線性表的生成，即建表操作*/ int i;V0=a;for(i=1;i=

13、n-1;i+) Vi=Vi-1+1; 核心語句：法1 Vi= Vi-1+1;法2 Vi=a+i;法3 Vi=97+i;例2void build();void display();#define n 26int Vn;void main(void) /*主函數，字母線性表的生成和輸出*/ build(); display();void display() /*字母線性表的顯示，即讀表操作*/ int i;for(i=0;i=n-1;i+)printf(%c,Vi);printf(n);執(zhí)行結果： a b c d e f g h i j k l m n o p q r s t u v w x y

14、z2626個字母 另一種寫法#includeint main()int i;for(i=0;i=i;j-)aj+1=aj; ai=x; n+;/ 元素后移一個位置/ 插入x / 表長加1 4. 刪除操作刪除操作 指將表的第指將表的第i(1in)個元素刪去，使長度為個元素刪去，使長度為n的線性表的線性表(e1，, ei-1，ei，ei+1，en)變成長度為變成長度為n-1的線性表的線性表(e1，, ei-1， ei+1，en)。 實現(xiàn)步驟：實現(xiàn)步驟： 將第將第i +1至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置； 表長減表長減1。注意：注意：事先需要判斷，事先需要判斷，刪除位置

15、刪除位置i 是否合法是否合法?圖圖2.4 順序表中刪除元素順序表中刪除元素 例如：線性表例如：線性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)刪除第刪除第5個元素，則需將第個元素，則需將第6個元素到第個元素到第10個元素依次向前移動個元素依次向前移動一個位置，如圖一個位置，如圖2.4所示。所示。 for (j=i+1;jdata=a; p-next=q; 方式3：先讓指針變量p指向該結點的首地址，然后用： (*p).data=a； (*p).nextq單鏈表可以由頭指針唯一確定單鏈表可以由頭指針唯一確定。 單鏈表的存儲結構描述如下：單鏈表的存儲結構描述如下：

16、typedeftypedef structstruct LNodeLNode ElemType ElemType data;data; struct struct LNodeLNode * *next;next;LNode ,*LinkList; /* LinkList為結構指針類型為結構指針類型*/ 假設假設L是是LinkList型的變量，則型的變量，則L是一個結構指針，即單鏈表的是一個結構指針，即單鏈表的頭指針，它指向表中第一個結點。頭指針，它指向表中第一個結點。 若若L=NULL（對于帶頭結點的單鏈表為（對于帶頭結點的單鏈表為L-next=NULL），），則表示單鏈表為一個空表，其長度為

17、則表示單鏈表為一個空表，其長度為0。 若不是空表，對于帶頭結點的單鏈表若不是空表，對于帶頭結點的單鏈表L，p=L-next指向指向表中的第一個結點表中的第一個結點a1，即，即p-data=a1，而，而p-next-data=a2。其余依此類推。其余依此類推。1. 查找查找 算法描述：算法描述： 查找第查找第i個結點，從頭指針個結點，從頭指針L出發(fā)，順著鏈域掃描。出發(fā)，順著鏈域掃描。 用指針用指針p指向當前掃描到的結點，用指向當前掃描到的結點，用j做計數器，累計當前掃做計數器，累計當前掃描過的結點數。描過的結點數。 當當j = i時，指針時，指針p所指的結點就是要找的第所指的結點就是要找的第i個

18、結點。個結點。 2.3.2 單鏈表上的基本運算單鏈表上的基本運算 2. 單鏈表插入操作單鏈表插入操作 算法描述：算法描述： 要在第要在第i個位置插入元素個位置插入元素e，需要找到第，需要找到第i-1個結點并由指個結點并由指針針p指示，然后申請一個新的結點并由指針指示，然后申請一個新的結點并由指針s指示，其數據域指示，其數據域的值為的值為e。 修改第修改第i-1個結點的指針使其指向個結點的指針使其指向s，使，使s結點的指針域指結點的指針域指向原第向原第i個結點。個結點。 插入：插入：s-next=p-next; p-next=s; 在鏈表中插入一個元素的示意圖如下：在鏈表中插入一個元素的示意圖如

19、下：x xsb ba apa ab bp插入步驟（即核心語句）：插入步驟（即核心語句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s ；p-nexts-next元素元素x x結點應預先生成：結點應預先生成：s=(LinkList)malloc(m);s=(LinkList)malloc(m);s-data=x;s-data=x;s-next=p-next;s-next=p-next;p-next=s;p-next=s;3. 3. 刪除 在鏈表中刪除某元素的示意圖如下：在鏈表中刪除某元素的示意圖如下：c ca ab bp刪除步驟（即核心語句）：

20、刪除步驟（即核心語句）：q = p-next; /保存保存b的指針，靠它才能指向的指針，靠它才能指向cp-next=q-next; /a、c兩結點相連兩結點相連free(q) ； /刪除刪除b結點，徹底釋放結點，徹底釋放p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - next4. 建立單鏈表建立單鏈表圖圖2.10 頭插法建立單鏈表圖示頭插法建立單鏈表圖示 2） 尾插法建表尾插法建表 圖圖2.11 尾插法建表圖示尾插法建表圖示 rs；r 始終指向單鏈表的表尾L(a) 建空表c1ss 指向新申請的結點空間sdatac1(b) 申請新結點并賦值Lc1s(

21、c) 插入第一個結點Lc2c1rrr nexts；(d) 插入第二個結點sr5.5.應用舉例：兩個鏈表的歸并應用舉例：兩個鏈表的歸并( (教材教材P31)P31)算法要求：已知：線性表 A、B，分別由單鏈表 LA , LB 存儲，其中數據元素按值非遞減有序排列，要求：將 A ，B 歸并為一個新的線性表C , C 的數據元素仍按值非遞減排列 。設線性表 C 由單鏈表 LC 存儲。假設：A=(3，5，8，11)，B=(2，6，8，9，11)預測：合并后 C =( 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 )用鏈表可表示為： 3 3 5 511 11 / 8 8 La 2

22、2 6 611 11 / 8 8 Lb 9 9 2 2 3 3 6 6 5 5 Lc 8 8 811 / 911頭結點算法分析：算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針搜索兩個鏈表；比較：比較結點數據域中數據的大??；插入：將兩個結點中數據小的結點插入新鏈表。La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索La和Lb， Pc指向新鏈表當前結點Lc Pa3 PcPa5 Pc11Pc2 PbPcPa思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何編程？2、要求不能有重復的數據元素，如何編程？6 6，其他形式的鏈表討論1：

23、 用一維數組也能存放鏈表嗎？怎樣實現(xiàn)？答：能。只要定義一個結構類型(含數據域和指示域)數組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數據域含義與前面相同，指示域相當于前面的指針域。靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。具體實現(xiàn)過程見教材P31-34。討論討論2 2： 鏈表能不能首尾相連？怎樣實現(xiàn)？鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結點的指針域指向頭結點即可 (P-next=head;) 。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。特別：帶頭結點的空循環(huán)鏈表樣式H參見教材P35 特點： 圖圖2.13 循環(huán)鏈表循環(huán)鏈表 La1ai 1ai

24、anL(a) 帶頭結點的空循環(huán)鏈表(b) 帶頭結點的循環(huán)單鏈表的一般形式a1ai 1aianrearrear*(rearnext)*(c) 采用尾指針的循環(huán)單鏈表的一般形式討論討論3 3： 單鏈表只能查找結點的直接后繼，單鏈表只能查找結點的直接后繼，能不能查找直接前驅？如何實現(xiàn)？能不能查找直接前驅？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可(例如用*next和*prior;) 。雙向鏈表在非線性結構(如樹結構)中將大量使用。priordatanext這種有兩個指針的鏈表稱為雙向鏈表。其特點是可以雙向查找表中結點。參見教材P3539。特別：帶頭結點的空雙向鏈表樣式： /圖圖2.14 雙向

25、鏈表的結點結構雙向鏈表的結點結構 priordatanext前驅指針域數據域后繼指針域 由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結點的直接前驅結點與直接后繼結點變得非常方便。個結點的直接前驅結點與直接后繼結點變得非常方便。 設指針設指針p指向雙鏈表中某一結點，則有下式成立：指向雙鏈表中某一結點，則有下式成立：p-prior-next = p = p-next-prior 圖圖2.15 雙向循環(huán)鏈表圖示雙向循環(huán)鏈表圖示 La1a2a3L(a) 空的雙向循環(huán)鏈表(b) 非空的雙向循環(huán)鏈表1. 雙向鏈表的前插操作雙向鏈表的前插操作 圖圖2.16

26、雙向鏈表插入操作雙向鏈表插入操作 abspc2. 雙向鏈表的刪除操作雙向鏈表的刪除操作 算法描述：算法描述： 圖圖2.17 雙向鏈表的刪除操作雙向鏈表的刪除操作 abcp要點回顧1. 鏈表的表示(包括有關術語、結構數據類型等)2. 鏈表的實現(xiàn)(建表、輸出、修改、插入、刪除)了解：其它鏈表形式了解：其它鏈表形式靜態(tài)鏈表循環(huán)鏈表雙向鏈表提問： 怎樣讀取頭結點數據域中的信息？ 鏈表的操作要用指針？ 用L-data僅兩個作用：找位置和改地址！ 順序表和鏈表的比較順序表和鏈表的比較 1. 基于空間的考慮基于空間的考慮 在鏈表中的每個結點，除了數據域外，還要額外設置指針在鏈表中的每個結點，除了數據域外，還

27、要額外設置指針（或光標）域，（或光標）域，從存儲密度來講，這是不經濟的從存儲密度來講，這是不經濟的。所謂存儲密度。所謂存儲密度(Storage Density), 是指結點數據本身所占的存儲量和整個結點結是指結點數據本身所占的存儲量和整個結點結構所占的存儲量之比，構所占的存儲量之比， 即即 存儲密度存儲密度=結點數據本身所占的存儲量結點數據本身所占的存儲量/結點結構所占的存儲總結點結構所占的存儲總量量 一般地，存儲密度越大，存儲空間的利用率就越高。顯一般地，存儲密度越大，存儲空間的利用率就越高。顯然，順序表的存儲密度為然，順序表的存儲密度為1，而鏈表的存儲密度小于，而鏈表的存儲密度小于1。 由此可知，由此可知，當線性表的長度變化不大，易于事先確定其當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結構。大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結構。 2. 基于時間的考慮基于時間的考慮 順序表是由向量實現(xiàn)的，它是一種隨機存取結構，對表中任順序表是由向量實現(xiàn)的，它是一種隨機存取結構，對表中任一結點都可以在一結點都可以在O(1)時間內直接地存取，而鏈表中的結點，需從時間內直接地存取，而鏈表中的結點，需從頭指針起順著鏈找