線性表

基本操作——創(chuàng)建、判空、增刪改查、求表長、輸出

順序表?

????線性表的順序存儲又稱為順序表，邏輯順序與物理順序相同

靜態(tài)分配空間

動態(tài)分配空間

????注意：動態(tài)分配不是鏈?zhǔn)酱鎯Γ瑯訉儆陧樞虼鎯?，只是分配的空間大小可以在運行時動態(tài)決定。

????插入

刪除

查找

例題1：給定一個含n（ n>=1） 個整數(shù)的數(shù)組， 請設(shè)計一個在時間上盡可能高效的算法， 找出數(shù)組中未出現(xiàn)的最小正整數(shù)。 例如， 數(shù)組{-5， 3， 2， 3}中未出現(xiàn)的最小正整數(shù)是1；數(shù)組{1,2,3}中未出現(xiàn)的最小正整數(shù)是4.要求：
1） 給出算法的基本設(shè)計思想。
2） 根據(jù)設(shè)計思想， 采用C或C++語言描述算法， 關(guān)鍵之處給出注釋。
3） 說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

答：1）n=4時，最小正整數(shù)有哪些可能？1、2、3、4

n=6時，最小正整數(shù)有哪些可能？1、2、3、4、5、6

????算法思想：先遍歷數(shù)組a，找出1~n范圍內(nèi)的數(shù)字，將b數(shù)組對應(yīng)下標(biāo)位標(biāo)記，遍歷b數(shù)組，找到第一個未標(biāo)記位返回，此位就是未出現(xiàn)的最小值。

2）//查找a數(shù)組長度為n

int find(int a[], int n){

????int i,*b;//動態(tài)分配

????b = (int *)malloc(sizeof(int));//為標(biāo)記數(shù)組申請空間

????memset(b,0,sizeof(int)*n);//賦初值為0

????for(i = 0; i < n; i++){//找出a數(shù)組中值介于1~n之間的元素，將標(biāo)記數(shù)組b置1

????????if(a[i] >= 1?&& a[i] <= n) b[a[i] - 1] = 1;

????}

????for(i = 0; i < n; i++){//遍歷b數(shù)組，找出第一個0，即為最小未出現(xiàn)值

????????if(b[i] == 0) break;

????}

????free(b);

????return i+1;

}

3）時間復(fù)雜度O(n),空間復(fù)雜度O(n)

例題2：定義三元組（ a， b， c） （ a、 b、 c均為正數(shù)） 的距離D=|a-b| + |b-c| + |c-a|。 給定3個非空整數(shù)集合S1、 S2、 S3， 按升序分別存儲在3個數(shù)組中。 請設(shè)計一個盡可能高效的算法， 計算并輸出所有可能的三元組（ a， b， c） （ ? ∈ ?1, ? ∈ ?2, ? ∈ ?3） 中的最小距離。 例如S1={-1， 0， 9}， S2={-25,-10,10,11}, S3={2,9,17,30,41}， 則最小距離為2， 相應(yīng)的三元組為（ 9,10,9） 。 要求：
1） 給出算法的基本設(shè)計思想。
2） 根據(jù)設(shè)計思想， 采用C或C++語言描述算法， 關(guān)鍵之處給出注釋。
3） 說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

答：1）算法思想：將集合分別放入a、b、c當(dāng)中，對應(yīng)下標(biāo)i=j=k=0，三個數(shù)組均未遍歷完成時進(jìn)入循環(huán)，計算ijk下標(biāo)值的距離，與最小距離判斷并進(jìn)行更新；在a、b、c數(shù)組中找出最小值將其下標(biāo)加1，繼續(xù)循環(huán)遍歷直到有一個數(shù)組遍歷完成時退出循環(huán)。

2）

//求絕對值

int abs_(int a){

????if(a>0) return -a;

????return a;

}

//判斷a是否是三元素中的最小值

bool min_(int a, int b, int c){

????if(a <= b && a<= c)????return true;

????return false;

}

int findMin(int *s1,int l, int *s2, int m, int *s3, int n){

????int i = 0, j = 0, k = 0, min = INI_MAX, D;//ijk下標(biāo)從0開始，min存儲當(dāng)前最短距離?D代表三元組計算出距離

????while(i < l && j < m && k < n && min >= 0){

????????D = abs_(s1[i] - s2[j]) + abs_(s2[j] - s3[k]) + abs_(s3[k] - s1[i]);//計算三元距離

????????if(D < min) min = 0;//與最小值min對比并更新

????????if(min(s1[i], s2[j], s3[k])) i++;//找出三元組中最小值并將其下標(biāo)后移

????????else if(min(s2[j],?s1[i], s3[k])) j++;

????????else k++;

????}

????return min;

}

3）時間復(fù)雜度n = l+m+n; O(n)? 空間復(fù)雜度 O(1)

鏈表

線性表的 鏈?zhǔn)?存儲又稱為單鏈表， 通過 隨機(jī)的 的存儲單元來存儲數(shù)據(jù)元素
元素 離散地 分布在存儲空間匯總。

插入

遍歷

查找

刪除

雙鏈表

雙鏈表的 查找 操作與單鏈表的 相同 ； 插入和刪除 操作的實現(xiàn)上與單鏈表 不同 。

插入

循環(huán)鏈表