數(shù)據(jù)結(jié)構(gòu)第一次課緒論新

數(shù)據(jù)結(jié)構(gòu)1手機師的聯(lián)系方式：2課時安排：數(shù)據(jù)結(jié)構(gòu)——56學(xué)時+8學(xué)時實驗教材：

嚴(yán)蔚敏,《數(shù)據(jù)結(jié)構(gòu)》,北京:清華大學(xué)出版社參考書：嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)》.北京:清華大學(xué)出版社嚴(yán)蔚敏等，《數(shù)據(jù)結(jié)構(gòu)題集》,1995WilliamFord，WilliamTopp，《DataStructurewithC++》清華大學(xué)出版社PrenticeHall聯(lián)合出版,19963內(nèi)容安排章內(nèi)容學(xué)時章內(nèi)容學(xué)時

1序論36數(shù)組和廣義表42C語言補充37樹和二叉樹93線性表68圖94棧和隊列49查找85串410內(nèi)部排序6數(shù)據(jù)結(jié)構(gòu)——56學(xué)時課堂教學(xué)4第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)*1.4算法和算法分析*51.1什么是數(shù)據(jù)結(jié)構(gòu)Q1：數(shù)據(jù)結(jié)構(gòu)的定義？Q3：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？Q2：數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容？Q4：如何學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？61.1.1數(shù)據(jù)結(jié)構(gòu)的定義人腦：感受→判斷→計算→記憶→反應(yīng)電腦：輸入→控制→運算→存儲→輸出1.從計算機工作的特點說起用計算機解決一個具體問題時要考慮以下步驟：(1)

從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型。即從具體問題中找出操作對象之間含有的關(guān)系，然后用數(shù)學(xué)語言加以描述。(2)

設(shè)計一個適合該數(shù)學(xué)模型的算法。(3)

編寫程序。(4)

進行測試、調(diào)整、修改，直至解決問題。7科學(xué)計算→事務(wù)處理→人工智能

算法復(fù)雜度↑計算機問題求解＝信息表示＋信息處理程序設(shè)計＝數(shù)據(jù)結(jié)構(gòu)＋算法數(shù)值型數(shù)據(jù)→字符、表格、圖形圖像

對象復(fù)雜度↑數(shù)據(jù)結(jié)構(gòu)主要解決計算機中的信息表示及關(guān)系定義問題8線性表從實際生活中的問題說起：在實際問題中，各個對象之間的關(guān)系有線性的、層次的和網(wǎng)狀的等等.

實例1:線性關(guān)系:列車中各車箱之間的關(guān)系就是線性的。排隊買車票人之間的關(guān)系是線性的。疊盤子中各盤子之間的關(guān)系是線性的。9實例2:層次關(guān)系

在軍隊的編制中，軍下面是師，師下面是團，軍、師、團之間是層次關(guān)系。人的輩分關(guān)系中，祖輩下是父輩，父輩下是子輩，這些是層次關(guān)系。學(xué)校的編制中，學(xué)校分成若干個學(xué)院、學(xué)院下又分成若干個系、系下又分成若干個教研室，這些也都是層次關(guān)系。

10實例3:網(wǎng)狀關(guān)系在城市鐵路交通圖中，各城市之間的關(guān)系是網(wǎng)狀關(guān)系。

電話網(wǎng)中，各電話之間是網(wǎng)狀關(guān)系。

計算機網(wǎng)絡(luò)中，各計算機之間是網(wǎng)狀關(guān)系。11數(shù)據(jù)結(jié)構(gòu)定義:是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科

2.可以直接地認為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。通過以上幾例可以看出:1.描述非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。121.1.2數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容131.1.3學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用1.計算機系列課程之間的聯(lián)系

141.1.3學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用2.數(shù)據(jù)結(jié)構(gòu)課程的地位是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程關(guān)系物理存儲數(shù)學(xué)軟件硬件邏輯結(jié)構(gòu)與操作15離散數(shù)學(xué)+計算機數(shù)據(jù)處理1.1.3學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用2.數(shù)據(jù)結(jié)構(gòu)課程的地位地位：專業(yè)基礎(chǔ)課，應(yīng)用范圍廣、作用大161.1.3學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。3.有助于提高程序設(shè)計能力優(yōu)秀程序設(shè)計＝好數(shù)據(jù)結(jié)構(gòu)＋好算法程序設(shè)計＝數(shù)據(jù)結(jié)構(gòu)＋算法計算機問題求解＝信息表示＋信息處理17計算機專業(yè)＝?jīng)]有專業(yè)？通用工具－二十一世紀(jì)必備素質(zhì)之一其他專業(yè)都在學(xué)入門知識很簡單，沒有優(yōu)勢可言

所以，要想比別人強，就必須成為高手1.1.4如何學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？18武林高手計算機高手基礎(chǔ)練得好站樁、劈掌等程序設(shè)計基礎(chǔ)知識C、C++、Java、C#等內(nèi)功內(nèi)功心法如易筋經(jīng)、太極內(nèi)功心法等軟硬件技術(shù)基礎(chǔ)專業(yè)知識（物理、力學(xué)）武器、門派招式刀、劍、鉤等華山劍法、少林棍等可視化開發(fā)工具VC、VB、Delphi、VJ、VC#等武林高手

VS計算機高手大家想不想成為

計算機高手呢？19這門課的特點和學(xué)習(xí)方法武林高手和計算機高手的共同特性大抵都很聰明，悟性奇高。不管是什么，都能做到舉一反三。好動?？偸菚炎约旱囊蓡柾ㄟ^實戰(zhàn)來獲得答案。不斷修煉基礎(chǔ)和內(nèi)功。除傳統(tǒng)意義內(nèi)功外，內(nèi)功還包括經(jīng)驗值。執(zhí)著。不管是練功的時候，還是實戰(zhàn)的時候，不管是對自己的信念還是自己所從事的事情。這門課的特點和學(xué)習(xí)方法

注重理解－舉一反三。

注重實踐－通過實踐加深理解，眼過千遍不如手過一遍。有一定難度－相信通過努力能學(xué)好－不畏艱難，執(zhí)著追求?！懊丶痹谑?01.不得無故曠課、缺交作業(yè)，每次扣5分，若作業(yè)被確認為是抄襲的，抄襲者和被抄襲者平時成績減半，但有好的表現(xiàn)也會有獎勵分。兩條紀(jì)律：考試方式：筆試（閉卷）＋平時成績占70%占30%2.課堂內(nèi)請不要接打手機。

若有特殊情況，請切換到震動模式。（作業(yè)、實驗等占20％，考勤、提問占10％）211.2基本概念和術(shù)語數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)值型＋非數(shù)值型數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。22數(shù)據(jù)數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素數(shù)據(jù)項性質(zhì)相同存在一種或多種特定關(guān)系數(shù)據(jù)基本單位23數(shù)據(jù)結(jié)構(gòu)的形式化定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組：

Data-Structure=(D，S)

其中D是數(shù)據(jù)元素的有限集,S是D上關(guān)系的有限集。例復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：

Complex=(C，R)

其中：C是含兩個實數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。24根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)——一個對多個，如樹圖狀結(jié)構(gòu)——多個對多個，如圖解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？答：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。邏輯結(jié)構(gòu)可細分為4類：25例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。26（2）

S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d3該結(jié)構(gòu)是非線性的圖。解：上述表達式可用圖形表示為：27數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān) 算法設(shè)計 邏輯結(jié)構(gòu) 算法實現(xiàn) 存儲結(jié)構(gòu) 最常用的存儲結(jié)構(gòu)為：順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？答：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示（或映像）。它依賴于計算機。存儲結(jié)構(gòu)可分為4大類：順序、鏈?zhǔn)?、索引、散?8元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲291536元素21400元素11346元素3∧元素41345h存儲地址存儲內(nèi)容指針

1345元素1

1400

1346元素4∧…….……..…….

1400元素2

1536…….……..…….

1536元素3

1346

鏈?zhǔn)酱鎯?/p>

h30解釋3：什么是數(shù)據(jù)的運算（操作或處理）？答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作,它在數(shù)據(jù)的存儲結(jié)構(gòu)上實現(xiàn)。最常用的數(shù)據(jù)運算有5種：插入、刪除、修改、查找、排序31數(shù)據(jù)結(jié)構(gòu)是從‘具體’到‘抽象’的過程中產(chǎn)生的。核心是分解與抽象。1)通過分解，可以劃分出數(shù)據(jù)的三個層次：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項；再通過抽象，舍去數(shù)據(jù)元素的具體內(nèi)容而關(guān)注它們的邏輯關(guān)系，就得到邏輯結(jié)構(gòu)。

2)通過分解，可以劃分出處理要求的各種功能；再通過抽象，舍去實現(xiàn)細節(jié)，就得到運算定義。

3)歸納1)、2)可把問題變換為數(shù)據(jù)結(jié)構(gòu)。程序=數(shù)據(jù)結(jié)構(gòu)+算法程序是從‘抽象’到‘具體’的過程中產(chǎn)生的。1)通過對數(shù)據(jù)存儲實現(xiàn)的考慮，得到存儲結(jié)構(gòu)；2)通過對運算實現(xiàn)細節(jié)的考慮，得到解決問題的程序。

解釋4：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作及算法的關(guān)系？32實例：結(jié)合生活中廚師學(xué)藝實例理解33如何應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識求解決實際問題？課堂學(xué)習(xí)內(nèi)容（動腦）課外練習(xí)內(nèi)容（動手）理論與實踐相結(jié)合數(shù)據(jù)結(jié)構(gòu)算法設(shè)計34層次\方面數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運算實現(xiàn)存儲結(jié)構(gòu)算法評價不同結(jié)構(gòu)的比較及算法分析數(shù)據(jù)結(jié)構(gòu)課程包括三個層次的五個要素：35

1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)Q1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？Q2抽象數(shù)據(jù)類型如何定義？Q3抽象數(shù)據(jù)類型如何表示和實現(xiàn)？

討論：36Q1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？數(shù)據(jù)類型：是一個值的集合和定義在該值上的一組操作的總稱。intfloat…抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離，實行數(shù)據(jù)封裝和信息隱蔽（基于邏輯結(jié)構(gòu)定義，獨立于存儲結(jié)構(gòu)）。37抽象數(shù)據(jù)類型38定義抽象數(shù)據(jù)類型有何意義？舍棄個別的,非本質(zhì)的數(shù)據(jù)關(guān)系,抽象出共同的,本質(zhì)的數(shù)據(jù)關(guān)系,研究共性特征。使用與實現(xiàn)分離，實行數(shù)據(jù)封裝和信息隱蔽，方便程序的維護、改錯、升級和移植是現(xiàn)代程序設(shè)計方法－面向?qū)ο蟪绦蛟O(shè)計方法設(shè)計思路的基本體現(xiàn)。封裝、繼承和多態(tài)39Q2抽象數(shù)據(jù)類型如何定義？抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對象D上的關(guān)系集

D上的操作集ADT抽