數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類(lèi)型演示文稿

數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類(lèi)型演示文稿IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第1頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)（優(yōu)選）第一講數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類(lèi)型IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第2頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)回顧幾個(gè)相關(guān)概念數(shù)據(jù)類(lèi)型1++2…+,-,*,\intIOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第3頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)數(shù)據(jù)類(lèi)型的基本要件編碼方案運(yùn)算法則存儲(chǔ)空間定義IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第4頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)從數(shù)據(jù)抽象到數(shù)據(jù)關(guān)系抽象IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第5頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)存在唯一的一個(gè)被稱(chēng)做“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱(chēng)做“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有且僅有一個(gè)前驅(qū)元素；除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼元素。

線性結(jié)構(gòu)（代數(shù)定義）IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第6頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)線性結(jié)構(gòu)的具體實(shí)現(xiàn)TypedefintATypeATypea[20];AType*p=a;

p++;p[5]=9;…IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第7頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)線性結(jié)構(gòu)的另一種實(shí)現(xiàn)方案structNode{intINode*next;}typedefstructnodeNodetype;Nodetype*head;IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第8頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)數(shù)據(jù)結(jié)構(gòu)+算法=…structNode{inti;Node*next;};typedefstructNode*Queue;+intdeQueue(Queue);voidinQueue(Queue,int);…IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第9頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)初步設(shè)計(jì)思路IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第10頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)改進(jìn)的程序思路IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第11頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)進(jìn)一步改進(jìn)IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第12頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)抽象數(shù)據(jù)類(lèi)型（ADT）…FirstComeFirstService（queue）數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)InQueueDeQueueIsEmptyQueue對(duì)外操作接口結(jié)構(gòu)數(shù)據(jù)維護(hù)接口IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第13頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)算法與數(shù)據(jù)結(jié)構(gòu)

VS計(jì)算概論數(shù)據(jù)編碼與存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)與關(guān)系表達(dá)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型特定的算法與問(wèn)題求解算法求解思路的類(lèi)型化IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第14頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)函數(shù)VS抽象數(shù)據(jù)類(lèi)型函數(shù)f(i)

抽象數(shù)據(jù)類(lèi)型

數(shù)據(jù)及運(yùn)算、對(duì)象及服務(wù)基于服務(wù)的服務(wù)軟件

IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第15頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)算法+數(shù)據(jù)結(jié)構(gòu)線性表（棧、隊(duì)列）：鏈表、倒排表、hash表。二叉樹(shù)（堆）：排序樹(shù)、優(yōu)先隊(duì)列、表達(dá)式樹(shù)、AVL樹(shù)樹(shù)（索引）：深搜、廣搜圖（有向、無(wú)向、加權(quán)）：MST，最短路徑、關(guān)鍵路徑IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第16頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)算法與算法復(fù)雜度分治：快速排序貪心：Dijkstra動(dòng)態(tài)規(guī)劃（分階段貪心）：背包問(wèn)題搜索（回溯）:迷宮老鼠IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第17頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)擴(kuò)展的問(wèn)題求解最大相似問(wèn)題：回帖相似、詩(shī)歌相似復(fù)雜系統(tǒng)算法：生命游戲IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第18頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第19頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第20頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)課程的特點(diǎn)是關(guān)于世界觀、方法論的形式化描述以及可計(jì)算性的科學(xué)。是需要調(diào)整思維習(xí)慣和方式而非僅僅充實(shí)知識(shí)庫(kù)。一旦領(lǐng)會(huì)，終生受益。IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第21頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)建議的學(xué)習(xí)方案聽(tīng)課提問(wèn)上機(jī)討論睡覺(jué)IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第22頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)教材算法與數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言描述（第二版）張乃孝高等教育出版社教學(xué)參考：

MITOpencourseIntroductiontoAlgorithm課程網(wǎng)站：IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第23頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)課程教學(xué)團(tuán)隊(duì)任課教師：胡俊峰助教：

彭躍輝:

鄧昌明：

馬秀娟：

劉亮：

曲強(qiáng)：IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第24頁(yè)\共有26頁(yè)\編于星期五\0點(diǎn)課時(shí)的基本安排周二3-4

周四1-2（單周）上機(jī)周二11-12（第二周開(kāi)始）共16周，23次課。14項(xiàng)基礎(chǔ)知識(shí)內(nèi)容。3次POJ練習(xí)、解題討論。擴(kuò)展報(bào)告、大作業(yè)討論。IOI2009國(guó)家集訓(xùn)隊(duì)論文演示張昆瑋當(dāng)前第25頁(yè)\共有26頁(yè)\編于星期五