第一篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)教學(xué)方法探討的教育論文

摘要：《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程，具有很強(qiáng)的實(shí)踐性。本文結(jié)合筆者在課程教學(xué)的一些體會(huì)，從實(shí)驗(yàn)教學(xué)設(shè)計(jì)、實(shí)驗(yàn)教學(xué)手段等方面對(duì)《數(shù)據(jù)結(jié)構(gòu)》實(shí)踐教學(xué)方法提出自己的一些看法和建議。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)

引言

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)課程體系的核心課程之一。課程主要講述各種數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)及基本操作的實(shí)現(xiàn)算法以及數(shù)據(jù)查找、排序算法，并對(duì)各種算法進(jìn)行性能分析和比較。

根據(jù)調(diào)查發(fā)現(xiàn)，目前大多數(shù)院?！稊?shù)據(jù)結(jié)構(gòu)》課程教學(xué)現(xiàn)狀不容樂觀。學(xué)生普遍反映課程學(xué)習(xí)比較困難，教師也感覺教學(xué)效果不理想。實(shí)驗(yàn)教學(xué)更是因?yàn)槌绦蛟O(shè)計(jì)語言基礎(chǔ)不扎實(shí)、課程內(nèi)容太抽象等原因而較難開展，有些學(xué)校因此而縮短學(xué)時(shí)甚至不開設(shè)實(shí)驗(yàn)。一些專家和教師就課程實(shí)驗(yàn)教學(xué)改革已經(jīng)提出了一些具體的教學(xué)方法，如案例驅(qū)動(dòng)、課題答辯等。這些方法都具有比較重要的借鑒價(jià)值，但某些文章過于片面的強(qiáng)調(diào)某一種教學(xué)方法。筆者認(rèn)為根據(jù)學(xué)生的實(shí)際情況完善教學(xué)設(shè)計(jì)、加強(qiáng)教學(xué)管理，通過行之有效的教學(xué)手段使學(xué)生學(xué)有所獲才是根本。下面結(jié)合自己的實(shí)際教學(xué)工作，談?wù)剬?duì)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)方法的認(rèn)識(shí)。我校《數(shù)據(jù)結(jié)構(gòu)》課程理論學(xué)時(shí)48，實(shí)踐學(xué)時(shí)16，教材選用嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》）。

1講好理論第一課，明確課程性質(zhì)

僅從課程名稱來看，《數(shù)據(jù)結(jié)構(gòu)》就很容易被誤解為實(shí)踐性不強(qiáng)的理論課。講好第一堂理論課非常重要，應(yīng)讓學(xué)生明確課程性質(zhì)并理解實(shí)踐學(xué)習(xí)的重要性。

結(jié)合程序設(shè)計(jì)語言、操作系統(tǒng)等課程內(nèi)容，筆者設(shè)計(jì)了一些學(xué)生比較熟悉并容易理解的應(yīng)用實(shí)例和學(xué)生一起探討，如：inta[10]和a[i]=5的確切含義；文件簇的鏈?zhǔn)叫螒B(tài)；國(guó)際象棋大師與超級(jí)計(jì)算機(jī)的對(duì)決；圖的著色問題等。在講解圖的著色問題時(shí)引導(dǎo)學(xué)生思考圖的存儲(chǔ)中需要關(guān)心什么，怎么存以及大致的程序邏輯等。通過對(duì)實(shí)例的分析，引入課程主要內(nèi)容，學(xué)生也可明確課程的性質(zhì)和專業(yè)地位并思考課程學(xué)習(xí)目標(biāo)。

2制定實(shí)驗(yàn)教學(xué)計(jì)劃，設(shè)計(jì)實(shí)驗(yàn)內(nèi)容

程序設(shè)計(jì)語言是數(shù)據(jù)結(jié)構(gòu)的前驅(qū)課程之一，多數(shù)院校都是以C語言程序設(shè)計(jì)作為學(xué)生程序邏輯訓(xùn)練的課程。數(shù)據(jù)結(jié)構(gòu)教材中采用類C語言來描述算法，對(duì)指針、結(jié)構(gòu)體等內(nèi)容并未作詳細(xì)的介紹。對(duì)于剛剛學(xué)完C語言的學(xué)生來說，指針等內(nèi)容本來就比較模糊，要將類C算法轉(zhuǎn)換為程序?qū)崿F(xiàn)就更加困難。

在制定實(shí)驗(yàn)教學(xué)計(jì)劃時(shí)，可以采用由易到難、逐步加深的方式來安排實(shí)驗(yàn)內(nèi)容。結(jié)合實(shí)驗(yàn)學(xué)時(shí)數(shù)和教學(xué)大綱要求，筆者將實(shí)驗(yàn)內(nèi)容作了如下設(shè)計(jì)和安排：

2.1第一次上機(jī)任務(wù)只要求學(xué)生運(yùn)用以前學(xué)過的C語言知識(shí)來編寫一個(gè)程序：給定一個(gè)整數(shù)序列，要求①用冒泡或選擇算法進(jìn)行排序；②輸入一個(gè)整數(shù)X，在此有序序列中進(jìn)行查找，如成功，則返回其位置；③如查找不成功，將X插入到序列中并使序列仍然有序。此題目運(yùn)用到數(shù)組的定義、排序、查找、數(shù)組元素插入算法等相關(guān)內(nèi)容。通過此實(shí)驗(yàn)，不僅能了解學(xué)生程序語言的熟悉程度，也能了解學(xué)生對(duì)排序和查找等基礎(chǔ)算法的掌握情況，為后面教學(xué)內(nèi)容設(shè)計(jì)作好鋪墊。

2.2結(jié)合教學(xué)進(jìn)度要求學(xué)生實(shí)現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的基本操作，并能作一些驗(yàn)證性的實(shí)驗(yàn)。如用數(shù)字菜單的形式實(shí)現(xiàn)單向鏈表的基本操作，并完成兩個(gè)有序鏈表合并算法的驗(yàn)證。實(shí)驗(yàn)要求學(xué)生能實(shí)現(xiàn)大多數(shù)基本操作算法，完成頭文件的設(shè)計(jì)，并能利用已實(shí)現(xiàn)的基本操作完成復(fù)雜算法的驗(yàn)證。通過此類實(shí)驗(yàn)，學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的理解更直觀，程序邏輯更清晰，C語言的掌握能力逐漸增強(qiáng)，同時(shí)也為面向?qū)ο笳n程的學(xué)習(xí)打下一定的基礎(chǔ)。

2.3設(shè)計(jì)性實(shí)驗(yàn)即課程設(shè)計(jì)安排。課程設(shè)計(jì)的目的在于培養(yǎng)學(xué)生分析和解決實(shí)際問題的能力，訓(xùn)練和提高學(xué)生規(guī)范的程序設(shè)計(jì)方法。教師可推出一些典型的并與后續(xù)課程有一定聯(lián)系的題目供學(xué)生選擇。每個(gè)題目規(guī)模不能太小，并能反映相關(guān)數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中起的關(guān)鍵作用。如：①實(shí)現(xiàn)一個(gè)串的基本操作演示程序，提供命令行的輸入（仿照COMMAND），并對(duì)命令行能進(jìn)行簡(jiǎn)單的編譯和出錯(cuò)處理，最后根據(jù)命令動(dòng)詞的功能來執(zhí)行命令；②利用哈夫曼編碼算法實(shí)現(xiàn)簡(jiǎn)單文本文件的壓縮和解壓。題目隨著理論教學(xué)進(jìn)度推出，有難有易，學(xué)生結(jié)合自己實(shí)際來選擇并可提前完成。

3規(guī)范實(shí)驗(yàn)過程，加強(qiáng)實(shí)驗(yàn)教學(xué)管理

為保障計(jì)劃的有效實(shí)施，必須規(guī)范實(shí)驗(yàn)過程并加強(qiáng)實(shí)驗(yàn)教學(xué)管理。

3.1根據(jù)計(jì)劃制定實(shí)驗(yàn)指導(dǎo)書。指導(dǎo)書中給出每個(gè)實(shí)驗(yàn)的目的、學(xué)時(shí)、內(nèi)容等。其中設(shè)計(jì)性實(shí)驗(yàn)另給出一些基本的分析思路，每個(gè)實(shí)驗(yàn)都適當(dāng)?shù)奶砑右恍┻x作題。學(xué)生通過閱讀實(shí)驗(yàn)指導(dǎo)書能進(jìn)一步明確每次實(shí)驗(yàn)的具體內(nèi)容和要求。

3.2要求學(xué)生做好上機(jī)前的準(zhǔn)備。大二學(xué)生的編碼速度普遍較慢，如果把實(shí)驗(yàn)課時(shí)間主要用于輸入代碼是非常不值得的，應(yīng)將主要精力放在程序調(diào)試上面。這樣不僅有充足的提問時(shí)間，也便于教師歸納并集中講解學(xué)生調(diào)試過程中所遇到的常見問題。

3.3要求學(xué)生實(shí)驗(yàn)后完成實(shí)驗(yàn)報(bào)告。報(bào)告中須給出問題分析、數(shù)據(jù)描述、算法描述、程序描述、測(cè)試結(jié)果和心得體會(huì)等內(nèi)容。教師對(duì)學(xué)生提交的實(shí)驗(yàn)報(bào)告進(jìn)行分析，總結(jié)并指出實(shí)驗(yàn)的成功和不足之處。

3.4加強(qiáng)實(shí)驗(yàn)教學(xué)管理，從正面引導(dǎo)學(xué)生。隨著網(wǎng)絡(luò)信息技術(shù)的發(fā)展，網(wǎng)絡(luò)中提供的各種信息服務(wù)和娛樂方式使部分學(xué)生的學(xué)習(xí)積極性逐漸降低，學(xué)習(xí)目標(biāo)也越來越不明確。如果管理松懈，有些學(xué)生就會(huì)把實(shí)踐學(xué)習(xí)當(dāng)成是簡(jiǎn)單的Ctrl-C和Ctrl-V，不能達(dá)到實(shí)驗(yàn)教學(xué)的預(yù)期目標(biāo)。因此，教師應(yīng)了解學(xué)生的學(xué)習(xí)動(dòng)態(tài)，加強(qiáng)實(shí)踐教學(xué)管理，并根據(jù)實(shí)際情況進(jìn)行相應(yīng)調(diào)整和改進(jìn)。

4豐富教學(xué)手段，搞好實(shí)驗(yàn)指導(dǎo)

在實(shí)踐教學(xué)過程，教師不能只停留于解決學(xué)生提出的問題，還應(yīng)不斷摸索教學(xué)方法，豐富教學(xué)手段。

4.1演示基本算法實(shí)現(xiàn)時(shí)可采用互動(dòng)的方式進(jìn)行。先按類型定義→初始化→輸入測(cè)試數(shù)據(jù)→輸出的實(shí)現(xiàn)順序和學(xué)生一起得到結(jié)果；再讓學(xué)生逐個(gè)實(shí)現(xiàn)其余算法，最后完成頭文件的設(shè)計(jì)。學(xué)生通過教師演示和實(shí)際操作可以更快的掌握類C算法和C程序的轉(zhuǎn)換思路。

4.2數(shù)據(jù)結(jié)構(gòu)中的程序規(guī)模相比C語言來說更大。由于缺乏經(jīng)驗(yàn)，很多學(xué)生在程序調(diào)試中會(huì)出現(xiàn)較多的語法和邏輯錯(cuò)誤，可利用多媒體網(wǎng)絡(luò)教學(xué)手段在學(xué)生機(jī)上直接演示并講解程序調(diào)試的方法和技巧。

4.3學(xué)生實(shí)驗(yàn)過程中盡力營(yíng)造一種你追我趕的競(jìng)爭(zhēng)氛圍，通過激勵(lì)機(jī)制提高學(xué)生學(xué)習(xí)積極性。如果有同學(xué)較早實(shí)現(xiàn)了某些算法，可有選擇性的適當(dāng)?shù)摹按碳ぁ辈糠謱W(xué)生以激發(fā)其不服輸?shù)男睦?，從而帶?dòng)其他學(xué)生。

4.4鼓勵(lì)學(xué)生多實(shí)踐，要求學(xué)生通過實(shí)踐來找出理論學(xué)習(xí)中存在的問題，提高自己的抽象思維和邏輯推理能力。對(duì)于編程能力較強(qiáng)的學(xué)生，鼓勵(lì)他們多做題，做難題，為今后參加各種資格水平考試和專業(yè)競(jìng)賽作好準(zhǔn)備。

5總結(jié)

《數(shù)據(jù)結(jié)構(gòu)》是一門理論和實(shí)踐結(jié)合性非常強(qiáng)的課程，其課程性質(zhì)決定了教學(xué)過程的復(fù)雜性。作為承擔(dān)課程教學(xué)的老師，不管是理論教學(xué)還是實(shí)驗(yàn)教學(xué)，都應(yīng)結(jié)合學(xué)生的特點(diǎn)，從教學(xué)設(shè)計(jì)、教學(xué)手段、教學(xué)管理等多方面進(jìn)行深入具體的探討和研究，并運(yùn)用到教學(xué)實(shí)踐中。只有這樣，才能真正使學(xué)生理解《數(shù)據(jù)結(jié)構(gòu)》課程意義和課程核心地位。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏,吳偉民.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：清華大學(xué)出版社.1997.[2]黃現(xiàn)代.“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)改革與實(shí)踐[J].北京：計(jì)算機(jī)教育.2007（16）.[3]李丹丹.數(shù)據(jù)結(jié)構(gòu)教學(xué)改革與實(shí)踐[J].北京：北京城市學(xué)院學(xué)報(bào).2007（3）.

第二篇：大學(xué)物理實(shí)驗(yàn)教學(xué)方法反思論文

[摘要]知識(shí)經(jīng)濟(jì)時(shí)代的來臨，促進(jìn)了復(fù)合型人才和高新型技術(shù)人才的發(fā)展，我國(guó)高校為了讓高水平的專業(yè)人才在多領(lǐng)域中發(fā)揮重要的推動(dòng)作用，在實(shí)際教學(xué)中不斷地研究創(chuàng)新教學(xué)方式，從而促進(jìn)高校人才的培養(yǎng)。而在大學(xué)物理實(shí)驗(yàn)教學(xué)中，當(dāng)前的教學(xué)方式還無法將教學(xué)的效果完美體現(xiàn)，高校需要在教學(xué)方式的選擇上，同時(shí)代的發(fā)展相結(jié)合，創(chuàng)新培養(yǎng)方式，推動(dòng)創(chuàng)新型人才的培養(yǎng)。因此，從大學(xué)物理實(shí)驗(yàn)教學(xué)的理論基礎(chǔ)開始分析，對(duì)物理規(guī)律探索下的物理實(shí)驗(yàn)教學(xué)方法簡(jiǎn)要闡述，通過構(gòu)建大學(xué)物理實(shí)驗(yàn)教學(xué)的模型，以促進(jìn)教學(xué)成效的優(yōu)化。

[關(guān)鍵詞]物理規(guī)律探索；大學(xué)物理實(shí)驗(yàn)；教學(xué)方式創(chuàng)新

當(dāng)前社會(huì)的發(fā)展促進(jìn)了人才的發(fā)展，許多高新型技術(shù)人才逐漸展露出自身的積極意義，其不僅能夠作為國(guó)家經(jīng)濟(jì)和國(guó)立發(fā)展的動(dòng)力，還能夠讓社會(huì)各行各業(yè)中的高層次發(fā)展水平進(jìn)一步提升。所以，在物理學(xué)科中，高水平專業(yè)人才的培養(yǎng)成為重點(diǎn)的教學(xué)目標(biāo)之一。物理學(xué)科在長(zhǎng)期的教學(xué)發(fā)展中，逐漸形成了有關(guān)教學(xué)的重要的指導(dǎo)思想和探索物理知識(shí)的規(guī)律和方式，這些規(guī)律能夠有效的促進(jìn)學(xué)生對(duì)物理學(xué)科的認(rèn)知，為學(xué)生的物理創(chuàng)造力提供有力的知識(shí)基礎(chǔ)。近些年，物理規(guī)律探索下的大學(xué)物理實(shí)驗(yàn)教學(xué)方式被廣泛關(guān)注，教師需要在整理完善理論基礎(chǔ)以及實(shí)驗(yàn)方法的基礎(chǔ)上，不斷的開創(chuàng)新的教學(xué)模式，幫助我國(guó)創(chuàng)新型人才的培養(yǎng)模式更加系統(tǒng)化。

1大學(xué)物理實(shí)驗(yàn)教學(xué)的理論基礎(chǔ)

1.1元認(rèn)知理論

主體認(rèn)知活動(dòng)的認(rèn)知是元認(rèn)知理論的主要內(nèi)容，其中包含了自身認(rèn)知能力、認(rèn)知過程以及這兩者之間的相互作用，這一理論主要研究元認(rèn)知知識(shí)、元認(rèn)知監(jiān)控、元認(rèn)知體驗(yàn)。元認(rèn)知知識(shí)主要對(duì)認(rèn)知的規(guī)律和知識(shí)內(nèi)容的研究；元認(rèn)知監(jiān)控主要是指認(rèn)知活動(dòng)的運(yùn)用過程；而元認(rèn)知體驗(yàn)則是包含了監(jiān)控過程中產(chǎn)生的不同情緒，一些人的自我效能感較高，在元認(rèn)知監(jiān)控過程中，體會(huì)的經(jīng)驗(yàn)會(huì)較多?，F(xiàn)代教學(xué)中，自主學(xué)習(xí)能力的培養(yǎng)和元認(rèn)知能力的培養(yǎng)相符[1]，大學(xué)中為學(xué)生開展的不同類型的教育活動(dòng)能夠有效的促進(jìn)學(xué)生的認(rèn)知能力和認(rèn)知情感發(fā)展，讓學(xué)生通過不同的渠道，掌握正確的思維方式，提升自我效能感。

1.2交往學(xué)習(xí)理論

這一理論主要是指學(xué)習(xí)者通過和其他人的交流、溝通、互動(dòng)，完善致使的獲取和能力的提升，所以，這一理論又被稱為人及學(xué)習(xí)理論，或者溝通學(xué)習(xí)理論。在實(shí)際的學(xué)習(xí)中，學(xué)習(xí)者之間的溝通要在平等、自由的基礎(chǔ)上，溝通雙方保持尊重，并且在溝通的過程中，能夠獲得靈感、啟發(fā)、借鑒，促進(jìn)學(xué)習(xí)者的學(xué)習(xí)效果，讓學(xué)習(xí)者從思想誤區(qū)中走出來，促進(jìn)雙方的心理和智力的提升。這樣，才能是良好的溝通交流。而大學(xué)教學(xué)中，交往學(xué)習(xí)理論能夠完美的運(yùn)用在其中，學(xué)生和教師之間、學(xué)生和學(xué)生之間都能夠進(jìn)行交流，尤其在實(shí)踐中，通過合理的組員分配，對(duì)單一問題實(shí)現(xiàn)充分的研究探討[2]。

2物理規(guī)律探索下的大學(xué)物理實(shí)驗(yàn)教學(xué)方式

2.1教學(xué)方式中的觀察實(shí)驗(yàn)法

大學(xué)物理學(xué)方法論在物理學(xué)的發(fā)展中，經(jīng)過了漫長(zhǎng)的過程之后，形成了較為成熟的科學(xué)探索方法，其中包含了許多極為有益于物理學(xué)發(fā)展的方式。而觀察實(shí)驗(yàn)法在物理學(xué)研究上屬于基礎(chǔ)的探索方式，大多數(shù)物理規(guī)律的發(fā)現(xiàn)和生活觀察以及實(shí)驗(yàn)的驗(yàn)證結(jié)果有著直接的關(guān)系。例如：牛頓發(fā)現(xiàn)了萬有引力現(xiàn)象等等，但是，在生活中，很多物理現(xiàn)象致使表面人們看到的現(xiàn)象，并且這些現(xiàn)象還有可能誤導(dǎo)人得出錯(cuò)誤的結(jié)論，例如：物體下落速度和物體的重量成正比這一說法。物理學(xué)研究需要經(jīng)過漫長(zhǎng)的觀察實(shí)驗(yàn)，驗(yàn)證總結(jié)之后，循環(huán)往復(fù)的找出其中的新型規(guī)律，這樣才能保證在長(zhǎng)期的發(fā)展中，實(shí)現(xiàn)物理學(xué)的拓展。

2.2教學(xué)方式中的邏輯思維法

邏輯思維顧名思義使用思維上的邏輯分析，將物理現(xiàn)象通過歸納演繹、系統(tǒng)分析、推論驗(yàn)證、假說試驗(yàn)真方式，將物理規(guī)律的過程發(fā)現(xiàn)。邏輯思維法得出的結(jié)論需要在事實(shí)材料為依據(jù)的基礎(chǔ)上實(shí)現(xiàn)，否則得出的結(jié)論必然會(huì)被推翻。而在歸納演繹中，就是將大量的事實(shí)依據(jù)進(jìn)行歸納，對(duì)其中的次要因素和干擾性因素排除之后，將不同的環(huán)節(jié)進(jìn)行研究，而后對(duì)不同環(huán)節(jié)中的研究成果綜合分析，最終完成復(fù)雜的問題研究，例如：物理學(xué)中的力學(xué)分解、微元思想等等。而推論驗(yàn)證主要是對(duì)已經(jīng)看到的事實(shí)或者現(xiàn)象提出一種假設(shè)[3]，這種假設(shè)需要符合物理學(xué)基本的理論，而后，再通過試驗(yàn)的方式，對(duì)得出的假設(shè)進(jìn)行驗(yàn)證，一般會(huì)需要大量的實(shí)驗(yàn)來完成這一步，如果實(shí)驗(yàn)法對(duì)同一個(gè)問題提出了不同假說，那么在采用不同方式進(jìn)行論證的同時(shí)，能夠?qū)㈠e(cuò)誤的觀點(diǎn)排除，通過不斷地驗(yàn)證之后，將正確的結(jié)論得出，從而實(shí)現(xiàn)物理學(xué)的規(guī)律驗(yàn)證。

2.3教學(xué)方式中的數(shù)學(xué)方法

這一方法在物理規(guī)律探索中，屬于重要的方式，數(shù)學(xué)方法不僅僅能夠?qū)⑽锢韺W(xué)研究計(jì)算推理，還能夠?qū)?shù)學(xué)中的思維運(yùn)用到物理學(xué)中，幫助物理學(xué)的研究更加深入化。例如：瞬時(shí)速度、電場(chǎng)強(qiáng)度和磁場(chǎng)感應(yīng)等等都應(yīng)用了數(shù)學(xué)思維。

3結(jié)語

物理規(guī)律探索下的大學(xué)物理實(shí)驗(yàn)教學(xué)更加有利于學(xué)生的物理思維培養(yǎng)，教師要用科學(xué)的教學(xué)方式激發(fā)學(xué)生對(duì)物理學(xué)習(xí)的興趣，從而引導(dǎo)性地促進(jìn)學(xué)生創(chuàng)新意識(shí)的產(chǎn)生，為創(chuàng)新型人才的培養(yǎng)提供良好的發(fā)展基礎(chǔ)。

【參考文獻(xiàn)】

[1]李冬梅.基于物理規(guī)律探索下大學(xué)物理實(shí)驗(yàn)教學(xué)方法的研究[J].高教學(xué)刊,2018,34(5):88-90.[2]張春玲.基于物理規(guī)律探索的大學(xué)物理實(shí)驗(yàn)教學(xué)方法初探[D].上海：華中師范大學(xué),2014.[3]梅策香,柳鈺,曾利霞.大學(xué)物理教學(xué)方法中實(shí)驗(yàn)教學(xué)的作用研究[J].科技經(jīng)濟(jì)導(dǎo)刊,2016,34(29):171.

第三篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書

數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書

目錄

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書.......................................................................................................................1

目錄...........................................................................................................................................1 實(shí)驗(yàn)指導(dǎo)書概述...............................................................................................................................2 上機(jī)實(shí)驗(yàn)題目...................................................................................................................................3

實(shí)驗(yàn)一 C語言相關(guān)知識(shí)復(fù)習(xí)................................................................................................3

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................3

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................3 實(shí)驗(yàn)二 單鏈表的插入、刪除...............................................................................................3

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................3

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................3

三、實(shí)現(xiàn)提示...................................................................................................................4 實(shí)驗(yàn)三 棧及其應(yīng)用.................................................................................................................5

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................5

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................5 實(shí)驗(yàn)四 二叉樹的遞歸算法.....................................................................................................6

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................6

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................6 實(shí)驗(yàn)五 圖的遍歷.....................................................................................................................7

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)六 有序表的查找.............................................................................................................7

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)七 哈希表.........................................................................................................................7

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)八 內(nèi)部排序算法的應(yīng)用.................................................................................................8

一、實(shí)驗(yàn)?zāi)康?..................................................................................................................8

二、實(shí)驗(yàn)內(nèi)容...................................................................................................................8

實(shí)驗(yàn)指導(dǎo)書概述

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是一門關(guān)鍵性核心課程。本課程系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對(duì)其進(jìn)行了性能分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)。

由于以下原因，使得掌握這門課程具有較大難度： ? 內(nèi)容多，時(shí)間短，給學(xué)習(xí)帶來困難；

? 貫穿全書的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)和難點(diǎn)； ? 隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點(diǎn)和難點(diǎn)； ? 先修課程中所介紹的專業(yè)性知識(shí)不多，加大了學(xué)習(xí)難度。

由于數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實(shí)踐性，《數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)》的設(shè)置十分必要。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計(jì)所需的技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些典型問題，通過分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。

上機(jī)實(shí)踐是對(duì)學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通過上機(jī)實(shí)踐，使學(xué)生在可能短的時(shí)間內(nèi)對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)的實(shí)踐和應(yīng)用有一個(gè)比較全面和系統(tǒng)的認(rèn)識(shí)，達(dá)到理論與實(shí)踐相結(jié)合的目的。

為了達(dá)到上述目的，本指導(dǎo)書安排了8個(gè)實(shí)驗(yàn)題目，它們與教科書的各章有緊密的關(guān)系，使學(xué)生在實(shí)驗(yàn)后能加深對(duì)課程內(nèi)容的理解，增強(qiáng)動(dòng)手能力。

每個(gè)實(shí)驗(yàn)題目采取了統(tǒng)一的格式，由問題描述、基本要求、測(cè)試數(shù)據(jù)、實(shí)現(xiàn)提示等部分組成。

問題描述旨在為讀者建立問題提出的背景環(huán)境，指明問題“是什么”；

要求則對(duì)問題進(jìn)一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求；

測(cè)試部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實(shí)習(xí)題時(shí)應(yīng)自己設(shè)計(jì)完整和 嚴(yán)格的測(cè)試方案，當(dāng)數(shù)據(jù)輸入量較大時(shí)，提倡以文件形式向程序提供輸入數(shù)據(jù)；

實(shí)現(xiàn)提示對(duì)實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問題作了簡(jiǎn)要提示，個(gè)別問題給出了參考實(shí)現(xiàn)。

下面帶*的題目為選做題目。

上機(jī)實(shí)驗(yàn)題目

實(shí)驗(yàn)一 C語言相關(guān)知識(shí)復(fù)習(xí)

一、實(shí)驗(yàn)?zāi)康?/p>

復(fù)習(xí)C語言中函數(shù)、數(shù)組、結(jié)構(gòu)體、文件等概念，掌握它們的描述與操作方法；熟悉掌握C++中typedef、引用參數(shù)調(diào)用（&）的概念及使用方法，為理解數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)內(nèi)容以及算法書寫奠定基礎(chǔ)。

二、實(shí)驗(yàn)內(nèi)容 問題描述：編寫一個(gè)函數(shù)，求一個(gè)整數(shù)數(shù)組中的最大、最小值。

要求：在函數(shù)聲明中采用引用參數(shù)傳遞方式實(shí)現(xiàn)最大、最小值的返回。測(cè)試：在主函數(shù)中輸入10個(gè)數(shù)，調(diào)用此函數(shù)，打印輸出最大和最小值。2 關(guān)于指針的使用：

用malloc方式分別申請(qǐng)兩個(gè)指針，并實(shí)現(xiàn)兩個(gè)指針內(nèi)容的比較大小操作。要求：此功能在一個(gè)函數(shù)內(nèi)實(shí)現(xiàn)，該函數(shù)接受兩個(gè)整數(shù)值，存儲(chǔ)到兩個(gè)指針內(nèi)容中，輸出兩者中的最大值。

測(cè)試：從主函數(shù)中輸入兩個(gè)數(shù)，調(diào)用該函數(shù)，打印輸出交換后的值。

實(shí)驗(yàn)二 單鏈表的插入、刪除

一、實(shí)驗(yàn)?zāi)康?/p>

1、熟悉某種數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)上實(shí)現(xiàn)的方法。

2、掌握單鏈表的定義、創(chuàng)建、插入、刪除、遍歷等基本操作的實(shí)現(xiàn)。

3、體會(huì)單鏈表操作、有序表插入、刪除的一般方法。

二、實(shí)驗(yàn)內(nèi)容

問題描述：已知遞增有序的單鏈表A，編寫算法實(shí)現(xiàn)向A中插入或刪除一個(gè)元素，并保持A的有序性。

實(shí)驗(yàn)要求：

1、結(jié)點(diǎn)的數(shù)據(jù)均為整型。

2、若表中已經(jīng)存在此元素，則不插入

三、實(shí)現(xiàn)提示

1.在已知的線性表中插入或刪除，需要下面的輔助函數(shù)：線性表的創(chuàng)建、線性表的遍歷

2.在單鏈表表中插入或刪除，需依次實(shí)現(xiàn)：

a)單鏈表結(jié)構(gòu)的定義

b)單鏈表的創(chuàng)建（頭插法或尾插法建表）c)單鏈表的遍歷

d)單鏈表的插入、刪除（采用順序查找方法，順頭指針往后，查找插入或刪除位置，再修改指針）

//頭文件

#include “stdlib.h” //預(yù)定義常量 #define NULL 0

//單鏈表的定義

typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//單鏈表的創(chuàng)建

void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

q=L;

scanf(“%d”,&data);while(data!=0){

p=(LinkList)malloc(sizeof(LNode));

p->data=data;

p->next=q->next;

q->next=p;

q=p;

scanf(“%d”,&data);} }

//單鏈表的遍歷

void TranverseList(LinkList L){

LinkList p;

p=L->next;

if(p==NULL)

{

printf(“niln”);

return;

}

while(p!=NULL)

{

printf(“%d ”,p->data);

p=p->next;

}

printf(“n”);}

實(shí)驗(yàn)三 棧及其應(yīng)用

一、實(shí)驗(yàn)?zāi)康?/p>

1、熟悉棧的順序表示與實(shí)現(xiàn)。

2、熟悉棧的應(yīng)用。

3、理解并掌握遞歸函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容 問題描述：利用棧實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為d進(jìn)制數(shù) 要求：

1)輸入一個(gè)n和d，打印輸出d進(jìn)制數(shù)序列。

2)利用順序棧來實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為其他d進(jìn)制數(shù)。此時(shí)，需要同時(shí)實(shí)現(xiàn)初始化空棧、入棧、出棧、判?？盏容o助功能。測(cè)試數(shù)據(jù)：

（1）輸入n:1348

d:8 輸出：2504（2）輸入n:9

d:8 輸出：11（3）輸入n:0

d:8 輸出：0 2 問題描述：利用棧實(shí)現(xiàn)算術(shù)表達(dá)式求值。要求：

1)參與運(yùn)算的操作數(shù)為10以內(nèi)的數(shù)值。測(cè)試數(shù)據(jù)：

自擬。

實(shí)驗(yàn)四 二叉樹的遞歸算法

一、實(shí)驗(yàn)?zāi)康?/p>

1、掌握二叉樹的表示與實(shí)現(xiàn)。

2、掌握二叉樹的定義、創(chuàng)建、遍歷等基本操作的實(shí)現(xiàn)。

3、熟悉求二叉樹深度等遞歸算法的設(shè)計(jì)與實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容

問題描述：已知二叉樹t，分別采用順序存儲(chǔ)結(jié)構(gòu)、二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)求二叉樹的深度，并對(duì)二叉樹分別進(jìn)行中序遍歷。要求：

1、二叉樹分別采用順序或二叉鏈表存儲(chǔ)。

2、樹中的數(shù)據(jù)類型約定為整型。測(cè)試數(shù)據(jù)：

1、輸入序列：-+a??*b??-c??d??/e??f??創(chuàng)建二叉樹； 輸出：深度：5

前序序列：-+a*b-cd/ef

中序序列：a+b*c-d-e/f

后序序列：abcd-*+ef/-T:d / e f

2、t=nil

輸入：?

輸出：深度：0 實(shí)驗(yàn)五 圖的遍歷

一、實(shí)驗(yàn)?zāi)康?/p>

熟悉圖的基本操作，掌握?qǐng)D遍歷的設(shè)計(jì)與實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容

問題描述：已知的描述校園景點(diǎn)的圖，實(shí)現(xiàn)對(duì)該圖的深度優(yōu)先和廣度優(yōu)先遍歷。要求：

圖采用鄰接矩陣存儲(chǔ)，頂點(diǎn)信息包括景點(diǎn)的名稱和簡(jiǎn)單描述。

實(shí)驗(yàn)六 有序表的查找

一、實(shí)驗(yàn)?zāi)康?/p>

1、理解各種查找方法的基本思想

2、熟悉有序表查找方法的算法實(shí)現(xiàn)

二、實(shí)驗(yàn)內(nèi)容 已知一有序的序列{1,3,5,7,9}，采用折半法分別查找3和6。

2已知輸入一無序的序列{5,1,3,9,7}，創(chuàng)建一棵二叉排序樹，然后對(duì)其遍歷，輸出遞增有序的序列。

實(shí)驗(yàn)七 哈希表

一、實(shí)驗(yàn)?zāi)康?/p>

理解哈希表的概念和基本操作；熟悉哈希表的創(chuàng)建、查找、插入的算法實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容

問題描述：已知11位好友的名字各不相同，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)哈希表，根據(jù)好友的名字，可以取得其生日。要求：

1、好友的信息包含名字和生日兩個(gè)數(shù)據(jù)項(xiàng)，其中好友的名字為主鍵，用漢語拼音形式存放；

2、哈希函數(shù)采?。汉糜衙种兴衅匆糇帜窤SCII碼值的和 MOD 11(除以1取余)；

3、采取線性探測(cè)再散列的方式處理沖突。

實(shí)驗(yàn)八 內(nèi)部排序算法的應(yīng)用

一、實(shí)驗(yàn)?zāi)康?/p>

理解各種內(nèi)部排序方法的基本思想；熟悉各種內(nèi)部排序方法的算法實(shí)現(xiàn)

二、實(shí)驗(yàn)內(nèi)容

問題描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分別采取下列排序方法對(duì)其進(jìn)行排序：

（1）直接插入排序；

（2）簡(jiǎn)單選擇排序；

（3）起泡排序；（4）快速排序；（5）堆排序。

第四篇：實(shí)驗(yàn)7 數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)七

稀疏矩陣的實(shí)現(xiàn)基本操作

班級(jí)：1208341

4學(xué)號(hào)：1208141姓名：陳峰

一、實(shí)驗(yàn)內(nèi)容

（1）掌握稀疏矩陣的壓縮存儲(chǔ)；（2）掌握稀疏矩陣的轉(zhuǎn)置算法；

二、實(shí)驗(yàn)?zāi)康?/p>

（1）實(shí)現(xiàn)上三角陣的壓縮存儲(chǔ)；

（2）用三元組書序表存儲(chǔ)稀疏矩陣，并實(shí)現(xiàn)矩陣的轉(zhuǎn)置；

三、設(shè)計(jì)思想

（1）創(chuàng)建一個(gè)數(shù)組；（2）輸入數(shù)據(jù)；

（3）給定矩陣任一元素的下標(biāo)；（4）打印給定下標(biāo)所對(duì)應(yīng)的數(shù)據(jù)；（5）創(chuàng)建三元組順序表；（6）輸入矩陣中的數(shù)據(jù)；（7）輸出對(duì)應(yīng)的矩陣；

四、程序源代碼

（1）三元組順序表存儲(chǔ)稀疏矩陣并實(shí)現(xiàn)矩陣的轉(zhuǎn)置；

#include #include

# define MAXSIZE 100 # define MAXRC 10

struct Triple {

int i,j;

/*該非零元的行下標(biāo)和列下標(biāo)*/

int e;};struct TSMtrix {

struct Triple data[MAXSIZE+1];

/*非零元三元組表，data[0]未用*/

int rpos[MAXRC+1];

/*各行第一個(gè)非零元的位置表*/

int cpos[MAXRC+1];

/*各列第一個(gè)非零元的位置表*/

int num[MAXRC+1];

/*各列非零元的個(gè)數(shù)*/

int mu,nu,tu;

/*矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)*/ };

void CreateMtrix(struct TSMtrix *M){ /*創(chuàng)建一個(gè)稀疏矩陣*/

int i,elem,col,row,mu,nu,tu;

printf(“please input matrix col,row,unzeroed numbers:n”);

scanf(“%d%d%d”,&mu,&nu,&tu);

M->mu=mu;

M->nu=nu;

M->tu=tu;

for(i=1;i<=tu;i++)

{

printf(“please input element col,row,value:n”);

scanf(“%d%d%d”,&col,&row,&elem);

if(mu<0 || nu<0 || mu>M->mu || nu>M->nu)

{

printf(“error!”);

i--;

}

else

{

M->data[i].i=col;

M->data[i].j=row;

M->data[i].e=elem;

}

} }

void ShowMtrix(struct TSMtrix M){ /*打印出矩陣*/

int i=1,j=1,dir=1;

printf(“The matrix is:n”);

for(i=1;i<=M.mu;i++)

{

for(j=1;j<=M.nu;j++)

{

if(M.data[dir].i==i && M.data[dir].j==j)

{

printf(“%d

”,M.data[dir].e);

/*存在非零元*/

dir++;

}

else

printf(“0

”);

}

printf(“n”);

} }

void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T){ /*矩陣的快速轉(zhuǎn)置*/

int t=1,p=1,q,col=M.nu;

T->mu=M.mu;

T->nu=M.nu;

T->tu=M.tu;

if(T->tu)

{

for(col=1;col<=M.nu;col++)

M.num[col]=0;

for(t=1;t<=M.nu;t++)

++M.num[M.data[t].j];

M.cpos[1]=1;

/*找到M中cpos的位置*/

for(col=2;col<=M.nu;col++)

M.cpos[col]=M.cpos[col-1]+M.num[col-1];

for(p=1;p<=M.tu;p++)

{

col=M.data[p].j;

q=M.cpos[col];

T->data[q].i=M.data[p].j;

T->data[q].j=M.data[p].i;

T->data[q].e=M.data[p].e;

++M.cpos[col];

}

} }

main(){

struct TSMtrix M;

struct TSMtrix N;

CreateMtrix(&M);

ShowMtrix(M);

printf(“n”);

FastTransposeSMtrix(M,&N);

ShowMtrix(N);

getch();}

（2）實(shí)現(xiàn)矩陣的經(jīng)典轉(zhuǎn)置算法并測(cè)試；

#include #include #define maxsize 1200 #define Elemtype int //該結(jié)構(gòu)體中存的是數(shù)組data[maxsize+1]中的元素的值和行標(biāo)和列標(biāo)//

typedef struct { int i,j;Elemtype e;}te;

typedef struct { te data[maxsize+1];//存儲(chǔ)非0元素的數(shù)組，該數(shù)組是從1開始，所以下面的p從等于1開始// int mu,nu,tu;//mu 表示行數(shù)，nu 表示列數(shù)，tu 表示該矩陣中非0的個(gè)數(shù)// }tx;

//向矩陣中輸入元素 int intput(tx &a){

int row,col,p=1;//row 表示元素的行標(biāo)，col 表示元素的列標(biāo)，p表示非0元素的計(jì)數(shù)器//

int temp;

printf(“請(qǐng)輸入矩陣行數(shù)：”);

scanf(“%d”,&a.mu);

printf(“請(qǐng)輸入矩陣列數(shù)：”);

scanf(“%d”,&a.nu);

printf(“請(qǐng)輸入原始矩陣的每行每列元素：n”);

for(row=1;row<=a.mu;row++)//雙重循環(huán)// {

for(col=1;col<=a.nu;col++)

{

scanf(“%d”,&temp);

if(temp!=0)

{

a.data[p].i=row;

a.data[p].j=col;

a.data[p].e=temp;

p++;

}

a.tu=p;

}

printf(“n”);

}

return 0;}

//輸出上面的矩陣

int output(tx &a){

int row,col;

int p=1;

printf(“輸出原始矩陣：n”);

for(row=1;row<=a.mu;row++)

{

for(col=1;col<=a.nu;col++)

{

if(row==a.data[p].i && col==a.data[p].j)

{

printf(“t%d”,a.data[p].e);

p++;

}

else

//剩余的輸出0//

printf(“t%d”,0);

}

printf(“n”);//換行符的位置//

}

return 0;}

//定義了一個(gè)新的矩陣b// int transpose(tx a,tx &b)

{

int row,col;

//找出非0元素//

int p,q=1;

b.mu=a.nu;//矩陣b的行數(shù)等于矩陣a的列數(shù)//

b.nu=a.mu;//矩陣b的列數(shù)等于矩陣a的行數(shù)//

b.tu=a.tu;//非0元素的個(gè)數(shù)///

if(a.tu!=0)//判斷是否有非0元素// {

//雙重循環(huán)//

for(col=1;col<=a.nu;col++)

// 該循環(huán)是以列循環(huán)目的是：把非0元素中列標(biāo)小的元素從頭排列//

{

for(p=1;p<=a.tu;p++){

if(a.data[p].j==col)

//循環(huán)非0數(shù)組中的元素，并找出a.data[p].j等于當(dāng)時(shí)的a矩陣在中的col// { //把矩陣a中非0元素的行標(biāo)和列標(biāo)等于矩陣b非0元素的列標(biāo)和行標(biāo)//

b.data[q].i=a.data[p].j;

b.data[q].j=a.data[p].i;

b.data[q].e=a.data[p].e;

q++;

} }

}

printf(“n”);

}

return 0;}

//輸出轉(zhuǎn)置后的矩陣

int outputtranspose(tx &b){

int q=1;

int row,col;

printf(“輸出轉(zhuǎn)置后的矩陣：n”);

for(row=1;row<=b.mu;row++)

{

for(col=1;col<=b.nu;col++)

{

if(row==b.data[q].i && col==b.data[q].j)//找出b矩陣非0元素//

{

printf(“t%d”,b.data[q].e);

q++;

}

else

printf(“t%d”,0);//剩余的輸出0//

}

printf(“n”);

}

return 0;}

void main(){ tx a,b;intput(a);output(a);transpose(a,b);outputtranspose(b);}

五、調(diào)試及測(cè)試數(shù)據(jù)

（1）三元組順序表存儲(chǔ)稀疏矩陣并實(shí)現(xiàn)矩陣的轉(zhuǎn)置；

（2）實(shí)現(xiàn)矩陣的經(jīng)典轉(zhuǎn)置算法并測(cè)試；

六、實(shí)驗(yàn)總結(jié)

在本實(shí)驗(yàn)中，老師給出了“三元組順序表存儲(chǔ)稀疏矩陣并實(shí)現(xiàn)矩陣的轉(zhuǎn)置”的完整實(shí)驗(yàn)代碼供我們參考。通過對(duì)參考例子的代碼的理解，看懂之后程序代碼之后就能比較輕松地寫出題目的代碼。在本次實(shí)驗(yàn)中能夠清楚的知道要做什么，從哪里開始做，怎么做，思路很清晰。經(jīng)過編程，學(xué)會(huì)了串的操作與實(shí)現(xiàn)，并且對(duì)C++也有了新的認(rèn)識(shí)。

第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書

目 錄

實(shí)驗(yàn)規(guī)則················································2 實(shí)驗(yàn)環(huán)境················································2 實(shí)驗(yàn)報(bào)告要求············································3 實(shí)驗(yàn)一 單鏈表

（一）······································4 實(shí)驗(yàn)二 單鏈表

（二）······································5 實(shí)驗(yàn)三 ?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ? 實(shí)驗(yàn)四 二叉樹···········································7 實(shí)驗(yàn)五 最短路徑·········································8 實(shí)驗(yàn)六 內(nèi)部排序·········································9

實(shí) 驗(yàn) 規(guī) 則

為了順利完成實(shí)驗(yàn)教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴(yán)謹(jǐn)、踏實(shí)、實(shí)事求是的科學(xué)作風(fēng)和愛護(hù)國(guó)家財(cái)產(chǎn)的優(yōu)良品質(zhì)，特制定以下實(shí)驗(yàn)規(guī)則：

1、實(shí)驗(yàn)前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下：

（1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計(jì)與計(jì)算。（2）熟悉實(shí)驗(yàn)內(nèi)容。

（3）預(yù)先復(fù)習(xí)，并按要求編寫程序。（4）未完成預(yù)習(xí)任務(wù)者不得進(jìn)入實(shí)驗(yàn)室。

2、遵守以下紀(jì)律：

（1）在實(shí)驗(yàn)室不得做和實(shí)驗(yàn)無關(guān)的事情。

（2）進(jìn)行任課老師指定內(nèi)容以外的實(shí)驗(yàn)，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀(jì)律，不遲到。

（4）保持實(shí)驗(yàn)室內(nèi)安靜、整潔，愛護(hù)公物，不許亂寫亂畫。

實(shí) 驗(yàn) 環(huán) 境

本實(shí)驗(yàn)在386以上的微機(jī)上進(jìn)行，運(yùn)行環(huán)境為VC6.0。

實(shí)驗(yàn)報(bào)告要求

1、實(shí)驗(yàn)題目 2．實(shí)驗(yàn)?zāi)康?3．實(shí)驗(yàn)環(huán)境

4．實(shí)驗(yàn)內(nèi)容與完成情況（可以附上自主設(shè)計(jì)的源程序）5．出現(xiàn)的問題及對(duì)問題的解決方案 6．實(shí)驗(yàn)思考：（學(xué)生對(duì)本次實(shí)驗(yàn)的收獲的總結(jié)）

實(shí)驗(yàn)一 單鏈表

（一）一、實(shí)驗(yàn)?zāi)康?/p>

掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作。

二、預(yù)習(xí)要求

1、看懂書上的算法，深入理解鏈表的物理存儲(chǔ)模式和邏輯模式。

2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。

三、實(shí)驗(yàn)內(nèi)容

實(shí)現(xiàn)一個(gè)簡(jiǎn)單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有：

1、利用單鏈表建立學(xué)生基本信息表

2、瀏覽每個(gè)學(xué)生的信息

3、根據(jù)學(xué)號(hào)查詢某個(gè)學(xué)生的基本信息

4、添加學(xué)生信息到單鏈表中

5、刪除一個(gè)學(xué)生的信息

四、實(shí)現(xiàn)提示

設(shè)計(jì)結(jié)點(diǎn)的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號(hào)、姓名、年齡、性別；要求設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個(gè)函數(shù)實(shí)現(xiàn)上述的一個(gè)功能。

實(shí)驗(yàn)二 單鏈表

（二）一、實(shí)驗(yàn)?zāi)康?/p>

掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作。

二、預(yù)習(xí)要求

1、看懂書上的算法，深入理解鏈表的物理存儲(chǔ)模式和邏輯模式。

2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。

三、實(shí)驗(yàn)內(nèi)容

1、實(shí)現(xiàn)單鏈表的就地逆置。

2、建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞減鏈表。

3、建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增鏈表。

4、編寫一個(gè)主函數(shù),調(diào)試上述算法。

四、選做題、思考題

1、如何用帶表頭結(jié)點(diǎn)的單鏈表作為多項(xiàng)式的存儲(chǔ)表示，實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加。

2、約毖夫環(huán)的實(shí)現(xiàn)。

3、如何利用文件實(shí)現(xiàn)學(xué)生信息的存取。

實(shí)驗(yàn)三 棧

一、實(shí)驗(yàn)?zāi)康?/p>

深入了解并掌握棧的特性及其在實(shí)際中的應(yīng)用；熟練掌握棧的算法實(shí)現(xiàn)；運(yùn)用棧操作求解實(shí)際問題。

二、預(yù)習(xí)要求

1、看懂書上的算法，深入理解棧的特性和存儲(chǔ)結(jié)構(gòu)，以便在實(shí)際問題背景下靈活運(yùn)用。

2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。

三、實(shí)驗(yàn)內(nèi)容

利用棧實(shí)現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時(shí)進(jìn)棧1，當(dāng)輸入為奇數(shù)時(shí)進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。

四、實(shí)現(xiàn)提示

1、開辟一個(gè)連續(xù)的存儲(chǔ)空間，實(shí)現(xiàn)兩個(gè)棧順序存儲(chǔ)空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實(shí)現(xiàn)棧操作。

2、采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。

五、選做題、思考題

1、兩?？臻g共享時(shí)，棧滿的條件是什么？

2、為停車場(chǎng)編制進(jìn)行管理的模擬程序（習(xí)題集P96，2.1）。

3、編寫程序，利用棧實(shí)現(xiàn)表達(dá)式求值。

實(shí)驗(yàn)四 二叉樹

一、實(shí)驗(yàn)?zāi)康?/p>

通過實(shí)踐掌握二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷思想；掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。

二、預(yù)習(xí)要求

二叉樹的三種遍歷方法。

三、實(shí)驗(yàn)內(nèi)容

1、輸入字符序列，建立二叉鏈表。

2、利用棧，編寫非遞歸算法，編程實(shí)現(xiàn)二叉樹的中序遍歷。

3、求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)。

4、在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。

四、選做題、思考題

1、如何實(shí)現(xiàn)二叉樹的后序遍歷（非遞歸）。

2、如何求二叉樹的高度。

實(shí)驗(yàn)五 最短路徑（旅游景點(diǎn)導(dǎo)游咨詢模擬）

一、實(shí)驗(yàn)?zāi)康?/p>

利用圖的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實(shí)現(xiàn)。

二、預(yù)習(xí)要求

學(xué)習(xí)了解圖的存儲(chǔ)結(jié)構(gòu)，掌握求最短路徑的兩種算法。

三、實(shí)驗(yàn)內(nèi)容

設(shè)計(jì)一個(gè)旅游景點(diǎn)導(dǎo)游模擬程序，為來訪的客人提供景點(diǎn)最短路徑的信息查詢服務(wù)，任意選取n城市，構(gòu)成一個(gè)有向帶權(quán)圖，圖中頂點(diǎn)表示城市，邊上的權(quán)值表示兩點(diǎn)間的距離，根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)的最短路徑。

四、實(shí)現(xiàn)提示

咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行，由用戶輸入起始點(diǎn)和終點(diǎn)，輸出信息：最短路徑是多少？并指出所經(jīng)過的城市。存儲(chǔ)結(jié)構(gòu)可選用鄰接矩陣。

五、選做題、思考題

1．如何實(shí)現(xiàn)對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能。

2．用鄰接表作存儲(chǔ)結(jié)構(gòu)，求一指定景點(diǎn)出發(fā)，到其余各景點(diǎn)的最短路徑。

實(shí)驗(yàn)六 內(nèi)部排序

一、實(shí)驗(yàn)?zāi)康?/p>

直觀感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)。

二、預(yù)習(xí)要求

1、常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點(diǎn)及其適用條件。

2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。

三、實(shí)驗(yàn)內(nèi)容

1、對(duì)直接插入排序和簡(jiǎn)單選擇排序算法進(jìn)行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)的比較。

2、利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編寫程序，實(shí)現(xiàn)直接插入排序和冒泡排序。

四、實(shí)現(xiàn)提示

測(cè)試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。

五、選做題、思考題

1、快速排序算法的非遞歸實(shí)現(xiàn)。

2、結(jié)合實(shí)驗(yàn)，理解針對(duì)不同待排元素的特點(diǎn)而選擇不同排序方法的重要性。

3、如何對(duì)本實(shí)驗(yàn)進(jìn)行時(shí)間、空間的復(fù)雜度分析。