1、數(shù)據(jù)結(jié)構(gòu)、課程背景數(shù)據(jù)結(jié)構(gòu)是校訂機(jī)構(gòu)相關(guān)專業(yè)的重要專業(yè)基礎(chǔ)課。 它主要研究實(shí)現(xiàn)修正機(jī)加工對(duì)象的邏輯結(jié)構(gòu)、修正機(jī)中的表現(xiàn)形式、各種基本操作的算法。 掌握本課程的內(nèi)容是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的必要條件，也是編程的必要基礎(chǔ)。 開(kāi)發(fā)程序系統(tǒng)的實(shí)際問(wèn)題通?？煞譃橐韵?個(gè)階段：1、分析階段：揭示用戶需求2 .設(shè)置修訂階段：建立求解系統(tǒng)的實(shí)現(xiàn)模型，著重于算法設(shè)置修訂和數(shù)據(jù)結(jié)構(gòu)設(shè)置修訂3 .編碼(與本課程有最密切的關(guān)系)、機(jī)外顯示處理要求、邏輯結(jié)構(gòu)基本運(yùn)算、內(nèi)存結(jié)構(gòu)實(shí)現(xiàn)、本課程所述的主要內(nèi)容本課程中，數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、堆棧和隊(duì)列、字符串和排列、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)、檢索、 分別記述排序等學(xué)習(xí)本課程的基本方

2、法的l課要認(rèn)真閱讀認(rèn)真聽(tīng)講的l教材中的許多例題，掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念，最終獨(dú)立完成l章后的練習(xí)問(wèn)題認(rèn)真完成l實(shí)驗(yàn)和課程設(shè)置修訂。 課程安排：講座65點(diǎn)：系統(tǒng)介紹軟件設(shè)置修訂中常用的一些數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的存儲(chǔ)結(jié)構(gòu)和算法，以及常用的一些檢索和排序算法。 本課程為以下課程的學(xué)習(xí)和軟件設(shè)置修訂水平的提高奠定了良好的基礎(chǔ)。 上機(jī)10學(xué)時(shí)(不夠):利用學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)和算法制作功能單一的小算法，用c語(yǔ)言實(shí)現(xiàn)。 課程設(shè)計(jì)課外(2周):加深理解，靈活掌握教學(xué)內(nèi)容，進(jìn)行軟件設(shè)計(jì)綜合訓(xùn)練。實(shí)驗(yàn)和課程設(shè)置修訂要求獨(dú)立完成，不與他人合作完成，不模仿他人，不選擇別人代替完成要求的至少一個(gè)實(shí)驗(yàn)，各實(shí)驗(yàn)選擇其中一個(gè)主題在本

3、學(xué)期第二十周完成課程設(shè)置修訂工作。 在每個(gè)人的文件夾中，實(shí)驗(yàn)報(bào)告：每個(gè)實(shí)驗(yàn)寫(xiě)實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告的內(nèi)容，用WORD軟件排版。 用提升機(jī)調(diào)試渦輪c環(huán)境下通過(guò)的源程序。參考書(shū)：數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)秦鋒主編科大出版社數(shù)據(jù)結(jié)構(gòu)例題詳細(xì)解和課程設(shè)置指導(dǎo)秦鋒主編科大出版社數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)嚴(yán)蔚敏主編清華大學(xué)出版社，第一章緒論，關(guān)于主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念算法的概念、記述方法和評(píng)價(jià)標(biāo)準(zhǔn)，本章學(xué)習(xí)要求理解：研究數(shù)據(jù)理解把握：算法的基本概念和算法的評(píng)價(jià)依據(jù)。 掌握：算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 第一章緒論，1.1數(shù)據(jù)結(jié)構(gòu)的概念1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型1.3算法和算法分析，1.1數(shù)據(jù)

4、結(jié)構(gòu)的概念，1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.1.2相關(guān)概念和術(shù)語(yǔ)1.1.3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容，1.1.1非數(shù)值修正：(數(shù)據(jù)量數(shù)學(xué)模型不能用數(shù)學(xué)方程式記述的對(duì)數(shù)數(shù)據(jù)的操作不僅僅是數(shù)值修正運(yùn)算，大多需要組織、管理、檢索。 例1人口信息檢索系統(tǒng)，表1-1無(wú)序的人口信息表，表1-2無(wú)序的人口信息表，例1人口信息檢索系統(tǒng)，例1人口信息檢索系統(tǒng)，表1-3人口信息索引表，特征： l每個(gè)人的信息占一行，全體人員的信息按身份證號(hào)碼順序構(gòu)成一個(gè)表這就是我們所說(shuō)的線性構(gòu)造。l對(duì)它的操作，通常是插入某人的信息，刪除某人的信息，更新某人的信息，在條件下檢索某人的信息等。例2在人機(jī)對(duì)奕問(wèn)題、特征： l求解過(guò)程中，所處理

5、的數(shù)據(jù)間存在階層關(guān)系，這是我們所說(shuō)的樹(shù)形結(jié)構(gòu)，作為對(duì)此的操作，有制作樹(shù)結(jié)構(gòu)，輸出最下位節(jié)點(diǎn)的內(nèi)容等。 例3教育訂正計(jì)劃的制定在制定教育訂正計(jì)劃時(shí)，有必要考慮各課程的開(kāi)設(shè)順序。 有些課程需要試點(diǎn)課程，有些課程不需要，有些課程是其他課程的試點(diǎn)課程。 例如，計(jì)算機(jī)專業(yè)課程的開(kāi)設(shè)狀況如表1-4所示。表1-4計(jì)算機(jī)專業(yè)學(xué)生的必修課程、課程前后關(guān)系的圖形描繪形式：圖1-3計(jì)算機(jī)專業(yè)必修課程的開(kāi)設(shè)前后關(guān)系、特征l課程間的前后關(guān)系通過(guò)用圖構(gòu)造記述的l安裝制作圖構(gòu)造，根據(jù)需要將圖構(gòu)造中的頂點(diǎn)線性排列。 結(jié)論修正算機(jī)的操作對(duì)象的關(guān)系越來(lái)越復(fù)雜，操作形式不僅僅是數(shù)值修正算法，更多的是組織管理這些具有一定關(guān)系的數(shù)據(jù)，

6、這被稱為非數(shù)值處理。 為了修正計(jì)算機(jī)能更有效地進(jìn)行這些非數(shù)值性的處理，有必要明確這些操作對(duì)象的特征、修正計(jì)算機(jī)中的顯示方式以及各操作的具體實(shí)現(xiàn)手段。 這是數(shù)據(jù)結(jié)構(gòu)這門課程研究的主要內(nèi)容。 數(shù)據(jù)結(jié)構(gòu)定義：是研究非數(shù)值修正算法的編程問(wèn)題中的修正算法機(jī)的操作對(duì)象和它們的關(guān)系與操作等的學(xué)科。 數(shù)據(jù)(data )是對(duì)客觀事物的符號(hào)表示。 在修正機(jī)科學(xué)中是指輸入到修正機(jī)中，可以由修正機(jī)程序處理的符號(hào)的集合。 “數(shù)據(jù)元素”(data element )數(shù)據(jù)的基本單位。 也稱為節(jié)點(diǎn)或記錄，通常具有概念的多方面信息。 數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)的最小單位，也被稱為項(xiàng)或場(chǎng)，并且1.1.2概念和術(shù)語(yǔ)，以及數(shù)據(jù)結(jié)構(gòu)數(shù)

7、據(jù)元素和數(shù)據(jù)元素之間的關(guān)系的集合，一般有以下三個(gè)2、計(jì)算機(jī)存儲(chǔ)器中數(shù)據(jù)要素和邏輯關(guān)系的表現(xiàn)方式。 這是計(jì)算機(jī)存儲(chǔ)器中邏輯結(jié)構(gòu)的映射，必須依賴于計(jì)算機(jī)，通常被稱為存儲(chǔ)器結(jié)構(gòu)。 3 .數(shù)據(jù)運(yùn)算，即添加到數(shù)據(jù)中的操作。 運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，而運(yùn)算的實(shí)現(xiàn)必須依賴于存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)只是抽象地反映數(shù)據(jù)要素的邏輯關(guān)系，根據(jù)數(shù)據(jù)要素間關(guān)系的基本特性，4種基本數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)要素之間沒(méi)有“屬于同一集合”以外的關(guān)系，要素是孤立的。 線性結(jié)構(gòu)是一對(duì)一的，在該結(jié)構(gòu)中，各元素的陣列成為一個(gè)表，第一個(gè)元素之后接著第二個(gè)元素，第二個(gè)元素之后接著第三個(gè)元素，依次類推，結(jié)構(gòu)整體像“鏈”一樣，稱為“線性結(jié)

8、構(gòu)”。 像線性表、堆棧、隊(duì)列樹(shù)結(jié)構(gòu)那樣的數(shù)據(jù)要素之間有一對(duì)多的關(guān)系。 呈分歧、階層狀態(tài)。 在這種結(jié)構(gòu)中，元件之間的邏輯關(guān)系通常被稱為父母與孩子之間的關(guān)系。 例如，家譜、行政組織結(jié)構(gòu)等都可以用樹(shù)結(jié)構(gòu)表示。 圖表結(jié)構(gòu)中的要素之間存在多對(duì)多的關(guān)系，即要素間的邏輯關(guān)系是任意的。 在這種構(gòu)造中，元件之間的邏輯關(guān)系也被稱為相鄰關(guān)系。 數(shù)據(jù)的存儲(chǔ)(物理)構(gòu)造數(shù)據(jù)的邏輯構(gòu)造與在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)和獨(dú)立的數(shù)據(jù)要素的表現(xiàn)形式不同，數(shù)據(jù)構(gòu)造中的數(shù)據(jù)要素不僅表示自身的實(shí)際內(nèi)容，而且明確數(shù)據(jù)要素之間的邏輯構(gòu)造。 中的組合圖層性質(zhì)變更選項(xiàng)。 鏈存儲(chǔ)通過(guò)指示元素的存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，索引存儲(chǔ)在存儲(chǔ)

9、數(shù)據(jù)元素中，同時(shí)其他索引表索引表中的每個(gè)項(xiàng)稱為索引項(xiàng)。 索引條目的一般形式是關(guān)鍵字、地址。 關(guān)鍵字是能夠唯一識(shí)別數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。哈希存儲(chǔ)使用預(yù)先設(shè)置的函數(shù)，根據(jù)數(shù)據(jù)元素的關(guān)鍵字來(lái)校正數(shù)據(jù)元素的存儲(chǔ)地址，并將其存儲(chǔ)在該地址中。 該函數(shù)稱為散列函數(shù)，并且根據(jù)散列函數(shù)校正的地址稱為散列地址。 Loc (元素i)=Lo (i-1)*m、順序存儲(chǔ)、1536、元素2、1400、元素1、1346地域名的第一個(gè)拼音字符的編號(hào)為散列函數(shù)： h (Beijing )=2h (Shanghai )=19 h (Shenyang )=19、 每個(gè)邏輯結(jié)構(gòu)都有一組基本的運(yùn)算。 例如，最常見(jiàn)的基本運(yùn)算是搜索、插入、刪除

10、、更新、排序等。 因?yàn)檫@些運(yùn)算是邏輯結(jié)構(gòu)上的操作，所以它們和邏輯結(jié)構(gòu)一樣是抽象的，只規(guī)定“做什么”，不需要考慮“怎么做”。 只有在存儲(chǔ)結(jié)構(gòu)已經(jīng)確定的情況下，才能考慮“如何”。 簡(jiǎn)單地說(shuō)，運(yùn)算是在邏輯結(jié)構(gòu)上定義的，其在存儲(chǔ)器結(jié)構(gòu)上實(shí)現(xiàn)。 另外，數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面。1.1.3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容、1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型、數(shù)據(jù)類型是與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的概念，在高級(jí)語(yǔ)言中是指一個(gè)值的集合和在該值的集合中定義的一系列操作的總稱。 用“值”能否分解，數(shù)據(jù)類型為(1)原子型：其值不能分解。 (2)結(jié)構(gòu)類型：其值可分解為若干成分(或稱成分)。 結(jié)構(gòu)型成分可以是原子型，也可以是某種

11、結(jié)構(gòu)型。 數(shù)據(jù)類型可以看作是編程語(yǔ)言實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 例如，c語(yǔ)言提供了原子類型，如int、char、float、double等，結(jié)構(gòu)類型，如數(shù)組、結(jié)構(gòu)、共享體、枚舉等，以及指針、空(void )類型等。 用戶可以選擇類型基礎(chǔ)結(jié)構(gòu)編號(hào)； 卡爾名稱20； 浮動(dòng)球； 史蒂文； 星際旅行1、星際旅行2、*p； 中的組合圖層性質(zhì)變更選項(xiàng)。 抽象數(shù)據(jù)類型(ADT )是指數(shù)學(xué)模型和為該模型定義的一系列操作。 抽象數(shù)據(jù)類型的定義取決于一組邏輯特性，無(wú)論它們是如何在計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)的。 也就是說(shuō)，無(wú)論其內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變化，就不會(huì)影響其外部的使用。 抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是概念。

12、例如，整數(shù)類型是ADT，數(shù)據(jù)對(duì)象是可以存儲(chǔ)的整數(shù)，基本操作包括加、減、乘、除、模等。 不同處理器的實(shí)現(xiàn)方式可能不同，但由于定義的數(shù)學(xué)特性相同，因此在用戶看來(lái)是相同的。 因此，“抽象”的意思在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。 1.3算法和算法分析、1.3.1算法的概念算法是特定問(wèn)題解決步驟的描述，指令的有限序列，每個(gè)指令代表一個(gè)或多個(gè)操作。 對(duì)于實(shí)際問(wèn)題，不僅要選擇合適的數(shù)據(jù)結(jié)構(gòu)，還需要更好的算法來(lái)解決問(wèn)題。 修正機(jī)的對(duì)數(shù)數(shù)據(jù)的操作可分為數(shù)值性和非數(shù)值性2種。 數(shù)值操作主要進(jìn)行算術(shù)運(yùn)算，非數(shù)值操作主要進(jìn)行檢索、排序、插入、刪除等。 設(shè)置修正算法的基本過(guò)程l通過(guò)詳細(xì)分析問(wèn)題，確定將相應(yīng)的數(shù)學(xué)模型抽象化的

13、l使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)置對(duì)該數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法，選擇將l算法轉(zhuǎn)換為程序的語(yǔ)言l調(diào)試這些程序中的組合圖層性質(zhì)變更選項(xiàng)。 算法有五個(gè)特性(1) : 一個(gè)算法必須在對(duì)合法輸入執(zhí)行了貧窮的步驟之后結(jié)束，每個(gè)步驟必須能夠在有限的時(shí)間內(nèi)完成。 (2)確定性：算法的每個(gè)步驟必須具有正確的意義，沒(méi)有二義性，任何條件下都只有唯一的執(zhí)行路徑。(3)可行性：算法中記述的各步驟的操作，可以通過(guò)現(xiàn)有的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。 (4)輸入：算法需要0個(gè)以上的輸入。 (5)輸出：一個(gè)算法需要一個(gè)以上的輸出。 這里的輸出指的是與輸入具有某種特定關(guān)系的量。 中的組合圖層性質(zhì)變更選項(xiàng)。 例如：按從小到大的順序

14、對(duì)x、y、z三個(gè)數(shù)值的內(nèi)容進(jìn)行排序。 算法： (1)輸入x、y、z三個(gè)數(shù)值；(2)從三個(gè)數(shù)值中選擇最小的數(shù)值替換為x；(3)從y、z中選擇較小的數(shù)值替換為y；(4)輸出排序結(jié)果。 1.3.2算法的描述選擇算法描述語(yǔ)言的指南(1)此語(yǔ)言應(yīng)當(dāng)具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能(2)應(yīng)當(dāng)盡可能容易地掌握和理解此語(yǔ)言(3)以此語(yǔ)言描述的算法應(yīng)用于哪種專業(yè)技術(shù)可以采用自然語(yǔ)言、程序流程圖、N-S圖、某種編程語(yǔ)言、偽代碼。 “c類”描述語(yǔ)言是精心過(guò)濾和保持c語(yǔ)言的核心子集，已經(jīng)進(jìn)行了一些擴(kuò)展修改以便于描述，并且已經(jīng)增強(qiáng)了語(yǔ)言描述功能。 1 .預(yù)定義常數(shù)和類型# define true1# define fa

15、lse0# defineo k1# define error0# define overflow-1數(shù)據(jù)元素約定為EntryType類型，用戶可以根據(jù)需要，使用為了簡(jiǎn)化語(yǔ)句序列函數(shù)的寫(xiě)入，提高算法描述的清晰度，函數(shù)殘奧參數(shù)表中的殘奧儀表除了需要說(shuō)明數(shù)據(jù)類型以外，函數(shù)中使用的局部變量也可以不說(shuō)明變量，可以根據(jù)需要給予相應(yīng)的注釋。 另外，在寫(xiě)算法的時(shí)候，應(yīng)該養(yǎng)成對(duì)重點(diǎn)句子的段落加注釋的好習(xí)慣。 3 .算法描述中可以使用的代入語(yǔ)句的形式是：簡(jiǎn)單代入變量名=式。串行代入變量名1=變量名2=.=變量名n=式組分配(變量名1，變量名n)=(式1，式n )； 結(jié)構(gòu)代入結(jié)構(gòu)名1=結(jié)構(gòu)名2結(jié)構(gòu)名=(值1、值2、值n )； 條件代入變量名稱=條件式？ 表達(dá)式1 :表達(dá)式2； 替代變量名稱1替換變量名稱24.算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句的格式是：條件語(yǔ)句1 if (表達(dá)式)語(yǔ)句條件語(yǔ)句2 if (表達(dá)式)語(yǔ)句else語(yǔ)句：開(kāi)關(guān)語(yǔ)句1 switch (表達(dá)式) case值1 :語(yǔ)句序列1； 中斷； case值2 :文件系列2 break； case值n :語(yǔ)句序列n； 中斷； 默認(rèn)：語(yǔ)句序列n 1； 5 .可以在算法描述中使用的循環(huán)結(jié)構(gòu)語(yǔ)句的格式是for循環(huán)語(yǔ)句for (表達(dá)式1循環(huán)表達(dá)式2 )語(yǔ)句whi