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

.,1,EssentialofLectureTwo：,一、线性表的定义二、线性表-顺序表三、顺序表的基本操作四、顺序表的优缺点五、顺序表的应用,第二讲顺序表,重点,难点,.,2,【定义】：由n(n0)个数据元素(结点)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,例3、学生健康情况登记表,.,4,设A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表（1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；（2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱，ai+1是ai的直接后继；,几点说明：,（3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构；,.,5,（4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；（5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号。,几点说明：,.,6,线性表的基本操作,1intLength()const初始条件：线性表已存在。操作结果：返回线性表元素个数。,2boolEmpty()const初始条件：线性表已存在。操作结果：如线性表为空，则返回true，否则返回false。,.,7,3voidClear()初始条件：线性表已存在。操作结果：清空线性表。,线性表的基本操作,4voidTraverse(void(*visit)(constElemType,.,9,5StatusCodeGetElem(intposition,ElemType/元素个数intmaxSize;/顺序表最大元素个数elemType*elems;/元素存储空间,.,16,/辅助函数boolFull()const;/判断线性表是否已满voidInit(intsize);/初始化线性表public:/抽象数据类型方法声明及重载编译系统默认/方法声明:SqList(intsize=DEFAULT_SIZE);/构造函数virtualSqList();/析构函数intLength()const;/求线性表长度boolEmpty()const;/判断线性表是否为空voidClear();/将线性表清空,.,17,voidTraverse(void(*Visit)(constelemType,.,18,顺序表辅助函数的实现,templateboolSqList:Full()const/操作结果：如线性表已满，则返回true，否则返回falsereturncount=maxSize;,.,19,templatevoidSqList:Init(intsize)/操作结果：初始化线性表为最大元素个数为size的空线/性表maxSize=size;/最大元素个数if(elems!=NULL)deleteelems;/释放存储空间elems=newElemTypemaxSize;/分配存储空间count=0;/空线性表元素个数为0,.,20,templateSqList:SqList(intsize)/操作结果：构造一个最大元素个数为size的空顺序表elems=NULL;/未分配存储空间前,elems为空Init(size);/初始化线性表templateSqList:SqList()/操作结果：销毁线性表deleteelems;/释放存储空间,顺序表部分公共操作的实现,.,21,指在表的第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表变为长度为n+1的线性表：（a1,a2,ai-1,ai,an）（a1,a2,ai-1,x,ai,an）,1、插入,三、顺序表的基本操作,.,22,25345716480963,12345678,data,25345716480963,12345678,data,例如：在i=4的位置插入x=50,i,09,63,48,16,.,23,templateStatusCodeSqList:Insert(intposition,constElemType,插入算法,.,24,if(Full()/线性表已满返回OVER_FLOWreturnOVER_FLOW;elseif(positionlen+1)/position范围错returnRANGE_ERROR;,插入算法,.,25,else/成功count+;/插入后元素个数将自增1for(intcurPosition=len;curPosition=position;curPosition-)/插入位置之后的元素右移GetElem(curPosition,tmp);SetElem(curPosition+1,tmp);SetElem(position,e);/将e赋值到position位置处returnSUCCESS;/插入成功,插入算法,.,26,上述算法for循环语句的执行次数为n-i+1；若i=1，需移动全部n个结点（最坏：O(n)）若i=n+1（在表尾插入），无需移动结点，直接插入即可。（最好:O(1)）移动结点的平均次数：,插入算法分析,.,27,按等概率考虑：可能的插入位置为i=1,2,n,n+1共n+1个，则pi=1/(n+1),顺序表插入算法平均约需移动一半结点。,插入算法分析,.,28,将线性表的第i(1in)个结点删除，使长度为n的线性表变为长度为n-1的线性表：（a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an）,2、删除,.,29,2534575016480963,12345678,data,16,2534575016480963,12345678,data,例如：删除第i个元素，i=5,48,09,63,i,.,30,templateStatusCodeSqList:Delete(intposition,ElemType,2、删除算法,.,31,else/position合法GetElem(position,e);/用e返回被删除元素的值for(intcurPosition=position+1;curPosition=len;curPosition+)/被删除元素之后的元素依次左移GetElem(curPosition,tmp);SetElem(curPosition-1,tmp);count-;/删除后元素个数将自减1returnSUCCESS;,2、删除算法,.,32,上述算法for循环语句的执行次数为n-i;若i=1，最坏：O(n)若i=n，无需用移动结点，直接删除即可。（最好O(1)）移动结点的平均次数：,2、删除算法分析,.,33,按等概率考虑：可能的删除位置为i=1,2,n共n个，则qi=1/n,顺序表删除算法平均约需移动一半结点。,2、删除算法分析,.,34,四、顺序表的优缺点,优点：无须为表示节点间的逻辑关系而增加额外的存储空间逻辑相邻，物理相邻;可随机存取任一元素缺点:插入、删除操作需要移动大量的元素要求占用连续的存储空间，存储分配只能预先进行预先分配空间需按最大空间分配，利用不充分,.,35,五、顺序表的应用,1、设计顺序表存储的两个集合求差集的算法,2534575016480963,12345678,la,1250237904342513,lb,lc,.,36,/文件路径名:s2_1alg.htemplatevoidDifference(constSqList/清空lc,算法实现,.,37,for(intaPosition=1;aPosition=la.Length();aPosition+)la.GetElem(aPosition,aItem);/取出la的一个元素aItemboolisExist=false;/表示aItem是否在lb中出现for(intbPosition=1;bPosition=lb.Length();bPosition+)lb.GetElem(bPosition,bItem);/取出lb的一个元素bItem,算法实现,.,38,if(aItem=bItem)isExist=true;/aItem同时在la和lb中/出现,置isExist为truebreak;/退出内层循环if(!isExist)/aItem在la中出现,而未在lb中未出现,/将其插入到lc中lc.Insert(lc.Length()+1,aItem);,算法实现,.,39,五、顺序表的应用,2、已知顺序表la的元素类型为int，设计算法讲其调整为左右两部分，左边的所有元素为奇数，右边的为偶数，要求T(n)=O(n)。,.,40,.,41,09,34,la,la,.,42,/文件路径名:s2_2alg.hvoidAdjust(SqList,算法实现,.,43,while(leftPositionrightPosition)la.GetElem(leftPosition,aItem);lb.GetElem(rightPosition,bItem);if(aItem%2=1)leftPosition+;elseif(bItem%2=0)rightPosition-;elsela.SetElem(leftPosition+,bItem);lb.SetElem(rightPosition-,aItem);,算法实现,.,44,类似：,北京理工大学2000年考研题算法题（本题8分）已知数组A1.n的元素类型为整形，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零（要求算法的时间复杂度为O（n）。,.,45,3、经典问题：约瑟夫环问题,n个人围成一圈，从第s个人开始报数，报到m的人出列，从下一个人再重新报数，报到m的人出列，如此下去，直至所有人都出列。试编写算法，输出出列人的编号。,.,46,算法思想：（1）把n个人看成一个环。（2）设当前有i个人，下一出列的人为s。s=（s+m-1）%i（3）将出列的人删除。,1,2,3,4,5,6,7,8,9,s=1,i=9,.,47,1,2,3,4,5,6,7,8,9,s=1,s=(s+m-1)%ii=9m=4,for(j=s;j1;i-)Start=(Start+Mima-1)%i;if(Start=0)/余数为0Start=i;la.GetElem(Start,tmp);for(j=Start;j=i-1;j+)la.GetElem(j+1,tmp2);la.SetElem(j,tmp2);la.SetElem(i,tmp);,算法实现,.,56,本讲小结