數(shù)據(jù)結(jié)構(gòu)[Python語言描述]作業(yè)布置單擊此處獲取APP掃碼作業(yè)布置方法作業(yè)布置宣傳片，歡迎播放了解單擊此處獲取微信掃碼作業(yè)布置方法使用說明文檔本課作業(yè)布置二維碼老師掃描此碼，即可進(jìn)行線上作業(yè)布置第1章緒論第2章線性表第3章棧和隊列第4章串目錄第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序第1章緒論簽到掃碼下載文旌課堂APP掃碼簽到（202X.X.XXXX:00至202X.X.XXXX:10）簽到方式教師通過“文旌課堂APP”生成簽到二維碼，并設(shè)置簽到時間，學(xué)生通過“文旌課堂APP”掃描“簽到二維碼”進(jìn)行簽到。。緒

論本章導(dǎo)讀早期的計算機(jī)主要用于數(shù)值計算，到20世紀(jì)中葉后，逐漸擴(kuò)展到對非數(shù)值的計算，它所處理的對象越來越多，包括圖像、視頻、表格等具有一定結(jié)構(gòu)的數(shù)據(jù)。如何合理地組織這些數(shù)據(jù)，并對它們進(jìn)行高效的處理，就是“數(shù)據(jù)結(jié)構(gòu)”主要研究的內(nèi)容。本章首先介紹數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，然后介紹數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，接著介紹抽象數(shù)據(jù)類型的概念，最后介紹算法和算法分析的相關(guān)知識。

第1章緒

論知識目標(biāo)

第1章 熟悉數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。 理解數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型等概念。 了解算法的定義、特性、描述方法和設(shè)計要求。 了解算法性能評價的重要指標(biāo)。緒

論技能目標(biāo)

第1章 能針對實際問題設(shè)計出較高質(zhì)量的算法，并使用多種方法進(jìn)行描述。 能分析簡單算法的時間復(fù)雜度和空間復(fù)雜度。緒

論素質(zhì)目標(biāo)

第1章 學(xué)習(xí)楷模事跡，汲取開拓創(chuàng)新、無私奉獻(xiàn)的榜樣力量。 通過對算法的改進(jìn)，培養(yǎng)科學(xué)嚴(yán)謹(jǐn)、精益求精的工匠精神。Content第1章邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型算法和算法分析1.1基本概念和術(shù)語第1章數(shù)據(jù)分析入門1.1基本概念和術(shù)語1．?dāng)?shù)據(jù)數(shù)據(jù)（data）是客觀事物的符號表示，在計算機(jī)科學(xué)中，是指所有能被計算機(jī)程序識別、存儲、加工和處理的符號的總稱，它是計算機(jī)程序加工的“原料”。對計算機(jī)科學(xué)而言，數(shù)據(jù)的含義極為廣泛，如圖像、聲音等都可以通過編碼而歸之于數(shù)據(jù)的范疇。例如，一個利用數(shù)值分析方法求解代數(shù)方程的程序，其處理的整數(shù)和實數(shù)都是數(shù)據(jù)；一個編譯程序或文字處理程序，其處理的字符串也是數(shù)據(jù)。2．?dāng)?shù)據(jù)元素數(shù)據(jù)元素（dataelement）是數(shù)據(jù)的基本單位，在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)元素又稱為元素或記錄，如表1-1（詳見教材）所示的學(xué)生基本信息表中，每個學(xué)生的信息就是一個數(shù)據(jù)元素。為便于理解數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語的含義，下面以表1-1中的數(shù)據(jù)為例，進(jìn)一步描述數(shù)據(jù)元素、數(shù)據(jù)項及數(shù)據(jù)對象之間的關(guān)系，如下圖所示。高手點撥1.1基本概念和術(shù)語1.1基本概念和術(shù)語3．?dāng)?shù)據(jù)項數(shù)據(jù)項（dataitem）是組成數(shù)據(jù)元素的、有獨立含義的、不可再分的最小單位，如學(xué)生基本信息表中的學(xué)號、姓名等。4．?dāng)?shù)據(jù)對象數(shù)據(jù)對象（dataobject）是性質(zhì)相同的有限個數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，集合N={2,4,6,8,10}是整數(shù)的一個數(shù)據(jù)對象，集合C={'a','b','c','d','e'}是小寫字母的一個數(shù)據(jù)對象。5．?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（datastructure）是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。結(jié)構(gòu)就是指數(shù)據(jù)元素之間的相互關(guān)系，因此，可以將數(shù)據(jù)結(jié)構(gòu)看作帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，如下圖所示。1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)第1章數(shù)據(jù)分析入門1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系的描述，它與數(shù)據(jù)的存儲無關(guān)，獨立于計算機(jī)，是從具體問題抽象出來的數(shù)學(xué)模型。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，可分為4種不同的邏輯結(jié)構(gòu)，如下圖所示。1.2.1邏輯結(jié)構(gòu)1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)（1）集合結(jié)構(gòu)的數(shù)據(jù)元素之間只有屬于同一個集合的關(guān)系。例如，判斷一個數(shù)字是否為整數(shù)，可以將所有整數(shù)看作一個集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)的數(shù)據(jù)元素之間是一對一的關(guān)系。此時每個數(shù)據(jù)元素都有唯一的前驅(qū)元素（第一個元素除外）和唯一的后繼元素（最后一個元素除外）。例如，由多節(jié)車廂組成的列車、排隊買票人員、一疊盤子等都可以看作線性結(jié)構(gòu)。（3）樹形結(jié)構(gòu)的數(shù)據(jù)元素之間是一對多的關(guān)系。例如，學(xué)校的組織結(jié)構(gòu)、家族關(guān)系等都可以看作樹形結(jié)構(gòu)。（4）圖形結(jié)構(gòu)（也稱網(wǎng)狀結(jié)構(gòu)）的數(shù)據(jù)元素之間是多對多的關(guān)系。此時每個數(shù)據(jù)元素都可以有多個前驅(qū)元素或后繼元素。例如，城市公共交通網(wǎng)、計算機(jī)網(wǎng)絡(luò)等都可以看作圖形結(jié)構(gòu)。1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)（也稱物理結(jié)構(gòu)）是指數(shù)據(jù)元素在計算機(jī)中的存儲表示，是邏輯結(jié)構(gòu)在計算機(jī)中的實現(xiàn)。將數(shù)據(jù)元素存儲到計算機(jī)時，通常既要存儲各數(shù)據(jù)元素的數(shù)據(jù)項，又要存儲數(shù)據(jù)元素之間的邏輯關(guān)系。根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系在計算機(jī)中的不同表示，可分為兩種不同的存儲結(jié)構(gòu)，分別是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.2.2存儲結(jié)構(gòu)1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)1．順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是指邏輯上相鄰的數(shù)據(jù)元素，其物理位置（內(nèi)存中的位置）也相鄰，數(shù)據(jù)元素間的邏輯關(guān)系由存儲單元的鄰接關(guān)系體現(xiàn)。順序存儲結(jié)構(gòu)是一種最基本的存儲方法，通常借助程序設(shè)計語言中的數(shù)組來實現(xiàn)。假設(shè)表1-1中每個學(xué)生的基本信息在內(nèi)存中占用10個字節(jié)的存儲單元，當(dāng)數(shù)據(jù)元素從1000號存儲單元開始由低地址向高地址方向依次存儲時，對應(yīng)的順序存儲結(jié)構(gòu)如下圖所示。1.2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)2．鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)是指在計算機(jī)中用一組任意的存儲單元存儲數(shù)據(jù)元素，然后再通過地址鏈接的形式將全部數(shù)據(jù)元素組織到一起。這組任意的存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助程序設(shè)計語言中的指針來實現(xiàn)，表1-1中學(xué)生基本信息的鏈?zhǔn)酱鎯Y(jié)構(gòu)如下圖所示。由此可以看出，在這種存儲結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素，其物理位置不一定相鄰。1.3抽象數(shù)據(jù)類型第1章數(shù)據(jù)分析入門數(shù)據(jù)類型（datatype）是一組性質(zhì)相同的值的集合和定義在該集合上的一組操作的總稱，它最早出現(xiàn)在高級程序設(shè)計語言中用于描述操作對象的特性（如取值范圍、允許執(zhí)行的操作等）。例如，Python中的列表數(shù)據(jù)類型（list）沒有長度限制，允許執(zhí)行的操作有添加元素、刪除元素、分片賦值和排序等。抽象數(shù)據(jù)類型（abstractdatatype，ADT）是指一個數(shù)學(xué)模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)。即無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。1.3抽象數(shù)據(jù)類型1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上可看作一個概念。例如，各個計算機(jī)都擁有的“整數(shù)”類型就是抽象數(shù)據(jù)類型，盡管它們在不同處理器上實現(xiàn)的方法不同，但由于其定義的數(shù)學(xué)特性相同，在用戶看來它們都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型是近年來計算機(jī)科學(xué)中提出的最重要的概念之一，它集中體現(xiàn)了程序設(shè)計中一個最基本的原則，即通過封裝和信息隱蔽，使對象操作的具體實現(xiàn)方法和外部引用相分離。抽象數(shù)據(jù)類型含義更廣，不僅包括各種不同的計算機(jī)處理器中已定義并實現(xiàn)的數(shù)據(jù)類型（又稱固有數(shù)據(jù)類型），還包括設(shè)計軟件系統(tǒng)時用戶自己定義的復(fù)雜數(shù)據(jù)類型，且所定義的數(shù)據(jù)類型的抽象層次越高，含有該數(shù)據(jù)類型的軟件復(fù)用程度就越高。高手點撥1.3抽象數(shù)據(jù)類型1.3抽象數(shù)據(jù)類型下面用三元組（D，S，P）來描述抽象數(shù)據(jù)類型。其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的操作集，因此抽象數(shù)據(jù)類型的格式定義如下。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義> }ADT抽象數(shù)據(jù)類型名1.4算法和算法分析第1章數(shù)據(jù)分析入門1.4算法和算法分析在計算機(jī)領(lǐng)域中，算法是指根據(jù)所要處理的問題，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)基礎(chǔ)上，利用有限的步驟解決這一特定問題所采用的一組有窮規(guī)則的集合。一個算法應(yīng)該具有如下5個特性。1.4.1算法的定義和特性（1）有窮性。一個算法必須在有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)。（2）確定性。算法中的每一個步驟必須有確定含義，不能有二義性。（3）可行性。算法中的每一個步驟都可以通過已經(jīng)實現(xiàn)的基本操作運算執(zhí)行有限次來實現(xiàn)。（4）輸入。一個算法可以有0個或多個輸入。（5）輸出。一個算法至少有一個或多個輸出。1.4算法和算法分析高德納·克努特被譽為現(xiàn)代計算機(jī)科學(xué)的鼻祖，他所著的描述基本算法與數(shù)據(jù)結(jié)構(gòu)的經(jīng)典著作《計算機(jī)程序設(shè)計藝術(shù)》在計算機(jī)史上的地位，堪比數(shù)學(xué)史上歐幾里得所著的《幾何學(xué)原理》。1973年，當(dāng)這部書出版到第三卷時，已被認(rèn)為是石破天驚的“神作”，高德納·克努特也因此獲得了圖靈獎，而當(dāng)時他才36歲。在算法方面，高德納·克努特和他的學(xué)生共同設(shè)計了Knuth-Bendix算法和Knuth-Morris-Pratt算法，前者曾成功地解決了群論中的等式的證明問題；后者是在文本中查找字符串的簡單而高效的算法。如今，高德納·克努特已是白發(fā)蒼蒼的老人，這位曠世大師，用自己的才華定義了屬于自己的時代。1.4算法和算法分析算法可以使用多種方法進(jìn)行描述，如自然語言、流程圖、偽代碼和程序設(shè)計語言等，接下來分別對其進(jìn)行介紹。1.4.2算法的描述方法1．自然語言使用自然語言（如漢語、英語等）描述算法的優(yōu)點是簡單直觀且便于閱讀，缺點是不夠嚴(yán)謹(jǐn)，與計算機(jī)采用的程序設(shè)計語言相差很大，需要用z戶自行進(jìn)行轉(zhuǎn)換。2．流程圖流程圖通過規(guī)定的圖形符號（見表1-2）來描述算法。使用流程圖描述算法的優(yōu)點是直觀、簡潔、明了。3．偽代碼偽代碼通常用文字和符號來表示。使用偽代碼描述算法的優(yōu)點是忽略了程序設(shè)計語言的語法規(guī)則和描述細(xì)節(jié)，更易于用戶理解。4．程序設(shè)計語言程序設(shè)計語言是用于編寫計算機(jī)程序的語言。使用程序設(shè)計語言描述算法必須嚴(yán)格遵循所用語言的語法規(guī)則，編寫的程序可直接在計算機(jī)上執(zhí)行，但相對來說不易理解，有時須借助注釋語句來提高程序的可讀性。1.4算法和算法分析知識庫流程圖還包括一些特殊的圖形符號，如注解符、文件符、顯示符和人工輸入符。其中，注解符用于標(biāo)識注解內(nèi)容，它不是程序流程圖的必要部分，不反應(yīng)流程和操作，只是為了對流程圖中某些符號的操作進(jìn)行必要的補充說明，以幫助讀者更好地理解；文件符表示可閱讀的數(shù)據(jù)，如打印輸出、表格輸入的數(shù)據(jù)等；顯示符表示任意媒體顯示的數(shù)據(jù)；人工輸入符表示任意媒體以人工形式輸入的數(shù)據(jù)，如通過鍵盤、開關(guān)裝置、按鈕、條形碼輸入器等輸入的數(shù)據(jù)。1.4算法和算法分析1.4.3算法的設(shè)計要求（1）正確性。其中，“正確”的含義可以分為如下3個層次。①對于幾組輸入數(shù)據(jù)，能夠得到滿足要求的結(jié)果。②對于精心選擇的典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)，能夠得到滿足要求的結(jié)果。③對于一切合法的輸入數(shù)據(jù)，都能得到滿足要求的結(jié)果。（2）可讀性。算法主要是為了人們的閱讀與交流，其次才是機(jī)器執(zhí)行。因此，算法的表達(dá)應(yīng)思路清晰，層次分明，易于理解，可讀性強(qiáng)，以便于后續(xù)對算法的使用和修改。（3）健壯性。當(dāng)輸入數(shù)據(jù)非法時，算法也能做出正確反應(yīng)或進(jìn)行相應(yīng)的處理，而不會產(chǎn)生一些莫名其妙的輸出結(jié)果。（4）高效率與低存儲量。通俗地說，效率指的是算法的執(zhí)行時間。對于同一個問題，若有多個算法可以解決，則執(zhí)行時間越短的算法效率越高。存儲量指的是算法執(zhí)行過程中所需要的最大存儲空間。1.4算法和算法分析要解決一個實際問題，通常可以有若干種算法，那么如何從這些算法中找出最有效的算法呢？或者對于一個解決實際問題的算法，如何來評價該算法的優(yōu)劣呢？這就需要進(jìn)行算法分析。算法分析是每個程序設(shè)計人員都應(yīng)該掌握的技術(shù)。評價一個算法的優(yōu)劣主要看執(zhí)行這個算法所需的時間（時間復(fù)雜度）和存儲空間（空間復(fù)雜度）。1.4.4算法分析1.4算法和算法分析1．算法的時間復(fù)雜度算法的時間復(fù)雜度（timecomplexity）是指算法的執(zhí)行時間隨問題規(guī)模的變化而變化的趨勢，反映算法執(zhí)行時間的長短，記作T(n)=O(f(n))。其中，n表示問題規(guī)模，是算法求解問題輸入量的多少，也是問題大小的本質(zhì)表示；T(n)表示語句的總執(zhí)行次數(shù)（稱為語句頻度或時間頻度）；f(n)是T(n)的同數(shù)量級函數(shù)，一般為問題規(guī)模n的某個函數(shù)。分析算法時間復(fù)雜度的步驟如下。（1）找出算法中語句頻度最大的語句。（2）計算頻度最大語句的頻度與問題規(guī)模n的某個函數(shù)f(n)。（3）取f(n)數(shù)量級并用符號O表示。1.4算法和算法分析2．算法的空間復(fù)雜度一個程序在計算機(jī)上運行時，除了需要存儲本身所用的指令、常數(shù)和輸入數(shù)據(jù)以外，還需要一些對數(shù)據(jù)進(jìn)行操作的輔助存儲空間。因此，一個算法的空間復(fù)雜度（spacecomplexity）就是指程序運行所需的存儲空間，記作S(n)=O(f(n))，該函數(shù)各參數(shù)的含義與時間復(fù)雜度相同，此處不再贅述。由于程序本身所用指令等所占存儲空間與算法無關(guān)，因此，分析算法的空間復(fù)雜度時，只需分析算法在實現(xiàn)時所需要的輔助存儲空間即可。同步訓(xùn)練將百分制成績轉(zhuǎn)換為五級制成績【問題描述】通過鍵盤輸入百分制成績，設(shè)計算法將其轉(zhuǎn)換為五級制成績并輸出。具體的百分制成績占比及與五級制成績的轉(zhuǎn)換規(guī)則如表1-4（詳見教材）所示。【問題分析】對于輸入的百分制成績，只需利用條件語句依次進(jìn)行判斷，然后根據(jù)表1-4進(jìn)行轉(zhuǎn)換即可。第一種算法可以根據(jù)分?jǐn)?shù)從低到高依次進(jìn)行判斷，其流程圖如下圖所示。使用算法一時，70分以上的成績（總占比80%）須進(jìn)行3次或3次以上的判斷才能得出結(jié)果。那么，怎樣才能減少判斷次數(shù)，從而提高效率呢？同步訓(xùn)練將百分制成績轉(zhuǎn)換為五級制成績同步訓(xùn)練將百分制成績轉(zhuǎn)換為五級制成績?yōu)榇?，可以將百分制成績范圍按照占比大小排序，并將具有較大占比的成績范圍排在前面，分別將輸入的成績與之進(jìn)行比較。這樣，大部分的成績經(jīng)過較少的比較次數(shù)就能得出其對應(yīng)的等級，從而提高了效率。因此，可以將算法一進(jìn)行改進(jìn)得到算法二，其流程圖如下圖所示。同步訓(xùn)練將百分制成績轉(zhuǎn)換為五級制成績【代碼實現(xiàn)】根據(jù)算法二，寫出Python源程序。var=6foriinrange(var):score