算法和數(shù)據(jù)結(jié)構(gòu)---（線性表-順序存儲）

2023-03-23 14:41 作者:圣母和正負喜歡沒辦法 0人讀過 | 我要投稿

最好用O( $%5Clog%20%7Bn%7D$ )算法，O(n)也行。 $O(nlog%20%20%7B%20n%7D%20)$ 也可以。

$O(1)%3CO(log(n))%3CO(n)%3CO(nlog(n))%3CO(n2)%3CO(n3)%3CO(2n)%3CO(n!)%3CO(n%5En)$

線性表：

結(jié)構(gòu)：

順序存儲：

C：

地址連續(xù)，依次存放，隨機存儲，類型相同

圖書表：

多項式：

$P(x)%3Dp_%7B1%7Dx%5E%7Be_%7B1%7D%7D%2Bp_%7B2%7Dx%5E%7Be_%7B2%7D%7D%2B...%2Bp_%7Bm%7Dx%5E%7Be_%7Bm%7D%7D$

分類方法：

1>首先考慮分解目標函數(shù)、數(shù)據(jù)的構(gòu)成，簡單說就是用一種簡化方式將其分成一種可以用一維、二維、三維數(shù)組代替的成分。比如圖書分類：有編號、價格、名字、日期、借出人。

多項式：系數(shù)、指數(shù)

2>再考慮計算機存儲方式：存儲空間基地址、目標對象個數(shù)。C語言特性連續(xù)、依次、隨機

數(shù)組靜態(tài)分配：JAVA這種沒指針的多用。

動態(tài)數(shù)組分配：

C：分配內(nèi)存：

JAVA：

C++:

?。∽⒁馊绻荢qList *L，則成員表示：

如果是SqList L,則成員表示：

預(yù)定義變量&類型：（實際工程中，可以提前宏定義好，以后改會很方便，宏定義減少調(diào)用時間）

以后實際工程中：要注意提前判斷，用于錯誤檢測。

C++：

線性表操作：

$ASL%3D%E2%88%91_%7Bi%3D0%7D%5E%7Bn%7D%E2%80%8BPi%E2%80%8BCi%E2%80%8B$

$%E5%88%A0%E9%99%A4%EF%BC%9AASL%3D%5Csum%5E%7Bn%7D_%7Bi%3D0%7DP_%7Bi%7DC_%7Bi%7D%3D%5Cfrac%7B1%7D%7Bn%E2%80%8B%7D%E2%88%91_%7Bi%3D0%7D%5E%7Bn%7D%E2%80%8Bn-i%3D%5Cfrac%7B1%7D%7Bn%E2%80%8B%7D%5Cfrac%7Bn(n-1)%7D%7B2%7D%E2%80%8B%3D%5Cfrac%7Bn-1%7D%7B2%E2%80%8B%7D$

刪除&插入

$%E6%8F%92%E5%85%A5%EF%BC%9AASL%3D%5Csum_%7Bi%3D0%7D%5E%7Bn%7DP_%7Bi%7DC_%7Bi%7D%3D%5Cfrac%7B1%7D%7Bn%2B1%E2%80%8B%7D%E2%88%91_%7Bi%3D0%7D%5E%7Bn%7D%E2%80%8B%7Bn-i%2B1%7D%3D%5Cfrac%7B1%7D%7Bn%E2%80%8B%2B1%7D%5Cfrac%7Bn(n%2B1)%7D%7B2%7D%E2%80%8B%3D%5Cfrac%7Bn%7D%7B2%E2%80%8B%7D$

$%E5%88%A0%E9%99%A4%EF%BC%9AASL%3D%5Csum_%7Bi%3D0%7D%5E%7Bn%7DP_%7Bi%7DC_%7Bi%7D%3D%5Cfrac%7B1%7D%7Bn%E2%80%8B%7D%E2%88%91_%7Bi%3D0%7D%5E%7Bn%7Dn-%E2%80%8Bi%3D%5Cfrac%7B1%7D%7Bn%E2%80%8B%7D%5Cfrac%7Bn(n-1)%7D%7B2%7D%E2%80%8B%3D%5Cfrac%7Bn-1%7D%7B2%E2%80%8B%7D$