(1.1.1)-1.1什么是數(shù)據(jù)結(jié)構(gòu)

1第一講：什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法1.1什么是數(shù)據(jù)結(jié)構(gòu)好的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)最優(yōu)效率的算法程序=算法+數(shù)據(jù)結(jié)構(gòu)——圖靈獎(jiǎng)獲得者尼古拉斯·沃斯1.1什么是數(shù)據(jù)結(jié)構(gòu)問(wèn)題求解的過(guò)程框架：實(shí)際問(wèn)題求解算法測(cè)試、調(diào)整程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)結(jié)構(gòu)課程中的內(nèi)容數(shù)學(xué)模型抽象

構(gòu)造求解算法

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

程序?qū)崿F(xiàn)

4例1如何在書架上擺放圖書非數(shù)值計(jì)算問(wèn)題舉例1：ontents什么是數(shù)據(jù)結(jié)構(gòu)不科學(xué)！5例1如何在書架上擺放圖書ontents什么是數(shù)據(jù)結(jié)構(gòu)例1如何在書架上擺放圖書圖書的擺放至少是跟兩個(gè)操作直接相關(guān)的：插入：新書怎么插入？查找：如何查找指定的某本書？6什么是數(shù)據(jù)結(jié)構(gòu)例1如何在書架上擺放圖書方法1：隨便放插入：新書怎么插入？哪里有空放哪里！查找：如何查找指定的某本書？順序查找7什么是數(shù)據(jù)結(jié)構(gòu)例1如何在書架上擺放圖書方法2：按書名拼音字母順序存放查找：如何查找指定的某本書？二分查找8什么是數(shù)據(jù)結(jié)構(gòu)ABCEDFGHIJKLMNOPQRXTUVWSYZ例1如何在書架上擺放圖書方法2：按書名拼音字母順序存放插入：新書怎么插入？確定插入位置,之后的書全部后移,空位插入9什么是數(shù)據(jù)結(jié)構(gòu)ZYABCEDFGHIJKLMNOPQRXTUVWS例1如何在書架上擺放圖書方法3：按照書的類別劃分區(qū)域，同類內(nèi)按拼音字母順序存放插入：新書怎么插入？先定類別,再二分查找確定位置,移出空位插入！查找：如何查找指定的某本書？先確定類別，再二分查找10什么是數(shù)據(jù)結(jié)構(gòu)例1如何在書架上擺放圖書方法3：按書按照書的類別劃分區(qū)域，同類內(nèi)按拼音字母順序存放面臨的新問(wèn)題：每類的空間應(yīng)如何分配？類別應(yīng)該分多細(xì)？11什么是數(shù)據(jù)結(jié)構(gòu)例1如何在書架上擺放圖書方法1、方法2、方法3：書架問(wèn)題總結(jié)：解決問(wèn)題方法的效率，跟數(shù)據(jù)的組織方式是直接相關(guān)的。12什么是數(shù)據(jù)結(jié)構(gòu)13例2田徑賽的時(shí)間安排問(wèn)題（無(wú)向圖的著色問(wèn)題）例2：田徑賽的時(shí)間安排問(wèn)題ontents數(shù)據(jù)結(jié)構(gòu)的概念

設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目,有人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。14（1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：

跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米

ABCDEF姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一ABE馬二CD

張三CEF李四DFA王五BF（2）用頂點(diǎn)代表比賽項(xiàng)目

不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。ontents例2田徑賽時(shí)間安排問(wèn)題的解法數(shù)據(jù)結(jié)構(gòu)的概念BAEFDC（3）某選手比賽的項(xiàng)目必定有邊相連（不能同時(shí)比賽）15比賽時(shí)間比賽項(xiàng)目1A，C2B，D3E4FBAEFDContents例2田徑賽時(shí)間安排問(wèn)題的解法數(shù)據(jù)結(jié)構(gòu)的概念BAEFDC日程安排結(jié)果是唯一的嗎？只需安排四個(gè)單位時(shí)間進(jìn)行比賽什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)對(duì)象的組織方式:邏輯結(jié)構(gòu)：表示數(shù)據(jù)元素之間的邏輯關(guān)系。物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式。數(shù)據(jù)對(duì)象必定與一系列加在其上的操作相關(guān)聯(lián)。完成這些操作所用的方法就是算法。

1617邏輯結(jié)構(gòu)(LogicalStructure)線性結(jié)構(gòu)：存在一對(duì)一的關(guān)系。樹形結(jié)構(gòu)：存在一對(duì)多的關(guān)系。圖：多對(duì)多的關(guān)系。集合：僅同屬一個(gè)集合。

存儲(chǔ)結(jié)構(gòu)(StorageStructure)運(yùn)算（Operations）ontents數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三要素：

給定數(shù)據(jù)，分析數(shù)據(jù)元素之間的邏輯