目錄：
資料結構實用概念
1）資料結構中的基本概念 2）資料的邏輯結構
3）資料的實體結構 4）資料的運算
算法
1）算法概念 2）算法和資料結構的差別
3）算法特性 4）算法效率的度量
1.資料結構的基本概念
資料：程式的操作對象，用于描述客觀事物
資料元素：組成資料的基本機關
資料對象：性質相同的資料元素的集合
資料結構：資料對象中資料元素之間的關系
2.資料的邏輯結構
指資料元素之間的邏輯關系，即從邏輯關系上描述資料，它與資料的存儲無關，是獨立于計算機的，邏輯結構可細分為4類：
1）集合：資料元素間除“同屬于一個集合”外，無其它關系
2）線性結構：一個對一個，如線性表、棧、隊列
3）樹形結構：一個對多個，如樹
4）圖狀結構：多個對多個，如圖
3.資料的實體結構
實體結構也是存儲結構，是資料的邏輯結構在計算機存儲器内的表示（或映像），它依賴于計算機
存儲結構分為4大類：順序、鍊式、索引、散列
最常用的存儲結構：
順序存儲結構——借助元素在存儲器中的相對位置來表示資料元素間的邏輯關系
鍊式存儲結構——借助訓示元素存儲位址的指針表示資料元素間的邏輯關系
資料的邏輯結構與存儲結構密切相關：算法設計（邏輯結構）、算法實作（存儲結構）
4.資料的運算（操作或處理）
在資料的邏輯結構上定義的操作，它在資料的存儲結構上實作
最常用的資料運算有5種：插入、删除、修改、查找、排序
5.算法
算法概念：特定問題的求解步驟的描述
算法和資料結構的差別：資料結構隻是靜态的描述了資料元素之間的關系，高效的程式需要在資料結構的基礎上設計和選擇算法
程式=資料結構+算法
算法特性：
1）輸入：算法具有0個或多個輸入
2）輸出：算法至少有一個或多個輸出
3）有窮性：算法在有限的步驟之後會自動結束而不會無限循環
4）确定性：算法中的每一步都有确定的含義，不會出現二義性
5）可行性：算法的每一步都是可行的
算法效率的度量：
1）事後統計法：表示不同算法對同一組輸入資料的運作處理時間
優點：直覺；缺點：為了獲得不同算法的運作時間必須編寫相應程式，運作時間依賴于硬體及運作時的環境因素，算法的測試數 據的選取相當困難
算法效率的度量：1）事前分析估算
2）依據統計的方法對算法效率進行估算
3）影響算法效率的主要因素：算法采用的政策和方法；問題的輸入規模；編譯器所産生的代碼；計算機執行 速度
注意1：判斷一個算法的效率時，往往隻需關注操作數量的最高次項，其它次要項和常數項可以忽略
注意2：在沒有特殊說明時，算法的時間複雜度是指最壞時間複雜度
2）大O表示法
算法效率嚴重依賴于操作數量
在判斷時首先關注操作數量的最高次項
操作數量的估算可以作為時間複雜度的估算
3）算法的時間複雜度
算法的最終要編譯成具體的計算機指令
每一個指令在具體的計算機CPU上運作的時間是固定的
通過具體的n的步驟的多少就可以推導出算法的複雜度
4）算法的空間複雜度
算法的空間複雜度通過計算算法的存儲空間實作
S(n)=O(f(n))
其中，n為問題規模，f(n)為在問題規模為n時所占用存儲空間的函數
大O表示法同樣适用于算法的空間複雜度
當算法執行時所需要的空間是常數時，空間複雜度為O(1)
空間與時間的政策：
多數情況下，算法執行時所用的時間更令人關注
如果有必要，可以通過增加空間複雜度來降低時間複雜度
同理，也可以通過增加時間複雜度來降低空間複雜度
空間換時間的典型思想和案例：
//練習：空間換時間
/*
問題：
在一個由自然數1-1000中某些數字所組成的數組中，每個數字可能出現零次或者多次，
設計一個算法，找出出現次數最多的數字。
*/
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
void search(int a[], int len)
{
int sp[1000] = { 0 };
int i = 0;
int max = 0;
for (i = 0; i < len; i++) //周遊數組，求出每一個數字出現的次數，然後記錄下來
{
int index = a[i] - 1;
sp[index]++;
}
for (i = 0; i < 1000; i++) //掃描數組求出最大值
{
if (max < sp[i])
{
max = sp[i];
}
}
for (i = 0; i < 1000; i++) //列印數字最多的
{
if (max == sp[i])
{
printf("%d\n", i + 1);
}
}
}
int main() //把每個數字出現的中間結果，緩存下來；在緩存的結果中求最大值
{
int array[] = {1,1,2,4,5,6,6,6,3,2};
search(array, sizeof(array) / sizeof(*array));
system("pause");
return 0;
}