1、線性表的存儲結構定義及基本操作線性表1的存儲結構和基本操作的定義。實驗目的：。掌握線性表的邏輯特征。掌握線性表順序存儲結構的特點。掌握序列表的基本 操作，掌握線性表的鏈式存儲結構的定義和基本操作，了解循環鏈表和雙鏈表的特點和基本操作，加深對序列存儲數據結構和鏈式存儲數據結構的理解。逐步培養解決實際問題的編程能力2,實驗內容：（1）基本實驗內容（序列表）：建立序列表，完成序列表的基本操作：初始化、插入、刪除、反轉、 輸出、銷毀、設置空表、查找表長、查找元素、判斷線性表是否為空； 1。問題描述：使用序列表，設計了一組輸入數據（假設為一組整數）， 可以對序列表執行以下操作：。創建新的序列表，實現動態

2、空間分配 的初始化；。根據節點在序列表中的位置插入一個新節點（位置插入），或者根據給定的值插入（值插入）以形成一個有序的序列表；。根據節點在序列表中的位置刪除一個節點（位置刪除），或者根據 給定的值刪除相應的第一個節點，或者刪除所有具有指定值的節點(值刪除)；。用最小空間反轉序列表元素；。實現序列表中每個元素的輸出；。徹底銷毀序列線性表并回收分配的空間；。刪除順序線性表的所有 元素，并將其設置為空表；。返回其數據元素的數量；。按序列號搜索。根據序列表的特點，可以在第I個節點隨機直接訪問序列表，查找元素的值并返回搜索結果。按值查找。根據給定數據元素的值，您只能順序比較，找到元素 的位置，并返回搜

3、索結果。判斷序列表中是否有元素，并返回判斷結 果；編寫主程序調用不同的算法 2.實現要求：對序列表運算必須寫成C(C+)語言函數，組合成模塊化形式，并且 每個算法的實現必須從時間復雜度和空間復雜度兩方面進行評估；。初始化算法”的運算結果：構造一個空的序列線性表對序列表的空 間進行動態管理，實現存儲空間的動態分配、恢復和增加。位置插入算法”的初始條件是：序列線性表L已經存在，給定的元 素位置為1, 1W1列表長度(L)+1 ;操作結果:在l中的I位置前插入一 個新的數據元素e,并將l的長度加1;。位置刪除算法”的初始條件是序列線性表L已經存在，1W1列表 長度(L);操作結果 刪除l的第I個數據

4、元素，用e返回其值，并將l 的長度減1;反向算法”的初始條件是序列線性表L已經存在；的運算結果：順序交換L的每個數據元素，交換順序表的元素以使用 最少的額外空間；線性表和基本運算的存儲結構定義。 輸出算法”的初始條件：序列線性表L已經存在； 運算結果:順序輸出L的每個數據元素； 銷毀算法”初始條件:順序線 性表L已經存在；操作結果：銷毀順序線性表1;空表算法”初始條件:順序線性表L已經存在；操作結果：將L重置 為空表；裳長算法”初始條件:順序線性表L已經存在；操作結果:返回數據元 素的個數，以L為單位；按序列號搜索算法”初始條件:順序線性表L已經存在，元素位置為1, iwi WLisfengt

5、h(L)運算結果:返回L按值搜索算法”初始條件：順序 線性表L已經存在，元素值為e;操作結果：返回數據元素值為E的 元素位置；。裝空判斷算法”的初始條件：順序線性表L已經存在；操 作結果:如果l是空表，返回真，否則返回假；分析:修改輸入數據，期待輸出，驗證輸出結果，加深對相關算法的 理解(2)基本實驗內容(鏈表)：建立一個鏈表來完成鏈表(帶標題的節點)的基本操作：建立鏈表、插 入、刪除、搜索、輸出、查找前導、查找后繼和合并兩個有序鏈表的其他基本操作包括銷毀鏈表、將鏈表設置為空表、查找鏈表的長 度、獲取某個位置的節點內容以及搜索節點 1.問題描述：使用線性表的鏈式存儲結構來設計一組輸入數據（假設

6、是一組整數），它可以對單個鏈表執行以下操作：。用標題節點初始化空鏈表；。創建單個鏈表就是從頭創建一個鏈表，即逐個輸入每個節點的數據，并建立前后鏈接的關系。它也分為輸入 N個元素值的逆序（插入 表頭）和輸入N個元素值的正序（插入表尾）。插入的節點可以根據給定的位置插入 （位置插入），或者它們可以 根據節點的值插入到已知的鏈表中（值插入）,并且節點的數據保持原 始的升序以形成有序的鏈表。刪除節點可以根據給定的位置刪除（位置刪除），也可以刪除鏈表 中所有值為搜索對象的節點（值刪除）；。輸出單個鏈表的內容是顯示鏈表中每個節點的數據，直到鏈表的最后一個節點；編寫主程序調用不同的算法其他運算算法的描述2.

7、實現要求：對鏈表的每一個操作都必須寫成 C（C+）語言函數，組合成模塊形 式，并根據每個算法實現的時間復雜度和空間復雜度進行評估。初始化算法”的運算結果：構造一個空的線性表L,生成一個頭節 點，并使L指向該頭節點；建立鏈表算法”的初始條件是：空鏈存在； 運算結果:選擇逆序或正序的方法，建立一個鏈表，返回完整的結果； 鏈表（位置）插入算法”的初始條件是已知存在單個鏈表 L;的運算結果：在頭節點的單鏈線性表l的位置I之前插入元素e;列表（位置）刪除算法”的初始條件是已知單個列表L存在；的運算結果：在頭節點的單鏈線性表l中，刪除第I個元素，其值由e 返回；輸出算法”初始條件：鏈表l已經存在；操作結果

8、：依次輸出鏈 表各節點的值；存儲結構的定義和基本操作2線性表（3）擴展實驗內容（序列表）檢查前驅元素、檢查后續元素、合并序列表等。1.問題描述：。根據給定元素的值計算前驅元素；。根據給定元素的值，找到后續 元素；。合并兩個構建的序列表。如果原始線性表中的元素沒有按降序排 列，則要求合并結果仍然是有序的（有序合并）；對于原始順序表中無 序排列的元素組合，只完成了 A=A UB（無序組合），并且同一數據元 素只需要出現一次。修改主程序以調用不同的算法 2.實施要求：。檢查前驅元素算法”的初始條件：序列線性表L已經存在；操作結果：如果數據元素存在且不是第一個，則返回前一個，否則操作失敗；檢查后續元素

9、算法”的初始條件是序列線性表L已經存在； 的操作結果：如果數據元素存在且不是最后一個，則返回后繼，否則 操作失敗；無序合并算法”的初始條件是線性表1a和1b是已知的；運算結果:線性表Lb中的所有數據元素都被插入到La中，但La中 沒有；,宥序合并算法”的初始條件：已知線性表La和Lb中的數據元素以 非遞減的值順序排列；運算結果如下：通過合并La和Lb得到一個新 的線性表LC,并且LC的數據元素也按值的非遞減順序排列；（4）擴 展實驗內容（鏈表）1。問題描述：。為了找到前體節點，在單個鏈表中搜索其當前節點的后繼節點值 為給定值，并將當前節點返回；。查找后繼節點是基于給定節點的值，在單個鏈表中搜索

10、其當前節 點值為給定值，并返回后繼節點；兩個有序鏈表的合并是將兩個單鏈 表的節點依次插入到第三個單鏈表中，以保持節點的有序性。2.實施要求：。尋找前驅算法”的初始條件：線性表L已經存在；的運算結果：如果cur_e是l的數據元素且不是第一個，則pre_e用于 返回其前身；尋找后繼算法”的初始條件是線性表L已經存在；的運算結果：如果cur_e是l的數據元素而不是最后一個，則 next_e 用于返回其后繼元素；兩個有序鏈表合并算法的初始條件”線性形式鏈的線性表La和Lb 的元素按值的非遞減順序排列；操作結果：合并La和Lb以獲得新的 單個鏈表線性表順序存儲結構的定義及其基本操作參考程序（順序表）（1

11、）文件1：公開使用。h是一個常用的常量定義和系統函數調用聲明， 在未來的幾乎所有實驗中都將涉及到它。# include # include# include/* malloc(), etc */ #include /* INT_MAX , etc */# include/* eof (= "成 F6), NULL */# include/* atoi()*/# include/* eof()*/# include/* floor() ， ceil() ， Abs() */3線性表存儲結構定義和基本操作# include/* exit()*/*函數結果狀態代碼*/#定義TRUE 1 #

12、定義FALSE 0 #定義ok 1 #定義錯誤0# 定義不可行-1/* #定義OVERFLOW-2 ,因為在數學中 OVERFLOW 的值已定義為3。h,因此刪除該行*/typedef int狀態；/*狀態是函數的類型，它的值是 函數結果狀態代碼，如確定等*/type define布爾值；/*布爾是布爾類型。它的值為TRUE或FALSE */(2)文件 2: seqlistdef.h表示# Define list _ init _ size10/* 初始分配量 */# Define LISTINGRENT 2/* 線性表存儲空間分配增量*/typedefstruct elem type * e

13、lem; /*存儲空間的基址*/int length ; /*當前長度*/ intlistsize。/* 當前在 sizeof(ElemType) */ SQLIST 中分配的存儲容量；(3)文件3:線性表順序存儲結構的基本實驗算法定義狀態列表初始化_Sq(SqList &L) /*算法2。3 */ /*運算結果：構造一個空的順序線性表 */ l . elem =(elem type *)malloc(list _ init _ size * sizeof(elem type); 如果(! l . elem)出口(OVERFLOW)。/*存儲分配失敗*/l . length = 0 ;

14、 /*空表長度為0 */l . list size = list _ init _ size; /* 初始存儲容量 */returnok; statuslistinsert _ sq(SQL & l, inti, elemtype)/*算法 2。4 */ /* 初始條 件:順序線性表l已經存在，1WI <list length(l)+1 */*運算結果:在l中的I位置前插入新的數據元素e, l長度加1 */ElemType *newbase, *q , * p; * q , * p;if(ILl。length+1) /* i 值非法*/return error;如果(l.leng

15、th > = l.listsize)/*當前存儲空間已滿，增加分配*/new base =(elem type *)real loc(l . elem , (l . list size+list increment)*size of(elem type);女果(! new base)exit(OVERFLOW) ; /* 存儲分配失敗 */l . elem = new base ; /* 新基址*/l . list size+= list increment. /* 增加存儲容量 */q = l . elem+I-1 ; /* q 是插入位置處線性表(p = l.elem+l.length-1)的存 儲結構定義和基本操作*/4;p > = q; -p)/*在其右移后插入位置和元素*/*(p+1)= * p ;* q = e; /* 插入 e */+ l . length; /* 表長度增加了 1 */returnok; statuslisstdelete _ sq(SQL & | inti, elemtype * e)/*算法