《第2章 線性表及其應用》習題解答

1、第2章線性表及其應用.13.第2章線性表及其應用本章學習要點◆掌握線性表的邏輯結(jié)構(gòu)及相關(guān)概念。◆掌握線性表的兩種基本存儲結(jié)構(gòu)，即線性順序表（順序表）和線性鏈表（鏈表）的存儲結(jié)構(gòu)。體會線性表在各種存儲方式之間的差異及其各自的優(yōu)缺點。◆熟練掌握順序表和鏈表上各種基本操作的實現(xiàn)過程?！綮`活運用順序表和鏈表的特點解決實際應用問題。線性表（LinearList）是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表有兩種基本存儲表示方法，即順序存儲表示和鏈表表示

2、。線性表的基本操作主要有插入、刪除和查找等。本章將具體給出線性表的定義、存儲結(jié)構(gòu)、基本操作及其算法實現(xiàn)，最后給出線性表的應用實例。2.1線性表的定義和基本運算2.1.1線性表的定義線性表線性表是n(n≥0)個同類型數(shù)據(jù)元素（記錄或結(jié)點）的有限序列：a0a1a2…an1。記為：Ln=(a0a1a2…an1)。其中：a0是開始結(jié)點開始結(jié)點，an1是終端結(jié)點終端結(jié)點，ak是ak1的直接前驅(qū)直接前驅(qū)結(jié)點，而ak1是ak的直接后直接后繼結(jié)點(k=

3、012…n2)；終端結(jié)點an1沒有后繼結(jié)點，開始結(jié)點a0沒有前驅(qū)結(jié)點；元素ai(i=012…n1)在表中的位置為i1；元素的個數(shù)n稱為線性表L的長度，長度為零的線性表叫空表。需要說明的是：在CC語言中，數(shù)組元素的下標是從0開始的，具有n個數(shù)據(jù)元素的數(shù)組A的所有元素為A[0]A[1]…A[n1]。在線性表的定義中，第i個元素的下標為i1即元素的位置等于其下標加1。日常生活中，線性表的例子很多：【例2.1】L10=（1，3，5，7，9，2，

4、4，6，8，10）是一個線性表。其中的數(shù)據(jù)元素是整數(shù)，該線性表的長度為10。按表中的排列順序，元素1是第一個元素沒有前驅(qū)，元素10是最后一個元素沒有后繼?！纠?.2】L36=（0123456789ABCD…XYZ）是一個線性表。其中的數(shù)據(jù)元素是所有數(shù)字字符和所有大寫字母字符，線性表的長度為36。按表中的排列順序，元素‘0’是第一個元素沒有前驅(qū)，元素‘Z’是最后一個元素沒有后繼。【例2.3】由圖2.1所示的學生基本情況表L7也是一個線性表

5、。線性表中的元素是由5個數(shù)據(jù)項組成的紀錄，表的長度為7。第2章線性表及其應用.15.順序表的存儲結(jié)構(gòu)和一維數(shù)組的存儲結(jié)構(gòu)極為相近；但是由于在線性表中允許執(zhí)行插入和刪除等操作，也就是說一個線性表的長度是可變的，為適應這種情況在C語言中用以下結(jié)構(gòu)類型來表示順序表。typedefintElemType為了方便上機調(diào)試程序，本章假定數(shù)據(jù)元素的類型為整型constintMAXLEN=100定義順序表存儲空間大小的初始分配常量constintINC

6、SIZE=50定義順序表存儲空間的擴充常量值structSqList定義順序表的結(jié)構(gòu)類型為SqListElemTypeelem存儲空間的基址intlength線性表的長度intlistsize當前表的存儲容量intincsize一次增補的容量值在以上結(jié)構(gòu)表示下，許多關(guān)于線性表的運算（如存、取、求線性表的長度和置表空等操作）極易實現(xiàn)。以下主要討論關(guān)于順序表的插入、刪除、查找和遍歷等操作。2.2.2順序表中基本操作的實現(xiàn)1初始化操作Init

7、List_Sq(（2）置線性表的長度值length為0（3）置表的當前容量listsize為動態(tài)分配時的大?。唬?）置容量擴充值incsize的大小為INCSIZE。線性表L的初始化存儲結(jié)構(gòu)如圖2.3所示。算法實現(xiàn)voidInitList_Sq(SqList動態(tài)分配一個長度為maxlength的連續(xù)存儲空間，類型為ElemType，返回首地址到L.elemL.length=0L.listsize=maxlengthL.incsize=i