數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)(已修改)
2025-04-29 01:46 本頁面
【正文】 WORD文檔 可編輯第一章 數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1．?dāng)?shù)據(jù)：數(shù)據(jù)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序所處理的符號的總稱。：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中的個體，也稱之為元素，結(jié)點(diǎn)，頂點(diǎn)記錄。 （補(bǔ)充：一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。）3．?dāng)?shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。（有時候也叫做屬性。）4．?dāng)?shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計算機(jī)的。 依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個集合“的關(guān)系以外，沒有其他關(guān)系。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對一“的關(guān)系。若結(jié)構(gòu)為非空集合，則除了第一個元素之外，和最后一個元素之外，其他每個元素都只有一個直接前驅(qū)和一個直接后繼。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對多“的關(guān)系。若數(shù)據(jù)為非空集，則除了第一個元素（根）之外，其它 每個數(shù)據(jù)元素都只有一個直接前驅(qū)，以及多個或零個 直接后繼。：結(jié)構(gòu)中的數(shù)據(jù)元素存在“多對多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個數(shù)據(jù)可有多個（或零個）直接后繼。（2）數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。想要計算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)可以映射為以下兩種存儲結(jié)構(gòu)：：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元中，借助元素在存儲器中的相對位置來表示數(shù)據(jù)之間的邏輯關(guān)系。：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。 ：：算法的時間復(fù)雜度與問題規(guī)模n無關(guān)系T(n)=O(1) ：算法的時間復(fù)雜度與問題規(guī)模n成線性關(guān)系T(n)=O(n) ：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++時間復(fù)雜度的大小比較：O(1) O(log 2 n) O(n ) O(n log 2 n) O(n2) O(n3) O(2 n )O(n!)O(n n)：（1）算法的5個特性 輸入：有零個或多個輸入 輸出：有一個或多個輸出有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序列的執(zhí)行在有限的時間內(nèi)結(jié)束。（程序與算法的區(qū)別在于，程序不需要有有窮性）確定性：算法中的每一個步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。沒有歧義?？尚行裕核惴ㄖ械拿恳粋€步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。（2）.算法設(shè)計的要求： 正確性（達(dá)到預(yù)期效果，滿足問題需求） 健壯性（能處理合法數(shù)據(jù)，也能對不合法的數(shù)據(jù)作出反應(yīng)，不會產(chǎn)生不可預(yù)期的后果） 可讀性（要求算法易于理解，便于分析） 可修改可擴(kuò)展性 高效率（較好的時空性能 ）補(bǔ)充內(nèi)容：名詞解釋：數(shù)據(jù)結(jié)構(gòu)、二元組數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。二元組就是一種用來表示某個數(shù)據(jù)對象以及各個元素之間關(guān)系的有限集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)四種類型。常見的數(shù)據(jù)存儲結(jié)構(gòu)一般有兩種類型，它們分別是順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)，一個算法的時間復(fù)雜度是問題規(guī)模的函數(shù)：常數(shù)階O（1）、線性階O（n）、對數(shù)階O（log 2 n）、平方階O(n^2)、指數(shù)階O(2^n)。通常認(rèn)為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是差算法。第二章 線性表定義：線性表是n個數(shù)據(jù)元素的有限序列。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。1. 順序表結(jié)構(gòu)線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。 2. 單鏈表（1） 鏈表結(jié)點(diǎn)結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以用任意的一組存儲單元來存儲，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。（2） 鏈表操作算法：初始化、插入、輸出、刪除、遍歷初始化：p=(struct student *)malloc(sizeof(struct student))。插入： pnext=headnext。 headnext=p。輸出：printf(“%d”,pdata)。刪除：q=pnext。 pnext = qnext 。 free(q)。結(jié)點(diǎn)遍歷： for(p=head。p。p=pnext)。補(bǔ)充內(nèi)容：線性表中，第一個元素沒有直接前驅(qū)，最后一個元素沒有直接后驅(qū)。在一個單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語句為 Pnext = qnext 。 free(q)。在長度為N的順序表中，插入一個新元素平均需要移動表中N/2個元素，刪除一個元素平均需要移動（N1）/2個元素。若線性表的主要操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用順序表存儲結(jié)構(gòu)最節(jié)省運(yùn)算時間。已知順序表中每個元素占用3個存儲單元，第13個元素的存儲地址為336，則順序表的首地址為300。（第n個元素的地址即首地址+(n1)*每個元素的存儲空間，如a[12]（第13個元素）的地址=a[0]+12*3）
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1