《數(shù)據(jù)結(jié)構(gòu)：2 第2章線性表A.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)：2 第2章線性表A.ppt（67頁珍藏版）》請在匯文網(wǎng)上搜索。

1、上堂課上堂課要點回顧要點回顧數(shù)據(jù)結(jié)構(gòu)課程數(shù)據(jù)結(jié)構(gòu)課程涉及數(shù)學、計算機硬件和計涉及數(shù)學、計算機硬件和計算機軟件算機軟件數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義指互相有關(guān)聯(lián)的數(shù)據(jù)元素的指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用集合，用D_S=(D,S)表示。數(shù)據(jù)結(jié)構(gòu)內(nèi)容數(shù)據(jù)結(jié)構(gòu)內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算和運算算法效率指標算法效率指標時間效率和空間效率時間效率和空間效率1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴運算的實現(xiàn)依賴于存儲結(jié)構(gòu)于存儲結(jié)構(gòu)2近近3周周上課上課內(nèi)容內(nèi)容第第2 2章章 線性表線性表第第3 3章章 棧和隊列棧和隊列第

2、第4 4章章 串串第第5 5章章 數(shù)組和廣義表數(shù)組和廣義表線性結(jié)構(gòu)線性結(jié)構(gòu)若若結(jié)結(jié)構(gòu)構(gòu)是是非非空空有有限限集集，則則有有且且僅僅有有一一個個開開始始結(jié)結(jié)點點和和一一個個終終端端結(jié)結(jié)點點，并并且且所所有有結(jié)結(jié)點點都都最最多多只只有有一一個個直接前趨和一個直接后繼。直接前趨和一個直接后繼。可表示為可表示為：（：（a1,a2,an）線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：（邏輯、存儲（邏輯、存儲和運算）和運算）3第二章第二章 線性表線性表 學習指南學習指南【學習目標學習目標】1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。用前

3、者表示的線性表簡稱為順序表順序表，用后者表示的線性表簡稱為鏈表鏈表。2.熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)。3.能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。4.結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。4【重點和難點重點和難點】鏈表是本章的重點和難點。扎實的指針操作針操作和內(nèi)內(nèi)存動態(tài)分配存動態(tài)分配的編程技術(shù)是學好本章的基本要求，分清鏈表中指針 p 和結(jié)點*p 之間的對應關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等?！局R點知識點】線性表、順序表、鏈表【學習指南學習指南】本章建議

4、完成的算法設(shè)計題為：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38 第二章第二章 線性表線性表 學習指南學習指南(續(xù))5線性結(jié)構(gòu)的特點：線性結(jié)構(gòu)的特點：只有一個首結(jié)點和尾結(jié)點；只有一個首結(jié)點和尾結(jié)點；除除首首尾尾結(jié)結(jié)點點外外，其其他他結(jié)結(jié)點點只只有有一一個個直直接接前前驅(qū)驅(qū)和和一一個直接后繼。個直接后繼。線性結(jié)構(gòu)表達式：（線性結(jié)構(gòu)表達式：（a1,a2,an）線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是組等等，其中，最典型、最常用的是-線性表線性表簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是簡言之，

5、線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一一對一的的見見第第2章章6第二章第二章線性表線性表2.1 2.1 線性表的類型定義線性表的類型定義2.2 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)2.3 2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) 2.3.1 2.3.1 線性鏈表線性鏈表 2.3.2 2.3.2 循環(huán)鏈表循環(huán)鏈表 2.3.3 2.3.3 雙向鏈表雙向鏈表 2.4 2.4 一元多項式的表示及相加一元多項式的表示及相加7線性表：線性表：由一組數(shù)據(jù)組成，線性表或者是一個空表，由一組數(shù)據(jù)組成，線性表或者是一個空表，或者可以寫成（或者可以寫成（a a1 1,a,a2 2,a ai

6、 i,a,an n）,其中其中a ai i是取自某個是取自某個集合集合S S的元素。當?shù)脑?。?in1in時，數(shù)據(jù)元素時，數(shù)據(jù)元素a ai-1i-1稱為數(shù)據(jù)元素稱為數(shù)據(jù)元素a ai i的直接前驅(qū)，而稱的直接前驅(qū)，而稱a ai+1i+1為為a ai i的直接后繼。線性表中數(shù)的直接后繼。線性表中數(shù)據(jù)元素的個數(shù)稱為該線性表的長度。據(jù)元素的個數(shù)稱為該線性表的長度。2.1線性表的類型定義線性表的類型定義8（a1,a2,ai-1，ai,ai1，,an）1.線性表的定義：線性表的定義：用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0時稱為時稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點線性起點ai的直接前趨的直接前趨

7、ai的直接后繼的直接后繼下標，下標，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總個為元素總個數(shù)，即表長數(shù)，即表長空表空表線性終點線性終點9形式化定義：形式化定義：Linearlist=(D,R)其中：其中：D0為某個數(shù)據(jù)對象的集合為某個數(shù)據(jù)對象的集合N為線性表長度為線性表長度10線性表的主要操作 初始化 求長度 取元素 定位 插入 刪除11對線性表可進行如下基本運算：對線性表可進行如下基本運算：InitList(&LInitList(&L)：構(gòu)造一個空的線性表構(gòu)造一個空的線性表L L。ListLength(&LListLength(&L)：返回返回L L數(shù)據(jù)元

8、素的個數(shù)。數(shù)據(jù)元素的個數(shù)。GetElem(L,i,&eGetElem(L,i,&e)：用用e e返回返回L L中第中第i i個數(shù)據(jù)元素的值。個數(shù)據(jù)元素的值。ListInsert(&L,i,eListInsert(&L,i,e)：在在L L中第中第i i個位置前插入新的數(shù)據(jù)元素個位置前插入新的數(shù)據(jù)元素e e，L L的長度加的長度加1 1。ListDelete(&L,i,&eListDelete(&L,i,&e)：刪去刪去L L中第中第i i個元素，用個元素，用e e返回其值，返回其值，L L的長度減的長度減1 1。PriorElem(L,cur_e,&pre_ePriorElem(L,cur_e

9、,&pre_e)：用用pre_epre_e返回數(shù)據(jù)元素返回數(shù)據(jù)元素cur_ecur_e的前驅(qū)，如果存在的前驅(qū)，如果存在的話。的話。NextElem(L,cur_e,&next_eNextElem(L,cur_e,&next_e)：用用next_enext_e返回數(shù)據(jù)元素返回數(shù)據(jù)元素cur_ecur_e的后繼，如果存在的后繼，如果存在的話。的話。LocateElem(L,e,compareLocateElem(L,e,compare()()：返回返回L L中第一個與中第一個與e e滿足關(guān)系滿足關(guān)系compare()compare()的數(shù)據(jù)元的數(shù)據(jù)元素的位序。素的位序。0 0表示這種元素不存在。表

10、示這種元素不存在。12例例1分析分析26個英文字母組成的英文表個英文字母組成的英文表（A,B,C,D,Z）學號學號姓名姓名性別性別年齡年齡班級班級2001011810205于春梅于春梅女女182001級電信級電信016班班2001011810260何仕鵬何仕鵬男男182001級電信級電信017班班2001011810284王王爽爽女女182001級通信級通信011班班2001011810360王亞武王亞武男男182001級通信級通信012班班：例例2分析學生情況登記表分析學生情況登記表數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性元素間關(guān)系是線性數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母;元素間關(guān)系

11、是線性元素間關(guān)系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性13例3、學生健康情況登記表如下：姓 名學 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱.14例4、一副撲克的點數(shù) （2，3，4，J，Q，K，A）15從以上例子可看出線性表的邏輯特征是：從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點在非空的線性表，有且僅有一個開始結(jié)點a a1 1，它它沒有直接前趨，而僅有一個直接后繼沒有直接前趨，而僅有一個直接后繼a a2 2；有

12、且僅有一個終端結(jié)點有且僅有一個終端結(jié)點a an n，它沒有直接后繼，而它沒有直接后繼，而僅有一個直接前趨僅有一個直接前趨a a n-1n-1；其余的內(nèi)部結(jié)點其余的內(nèi)部結(jié)點a ai i(2in-1)(2in-1)都有且僅有一個都有且僅有一個直接前趨直接前趨a a i-1i-1和一個直接后繼和一個直接后繼a a i+1i+1。16 線性表是一種典型的線性結(jié)構(gòu)。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。抽象數(shù)據(jù)類型的定義為：抽象數(shù)據(jù)類型的定義為：P P191917 算法2

13、.1例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。void union(List&La，List Lb)La-len=ListLength(La);Lb-len=ListLength(Lb);for(I=1;I=Lb-len;I+)GetElem(Lb，I，e);if(!LocateElem(La，e，equal)ListInsert(La，+La-len，e)/for 18 算法2.2 p21例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算法如

14、下：19void MergeList(list la，list lb，list&lc)InitList(lc);I=j=1;k=0;La-len=ListLength(la);Lb-len=ListLength(lb);while(I=la-len)&(j=lb-len)GetElem(la，I，ai);getelem(lb，j，bj);if(ai=bj)listinsert(lc，+k，ai);+I;elselistinsert(lc，+k，bj);+j;/while 20 while(I=la-len)getelem(la，I+，ai);listinsert(lc，+k，ai);/whil

15、e 處理la表 while(j=lb-len)getelem(lb，j+，bj);listinsert(lc，+k，bi);/while 處理lb表 /MergeList21練：判斷下列敘述的正誤：練：判斷下列敘述的正誤：1.數(shù)數(shù)據(jù)據(jù)的的邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)是是指指數(shù)數(shù)據(jù)據(jù)元元素素之之間間的的邏邏輯輯關(guān)關(guān)系系，是用戶按使用需要建立的。是用戶按使用需要建立的。2.線線性性表表的的邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)定定義義是是唯唯一一的的，不不依依賴賴于于計計算機。算機。3.數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)是是指指相相互互之之間間存存在在一一種種或或多多種種關(guān)關(guān)系系的的數(shù)據(jù)元素的全體。數(shù)據(jù)元素的全體。4.線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是

16、一對一的。線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。5.一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。6.“同同一一數(shù)數(shù)據(jù)據(jù)邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)中中的的所所有有數(shù)數(shù)據(jù)據(jù)元元素素都都具具有有相相同同的的特特性性”是是指指數(shù)數(shù)據(jù)據(jù)元元素素所所包包含含的的數(shù)數(shù)據(jù)據(jù)項項的的個數(shù)都相等。個數(shù)都相等。222.2線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)2.2.1順序表的表示順序表的表示2.2.2順序表的實現(xiàn)順序表的實現(xiàn)2.2.3順序表的運算效率分析順序表的運算效率分析本節(jié)小結(jié)本節(jié)小結(jié)作作 業(yè)業(yè)232.2.1順序表的表示順序表的表示用用一一組組地地址址連連續(xù)續(xù)的的存存儲儲單單元元

17、依依次次存儲線性表的元素，可通過存儲線性表的元素，可通過數(shù)組數(shù)組VnVn來實現(xiàn)來實現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲在物把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。理上相鄰的存儲單元中的存儲結(jié)構(gòu)。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或或順序映像順序映像。順序存儲定義：順序存儲定義：順序存儲方法：順序存儲方法：簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也相鄰24線性表順序存儲特點：線性表順序存儲特點：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.若已知表中首元素在存儲器中的位置，則其他元若已知表中

18、首元素在存儲器中的位置，則其他元素存放位置亦可求出（素存放位置亦可求出（利用數(shù)組下標利用數(shù)組下標）。計算方法）。計算方法是（是（參見存儲結(jié)構(gòu)示意圖參見存儲結(jié)構(gòu)示意圖）：）：設(shè)首元素設(shè)首元素a1的存放地址的存放地址為為LOC(a1)（稱為稱為首地址首地址），），設(shè)每個元素占用存儲空間（地址長度設(shè)每個元素占用存儲空間（地址長度）為）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L注意：注意：C C語言中的數(shù)組的下標從語言中的數(shù)組的下標從0 0開始，開始，即：即：VnVn的有效范圍是的

19、有效范圍是V0V0Vn-1Vn-125線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(jié)構(gòu)示意圖a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序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 Lb+(max-1)+(max-1)L L26一個一維數(shù)組，下標的范圍是到一個一維數(shù)組，下標的范圍是到，每個數(shù)組元素用相鄰的，每個數(shù)組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素 的第一個字節(jié)的

20、地址是的第一個字節(jié)的地址是，則，則 的的第一個字節(jié)的地址是第一個字節(jié)的地址是 113例例1因此：因此：LOC(M3)=98+5(3-0)=113解：解：地址計算通式為：地址計算通式為：LOC(ai)=LOC(a1)+L*（i-1）27用數(shù)組用數(shù)組V來存放來存放26個英文字母組成個英文字母組成的線性表（的線性表（a，b，c，z），），寫出在順寫出在順序結(jié)構(gòu)上序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語言程序。語言程序。voidbuild()/*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;核心語句：核心語句：

21、法法1Vi=Vi-1+1;法法2Vi=a+i;法法3Vi=97+i;例例228voidmain(void)/*主函數(shù)主函數(shù)，字母線性表的生成和輸出，字母線性表的生成和輸出*/n=26;/*n是表長，是數(shù)據(jù)元素的個數(shù)，而不是是表長，是數(shù)據(jù)元素的個數(shù)，而不是V的的實際下標實際下標*/build();display();voiddisplay()/*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/inti;for(i=0;i=i;j-)for(j=n;j=i;j-)aj+1=aj;aj+1=aj;aiai=x;=x;n+;n+;/元素后移一個位置元素后移一個位置/插入插入x x/表長加表

22、長加1 1 核心語句：核心語句：31由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。用結(jié)構(gòu)類型來定義順序表類型。#define ListSize 100 typedef int DataType;typedef struc DataType dataListSize;int length;Sqlist;32線性表的插入運算是指在表的第I(1in+1)個位置上，插入一個新結(jié)點x，使長度為n的線性表 (a1，a i-1，ai，an)變成長度為n+1的線性表 (a1，a i-1，x，ai，an)33算法2.3 P23Void InsertList(Sqlist*L，Data

23、Type x，int I)int j;if(Il.length+1)printf(“Position error”);return ERROR ;34 if(L.length=ListSize)printf(“overflow”);exit(overflow);for(j=L.length-1;j=I-1;j-)L.dataj+1=L.dataj;L.dataI-1=x;L.length+;35在線性表的第在線性表的第i i個位置前插入一個元素的示意圖如下：個位置前插入一個元素的示意圖如下：121321242830427712132124252830427712345678123456789插

24、入插入252536實現(xiàn)步驟：實現(xiàn)步驟：將第將第i至第至第n位的元素向前移動一個位置；位的元素向前移動一個位置；表長減表長減1。注意：注意：事先需要判斷，事先需要判斷，刪除位置刪除位置i是否合法是否合法?應當有應當有1in或或i=1,n3)3)刪除刪除 刪除刪除線性表的第線性表的第i i個位置上的元素個位置上的元素for(j=i+1;j=n;j+)for(j=i+1;jdata=a;p-next=q;方式方式3：先讓指針變量：先讓指針變量p指向該結(jié)點的首地址，然后用：指向該結(jié)點的首地址，然后用：(*p).data=a；(*p).nextq64設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個元素的指

25、針個元素的指針,則第則第i i個元素的個元素的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺椋羔樣驅(qū)憺?。至此應可看懂教材P28對于單鏈表的抽象描述，和教材教材P22關(guān)于順序表的關(guān)于順序表的抽象抽象定義。定義。練習：練習：p-dataai的值的值p-nextai+1的地址的地址65附2：教材教材P22關(guān)于順序表的關(guān)于順序表的抽象抽象定義：定義：Typedefstruct/若后面不再用，可省略結(jié)構(gòu)名若后面不再用，可省略結(jié)構(gòu)名ElemType*elem;/表基址表基址intlength;/表長（特指元素個數(shù)）表長（特指元素個數(shù)）intlistsize;/表當前存儲容量（字節(jié)數(shù)）表當前存儲容量（字節(jié)數(shù)）SqL

26、ist;TypedefstructLnodeElemTypedata;/數(shù)據(jù)域structLnode*next;/指針域Lnode,*LinkList;/*LinkList為Lnode類型的指針附1：教材P28對于單鏈表的抽象描述:66補充：結(jié)構(gòu)類型的補充：結(jié)構(gòu)類型的C語言表示法語言表示法介紹三個有用的庫函數(shù)（都在介紹三個有用的庫函數(shù)（都在中）：中）：sizeof(x)計算變量計算變量x的長度；的長度；malloc(m)開辟開辟m字節(jié)長度的地址空間，并返回這段空間字節(jié)長度的地址空間，并返回這段空間的首地址；的首地址；free(p)釋放指針釋放指針p所指變量的存儲空間，即徹底刪除所指變量的存儲空間，即徹底刪除一個變量。一個變量。問問1：自定義結(jié)構(gòu)類型變量自定義結(jié)構(gòu)類型變量test的長度的長度m是多少？是多少？問問2：結(jié)構(gòu)變量結(jié)構(gòu)變量test的首地址的首地址(指針指針p）是多少？是多少？問問3：怎樣刪除結(jié)構(gòu)變量怎樣刪除結(jié)構(gòu)變量test？只能借助其指針刪除！只能借助其指針刪除！*nextdatatest，長度為長度為m字節(jié)字節(jié)pmsizeof(test)p(test*)malloc(m)free(p)67