數(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)和時(shí)間性能、(1)循環(huán)鏈接表(2)雙鏈接表線性表的長(zhǎng)度：線性表中的數(shù)據(jù)元素的數(shù)量，包括：李二、87、90、78、0102、張三、67、86、0103、孫紅、69、8103 2。 3 .空表：長(zhǎng)度等于零的線性表，記為

2、L=()。 4 .非空標(biāo)記： L(a1，a2，ai-1，ai，an )，2.1線性表的邏輯結(jié)構(gòu)，2.1.1線性表的定義，其中，ai(1in )下角I表示該元素在線性表中的位置或編號(hào)。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沒(méi)有前體，an沒(méi)有后繼者，其他各元素只有一個(gè)前體和一個(gè)后繼者。 2.1.2線性表的抽象數(shù)

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

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

5、4、排列、2.2線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)、2.2.1順序表的順序存儲(chǔ)結(jié)構(gòu)如何獲得任何元素的存儲(chǔ)地址？ 0 i-2 i-1 n-1 Max-1，a1，ai-1，ai，an，空閑，長(zhǎng)度，2.2線性表的順序記憶結(jié)構(gòu)及隨機(jī)存?。涸贠(1)時(shí)間內(nèi)取數(shù)據(jù)要素，實(shí)現(xiàn)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)、存儲(chǔ)結(jié)構(gòu)和訪問(wèn)結(jié)構(gòu)，“序列表是隨機(jī)訪問(wèn)的存儲(chǔ)結(jié)構(gòu)”的意思是在如序列表的存儲(chǔ)結(jié)構(gòu)上進(jìn)行的查找操作，其時(shí)間性能為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 ()； 求出/長(zhǎng)度T Get(int i )。 /按位搜索位置(tx )； 用/值檢索void插入(inti，T x )。 插入/t刪除(inti )； void打印列表()； 遍歷私有3360 t數(shù)據(jù)最大化。 /數(shù)組int length； /長(zhǎng)度；2.2線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)、構(gòu)造函數(shù)、構(gòu)造函數(shù)的作用是初始化一個(gè)對(duì)象的成員變量。 構(gòu)造函數(shù)的特征： 1 .構(gòu)造函數(shù)必須與類名相同2 .必須聲明為類的公共成員函數(shù)3 .不能指定門限值或門限值類型4 .構(gòu)造函數(shù)可以重新加載。 構(gòu)造函數(shù)的作用是什么(假設(shè))？ 什么時(shí)候呼叫？ 誰(shuí)(世衛(wèi)組織)呼叫？ 析構(gòu)函數(shù)，用于在對(duì)象被撤消時(shí)刪除成員變量。 標(biāo)志表示該類的名稱前面有“”。 析構(gòu)函數(shù)的特征： 1 .析構(gòu)函數(shù)沒(méi)有關(guān)殘奧儀表和門檻值2 .一個(gè)類只有一個(gè)析構(gòu)函數(shù)3 .析構(gòu)函數(shù)不允許重負(fù)荷。 析構(gòu)函數(shù)的作用是什么？ 什么時(shí)候呼叫？ 誰(shuí)(世衛(wèi)組織)呼叫？ 操作接口： SeqList ()，算法描述： seq list :3360 seq list ()長(zhǎng)度=0； 2.2線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)，1 .順序表的實(shí)現(xiàn)無(wú)殘奧儀表構(gòu)造函數(shù)，0，創(chuàng)建空的順序表，操作界面： SeqList(T a，int n )，1 .順序表的實(shí)現(xiàn)殘奧儀表構(gòu)造函