數(shù)據(jù)描述資料學(xué)習(xí)教案

1、數(shù)據(jù)描述數(shù)據(jù)描述(mio sh)資料資料第一頁，共89頁。第1頁/共89頁第二頁，共89頁。ADT該數(shù)據(jù)結(jié)構(gòu)(sh j ji u)有什么特點？有哪些操作？C+實現(xiàn)實現(xiàn)可執(zhí)行的C+代碼是怎樣的？性能分析性能分析空間消耗如何？關(guān)鍵操作的時間性能如何？應(yīng)用應(yīng)用用在什么地方？怎么用？第2頁/共89頁第三頁，共89頁。第3頁/共89頁第四頁，共89頁。第4頁/共89頁第五頁，共89頁。年份年份片名片名2006Crash2007The Departed2008No Country for Old Men2009Slumdog Millionaire2010The Hurt Locker2011The Ki

2、ngs Speech 2012The Artist 2013Argo 201412 years a slave2015Birdman第5頁/共89頁第六頁，共89頁。數(shù)據(jù)是計算機的處理對象，數(shù)據(jù)是計算機的處理對象，也是計算機的關(guān)鍵所在。也是計算機的關(guān)鍵所在。數(shù)據(jù)操作包括數(shù)據(jù)操作包括(boku)增、增、刪、改、查四種刪、改、查四種第6頁/共89頁第七頁，共89頁。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型LinearList LinearList 實例實例0 0或多個元素的有序集合或多個元素的有序集合操作操作Create()Create()： 創(chuàng)建創(chuàng)建(chungjin)(chungjin)一個空線性表一個空線性

3、表Destroy()Destroy()： 刪除表刪除表IsEmpty()IsEmpty()： 如果表為空則返回如果表為空則返回truetrue，否則返回，否則返回falsefalseLength()Length()： 返回表的大小返回表的大小( (即表中元素個數(shù)即表中元素個數(shù)) ) Find(k,x) Find(k,x)： 尋找表中第尋找表中第k k個元素，并把它保存到個元素，并把它保存到x x中；中；如果不存如果不存 在，則返回在，則返回falsefalseSearch(x)Search(x)： 返回元素返回元素x x在表中的位置；如果在表中的位置；如果x x不在表不在表中，返回中，返回0

4、0Delete(k,x)Delete(k,x)：刪除表中第：刪除表中第k k個元素，并把它保存到個元素，并把它保存到x x中；中；函數(shù)返回函數(shù)返回 修改后的線性表修改后的線性表Insert(k,x)Insert(k,x)：在第：在第k k個元素之后插入個元素之后插入x x；函數(shù)返回修改；函數(shù)返回修改后的線性表后的線性表Output(out)Output(out)：把線性表放入輸出流：把線性表放入輸出流outout之中之中 第7頁/共89頁第八頁，共89頁。e1e2en第8頁/共89頁第九頁，共89頁。第9頁/共89頁第十頁，共89頁。e1e2en第10頁/共89頁第十一頁，共89頁。第11頁/

5、共89頁第十二頁，共89頁。第12頁/共89頁第十三頁，共89頁。第13頁/共89頁第十四頁，共89頁。第14頁/共89頁第十五頁，共89頁。Delete(2, x)第15頁/共89頁第十六頁，共89頁。(length - k)s)第16頁/共89頁第十七頁，共89頁。第17頁/共89頁第十八頁，共89頁。Insert(3, 7)第18頁/共89頁第十九頁，共89頁。第19頁/共89頁第二十頁，共89頁。第20頁/共89頁第二十一頁，共89頁。第21頁/共89頁第二十二頁，共89頁。第22頁/共89頁第二十三頁，共89頁。第23頁/共89頁第二十四頁，共89頁。firsti第i個表的第一個元素

6、在數(shù)組中的位置lasti第i個表最后一個元素在數(shù)組中的位置第24頁/共89頁第二十五頁，共89頁。第25頁/共89頁第二十六頁，共89頁。個位置第26頁/共89頁第二十七頁，共89頁。第27頁/共89頁第二十八頁，共89頁。第28頁/共89頁第二十九頁，共89頁。第29頁/共89頁第三十頁，共89頁。第30頁/共89頁第三十一頁，共89頁。第31頁/共89頁第三十二頁，共89頁。第32頁/共89頁第三十三頁，共89頁。第33頁/共89頁第三十四頁，共89頁。使用(shyng)鏈Chain L;第34頁/共89頁第三十五頁，共89頁。資源(zyun)，而非內(nèi)容第35頁/共89頁第三十六頁，共89

7、頁。第36頁/共89頁第三十七頁，共89頁。尋找第k個元素復(fù)雜性為(k)公式(gngsh)描述為(1)情況1：目標(mbio)非法，k過小情況2：目標(mbio)合法，且存在情況3：目標(mbio)非法，k過大第37頁/共89頁第三十八頁，共89頁。第38頁/共89頁第三十九頁，共89頁。第39頁/共89頁第四十頁，共89頁。第40頁/共89頁第四十一頁，共89頁。情況1：目標(mbio)非法，因其過小或表為空情況2：目標(mbio)合法，刪第一個元素情況3：目標(mbio)合法，刪其他元素情況4：目標(mbio)非法，因其過大第41頁/共89頁第四十二頁，共89頁。【繪圖(hu t)演示】第

8、42頁/共89頁第四十三頁，共89頁。k0：令節(jié)點(ji din)k的link域指向新節(jié)點(ji din)，新節(jié)點(ji din)的link指向原來的節(jié)點(ji din)k+1第43頁/共89頁第四十四頁，共89頁。情況1：目標(mbio)非法，因其過小情況2：目標(mbio)非法，因其過大情況3：目標(mbio)合法，插入到表中或表后情況4：目標(mbio)合法，插入到表頭【繪圖演示】第44頁/共89頁第四十五頁，共89頁。這兩句話能互換順序這兩句話能互換順序(shnx)嗎？嗎？第45頁/共89頁第四十六頁，共89頁。 first = next; 第46頁/共89頁第四十七頁，共89頁。第4

9、7頁/共89頁第四十八頁，共89頁。 last = y; else / chain is empty first = last = y; return *this;第48頁/共89頁第四十九頁，共89頁。第49頁/共89頁第五十頁，共89頁。第50頁/共89頁第五十一頁，共89頁。第51頁/共89頁第五十二頁，共89頁。第52頁/共89頁第五十三頁，共89頁。第53頁/共89頁第五十四頁，共89頁。雙向循環(huán)(xnhun)鏈表可省掉RightEnd第54頁/共89頁第五十五頁，共89頁。第55頁/共89頁第五十六頁，共89頁。時間復(fù)雜性插入、刪除操作(cozu)，鏈表描述性能更好隨機訪問，公式化

10、描述性能更優(yōu)第56頁/共89頁第五十七頁，共89頁。 Chain& Delete(int k, T& x); Chain& Insert(int k, const T& x);template class ChainNode friend Chain;private: T data; ChainNode *link;第57頁/共89頁第五十八頁，共89頁。操作操作(ADT)順序表順序表單向鏈表單向鏈表Destroy(1)(1)(n)(n)IsEmpty(1)(1)(1)(1)Length(1)(1)(n)(n)Find(1)(1)(k)(k)Search(n)(

11、n)(n)(n)Delete(n-k)s)(n-k)s)(k)(k)Insert(n-k)s)(n-k)s)(k)(k)Output(n)(n)(n)(n)第58頁/共89頁第五十九頁，共89頁。第59頁/共89頁第六十頁，共89頁。第60頁/共89頁第六十一頁，共89頁。第61頁/共89頁第六十二頁，共89頁。(1)，與公式化描述(mio sh)的實現(xiàn)非常相似第62頁/共89頁第六十三頁，共89頁。第63頁/共89頁第六十四頁，共89頁。數(shù)組保存元素指針，比元素所需空間(kngjin)少很多，可一定程度解決公式化描述的缺點第64頁/共89頁第六十五頁，共89頁。第65頁/共89頁第六十六頁，

12、共89頁。公式化：定位(1)，刪除元素(yun s)移動(length - k)s)鏈表：定位(k)，刪除(1) 間接：定位(1)，刪除指針移動(length k)第66頁/共89頁第六十七頁，共89頁。時間(shjin)復(fù)雜性類似刪除操作第67頁/共89頁第六十八頁，共89頁。第68頁/共89頁第六十九頁，共89頁。描述方法描述方法操作操作查找第查找第k個元素個元素刪除第刪除第k個元素個元素插入第插入第k元素后元素后公式化公式化(1)O(n-k)s)O(n-k)s)鏈表鏈表O(k)O(k)O(k+s)間接尋址間接尋址(1)O(n-k)O(n-k)第69頁/共89頁第七十頁，共89頁。第70頁

13、/共89頁第七十一頁，共89頁。第71頁/共89頁第七十二頁，共89頁。第72頁/共89頁第七十三頁，共89頁。第73頁/共89頁第七十四頁，共89頁。第74頁/共89頁第七十五頁，共89頁。Chain類需要Node類支持這兩個(lin )操作第75頁/共89頁第七十六頁，共89頁。元素(yun s)的取值范圍第76頁/共89頁第七十七頁，共89頁。第77頁/共89頁第七十八頁，共89頁。*top; bottom = new ChainNode* range + 1; top = new ChainNode*range + 1; for (b = 0; b = range; b+) bottomb = 0;bottomb：箱子(xing zi)b鏈表首topb：箱子(xing zi)b鏈表尾第78頁/共89頁第七十九頁，共89頁。Delete、Insert調(diào)用(dioyng)變?yōu)閷︽湵韮?nèi)部結(jié)構(gòu)的直接操縱舊版本：DeletedeleteInsertnew新版本：節(jié)點從原鏈表摘除，直接放入箱子鏈表第79頁/共89頁第八十頁，共89頁。時間(shjin)復(fù)雜性(n+2range)穩(wěn)定排序第80頁/共89頁第八十一頁，共89頁。第81頁/共89頁第八十二頁，共89頁。第82頁/共89頁第八十三頁，共89頁。第