一、什么是數(shù)據(jù)結構

1、數(shù)據(jù)結構的起源

• 數(shù)據(jù)結構不是研究數(shù)值計算的這些是數(shù)學家應該研究的問題，它是研究計算機存儲、組織數(shù)據(jù)的方式問題的學科，數(shù)據(jù)結構會影響算法的效率，合適的數(shù)據(jù)結構可以帶來更高的運行或存儲效率。

• 1968年，美國的高納德（Donald E. Knuth）教授《基本算法》，開創(chuàng)了數(shù)據(jù)結構課程體系的先河。

• 程序設計 = 數(shù)據(jù)結構 + 算法

  • 憑借一句話獲得圖靈獎的Pascal之父——Nicklaus Wirth，讓他獲得圖靈獎的這句話就是他提出的著名公式：“算法+數(shù)據(jù)結構=程序”。

  • 這個公式對計算機科學的影響程度足以類似物理學中愛因斯坦的“E=MC^2”——一個公式展示出了程序的本質(zhì)。

2、數(shù)據(jù)結構的基本概念

• 數(shù)據(jù)(data)：所有能輸入到計算機中去的描述客觀事物的符號
• 數(shù)據(jù)項(data item)：有獨立含義的數(shù)據(jù)最小單位，也稱域(field)
• 數(shù)據(jù)元素(data element)：數(shù)據(jù)結構的基本單位，也稱節(jié)點（node）或記錄（record）
• 數(shù)據(jù)結構(data structure)：數(shù)據(jù)元素和數(shù)據(jù)元素關系的集合
• 算法(algorithm)：是對特定問題求解步驟的一種描述，是指令的有限序列

#include <stdio.h>

typedef struct Student
{
    int id;         // 結構成員就是 數(shù)據(jù)項
    char name[20];
    char sex;
    short age;
    float score;
}Student;

int main(int argc,const char* argv[])
{
    Student stu = { // 結構變量 stu 是數(shù)據(jù)元素，負責給他初始化的叫數(shù)據(jù)
        10086,
        "hehe",
        'w',
        23,
        88.5
    };  

    // 數(shù)據(jù)結構
    Student stus[5] = { 
        {10010,"hehe1",'m',18,92},
        {10011,"hehe2",'w',18,91},
        {10012,"hehe3",'m',17,93},
        {10013,"hehe4",'w',18,96},
        {10014,"hehe5",'m',15,95},
    };  

    // 算法
    for(int i=0; i<5; i++)
    {   
        printf("%d %s %c %hd %g\n",
            stus[i].id,
            stus[i].name,
            stus[i].sex,
            stus[i].age,
            stus[i].score);
    }   
}

3、數(shù)據(jù)結構的三個方面

• 數(shù)據(jù)的邏輯結構：元素之間具有什么關系。
• 數(shù)據(jù)的存儲結構：元素在內(nèi)存中如何存儲的。
• 數(shù)據(jù)結構的運算：數(shù)據(jù)結構應具有的功能或擅長的功能。

二、數(shù)據(jù)元素之間的邏輯結構有四種基本類型

• 集合：數(shù)據(jù)元素之間除了同屬一個集合外沒有其它關系。
• 線性結構：數(shù)據(jù)元素之間存在一對一的關系，也被稱為線性表，簡稱為表，最具代表性的就是數(shù)組、鏈表。
• 樹型結構：數(shù)據(jù)元素之間存在一對多的關系，如：族譜關系、組織關系。
• 圖狀結構：數(shù)據(jù)元素之間存在多對多的關系，如：地鐵、高鐵線路圖。

三、數(shù)據(jù)結構的存儲方式

數(shù)據(jù)結構在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素關系的表示。

元素之間的關系在計算機中有兩種不同的表示方法，順序表示和非順序表示。

1、順序存儲結構

數(shù)據(jù)存儲在一段連續(xù)的空間中，用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素的關系。

• 優(yōu)點：隨機訪問方便，訪問效率極高。

• 缺點：插入刪除不方便。

2、鏈式存儲結構

結構中的數(shù)據(jù)元素存放在彼此獨立的地址空間中，每個獨立的地址空間稱為節(jié)點。

在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針，用來表示數(shù)據(jù)元素之間的關系。

• 優(yōu)點：插入刪除方便，空間利用率高。
• 缺點：隨機訪問不方便，只能由前到后逐個訪問。

四、邏輯結構和存儲結構的關系

每種邏輯結構采用何種物理結構實現(xiàn)，并沒有明確規(guī)定，通常根據(jù)實現(xiàn)的難易程度，以及在時間和空間方面的要求，選擇最適合的物理結構，也不排除復合多種物理結構實現(xiàn)一種邏輯結構的可能。

五、數(shù)據(jù)結構的運算

• 1、建立數(shù)據(jù)結構：create

• 2、銷毀數(shù)據(jù)結構：destroy

• 3、從數(shù)據(jù)結構中刪除一個元素：delete

• 4、把一個元素插入到一個數(shù)據(jù)結構中：install

• 5、訪問數(shù)據(jù)結構中的元素：access

• 6、修改數(shù)據(jù)結構中的元素：modify

• 7、對數(shù)據(jù)結構中的元素進行排序：sort

• 8、在數(shù)據(jù)結構中查找元素：query