數(shù)據(jù)結(jié)構(gòu)——第二章線性表.ppt

1、數(shù)據(jù)結(jié)構(gòu)第二章，發(fā)表者：陳頻，第二章線性表，2.1線性表的邏輯結(jié)構(gòu)(把握)2.2線性表的順序記憶和實(shí)現(xiàn)(把握)2.3線性表的鏈接記憶和實(shí)現(xiàn)(把握)2.4順序表和單鏈接表的比較(把握)2.5線性表邏輯結(jié)構(gòu)，記憶結(jié)構(gòu)，基本概念，采樣類型數(shù)據(jù)鏈接內(nèi)存結(jié)構(gòu)、其他內(nèi)存方法、(1)線性表定義(2)邏輯特征、(1)ADT定義(2)基本操作(1)單鏈接表的特征(2)單鏈接表類定義(3)基本操作的實(shí)現(xiàn)和時間性能、(1)循環(huán)鏈接表(2)雙鏈接表線性表的長度：線性表中的數(shù)據(jù)元素的數(shù)量，包括：李二、87、90、78、0102、張三、67、86、0103、孫紅、69、8103 2。 3 .空表：長度等于零的線性表，記為

2、L=()。 4 .非空標(biāo)記： L(a1，a2，ai-1，ai，an )，2.1線性表的邏輯結(jié)構(gòu)，2.1.1線性表的定義，其中，ai(1in )下角I表示該元素在線性表中的位置或編號。2.1線性表的邏輯結(jié)構(gòu)、線性表的圖表表示、線性表(a1、a2、ai-1、ai、an )的圖表表示、2.1線性表的邏輯結(jié)構(gòu)、線性表的特性、1 .有限、2 .同一性：線性表的數(shù)據(jù)元素類型相同。 3 .順序性：線性表中相鄰數(shù)據(jù)元素ai-1和ai之間的順序偶關(guān)系(ai-1，ai )，即ai-1是ai的前體，而ai是ai-1的后繼。 a1沒有前體，an沒有后繼者，其他各元素只有一個前體和一個后繼者。 2.1.2線性表的抽象數(shù)

3、據(jù)類型定義、ADT List Data線性表的數(shù)據(jù)元素具有相同的類型， 鄰接要素具有前驅(qū)和后續(xù)的關(guān)系Operation InitList前置條件：表中沒有輸入：沒有功能：表的初始化輸出：沒有后置條件：制作空的表的DestroyList前置條件：表現(xiàn)存在輸入：沒有功能：表輸出廢棄：沒有后置條件：表占有的記憶空間Length前置條件釋放： 求出長度輸出：表中數(shù)據(jù)要素的個數(shù)后置條件：表不變、2.1線性表的邏輯結(jié)構(gòu)Get前置條件：表現(xiàn)存在輸入：要素的序號I功能：在表中取序號I的數(shù)據(jù)要素輸出：如果I有效則返回序號I的要素值， 否則拋出異常后置條件：表不變Locate前置條件：表現(xiàn)存在輸入：數(shù)據(jù)要素x功能

4、：在線性表中查找值x的要素輸出插入等待x功能：在表的第I個位置插入新要素x輸出：插入失敗時拋出異常后置條件：插入成功時在表中插入新要素Delete前置條件否則，拋出異常后置條件的2.1線性表的邏輯結(jié)構(gòu)，Empty前置條件：表現(xiàn)存在輸入：無功能：判斷表是否為空輸出：如果是空表，則返回1，否則返回0后置條件：表不變endADT，再說明： (1)線性表的基本操作在實(shí)際應(yīng)用中復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)(3)根據(jù)應(yīng)用程序的不同，操作界面也會不同。、2.1線性表的邏輯結(jié)構(gòu)、2.2線性表的順序存儲結(jié)構(gòu)和實(shí)現(xiàn)、2.2.1順序表的順序存儲結(jié)構(gòu)，例如(34，23，67，43 )、34，23，67，44

5、4、排列、2.2線性表的順序存儲結(jié)構(gòu)和實(shí)現(xiàn)、2.2.1順序表的順序存儲結(jié)構(gòu)如何獲得任何元素的存儲地址？ 0 i-2 i-1 n-1 Max-1，a1，ai-1，ai，an，空閑，長度，2.2線性表的順序記憶結(jié)構(gòu)及隨機(jī)存?。涸贠(1)時間內(nèi)取數(shù)據(jù)要素，實(shí)現(xiàn)2.2線性表的順序存儲結(jié)構(gòu)和存儲、存儲結(jié)構(gòu)和訪問結(jié)構(gòu)，“序列表是隨機(jī)訪問的存儲結(jié)構(gòu)”的意思是在如序列表的存儲結(jié)構(gòu)上進(jìn)行的查找操作，其時間性能為O(1)。 聲明序列表類，const int MaxSize=100； 模板類class seq list公用： seq list ()； /構(gòu)造函數(shù)列表(t a，int n )； SeqList ()；

6、 /析構(gòu)函數(shù)int Length ()； 求出/長度T Get(int i )。 /按位搜索位置(tx )； 用/值檢索void插入(inti，T x )。 插入/t刪除(inti )； void打印列表()； 遍歷私有3360 t數(shù)據(jù)最大化。 /數(shù)組int length； /長度；2.2線性表的順序存儲結(jié)構(gòu)和實(shí)現(xiàn)、構(gòu)造函數(shù)、構(gòu)造函數(shù)的作用是初始化一個對象的成員變量。 構(gòu)造函數(shù)的特征： 1 .構(gòu)造函數(shù)必須與類名相同2 .必須聲明為類的公共成員函數(shù)3 .不能指定門限值或門限值類型4 .構(gòu)造函數(shù)可以重新加載。 構(gòu)造函數(shù)的作用是什么(假設(shè))？ 什么時候呼叫？ 誰(世衛(wèi)組織)呼叫？ 析構(gòu)函數(shù)，用于在對象被撤消時刪除成員變量。 標(biāo)志表示該類的名稱前面有“”。 析構(gòu)函數(shù)的特征： 1 .析構(gòu)函數(shù)沒有關(guān)殘奧儀表和門檻值2 .一個類只有一個析構(gòu)函數(shù)3 .析構(gòu)函數(shù)不允許重負(fù)荷。 析構(gòu)函數(shù)的作用是什么？ 什么時候呼叫？ 誰(世衛(wèi)組織)呼叫？ 操作接口： SeqList ()，算法描述： seq list :3360 seq list ()長度=0； 2.2線性表的順序存儲結(jié)構(gòu)和實(shí)現(xiàn)，1 .順序表的實(shí)現(xiàn)無殘奧儀表構(gòu)造函數(shù)，0，創(chuàng)建空的順序表，操作界面： SeqList(T a，int n )，1 .順序表的實(shí)現(xiàn)殘奧儀表構(gòu)造函