1. 概述

數(shù)據(jù)結(jié)構(gòu)定義:

我們?nèi)绾伟熏F(xiàn)實(shí)中大量而復(fù)雜的問題以特定的數(shù)據(jù)類型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器(內(nèi)存)中,以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能(如元素的CURD、排序等)而執(zhí)行的相應(yīng)操作，

這個(gè)相應(yīng)的操作也叫算法。

數(shù)據(jù)結(jié)構(gòu) = 元素 + 元素的關(guān)系

算法 = 對(duì)數(shù)據(jù)結(jié)構(gòu)的操作

算法:

算法就是：解決問題的方法和步驟

衡量算法有如下標(biāo)準(zhǔn):

1.時(shí)間復(fù)雜度

程序要執(zhí)行的次數(shù)，并非執(zhí)行時(shí)間

2.空間復(fù)雜度

算法執(zhí)行過程中大概要占用的最大內(nèi)存

3.難易程度(可讀性)

4.健壯性

2. 數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和地位

地位:

數(shù)據(jù)結(jié)構(gòu)處于軟件中核心的地位。

如計(jì)算機(jī)內(nèi)存中棧和堆的區(qū)別，不懂?dāng)?shù)據(jù)結(jié)構(gòu)的人可能會(huì)認(rèn)為內(nèi)存就是分兩大部分，一塊叫棧，一塊叫堆，顯然這是非常膚淺且不正確的結(jié)論。

實(shí)際上如果一塊內(nèi)存是以壓棧出棧的方式分配的內(nèi)存，那么這塊內(nèi)存就叫棧內(nèi)存，如果是以堆排序的方式分配的內(nèi)存，那么這塊內(nèi)存就叫堆內(nèi)存，其最根本的區(qū)別還是其內(nèi)存分配

算法的不同。

例如，函數(shù)的調(diào)用方式也是通過壓棧出棧的方式來調(diào)用的，或者操作系統(tǒng)中多線程操作有隊(duì)列的概念，隊(duì)列用于保證多線程的操作順序，這也是數(shù)據(jù)結(jié)構(gòu)里面的內(nèi)容、或者計(jì)算機(jī)

編譯原理里面有語法樹的概念，這實(shí)際上就是數(shù)據(jù)結(jié)構(gòu)里面的樹，比如軟件工程、數(shù)據(jù)庫之類都有數(shù)據(jù)結(jié)構(gòu)的影子。

特點(diǎn):

數(shù)據(jù)結(jié)構(gòu)修煉的是內(nèi)功，并不能直接立竿見影的可以解決現(xiàn)實(shí)問題，但是有了這門內(nèi)功會(huì)在其他方面的學(xué)習(xí)中對(duì)你大有益處。

3. 預(yù)備知識(shí)（C語言）

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)該具備如下知識(shí)：

指針

結(jié)構(gòu)體

動(dòng)態(tài)內(nèi)存的分配和釋放

跨函數(shù)使用內(nèi)存

本小節(jié)主要介紹學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)該有的基礎(chǔ)，并對(duì)相關(guān)知識(shí)稍作講解。

指針

指針是 C語言 的靈魂，重要性不需多言。

指針定義

地址：

地址是內(nèi)存單元的編號(hào)

其編號(hào)是從 0 開始的非負(fù)整數(shù)

范圍： 0 -- 0xFFFFFFFF (2^32 - 1)  注：此指x86平臺(tái)，x64平臺(tái)下最大內(nèi)存地址為 (2^64 - 1)

指針：

指針就是地址，地址就是指針。

指針變量是存放內(nèi)存單元地址的變量,它內(nèi)部保存的值是對(duì)應(yīng)的地址,地址就是內(nèi)存單元的編號(hào)(如內(nèi)存地址值：0xffc0)。

指針的本質(zhì)是一個(gè)操作受限的非負(fù)整數(shù)

在計(jì)算機(jī)系統(tǒng)中，CPU 可以直接操作內(nèi)存，關(guān)于 CPU 對(duì)內(nèi)存的操作與控制原理可以簡單理解如下圖

地址線 ： 確定操作哪個(gè)地址單元

控制線 ： 控制該數(shù)據(jù)單元的讀寫屬性

數(shù)據(jù)線 ： 傳輸 CPU 和內(nèi)存之間的數(shù)據(jù)

指針的分類

1.基本類型的指針

int i = 10;  // 定義一個(gè) 整形變量 i 初始值 10
int *p = i;  // 定義一個(gè) 整形的指針變量 p , 變量 p 指向 i 的地址    
int *p;      // 這兩行等價(jià)于上面一行
p = &i;
1. p 存放了 i 的地址，我們就可以說“ p 指向了 i” ，但 p 和 i 是兩個(gè)不同的變量，修改一方不會(huì)影響另一個(gè)的值。
2. *p 等價(jià)于 i ，i 等價(jià)于 *p;兩者是一塊內(nèi)存空間，里面的值一變具變。

2.指針和函數(shù)

// 修改外部實(shí)參的值
void func(int * p)
{
    *p = 100;   // 函數(shù)內(nèi)修改外部變量的值   
}
// 修改外部實(shí)參的值，二級(jí)指針的值
void func2(int ** p)
{
    *p = 100;   
    // 函數(shù)內(nèi)修改外部變量的值 ，這里實(shí)際修改的是指針的內(nèi)部的地址，這里直接自己修改并不嚴(yán)謹(jǐn)也不安全，只是為了表達(dá)意思  
}
int main(void)
{
    // 修改外部實(shí)參
   int i = 10;
   func(&i);
   printf("i = %d",i);
   // 修改外部二級(jí)指針
   int *p = i; // 等價(jià)于 int *p; p = &i;
   func(&p);
   printf("i = %d",i);
   return 0;
}
// 通過函數(shù)調(diào)用，改變函數(shù)外部變量（實(shí)參）的值

3.指針和數(shù)組

【指針】 和 【一維數(shù)組】

int a[5] = {1,2,3,4,5 };
 a[3] == *(a + 3)  
 // 等價(jià)于 a[3] == *(3 + a) == 3[a];
 // 3[a] 這種寫法只是不常用，從原理上來說是正確的 a 等價(jià)于 a[0];
 // a 是數(shù)組中第一個(gè)元素，每個(gè)元素占用內(nèi)存單位長度相同，
 // a[i] 中的 i 實(shí)際代表的是單位長度的倍數(shù)

數(shù)組名:

　一維數(shù)組名是個(gè)指針常量(它的值不可變)

它存放的是該一維數(shù)組的第一個(gè)元素的地址(一維數(shù)組名指向其第一個(gè)元素)

下標(biāo)和指針的關(guān)系:

(1)、 a[i] 等價(jià)于 *(a + i)

(2)、假設(shè)指針變量的名字為 p,

則 p + i 的值為 p + i * (p 所指向的變量所占字節(jié)數(shù))

(3)、每個(gè)下標(biāo)表示的是第 i+1 個(gè)元素，根據(jù)元素類型分配的字節(jié)長度不同(int 類型4個(gè)字節(jié))，每個(gè)字節(jié)都有對(duì)應(yīng)的內(nèi)存地址編號(hào)，指針變量 p 保存的是該元素首字節(jié)的地址。

指針變量的運(yùn)算:　

指針變量不能相加、相乘、相除

如果兩指針變量屬于同一數(shù)組，則可以相減

指針變量可以加減一個(gè)整數(shù)，前提是最終結(jié)果不能超過指針最大可訪問范圍

// 指針變量的運(yùn)算
p + i 的值是 p + i*(所指向的變量所占字節(jié)數(shù))
p - i 的值是 p - i*(所指向的變量所占字節(jié)數(shù))
p++   等價(jià)于 p + 1
p--   等價(jià)于 p - 1
// 下面是一個(gè)通過函數(shù)修改數(shù)組內(nèi)部元素
void my_Array(int *a , int length)
{
    for(int i = 0; i < length; i++)
    {
        *a[i]++;  // 給每個(gè)元素加 1
    }
}
int main(void){
    int a[5] = {1,2,3,4,5};
    my_Array(a , 5); // 調(diào)用
}

結(jié)構(gòu)體

為什么會(huì)出現(xiàn)結(jié)構(gòu)體、

為了表示一些復(fù)雜的數(shù)據(jù)，而普通的基本數(shù)據(jù)無法滿足要求.

什么叫結(jié)構(gòu)體

結(jié)構(gòu)體是用戶根據(jù)實(shí)際需要，自己定義的復(fù)合數(shù)據(jù)類型

// 如學(xué)生類型
struct Student{
   int age;
   char * name; // name 不同，賦值方法不同
   char name2[100]; // 這個(gè)只能 strcpy(s.name2, "zhangwangdsd"); 字符串拷貝
   double height;
};

如何使用結(jié)構(gòu)體

總結(jié)起來有兩種結(jié)構(gòu)體的使用方式：直接使用 && 通過指針使用

struct Student ss = {12,"xiaoyou",1.73,"xiaozhang"};

struct Student *pst = &ss;

ss.name ;  這里直接操作結(jié)構(gòu)體本身

pst -> name ;   這里通過指針地址操作，更加節(jié)省空間

struct Student{ // 自定義結(jié)構(gòu)體
    int age;
    char * name;
    double height;
    char name2[100];
};
int main(void) {
   struct Student s = {12,"xiaoyou",1.73,"xiaozhang"};
// 直接使用
   printf(" age = %d 
 name = %s 
 height = %.2f 
",s.age,s.name,s.height);
   s.age = 21;
   s.name = "xiaozhu";
   strcpy(s.name2, "zhangwangdsd");  // 字符串拷貝
   s.height = 1.70;
   printf(" age = %d 
 name = %s 
 height = %.2f 
 %s 
",s.age,s.name,s.height,s.name2);
   // 以指針的方式使用
   struct Student *pst = &ss;
   pst -> name = "my new name";
   printf(" name = %s
",pst->name);
   printf(" name = %s
",(*pst)->name);
// pst -> name 等價(jià)于 (*pst).name ,
// 而(*pst).name 又等價(jià)于 ss.name
// 所以 pst -> name 等價(jià)于 ss.name
   return 0;
}

注意事項(xiàng)

結(jié)構(gòu)體變量的類型為： struct Student

結(jié)構(gòu)體變量不能加減乘除，但是能夠相互賦值

普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)傳參的問題

typedef struct Student{ // 結(jié)構(gòu)體定義
    int age;
    char * name;
    char name2[100];
    double height;
}myStudent;
// 直接傳遞整個(gè)結(jié)構(gòu)體數(shù)據(jù)，耗時(shí) && 浪費(fèi)內(nèi)存空間
void func(struct Student st);
// 直接傳遞 只占用 4 byte 的指針，省時(shí)效率也高 <推薦用法>
void func2(struct Student * pst);
int main(void){
    myStudent ss = {12,"xiaoyou",1.73};
    func(ss);
    func2(&ss);
    return 0;
}
void func(struct Student st){
    printf("age = %d 
 name = %s",st.age,st.name);
}
void func2(struct Student * pst){
    printf("age = %d 
 name = %s",(*pst).age,(*pst).name);
    printf("age = %d 
 name = %s",pst->age,pst->name);
}

動(dòng)態(tài)內(nèi)存分配和釋放

平時(shí)直接創(chuàng)建數(shù)組的寫法都是靜態(tài)創(chuàng)建，創(chuàng)建完畢之后在整個(gè)程序的運(yùn)行過程中，會(huì)固定占用對(duì)應(yīng)的內(nèi)存，不僅會(huì)造成內(nèi)存空間浪費(fèi)，還無法動(dòng)態(tài)添加元素，所以局限性很大，而

程序中我們?yōu)榱吮苊膺@種情況，應(yīng)該使用動(dòng)態(tài)的方式創(chuàng)建和銷毀數(shù)組。

// 靜態(tài)創(chuàng)建數(shù)組
int a[5] = {1,2,3,4,5};

動(dòng)態(tài)構(gòu)造一維數(shù)組

動(dòng)態(tài)構(gòu)造一個(gè) int 型的一維數(shù)組。

int *p = (int *)malloc(int length);
1. void * malloc(size_t __size) 函數(shù),只有一個(gè) int 類型的形參，表示要求系統(tǒng)分配的字節(jié)數(shù)
2. malloc 函數(shù)的功能是請(qǐng)求系統(tǒng) length 個(gè)字節(jié)的內(nèi)存空間，如果請(qǐng)求完成則返回的是第一個(gè)字節(jié)的地址，
    如果請(qǐng)求不成功，則返回NULL
3. malloc 函數(shù)能且只能返回第一個(gè)字節(jié)的地址，所以我們需要把沒有實(shí)際意義的第一個(gè)字節(jié)地址（干地址）轉(zhuǎn)化為一個(gè)有實(shí)際意義的地址，
    所以 malloc 前面必須加(數(shù)據(jù)類型 *)，表示把這個(gè)無意義的地址轉(zhuǎn)化為對(duì)應(yīng)類型的地址
    實(shí)例：
        int *p = (int *)malloc(50);
        表示將系統(tǒng)分配的 50 個(gè)字節(jié)的第一個(gè)字節(jié)的地址轉(zhuǎn)化為 int 類型的地址，準(zhǔn)確的說是轉(zhuǎn)化為 4 個(gè)一組的地址的首地址，
        這樣 p 就指向了第一個(gè)四個(gè)字節(jié)··· p+i 就指向了第 i+1 個(gè)四個(gè)字節(jié)，p[0],p[i]也就分別是第一個(gè)，第i+1個(gè)元素。
        double *p = (double *)malloc(80);
        表示將系統(tǒng)分配的 80 個(gè)字節(jié)的第一個(gè)字節(jié)的地址轉(zhuǎn)化為 double 類型的地址，準(zhǔn)確的說是轉(zhuǎn)化為 8 個(gè)一組的地址的首地址，
        這樣 p 就指向了第一個(gè)八個(gè)字節(jié)··· p+i 就指向了第 i+1 個(gè)八個(gè)字節(jié)，p[0],p[i]也就分別是第一個(gè)，第i+1個(gè)元素。
4. free(p);
    釋放 p 所指向的內(nèi)存，而不是釋放 p 本身所占用的內(nèi)存

代碼示例如下：

void test2(void)
{
    int len;
    printf("請(qǐng)輸入你要?jiǎng)討B(tài)創(chuàng)建的數(shù)組長度:");
    scanf("%d",&len);
    int *pArr = (int *)malloc(len); // 動(dòng)態(tài)創(chuàng)建數(shù)組
    *pArr = 4;      // 相當(dāng)于 a[0] = 4;  這里 pArr 就等于數(shù)組首地址，等于數(shù)組名
    pArr[2] = 5;    // 相當(dāng)于 a[2] = 5;
    printf("pArr[0] = %d 
pArr[2] = %d
",pArr[0],pArr[2]);
    free(pArr);     // 使用完畢，釋放對(duì)應(yīng)的數(shù)組空間 
}

跨函數(shù)使用內(nèi)存

在函數(shù)內(nèi)部分配的局部變量，在函數(shù)調(diào)用完成之后就會(huì)被系統(tǒng)回收，其內(nèi)存也會(huì)消失。但是程序中常常需要定義一塊內(nèi)存，當(dāng)我們用完之后再會(huì)回收。如 OC 語言中對(duì)象。所以需

要保存住分配的內(nèi)存，應(yīng)該用動(dòng)態(tài)分配內(nèi)存，當(dāng)用完之后再手動(dòng)釋放。這也是C語言的一個(gè)不足之處：內(nèi)存需要我們手動(dòng)創(chuàng)建和手動(dòng)釋放，這也是 OC 語言在開發(fā) iOS 程序時(shí)候，

我們所講的MRC?！咎O果也發(fā)現(xiàn)了這個(gè)不足，于 iOS 5 的時(shí)候推出了ARC 】

下面是一個(gè)跨函數(shù)使用內(nèi)存的例子：

// 這個(gè)例子已經(jīng)非常有面向?qū)ο蟮奈兜懒?
typedef struct Student{     // 自定義 student 結(jié)構(gòu)體
    int age;
    char * name;
}myStudent;
myStudent * createStudent(void); // 創(chuàng)建 student 
void showStudent(myStudent *);   // 輸出 student
int main(void) {
    myStudent *p = createStudent();  // 創(chuàng)建 student 
    showStudent(p);                  // 輸出 student
    return 0;
}
myStudent * createStudent(void)
{
    myStudent *p = (myStudent *)malloc(sizeof(myStudent));
    p->age = 20;
    p->name = "xiaoyou";
    return p;
}
void showStudent(myStudent *p)
{
    printf("student.age = %d 
student.name = %s
",p->age,p->name);
}

4. 小結(jié)

本文主要講解了數(shù)據(jù)結(jié)構(gòu)的定義和簡介。

回顧了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)該具備的一些 C語言 的基礎(chǔ)知識(shí)，如指針、結(jié)構(gòu)體、和內(nèi)存等。

后面會(huì)繼續(xù)開始對(duì)數(shù)據(jù)結(jié)構(gòu)的講解。