如果說，熟練掌握編程語言是外功展哭，那么
數(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ù)結構》
