【文章內容簡介】 eof(ElemType),整個線性表所占用存儲空間的大小為 : n*sizeof(ElemType) 其中 ,n表示線性表的長度。 a 1 LO C (A ) 0 a 2 LO C (A )+s iz e o f(E le m T y p e ) 1 線性表存儲空間 存儲地址 下標位置 ┇ ┇ a i LO C (A )+(i 1 )* s iz e o f(E le m T y p e ) i 1 ┇ ┇ a n LO C (A )+(n 1 )* s iz e o f(E le m T y p e ) n 1 ┇ ┇ ┇ LO C (A )+(M a x Size 1 )* s iz e o f(E le m T y p e ) M a x Size 1 順序表示意圖 在定義一個線性表的順序存儲類型時 ,需要定義一個數組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度 。 假定數組用 elem[MaxSize]表示 ,長度整型變量用length表示 ,并采用結構體類型表示 ,則元素類型為通用類型標識符 ElemType的線性表的順序存儲類型可描述如下 : typedef struct { ElemType elem[MaxSize]。 int length。 } SqList。 /*順序表類型 */ 其中 ,elem成員存放元素 ,length成員存放線性表的實際長度。 說明：由于 C/C++中數組的下標從 0開始，線性表的第 i個元素 ai存放順序表的第 i1位置上。為了清楚，我們 ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。 順序表基本運算的實現 一旦采用順序表存儲結構 ,我們就可以用 C/C++語言實現線性表的各種基本運算。為了方便 ,假設ElemType為 char類型 ,使用如下自定義類型語句 : typedef char ElemType。 (1)初始化線性表 InitList(L) 該運算的結果是構造一個空的線性表 L。 實際上只需將 length成員設置為 0即可 。 void InitList(SqList *amp。L) //引用型指針 { L=(SqList *)malloc(sizeof(SqList))。 /*分配存放線性表的空間 */ Llength=0。 } 本算法的時間復雜度為 O(1)。 (2)銷毀線性表 DestroyList(L) 該運算的結果是釋放線性表 L占用的內存空間 。 void DestroyList(SqList *amp。L) { free(L)。 } 本算法的時間復雜度為 O(1)。 (3)判定是否為空表 ListEmpty(L) 該運算返回一個值表示 L是否為空表 。 若 L為空表 ,則返回 1,否則返回 0。 int ListEmpty(SqList *L) { return(Llength==0)。 } 本算法的時間復雜度為 O(1)。 (4)求線性表的長度 ListLength(L) 該運算返回順序表 L的長度 。 實際上只需返回length成員的值即可 。 int ListLength(SqList *L) { return(Llength)。 } 本算法的時間復雜度為 O(1)。 (5)輸出線性表 DispList(L) 該運算當線性表 L不為空時 ,順序顯示 L中各元素的值 。 void DispList(SqList *L) { int i。 if (ListEmpty(L)) return。 for (i=0。iLlength。i++) printf(%c,Lelem[i])。 printf(\n)。 } 本算法中基本運算為 for循環(huán)中的 printf語句 ,故時間復雜度為 : O(Llength)或 O(n) (6)求某個數據元素值 GetElem(L,i,e) 該運算返回 L中第 i(1≤i≤ListLength(L))個元素的值 ,存放在 e中 。 int GetElem(SqList *L,int i,ElemType amp。e) { if (i1 || iLlength) return 0。 e=Lelem[i1]。 return 1。 } 本算法的時間復雜度為 O(1)。 (7)按元素值查找 LocateElem(L,e) 該運算順序查找第 1個值域與 e相等的元素的位序 。 若這樣的元素不存在 ,則返回值為 0。 int LocateElem(SqList *L, ElemType e) { int i=0。 while (iLlength amp。amp。 Lelem[i]!=e) i++。 if (i=Llength) return 0。 else return i+1。 } 本算法中基本運算為 while循環(huán)中的 i++語句 ,故時間復雜度為 : O(Llength)或 O(n) (8)插入數據元素 ListInsert(L,i,e) 該 運 算 在 順 序 表 L 的第 i 個位置(1≤i≤ListLength(L)+1)上插入新的元素 e。 思路：如果 i值不正確 ,則顯示相應錯誤信息；否則將順序表原來第 i個元素及以后元素均后移一個位置 ,騰出一個空位置插入新元素 ,順序表長度增 1。 int ListInsert(SqList *amp。L,int i,ElemType e) { int j。 if (i1 || iLlength+1) return 0。 i。 /*將順序表 邏輯位序 轉化為 elem下標即 物理位序 */ for (j=Llength。ji。j) Lelem[j]=Lelem[j1]。 /*將 elem[i]及后面元素后移一個位置 */ Lelem[i]=e。 Llength++。 /*順序表長度增 1*/ return 1。 } 對于本算法來說 ,元素移動的次數不僅與表長=n有關 ,而且與插入位置 i有關 :當 i=n+1時 ,移動次數為 0；當 i=1時 ,移動次數為 n,達到最大值。在線性表 sq中共有 n+1個可以插入元素的地方。假設pi(= )是在第 i個位置上插入一個元素的概率 ,則在長度為 n的線性表中插入一個元素時所需移動元素的平均次數為 : 因此插入算法的平均時間復雜度為 O(n)。 )(2)1(11)1(1111nOninninnini ip ???????? ?? ???? (9)刪除數據元素 ListDelete(L,i,e) 該運算刪除順序表 L的第 i(1≤i≤ListLength(L))個元素 。 思路：如果 i值不正確 ,則顯示相應錯誤信息；否則將線性表第 i個元素以后元素均向前移動一個位置 ,這樣覆蓋了原來的第 i個元素 ,達到刪除該元素的目的 ,最后順序表長度減 1。 int ListDelete(SqList *amp。L,int i,ElemType amp。e) { int j。 if (i1 || iLlength) return 0。 i。 /*將順序表邏輯位序轉化為 elem下標即物理位序 */ e=Lelem[i]。 for (j=i。jLlength1。j++) Lelem[j]=Lelem[j+1]。 /*將 elem[i]之后的元素前移一個位置 */ Llength。 /*順序表長度減 1*/ return 1。 } 對于本算法來說 ,元素移動的次數也與表長 n和刪除元素的位置 i有關 :當 i=n時 ,移動次數為 0；當 i=1時 ,移動次數為 n1。在線性表 sq中共有 n個元素可以被刪除。假設 pi(pi= )是刪除第 i個位置上元素的概率 ,則在長度為 n的線性表中刪除一個元素時所需移動元素的平均次數為 : = 因此刪除算法的平均時間復雜度為 O(n)。 )(2 1)(1)(11nOninninpninii ?????? ????n1 例 設計一個算法 ,將 x插入到一個有序(從小到大排序 )的線性表 (順序存儲結構即順序表 )的適當位置上 ,并保持線性表的有序性 。 解 :先通過比較在順序表 L中找到存放 x的位置 i,然后將 x插入到 [i]中 ,最后將順序表的長度增 1。 void Insert(SqList *amp。L,ElemType x) { int i=0,j。 while (iLlength amp。amp。 Lelem[i]x) i++。 for (j=Llength1。j=i。j) Lelem[j+1]=Lelem[j]。 Lelem[i]=x。 Llength++。 } 例 設計一個算法 ,將兩個元素有序 (從小到大 )的順序表合并成一個有序順序表 。 思路 :將兩個順序表進行二路歸并 。 例如 : 順序表 p:1,3,5 ←i 掃描 p 順序表 q:2,4,10,20 ←j 掃描 q 歸并到順序表 r中 ← k記錄 r中元素個數 1(i=0) ? 2(j=0) ? 將 1(i=1)插入 r(k=1) 3(i=1) ? 2(j=0) ?將 2(j=1)插入 r(k=2) 3(i=1) ? 4(j=1) ?將 3(i=2)插入 r(k=3) 5(i=2) ? 4(j=1) ?將 4(j=2)插入 r(k=4) 5(i=2) ? 10(j=2) ?將 5(j=3)插入 r(k=5) 將 q中余下元素插入 r中 。 SqList *merge(SqList *p, SqList *q) { SqList *r。 int i=0,j=0,k=0。 r=(SqList *)malloc(sizeof(SqList))。 while (iplength amp。amp。 jqlength) { if (pelem[i]q elem[j]) { r elem [k]=p elem [i]。 i++。k++。 } else { r elem[k]=q elem[j]。 j++。k++。 } } while (iplength) { relem[k]=pelem[i]。 i++。k++。 } while (jqlength) { relem[k]=qelem[j]。 j++。k++。 } rlength=k。 /*或 plength+qlength*/ return(r)。 } 例 已知長度為 n的線性表 A采用順序存儲結構 ,編寫一個時間復雜度為 O(n)、 空間復雜度為 O(1)的算法 ,該算法刪除線性表中所有值為 item的數據元素 。 解 :用 k記錄順序表 A中等于 item的元素個數 ,邊掃描 A邊統計 k,并將不為 item的元素前移 k個位置 ,最后修改 A的長度 。 對應的算法如下 : void delnode(SqList amp。A,ElemType i