資源描述:
《-線性表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