數(shù)據(jù)結(jié)構(gòu)課件 附錄A-課程設(shè)計(jì)實(shí)習(xí)指導(dǎo)

課程設(shè)計(jì)指導(dǎo)1一．課程設(shè)計(jì)目的課程設(shè)計(jì)是為了進(jìn)一步培養(yǎng)學(xué)生結(jié)構(gòu)化程序設(shè)計(jì)的思想，加深對高級語言基本語言要素和控制結(jié)構(gòu)的理解，針對算法與數(shù)據(jù)結(jié)構(gòu)中的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行訓(xùn)練，獨(dú)立完成有一定工作量的程序設(shè)計(jì)任務(wù)，同時強(qiáng)調(diào)好的程序設(shè)計(jì)風(fēng)格。二．課程設(shè)計(jì)步驟2問題理解和分析充分地分析和理解問題本身，弄清要求做什么。確定解決問題的方法（設(shè)計(jì)）主要是找到解決問題的主要思路，是怎么做。在此階段可考慮系統(tǒng)的功能和模塊劃分等。詳細(xì)設(shè)計(jì)和編碼確定算法的主要流程，再進(jìn)行編程。上機(jī)前程序靜態(tài)檢查靜態(tài)檢查主要有兩種途徑：用一組測試數(shù)據(jù)手工執(zhí)行程序；通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯。程序調(diào)試和運(yùn)行完成課程設(shè)計(jì)報(bào)告按課程設(shè)計(jì)報(bào)告提綱的要求完成書寫工作。3二．課程設(shè)計(jì)步驟問題描述：題目要解決的問題是什么?；疽螅阂?guī)格及功能要求。系統(tǒng)分析：解決問題的基本方法說明，包括主要算法思想，算法的流程圖，程序中主要函數(shù)或過程的功能說明。4三．課程設(shè)計(jì)報(bào)告提綱測試數(shù)據(jù)及結(jié)果：測試數(shù)據(jù)和運(yùn)行輸出及結(jié)果分析。體會：調(diào)試過程中遇到的主要問題，是如何解決的；對設(shè)計(jì)和編碼的回顧討論和分析；改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會等。附錄：源程序清單。5三．課程設(shè)計(jì)報(bào)告提綱四．實(shí)習(xí)任務(wù)書程序調(diào)試類題目：1、單鏈表的基本操作2、用單鏈表編制集合運(yùn)算的程序3、用數(shù)組實(shí)現(xiàn)兩個非稀疏矩陣的相乘運(yùn)算4、按層次遍歷二叉樹5、快速排序6、堆排序7、二叉樹的建立及操作8、無向圖的建立及遍歷操作61．一元稀疏多項(xiàng)式計(jì)算器[問題描述]設(shè)計(jì)一個一元稀疏多項(xiàng)式簡單計(jì)算器。[基本要求]一元稀疏多項(xiàng)式簡單計(jì)算器的基本功能是：(1）輸入并建立多項(xiàng)式；(2）輸出多項(xiàng)式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,,,,,,其中n是多項(xiàng)式的項(xiàng)數(shù)，ci,ei,分別是第i項(xiàng)的系數(shù)和指數(shù)，序列指數(shù)降序排序；(3)多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；(4)多項(xiàng)式a和b相減，建立多項(xiàng)式a-b；(5)計(jì)算多項(xiàng)式在x處的值。(6)計(jì)算器的仿真界面。（選做）7程序編寫類題目[測試數(shù)據(jù)]見263頁[實(shí)現(xiàn)提示]用帶表頭結(jié)點(diǎn)的單鏈表存儲多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存放在頭結(jié)點(diǎn)中。81．一元稀疏多項(xiàng)式計(jì)算器[問題描述]以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。[基本要求](1)實(shí)現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向(2)編寫遞歸形式的算法，求得迷宮中所有可能的通路；(3)以方陣形式輸出迷宮及其通路。（選做）92．迷宮問題1

2

3

4

5

6

7

810[測試數(shù)據(jù)]左上角（1）為入口右下角（9）為出口10，01000100，010001080，。00011010111001000010000010001010111100111000101110000002．迷宮問題[實(shí)現(xiàn)提示]計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。112．迷宮問題[問題描述]利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編譯碼系統(tǒng)。123．哈夫曼編/譯碼器[基本要求]一個完整的系統(tǒng)應(yīng)具有以下功能：I:初始化(Initialization)。從終端讀入字符集大小n，及n個和m個權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree中。C:編碼(Coding)。利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件hfmtree中讀入)對文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)存入文件codefile中。133．哈夫曼編/譯碼器[基本要求]D:編碼(Decoding)。利用已建好的哈夫曼樹將文件codefile代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。P:印代碼文件(Print)。將文件codefile以緊湊格式顯示在終每行50個代碼。同時將此字符形式的編碼文件寫入文件codeprin中。T:印哈夫曼樹(Treeprinting)。將已在內(nèi)存中的哈夫曼樹以的方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件treeprint中。143．哈夫曼編/譯碼器[實(shí)現(xiàn)提示]可以根據(jù)題目要求把程序劃成5個模塊，設(shè)計(jì)成菜單方式，每次執(zhí)行一個模塊后返回菜單。除了初始化(I)過程外，在每次執(zhí)行時都經(jīng)過一次讀取磁盤文件數(shù)據(jù)。這是為了如果在程序執(zhí)行后一直沒有進(jìn)行初始化(I)過程，為了能使后面的操作順利進(jìn)行，可以通過讀取舊的數(shù)據(jù)來進(jìn)行工作。比如：如果程序的工作需要的字符集和權(quán)值數(shù)據(jù)是固定的，只要在安裝程序時進(jìn)行一次初始(I)化操作就可以了。再在次運(yùn)行程序時，不管進(jìn)行那項(xiàng)操作都可以把需要的數(shù)據(jù)讀入到內(nèi)存。153．哈夫曼編/譯碼器[算法分析]：本程序主要用到了三個算法。(1)哈夫曼編碼在初始化(I)的過程中間，要用輸入的字符和權(quán)值建立哈夫曼樹并求得哈夫曼編碼。先將輸入的字符和權(quán)值存放到一個結(jié)構(gòu)體數(shù)組中，建立哈夫曼樹，將計(jì)算所的哈夫曼編碼存儲到另一個結(jié)構(gòu)體數(shù)組中。(2)串的匹配在編碼(D)的過程中間，要對已經(jīng)編碼過的代碼譯碼，可利用循環(huán)，將代碼中的與哈夫曼編碼的長度相同的串與這個哈夫曼編碼比較，如果相等就回顯并存入文件。3)二叉樹的遍歷在印哈夫曼樹(T)的中，因?yàn)楣蚵鼧湟彩嵌鏄?，所以就要利用二叉樹的先序遍歷將哈夫曼樹輸出。163．哈夫曼編/譯碼器[測試數(shù)據(jù)]根據(jù)實(shí)驗(yàn)要求，在tobetrans.dat中輸入"THIS

PROGRAM

IS

MYFAVORITE"，字符集和其頻度如下：字符字符17頻度

20A

B

C

D

E

F

G

H

I

J

K

L

M頻度 186

64 23

22

32

103

21

15

47 57

1

5

32

20N

O

P

Q

R

S

T

U

V

W

X

Y

Z56 19

2

50

51

55

30

10 11

2 21

23．哈夫曼編/譯碼器[問題描述]大學(xué)的每個專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計(jì)一個教學(xué)計(jì)劃編制程序。184．教學(xué)計(jì)劃編制問題[基本要求]輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔?；否則將

教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)。194．教學(xué)計(jì)劃編制問題[測試數(shù)據(jù)]學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從C01到C12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見157頁圖6.22。[實(shí)現(xiàn)提示]可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯誤處理。應(yīng)建立內(nèi)部課程號與課程號之間的對應(yīng)關(guān)系204．教學(xué)計(jì)劃編制問題[問題描述]錄入、保存一個班級學(xué)生多門課程的成績，并對成績進(jìn)行分析。215．成績分析問題[基本要求]通過鍵盤輸入各學(xué)生的多門課程的成績，建立相應(yīng)的文件input.dat。對文件input.dat中的數(shù)據(jù)進(jìn)行處理，要求具有如下功能：1)按各門課程成績排序，并生成相應(yīng)的文件輸出。計(jì)算每人的平均成績，按平均成績排序，并生成文件。求出各門課程的平均成績、最高分、最低分、不及格人數(shù)、60~69分人數(shù)、70~79分人數(shù)、80~8