1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)書粧選課程設(shè)計(jì)周（時(shí)）數(shù)：1 1周指導(dǎo)方式，集體輔導(dǎo)與個(gè)別輔導(dǎo)相結(jié)合課程設(shè)計(jì)適用專業(yè)=網(wǎng)絡(luò)工程系一.課程設(shè)計(jì)的目的1、掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，初步具備根據(jù)應(yīng)用需求選擇合理數(shù)據(jù)結(jié)構(gòu)并 進(jìn)行算法設(shè)訃的能力；2、進(jìn)一步提升C語言的應(yīng)用能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和 技能；3、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具 備的科學(xué)的工作方法和作風(fēng)；5、提升文檔寫作能力。二課程設(shè)計(jì)要求1、認(rèn)真分析課題內(nèi)容和要求，明確設(shè)計(jì)任務(wù)。2、仔細(xì)分析課題，合

2、理設(shè)計(jì)算法。3、一人一題，必須獨(dú)立完成。4、必須在規(guī)定的時(shí)間內(nèi)完成課設(shè)任務(wù)，否則沒有資格參加答辯，無成績(jī)。5、嚴(yán)禁抄襲，否則取消答辯資格或成績(jī)作廢。6、設(shè)訃達(dá)到一定工作量（300行以上代碼7、課程設(shè)訃說明書不少于15貝（不包括代碼）。三、課程設(shè)計(jì)方法與步驟1、問題定義與需求分析：根據(jù)設(shè)計(jì)題U的要求，充分地分析和理解問題，確定功 能需求和限制條件。2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型和各抽象數(shù) 據(jù)類型，寫出每個(gè)抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說 明）。3、總體設(shè)訃：采用結(jié)構(gòu)化設(shè)計(jì)方法，按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，設(shè) 計(jì)軟件層次結(jié)構(gòu)和模塊

3、間的調(diào)用關(guān)系，定義主程序，畫出模塊之間的調(diào)用關(guān)系圖。在這 個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試。4、詳細(xì)設(shè)訃：定義數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，各個(gè)主要模塊的算法定義。詳細(xì)設(shè)訃的結(jié)果是 對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，用偽碼寫出 函數(shù)的算法。5、程序編碼：把詳細(xì)設(shè)訃的結(jié)果進(jìn)一步求精為程序設(shè)訃語言程序。同時(shí)加入一些 注解，使程序中邏輯概念清楚。要求用C語言編寫。6、程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練 掌握調(diào)試工具的各種功能，設(shè)訃測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。 調(diào)試正確后，認(rèn)真整理源程序及其注釋，

4、形成格式和風(fēng)格良好的源程序清單和結(jié)果。7、 設(shè)計(jì)結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入 及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析。課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)老師&*粧選8、 編寫課程設(shè)訃報(bào)告。四.設(shè)計(jì)選題：1.在圍棋比賽中，某一方（假設(shè)為黑方）在棋盤的某個(gè)位置（i, j）下子后，有 可能提取對(duì)方（0方的一審子）。以W1919表示一個(gè)棋盤，若Wij=0表示在位置（i,j）上沒有子，Wij=l表示該位置上的是黑子,Wij=-1表示該位置上是白子。 模擬實(shí)現(xiàn)五子棋功能。2.商店貨架以棧的形式擺放商品，生產(chǎn)日期越近的越黑近棧底，出棧是從棧頂取貨，一天營(yíng)業(yè)結(jié)束，

5、如果貨架不滿，則需上貨，如果直接將商品擺放到貨架上，則會(huì)使生產(chǎn) 日期越近的越鼎近棧頂這就需要倒貨架，仍使生產(chǎn)日期越近的越幕近棧底。寫出貨物 進(jìn)棧、出棧算法。3.銀行業(yè)務(wù)模擬：銀行業(yè)務(wù)模擬問題描述：客戶業(yè)務(wù)分為兩種。第一種是申請(qǐng)從銀行得到一筆資金，即取款或借款。第二種是 向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)的有兩個(gè)隊(duì)列。客戶 到達(dá)銀行后先排第一個(gè)隊(duì)。處理每個(gè)客戶業(yè)務(wù)時(shí)，如果屬于第一種，且申請(qǐng)額超出銀行 現(xiàn)存資金總額而得不到滿足，則立即排入第二隊(duì)等候，直至滿足時(shí)才離開銀行，否則業(yè) 務(wù)處理完后立即離開銀行。每接待完一個(gè)第二種業(yè)務(wù)的客戶，則順序檢查和處理（如果 可能）第二個(gè)隊(duì)列的

6、客戶，對(duì)能滿足的申請(qǐng)者予以滿足，不能滿足者重新排到第二個(gè)隊(duì) 列的隊(duì)尾。注意，在此檢査過程中，一旦銀行資金總額少于或等于剛才第一個(gè)隊(duì)列中最 后一個(gè)客戶（第二種業(yè)務(wù)）被接待之前的數(shù)額，或者本次已將第二個(gè)隊(duì)列檢查或處理了 一遍，就停止檢査（因?yàn)榇藭r(shí)已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個(gè)隊(duì)列的客戶。 任何時(shí)刻都只開一個(gè)窗口。假設(shè)檢査不需要時(shí)間。營(yíng)業(yè)時(shí)間結(jié)束時(shí)所有客戶立即離開銀 行。寫一個(gè)上述銀行業(yè)務(wù)的事件驅(qū)動(dòng)模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的 平均時(shí)間。4.運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)程序的設(shè)計(jì)任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)U,和w個(gè)女子項(xiàng)U。項(xiàng)U編號(hào)為男子1m,女子m+

7、lm+wo不同的項(xiàng)U取前五名或前三 名積分；取前五名的積分分別為：7、5、3、2、1,前三名的積分分別為：5、3、2；哪 些取前五名或前三名山學(xué)生自己設(shè)定。（ni=20,n=20）功能要求：1） .可以輸入各個(gè)項(xiàng)U的前三名或前五名的成績(jī)；2） .能統(tǒng)計(jì)各學(xué)校總分，3） .可以按學(xué)校編號(hào)、學(xué)校總分、男女團(tuán)體總分排序輸db4） ,可以按學(xué)校編號(hào)査詢學(xué)校某個(gè)項(xiàng)U的悄況；可以按項(xiàng)U編號(hào)査詢?nèi)〉们叭蚯?五名的學(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范IS： 20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱， 運(yùn)動(dòng)項(xiàng)U的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，

8、可以完成相關(guān)的功 能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存 儲(chǔ)在數(shù)據(jù)文件中。 （數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在C語言程序設(shè)計(jì)的書上，請(qǐng) 自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn) 行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；5.八皇后問題問題描述：八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué) 家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻由，即任意兩個(gè)皇后 都不能處于同一行、同一

9、列或同一斜線上，基本要求：在一個(gè)8 X 8的棋盤里放魚8個(gè)皇后，列只有一個(gè)皇后）.6.圖書管理基本業(yè)務(wù)模擬1）書的登記內(nèi)容包括書號(hào)、 書名、2）號(hào)建立索引表（線性表）以提高査找效率;3）主要功能如下：a）釆編入庫：新購(gòu)一種書，確定書號(hào)后，登記到圖書帳B表中，如果表中已有， 則只將庫存量增加；b）借閱.如果一種書的現(xiàn)存量大于0.則借出一本，登記借閱者的書證號(hào)和歸還 期限，改變現(xiàn)存量；C）歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。輸出形式：能按書號(hào)、書名、著作者査找?guī)齑娴臅畔⒛馨磳W(xué)生的借書證號(hào)顯示學(xué)生信息和借閱信息書籍入庫 借書功能實(shí)現(xiàn) 還書功能實(shí)現(xiàn)7.漫步迷宮問題描述：用m行n列的個(gè)正方格

10、表示一個(gè)迷宮，其中劃有斜線的方格表示不可通行，未劃有斜線的 方格表示可以通行。請(qǐng)編寫尋找從入口到出口的一條最短路徑的程序。基本要求：1）迷宮的規(guī)格（即行數(shù)與列數(shù)），狀態(tài)設(shè)置（即各方格能否通行的狀態(tài)），以及入口和出口的位苣, 均應(yīng)由輸入隨機(jī)確定。2）求得的最短路徑，應(yīng)該以從入口到出口的路徑上的各個(gè)方格的坐標(biāo)的線性序列輸出。當(dāng)無通 路時(shí)，應(yīng)該報(bào)告無路徑的信息。3）盡量采用結(jié)構(gòu)化程序設(shè)計(jì)方法，要求對(duì)$個(gè)模塊的功能及參數(shù)作必要的說明。實(shí)現(xiàn)提示：（1）迷宮可以采用matrix類型的二維數(shù)組A表示。A. rownum與A. colnum分別表示迷宮的實(shí)際 的行數(shù)打列數(shù)。而A. mazeij表示迷宮中第i行

11、第j列的一個(gè)方格，用A. mazeij=0表示該 方格可以通行用A. mazeij=l表示該方格不可以通行。粧選問有多少種擺法。要求毎個(gè)皇后兩兩之間不相沖突（在每一橫列豎列斜著作者、現(xiàn)存量和庫存量;粧選(2)由于要尋找從入口到出口的一條最短路徑.最好將迷宮看作是一個(gè)圖結(jié)構(gòu)。 則問題轉(zhuǎn)化為尋 找從對(duì)應(yīng)于入口頂點(diǎn)到對(duì)應(yīng)于出口頂點(diǎn)的一條最短路徑的問題。該問題可以采用從入口頂點(diǎn)出發(fā)， 進(jìn)行廣度優(yōu)先搜索遍歷，直到遇到出口頂點(diǎn)或者遍歷完畢也沒有遇到出口頂點(diǎn)為止。這二種情況分 別對(duì)應(yīng)于最短路徑探索成功與查無通路的事實(shí)。(3)基于上述分析，涉及到數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，即將二維數(shù)組表示的迷宮A轉(zhuǎn)換為以adjlist類

12、型的鄰接表表示的圖結(jié)構(gòu)G。在圖結(jié)構(gòu)中，將迷宮中的每個(gè)方格看作是一個(gè)頂點(diǎn)。不可通行的方 格都是孤立頂點(diǎn)：相鄰的可通行的方格所對(duì)應(yīng)的頂點(diǎn)之間看作是有邊相連。因此迷宮可以看作是由m如個(gè)頂點(diǎn)及無向邊構(gòu)成的一個(gè)非連通的無向圖。盡皆圖是不連通的，但不影響本問 題的求解，而且本問題有解的條件是：入口頂點(diǎn)與出口頂點(diǎn)在同一個(gè)連通分量中。 圖結(jié)構(gòu)G中，G. adjk表示編號(hào)為k的頂點(diǎn)的鄰接情況的單鏈表的頭指針：G.實(shí)際頂點(diǎn)數(shù)，而且具有如下關(guān)系：G. vexnum=A. rownum*A. colnum(4)為了避免迷宮數(shù)據(jù)的重復(fù)輸入，我們期望A能夠自動(dòng)地轉(zhuǎn)換為G。因此應(yīng)該設(shè)訃一個(gè)轉(zhuǎn)換算 法create_adjli

13、st(A. G)o而圖結(jié)構(gòu)中頂點(diǎn)是要編號(hào)的，我們約定以行為序，順序給迷宮A中的方 格所對(duì)應(yīng)的頂點(diǎn)編號(hào)。這樣迷宮中方格的坐標(biāo)(即行row和列coD與圖G中所對(duì)應(yīng)的頂點(diǎn)的編號(hào)(KP verno)之間具有如下關(guān)系：verno= (row-1) * n + colrow= (verno-1) / n + 1col= (verno-1) % n + 1(5)在廣度優(yōu)先搜索遍歷求解最短路徑過程中，應(yīng)該設(shè)置一個(gè)隊(duì)列queue作為輔助數(shù)搖結(jié)構(gòu)：路 徑采用一個(gè)整數(shù)數(shù)組pred來表示。這二個(gè)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)類型均為list類型，其說明立義如E： typedef intlistMAXVER；隊(duì)列queue應(yīng)該設(shè)置

14、front和rear分別指示列首與列尾,queuek表示第k個(gè)入列的頂點(diǎn)編號(hào)。 采用pred記錄路徑，predEi表示頂點(diǎn)i在廣度優(yōu)先搜索遍歷過程中的前趨頂點(diǎn)的編號(hào)，它表明是 經(jīng)過邊(predi, i)達(dá)到頂點(diǎn)i的。這樣，當(dāng)路徑探索成功時(shí)，我們可以從出口頂點(diǎn)倒推出從入 口到出口的一條路徑來。當(dāng)然要涉及到從頂點(diǎn)編號(hào)向方格坐標(biāo)的反轉(zhuǎn)換，這個(gè)公式在上面已經(jīng)給出To則輸出的最短路徑應(yīng)該是：6,106, 95, 95, 85, 7 5, 6 4, 64, 5-4, 4-5, 4 5,3 5, 25,14, 1-3, 1 217 18.交通咨詢系統(tǒng)(最短路徑問題)問題描述：設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能讓旅客咨

15、詢從任一個(gè)城市頂點(diǎn)到列一個(gè)城市頂點(diǎn)之間的最短路徑或 最低費(fèi)用或最少時(shí)間等問題。對(duì)于不同咨詢要求，可以輸入城市間的路程或所需要時(shí)間或所需費(fèi)用。 設(shè)計(jì)分三個(gè)部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實(shí)現(xiàn)兩個(gè) 城市頂點(diǎn)之間的最短路徑問題。基本要求：1）、對(duì)城市信息（城市需、城市間的里程）進(jìn)行編輯：具備添加、修改、刪除功能：2）、對(duì)城市間的兩種交通工具：飛機(jī)和火車。對(duì)飛機(jī)航班和列車時(shí)刻表進(jìn)行編輯：里程、航班 和列車vexnum表示圖G中的測(cè)試數(shù)據(jù)：設(shè)有如下5行10列的迷宮1 1 11 0 00 0 1000A.&C.raaze=0 01111111 0 0 0 1 1

16、10 10 0 1入口坐標(biāo)為1,10 1 1 0 0 0 1 1 0 10 0 1 0 0 0 0 1出口坐標(biāo)為6, 10 11111100粧選班次的添加、修改、刪除；3）、提供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具，可以不考慮回程：4）、旅途中的耗費(fèi)的總時(shí)間應(yīng)包括中轉(zhuǎn)站的等候時(shí)間。其中飛機(jī)至少二小時(shí)，火車至少一小時(shí)：5）、咨詢以用戶和計(jì)算機(jī)對(duì)話方式進(jìn)行，要注意人機(jī)交互的屏幕界而。由用戶選擇最優(yōu)決策原 則和交通工具，輸入超始站、終點(diǎn)站、岀發(fā)時(shí)間，輸出信息：最快需要多長(zhǎng)時(shí)間才能到達(dá)及旅費(fèi)， 或者最少需要多少旅費(fèi)才能到達(dá)及時(shí)間，井詳細(xì)說明依次于何時(shí)何地乘坐哪一趟班機(jī)或列車何時(shí)到

17、 達(dá)何地。實(shí)現(xiàn)提示：1）、算法思路（1）數(shù)據(jù)存儲(chǔ)。城市信息（城市需、代碼）、交通信息（城市間的里程、各航班和列車時(shí)刻）存儲(chǔ) 于磁盤文件。建議把城市信息存于文件前面，交通信息存于文件的后而，用fread和fwrite函數(shù)操 作。（2）數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)設(shè)計(jì)任務(wù)的描述，其城市之間的旅游交通問題是典型的圖結(jié)構(gòu)，可 看作為有向圖，圖的頂點(diǎn)是城市，邊是城市之間所耗費(fèi)的時(shí)間（要包括中轉(zhuǎn)站的等候時(shí)間）或旅費(fèi)。（3）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。采用鄰接表和鄰接矩陣都可作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，但當(dāng)鄰接邊不多時(shí)， 宜采用鄰接表，以提高空間的存儲(chǔ)效率。這里建議采用鄰接表作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（4）用不同的功能模塊對(duì)城市信息和交通信

18、息進(jìn)行編輯。添加、修改、刪除功能可用菜單方式 或命令提示方式。只要能方便的對(duì)城市信息和交通信息進(jìn)行管理即可，但要注意人機(jī)界面，具體實(shí) 現(xiàn)由學(xué)生自行設(shè)計(jì)，也可參考有關(guān)程序（屆時(shí)在網(wǎng)上提供）。這些工作有不小的工作量。（5）最優(yōu)決策功能模塊（fast or province）=1讀入城市信息和交通信息，用鄰接表生成含權(quán)網(wǎng)絡(luò)，表頭數(shù)組中的元素存放城市名及對(duì)方城 市到達(dá)該元素所代表城市的所有信息：表頭數(shù)組中的元素所對(duì)應(yīng)的單鏈表存放與該元素所代表的城 市有交通聯(lián)系的城市（代碼、里程、航班、列車車次）。2根據(jù)具體最優(yōu)決策的要求，用Dijkstra法求出岀發(fā)城市到其它各城市的最優(yōu)值（最短時(shí)間 或最小的費(fèi)用），

19、搜索過程中所經(jīng)過城市的局部最優(yōu)信息都保存在鄰接表的表頭數(shù)組中。其目的城市 所代表的元素中就保存了所需的最優(yōu)決策結(jié)果。這過程中，要用隊(duì)列或棧保存局部最優(yōu)決策值（局部 最短的時(shí)間或最省的費(fèi)用）變小的城市，其相應(yīng)的初始值可為 8,并在表頭數(shù)組對(duì)應(yīng)的城市元素中保 存響應(yīng)的信息。開始時(shí)，棧（隊(duì)）中只有岀發(fā)地城市，隨著對(duì)棧（隊(duì)）頂（首）城市有交通聯(lián)系的城市求 得決策值（最短時(shí)間或最小的費(fèi)用），若該值是局部最優(yōu)值且該城市不在棧（隊(duì)）中，則進(jìn)棧（隊(duì)），直 至棧（隊(duì)）為空。3輸岀結(jié)果。從目的城市出發(fā)，搜索到出發(fā)城市，所經(jīng)過的城市均入棧，再逐一出棧棧中的城 市，輸出保存在表頭數(shù)組中對(duì)應(yīng)城市的信息（對(duì)方城市的出發(fā)信

20、息，里程、時(shí)間、費(fèi)用等）及最終結(jié) 果。即輸出依次于何時(shí)何地乘坐幾點(diǎn)的飛機(jī)或火車于何時(shí)到達(dá)何地：最終所需的最快需要多長(zhǎng)時(shí)間 才能到達(dá)及旅費(fèi)，或者最少需要多少旅費(fèi)才能到達(dá)及時(shí)間。（6）主程序可以有系統(tǒng)界面、菜單：也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運(yùn) 行過程中可以反復(fù)操作。測(cè)試數(shù)據(jù)：飛機(jī)最快到達(dá)咨詢：北京到烏魯木齊，北京11點(diǎn)出發(fā)：火車最快到達(dá)咨詢：廣州到哈爾濱，廣州10點(diǎn)出發(fā)：飛機(jī)最省錢到達(dá)咨詢：烏魯木齊到南京，烏魯木齊12點(diǎn)出發(fā)：火車最省錢到達(dá)咨詢：沈陽到杭州，沈陽12點(diǎn)出發(fā)：五課程設(shè)計(jì)考核標(biāo)準(zhǔn)考核時(shí)主要有如下兒項(xiàng)參考：1.初步設(shè)計(jì)內(nèi)容的考核：是否有查閱資料能力？是否有設(shè)計(jì)思想？2

21、.程序編碼能力調(diào)試能力的考核：程序是否清晰、易讀？在技算計(jì)上是否可獨(dú) 立完成程序的調(diào)試，是否熟練？3.4.六設(shè)訃結(jié)束后要寫出課程設(shè)計(jì)報(bào)告，以作為整個(gè)課程設(shè)計(jì)評(píng)分的書面依據(jù)和存檔材料. 設(shè)計(jì)報(bào)告以規(guī)定專用課程設(shè)計(jì)報(bào)告書來寫，版面整潔，圖，表要清楚，工整正文包括以下12個(gè)內(nèi)容：1.設(shè)訃U的2.設(shè)計(jì)內(nèi)容與要求3.課題分析：以無歧義的陳述說明程序設(shè)訃的任務(wù),強(qiáng)調(diào)的是程序要做什么，需要 什么結(jié)果、所能達(dá)到的功能-4.算法思想：闡述要達(dá)到課題分析功能準(zhǔn)備采用的算法思路。例如：本程序是掃描一個(gè)C源程序,有Hash表存儲(chǔ)程序中出現(xiàn)的關(guān)鍵字,并統(tǒng)汁該程序中的關(guān)鍵字 岀現(xiàn)的頻度。用線性探測(cè)法解決Hash沖突。設(shè)H

22、ash函數(shù)為:Hash (key) =(key的第一個(gè)字母序 號(hào))*100+ (Xey的最后一個(gè)字母序號(hào))J MOD 4i。算法思想如下:建立一個(gè)結(jié)構(gòu)體數(shù)組的hash表,存放讀入的關(guān)鍵字和其出現(xiàn)的次數(shù)。先初始化并建立該hash表,先初始化為”0 ,0,再?gòu)奈募幸粋€(gè)個(gè)讀入所有關(guān)鍵字,存放在hash表中相應(yīng)位宜。從坍一文件中一行行讀入,找出其中非注釋中的也非中的,長(zhǎng)度2 8個(gè)字符的小寫字 符串,用hash查找,看該單詞是否關(guān)鍵字,如是其出現(xiàn)次數(shù)加一， 若不是就繼續(xù)下一個(gè)這樣的字符串,直至文件尾。崔找這樣的字符串途中,遇到無法匹配的單或雙引號(hào)打印出出現(xiàn)在第幾行。Hash表建立好后打印出來。其中核心

23、算法分為兩塊:1. hash表的建立和hash査找。2.尋找上述的字符串。Z建立Hash表的算法:該函數(shù)實(shí)參為已建立的hash表和住。源程序中找到的一個(gè)小寫字母字符串。該字符串key為下標(biāo)處依次開始查找,到數(shù)組末尾是返回?cái)?shù)組頭(kcy= (key+1) U4;),分兩種 情況:1若先找到空位,說明該字符串不是關(guān)鍵字。則不改變hash表。2若先找到了該關(guān)鍵字的紀(jì)錄,則該字符串是關(guān)鍵字,Khash處y num：2尋找疑似關(guān)鍵字字符串的算法說明書質(zhì)量的考核：設(shè)計(jì)結(jié)構(gòu)是否合理？敘述是否正確？方案是否可行? 答辯：設(shè)計(jì)結(jié)果的調(diào)試能力，對(duì)自己設(shè)計(jì)是否熟練？課程設(shè)計(jì)報(bào)告的內(nèi)容功能:依次找出被非標(biāo)識(shí)符且非 、

24、/*/隔開的,長(zhǎng)度為2 8個(gè)字符、非注釋中的.也非 中的小寫字母字符串,因?yàn)樗赡苁顷P(guān)鍵字。粧選粧選首先,一行行讀入C源程序,用續(xù)行符柑連的幾行當(dāng)一行一起讀入。（1）.casecase0和case 1：雙引號(hào)中的不算,跳過。（T）“”匹配中，“”不算.“II像2單引號(hào)中的戲引號(hào)不算,而且單引號(hào)中不會(huì)有關(guān)鍵字,所以單引號(hào)中的也跳過。3匹配中,T不算,Tl韋、case 2：注釋中的不算,跳過。分為/*/ /1設(shè)一個(gè)標(biāo)志符找到/*但在該行沒找到*/時(shí),滬1;此時(shí)隹下行中尋找*/ ,以此 類推,直至找到*/后“薩0,以后字符恢復(fù)有效。2當(dāng)找到時(shí)放棄該行之后的所有字符,讀入下一行（3）、case 3：讀

25、到大寫字母、下劃線或數(shù)字時(shí),肯定該字符串不是關(guān)鍵字,則淸除已存在s中的 字符串,井跳過緊接宦后而的允許在標(biāo)識(shí)符中岀規(guī)的字符。4:讀到的是小寫字碌,則存放到字符串S中。case 5：本算法以除“，、/、/*、*/之外的不能在標(biāo)識(shí)符中出現(xiàn)的字符隔開整行字符串, 并判斷被隔開的長(zhǎng)度2-8個(gè)字符,不含大寫字母、下劃線、數(shù)字的字符串（即小寫字母字符串）是 否關(guān)鍵字,是則増加其統(tǒng)計(jì)個(gè)數(shù)（判斷方法為hash査找）。5.概要設(shè)計(jì)：說明本程序中用到的所有抽象數(shù)據(jù)類型的定義,主程序的流程以及各 程序模塊之間的層次（調(diào)用）關(guān)系.包括數(shù)據(jù)結(jié)構(gòu)定義、程序結(jié)構(gòu)、界面設(shè)計(jì)。例如：（1）數(shù)據(jù)結(jié)構(gòu)定義struct edgeno

26、defII定義鄰接表的邊結(jié)點(diǎn)類型(4) case、int adjvex;該弧所指向的頂點(diǎn)的位置edgenocie * next;指向下條條弧的指針定義鄰接表類型typedef edgenode * * adjUst：(2)程序結(jié)構(gòu)粧選EqualO粧選如圖,main 0函數(shù)調(diào)用 了PQ個(gè)子函數(shù),chu_shi_hash 0、crcatc_hash ()、Gusn_Jian_Zi ()、print 0其中,chii_shi_hashO把hash表初始化為“0000 0,標(biāo)記空位,便于U后操作。C creatjhashO實(shí)規(guī)hash表的創(chuàng)建,從放關(guān)鍵字的文件一個(gè)個(gè)關(guān)鍵字,它調(diào)用了兩個(gè)子函數(shù),equa

27、l ()判斷兩數(shù)組是否相等，用來確定某處是否空位.copyO把一個(gè)數(shù)組賦給另一數(shù)組、隹確定插入 位這插入該關(guān)鍵字。Guan_Jian_Zi()從C源程序中依次找到可能是關(guān)鍵字的字符串,然后用hash查找判斷它是否 關(guān)鍵字,是則增加其統(tǒng)汁次數(shù)。它調(diào)用了兩個(gè)子函數(shù):PanDuan (char)和chang_hash (Hash,const char ch J),前者用來判斷一個(gè)字符的的類別,后者在hash表中査找判斷ch是否關(guān)鍵字,是則 增加其在hash表中的統(tǒng)汁量。而chandhash ()調(diào)用了函數(shù)equal 0,用來確定某處是否空位或ch .print (bash)用來打印hash表界而設(shè)計(jì)

28、(略)6.詳細(xì)設(shè)計(jì):進(jìn)一步細(xì)化概要設(shè)計(jì)中定義的各模塊或函數(shù)功能，畫出算法實(shí)現(xiàn)流程 圖-7.測(cè)試數(shù)據(jù)定義：定義典型的測(cè)試輸入數(shù)據(jù)，包括各種體現(xiàn)課設(shè)正常功能的數(shù)據(jù), 也包括各種異常測(cè)試數(shù)據(jù)。測(cè)試數(shù)據(jù)應(yīng)與課題分析所要求的U標(biāo)一致。&源碼：打印9.測(cè)試結(jié)果：打印例如：錨A圖的頂點(diǎn)數(shù)M M新、是否!2!Ul!-!-!2!-!-!1!-!-!1!1 1 : :U2rU2r- -13!*!13!*!3 3 !U4!-!-!eri!U4!-!-!eri目的深應(yīng) ft 無M 歷序列：1313 4 4 2 2歷序列1313 2 2 4 4將選2 2 !U3!-!U3!-10.算法分析：算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù) 雜度的分析)和改進(jìn)設(shè)想；12使用說明：13.總結(jié)與體會(huì)：要寫出自己的真實(shí)感受。例如一：轉(zhuǎn)眼,為期兩周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(xí)中,自己的C語言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固,編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解 決問題的方法。總結(jié)起來,自己主要有以下兒點(diǎn)體會(huì):1必須牢固掌握基礎(chǔ)知識(shí)。山于C語言是大一所學(xué)知識(shí),有所遺忘,且未掌握好這 學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)這門課,所以在實(shí)習(xí)之初感到棘手。不知如何下手,但在后來 的實(shí)習(xí)過程中自己通過看書和課外資料,