摘要：程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是關(guān)系，沒錯(cuò)，就是數(shù)據(jù)元素相互之間存在的一種或多種特定關(guān)系的集合。物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。

程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法

數(shù)據(jù)結(jié)構(gòu)就是關(guān)系，沒錯(cuò)，就是數(shù)據(jù)元素相互之間存在的一種或多種特定關(guān)系的集合。

傳統(tǒng)上，我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系，也是我們今后最需要關(guān)注和討論的問題。

物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。

常用的數(shù)據(jù)結(jié)構(gòu)有：

數(shù)組，隊(duì)列（queue），堆（heap）,棧（stack），鏈表（linked list ），樹（tree），圖（graph）和散列表（hash）

棧（stack）：運(yùn)算只在表的一端進(jìn)行；隊(duì)列（Queue）：運(yùn)算只在表的兩端進(jìn)行。

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

與棧相反，隊(duì)列是一種先進(jìn)先出（First In First Out, FIFO）的線性表。

與棧相同的是，隊(duì)列也是一種重要的線性結(jié)構(gòu)，實(shí)現(xiàn)一個(gè)隊(duì)列同樣需要順序表或鏈表作為基礎(chǔ)。

集合結(jié)構(gòu)

線性結(jié)構(gòu)

樹形結(jié)構(gòu)

圖形結(jié)構(gòu)

數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。
例如我們編程語言的數(shù)組結(jié)構(gòu)就是這樣滴。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表：就好像是排隊(duì)一樣，具有線一樣性質(zhì)的結(jié)構(gòu)，它是由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列。

若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，而最后一個(gè)元素?zé)o后繼，其他元素都有且只有一個(gè)前驅(qū)和后繼。

若將線性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1,稱ai-1是ai的直接前驅(qū)元素,ai+1是ai的直接后繼元素。

數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。

例如很多編程語言的整型，浮點(diǎn)型，字符型這些指的就是數(shù)據(jù)類型。

在計(jì)算機(jī)中，內(nèi)存不是無限大的，如果要計(jì)算或處理一些較大的數(shù)時(shí)，需要開辟較大的內(nèi)存空間，于是就要對(duì)計(jì)算機(jī)進(jìn)行數(shù)據(jù)類型分類，分出多種數(shù)據(jù)類型來適合各種不同的計(jì)算條件差異。

在C語言中，數(shù)據(jù)類型可以分為：

原子類型：不可以再分解的基本類型，例如整型、浮點(diǎn)型、字符型等。

結(jié)構(gòu)類型：由若干個(gè)類型組合而成，是可以再分解的，例如整型數(shù)組是由若干整型數(shù)據(jù)組成的。

算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

算法具有五個(gè)基本特征：輸入、輸出、有窮性、確定性和可行性。

輸出：算法至少有一個(gè)或多個(gè)輸出。
有窮性：指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。

確定性：算法的每一個(gè)步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。

可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。

正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案。

高級(jí)語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：

1. 算法采用的策略，方案
2. 編譯產(chǎn)生的代碼質(zhì)量
3. 問題的輸入規(guī)模
4. 機(jī)器執(zhí)行指令的速度

我們可以想象，線性表有兩種物理存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

線性表（a1,a2,…,an）的順序存儲(chǔ)如下：

#define MAXSIZE 20    

typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int length;    // 線性表當(dāng)前長(zhǎng)度
} SqList;

總結(jié)下，順序存儲(chǔ)結(jié)構(gòu)封裝需要三個(gè)屬性：

存儲(chǔ)空間的起始位置，數(shù)組data，它的存儲(chǔ)位置就是線性表存儲(chǔ)空間的存儲(chǔ)位置。

線性表的最大存儲(chǔ)容量：數(shù)組的長(zhǎng)度MaxSize。

線性表的當(dāng)前長(zhǎng)度：length。

    如果插入位置不合理，拋出異常；

    如果線性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度，則拋出異?；騽?dòng)態(tài)增加數(shù)組容量；

    從最后一個(gè)元素開始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置；

    將要插入元素填入位置i處；

    線性表長(zhǎng)+1。