【正文】 。 } 例 已知長(zhǎng)度為 n的線性表 A采用順序存儲(chǔ)結(jié)構(gòu) ,編寫(xiě)一個(gè)時(shí)間復(fù)雜度為 O(n)、 空間復(fù)雜度為 O(1)的算法 ,該算法刪除線性表中所有值為 item的數(shù)據(jù)元素 。 } rlength=k。 j++。k++。 } } while (iplength) { relem[k]=pelem[i]。 j++。k++。 jqlength) { if (pelem[i]q elem[j]) { r elem [k]=p elem [i]。 while (iplength amp。 int i=0,j=0,k=0。 例如 : 順序表 p:1,3,5 ←i 掃描 p 順序表 q:2,4,10,20 ←j 掃描 q 歸并到順序表 r中 ← k記錄 r中元素個(gè)數(shù) 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中 。 } 例 設(shè)計(jì)一個(gè)算法 ,將兩個(gè)元素有序 (從小到大 )的順序表合并成一個(gè)有序順序表 。 Lelem[i]=x。j=i。 Lelem[i]x) i++。 while (iLlength amp。 void Insert(SqList *amp。 )(2 1)(1)(11nOninninpninii ?????? ????n1 例 設(shè)計(jì)一個(gè)算法 ,將 x插入到一個(gè)有序(從小到大排序 )的線性表 (順序存儲(chǔ)結(jié)構(gòu)即順序表 )的適當(dāng)位置上 ,并保持線性表的有序性 。在線性表 sq中共有 n個(gè)元素可以被刪除。 /*順序表長(zhǎng)度減 1*/ return 1。j++) Lelem[j]=Lelem[j+1]。 for (j=i。 i。e) { int j。 int ListDelete(SqList *amp。 )(2)1(11)1(1111nOninninnini ip ???????? ?? ???? (9)刪除數(shù)據(jù)元素 ListDelete(L,i,e) 該運(yùn)算刪除順序表 L的第 i(1≤i≤ListLength(L))個(gè)元素 。在線性表 sq中共有 n+1個(gè)可以插入元素的地方。 /*順序表長(zhǎng)度增 1*/ return 1。 /*將 elem[i]及后面元素后移一個(gè)位置 */ Lelem[i]=e。ji。 i。L,int i,ElemType e) { int j。 思路：如果 i值不正確 ,則顯示相應(yīng)錯(cuò)誤信息；否則將順序表原來(lái)第 i個(gè)元素及以后元素均后移一個(gè)位置 ,騰出一個(gè)空位置插入新元素 ,順序表長(zhǎng)度增 1。 else return i+1。 Lelem[i]!=e) i++。 while (iLlength amp。 若這樣的元素不存在 ,則返回值為 0。 } 本算法的時(shí)間復(fù)雜度為 O(1)。 e=Lelem[i1]。 int GetElem(SqList *L,int i,ElemType amp。 printf(\n)。iLlength。 if (ListEmpty(L)) return。 (5)輸出線性表 DispList(L) 該運(yùn)算當(dāng)線性表 L不為空時(shí) ,順序顯示 L中各元素的值 。 int ListLength(SqList *L) { return(Llength)。 (4)求線性表的長(zhǎng)度 ListLength(L) 該運(yùn)算返回順序表 L的長(zhǎng)度 。 int ListEmpty(SqList *L) { return(Llength==0)。 (3)判定是否為空表 ListEmpty(L) 該運(yùn)算返回一個(gè)值表示 L是否為空表 。L) { free(L)。 (2)銷毀線性表 DestroyList(L) 該運(yùn)算的結(jié)果是釋放線性表 L占用的內(nèi)存空間 。 /*分配存放線性表的空間 */ Llength=0。 void InitList(SqList *amp。 (1)初始化線性表 InitList(L) 該運(yùn)算的結(jié)果是構(gòu)造一個(gè)空的線性表 L。 順序表基本運(yùn)算的實(shí)現(xiàn) 一旦采用順序表存儲(chǔ)結(jié)構(gòu) ,我們就可以用 C/C++語(yǔ)言實(shí)現(xiàn)線性表的各種基本運(yùn)算。 說(shuō)明：由于 C/C++中數(shù)組的下標(biāo)從 0開(kāi)始，線性表的第 i個(gè)元素 ai存放順序表的第 i1位置上。 } SqList。 假定數(shù)組用 elem[MaxSize]表示 ,長(zhǎng)度整型變量用length表示 ,并采用結(jié)構(gòu)體類型表示 ,則元素類型為通用類型標(biāo)識(shí)符 ElemType的線性表的順序存儲(chǔ)類型可描述如下 : typedef struct { ElemType elem[MaxSize]。 假定線性表的元素類型為 ElemType,則每個(gè)元素所占用存儲(chǔ)空間大小 (即字節(jié)數(shù) )為 sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為 : n*sizeof(ElemType) 其中 ,n表示線性表的長(zhǎng)度。 線性表的順序存儲(chǔ) 線性表的順序存儲(chǔ) —順序表 順序表基本運(yùn)算的實(shí)現(xiàn) 線性表的順序存儲(chǔ) —順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)就是 :把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)器中指定存儲(chǔ)位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中。 /*取 LB中第 i個(gè)數(shù)據(jù)元素賦給 e*/ if (!LocateElem(LA,e)) ListInsert(LC,++lena,e)。i=lenb。 /*求線性表的長(zhǎng)度 */ lenb=ListLength(LB)。 ListInsert(LC,i,e)。i=ListLength(LA)。 InitList(LC)。LC) { int lena,lenc,i。 解 :本算法思想是 :先初始化線性表 LC,將 LA的所有元素復(fù)制到 LC中 ,然后掃描線性表 LB,若 LB的當(dāng)前元素不在線性表 LA中 ,則將其插入到 LC中。 例 假設(shè)有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示 ,即線性表中的數(shù)據(jù)元素即為集合中的成員 。L,i,amp。L,i,e): 在 L 的第i(1≤i≤ListLength(L)+1)個(gè)元素之前插入新的元素 e,L的長(zhǎng)度增 1。 若這樣的元素不存在 ,則返回值為 0。e):用 e返回 L中第 i(1≤i≤ListLength(L))個(gè)元素的值 。 (5)輸出線性表 DispList(L):當(dāng)線性表 L不為空時(shí) ,順序顯示 L中各結(jié)點(diǎn)的值域 。 (3)判線性表是否為空表 ListEmpty(L):若 L為空表 ,則返回真 ,否則返回假 。 (2)銷毀線性表 DestroyList(amp。 線性表的運(yùn)算 線性表的基本運(yùn)算如下 : (1)初始化線性表 InitList(amp。 線性表的一般表示為 : (a1,a2,… ai,ai+1,… ,an) 其中 a1為第一個(gè)元素 ,又稱做表頭元素 ,a2為第二個(gè)元素 ,an為最后一個(gè)元素 ,又稱做表尾元素 。 當(dāng) n=0時(shí) ,表示線性表是一個(gè)空表 ,即表中不包含任何元素。 第 2章 線性表 線性表的基本概念 線性表的順序存儲(chǔ) 線性表的鏈?zhǔn)酱鎯?chǔ) 線性表的應(yīng)用 本章小結(jié) 有序表 線性表的基本概念 線性表的定義 線性表的運(yùn)算 線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。 (5)算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。 返回 (3)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的差別和聯(lián)系 。 本章小結(jié) 本章介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念 ,主要學(xué)習(xí)要點(diǎn)如下： (1)數(shù)據(jù)結(jié)構(gòu)的定義 ,數(shù)據(jù)結(jié)構(gòu)包含的邏輯結(jié)構(gòu) 、存儲(chǔ)結(jié)構(gòu)和運(yùn)算三方面的相互關(guān)系 。 算法空間復(fù)雜度分析 返回 例 分析例 。 ? ? ?? ? ?niijjk0 0 01 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中 臨時(shí)占用的存儲(chǔ)空間 大小的量度 ,一般也作為問(wèn)題規(guī)模 n的函數(shù) ,以數(shù)量級(jí)形式給出 ,記作： S(n) = O(g(n)) 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù) ,則稱此算法為原地工作 。 return(s)。k=j。j=i。i=n。 s=0。 } 該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語(yǔ)句C[i][j]=A[i][j]+B[i][j],分析它的頻度 ,即 ： T(n)= =O(n2) ??? ? ????????????102101010*11ninininjnnnnn例 分析以下算法的時(shí)間復(fù)雜度 。jn。in。 define MAX 20 /*定義最大的方階 */ void matrixadd(int n,int A[MAX][MAX], int B[MAX][MAX],int C[MAX][MAX]) { int i,j。 其余常用的還有平方階 O(n2)、立方階 O(n3)、對(duì)數(shù)階 O(log2n)、指數(shù)階 O(2n)等。 例如 ,T(n)=3n25n+10000=O(n2) 一個(gè)沒(méi)有循環(huán)的算法的基本運(yùn)算次數(shù)與問(wèn)題規(guī)模n無(wú)關(guān) ,記作 O(1),也稱作 常數(shù)階 。 算法中基本運(yùn)算次數(shù) T(n)是問(wèn)題規(guī)模 n的某個(gè)函數(shù)f(n),記作 ： T(n)=O(f(n)) 記號(hào) “ O”讀作 “ 大 O”,它表示隨問(wèn)題規(guī)模 n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同 。 在一個(gè)算法中 ,進(jìn)行基本運(yùn)算的次數(shù)越少 ,其運(yùn)行時(shí)間也就相對(duì)地越少；基本運(yùn)算次數(shù)越多 ,其運(yùn)行時(shí)間也就相對(duì)地越多 。 算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次數(shù) (也稱為頻度 )的乘積 。 } 算法分析 算法時(shí)間復(fù)雜度分析 算法空間復(fù)雜度分析 返回 一個(gè)算法是由控制結(jié)構(gòu) (順序 、 分支和循環(huán)三種 )和原操作 (指固有數(shù)據(jù)類型的操作 )構(gòu)成的 ,則算法時(shí)間取決于兩者的綜合效果 。x=temp。 z=y。 x=y。z)。x,amp。 void Descending() { printf(輸入 x,y,z)。 解：依次輸入 x,y和 z這三個(gè)整數(shù) ,通過(guò)比較交換后 ,使得 x≥y≥z,然后輸出 x,y,z。所以本書(shū)后面很多算法都采用引用形參。a,amp。 /*將 a的值放在 temp中 */ *a=*b。 } 在 C語(yǔ)言中，由于不支持引用類型，所以采用指針的方式來(lái)回傳形參的值，需將上述函數(shù)改為： int swap2(int *x,int *y) { int temp。a=b。 void swap1(int x,int y) { int temp。y=tmp } 當(dāng)用執(zhí)行語(yǔ)句 swap(a,b)時(shí) ,a和 b的值發(fā)生了交換?！狈?hào)不是指針運(yùn)算符 */ { int tmp=x。x,int amp。 當(dāng) a改變時(shí) b也同步改變 ， 同樣 ， 當(dāng)b改變時(shí) a也同步改變 。b=a。 返回 例如：