閱讀完成大概需要10分鐘 | 2019-03-29 | 原創(chuàng) | 有編程基礎(chǔ)者適宜

個人博客 | B站空間

1. 我的理解

• 數(shù)據(jù)結(jié)構(gòu)?什么是數(shù)據(jù)結(jié)構(gòu)?

  • 就是數(shù)據(jù)(比如學生成績等這些具有實際意義的東西)通過某種關(guān)系關(guān)聯(lián)起來, 方便我們使用計算機統(tǒng)計和其他操作, 這樣就是數(shù)據(jù)結(jié)構(gòu).

  • 在我看來數(shù)據(jù)結(jié)構(gòu)就是個工具, 基于基本類型, 而形成的, 它的重點只是研究操作(數(shù)據(jù)元素)對象的關(guān)系, 根據(jù)不同問題對于數(shù)據(jù)操作的的特點(比如經(jīng)常需要和插入刪除元素), 使用不同的數(shù)據(jù)結(jié)構(gòu), 可以更加高效的解決問題.

• 算法就是解決問題的具體方法.

數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序.

2. 算法:

數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述數(shù)據(jù)元素之間的關(guān)系, 高效的程序需要在 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上數(shù)據(jù)和選擇算法.

• 算法是為了解決實際問題而設(shè)計的.
• 數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體.
• 數(shù)據(jù)結(jié)構(gòu)于算法相輔相成.

2.1. *算法的特性

輸入:有0或多個輸入.
輸出:至少有一個輸出(有1或以上的輸出).
有窮性: 有始有終.
確定性: 每一步都有確定的含有, 不會出現(xiàn)二義性.
可行性: 算法的每一步都是可行的.

2.2. 統(tǒng)計算法的效率: 算法效率的度量

因為解決問題算法有多種, 貨比三家, 那么我們需要 一把尺子來衡量算法的好壞, 來幫助我們判斷優(yōu)劣算法.

2.2.1. 時間復雜度(運行消耗時間的度量)

2.2.1.1. *事后統(tǒng)計法

記錄程序運所消耗的時間, 作為參照物.

缺點: 這樣有很多不確定性, 嚴重依賴于計算機硬件以及運行環(huán)境.

了解即可

實現(xiàn)方法: 獲取在算法執(zhí)行前獲取時間戳并且賦值, 在算法完成時再獲取并且減去執(zhí)行前的時間戳.

--Lua代碼
time = os.clock()
--代碼
print(os.clock() - time)

2.2.1.2. 事前分析估算

假設(shè)每一行指令在計算機上運行速度固定, 通過計數(shù)算法中代碼執(zhí)行步數(shù)的多少, 來衡量算法效率(簡單來說: 數(shù)執(zhí)行了多少行).

判斷規(guī)則:

• 只關(guān)注最高次項: 只關(guān)系操作數(shù)量的最高次項, 其他次項的常數(shù)忽略(因為大部分情況是人工數(shù)的, 偷懶而已啦).
• 最壞的時間復雜度: 我們分析的算法復雜度往往都是最壞的時間復雜度.
• 常數(shù)項記為1.

大O表示法 :
O(_{執(zhí)行行數(shù)})

O(₅)==O(₁),以后O(常數(shù))都寫成O(1)
O(N⁴+N³+N)==O(N⁴)

比如:

void sum(int a,int b)
{
   int s;  //1
   s = a + b;  //2
   std::cout<< s <<std::endl;  //3
}

這個就是O(₃) ==_{(因為常數(shù)記為1)}== O(₁)
注意: O(_n)!=O(₁)

又比如:

void fun(int n)
{
    int s = 1;
    for( ; s < n ; )
      s * = 2;
}

要想結(jié)束循環(huán): 2^x=N; 即 x=log₂N, 記為O(_logN)
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(n!)<O(x^x)
是不是覺得很復雜? 其實只要數(shù), 執(zhí)行了多少行即可.

2.2.2. 空間復雜度(占用存儲空間大小的量度)

使用S(f(n))表示, 有空再更新, 敬請期待.

3. 數(shù)據(jù)結(jié)構(gòu)

如果說 數(shù)組, 指針 等這些 基本的數(shù)據(jù)類型 是花瓶材料(粘土), 那么數(shù)據(jù)結(jié)構(gòu)出現(xiàn)的那些線性表, 棧等 那些, 就是 就是各種各樣的花瓶, 不同的 花 使用不同的容器, 在效率來說也許更加高效.

基本功能:刪除元素, 查找元素, 添加(插入)元素, 遍歷全表.
它們都是類型相同的數(shù)據(jù)的集合.
元素有限.
想不出來了2333.

4.1. 線性結(jié)構(gòu)

線性表包括: 數(shù)組(順序表), 鏈表, 隊列, 棧等.

4.1.1 線性表

數(shù)學定義: 具有相同數(shù)據(jù)類型的 N (>=0) 個數(shù)據(jù)元素的有限序列(連續(xù)的).

順序表_{(其實就是數(shù)組)}

1. 地址連續(xù), 直接定義數(shù)組使用的棧空間, 使用new開辟空間使用堆空間, 這個主要用開辟堆空間, 可以用參數(shù)同態(tài)分配數(shù)組長度.
2. 原則上長度無法增減, 需要重新開辟新空間, 再拷貝原來的的數(shù)據(jù),一般都實際大小都要大于開辟的空間.

簡單實現(xiàn)(原創(chuàng)):

template<class T>
class Arr
{
  T* data;//指針
  unsigned int len;//長度
public:
Arr(unsigned int s)
{
  len=s;
  data=new T[s];
};// 構(gòu)造
~Arr()
{
  delete[] data;//釋放內(nèi)存
}//構(gòu)析
  T &operator[](int i)
{
  if(i<0||i>size)
    exit(EXIT_FAILURE);
  return data[i];
}//運算符重載 [i]
};

使用

Arr<type> data(len);
data[0]=(type)data
//---// 
Arr<int> int_data(10);
int_data[0]=100;
std::cout<<int_data[0]<<std::endl;

基于vector實現(xiàn):

本家:

#include<vector>

初始化:

vector<type> p;
vector<type> p(int len);//設(shè)置初始大小.
vector<type> p(int len, type data)//設(shè)置大小, 并且設(shè)置每個的內(nèi)容都為data.

//在這里導入?yún)?shù)vector<type> s, vector<type>是數(shù)據(jù)類型
vector<type> p(vector<type> s);//初始化一個和s內(nèi)容相同的向量.
//假設(shè)x和y是向量t的兩個元素指針,并且x<y.
vector<type> p(vector<type> *x,vector<type> *y);//初始化一個向量, 內(nèi)容范圍是t向量的x指針到y(tǒng)指針位置.

常用的API:

vector<type> s;


s.size();//獲取元素個數(shù)
s.empty();//是否為空
s.clear();//清空所有的

vector<type> p;
p=s;//拷貝s的內(nèi)容到p中.不是指針的操作.已經(jīng)重載運算符.

==、!=、>、>=、<、<= 也適用. 返回值真1,假0.(某種程度上來說也是bool)

4.2. 非線性表

非線性結(jié)構(gòu): 樹, 圖等.