数据结构课件C++版第二章.ppt

第二章线性表线性表顺序表单链表循环链表和双向链表多项式及其运算静态链表2.1线性表（LinearList）

2.1.1概念线性表的概念 线性表（linearlist）是n(≥0)个数据元素的有限序列，记作其中，2.1线性表（LinearList）

2.1.2线性结构的特点线性结构的特点存在一个唯一被称作“第一个”的数据元素；存在一个唯一被称作“最后一个”的数据元素；除第一个数据元素外，其他元素均有且仅有一个直接前驱，第一个元素没有前驱；除最后一个数据元素外，其他元素均有且仅有一个直接后继，最后一个元素没有后继。2.1线性表（LinearList）

2.1.3线性表的抽象基类线性表的抽象基类templateclassTclassLinearList{public:LinearList(); //构造函数～LinearList(); //析构函数virtualintSize()const=0;//求表中最大可容纳的表项个数virtualintLength()const=0; //求表长度 virtualintSearch(Tx)const=0; //有哪些信誉好的足球投注网站virtualintLocate(inti)const=0; //定位2.1线性表（LinearList）

2.1.3线性表的抽象基类virtualT*getData(inti)const=0; //取值virtualvoidsetData(inti,Tx)=0; //赋值virtualboolInsert(inti,Tx)=0; //插入virtualboolRemove(inti,Tx)=0; //删除virtualboolIsEmpty()const=0; //判表空virtualboolIsFull()const=0; //判表满virtualvoidSort()=0; //排序virtualvoidinput()=0; //输入virtualvoidoutput()=0; //输出virtualLinearListToperator= (LinearListTL)=0; //复制};2.1线性表（LinearList）

2.1.4线性表的存储表示线性表的存储表示顺序存储方式链表存储方式2.2顺序表（SequentialList）

2.2.1定义及特点定义 线性表的顺序存储方式（顺序表）指的是用一组地址连续的存储单元依次存储线性表的数据元素。即它利用元素在物理位置上的邻接关系来表示表中元素间的逻辑关系。通常用数组来实现。2.2顺序表（SequentialList）

2.2.1定义及特点优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；只要确定了线性表的起始地址，就可以对表中的元素进行随机存取—随机存取的存储结构；缺点：插入和删除元素的运算不方便，除最后一个元素外，做插入、删除操作时均须移动大量元素，其效率较低；分配存储空间的问题。2.2顺序表（SequentialList）

2.2.2类定义及其操作--类定义#includeiostream.h //定义在“seqList.h”中#includestdlib.h#includelinearList.hconstintdefaultSize=100;templateclassTclassSeqList:publicLinearListT{protected: T*data; //存放数组 intmaxSize; //最大可容纳表项的项数intlast; //当前已存表项数（从0开始） voidreSize(intnewSize); //改变数组空间大小2.2顺序表（SequentialList）

2.2.2类定义及其操作--类定义public: SeqList(intsz=defaultSize);//构造函数 SeqList(SeqListTL); //复制构造函数 ～SeqList(){delete[]data;} //析构函数intSize()cons