数据描述资料学习教案

1、数据描述数据描述(mio sh)资料资料第一页，共89页。第1页/共89页第二页，共89页。ADT该数据结构(sh j ji u)有什么特点？有哪些操作？C+实现实现可执行的C+代码是怎样的？性能分析性能分析空间消耗如何？关键操作的时间性能如何？应用应用用在什么地方？怎么用？第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页。数据是计算机的处理对象，数据是计算机的处理对象，也是计算机的关键所在。也是计算机的关键所在。数据操作包括数据操作包括(boku)增、增、删、改、查四种删、改、查四种第6页/共89页第七页，共89页。抽象数据类型抽象数据类型LinearList LinearList 实例实例0 0或多个元素的有序集合或多个元素的有序集合操作操作Create()Create()： 创建创建(chungjin)(chungjin)一个空线性表一个空线性

3、表Destroy()Destroy()： 删除表删除表IsEmpty()IsEmpty()： 如果表为空则返回如果表为空则返回truetrue，否则返回，否则返回falsefalseLength()Length()： 返回表的大小返回表的大小( (即表中元素个数即表中元素个数) ) 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中；中；函数返回函数返回 修改后的线性表修改后的线性表Insert(k,x)Insert(k,x)：在第：在第k k个元素之后插入个元素之后插入x x；函数返回修改；函数返回修改后的线性表后的线性表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、在数组中的位置lasti第i个表最后一个元素在数组中的位置第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)，而非内容第35页/共89页第三十六页，共89

7、页。第36页/共89页第三十七页，共89页。寻找第k个元素复杂性为(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 din)k的link域指向新节点(ji din)，新节点(ji din)的link指向原来的节点(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页。双向循环(xnhun)链表可省掉RightEnd第54页/共89页第五十五页，共89页。第55页/共89页第五十六页，共89页。时间复杂性插入、删除操作(cozu)，链表描述性能更好随机访问，公式化

10、描述性能更优第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)的实现非常相似第62页/共89页第六十三页，共89页。第63页/共89页第六十四页，共89页。数组保存元素指针，比元素所需空间(kngjin)少很多，可一定程度解决公式化描述的缺点第64页/共89页第六十五页，共89页。第65页/共89页第六十六页，

12、共89页。公式化：定位(1)，删除元素(yun s)移动(length - k)s)链表：定位(k)，删除(1) 间接：定位(1)，删除指针移动(length k)第66页/共89页第六十七页，共89页。时间(shjin)复杂性类似删除操作第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调用(dioyng)变为对链表内部结构的直接操纵旧版本：DeletedeleteInsertnew新版本：节点从原链表摘除，直接放入箱子链表第79页/共89页第八十页，共89页。时间(shjin)复杂性(n+2range)稳定排序第80页/共89页第八十一页，共89页。第81页/共89页第八十二页，共89页。第82页/共89页第八十三页，共89页。第