1. 概述

數據結構定義:

我們如何把現實中大(dà)量而複雜(zá)的(de)問題以特定的(de)數據類型和(hé)特定的(de)存儲結構保存到主存儲器(内存)中,以及在此基礎上爲實現某個(gè)功能(如元素的(de)CURD、排序等)而執行的(de)相應操作，

這(zhè)個(gè)相應的(de)操作也(yě)叫算(suàn)法。

數據結構 = 元素 + 元素的(de)關系

算(suàn)法 = 對(duì)數據結構的(de)操作

算(suàn)法:

算(suàn)法就是：解決問題的(de)方法和(hé)步驟

衡量算(suàn)法有如下(xià)标準:

1.時(shí)間複雜(zá)度

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

2.空間複雜(zá)度

算(suàn)法執行過程中大(dà)概要占用(yòng)的(de)最大(dà)内存

3.難易程度(可(kě)讀性)

4.健壯性

2. 數據結構的(de)特點和(hé)地位

地位:

數據結構處于軟件中核心的(de)地位。

如計算(suàn)機内存中棧和(hé)堆的(de)區(qū)别，不懂(dǒng)數據結構的(de)人(rén)可(kě)能會認爲内存就是分(fēn)兩大(dà)部分(fēn)，一塊叫棧，一塊叫堆，顯然這(zhè)是非常膚淺且不正确的(de)結論。

實際上如果一塊内存是以壓棧出棧的(de)方式分(fēn)配的(de)内存，那麽這(zhè)塊内存就叫棧内存，如果是以堆排序的(de)方式分(fēn)配的(de)内存，那麽這(zhè)塊内存就叫堆内存，其最根本的(de)區(qū)别還(hái)是其内存分(fēn)配

算(suàn)法的(de)不同。

例如，函數的(de)調用(yòng)方式也(yě)是通(tōng)過壓棧出棧的(de)方式來(lái)調用(yòng)的(de)，或者操作系統中多(duō)線程操作有隊列的(de)概念，隊列用(yòng)于保證多(duō)線程的(de)操作順序，這(zhè)也(yě)是數據結構裏面的(de)内容、或者計算(suàn)機

編譯原理(lǐ)裏面有語法樹的(de)概念，這(zhè)實際上就是數據結構裏面的(de)樹，比如軟件工程、數據庫之類都有數據結構的(de)影(yǐng)子。

特點:

數據結構修煉的(de)是内功，并不能直接立竿見影(yǐng)的(de)可(kě)以解決現實問題，但是有了(le)這(zhè)門内功會在其他(tā)方面的(de)學習(xí)中對(duì)你大(dà)有益處。

3. 預備知識（C語言）

學習(xí)數據結構應該具備如下(xià)知識：

指針

結構體

動态内存的(de)分(fēn)配和(hé)釋放

跨函數使用(yòng)内存

本小節主要介紹學習(xí)數據結構應該有的(de)基礎，并對(duì)相關知識稍作講解。

指針

指針是 C語言 的(de)靈魂，重要性不需多(duō)言。

指針定義

地址：

地址是内存單元的(de)編号

其編号是從 0 開始的(de)非負整數

範圍： 0 -- 0xFFFFFFFF (2^32 - 1)  注：此指x86平台，x64平台下(xià)最大(dà)内存地址爲 (2^64 - 1)

指針：

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

指針變量是存放内存單元地址的(de)變量,它内部保存的(de)值是對(duì)應的(de)地址,地址就是内存單元的(de)編号(如内存地址值：0xffc0)。

指針的(de)本質是一個(gè)操作受限的(de)非負整數

在計算(suàn)機系統中，CPU 可(kě)以直接操作内存，關于 CPU 對(duì)内存的(de)操作與控制原理(lǐ)可(kě)以簡單理(lǐ)解如下(xià)圖

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

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

數據線 ： 傳輸 CPU 和(hé)内存之間的(de)數據

指針的(de)分(fēn)類

1.基本類型的(de)指針

int i = 10;  // 定義一個(gè) 整形變量 i 初始值 10
int *p = i;  // 定義一個(gè) 整形的(de)指針變量 p , 變量 p 指向 i 的(de)地址    
int *p;      // 這(zhè)兩行等價于上面一行
p = &i;
1. p 存放了(le) i 的(de)地址，我們就可(kě)以說“ p 指向了(le) i” ，但 p 和(hé) i 是兩個(gè)不同的(de)變量，修改一方不會影(yǐng)響另一個(gè)的(de)值。
2. *p 等價于 i ，i 等價于 *p;兩者是一塊内存空間，裏面的(de)值一變具變。

2.指針和(hé)函數

// 修改外部實參的(de)值
void func(int * p)
{
    *p = 100;   // 函數内修改外部變量的(de)值   
}
// 修改外部實參的(de)值，二級指針的(de)值
void func2(int ** p)
{
    *p = 100;   
    // 函數内修改外部變量的(de)值 ，這(zhè)裏實際修改的(de)是指針的(de)内部的(de)地址，這(zhè)裏直接自己修改并不嚴謹也(yě)不安全，隻是爲了(le)表達意思  
}
int main(void)
{
    // 修改外部實參
   int i = 10;
   func(&i);
   printf("i = %d",i);
   // 修改外部二級指針
   int *p = i; // 等價于 int *p; p = &i;
   func(&p);
   printf("i = %d",i);
   return 0;
}
// 通(tōng)過函數調用(yòng)，改變函數外部變量（實參）的(de)值

3.指針和(hé)數組

【指針】 和(hé) 【一維數組】

int a[5] = {1,2,3,4,5 };
 a[3] == *(a + 3)  
 // 等價于 a[3] == *(3 + a) == 3[a];
 // 3[a] 這(zhè)種寫法隻是不常用(yòng)，從原理(lǐ)上來(lái)說是正确的(de) a 等價于 a[0];
 // a 是數組中第一個(gè)元素，每個(gè)元素占用(yòng)内存單位長(cháng)度相同，
 // a[i] 中的(de) i 實際代表的(de)是單位長(cháng)度的(de)倍數

數組名:

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

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

下(xià)标和(hé)指針的(de)關系:

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

(2)、假設指針變量的(de)名字爲 p,

則 p + i 的(de)值爲 p + i * (p 所指向的(de)變量所占字節數)

(3)、每個(gè)下(xià)标表示的(de)是第 i+1 個(gè)元素，根據元素類型分(fēn)配的(de)字節長(cháng)度不同(int 類型4個(gè)字節)，每個(gè)字節都有對(duì)應的(de)内存地址編号，指針變量 p 保存的(de)是該元素首字節的(de)地址。

指針變量的(de)運算(suàn):　

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

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

指針變量可(kě)以加減一個(gè)整數，前提是最終結果不能超過指針最大(dà)可(kě)訪問範圍

// 指針變量的(de)運算(suàn)
p + i 的(de)值是 p + i*(所指向的(de)變量所占字節數)
p - i 的(de)值是 p - i*(所指向的(de)變量所占字節數)
p++   等價于 p + 1
p--   等價于 p - 1
// 下(xià)面是一個(gè)通(tōng)過函數修改數組内部元素
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); // 調用(yòng)
}

結構體

爲什(shén)麽會出現結構體、

爲了(le)表示一些複雜(zá)的(de)數據，而普通(tōng)的(de)基本數據無法滿足要求.

什(shén)麽叫結構體

結構體是用(yòng)戶根據實際需要，自己定義的(de)複合數據類型

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

如何使用(yòng)結構體

總結起來(lái)有兩種結構體的(de)使用(yòng)方式：直接使用(yòng) && 通(tōng)過指針使用(yòng)

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

struct Student *pst = &ss;

ss.name ;  這(zhè)裏直接操作結構體本身

pst -> name ;   這(zhè)裏通(tōng)過指針地址操作，更加節省空間

struct Student{ // 自定義結構體
    int age;
    char * name;
    double height;
    char name2[100];
};
int main(void) {
   struct Student s = {12,"xiaoyou",1.73,"xiaozhang"};
// 直接使用(yòng)
   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);
   // 以指針的(de)方式使用(yòng)
   struct Student *pst = &ss;
   pst -> name = "my new name";
   printf(" name = %s
",pst->name);
   printf(" name = %s
",(*pst)->name);
// pst -> name 等價于 (*pst).name ,
// 而(*pst).name 又等價于 ss.name
// 所以 pst -> name 等價于 ss.name
   return 0;
}

注意事項

結構體變量的(de)類型爲： struct Student

結構體變量不能加減乘除，但是能夠相互賦值

普通(tōng)結構體變量和(hé)結構體指針變量作爲函數傳參的(de)問題

typedef struct Student{ // 結構體定義
    int age;
    char * name;
    char name2[100];
    double height;
}myStudent;
// 直接傳遞整個(gè)結構體數據，耗時(shí) && 浪費内存空間
void func(struct Student st);
// 直接傳遞 隻占用(yòng) 4 byte 的(de)指針，省時(shí)效率也(yě)高(gāo) <推薦用(yòng)法>
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);
}

動态内存分(fēn)配和(hé)釋放

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

程序中我們爲了(le)避免這(zhè)種情況，應該使用(yòng)動态的(de)方式創建和(hé)銷毀數組。

// 靜态創建數組
int a[5] = {1,2,3,4,5};

動态構造一維數組

動态構造一個(gè) int 型的(de)一維數組。

int *p = (int *)malloc(int length);
1. void * malloc(size_t __size) 函數,隻有一個(gè) int 類型的(de)形參，表示要求系統分(fēn)配的(de)字節數
2. malloc 函數的(de)功能是請求系統 length 個(gè)字節的(de)内存空間，如果請求完成則返回的(de)是第一個(gè)字節的(de)地址，
    如果請求不成功，則返回NULL
3. malloc 函數能且隻能返回第一個(gè)字節的(de)地址，所以我們需要把沒有實際意義的(de)第一個(gè)字節地址（幹地址）轉化(huà)爲一個(gè)有實際意義的(de)地址，
    所以 malloc 前面必須加(數據類型 *)，表示把這(zhè)個(gè)無意義的(de)地址轉化(huà)爲對(duì)應類型的(de)地址
    實例：
        int *p = (int *)malloc(50);
        表示将系統分(fēn)配的(de) 50 個(gè)字節的(de)第一個(gè)字節的(de)地址轉化(huà)爲 int 類型的(de)地址，準确的(de)說是轉化(huà)爲 4 個(gè)一組的(de)地址的(de)首地址，
        這(zhè)樣 p 就指向了(le)第一個(gè)四個(gè)字節··· p+i 就指向了(le)第 i+1 個(gè)四個(gè)字節，p[0],p[i]也(yě)就分(fēn)别是第一個(gè)，第i+1個(gè)元素。
        double *p = (double *)malloc(80);
        表示将系統分(fēn)配的(de) 80 個(gè)字節的(de)第一個(gè)字節的(de)地址轉化(huà)爲 double 類型的(de)地址，準确的(de)說是轉化(huà)爲 8 個(gè)一組的(de)地址的(de)首地址，
        這(zhè)樣 p 就指向了(le)第一個(gè)八個(gè)字節··· p+i 就指向了(le)第 i+1 個(gè)八個(gè)字節，p[0],p[i]也(yě)就分(fēn)别是第一個(gè)，第i+1個(gè)元素。
4. free(p);
    釋放 p 所指向的(de)内存，而不是釋放 p 本身所占用(yòng)的(de)内存

代碼示例如下(xià)：

void test2(void)
{
    int len;
    printf("請輸入你要動态創建的(de)數組長(cháng)度:");
    scanf("%d",&len);
    int *pArr = (int *)malloc(len); // 動态創建數組
    *pArr = 4;      // 相當于 a[0] = 4;  這(zhè)裏 pArr 就等于數組首地址，等于數組名
    pArr[2] = 5;    // 相當于 a[2] = 5;
    printf("pArr[0] = %d 
pArr[2] = %d
",pArr[0],pArr[2]);
    free(pArr);     // 使用(yòng)完畢，釋放對(duì)應的(de)數組空間 
}

跨函數使用(yòng)内存

在函數内部分(fēn)配的(de)局部變量，在函數調用(yòng)完成之後就會被系統回收，其内存也(yě)會消失。但是程序中常常需要定義一塊内存，當我們用(yòng)完之後再會回收。如 OC 語言中對(duì)象。所以需

要保存住分(fēn)配的(de)内存，應該用(yòng)動态分(fēn)配内存，當用(yòng)完之後再手動釋放。這(zhè)也(yě)是C語言的(de)一個(gè)不足之處：内存需要我們手動創建和(hé)手動釋放，這(zhè)也(yě)是 OC 語言在開發 iOS 程序時(shí)候，

我們所講的(de)MRC。【蘋果也(yě)發現了(le)這(zhè)個(gè)不足，于 iOS 5 的(de)時(shí)候推出了(le)ARC 】

下(xià)面是一個(gè)跨函數使用(yòng)内存的(de)例子：

// 這(zhè)個(gè)例子已經非常有面向對(duì)象的(de)味道了(le)
typedef struct Student{     // 自定義 student 結構體
    int age;
    char * name;
}myStudent;
myStudent * createStudent(void); // 創建 student 
void showStudent(myStudent *);   // 輸出 student
int main(void) {
    myStudent *p = createStudent();  // 創建 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. 小結

本文主要講解了(le)數據結構的(de)定義和(hé)簡介。

回顧了(le)學習(xí)數據結構應該具備的(de)一些 C語言 的(de)基礎知識，如指針、結構體、和(hé)内存等。

後面會繼續開始對(duì)數據結構的(de)講解。