第一章-緒論
一、資料結構的三要素
1、邏輯結構
資料結構著重關注的是資料元素之間的關系，和對這些資料元素的操作，而不關心具體的資料項內容
- 集合結構
定義：各個元素同屬于一個集合，別無其他關系；
- 線性結構（一對一）——>第二、三章
定義：
- 除了第一個元素，所有元素都有唯一前驅；
- 除了最后一個元素，所有元素都有唯一后繼；
-
樹形結構（一對多）——>第四章
-
圖狀結構（多對多）——>第五章
2、資料的運算
定義：針對于某種邏輯結構，結合實際需求，定義基本運算
基本運算：
- 查找第i個資料元素
- 在第i個位置插入新的資料元素
- 是洗掉第i個位置的資料元素
3、物理結構（存盤結構）
- 順序存盤
- 鏈式存盤
- 索引存盤
- 散列存盤（Hash存盤）
總結:
- 若采用順序存盤，則各個資料元素在物理上必修是連續的；若采用非順序存盤，則各個資料元素在物理上可以是離散的；
- 資料的存盤結構會影響存盤空間分配的方便程度；
- 資料的存盤結構會影響對資料運算的速度；
二、演算法的基本概念
1、什么是演算法
程式 = 資料結構 + 演算法
演算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作；
2、演算法的五個特征
- 有窮性：有窮步驟，有窮時間
- 確定性：相同輸入——>相同輸出
- 可行性：基本運算執行有限次
- 輸入：有零個或多個輸入
- 輸出：有一個或多個輸出
3、“好”演算法的特質
- 正確性：演算法能夠正確地解決求解問題；
- 可讀性：具有良好的可讀性，以幫助人理解；
- 健壯性：輸入非法資料時，演算法能夠做出反應，而不會產生莫名其妙的輸出結果；
- 高效率與低存盤量需求；
三、演算法效率的度量
1、時間復雜度
事前預估演算法時間開銷T(n)與問題規模n的關系（T表示“time”）
例題：
// 演算法1—— 逐步遞增型愛你
void loveYou(int n) { //n 為問題規模
（1） int i=1; // 愛你的程度
（2） while(i<=n) {
(3) i++; // 每次+1
(4) printf("I Love You %d\n", i);
}
(5) printf("I Love You More Than %d\n", n);
}
int main(){
loveYou(3000);
}
陳述句頻度
（1） ——1次
（2） ——3001次
（3）（4） ——3000次
（5） ——1次
T(3000) = 1 + 3001 + 2 * 3000 + 1
時間開銷與問題規模n的關系：
T(n)=3n+3 只關注復雜度的數量級 ——> T(n) = O(n)
復雜度大小優先級排序：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
口訣：常對冪指階
例題：
// 演算法1—— 嵌套回圈型愛你
void loveYou(int n) { //n 為問題規模
（1） int i=1; // 愛你的程度
（2） while(i<=n) {
(3) i++; // 每次+1
(4) printf("I Love You %d\n", i);
(5) for (int j=1; j<=n; j++){
(6) printf("I am a man!\n") ;
}
}
(7) printf("I Love You More Than %d\n", n);
}
int main(){
loveYou(3000);
}
時間開銷與問題規模n的關系：
T(n) = O(n) + O(n2) = O(n2)
例題：
// 演算法3——指數增長型愛你
void loveYou(int n) {
int i=1;
while(i<=n0){
i=i*2; // 第一次回圈 i=2；第二次回圈 i=4；第三次回圈 i=8......
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
通過上述回圈可知 i = 2x
所以想要退出while回圈，x = log2n + 1
所以上述演算法的時間復雜度為T(n) = O(x) = O(log2n)
2、空間復雜度
空間開銷S(n)與問題規模n的關系（S表示“Space”）
例題：
// 演算法1——逐步遞增型愛你
void loveYou(int n) {
int i=1;
while(i<=n){
i++;
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
轉入記憶體 程式代碼 資料
綜上所述，上述演算法的空間復雜度為：S(n)=O(1)
演算法原地作業——演算法所需記憶體空間為常量；
函式遞回呼叫帶來的記憶體開銷：
// 演算法5——遞回型愛你
void loveYou(int n) {
int a,b,c;
if (n > 1) {
loveYou(n-1);
}
printf("I Love You %d\n",n);
}
int main() {
loveYou(5);
}
上述代碼的空間復雜度為：S(n)=O(n) O(n)空間復雜度 = 遞回呼叫的深度
第二章-線性表
一、線性表的定義和基本操作
1、定義
線性表是具有相同資料型別的n（n>=0）個資料元素的有限 序列，其中n為表長，當n=0時線性表是一個空表，若用L命名線性表，則其一般表現為：
L = (a1, a2, ... , ai, ai+1, ... , an) 腳標從1開始計數
- 幾個概念：
- ai是線性表中的“第i個”元素線性表中的位序； 位序是從1開始的，陣列下標是從0開始的；
- a1是表頭元素；an是表尾元素；
- 除第一個元素外，每個元素有且僅有一個直接前驅；
- 除最后一個元素外，每個元素有且僅有一個直接后繼；
2、基本操作
InitList(&L): //初始化表，構造一個空的線性表L，分配記憶體空間；
DestroyList(&L): //銷毀操作，銷毀線性表，并釋放線性表L所占用的記憶體空間；
ListInsert(&L,i,e): //插入操作，在表L中的第i個位置上插入指定元素e；
ListDelete(&L,i,&e): //洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值；
LocateElem(L,e): //按值查找操作，在表L中查找具有給定關鍵字的元素；
GetElem(L,i): //按位查找操作，獲取表L中第i個位置的元素的值；
Tips：
- 對資料的操作（記憶思路） --創銷、增刪改查；
- C語言函式的定義 --<回傳值型別> 函式名(<引數1型別>引數1， <引數2型別>引數2,...)
- 實際開發中，可根據實際需求定義其他的基本操作
- 函式名和引數的形式、命名都可改變
二、順序表的定義
1、順序表的定義
用順序存盤 的方式實作線性表的順序存盤；把邏輯上相鄰的元素存盤在物理位置上也相鄰的存盤單元中，元素之間的關系由存盤單元的鄰接關系來體現；
如何知道一個資料元素大小？
C語言 sizeof(ElemType)
sizeof(int) = 4B
sizeof(Customer) = 8B
2、順序表的靜態分配
#define MaxSize 10 //定義最大長度
typedef struct {
ElemType data[MaxSize]; //用靜態的“陣列”存放資料元素
int length; //順序表的當前長度
}SqList; //順序表的型別定義（靜態分配方式）
//基本操作---初始化一個順序表
void InitList(SqList &L){
for(int i=0; i<MaxSize; i++)
L.data[i] = 0; //將所有資料元素設定為默認初始值
L.length=0; //順序表初始長度為0
}
int main() {
SqList; //宣告一個順序表
InitList(L); //初始化順序表
//嘗試“違規”列印整個data陣列
for(int i=0;i<MaxSize;i++)
printf("data[%d]=%d\n",i, L.data[i]);
return 0;
}
//注:
i<MaxSize這么寫是違規的，不允許這么訪問順序表結構，應該寫成
i<L.length
或者寫成基本操作 GetElem(L,i)
3、順序表的動態分配
#define InitSize 10 //順序表的初始長度
typedef struct {
ElemType *data; //指標動態分配陣列的指標
int MaxSize; //順序表的最大容量
int length; //順序表的當前長度
}SqList; //順序表的型別定義（動態分配方式）
key：動態申請和釋放記憶體空間
malloc 和 free 函式：
L.data = https://www.cnblogs.com/zhenghaoxue/archive/2022/11/14/(ElemType *)malloc(sizeof(ElemType)*InitSize);
//malloc函式申請一整片連續空間
- 具體實作：
#define InitSize 10 //順序表的初始長度
typedef struct {
ElemType *data; //指標動態分配陣列的指標
int MaxSize; //順序表的最大容量
int length; //順序表的當前長度
}SqList;
void InitList(SeqList &L){
//用malloc函式申請一片連續的存盤空間
L.data=https://www.cnblogs.com/zhenghaoxue/archive/2022/11/14/(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize = InitSize;
}
//增加動態陣列的長度
void IncreaseSize(SeqList &L, int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize + len)* sizeof(int));
for(int i=0;i第三章-堆疊、佇列和陣列
第四章-串
第五章-樹與二叉樹
第六章-圖
第七章-查找
第八章-排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/533496.html
標籤：其他
上一篇：每日演算法之不用加減乘除做加法