數(shù)據(jù)結(jié)構(gòu)編程實(shí)驗(yàn)

前言

前言我們長(zhǎng)期從事數(shù)據(jù)結(jié)構(gòu)教學(xué)和競(jìng)賽培訓(xùn)，教學(xué)實(shí)踐使我們萌發(fā)了對(duì)數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)模式進(jìn)行改革的想法：  1）在課程中需要增加思維方式和解題策略的引導(dǎo)，引導(dǎo)學(xué)生思考各類數(shù)據(jù)結(jié)構(gòu)的本質(zhì)特征是什么；面對(duì)當(dāng)前問(wèn)題為什么要采用這樣的數(shù)據(jù)結(jié)構(gòu)而不宜采用那樣的數(shù)據(jù)結(jié)構(gòu)；當(dāng)有多個(gè)數(shù)據(jù)結(jié)構(gòu)可用時(shí)，怎樣權(quán)衡時(shí)間復(fù)雜度、空間復(fù)雜度、編程復(fù)雜度和思維復(fù)雜度四個(gè)因素，尋找最合時(shí)宜的數(shù)據(jù)結(jié)構(gòu)，將“知識(shí)導(dǎo)向”與“智慧導(dǎo)向”真正結(jié)合起來(lái)。 2）在課程中需要引入案例教學(xué)，通過(guò)模擬或者重現(xiàn)現(xiàn)實(shí)生活中的一些場(chǎng)景，讓學(xué)生置身問(wèn)題情境之中，通過(guò)思考、討論和上機(jī)編程來(lái)進(jìn)行學(xué)習(xí)。傳統(tǒng)教學(xué)將數(shù)據(jù)結(jié)構(gòu)“束之高閣”，在理論教學(xué)和筆試上兜來(lái)兜去，可能會(huì)使學(xué)生渾然不知數(shù)據(jù)結(jié)構(gòu)在現(xiàn)實(shí)生活中究竟派什么用處，懵懵懂懂，最終失去了學(xué)習(xí)的意義?！凹埳系脕?lái)終覺(jué)淺，絕知此事要躬行”。案例教學(xué)則是一種以問(wèn)題和動(dòng)手編程驅(qū)動(dòng)學(xué)習(xí)的方式：將知識(shí)置于問(wèn)題情境和實(shí)踐過(guò)程之中，變枯燥乏味為生動(dòng)活潑。學(xué)生拿到試題后，先進(jìn)行審題，然后溫習(xí)或查閱各種他認(rèn)為必要的數(shù)據(jù)結(jié)構(gòu)知識(shí)，這無(wú)形中激發(fā)了他們的求知欲望，加深了他們對(duì)知識(shí)真諦的理解。捕捉到相關(guān)的理論知識(shí)后，學(xué)生還要經(jīng)過(guò)縝密思考和動(dòng)手編程，使之變?yōu)榻鉀Q問(wèn)題的程序方案。這個(gè)“認(rèn)識(shí)-實(shí)踐-再認(rèn)識(shí)-再實(shí)踐”的過(guò)程，應(yīng)視為知識(shí)理解上的一種提高，知識(shí)學(xué)習(xí)與應(yīng)用能力間的一種轉(zhuǎn)變和升華。  基于上述想法，我們近年來(lái)開(kāi)設(shè)了“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)”課程，并將ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽和其他程序設(shè)計(jì)競(jìng)賽中的典型試題分門別類，精選了其中204道試題，翻譯后作為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)的實(shí)驗(yàn)案例。這些試題不僅為相關(guān)知識(shí)創(chuàng)設(shè)了豐富有趣的問(wèn)題背景，而且在相關(guān)網(wǎng)站上都有試題的在線測(cè)試。學(xué)生不僅可以帶著問(wèn)題學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，而且所編程序的正確性和效率也可以通過(guò)相關(guān)網(wǎng)站上的測(cè)試系統(tǒng)得到實(shí)時(shí)檢驗(yàn)，達(dá)到“學(xué)以致用”的目的。……

內(nèi)容概要

　　本書(shū)以知識(shí)體系結(jié)構(gòu)和思維方式兩個(gè)方面作為主線，分成四大篇14章介紹了基本編程能力的實(shí)驗(yàn)（基礎(chǔ)）、線性數(shù)據(jù)結(jié)構(gòu)的編程實(shí)驗(yàn)（線性表）、層次類非線性表的編程實(shí)驗(yàn)（樹(shù)）以及群聚類非線性表的編程實(shí)驗(yàn)（圖），并將“排序”和“搜索”的內(nèi)容融合到相關(guān)章節(jié)中。每章節(jié)由實(shí)驗(yàn)范例和題庫(kù)兩個(gè)部分組成，試題全部選自ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽和其他程序設(shè)計(jì)競(jìng)賽，共204題，并給出了試題來(lái)源和在線測(cè)試地址。每個(gè)實(shí)驗(yàn)范例不僅有詳盡的知識(shí)要點(diǎn)闡述和試題解析，而且列出了寫有詳細(xì)注釋的參考程序；而題庫(kù)中的所有試題無(wú)論難易，都有清晰的提示。該書(shū)還附帶了存儲(chǔ)所有試題的英文原版描述和大部分試題的測(cè)試數(shù)據(jù)等資料的光盤。
　　本書(shū)的實(shí)驗(yàn)范例部分可以作為程序設(shè)計(jì)語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)教材，供大學(xué)教學(xué)使用；題庫(kù)部分則可以作為計(jì)算機(jī)專業(yè)學(xué)生的研修資料和程序設(shè)計(jì)競(jìng)賽的培訓(xùn)教材。

作者簡(jiǎn)介

　　吳永輝 博士，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系副教授，ACM-ICPC中國(guó)賽區(qū)指導(dǎo)委員會(huì)（ACM-ICPC Council
China）成員，復(fù)旦大學(xué)ACM程序設(shè)計(jì)競(jìng)賽隊(duì)教練。作者自2001年起連續(xù)帶隊(duì)進(jìn)入ACM-ICPC世界總決賽，并取得過(guò)世界第6名的佳績(jī)。他的主要研究方向?yàn)閿?shù)據(jù)庫(kù)，在《計(jì)算機(jī)研究與發(fā)展》、《軟件學(xué)報(bào)》以及重大學(xué)術(shù)會(huì)議上發(fā)表過(guò)多篇論文，參與翻譯出版了《數(shù)據(jù)通信與網(wǎng)絡(luò)》和《數(shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)與開(kāi)放系統(tǒng)》。
　　王建德，著名的信息學(xué)奧林匹克競(jìng)賽金牌教練，國(guó)務(wù)院特殊津貼專家，中學(xué)特級(jí)教師。他所輔導(dǎo)的學(xué)生在國(guó)際奧林匹克信息學(xué)競(jìng)賽（IOI）中獲7金、3銀、2銅的優(yōu)異成績(jī)，先后出版了24本關(guān)于程序設(shè)計(jì)和算法的學(xué)術(shù)專著，其中《實(shí)用算法的分析與程序設(shè)計(jì)》廣受好評(píng)，長(zhǎng)期以來(lái)是國(guó)內(nèi)各類程序設(shè)計(jì)競(jìng)賽的必備教程。
　　ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（簡(jiǎn)稱ACM／ICPC）是由美國(guó)計(jì)算機(jī)協(xié)會(huì)(ACM)主辦的國(guó)際性大學(xué)生計(jì)算機(jī)學(xué)科競(jìng)賽，創(chuàng)辦于1977年，競(jìng)賽以大學(xué)為單位，3人一隊(duì)，先在各大洲進(jìn)行各級(jí)預(yù)選賽，從中選拔優(yōu)勝隊(duì)參加全球總決賽。ACM／ICPC目前已經(jīng)成為全世界范圍內(nèi)歷時(shí)久遠(yuǎn)、規(guī)模宏大、影響最大的權(quán)威性的大學(xué)生程序設(shè)計(jì)競(jìng)賽。

書(shū)籍目錄

前言
第一篇　 基本能力的編程實(shí)驗(yàn)
　第1章　 簡(jiǎn)單計(jì)算的編程實(shí)驗(yàn)
　　1.1　 改進(jìn)程序書(shū)寫風(fēng)格的實(shí)驗(yàn)范例
　　1.2　 正確處理多組測(cè)試數(shù)據(jù)的實(shí)驗(yàn)范例
　　1.3　 提高實(shí)數(shù)精度的實(shí)驗(yàn)范例
　　1.4　 使用二分法提高計(jì)算時(shí)效的實(shí)驗(yàn)范例
　　1.5　 相關(guān)題庫(kù)
　第2章　 簡(jiǎn)單模擬的編程實(shí)驗(yàn)
　　2.1　 直敘式模擬的實(shí)驗(yàn)范例
　　2.2　 篩選法模擬的實(shí)驗(yàn)范例
　　2.3　 構(gòu)造法模擬的實(shí)驗(yàn)范例
　　2.4　 相關(guān)題庫(kù)
　第3章　 簡(jiǎn)單遞歸的編程實(shí)驗(yàn)
　　3.1　 計(jì)算遞歸函數(shù)的實(shí)驗(yàn)范例
　　3.2　 用遞歸算法求問(wèn)題解的實(shí)驗(yàn)范例
　　3.3　 求解遞歸數(shù)據(jù)的實(shí)驗(yàn)范例
　　3.4　 相關(guān)題庫(kù)
　本篇小結(jié)
第二篇　 線性數(shù)據(jù)結(jié)構(gòu)的編程實(shí)驗(yàn)
　第4章　 應(yīng)用直接存取類線性表編程
　　4.1　 數(shù)組應(yīng)用一：日期計(jì)算的實(shí)驗(yàn)范例
　　4.2　 數(shù)組應(yīng)用二：高精度運(yùn)算的實(shí)驗(yàn)范例
　　4.3　 數(shù)組應(yīng)用三：多項(xiàng)式表示與處理的實(shí)驗(yàn)范例
　　4.4　 數(shù)組應(yīng)用四：數(shù)值矩陣運(yùn)算的實(shí)驗(yàn)范例
　　4.5　 字符串處理一：串的存儲(chǔ)結(jié)構(gòu)的實(shí)驗(yàn)范例
　　4.6　 字符串處理二：串模式匹配的實(shí)驗(yàn)范例
　　4.7　 相關(guān)題庫(kù)
　第5章　 應(yīng)用順序存取類線性表編程
　　5.1　 順序表應(yīng)用的實(shí)驗(yàn)范例
　　5.2　 棧應(yīng)用的實(shí)驗(yàn)范例
　　5.3　 隊(duì)列應(yīng)用的實(shí)驗(yàn)范例
　　5.4　 相關(guān)題庫(kù)
　第6章　 應(yīng)用廣義索引類線性表編程
　　6.1　 使用詞典解題的實(shí)驗(yàn)范例
　　6.2　 使用散列表與散列方法解題的實(shí)驗(yàn)范例
　　6.3　 相關(guān)題庫(kù)
　第7章　 應(yīng)用線性表排序編程
　　7.1　 利用STL中自帶的排序功能編程的實(shí)驗(yàn)范例
　　7.2　 應(yīng)用排序算法編程的實(shí)驗(yàn)范例
　　7.3　 相關(guān)題庫(kù)
　本篇小結(jié)
第三篇　 層次類非線性表的編程實(shí)驗(yàn)
　第8章　 采用樹(shù)結(jié)構(gòu)的非線性表編程
　　8.1　 用樹(shù)的遍歷求解層次性問(wèn)題的實(shí)驗(yàn)范例
　　8.2　 用樹(shù)結(jié)構(gòu)支持并查集的實(shí)驗(yàn)范例
　　8.3　 用樹(shù)狀數(shù)組統(tǒng)計(jì)子樹(shù)權(quán)和的實(shí)驗(yàn)范例
　　8.4　 相關(guān)題庫(kù)
　第9章　 應(yīng)用二叉樹(shù)的基本概念編程
　　9.1　 普通有序樹(shù)轉(zhuǎn)化為二叉樹(shù)的實(shí)驗(yàn)范例
　　9.2　 計(jì)算二叉樹(shù)路徑的實(shí)驗(yàn)范例
　　9.3　 通過(guò)遍歷確定二叉樹(shù)結(jié)構(gòu)的實(shí)驗(yàn)范例
　　9.4　 相關(guān)題庫(kù)
　第10章　 應(yīng)用經(jīng)典二叉樹(shù)編程
　　10.1　 二叉搜索樹(shù)的實(shí)驗(yàn)范例
　　10.2　 二叉堆的實(shí)驗(yàn)范例
　　10.3　 哈夫曼樹(shù)的實(shí)驗(yàn)范例
　　10.4　 相關(guān)題庫(kù)
　本篇小結(jié)
第四篇　 群聚類非線性表的編程實(shí)驗(yàn)
　第11章　 應(yīng)用圖的遍歷算法編程
　　11.1　 BFS算法的實(shí)驗(yàn)范例
　　11.2　 DFS算法的實(shí)驗(yàn)范例
　　11.3　 拓?fù)渑判虻膶?shí)驗(yàn)范例
　　11.4　 計(jì)算無(wú)向圖的連通性的實(shí)驗(yàn)范例
　　11.5　 相關(guān)題庫(kù)
　第12章　 應(yīng)用最小生成樹(shù)算法編程
　　12.1　 Kruskal算法的實(shí)驗(yàn)范例
　　12.2　 Prim算法的實(shí)驗(yàn)范例
　　12.3　 相關(guān)題庫(kù)
　第13章　 應(yīng)用最佳路徑算法編程
　　13.1　 Warshall算法和Floyed-Warshall算法的實(shí)驗(yàn)范例
　　13.2　 Dijkstra算法的實(shí)驗(yàn)范例
　　13.3　 Bellman-Ford算法的實(shí)驗(yàn)范例
　　13.4　 SPFA算法的實(shí)驗(yàn)范例
　　13.5　 相關(guān)題庫(kù)
　第14章　 應(yīng)用特殊圖的經(jīng)典算法編程
　　14.1　 二分圖匹配的實(shí)驗(yàn)范例
　　14.2　 計(jì)算網(wǎng)絡(luò)最大流的實(shí)驗(yàn)范例
　　14.3　 相關(guān)題庫(kù)
　本篇小結(jié)

章節(jié)摘錄

版權(quán)頁(yè)：3.2用遞歸算法求問(wèn)題解的實(shí)驗(yàn)范例如果問(wèn)題給出了初始狀態(tài)、目標(biāo)狀態(tài)，且擴(kuò)展子狀態(tài)的規(guī)則和約束條件同一的話，則可以使用遞歸算法找出一個(gè)由初始狀態(tài)至目標(biāo)狀態(tài)的求解方案。使用遞歸算法需要注意幾個(gè)問(wèn)題：怎樣將求解過(guò)程中每一步的狀況組合成值參或局部變量，以便回溯時(shí)能恢復(fù)遞歸前的狀態(tài)。若這些參數(shù)的存儲(chǔ)量大（例如數(shù)組）且初始值需由主程序傳入，為避免內(nèi)存溢出，則必須將其設(shè)為全局變量，且回溯前需恢復(fù)其遞歸前的值。  確定邊界條件，即程序在什么情況下不再遞歸下去。確定搜索的范圍和約束條件，即在當(dāng)前狀態(tài)未達(dá)邊界的情況下，在什么范圍內(nèi)擴(kuò)展子狀態(tài)，這些子狀態(tài)應(yīng)滿足什么條件方可繼續(xù)遞歸下去。上述遞歸算法簡(jiǎn)稱回溯法。實(shí)際上這種方法與第四篇中圖的深度優(yōu)先搜索本質(zhì)上是一致的，只不過(guò)深度優(yōu)先搜索一般用于現(xiàn)成的顯式圖，而回溯法一般用于遞歸問(wèn)題的求解，兩者都是采用縱深搜索的遞歸策略?！?.2.1Red and Black】有一個(gè)矩形房間，覆蓋正方形瓷磚。每塊瓷磚涂成了紅色或黑色。一名男子站在黑色的瓷磚上，由此出發(fā)，可以移到四個(gè)相鄰瓷磚之一，但他不能移動(dòng)到紅磚上，只能移動(dòng)到黑磚上。編寫一個(gè)程序，計(jì)算他通過(guò)重復(fù)上述移動(dòng)所能經(jīng)過(guò)的黑磚數(shù)。輸入輸入包含多個(gè)數(shù)據(jù)集。一個(gè)數(shù)據(jù)集開(kāi)頭行包含兩個(gè)正整數(shù)W和H，W和H分別表示矩形房間的列數(shù)和行數(shù)，且都不超20。每個(gè)數(shù)據(jù)集有H行，其中每行包含W個(gè)字符。每個(gè)字符的含義如下所示：'. '—黑磚；'#'—紅磚；'@'—男子（每個(gè)數(shù)據(jù)集僅出現(xiàn)一次）。兩個(gè)0表示輸入結(jié)束。輸出對(duì)每個(gè)數(shù)據(jù)集，程序應(yīng)該輸出一行，包含男子從初始瓷磚出發(fā)可到達(dá)的瓷磚數(shù)。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)編程實(shí)驗(yàn):大學(xué)程序設(shè)計(jì)課程與競(jìng)賽訓(xùn)練教材》編輯推薦：204道試題全部從ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽和其他程序設(shè)計(jì)競(jìng)賽中精選而出，并給出詳盡試題解析。由淺入深、循序漸進(jìn)地引入基本能力、線性表、樹(shù)、圖的編程實(shí)驗(yàn)，同時(shí)注重從思維方式上歷練讀者的編程能力。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)編程實(shí)驗(yàn) PDF格式下載

---