2-2線性表的邏輯結構v第二章線性表線性表的定義線性表的邏輯特征線性表的抽象數(shù)據(jù)類型定義學什么？2-2-1線性表的定義v第二章線性表線性表的定義線性表（表）：n（n≥0）個具有相同類型的數(shù)據(jù)元素的有限序列（a1,a2,…,ai,…,an）線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)空表：長度等于零的線性表ai（1≤i≤n）稱為數(shù)據(jù)元素下角標

i表示該元素在線性表中的位置或序號線性表的邏輯特征1.數(shù)據(jù)元素個數(shù)的有限性a1ai-1aiana22.數(shù)據(jù)元素類型的相同性3.數(shù)據(jù)元素類型的抽象性4.相鄰數(shù)據(jù)元素的序偶性，且a1無前驅，an無后繼序偶：兩個具有固定次序的元素組成的序列，記作(a，b)，且稱a是b

的前驅，b是a

的后繼L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))不確定、任意2-2-2線性表的抽象數(shù)據(jù)類型定義v第二章線性表線性表的抽象數(shù)據(jù)類型定義ADTListDataModelOperationendADT線性表中的數(shù)據(jù)元素具有相同類型，相鄰元素具有前驅和后繼關系InitList：表的初始化，建一個空表CreateList：建立具有n個元素的線性表DestroyList：銷毀表，釋放表所占用的存儲空間Length：求表的長度Get：在表中取序號為i

的數(shù)據(jù)元素Locate：在線性表中查找值等于x

的元素Insert：在表的第i

個位置處插入一個新元素xDelete：刪除表中的第i

個元素Empty：判斷表是否為空InitList

輸入：無功能：表的初始化，建一個空表輸出：無CreateList

輸入：n個數(shù)據(jù)元素

功能：建立一個線性表

輸出：具有n個元素的線性表DestroyList輸入：無功能：銷毀表，釋放表所占用的存儲空間輸出：無Locate輸入：數(shù)據(jù)元素x

功能：在線性表中查找值等于x

的元素輸出：查找成功返回x

在表中的序號，否則返回0線性表的抽象數(shù)據(jù)類型定義（a1,a2,…,ai,…,an）Get輸入：元素的序號i

功能：在表中取序號為i

的數(shù)據(jù)元素輸出：若i合法，返回序號為i的元素值Length

輸入：無功能：求表的長度輸出：表中數(shù)據(jù)元素的個數(shù)Insert輸入：插入位置i，待插x功能：在表的第i

個位置處插入一個新元素x輸出：若插入成功，表中增加一個新元素；否則給出失敗信息Delete

輸入：刪除位置i功能：刪除表中的第i

個元素輸出：若刪除成功，表中減少一個元素；否則給出失敗信息Empty輸入：無功能：判斷表是否為空輸出：若是空表，返回1，否則返回0線性表的抽象數(shù)據(jù)類型定義（a1,a2,…,ai