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

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

嚴(yán)蔚敏,《數(shù)據(jù)結(jié)構(gòu)》,北京:清華大學(xué)出版社參考書(shū)：嚴(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é)時(shí)章內(nèi)容學(xué)時(shí)

1序論36數(shù)組和廣義表42C語(yǔ)言補(bǔ)充37樹(shù)和二叉樹(shù)93線性表68圖94棧和隊(duì)列49查找85串410內(nèi)部排序6數(shù)據(jù)結(jié)構(gòu)——56學(xué)時(shí)課堂教學(xué)4第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(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)的定義人腦：感受→判斷→計(jì)算→記憶→反應(yīng)電腦：輸入→控制→運(yùn)算→存儲(chǔ)→輸出1.從計(jì)算機(jī)工作的特點(diǎn)說(shuō)起用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)要考慮以下步驟：(1)

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

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

編寫(xiě)程序。(4)

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

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

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

實(shí)例1:線性關(guān)系:列車(chē)中各車(chē)箱之間的關(guān)系就是線性的。排隊(duì)買(mǎi)車(chē)票人之間的關(guān)系是線性的。疊盤(pán)子中各盤(pán)子之間的關(guān)系是線性的。9實(shí)例2:層次關(guān)系

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

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

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

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

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

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

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

VS計(jì)算機(jī)高手大家想不想成為

計(jì)算機(jī)高手呢？19這門(mén)課的特點(diǎn)和學(xué)習(xí)方法武林高手和計(jì)算機(jī)高手的共同特性大抵都很聰明，悟性奇高。不管是什么，都能做到舉一反三。好動(dòng)?？偸菚?huì)把自己的疑問(wèn)通過(guò)實(shí)戰(zhàn)來(lái)獲得答案。不斷修煉基礎(chǔ)和內(nèi)功。除傳統(tǒng)意義內(nèi)功外，內(nèi)功還包括經(jīng)驗(yàn)值。執(zhí)著。不管是練功的時(shí)候，還是實(shí)戰(zhàn)的時(shí)候，不管是對(duì)自己的信念還是自己所從事的事情。這門(mén)課的特點(diǎn)和學(xué)習(xí)方法

注重理解－舉一反三。

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

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

Data-Structure=(D，S)

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

Complex=(C，R)

其中：C是含兩個(gè)實(shí)數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。24根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹(shù)形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹(shù)圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？答：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)可細(xì)分為4類(lèi)：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)}解：上述表達(dá)式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。26（2）

S=(D,R)

D={di|1≤i≤5}

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

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

1345元素1

1400

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

1400元素2

1536…….……..…….

1536元素3

1346

鏈?zhǔn)酱鎯?chǔ)

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

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

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

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

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

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

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

D上的操作集ADT抽