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

線性結(jié)構(gòu)（代數(shù)定義）IOI2009國家集訓(xùn)隊論文演示張昆瑋現(xiàn)在是6頁\一共有26頁\編輯于星期五線性結(jié)構(gòu)的具體實現(xiàn)TypedefintATypeATypea[20];AType*p=a;

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

VS計算概論數(shù)據(jù)編碼與存儲數(shù)據(jù)結(jié)構(gòu)與關(guān)系表達數(shù)據(jù)類型抽象數(shù)據(jù)類型特定的算法與問題求解算法求解思路的類型化IOI2009國家集訓(xùn)隊論文演示張昆瑋現(xiàn)在是14頁\一共有26頁\編輯于星期五函數(shù)VS抽象數(shù)據(jù)類型函數(shù)f(i)

抽象數(shù)據(jù)類型

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

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

MITOpencourseIntroductiontoAlgorithm課程網(wǎng)站：IOI2009國家集訓(xùn)隊論文演示張昆瑋現(xiàn)在是23頁\一共有26頁\編輯于星期五課程教學(xué)團隊任課教師：胡俊峰助教：

彭躍輝:

鄧昌明：

馬秀娟：

劉亮：

曲強：IOI2009國家集訓(xùn)隊論文演示張昆瑋現(xiàn)在是24頁\一共有26頁\編輯于星期五課時的基本安排周二3-4

周四1-2（單周）上機周二11-12（第二周開始）共16周，23次課。14項基礎(chǔ)知識內(nèi)容。3次POJ練習(xí)、解題討論。擴展報告、大作業(yè)討論。IOI2009國家集訓(xùn)隊論文演示張昆瑋現(xiàn)在是25頁\一共有26頁\編輯于星