C++教程教学课件 作者 郑莉 李宁 13_数据结构简介.ppt

《C++教程教学课件 作者 郑莉 李宁 13_数据结构简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十三章数据结构简介清华大学郑莉学习目标掌握线性群体的概念；掌握直接存取线性群体——数组的使用；掌握顺序存取线性群体——链表的使用；掌握由数组或者链表存储的栈和队列；掌握部分排序与查找算法。2目录13.1线性群体13.1.1线性群体的概念13.1.2直接存取群体——数组13.1.3顺序存取群体——链表13.1.4栈13.1.5队列3目录（续）13.2群体数据的组织13.2.1顺序查找13.2.2折半查找13.2.3插入排序13.2.4选择排序13.2.5交换排序413.1.1线性群体的概念线性群体也可以称为线性表，其元素按一定的次序排列。线性表中有且只有一个

2、元素没有直接前驱，我们称之为头元素；有且只有一个元素没有直接后继，我们称之为尾元素；除头元素外，每个元素都有且只有一个直接前驱；除尾元素外每个元素都有且只有一个直接后继，如下图。513.1线性群体A1A2A3An-1An13.1.1线性群体的概念（续）按照群体中元素不同的存取方式又可以分为直接存取类、顺序存取类和广义索引类。本章只简单介绍前两种存取方式群体。对于直接访问的线性群体，我们可以直接访问群体中任何一个元素而不必要访问该元素的前驱元素，比如一维数组的访问。对于顺序访问的线性群体，只能按元素的顺序从头开始依次访问各个元素，这种访问也称为遍历。如我们即将

3、学习的链表。613.1线性群体13.1.2直接存取群体—数组用一组地址连续的存储单元依次存放线性表中的数据元素。我们称线性表中第一个数据元素的存储地址为线性表的起始地址，也称作线性表的基地址。如果我们已知线性表中第一个元素位置为LOC(a1)，则表中任一个数据元素的存储位置都按下式计算：LOC(ai)=LOC(a1)+(i-1)l数组的不足：大小需要由常量表达式进行确定，运行时不能改变；对于数组下标的越界，编译器并没有进行任何警告。713.1线性群体例13-1：动态数组//Array_int.h#ifndefARRAY_INT_H#defineARRAY_

4、INT_H#include#includeusingnamespacestd;#ifndefNULLconstintNULL=0;#endif813.1线性群体——13.1.2直接存取群体——数组例13-1（续）classArray{private:int*alist;//int类型指针，用于存放动态分配内存首地址intsize;//记录数组大小public:Array(int_size=50);//构造函数Array(constArray&A);//拷贝构造函数~Array(void);//析构函数Array&oper

5、ator=(constArray&rhs);//重载=号int&operator[](inti);//重载下标运算符operatorint*(void)const;//重载指针运算intListSize(void)const;//获取数组大小voidResize(int_size);//修改数组大小};913.1线性群体——13.1.2直接存取群体——数组例13-1（续）Array::Array(int_size){if(_size<=0){cerr<<“InvalidArraySize”<

6、小alist=newint[size];//分配内存if(alist==NULL){//分配不成功则警告错误，跳出程序cerr<<“MemoryAllocationfailed”<

7、错警告错误cerr<<"MemoryAllocationfailed"<

8、){//分配不成功则警告并跳出程序cerr<<"Me