一、緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)

概念：簡單的來說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及他們之間的關(guān)系和操作等的學科。

數(shù)據(jù)在計算機中進行處理，要考慮：

（1）數(shù)據(jù)本身的數(shù)學性質(zhì)

（2）數(shù)據(jù)的存儲結(jié)構(gòu)

程序設(shè)計的實質(zhì)是：對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計一種好的算法

數(shù)據(jù)結(jié)構(gòu)介于：數(shù)學、計算機硬件、計算機軟件之間。

1.2 基本概念和術(shù)語

1.2.1 相關(guān)概念

數(shù)據(jù)：對客觀事物的符號表示；

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，數(shù)據(jù)元素可以有多個數(shù)據(jù)項組成；

數(shù)據(jù)項：數(shù)據(jù)不可分割的最小單位；

數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集；

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

1.2.2 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有以下四類基本結(jié)構(gòu)：

（1）集合

（2）線性結(jié)構(gòu)

（3）樹形結(jié)構(gòu)

（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

1.2.3數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

邏輯結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系

物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示

1.2.4數(shù)據(jù)元素之間的關(guān)系的兩種表示方法：

順序映像和非順序映像

特點：

順序映像：借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系

非順序：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系

由此到兩種不同的存儲結(jié)構(gòu)：

1、順序存儲結(jié)構(gòu)

2、鏈式存儲結(jié)構(gòu)

任何一個算法的設(shè)計取決于選他的數(shù)據(jù)（邏輯）結(jié)構(gòu)，

而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。

1.2.5結(jié)構(gòu)類型和非結(jié)構(gòu)類型

非結(jié)構(gòu)的原子類型：C語言中的基本類型（整形、實型、字符型和枚舉類型）、指針類型、空類型

結(jié)構(gòu)類型：由若干成分按照某種結(jié)構(gòu)組成的，可以分解，成分可以是非結(jié)構(gòu)的也可以是結(jié)構(gòu)的。

1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)

1.4算法和算法分析

1.4.1算法概念及特性

概念：算法是對特定問題求解步驟的一種描述，是指令的有限序列，其中一個指令表示一個或多個操作。

5個特性：

（1）有窮性 （2）確定性 （3）可行性 （4）輸入 （5）輸出

1.4.2算法設(shè)計的要求

一個“好”的算法該有的目標：

（1）正確性

（2）可讀性

（3）健壯性

（4）效率與低存儲量需求

1.4.3算法效率的度量（時間復雜度、空間復雜度）

（1）事后統(tǒng)計 （2）事前分析估算

時間復雜度(漸近時間復雜度)：

例：

//(a)
{
    ++x;
    s=0;
}
//(b)
for(i=1;i<=n;i++){
    ++x;
    s+=x;
}
//(c)
for(j=1;j<=n;++j){
    for(k=1;k<=n;++k){
        ++x;
        s+=x;
    }
}

其中語句的頻度分別為 1、n、n^{2，則其時間復雜度分別為O(1)、O(n)、O(n}2)，分別稱為常量階、線性階和平方階。時間復雜度還有對數(shù)階O(log n)、指數(shù)階O(2^n)。

我們盡可能使用多項式階的算法O(n^k)，而不希望使用指數(shù)階算法

基本操作執(zhí)行次數(shù)（或語句頻度），只需求出他關(guān)于n的增長率或階即可

例：

for(i=2;i<=n;++i)
    for(j=2;j<=i-1;++j){
        ++x;
        a[i][j] = x;
    }

語句++x執(zhí)行次數(shù)關(guān)于n的增長率為n^2，他的語句頻度表達式為

空間復雜度：