數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)

前言

在聯(lián)合國(guó)教科文組織的倡導(dǎo)下，自1989年至今國(guó)際信息學(xué)奧林匹克學(xué)科競(jìng)賽（IOI）已經(jīng)舉辦了21屆。在世界各國(guó)青少年優(yōu)秀選手競(jìng)展雄姿的舞臺(tái)上，中國(guó)代表隊(duì)?wèi)?zhàn)績(jī)輝煌。與.IOI同步的全國(guó)青少年信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP）的開展，提高了我國(guó)青少年的科學(xué)素養(yǎng)，促進(jìn)了信息科技活動(dòng)的普及，選拔出了大量的計(jì)算機(jī)拔尖人才，受到了眾多信息學(xué)愛好者的關(guān)注。目前在競(jìng)賽中多數(shù)選手選用Pascal語(yǔ)言。Pascal語(yǔ)言功能強(qiáng)大，數(shù)據(jù)類型豐富，程序結(jié)構(gòu)嚴(yán)謹(jǐn)，便于閱讀和理解。應(yīng)用Pascal語(yǔ)言程序設(shè)計(jì)求解問題，核心是數(shù)據(jù)結(jié)構(gòu)和算法的整合。因此，系統(tǒng)地研究數(shù)據(jù)結(jié)構(gòu)和算法，將會(huì)使選手的編程技能如虎添翼。在目前的圖書市場(chǎng)上，有關(guān)Pascal語(yǔ)言數(shù)據(jù)結(jié)構(gòu)和算法的競(jìng)賽輔導(dǎo)教材極少，而且其中一些是寫給大學(xué)生的，不適合中小學(xué)生閱讀。為了幫助中小學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)，特聘請(qǐng)具有豐富競(jìng)賽輔導(dǎo)經(jīng)驗(yàn)的一線教師和曾在國(guó)際信息學(xué)奧賽中獲得金牌的優(yōu)秀選手共同編寫了這本書。本書是Pascal語(yǔ)言（小學(xué)版）和Pascal語(yǔ)言（中學(xué)版）的后繼教材，內(nèi)容緊扣信息學(xué)競(jìng)賽大綱，結(jié)構(gòu)嚴(yán)謹(jǐn)，語(yǔ)言簡(jiǎn)練。希望本書能為提高讀者競(jìng)賽技藝奉獻(xiàn)綿薄之力。本書第1版自2006年出版至今，受到廣大讀者的關(guān)注和厚愛，在此深表謝意。近年來，：FreePascal語(yǔ)言已替代turboPascal語(yǔ)言成為我國(guó)青少年信息學(xué)奧林匹克競(jìng)賽（NOI）和分區(qū)聯(lián)賽（NOIP）的復(fù)賽語(yǔ)言之一。為了適應(yīng)競(jìng)賽的需要，我們對(duì)書中內(nèi)容進(jìn)行了修訂。第2版中增加了隊(duì)列、棧、數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用和貪心法4章，所有的例題和習(xí)題均能在FreePascal環(huán)境中運(yùn)行。這本書的內(nèi)容共分14章，主要內(nèi)容包括：數(shù)據(jù)結(jié)構(gòu)與算法的引入、隊(duì)列、棧、樹、圖、數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用、排列和組合、、高精度計(jì)算、排序法、搜索策略、分治策略、貪心法、動(dòng)態(tài)規(guī)劃和算法的綜合應(yīng)用等。具體編寫分工如下：第l、6章由李文編寫，第2章由安文君編寫，第3章由劉萍萍編寫，第4章由張文雙編寫，第5章由王學(xué)紅編寫，第7章由戰(zhàn)久成編寫，第8、13章由郭連鳳編寫，第9章由周敏編寫，第10章由王宇編寫，第11章由楊偉編寫，第12章由王亞平編寫，第14章由侯啟明編寫。全書由張文雙統(tǒng)稿審定。由于編者的水平有限，新版中若有疏漏之處，懇請(qǐng)各位讀者指正。

內(nèi)容概要

目前在競(jìng)賽中多數(shù)選手選用Pascal語(yǔ)言。Pascal語(yǔ)方功能強(qiáng)大，數(shù)據(jù)類型豐富，程序結(jié)構(gòu)嚴(yán)謹(jǐn)，便于閱讀和理解。應(yīng)用Pascal語(yǔ)言程序設(shè)計(jì)求解問題，核心是數(shù)據(jù)結(jié)構(gòu)和算法的整合。因此，系統(tǒng)研究數(shù)據(jù)結(jié)構(gòu)和算法，編程技能將如虎添翼。    在目前的圖書市上，有關(guān)Pascal語(yǔ)言數(shù)據(jù)結(jié)構(gòu)和算法的競(jìng)賽輔導(dǎo)教材極少。見到一些是寫給大學(xué)生，不適合中小學(xué)生閱讀。為了幫助中小學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)，特聘請(qǐng)具有豐富競(jìng)賽輔導(dǎo)經(jīng)驗(yàn)的一線教師和曾在國(guó)際信息學(xué)奧林匹克學(xué)科競(jìng)賽中獲得金牌的優(yōu)秀選手共同編寫了這本書。本書是Pascal語(yǔ)言（小學(xué)版）和Pascal語(yǔ)言（中學(xué)版）的后繼教材，內(nèi)容緊扣信息學(xué)競(jìng)賽大綱，結(jié)構(gòu)嚴(yán)謹(jǐn)，語(yǔ)言簡(jiǎn)練，希望它難為讀者提高競(jìng)賽技藝奉獻(xiàn)綿薄之力。

作者簡(jiǎn)介

　　吳文虎，清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系教授、博士生導(dǎo)師，國(guó)際信息學(xué)奧林匹克競(jìng)賽中國(guó)隊(duì)總教練。　　自1989年以來一直擔(dān)任國(guó)際信息學(xué)奧林匹克競(jìng)賽中國(guó)隊(duì)的總教練，帶領(lǐng)中國(guó)國(guó)家隊(duì)在國(guó)際信息學(xué)奧林匹克競(jìng)賽中連續(xù)15年取得輝煌戰(zhàn)績(jī)！

書籍目錄

第1章 數(shù)據(jù)結(jié)構(gòu)與算法的引入  1.1 數(shù)據(jù)結(jié)構(gòu)的概念  1.2 算法  1.3 建立數(shù)學(xué)模型  1.4 程序的調(diào)試  習(xí)題及參考答案第2章 指針和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)  2.1 指針變量的定義及基本使用  2.2 鏈表  習(xí)題及參考答案第3章 文件  3.1 文本文件的邏輯組織  3.2 文本文件的基本操作  3.3 文本文件應(yīng)用舉例  習(xí)題及參考答案第4章 樹  4.1 樹的概念  4.2 二叉樹  4.3 樹的存儲(chǔ)結(jié)構(gòu)  4.4 樹的遍歷  4.5 最優(yōu)二叉樹  習(xí)題及參考答案第5章 圖  5.1 圖的概念  5.2 圖的遍歷  5.3 圖的最短路  5.4 最小生成樹  5.5 圖的應(yīng)用  習(xí)題及參考答案第6章 排列和組合  6.1 加法原理和乘法原理  6.2 排列  6.3 組合  習(xí)題及參考答案第7章 高精度計(jì)算  7.1 高精度基本計(jì)算  7.2 高精度計(jì)算的優(yōu)化  習(xí)題及參考答案第8章 排序法  8.1 插入排序  8.2 希爾排序  8.3 選擇排序  8.4 冒泡排序  8.5 快速排序  8.6 堆排序  8.7 基數(shù)排序（多關(guān)鍵字排序）  8.8 各種內(nèi)部排序方法的比較  習(xí)題及參考答案第9章 搜索策略  9.1 搜索的基本知識(shí)  9.2 窮舉搜索  9.3 回溯搜索  9.4 廣度優(yōu)先搜索  9.5 分支定界  習(xí)題及參考答案第10章 分治策略  10.1 分治原理  10.2 二分法  10.3 遞推法的分治處理  習(xí)題及參考答案第11章 動(dòng)態(tài)規(guī)劃  11.1 動(dòng)態(tài)規(guī)劃的基本思想  11.2 動(dòng)態(tài)規(guī)劃的進(jìn)一步討論  11.3 記憶化搜索的應(yīng)用  習(xí)題及參考答案第12章 算法的綜合應(yīng)用附錄  附錄1 編譯器開關(guān)表  附錄2 Free Pascal和Turbo Pascal的主要區(qū)別

章節(jié)摘錄

插圖：1.2.1 算法的特點(diǎn)計(jì)算機(jī)算法大體可分為數(shù)值計(jì)算和非數(shù)值計(jì)算兩大類。比如求若干個(gè)數(shù)之和、求方程的根、求n！等，都屬于數(shù)值計(jì)算類，而圖書檢索、按考試成績(jī)排列名次等則屬于非數(shù)值計(jì)算類。無論哪一類算法，也無論算法多么簡(jiǎn)單或多么復(fù)雜，都必須滿足以下特點(diǎn)：1.確定性算法的每一步都必須是明確無誤的，不能含糊其辭，不能存在歧義（具有二義性或多義性），否則就會(huì)使執(zhí)行者無所適從。如在算法中出現(xiàn)“計(jì)算3／0”或“將3或4與x相乘”等是不允許的，原因是前者的計(jì)算結(jié)果不確定，后者則無法確定究竟是哪個(gè)數(shù)與x相乘。2.有效性算法中的每一步運(yùn)算都必須能夠在計(jì)算機(jī)上有效地執(zhí)行，整個(gè)算法執(zhí)行完畢后必須得到確定的結(jié)果。例如求-5的平方根，求所有自然數(shù)的和，就無法在計(jì)算機(jī)上有效地執(zhí)行。3.有窮性一個(gè)算法必須包含有限個(gè)操作步驟，即執(zhí)行若干步之后，算法能夠終止，而不能無限地執(zhí)行下去。當(dāng)然，這種有窮性還應(yīng)該在一個(gè)合理的范圍之內(nèi)，比如一個(gè)算法要執(zhí)行10000年才能得到結(jié)果，盡管它不是無限的，但顯然沒有什么實(shí)際意義。4.輸入一個(gè)算法可以含有0個(gè)或多個(gè)輸入，用于提供算法執(zhí)行所需要的外界信息。5.輸出設(shè)計(jì)算法的目的是得到問題的解，所以一個(gè)算法應(yīng)包含一個(gè)或多個(gè)輸出，用于描述問題求解后所得的結(jié)果。比如求100個(gè)數(shù)中最大的數(shù)，算法執(zhí)行完畢應(yīng)該輸出最大的數(shù)。的算法

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì):Pascal語(yǔ)言(第2版)》：青少年信息雪奧林匹克競(jìng)賽培訓(xùn)教材

圖書封面

圖書標(biāo)簽Tags

無

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

---

    數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) PDF格式下載

---