數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)-展示頁
2025-04-26 01:46本頁面
【正文】 歷初始化：p=(struct student *)malloc(sizeof(struct student))。1. 順序表結(jié)構(gòu)線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。第二章 線性表定義：線性表是n個數(shù)據(jù)元素的有限序列。常見的數(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)。二元組就是一種用來表示某個數(shù)據(jù)對象以及各個元素之間關(guān)系的有限集合?？尚行裕核惴ㄖ械拿恳粋€步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。（程序與算法的區(qū)別在于，程序不需要有有窮性）確定性：算法中的每一個步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。邏輯結(jié)構(gòu)可以映射為以下兩種存儲結(jié)構(gòu)：：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元中，借助元素在存儲器中的相對位置來表示數(shù)據(jù)之間的邏輯關(guān)系。（2）數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。：結(jié)構(gòu)中的數(shù)據(jù)元素存在“多對多”的關(guān)系。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對多“的關(guān)系。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對一“的關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。）4．?dāng)?shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。）3．?dāng)?shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 （補(bǔ)充：一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。WORD文檔 可編輯第一章 數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1．?dāng)?shù)據(jù)：數(shù)據(jù)是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號的總稱。：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中的個體，也稱之為元素，結(jié)點(diǎn)，頂點(diǎn)記錄。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。（有時候也叫做屬性。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。 依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個集合“的關(guān)系以外，沒有其他關(guān)系。若結(jié)構(gòu)為非空集合，則除了第一個元素之外，和最后一個元素之外，其他每個元素都只有一個直接前驅(qū)和一個直接后繼。若數(shù)據(jù)為非空集，則除了第一個元素（根）之外，其它 每個數(shù)據(jù)元素都只有一個直接前驅(qū)，以及多個或零個 直接后繼。若結(jié)構(gòu)為非空集，折每個數(shù)據(jù)可有多個（或零個）直接后繼。想要計(jì)算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲結(jié)構(gòu)。：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。 ：：算法的時間復(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é)束。沒有歧義。（2）.算法設(shè)計(jì)的要求： 正確性（達(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ù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)四種類型。通常認(rèn)為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是差算法。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。 2. 單鏈表（1） 鏈表結(jié)點(diǎn)結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以用任意的一組存儲單元來存儲，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。插入： pnext=headnext。輸出：printf(“%d”,pdata)。 pnext = qnext 。結(jié)點(diǎn)遍歷： for(p=head。p=pnext)。在一個單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語句為 Pnext = qnext 。在長度為N的順序表中，插入一個新元素平均需要移動表中N/2個元素，刪除一個元素平均需要移動（N1）/2個元素。已知順序表中每個元素占用3個存儲單元，第13個元素的存儲地址為336，則順序表的首地址為300。（函數(shù)名自定義）結(jié)點(diǎn)定義：typedef int datatype。 struct node *next。 //結(jié)點(diǎn)類型,結(jié)點(diǎn)指針類型typedef pointer lklist。 head=new node。 這是C語言做法 headnext=NULL。//雙向鏈表應(yīng)加上headprevios=NULL。} ：（C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）int insert(lklist head,datatype x,int i){
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1