做網(wǎng)站php與python做推廣怎么賺錢
目錄
大綱
1.數(shù)據(jù)結構基礎知識
1.1 什么是數(shù)據(jù)結構
1.2 數(shù)據(jù)
1.3 邏輯結構
1.4 存儲結構
1.4.1 順序存儲
1.4.2 鏈式存儲
1.4.3 索引存儲結構
1.4.4 散列存儲
1.5 操作
2.算法基礎知識
2.1 什么是算法
2.2 算法的設計
2.3 算法的特性
2.4 評價算法的好壞
大綱
數(shù)據(jù)結構、算法(理解)
線性表：順序表(數(shù)組)、鏈表(單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表)、棧(順序棧、鏈式棧)、隊列(循環(huán)隊列、鏈式隊列)
樹：特性、二叉樹(性質、創(chuàng)建、遍歷)
排序方法、查詢方法(原理、思路)
1.數(shù)據(jù)結構基礎知識
1.1 什么是數(shù)據(jù)結構
數(shù)據(jù)結構就是數(shù)據(jù)的邏輯結構以及存儲操作 (類似數(shù)據(jù)的運算)
數(shù)據(jù)結構就教會你一件事：如何更有效的存儲數(shù)據(jù)
1.2 數(shù)據(jù)
數(shù)據(jù)：不再是單純的數(shù)字，而是類似于集合的概念。
數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項組成。
數(shù)據(jù)項：數(shù)據(jù)的最小單位，描述數(shù)據(jù)元素的有用的信息。
數(shù)據(jù)元素又叫節(jié)點
例如：
計算機處理的對象(數(shù)據(jù))已不再是單純的數(shù)值：
圖書管理中的數(shù)據(jù)，如下表所列:
數(shù)據(jù)：圖書
數(shù)據(jù)元素：每一本書
數(shù)據(jù)項：編號、書名、作者、出版社等
1.3 邏輯結構
數(shù)據(jù)元素并不是孤立存在的，它們之間存在著某種關系(或聯(lián)系、結構)。元素和元素之間的關系：
- 線性關系
線性結構 ==> 一對一 ==> 線性表：順序表、鏈表、棧、隊列
- 層次關系
樹形結構 ==> 一對多 ==> 樹：二叉樹
- 網(wǎng)狀關系
圖狀結構 ==> 多對多 ==> 圖
例題：
田徑比賽的時間安排問題
1.4 存儲結構
數(shù)據(jù)的邏輯結構在計算機中的具體實現(xiàn)（數(shù)據(jù)的運算）
1.4.1 順序存儲
特點：內存連續(xù)、隨機存取、每個元素占用較少
實現(xiàn)：數(shù)組
1.4.2 鏈式存儲
通過指針存儲
特點：內存不連續(xù)，通過指針實現(xiàn)
鏈表實現(xiàn)：
結構體：
#include <stdio.h>struct node
{int data; //數(shù)據(jù)域：存放節(jié)點中要保存的數(shù)據(jù)struct node *next; //指針域：保存下一個節(jié)點的地址，也就是說指向了下一個節(jié)點 (類型為自身結構體指針)
};int main()
{//定義三個節(jié)點struct node A = {1, NULL}; //定義結構體變量的同時給每個成員賦值struct node B = {2, NULL};struct node C = {3, NULL};// struct node D; //先定義結構體變量，再單獨給其中成員賦值// D.data=4;// D.next=NULL;//連接三個節(jié)點A.next = &B; //連接A和B節(jié)點，通過讓A中的指針域保存B的地址B.next = &C;printf("%d\n", A.data);printf("%d\n", A.next->data);printf("%d\n", A.next->next->data);
}
1.4.3 索引存儲結構
在存儲數(shù)據(jù)的同時，建立一個附加的索引表。
也就是索引存儲結構 = 索引表 + 存數(shù)據(jù)的文件
可以提高查找速度，特點檢索速度快，但是占用內存多，刪除數(shù)據(jù)文件要及時更改索引表。
1.4.4 散列存儲
數(shù)據(jù)存儲按照和關鍵碼之間的關系進行存取。關系由自己決定，比如關鍵碼是key, 存儲位置也就是關系是key+1。獲取關鍵數(shù)據(jù)，通過元素的關鍵碼方法的返回值來獲取。
存的時候按關系存
取的時候按關系取
1.5 操作
增刪改查
2.算法基礎知識
2.1 什么是算法
算法就是解決問題的思想方法，數(shù)據(jù)結構是算法的基礎。
數(shù)據(jù)結構 + 算法 = 程序
2.2 算法的設計
算法的設計： 取決于數(shù)據(jù)的邏輯結構
算法的實現(xiàn)：依賴于數(shù)據(jù)的存儲結構
2.3 算法的特性
有窮性： 步驟是有限
確定性：每一個步驟都有明確的含義，無二義性
可行性：在規(guī)定時間內可以完成
輸入
輸出
2.4 評價算法的好壞
正確性
易讀性
健壯性：容錯處理
高效性：執(zhí)行效率，通過重復執(zhí)行語句的次數(shù)來判斷，也就是時間復雜度(時間處理函數(shù))來判斷。
時間復雜度：
語句頻度：用時間規(guī)模函數(shù)表達
時間規(guī)模函數(shù): T(n)=O(f(n))
T(n) //時間規(guī)模的時間函數(shù)
O //時間數(shù)量級
n //問題規(guī)模，例如：a[100], n=100
f(n) //算法可執(zhí)行重復語句的次數(shù)
稱O(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。
漸進時間復雜度用大寫O來表示，所以也被稱為大O表示法。直白的講，時間復雜度就是把時間規(guī)模函數(shù)T(n)簡化為一個數(shù)量級，如n，n^2，n^3。
例1：
求1+2+3+4+...+n的和
算法1：
int sum=0;
for(int i=1;i<=n;i++)
{sum += i; //重復執(zhí)行n次
}
f(n) = n
==>T(n) = O(n)
算法2：
利用等差數(shù)列前n項和公式：Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2 (d是公差）
int sum = (1+n)*n/2; //重復執(zhí)行1次f(n) = 1
==> T(n) = O(1)
例2：
int i,j;
for(i=0;i<n;i++)
{for(j=0;j<n;j++){printf("ok\n"); //重復執(zhí)行n*n次}
}
T(n) = O(n^2)
例3：
int i,j;
for(i=0;i<n;i++)
{for(j=0;j<=i;j++){printf("ok\n"); }
}
1 + 2 + ... n
f(n) = n*(1+n)/2 = n^2/2 + n/2 //只保留最高項n^2/2, 除以最高項系數(shù) 得到n^2
T(n) = O(n^2)
計算大O的方法
- 根據(jù)問題規(guī)模n寫出表達式f(n)
- 如果有常數(shù)項，將其置為1 //當f(n)的表達式中只有常數(shù)項，例如f(n) = 8 ==> O(1)
- 只保留最高項，其他項舍去。
- 如果最高項系數(shù)不為1，則除以最高項系數(shù)。
f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10;
==> O(n^7)