教學目標1、知識目標1）了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的有關(guān)概念；2）掌握數(shù)據(jù)結(jié)構(gòu)包含的三個方面、邏輯結(jié)構(gòu)的分類、四種基本邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的四種存儲方法中的順序存儲方法和鏈式存儲方法；3）掌握算法及算法的五個重要特性。2、能力目標：能熟練進行時間復雜度的算法分析，從而選擇一個好的算法。3、素質(zhì)目標：養(yǎng)成對算法進行分析的良好職業(yè)習慣。2一、任務(wù)描述程序設(shè)計就是使用計算機解決現(xiàn)實生活中的實際問題。對于給定的一個實際問題，在進行程序設(shè)計時，首先要把實際問題中用到的信息抽象為能夠用計算機表示的數(shù)據(jù)；第二要把抽象出來的這些數(shù)據(jù)建立一個數(shù)據(jù)模型，這個數(shù)據(jù)模型也稱為邏輯結(jié)構(gòu)，即建立數(shù)據(jù)的邏輯結(jié)構(gòu)；第三要把邏輯結(jié)構(gòu)中的數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系存放到計算機中，即建立數(shù)據(jù)的存儲結(jié)構(gòu)；最后在所建立的存儲結(jié)構(gòu)上實現(xiàn)對數(shù)據(jù)元素的各種操作，即算法的實現(xiàn)。本任務(wù)就是要使大家了解計算機中的數(shù)據(jù)表示，理解數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法的有關(guān)概念；能夠選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；能夠?qū)λ惴ㄟM行時間復雜度分析，從而選擇一個好的算法，帶領(lǐng)大家走進數(shù)據(jù)結(jié)構(gòu)。3二、知識儲備（一）基本概念1、數(shù)據(jù)（Data）

數(shù)據(jù)是信息的載體。它能夠被計算機識別、存儲和加工處理，是計算機程序加工的“原料”。隨著計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的范疇包括：整數(shù)、實數(shù)、字符串、圖像和聲音等。2、數(shù)據(jù)元素（DataElement）

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點、頂點、記錄。3、數(shù)據(jù)項（Dataitem）數(shù)據(jù)項是具有獨立含義的最小標識單位。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（也可稱為字段、域、屬性）組成。例如：學生的信息，包括：學號、姓名、成績。一個學生的信息就是一個數(shù)據(jù)元素。44、數(shù)據(jù)結(jié)構(gòu)（DataStructure）：數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：①數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)（邏輯）結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組（D，R），其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。②數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系在計算機存儲器內(nèi)的表示。③

數(shù)據(jù)的運算：即對數(shù)據(jù)施加的操作。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，只有確定了存儲結(jié)構(gòu)，才能具體實現(xiàn)這些運算。數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及它們之間的相互關(guān)系和所定義的算法如何在計算機上實現(xiàn)，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。例如：某個班學生成績表，包括：學號、姓名和各科成績，每一個學生的信息都是一個數(shù)據(jù)元素。數(shù)據(jù)元素之間有這樣的邏輯關(guān)系：在一個數(shù)據(jù)元素的前面最多有一個與其相鄰的數(shù)據(jù)元素（稱為直接前驅(qū)），在一個數(shù)據(jù)元素的后面也最多有一個與其相鄰的數(shù)據(jù)元素（稱為直接后繼）。數(shù)據(jù)元素之間的這種關(guān)系構(gòu)成了學生成績表的邏輯結(jié)構(gòu)。5（二）數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)1、數(shù)據(jù)的邏輯結(jié)構(gòu)1）線性結(jié)構(gòu)：有且僅有一個開始結(jié)點和一個終端結(jié)點，且所有結(jié)點都最多只有一個直接前驅(qū)和一個直接后繼。2）非線性結(jié)構(gòu)：一個結(jié)點可能有多個直接前驅(qū)和多個直接后繼。2、基本邏輯結(jié)構(gòu)（如圖）①集合結(jié)構(gòu)：數(shù)據(jù)元素的有限集合。數(shù)據(jù)元素之間除了“屬于同一個集合”的關(guān)系之外沒有其他關(guān)系。

②線性結(jié)構(gòu)：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間形成一對一的關(guān)系。③樹型結(jié)構(gòu)：樹是層次數(shù)據(jù)結(jié)構(gòu)，樹中數(shù)據(jù)元素之間存在一對多的關(guān)系。④圖狀結(jié)構(gòu)：圖中數(shù)據(jù)元素之間的關(guān)系是多對多的。集合結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)63、存儲結(jié)構(gòu)存儲結(jié)構(gòu)可用以下四種存儲方法得到：①順序存儲方法：把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)通常是借助于程序語言的數(shù)組來描述的。②鏈接存儲方法：該方法不要求邏輯上相鄰的結(jié)點在物理位置上也相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段來表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)通常是借助于程序語言的指針來描述的。如圖：③索引存儲方法：除建立結(jié)點信息外，還要建立附加的索引表來標識結(jié)點的地址。④散列存儲方法：根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。

300008301……89.5400008303……90.5305008325……83302008318……78NULLhead30004000305030207（三）算法及其特性1、算法：是對特定問題求解步驟的一種描述，是指令的有限序列。一個算法是一系列將輸入轉(zhuǎn)換為輸出的計算步驟。2、算法的重要特性：①輸入：一個算法應(yīng)該有零個或多個輸入。②有窮性：一個算法必須在執(zhí)行有窮步驟之后正常結(jié)束，而不能形成無窮循環(huán)。③確定性：算法中的每一條指令必