數(shù)據(jù)結(jié)構(gòu)專升本01引論

數(shù)據(jù)結(jié)構(gòu)專升本01引論CATALOGUE目錄課程介紹與目標(biāo)數(shù)據(jù)結(jié)構(gòu)基本概念線性表及其操作棧和隊(duì)列及其應(yīng)用串、數(shù)組和廣義表樹(shù)和二叉樹(shù)及其應(yīng)用01課程介紹與目標(biāo)培養(yǎng)算法設(shè)計(jì)能力通過(guò)學(xué)習(xí)和實(shí)踐，培養(yǎng)學(xué)生設(shè)計(jì)、分析和應(yīng)用算法的能力，提高學(xué)生的計(jì)算機(jī)編程能力和解決實(shí)際問(wèn)題的能力。掌握基本數(shù)據(jù)結(jié)構(gòu)通過(guò)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本概念、原理和算法，使學(xué)生掌握線性表、棧、隊(duì)列、串、數(shù)組、樹(shù)、圖等基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方式及基本運(yùn)算。提高程序效率了解不同數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)，能夠在實(shí)際問(wèn)題中選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高程序的執(zhí)行效率。數(shù)據(jù)結(jié)構(gòu)課程的目的承上啟下的作用01數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程之一，它既是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，也是后續(xù)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)等課程的重要先修課程。理論與實(shí)踐相結(jié)合02數(shù)據(jù)結(jié)構(gòu)課程既有理論深度，又有實(shí)踐應(yīng)用廣度。通過(guò)本課程的學(xué)習(xí)，可以培養(yǎng)學(xué)生抽象思維和創(chuàng)造性思維能力，提高分析問(wèn)題和解決問(wèn)題的能力。適應(yīng)社會(huì)發(fā)展需求03隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，數(shù)據(jù)結(jié)構(gòu)的應(yīng)用領(lǐng)域不斷擴(kuò)大。掌握數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和技能，對(duì)于適應(yīng)社會(huì)發(fā)展需求、提高個(gè)人競(jìng)爭(zhēng)力具有重要意義。專升本數(shù)據(jù)結(jié)構(gòu)的重要性課程目標(biāo)與要求培養(yǎng)學(xué)生的創(chuàng)新精神和實(shí)踐能力；提高學(xué)生的團(tuán)隊(duì)協(xié)作和溝通能力；培養(yǎng)學(xué)生的自主學(xué)習(xí)和終身學(xué)習(xí)能力。素質(zhì)目標(biāo)掌握基本數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法；理解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；了解數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用。知識(shí)目標(biāo)能夠運(yùn)用所學(xué)知識(shí)分析和解決實(shí)際應(yīng)用問(wèn)題；具備一定的算法設(shè)計(jì)和分析能力；能夠熟練使用至少一種編程語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的基本操作和相關(guān)算法。能力目標(biāo)02數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合。數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值類型，還包括字符及聲音、圖像、視頻等非數(shù)值類型。數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理。也被稱為記錄。數(shù)據(jù)項(xiàng)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)的定義是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對(duì)象數(shù)據(jù)類型是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。數(shù)據(jù)類型是按照值的不同進(jìn)行劃分的。在高級(jí)語(yǔ)言中，每個(gè)表達(dá)式都有確定的數(shù)據(jù)類型，類型明顯或隱含地規(guī)定了表達(dá)式其它方面的性質(zhì)。抽象數(shù)據(jù)類型（ADT）抽象數(shù)據(jù)類型（AbstractDataType）是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。數(shù)據(jù)類型與抽象數(shù)據(jù)類型算法設(shè)計(jì)的要求正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。算法效率的度量事后統(tǒng)計(jì)方法和事前分析估算方法。事后統(tǒng)計(jì)方法需要解決測(cè)試數(shù)據(jù)的獲取和測(cè)試環(huán)境的依賴性問(wèn)題，因此比較片面；事前分析估算方法是通過(guò)分析某個(gè)算法的語(yǔ)義進(jìn)而估算出它的執(zhí)行時(shí)間。算法與算法分析算法與算法分析給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N，f(n)總是比g(n)大，那么，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)。函數(shù)的漸近增長(zhǎng)在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n)=O(f(n))。它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)。算法時(shí)間復(fù)雜度03線性表及其操作線性表的定義線性表是具有n個(gè)數(shù)據(jù)元素的有限序列。線性表的抽象數(shù)據(jù)類型定義了一個(gè)線性表的抽象數(shù)據(jù)類型，包括數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作。線性表的基本操作包括初始化、插入、刪除、查找、遍歷等。線性表的定義與基本操作順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)可以隨機(jī)存取，即可以直接通過(guò)下標(biāo)訪問(wèn)任意元素。順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)插入和刪除操作需要移動(dòng)大量元素，效率低下。順序存儲(chǔ)結(jié)構(gòu)的定義用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)插入和刪除操作不需要移動(dòng)大量元素，效率較高。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)不能隨機(jī)存取，只能通過(guò)從頭結(jié)點(diǎn)開(kāi)始的鏈?zhǔn)皆L問(wèn)方式訪問(wèn)元素。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)04棧和隊(duì)列及其應(yīng)用棧（Stack）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其元素的插入和刪除操作只能在同一端進(jìn)行，這一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧中沒(méi)有元素時(shí)，稱為空棧。棧的定義棧的基本操作包括入棧（Push）、出棧（Pop）、取棧頂元素（Top）和判斷棧是否為空（IsEmpty）。入棧操作將元素添加到棧頂，出棧操作將棧頂元素刪除并返回，取棧頂元素操作返回棧頂元素但不刪除，判斷棧是否為空操作返回一個(gè)布爾值表示棧是否為空。棧的基本操作棧的定義與基本操作隊(duì)列的定義隊(duì)列（Queue）也是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其元素的插入操作在一端進(jìn)行，稱為隊(duì)尾（Rear），刪除操作在另一端進(jìn)行，稱為隊(duì)頭（Front）。隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列。隊(duì)列的基本操作隊(duì)列的基本操作包括入隊(duì)（Enqueue）、出隊(duì)（Dequeue）、取隊(duì)頭元素（Front）和判斷隊(duì)列是否為空（IsEmpty）。入隊(duì)操作將元素添加到隊(duì)尾，出隊(duì)操作將隊(duì)頭元素刪除并返回，取隊(duì)頭元素操作返回隊(duì)頭元素但不刪除，判斷隊(duì)列是否為空操作返回一個(gè)布爾值表示隊(duì)列是否為空。隊(duì)列的定義與基本操作在編譯器設(shè)計(jì)中，表達(dá)式求值是棧的一個(gè)典型應(yīng)用。編譯器在解析表達(dá)式時(shí)，可以使用兩個(gè)棧，一個(gè)用于保存操作數(shù)，另一個(gè)用于保存運(yùn)算符。通過(guò)不斷從輸入中讀取字符并根據(jù)優(yōu)先級(jí)規(guī)則進(jìn)行相應(yīng)的入棧和出棧操作，最終可以計(jì)算出表達(dá)式的值。在編程中經(jīng)常需要檢查代碼中的括號(hào)是否匹配正確。這可以通過(guò)使用一個(gè)棧來(lái)實(shí)現(xiàn)。當(dāng)遇到一個(gè)左括號(hào)時(shí)將其壓入棧中，當(dāng)遇到一個(gè)右括號(hào)時(shí)從棧中彈出一個(gè)元素并檢查它們是否匹配。如果最終棧為空，則括號(hào)匹配正確；否則括號(hào)匹配錯(cuò)誤。在計(jì)算機(jī)操作系統(tǒng)中，CPU任務(wù)調(diào)度是一個(gè)重要的問(wèn)題。隊(duì)列在這里可以發(fā)揮重要作用。操作系統(tǒng)可以將待執(zhí)行的任務(wù)按照優(yōu)先級(jí)放入不同的隊(duì)列中，然后按照優(yōu)先級(jí)從高到低的順序依次執(zhí)行隊(duì)列中的任務(wù)。這樣可以保證高優(yōu)先級(jí)的任務(wù)能夠優(yōu)先得到執(zhí)行。表達(dá)式求值括號(hào)匹配CPU任務(wù)調(diào)度棧和隊(duì)列的應(yīng)用舉例05串、數(shù)組和廣義表串的定義串（string）是由零個(gè)或多個(gè)字符組成的有限序列。一般記為s='a1a2...an'(n>=0)，其中s是串的名稱，用單引號(hào)括起來(lái)的字符序列是串的值，ai(1<=i<=n)可以是字母、數(shù)字或其他字符，i是串中字符的位置。要點(diǎn)一要點(diǎn)二串的基本操作串的基本操作包括串的賦值、串的復(fù)制、串的連接、串的比較、求串長(zhǎng)、子串的查找、插入子串和刪除子串等。串的定義及基本操作數(shù)組的定義及基本操作數(shù)組的定義數(shù)組（Array）是有序元素的集合，數(shù)組中的每個(gè)元素都可以通過(guò)下標(biāo)進(jìn)行訪問(wèn)。數(shù)組通常用于存儲(chǔ)同一類型的數(shù)據(jù)，如整數(shù)、浮點(diǎn)數(shù)或字符等。數(shù)組的基本操作數(shù)組的基本操作包括數(shù)組的創(chuàng)建、數(shù)組的初始化、數(shù)組的賦值、數(shù)組的訪問(wèn)、數(shù)組的遍歷、數(shù)組的排序和數(shù)組的查找等。廣義表（GeneralizedList）是線性表的擴(kuò)展，它允許列表的元素可以是原子（即基本數(shù)據(jù)元素），也可以是另一個(gè)廣義表。廣義表通常用于表示具有層次結(jié)構(gòu)的數(shù)據(jù)。廣義表的定義廣義表的基本操作包括廣義表的創(chuàng)建、廣義表的深度計(jì)算、廣義表的長(zhǎng)度計(jì)算、廣義表的遍歷、廣義表的查找和廣義表的修改等。廣義表的基本操作廣義表的定義及基本操作06樹(shù)和二叉樹(shù)及其應(yīng)用樹(shù)的基本概念與性質(zhì)樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)和邊組成，具有層次結(jié)構(gòu)。基本術(shù)語(yǔ)根節(jié)點(diǎn)、子節(jié)點(diǎn)、父節(jié)點(diǎn)、葉子節(jié)點(diǎn)、度、深度、層次等。樹(shù)的性質(zhì)樹(shù)中節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)度數(shù)加1；葉子節(jié)點(diǎn)數(shù)等于總節(jié)點(diǎn)數(shù)減去非葉子節(jié)點(diǎn)數(shù)；樹(shù)的高度等于最大層次減1。樹(shù)的定義二叉樹(shù)是一種特殊的樹(shù)，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹(shù)的定義二叉樹(shù)的性質(zhì)二叉樹(shù)的基本操作二叉樹(shù)中第i層最多有2^(i-1)個(gè)節(jié)點(diǎn)；深度為k的二叉樹(shù)最多有2^k-1個(gè)節(jié)點(diǎn)；對(duì)于任何一棵二叉樹(shù)，葉子節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1。創(chuàng)建二叉樹(shù)、遍歷二叉樹(shù)（前序遍歷、中序遍歷、后序遍歷）、查找節(jié)點(diǎn)、插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)等。二叉樹(shù)的定義及基本操作VS孩子表示法、孩子兄弟表示法。森林的存儲(chǔ)結(jié)構(gòu)將森林中的每棵樹(shù)轉(zhuǎn)換為二叉樹(shù)進(jìn)行存儲(chǔ)，通過(guò)添加虛擬節(jié)點(diǎn)實(shí)現(xiàn)多棵樹(shù)的連接。樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)和森林的