第一章-緒論一、數據結構的三要素 1、邏輯結構數據結構著重關註的是數據元素之間的關係，和對這些數據元素的操作，而不關心具體的數據項內容集合結構定義：各個元素同屬於一個集合，別無其他關係；線性結構（一對一）——>第二、三章定義：除了第一個元素，所有元素都有唯一前驅；除了最後一個元素，所 ...

第一章-緒論

一、數據結構的三要素

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(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

口訣：常對冪指階

例題：

// 演算法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(n²) = O(n²)

例題：

// 演算法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 = 2^x

所以想要退出while迴圈，x = log₂n + 1

所以上述演算法的時間複雜度為T(n) = O(x) = O(log₂n)

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 = (a₁, a₂, ... , a_i, a_i+1, ... , a_n) 腳標從1開始計數

幾個概念：
1. a_i是線性表中的“第i個”元素線性表中的位序； 位序是從1開始的，數組下標是從0開始的；
2. a₁是表頭元素；a_n是表尾元素；
3. 除第一個元素外，每個元素有且僅有一個直接前驅；
4. 除最後一個元素外，每個元素有且僅有一個直接後繼；

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 = (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=(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<L.length; i++){
        L.data[i]=p[i];	//將數據複製到新區域
    }
    L.MaxSize=L.MaxSize + len;	//順序表最大長度增加len
    free(p);				//釋放原來的記憶體空間
}

王道數據結構（C語言）持續更新！！！