線性表的存儲結(jié)構(gòu)定義及基本操作.doc

線性表的存儲結(jié)構(gòu)定義及基本操作一、實驗目的：. 掌握線性表的邏輯特征. 掌握線性表順序存儲結(jié)構(gòu)的特點，熟練掌握順序表的基本運算. 熟練掌握線性表的鏈式存儲結(jié)構(gòu)定義及基本操作. 理解循環(huán)鏈表和雙鏈表的特點和基本運算. 加深對順序存儲數(shù)據(jù)結(jié)構(gòu)的理解和鏈式存儲數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實際問題的編程能力二、實驗內(nèi)容：（一）基本實驗內(nèi)容（順序表）：建立順序表，完成順序表的基本操作：初始化、插入、刪除、逆轉(zhuǎn)、輸出、銷毀, 置空表、求表長、查找元素、判線性表是否為空；1問題描述：利用順序表,設(shè)計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)樞虮磉M行如下操作：. 創(chuàng)建一個新的順序表，實現(xiàn)動態(tài)空間分配的初始化；. 根據(jù)順序表結(jié)點的位置插入一個新結(jié)點(位置插入)，也可以根據(jù)給定的值進行插入(值插入)，形成有序順序表；. 根據(jù)順序表結(jié)點的位置刪除一個結(jié)點(位置刪除)，也可以根據(jù)給定的值刪除對應的第一個結(jié)點，或者刪除指定值的所有結(jié)點(值刪除)；. 利用最少的空間實現(xiàn)順序表元素的逆轉(zhuǎn)；. 實現(xiàn)順序表的各個元素的輸出；. 徹底銷毀順序線性表，回收所分配的空間；. 對順序線性表的所有元素刪除，置為空表；. 返回其數(shù)據(jù)元素個數(shù)；. 按序號查找，根據(jù)順序表的特點，可以隨機存取，直接可以定位于第i 個結(jié)點，查找該元素的值，對查找結(jié)果進行返回；. 按值查找，根據(jù)給定數(shù)據(jù)元素的值，只能順序比較，查找該元素的位置，對查找結(jié)果進行返回；. 判斷順序表中是否有元素存在，對判斷結(jié)果進行返回；. 編寫主程序，實現(xiàn)對各不同的算法調(diào)用。2實現(xiàn)要求：對順序表的各項操作一定要編寫成為C（C+）語言函數(shù)，組合成模塊化的形式，每個算法的實現(xiàn)要從時間復雜度和空間復雜度上進行評價；. “初始化算法”的操作結(jié)果：構(gòu)造一個空的順序線性表。對順序表的空間進行動態(tài)管理，實現(xiàn)動態(tài)分配、回收和增加存儲空間；. “位置插入算法” 的初始條件：順序線性表L 已存在，給定的元素位置為i，且1iListLength(L)+1 ；操作結(jié)果：在L 中第i 個位置之前插入新的數(shù)據(jù)元素e，L 的長度加1；. “位置刪除算法”的初始條件：順序線性表L 已存在，1iListLength(L) ；操作結(jié)果：刪除L 的第i 個數(shù)據(jù)元素，并用e 返回其值，L 的長度減1 ；. “逆轉(zhuǎn)算法”的初始條件：順序線性表L 已存在；操作結(jié)果：依次對L 的每個數(shù)據(jù)元素進行交換，為了使用最少的額外空間，對順序表的元素進行交換；. “輸出算法”的初始條件：順序線性表L 已存在；操作結(jié)果：依次對L 的每個數(shù)據(jù)元素進行輸出；. “銷毀算法”初始條件：順序線性表L 已存在；操作結(jié)果：銷毀順序線性表L；. “置空表算法”初始條件：順序線性表L 已存在；操作結(jié)果：將L 重置為空表；. “求表長算法”初始條件：順序線性表L 已存在；操作結(jié)果：返回L 中數(shù)據(jù)元素個數(shù)；. “按序號查找算法”初始條件：順序線性表L 已存在，元素位置為i，且1iListLength(L)操作結(jié)果：返回L 中第i 個數(shù)據(jù)元素的值. “按值查找算法”初始條件：順序線性表L 已存在，元素值為e；操作結(jié)果：返回L 中數(shù)據(jù)元素值為e 的元素位置；. “判表空算法”初始條件：順序線性表L 已存在；操作結(jié)果：若L 為空表，則返回TRUE，否則返回FALSE；分析: 修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結(jié)果，加深對有關(guān)算法的理解。(二）基本實驗內(nèi)容（鏈表）：建立單鏈表，完成鏈表（帶表頭結(jié)點）的基本操作：建立鏈表、插入、刪除、查找、輸出、求前驅(qū)、求后繼、兩個有序鏈表的合并操作。其他基本操作還有銷毀鏈表、將鏈表置為空表、求鏈表的長度、獲取某位置結(jié)點的內(nèi)容、搜索結(jié)點。1 問題描述：利用線性表的鏈式存儲結(jié)構(gòu),設(shè)計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)捂湵磉M行如下操作：. 初始化一個帶表頭結(jié)點的空鏈表；. 創(chuàng)建一個單鏈表是從無到有地建立起一個鏈表，即一個一個地輸入各結(jié)點數(shù)據(jù)，并建立起前后相互鏈接的關(guān)系。又分為逆位序(插在表頭)輸入n 個元素的值和正位序(插在表尾)輸入n 個元素的值；. 插入結(jié)點可以根據(jù)給定位置進行插入（位置插入），也可以根據(jù)結(jié)點的值插入到已知的鏈表中（值插入），且保持結(jié)點的數(shù)據(jù)按原來的遞增次序排列，形成有序鏈表。. 刪除結(jié)點可以根據(jù)給定位置進行刪除（位置刪除），也可以把鏈表中查找結(jié)點的值為搜索對象的結(jié)點全部刪除（值刪除）；. 輸出單鏈表的內(nèi)容是將鏈表中各結(jié)點的數(shù)據(jù)依次顯示，直到鏈表尾結(jié)點；. 編寫主程序，實現(xiàn)對各不同的算法調(diào)用。其它的操作算法描述略。2實現(xiàn)要求：對鏈表的各項操作一定要編寫成為C（C+）語言函數(shù)，組合成模塊化的形式，還要針對每個算法的實現(xiàn)從時間復雜度和空間復雜度上進行評價。. “初始化算法”的操作結(jié)果：構(gòu)造一個空的線性表L，產(chǎn)生頭結(jié)點,并使L 指向此頭結(jié)點；. “建立鏈表算法” 初始條件：空鏈存在；操作結(jié)果：選擇逆位序或正位序的方法，建立一個單鏈表，并且返回完成的結(jié)果；. “鏈表（位置）插入算法”初始條件：已知單鏈表L 存在；操作結(jié)果：在帶頭結(jié)點的單鏈線性表L 中第i 個位置之前插入元素e；. “鏈表（位置）刪除算法”初始條件：已知單鏈表L 存在；操作結(jié)果：在帶頭結(jié)點的單鏈線性表L 中，刪除第i 個元素,并由e 返回其值；. “輸出算法”初始條件：鏈表L 已存在；操作結(jié)果：依次輸出鏈表的各個結(jié)點的值；（三）擴展實驗內(nèi)容（順序表）查前驅(qū)元素、查后繼元素、順序表合并等.1問題描述：. 根據(jù)給定元素的值，求出前驅(qū)元素；. 根據(jù)給定元素的值，求出后繼元素；. 對已建好的兩個順序表進行合并操作，若原線性表中元素非遞減有序排列,要求合并后的結(jié)果還是有序(有序合并）；對于原順序表中元素無序排列的合并只是完成A=AB（無序合并)，要求同樣的數(shù)據(jù)元素只出現(xiàn)一次。. 修改主程序，實現(xiàn)對各不同的算法調(diào)用。2實現(xiàn)要求：. “查前驅(qū)元素算法” 初始條件：順序線性表L 已存在；操作結(jié)果：若數(shù)據(jù)元素存在且不是第一個，則返回前驅(qū)，否則操作失??；. “查后繼元素算法” 初始條件：順序線性表L 已存在；操作結(jié)果：若數(shù)據(jù)元素存在且不是最后一個，則返回后繼，否則操作失?。? “無序合并算法”的初始條件：已知線性表La 和Lb；操作結(jié)果：將所有在線性表Lb 中但不在La 中的數(shù)據(jù)元素插入到La 中；. “有序合并算法”的初始條件： 已知線性表La 和Lb 中的數(shù)據(jù)元素按值非遞減排列；操作結(jié)果： 歸并La 和Lb 得到新的線性表Lc,Lc 的數(shù)據(jù)元素也按值非遞減排列；（四）擴展實驗內(nèi)容（鏈表）1問題描述：. 求前驅(qū)結(jié)點是根據(jù)給定結(jié)點的值，在單鏈表中搜索其當前結(jié)點的后繼結(jié)點值為給定的值，將當前結(jié)點返回；. 求后繼結(jié)點是根據(jù)給定結(jié)點的值，在單鏈表中搜索其當前結(jié)點的值為給定的值，將后繼結(jié)點返回；. 兩個有序鏈表的合并是分別將兩個單鏈表的結(jié)點依次插入到第3 個單鏈表中，繼續(xù)保持結(jié)點有序；2實現(xiàn)要求：. “求前驅(qū)算法”初始條件: 線性表L 已存在；操作結(jié)果: 若cur_e 是L 的數(shù)據(jù)元素,且不是第一個,則用pre_e 返回它的前驅(qū)；. “求后繼算法”初始條件: 線性表L 已存在；操作結(jié)果: 若cur_e 是L 的數(shù)據(jù)元素,且不是最后一個,則用next_e 返回它的后繼；. “兩個有序鏈表的合并算法”初始條件: 線性表單鏈線性表La 和Lb 的元素按值非遞減排列；操作結(jié)果:歸并La 和Lb 得到新的單鏈表。線性表的順序存儲結(jié)構(gòu)的定義及其基本操作的參考程序（順序表）(1) 文件1： pubuse. h 是公共使用的常量定義和系統(tǒng)函數(shù)調(diào)用聲明，以后每個實驗中幾乎都涉及到此文件。#include#include#include /* malloc()等*/#include /* INT_MAX 等*/#include /* EOF(=Z 或F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */* 函數(shù)結(jié)果狀態(tài)代碼*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因為在math. h 中已定義OVERFLOW 的值為3,故去掉此行*/typedef int Status； /* Status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK 等*/typedef int Boolean； /* Boolean 是布爾類型,其值是TRUE 或FALSE */(2) 文件2：seqlistDef. h 進行線性表的動態(tài)分配順序存儲結(jié)構(gòu)的表示#define LIST_INIT_SIZE 10 /* 線性表存儲空間的初始分配量*/#define LISTINCREMENT 2 /* 線性表存儲空間的分配增量*/typedef structElemType *elem； /* 存儲空間基址*/int length； /* 當前長度*/int listsize； /* 當前分配的存儲容量(以sizeof(ElemType)為單位) */SqList；(3)文件3：seqlistAlgo. h 進行線性表順序存儲結(jié)構(gòu)的基本實驗算法定義Status ListInit_Sq(SqList &L) /* 算法2. 3 */ /* 操作結(jié)果：構(gòu)造一個空的順序線性表*/L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)；if(!L. elem)exit(OVERFLOW)； /* 存儲分配失敗*/L. length=0； /* 空表長度為0 */L. listsize=LIST_INIT_SIZE； /* 初始存儲容量*/return OK；Status ListInsert_Sq(SqList &L,int i,ElemType e) /* 算法2. 4 */ /* 初始條件：順序線性表L 已存在，1iListLength(L)+1 */* 操作結(jié)果：在L 中第i 個位置之前插入新的數(shù)據(jù)元素e，L 的長度加1 */ElemType *newbase,*q,*p；if(iL. length+1) /* i 值不合法*/return ERROR；if(L. length=L. listsize) /* 當前存儲空間已滿,增加分配*/newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType)；if(!newbase)exit(OVERFLOW)； /* 存儲分配失敗*/L. elem=newbase； /* 新基址*/L. listsize+=LISTINCREMENT； /* 增加存儲容量*/q=L. elem+i-1； /* q 為插入位置*/for(p=L. elem+L. length-1；p=q；-p) /* 插入位置及之后的元素右移*/*(p+1)=*p；*q=e； /* 插入e */+L. length； /* 表長增1 */return OK；Status ListDelete_Sq(SqList &L,int i,ElemType *e) /* 算法2. 5 */ /* 初始條件：順序線性表L 已存在，1iListLength(L) */* 操作結(jié)果：刪除L 的第i 個數(shù)據(jù)元素，并用e 返回其值，L 的長度減1 */ElemType *p,*q；if(iL. length) /* i 值不合法*/return ERROR；p=L. elem+i-1； /* p 為被刪除元素的位置*/*e=*p； /* 被刪除元素的值賦給e */q=L. elem+L. length-1； /* 表尾元素的位置*/for(+p；p=q；+p) /* 被刪除元素之后的元素左移*/*(p-1)=*p；L. length-； /* 表長減1 */return OK；Status ListReverse_Sq(SqList &L) /* 初始條件：順序線性表L 已存在*/* 操作結(jié)果：依次對L 的數(shù)據(jù)元素成對交換*/ElemType t；int i；for(i=0；iL. length/2；i+)t=L. elemi； L. elemi= L. elemL. length-i-1； L. elemL. length-i-1=t； printf(n)；return OK；Status ListPrint_Sq(SqList L) /* 初始條件：順序線性表L 已存在*/* 操作結(jié)果：依次對L 的數(shù)據(jù)元素輸出*/int i；printf(n)；for(i=0；iL. length；i+)printf(%d , L. elemi)；return OK； (4)文件4：seqlistUse. cpp 進行線性表順序存儲結(jié)構(gòu)的基本算法驗