《第2章 線性表及其應(yīng)用》習(xí)題解答

1、第2章線性表及其應(yīng)用.13.第2章線性表及其應(yīng)用本章學(xué)習(xí)要點(diǎn)◆掌握線性表的邏輯結(jié)構(gòu)及相關(guān)概念。◆掌握線性表的兩種基本存儲(chǔ)結(jié)構(gòu)，即線性順序表（順序表）和線性鏈表（鏈表）的存儲(chǔ)結(jié)構(gòu)。體會(huì)線性表在各種存儲(chǔ)方式之間的差異及其各自的優(yōu)缺點(diǎn)?！羰炀氄莆枕樞虮砗玩湵砩细鞣N基本操作的實(shí)現(xiàn)過程。◆靈活運(yùn)用順序表和鏈表的特點(diǎn)解決實(shí)際應(yīng)用問題。線性表（LinearList）是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表有兩種基本存儲(chǔ)表示方法，即順序存儲(chǔ)表示和鏈表表示

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

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

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

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

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

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