-線性表ppt課件

《-線性表ppt課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、第二章線性表1【學(xué)習(xí)目標(biāo)】了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機(jī)中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)。能夠從時間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合。【重點(diǎn)和難點(diǎn)】鏈表。熟練掌握鏈表的操作對以后各章的學(xué)習(xí)將有很大幫助。2什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序集合。它有四個基本特征：1．集合中必存在唯一的一

2、個"第一元素"；沒有"前驅(qū)"2．集合中必存在唯一的一個"最后元素"；沒有"后繼"3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的"直接后繼"；4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的"直接前驅(qū)"。課前回顧32.1線性表的邏輯定義2.1.1線性表的定義什么是線性表？具有相同數(shù)據(jù)類型的n個數(shù)據(jù)元素的有限序列。L＝(a1,a2,...,ai,...,an)表長:序列中數(shù)據(jù)元素的個數(shù)n；n=0——空表若ai是第i個數(shù)據(jù)元素，稱i為ai在線性表中的位序。Linear_list=(D,R)D＝{aiai∈datatype,i=1,2,...,n,

3、n≥0}R＝{ai-1,ai∈D,i=2,...,n}42.1線性表的邏輯定義2.1.2線性表的基本操作基本操作：1.線性表初始化：Init_List(L)初始條件：線性表L不存在。操作結(jié)果：構(gòu)造一個空的線性表L。2.求線性表的長度：Length_List(L)初始條件：線性表L已存在。操作結(jié)果：返回L中元素個數(shù)。3.取表元：Get_List(L,i)初始條件：線性表L已存在，1≤i≤Length_List(L)。操作結(jié)果：返回L中第i個元素的值或地址。52.1線性表的邏輯定義2.1.2線性表的基本操作4.按值查

4、找：Locate_List(L,x)初始條件：線性表L已存在，x是給定的一個數(shù)據(jù)元素。操作結(jié)果：返回L中第一個值為x的數(shù)據(jù)元素的位序或地址。若這樣的元素不存在，則返回-1。5.插入操作：Insert_List(L,i,x)初始條件：線性表L已存在，1≤i≤Length_List(L)+1。操作結(jié)果：在L的第i個元素之前插入新的元素x，L的長度增1。6.刪除操作：Delete_List(L,i)初始條件：線性表L已存在且非空，1≤i≤Length_List(L)。操作結(jié)果：刪除L的第i個元素，L的長度減1。62.2線性表的順序存儲及

5、操作實(shí)現(xiàn)2.2.2順序表中基本操作的實(shí)現(xiàn)intLength_List(SeqListL){return(L->last＋1);}datatypeGet_List(SeqListL,intpos){returnL->data[pos-1];}92.2線性表的順序存儲及操作實(shí)現(xiàn)2.2.2順序表中基本操作的實(shí)現(xiàn)重點(diǎn)討論:一、初始化操作二、元素定位操作三、插入元素操作四、刪除元素操作102.2線性表的順序存儲及操作實(shí)現(xiàn)2.2.2順序表中基本操作的實(shí)現(xiàn)函數(shù)名:malloc功?能:內(nèi)存分配函數(shù)用?法:voidmalloc(unsignedsi

6、ze);返回值：指針，指向長度為size的存儲空間；若分配失敗，返回NULL。11一、初始化操作SeqListinit_SeqList(){SeqListL;L=malloc(sizeof(SeqList));L->last=-1;returnL;}時間復(fù)雜度為：O(1)12二、按值查找若順序表中存在和給定值相等的數(shù)據(jù)元素，就返回第一個滿足條件元素的在線性表中的位置，以-1返回值表示不存在這樣的數(shù)據(jù)元素。intLocation_SeqList(SeqListL,datatypex){inti=0;//數(shù)組下標(biāo)從0開始while(i

7、<=L->last&&L->data[i]!=x)i++;//依次進(jìn)行判定if(i>L->last)return-1;//下標(biāo)超出范圍，不存在elsereturni;//返回的是數(shù)組下標(biāo)}時間復(fù)雜度為：O(n)13三、插入元素操作按定義，在線性表的第i個元素之前插入一個元素x，使得線性表(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,x,ai,…,an)邏輯結(jié)構(gòu)的變換：(1)改變了表中ai-1,ai元素之間的關(guān)系，使改變?yōu)?ai-1,x>和(2)表長增101ii+1i+2n-1MAX

8、-1a1a2…ai-1aiai+1…an…01ii+1i+2nMAX-1a1a2…ai-1xai…an…線性表中數(shù)據(jù)元素的插入前后如下圖所示14在線性表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素XintInsert_SeqList(SeqListL，int