1、.第2章線性表、2.1線性表的基本概念、2.2線性表的順序記憶、2.3線性表的鏈接記憶、2.4線性表的應(yīng)用、本章總結(jié)、2.5線性表、2.1線性表的基本概念、2.1.1線性表的定義、2.1.2線性表的定義線性表將相同的特性包含在該排列中的元素的個數(shù)稱為線性表的長度，用n表示，n0。 如果n=0，則表示線性表是空表，表示該表不包含元素。 把序列中的第I個(I表示比特順序)的元素設(shè)為ai(1in )。 線性表的一般表示為： (a1、a2、ai、ai 1、an )，其中a-1是第一個元素，也稱為報頭元素，a-2是第二個元素，an是最后一個元素，也稱為頁腳元素。 例如，在線性表(1，4，3，2，8，10

2、 )中，1是報頭元素，10是頁腳元素。 2.1.2線性表的運算線性表的基本運算為： (1)，初始化線性表InitList(ilength=0本算法的時間復(fù)雜度為O(1)。 (4)求線性表的長度ListLength(L )的這個運算返回順序表l的長度。 實際上，它只返回length成員的值。 智能長度(sqlist * l ) 返回(l-length )； 本算法的時間復(fù)雜度為O(1)。 輸出(5)線性表DispList(L )該運算在線性表l不是空的情況下，依次顯示l中的各要素的值。 void DispList(SqList *L) int i； 列表空間(l )返回； for (i=0； i

3、length； I )打印(“% c”，L-datai )； printf(n )； 由于本算法的基本運算是for循環(huán)中的printf語句，所以時間復(fù)雜度為： O(L-length )或O(n ) .(6)求某個數(shù)據(jù)要素值GetElem(L，I，e )的運算是l中的第I個(1Ilis int GetElem(SqList *L，int i，ElemType )本算法的時間復(fù)雜度為O(1)。 按(7)要素值檢索LocateElem(L，e )的運算順序，檢索第1個值域與e相等的要素的順序。 如果這種元素不存在，返回值為0。 int LocateElem(SqList *L，ElemType e)

4、 int i=0； while (ilength )，因為在本算法中基本運算是while循環(huán)中的I語句，所以時間復(fù)雜度插入了： O(L-length )或O(n ) .(8)數(shù)據(jù)元素ListInsert(L，I，e )，此運算是序列想法：如果I的值不正確，則顯示相應(yīng)的錯誤信息，否則，將順序表的原第I個元素及其后的元素移動到一個位置，將空位置插入到新元素中，將順序表的長度增加1。 在本算法中，要素移動的次數(shù)不僅是表長度L.length=n，而且在關(guān)于插入位置I的：是i=n 1時，移動次數(shù)為0； 在i=1的情況下，移動次數(shù)為n，達到最大值。 線性表sq中，可以插入要素的地方有n 1處。 如果pi(

5、=)是在第I個位置插入元素的概率，則由于向長度為n的線性表中插入元素時需要的移動元素的平均次數(shù)為：所以插入算法的平均時間的復(fù)雜度為O(n )。 (9)刪除數(shù)據(jù)元素ListDelete(L，I，e )，并且刪除順序表l中的第I個(1Ilistlength(l ) )元素。 想法：如果I的值不正確，則顯示相應(yīng)的錯誤消息，否則將線性表中第I個要素以后的要素先移動一個位置，以實現(xiàn)復(fù)蓋原始第I個要素并刪除該要素的目的，最后將順序表的長度減1。 在.int ListDelete(SqList * ，邏輯位順序1 i i 1 n MaxSize，本算法中，在元素的移動次數(shù)也是對于表長度n和刪除元素的位置I，

6、在：i=n的情況下，移動次數(shù)為0； 在i=1的情況下，移動次數(shù)為n-1。 線性表sq中可以刪除n個要素。 假設(shè)pi(pi=)是刪除第I個位置的元素的概率，則根據(jù)刪除算法的平均時間復(fù)雜度為O(n )，因為從長度為n的線性表中刪除元素時所需的移動元素的平均次數(shù)為：=。例2.2設(shè)計了一種算法，在規(guī)則(從小到大)線性表(順序記憶結(jié)構(gòu)，順序表)的適當(dāng)位置插入x，以保持線性表的規(guī)則性。解：首先在序列表l中找到存儲x的位置I，接著將x插入L.datai，最后將序列表的長度增加1。 檢索void Insert(SqList * ，插入位置，在元素之后移動位置，邏輯位順序1 i i 1 n MaxSize，情況

7、2.3設(shè)計算法，將兩個元素順序(從小到大)的順序表合并成一個順序表。 解想法：把兩個順序表總結(jié)成兩個。 在順序表r中匯總在k記錄r的元素數(shù)1(I=0)2(j=0)r(k=1)3(i=1)2(j=0)中插入1(j=1)在r(k=2)3(I=1)4(j=1)中插入3 (I=2) r (k=3)。 順序表p:1 3 5、I、順序表q:2410、j、順序表r:1、k、和SqList *merge(SqList *p、SqList *q) SqList *r； int i=0，j=0，k=0； r=(sqlist * ) malloc (sizeof (sqlist ) )； while (ile le

8、ngth ) while (ile length ) r-data k =p-data I ； I； k； PS (jslength ) r-data k =q-data j ； j； k； r-length=k； /*或p-length q-length*/return(r) ，例2.4已知長度n的線性表a采用順序記憶結(jié)構(gòu)，創(chuàng)建時間復(fù)雜度為O(n )、空間復(fù)雜度為O(1)的算法，線性表的所有值都刪除item的數(shù)據(jù)元素。 解：用k記錄順序表a中的等于item的元素的數(shù)量，掃描a的同時合計k，將非item的元素前進k個位置，最后修改a的長度。 對應(yīng)的算法為：void delnode1(SqLis

9、t /*順序表a的長度為k*/，算法1 :類似于順序表的構(gòu)建，void delnode2(SqList /*順序表a的長度減少*。 算法只使用I、k兩個臨時變量，空間復(fù)雜度為O(1)。 2.3線性表的鏈接存儲，2.3.1線性表的鏈接存儲-鏈接表，2.3.2單鏈接表的基本運算的實現(xiàn)，2.3.3雙鏈接表，2.3.4循環(huán)鏈接表，2.3.5靜態(tài)鏈接表，2.3.1線性表的鏈接存儲-鏈接存儲中，各存儲節(jié)點中存儲要素自身的信息(數(shù)據(jù)通過不僅包括前一個節(jié)點而且包含元件之間的邏輯關(guān)系的信息，即前一節(jié)點包含后續(xù)節(jié)點的地址信息的情況稱為指針域，就可以容易地通過前一節(jié)點的指針域找到后續(xù)節(jié)點的位置，從而提高數(shù)據(jù)檢索速度

10、通常，每個節(jié)點具有一個或多個此類指針域。 如果節(jié)點的指針域不需要節(jié)點，則只有該值為空，并且用常數(shù)NULL表示。因為順序表的各要素最多有一個前驅(qū)動要素和一個后續(xù)要素，即數(shù)據(jù)要素之間有一對一的邏輯關(guān)系，所以在進行連鎖存儲的情況下，最簡單最常見的方法是：在各節(jié)點中包含數(shù)據(jù)區(qū)域，只設(shè)置一個指向其后的節(jié)點的指針區(qū)域而構(gòu)成的連鎖、開頭節(jié)點的鏈表的圖像，在線性表的鏈存儲中，為了容易實現(xiàn)插入和刪除算法，在各鏈表中帶有開頭節(jié)點，用開頭節(jié)點的指針唯一地識別該鏈表。在單鏈表中，因為每個節(jié)點只包含一個指向后續(xù)節(jié)點的指針，所以在訪問一個節(jié)點后，只能訪問后續(xù)節(jié)點，不能訪問其前驅(qū)節(jié)點。 另一種方法是：在每個節(jié)點上包括數(shù)值字

11、段，此外，設(shè)置了兩個指針字段來指示其前一節(jié)點和后一節(jié)點的鏈表，稱為線性雙向鏈表，簡稱為雙鏈表。 在、開頭節(jié)點的雙鏈表的圖像、雙鏈表中，由于各節(jié)點包含指向后續(xù)節(jié)點的指針和指向開頭節(jié)點的指針雙方，所以可以在訪問一個節(jié)點后，依次向后訪問各節(jié)點，也可以依次向前訪問各節(jié)點。 另外，在雙鏈表的特征中，假定各節(jié)點類型由鏈列表表示，應(yīng)該包含存儲元素的數(shù)據(jù)字段，在此用data表示，該類型由通用類型標(biāo)識符ElemType表示，存儲后續(xù)元素的位置鏈接列表類型定義為： typedef struct LNode /*，鏈接列表節(jié)點類型*/ ElemType data； 結(jié)構(gòu)節(jié)點*下一步； /*到下一個節(jié)點*/ Link

12、List；2.3.2鏈表基本運算的實現(xiàn)，1 .在制作鏈表之前，研究鏈表的制作方法。 例如，假設(shè)從包含n個數(shù)據(jù)的數(shù)組創(chuàng)建單鏈表。 創(chuàng)建單鏈表的常用方法是從空表中讀取字符串?dāng)?shù)組a的字符，生成新的節(jié)點，將讀取的數(shù)據(jù)存儲在新節(jié)點的數(shù)據(jù)字段中，將新節(jié)點插入當(dāng)前鏈表的報頭中，并且插入至最后。 使用插件法創(chuàng)建表的算法是：void createlistf (鏈接列表* ，i=0，i=1，i=2，i=3，head，使用插件法創(chuàng)建單鏈表的過程，head，head， 第一步驟：創(chuàng)建一個節(jié)點，第二步驟：i=0，新建一個a節(jié)點，插入一個頭節(jié)點后，第三步驟：i=1，新建一個d節(jié)點，插入一個頭節(jié)點后，第四步驟：i=2，新建

13、一個c節(jié)點在第五步驟：i=3、新建b節(jié)點并插入頭部節(jié)點后，第二步驟：i=1、通過尾插法創(chuàng)建鏈表是算法簡單的，但是生成的鏈表的節(jié)點順序與原始的數(shù)組元素的順序相反。 在想使兩者的順序一致的情況下，可以使用尾插法制作。 這種方法將新節(jié)點插入到當(dāng)前鏈表的末尾，因此必須始終添加末尾指針r以指向當(dāng)前鏈表的末尾節(jié)點。 使用尾插法制作表的算法為：void CreateListR(LinkList * /*終端節(jié)點next字段為NULL*/、b，c，d，a :i=0，i=1，I=，I=，3，h 使用、，末尾插入法生成鏈表的過程，2 .插入節(jié)點運算插入運算，將值x的新節(jié)點插入鏈表第I個節(jié)點的位置。 首先，在鏈表中

14、找到第i-1個節(jié)點，然后插入新節(jié)點。 鏈表插入節(jié)點的過程如下圖所示。 插入，節(jié)點映像，3 .刪除節(jié)點的運算刪除運算是刪除鏈表中第I個節(jié)點的運算。 首先，從鏈路列表中找到第i-1個節(jié)點，然后刪除后續(xù)節(jié)點。 刪除單鏈表的節(jié)點的步驟如下圖所示。 刪除，節(jié)點的映像.4 .線性表的基本運算實現(xiàn)(1)初始化線性表InitList(L )的運算，制作空的單一鏈表，即，制作1個磁頭節(jié)點。 void InitList(LinkList * ，(2)廢棄線性表DestroyList(L )，釋放單一鏈表l占有的存儲器區(qū)域。 也就是說，一個一個地釋放所有節(jié)點的空間。 void DestroyList(LinkLis

15、t * ，(3)線性表在空表ListEmpty(L )單一鏈表l中沒有數(shù)據(jù)節(jié)點時返回真，否則返回假。 英特爾列表* l (鏈接列表* l ) 返回(l-next=空)； 求出(4)線性表的長度ListLength(L )，則返回鏈接表l中的數(shù)據(jù)節(jié)點的數(shù)量。 英特爾列表長度(鏈路列表* l ) 鏈路列表* p=l； int i=0； p-next！=空) I； p=p-next； return(i) ，(5)輸出線性表DispList(L )逐一掃描鏈表l的各數(shù)據(jù)節(jié)點，顯示各節(jié)點的數(shù)據(jù)字段的值。 voidsdislist (鏈路列表* l ) 鏈路列表* p=l-next； PS！=null ) 打印( % c ，p-data )； p=p-next； printf(n )； ，(6)線性表l中具有指定位置的數(shù)據(jù)要素GetElem(L，I，int n=1； PS！=NULL ，(8)數(shù)據(jù)元素ListInsert(，if (p=NULL) return 0； 找不到排名為i-1的節(jié)點*/else /*找到排名為i-1的節(jié)點* p */ s=(鏈接列表* ) malloc (sizeof