数据结构与算法--线性表(C++)

1/55EssentialofLectureTwo：一、线性表的定义二、线性表---顺序表三、顺序表的基本操作四、顺序表的优缺点五、顺序表的应用重点难点2/55【定义】：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，......，an)一、线性表的定义(LinearList)例1、26个英文字母组成的字母表（A，B，C，......，Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）3/55例3、学生健康情况登记表姓名学号性别年龄健康情况王小林020631男18健康陈红020632女20一般刘建平020633男21健康张立立020634男17神经衰弱……..……..…….…….…….4/55设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表（1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；（2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱，ai+1是ai的直接后继；几点说明：（3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构；a1a2a3a4a5a65/55（4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；（5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号。几点说明：a1a2a3a4a5a66/55线性表的基本操作1．intLength()const初始条件：线性表已存在。操作结果：返回线性表元素个数。2．boolEmpty()const初始条件：线性表已存在。操作结果：如线性表为空，则返回true，否则返回false。7/553．voidClear()初始条件：线性表已存在。操作结果：清空线性表。线性表的基本操作4．voidTraverse(void(*visit)(constElemType&))const初始条件：线性表已存在。操作结果：依次对线性表的每个元素调用函数(*visit)。8/55为表示各种状态信息，定义枚举类型StatusCode供使用，具体声明如下：//自定义类型enumStatusCode{SUCCESS,FAIL,UNDER_FLOW,OVER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};9/555．StatusCodeGetElem(intposition,ElemType&e)const初始条件：线性表已存在，1≤position≤Length()。操作结果：用e返回第position个元素的值。线性表的基本操作6．StatusCodeSetElem(intposition,constElemType&e)初始条件：线性表已存在，1≤position≤Length()。操作结果：将线性表的第position个位置的元素赋值为e。10/557．StatusCodeDelete(intposition,ElemType&e)初始条件：线性表已存在，1≤position≤Length()。操作结果：删除线性表的第position个位置的元素,并用e返回其值，长度减1。线性表的基本操作8．StatusCodeInsert(intposition,constElemType&e)初始条件：线性表已存在，1≤position≤Length()+1。操作结果：在线性表的第position个位置前插入元素e，长度加1。11/55如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；12/55线性表按存储分类：1）顺序表SqList2）链表线性链表SimpleLinkList循环链表SimpleCircLinkList双向链表SimpleDblLinkList静态链表StLinkList13/55顺序表的定义和特点定义:将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构特点:线性表的顺序存储方式遍历:顺序访问二、顺序表SequentialList14/55线性表的顺序表示，就是用一组地址连续的内存单元依次存放线性表的数据元素。a1a2…ai-1aiai+1…an线性表（a1,a2,a3,...an）的顺序存储结构Loc(a1)Loc(ai)Loc(ai)=Loc(a1)+(i-1)*LL个单元二、顺序表SequentialList15/55顺序表(SqList)类的定义//顺序表类templateclasselemTypeclassSqList{protected://顺序表实现的数据成员:intcount;//元素个数intmaxSize;//顺序表最大元素个数elemType*elems;//元素存储空间16/55//辅助函数boolFull()const;//判断线性表是否已满voidInit(intsize);//初始化线性表public://抽象数据类型方法声明及重载编译系统默认//方法声明:SqList(intsize=DEFAULT_SIZE);//构造函数virtual~SqList();//析构函数intLength()const;//求线性表长度boolEmpty()const;//判断线性表是否为空voidClear();//将线性表清空17/55voidTraverse(void(*Visit)(constelemType&))const;//遍历线性表StatusCodeGetElem(intposition,elemType&e)const;//求指定位置的元素StatusCodeSetElem(intposition,constelemType&e);//设置指定位置的元素值StatusCodeDelete(intposition,elemType&e);//删除元素StatusCodeInsert(intposition,constelemType&e);//插入元素SqList(constSqListelemType©);//复制构造函数SqListelemType&operator=(constSqListelemType©);//赋值语句重载};18/55顺序表辅助函数的实现templateclassElemTypeboolSqListElemType::Full()const//操作结果：如线性表已满，则返回true，否则返回false{returncount==maxSize;}19/55templateclassElemTypevoidSqListElemType::Init(intsize)//操作结果：初始化线性表为最大元素个数为size的空线//性表{maxSize=size;//最大元素个数if(elems!=NULL)delete[]elems;//释放存储空间elems=newElemType[maxSize];//分配存储空间count=0;//空线性表元素个数为0}20/55templateclassElemTypeSqListElemType::SqList(intsize)//操作结果：构造一个最大元素个数为size的空顺序表{elems=NULL;//未分配存储空间前,elems为空Init(size);//初始化线性表}templateclassElemTypeSqListElemType::~SqList()//操作结果：销毁线性表{delete[]elems;//释放存储空间}顺序表部分公共操作的实现21/55指在表的第i(1≦i≦n+1)个位置上，插入一个新结点x，使长度为n的线性表变为长度为n+1的线性表：（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）1、插入三、顺序表的基本操作22/552534571648096312345678data2534571648096312345678data50例如：在i=4的位置插入x=50i0963481623/55templateclassElemTypeStatusCodeSqListElemType::Insert(intposition,constElemType&e)//操作结果：在线性表的第position个位置前插入元素e,//position的的取值范围为1≤position≤Length()+1//如线性表已满,则返回OVER_FLOW,//如position合法,则返回SUCCESS,否则函数返回//RANGE_ERROR{intlen=Length();ElemTypetmp;插入算法24/55if(Full()){//线性表已满返回OVER_FLOWreturnOVER_FLOW;}elseif(position1||positionlen+1){//position范围错returnRANGE_ERROR;}插入算法25/55else{//成功count++;//插入后元素个数将自增1for(intcurPosition=len;curPosition=position;curPosition--){//插入位置之后的元素右移GetElem(curPosition,tmp);SetElem(curPosition+1,tmp);}SetElem(position,e);//将e赋值到position位置处returnSUCCESS;//插入成功}}插入算法26/55上述算法for循环语句的执行次数为n-i+1；若i=1，需移动全部n个结点（最坏：O(n)）若i=n+1（在表尾插入），无需移动结点，直接插入即可。（最好:O(1)）移动结点的平均次数：插入算法分析27/55按等概率考虑：可能的插入位置为i=1,2,……n,n+1共n+1个，则pi=1/(n+1)顺序表插入算法平均约需移动一半结点。插入算法分析28/55将线性表的第i(1≦i≦n)个结点删除，使长度为n的线性表变为长度为n-1的线性表：（a1,a2,…,ai-1,ai,ai+1,…,an）（a1,a2,…,ai-1,ai+1,…,an）2、删除29/55253457501648096312345678data16253457501648096312345678data例如：删除第i个元素，i=5480963i30/55templateclassElemTypeStatusCodeSqListElemType::Delete(intposition,ElemType&e)//操作结果：删除线性表的第position个位置的元素,并且//用e返回其值,position的的取值范围为//1≤position≤Length(),position合法时函数返回//SUCCESS,否则函数返回RANGE_ERROR{intlen=Length();ElemTypetmp;if(position1||positionlen){//position范围错returnRANGE_ERROR;}2、删除算法31/55else{//position合法GetElem(position,e);//用e返回被删除元素的值for(intcurPosition=position+1;curPosition=len;curPosition++){//被删除元素之后的元素依次