數(shù)據(jù)結(jié)構(gòu)專題線性表的邏輯結(jié)構(gòu)PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)專題線性表的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)專題線性表的邏輯結(jié)構(gòu)2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)元素之間的關(guān)系是什么？第1頁/共10頁2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)元素之間的關(guān)系是什么？現(xiàn)實(shí)生活中，許多問題抽象出的數(shù)據(jù)模型是線性表，如何存現(xiàn)實(shí)生活中，許多問題抽象出的數(shù)據(jù)模型是線性表，如何存儲這種線性結(jié)構(gòu)并實(shí)現(xiàn)插入、刪除、查找等基本操作呢？儲這種線性結(jié)構(gòu)并實(shí)現(xiàn)插入、刪除、查找等基本操作呢？ 第2頁/共10頁2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)其中，其中，ai（1in）稱為數(shù)據(jù)元素；）稱為數(shù)據(jù)元素；下角標(biāo)下角標(biāo) i

2、表示該元素在線性表中的位置或序號表示該元素在線性表中的位置或序號 。第3頁/共10頁a1a3a4ana22.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)1. 有限性有限性：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。2. 相同性相同性：線性表中數(shù)據(jù)元素的類型是同一的。：線性表中數(shù)據(jù)元素的類型是同一的。3. 順序性順序性：線性表中相鄰的數(shù)據(jù)元素：線性表中相鄰的數(shù)據(jù)元素ai-1和和ai之間存在之間存在序偶關(guān)系序偶關(guān)系(ai-1, ai)，即，即ai-1是是ai的前驅(qū)，的前驅(qū)， ai是是ai-1的后繼的后繼；a1無前驅(qū)，無前驅(qū)，an無后繼，其它每個(gè)元素有且僅有一個(gè)無后繼，其它每個(gè)元素有

3、且僅有一個(gè)前驅(qū)和一個(gè)后繼。前驅(qū)和一個(gè)后繼。 第4頁/共10頁ADT ListData 線性表中的數(shù)據(jù)元素具有相同類型，線性表中的數(shù)據(jù)元素具有相同類型， 相鄰元素具有前驅(qū)和后繼關(guān)系相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitList 前置條件前置條件：表不存在：表不存在 輸入輸入：無：無 功能功能：表的初始化：表的初始化 輸出輸出： 無無 后置條件后置條件：建一個(gè)空表：建一個(gè)空表2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)第5頁/共10頁DestroyList 前置條件前置條件：表已存在：表已存在 輸入輸入：無：無 功能功能：銷毀表：銷毀表 輸出輸出：無：無 后置條件后置條件：釋放表所占用的

4、存儲空間：釋放表所占用的存儲空間Length 前置條件前置條件：表已存在：表已存在 輸入輸入：無：無 功能功能：求表的長度：求表的長度 輸出輸出：表中數(shù)據(jù)元素的個(gè)數(shù)：表中數(shù)據(jù)元素的個(gè)數(shù) 后置條件后置條件：表不變：表不變2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)第6頁/共10頁Get 前置條件前置條件：表已存在：表已存在 輸入輸入：元素的序號：元素的序號i 功能功能：在表中取序號為：在表中取序號為i的數(shù)據(jù)元素的數(shù)據(jù)元素 輸出輸出：若：若i合法，返回序號為合法，返回序號為i的元素值，否則拋出異常的元素值，否則拋出異常 后置條件后置條件：表不變：表不變Locate 前置條件前置條件：表已存在：表已存在 輸入輸入：數(shù)據(jù)元素：數(shù)據(jù)元素x 功能功能：在線性表中查找值等于：在線性表中查找值等于x的元素的元素 輸出輸出：若查找成功，返回：若查找成功，返回x在表中的序號，否則返回在表中的序號，否則返回0 后置條件后置條件：表不變：表不變2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)第7頁/共10頁2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)第8頁/共10頁進(jìn)一步說明進(jìn)一步說明: :（1 1）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定；）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定；（2）復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)；）復(fù)雜的操作可以通過