如果說,熟練掌握編程語言是外功展哭,那么
數(shù)據(jù)結構
可謂是內(nèi)功心法了
以下是我學習數(shù)據(jù)結構的總結和一些筆記
數(shù)據(jù)結構(Data Structure)
- 抽象數(shù)據(jù)類型(ADT)的物理實現(xiàn)
- “數(shù)據(jù)結構”是計算機中存儲秽之,組織數(shù)據(jù)的方式神年。
- “數(shù)據(jù)結構是數(shù)據(jù)對象”以及存在于該對象的實例和組成實例的數(shù)據(jù)元素之間的各種聯(lián)系
- 解決問題方法的效率跟
數(shù)據(jù)的組織方式
帘靡、空間的利用效率
和算法的巧妙程度
有關
例子1:
void PrintN( int N )
{
int i;
for( i=1 ; i<N ; i++)
printf("%d\n",i);
return;
}
void PrintN( int N )
{
if( N )
{
PrintN(N-1);
printf("%d\n",N);
}
return;
}
這個程序前一個用了循環(huán)實現(xiàn)打印1-N玄货,后面一個采用遞歸的方法實現(xiàn)的皇钞,很明顯遞歸的效率很低,是因為松捉,遞歸實現(xiàn)原理是以堆棧的方式夹界,也就是說函數(shù)把 PrintN(N) 到PrintN(1)這N個函數(shù)壓入棧中,在依次打印出來隘世,內(nèi)存消耗巨大可柿。
圖示:
例子2:
計算
double f(int n , double a[], double x)
{
int i;
double p = a[0];
for( i=1 ; i<=n ; i++)
p+= ( a[i] * pow( x , i ));
return p;
}
double f(int n , double a[], double x)
{
int i;
double p = a[0];
for( i=n ; i>0 ; i--)
p= a[i-1] +x*p;
return p;
}
在計算機中,有多次乘法與加法的運算時丙者,一般按照權重复斥,只需比較乘法次數(shù)就可以了,第一個算法每一次循環(huán)執(zhí)行了i+1次乘法蔓钟,一共執(zhí)行了(N^2+3*N)/2次永票,第二種算法執(zhí)行了N次乘法卵贱,顯然第二種效率高滥沫,這就是算法的妙用
其實數(shù)據(jù)結構是由一些基本數(shù)據(jù)類型組合成了一個復雜的數(shù)據(jù)類型侣集,用于解決某一類問題(基本問題有數(shù)據(jù)的增加,刪除兰绣,條件查詢世分,遍歷等)
總結:到底什么是數(shù)據(jù)結構?
-
數(shù)據(jù)對象在計算機中的組織方式
- 邏輯結構
- 物理存儲結構
數(shù)據(jù)對象必定與一系列加在其上的操作相關聯(lián)
完成這些操作所用的方法就是算法
抽象數(shù)據(jù)類型(Abstract Data Type)
- 數(shù)據(jù)類型
- 數(shù)據(jù)對象集
- 數(shù)據(jù)集合相關聯(lián)的操作集
- 抽象:描述數(shù)據(jù)類型的方法不依賴于具體實現(xiàn)
- 與存放的機器無關
- 與數(shù)據(jù)存儲的物理結構無關
- 與實現(xiàn)操作的算法和編程語言無關
算法
什么是算法缀辩?
- 一個有限指令集
- 接受一些輸入(有些時候不需要輸入)
- 產(chǎn)生輸出
- 一定在有限步驟之后終止
- 每一條指令必須
時間復雜度Tn
根據(jù)算法寫成的程序在執(zhí)行時占用存儲單源的長度
空間復雜度Sn
根據(jù)算法寫成的程序在執(zhí)行時好費時間的長度
牛刀小試
用算法實現(xiàn) 求一個數(shù)列的最大子列和
給出下列四個算法:
//第一種算法:時間復雜度為 T(n^3)
int MaxSubseqSum1(int a[] , int N)
{
int thisSum=0 , MaxSum=0;
int i,j,k;
for( i=0 ; i<N ; i++ ) /* i 是子列左端位置 */
for( int j=i ; j<N ; j++ ) /* j是子列右端位置 */
{
thisSum = 0; /* thisSum 是從 a[i] 到 a[j] 的子列和 */
for(int k=i;k<j;k++)thisSum+=a[k];
/* 如果剛得到的這個子列和更大臭埋,則更新結果 */
if(thisSum>MaxSum) MaxSum = thisSum;
}
return MaxSum;
}
//最快的算法,時間復雜度為T(n)
int MaxSubseqSum1(int a[] , int N)
{
int thisSum=0 , MaxSum = 0;
int i;
for( i=0 ; i<N ; i++)
{
thisSum+=a[i]; /* 向右累加 */
/* 發(fā)現(xiàn)更大的則更新當前結果 */
if(thisSum>MaxSum)MaxSum = thisSum;
/* 如果當前子列和為負數(shù)臀玄,則不可能是后面的部分和增大瓢阴,故舍棄 */
else if(thisSum<0)thisSum=0;
}
return MaxSum;
}
算法三可以嘗試寫一下。
以上資料來源于 MOOC 《數(shù)據(jù)結構》