tp-3432數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教程實(shí)驗(yàn)1do

1、1.11.1數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法的計(jì)算環(huán)境的計(jì)算環(huán)境(實(shí)驗(yàn)估計(jì)時(shí)間：90分鐘)1.1.1背景知識(shí)背景知識(shí)除了進(jìn)行科學(xué)計(jì)算之外，計(jì)算機(jī)已經(jīng)被廣泛地應(yīng)用在控制、管理和數(shù)據(jù)處理等非數(shù)值計(jì)算的領(lǐng)域中。與此相應(yīng)，處理對(duì)象也由早先純粹的數(shù)值發(fā)展到字符、表格和圖形圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這給計(jì)算機(jī)程序設(shè)計(jì)帶來了新的問題。為了編寫一個(gè)“好”的程序，必須明確處理對(duì)象的特征及各對(duì)象之間的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。任何實(shí)

2、際問題只有建立了數(shù)學(xué)模型才可以被計(jì)算機(jī)計(jì)算，而數(shù)據(jù)結(jié)構(gòu)就是實(shí)際問題中操作對(duì)象(元素)的數(shù)學(xué)抽象，算法則是建立和解決數(shù)學(xué)模型的方法。數(shù)據(jù)結(jié)構(gòu)用來反映計(jì)算機(jī)加工處理的對(duì)象，即數(shù)據(jù)的內(nèi)部構(gòu)成，即數(shù)據(jù)由哪幾部分構(gòu)成，以什么方式構(gòu)成，呈什么樣的結(jié)構(gòu)等。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。這里的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是指一個(gè)事物的兩個(gè)方面，而不是指兩個(gè)不同的對(duì)象。邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，而物理結(jié)構(gòu)反映了數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排，也稱為存儲(chǔ)

3、結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式，也是信息的一種組織方式，其目的是為了提高算法的效率。數(shù)據(jù)結(jié)構(gòu)通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。由于相同算法中的抽象數(shù)據(jù)類型用不同的數(shù)據(jù)結(jié)構(gòu)來表示，會(huì)造成不同的執(zhí)行效率，這就有必要來研究不同數(shù)據(jù)結(jié)構(gòu)表示的效率差異及實(shí)驗(yàn)1數(shù)據(jù)結(jié)構(gòu)和算法分析基礎(chǔ)實(shí)驗(yàn)1數(shù)據(jù)結(jié)構(gòu)和算法分析基礎(chǔ)3U=succ(U)。P有4種基本映射模型：順序(sequential)、鏈接(linked)

4、、索引(indexed)和散列(hashing)映射。因此，我們至少可以得到44種可能的物理結(jié)構(gòu)(并不是所有的可能組合都合理)：sequential(sets)linkedlistsindexedtreeshashgraphs例如，學(xué)生排隊(duì)問題中，因?yàn)閿?shù)據(jù)元素之間是一種前后次序關(guān)系，即采用的邏輯數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，在計(jì)算機(jī)中可以開辟一個(gè)連續(xù)的存儲(chǔ)空間來存放數(shù)據(jù)元素，故可采用順序結(jié)構(gòu)作為其物理結(jié)構(gòu)。2)數(shù)據(jù)結(jié)構(gòu)DS上的操作。所有的定義在D

5、S上的操作在改變數(shù)據(jù)元素(結(jié)點(diǎn))或結(jié)點(diǎn)的域時(shí)必須保持DS的邏輯和物理結(jié)構(gòu)。3)DS上的基本操作。任何其他對(duì)DS的高級(jí)操作都可以用這些基本操作來實(shí)現(xiàn)。最好將DS和它的所有基本操作看作為一個(gè)整體——稱之為模塊。我們可以進(jìn)一步將該模塊抽象為數(shù)據(jù)類型(其中DS的存儲(chǔ)結(jié)構(gòu)被表示為私有成員，基本操作被表示為公共方法)。例如，學(xué)生排隊(duì)問題中的基本操作有出列(刪除操作)、入列(插入操作)和點(diǎn)名(檢索)等。3.3.算法算法算法(algithm)是在有限步

6、驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗地說，就是計(jì)算機(jī)解題的過程。在這個(gè)過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。一個(gè)算法應(yīng)該具有以下5個(gè)重要的特征。1)有窮性：一個(gè)算法必須保證執(zhí)行有限步驟之后結(jié)束。2)確切性：算法的每一步驟必須有確切的定義。3)可行性：算法中的每一步驟必須充分可及，即算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。4)輸入：一個(gè)