c++数据结构 基础.ppt

《c++数据结构 基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目录13.1线性群体13.2群体数据的组织13.3小结1线性群体线性群体的概念直接访问群体--数组类顺序访问群体--链表类栈类队列类213.1线性群体群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。313.1线性群体13.1.1线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。41

2、3.1线性群体…第一个元素第二个元素第三个元素最后一个元素13.1.2直接访问群体——数组类静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。vector就是用类模板实现的动态数组。动态数组类模板：例9-3（Array.h）513.1线性群体6例13-1（教材例9-3）动态数组类模板程序#ifndefARRAY_H#defineARRAY_H#includetemp

3、late//数组类模板定义classArray{private:T*list;//用于存放动态分配的数组内存首地址intsize;//数组大小（元素个数）public:Array(intsz=50);//构造函数Array(constArray&a);//拷贝构造函数~Array();//析构函数Array&operator=(constArray&rhs);//重载"=“T&operator[](inti);//重载"[]”constT&operator[](inti)const;operatorT*

4、();//重载到T*类型的转换operatorconstT*()const;intgetSize()const;//取数组的大小voidresize(intsz);//修改数组的大小};13.1线性群体——13.1.2直接访问群体——数组类templateArray::Array(intsz){//构造函数assert(sz>=0);//sz为数组大小（元素个数），应当非负size=sz;//将元素个数赋值给变量sizelist=newT[size];//动态分配size个T类型的元素空间}template

5、ssT>Array::~Array(){//析构函数delete[]list;}//拷贝构造函数templateArray::Array(constArray&a){size=a.size;//从对象x取得数组大小，并赋值给当前对象的成员//为对象申请内存并进行出错检查list=newT[size];//动态分配n个T类型的元素空间for(inti=0;i

6、3-1（续）//重载"="运算符，将对象rhs赋值给本对象。实现对象之间的整体赋值templateArray&Array::operator=(constArray&rhs){if(&rhs!=this){//如果本对象中数组大小与rhs不同，则删除数组原有内存，然后重新分配if(size!=rhs.size){delete[]list;//删除数组原有内存size=rhs.size;//设置本对象的数组大小list=newT[size];//重新分配n个元素的内存}//从对象X复制数组元素到本对象fo

7、r(inti=0;iT&Array::operator[](intn){assert(n>=0&&nconstT&Array

8、::operator[](intn)const{assert(n>=0&&n