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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,/55,Essential of Lecture Two,：,一、线性表的定义,二、线性表,-,顺序表,三、顺序表的基本操作,四、顺序表的优缺点,五、顺序表的应用,第二讲 顺序表,重点,难点,1,【,定义,】,：由,n(n0),个数据元素,(,结点,)a,1,，,a,2,，,a,n,组成的有限序列。其中数据元素的个数,n,定义为表的长度。当,n=0,时称为空表，常常将非空的线性表,(n0),记作：,(a,1,，,a,2,，,. .,，,a,n,),一、线性表的定义,( Linear List ),例,1,、,26,个英文字母组成的字母表,（,A,，,B,，,C,，,. .,，,Z,）,例,2,、某校从,1978,年到,1983,年各种型号的计算机拥有量的变化情况。,（,6,，,17,，,28,，,50,，,92,，,188,）,2,例,3,、学生健康情况登记表,姓 名,学 号,性 别,年龄,健康情况,王小林,020631,男,18,健康,陈 红,020632,女,20,一般,刘建平,020633,男,21,健康,张立立,020634,男,17,神经衰弱,.,.,.,.,.,3,设,A=,（,a,1, a,2, . , a,i -1, a,i, a,i+1, , a,n,）,是一线性表,（,1,）,线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是,同一类型,的；,（,2,）,在表中,a,i-1,领先于,a,i,，,a,i,领先于,a,i+1,，称,a,i-1,是,a,i,的,直接前驱,，,a,i+1,是,a,i,的,直接后继,；,几点说明：,（,3,）,在线性表中，除第一个元素和最后一个元素之外，其他元素都,有且仅有,一个直接前驱，,有且仅有,一个直接后继，具有这种结构特征的数据结构称为,线性结构,；,a,1,a,2,a,3,a,4,a,5,a,6,4,（,4,）,线性表中元素的个数,n,称为线性表的长度，,n=0,时称为,空表,；,（,5,）,a,i,是线性表的第,i,个元素，称,i,为数据元素,a,i,的序号，每一个元素在线性表中的位置，仅取决于它的序号。,几点说明：,a,1,a,2,a,3,a,4,a,5,a,6,5,线性表的基本操作,1,int,Length() const,初始条件：线性表已存在。操作结果：返回线性表元素个数。,2,bool,Empty() const,初始条件：线性表已存在。操作结果：如线性表为空，则返回,true,，否则返回,false,。,6,3,void Clear(),初始条件：线性表已存在。操作结果：清空线性表。,线性表的基本操作,4,void,Traverse(void,(*,visit)(const,ElemType,&) const,初始条件：线性表已存在。操作结果：依次对线性表的每个元素调用函数,(*visit),。,7,为表示各种状态信息，定义枚举类型,StatusCode,供使用，具体声明如下：,/,自定义类型,enum,StatusCode,SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED,;,8,5,StatusCode,GetElem(int,position,ElemType,&e) const,初始条件：线性表已存在，,1positionLength(),。操作结果：用,e,返回第,position,个元素的值。,线性表的基本操作,6,StatusCode,SetElem(int,position, const,ElemType,&e),初始条件：线性表已存在，,1positionLength(),。操作结果：将线性表的第,position,个位置的元素赋值为,e,。,9,7,StatusCode Delete(int position, ElemType &e),初始条件：线性表已存在，,1positionLength(),。操作结果：删除线性表的第,position,个位置的元素,并用,e,返回其值，长度减,1,。,线性表的基本操作,8,StatusCode Insert(int position, const ElemType &e),初始条件：线性表已存在，,1positionLength()+1,。,操作结果,：,在线性表的第,position,个位置前插入元素,e,，,长度加,1,。,10,如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？,为了存储线性表，至少要保存两类信息：,1,）线性表中的数据元素；,2,）线性表中数据元素的顺序关系；,11,线性表按存储分类：,1,）顺序表,SqList,2,）,链表,线性链表,SimpleLinkList,循环链表,SimpleCircLinkList,双向链表,SimpleDblLinkList,静态链表,StLinkList,12,顺序表的定义和特点,定义,:,将线性表中的元素相继存放在一个连续的存储空间中。,可利用一维数组描述存储结构,特点,:,线性表的顺序存储方式,遍历,:,顺序访问,二、顺序表,Sequential List,13,线性表的,顺序表示,，就是用一组地址连续的内存单元依次存放线性表的数据元素。,a,1,a,2,a,i-1,a,i,a,i+1,a,n,线性表（,a,1,a,2,a,3, . a,n,）,的顺序存储结构,Loc( a,1,),Loc(,a,i,),Loc(a,i,) = Loc( a,1,)+ ( i-1 ) *,L,L,个单元,二、顺序表,Sequential List,14,顺序表,(,SqList,),类的定义,/,顺序表类,template ,class,SqList,protected:,/,顺序表实现的数据成员,:,int,count;,/,元素个数,int,maxSize,;,/,顺序表最大元素个数,elemType,*,elems,;,/,元素存储空间,15,/,辅助函数,bool,Full() const;,/,判断线性表是否已满,void,Init(int,size);,/,初始化线性表,public:,/,抽象数据类型方法声明及重载编译系统默认,/,方法声明,:,SqList(int,size = DEFAULT_SIZE);,/,构造函数,virtual ,SqList,();,/,析构函数,int,Length() const;,/,求线性表长度,bool,Empty() const;,/,判断线性表是否为空,void Clear();,/,将线性表清空,16,void,Traverse(void,(*,Visit)(const,elemType,&),const;,/,遍历线性表,StatusCode,GetElem(int,position,elemType,/,求指定位置的元素,StatusCode,SetElem(int,position, const,elemType,/,设置指定位置的元素值,StatusCode,Delete(int,position,elemType,/,删除元素,StatusCode,Insert(int,position, const,elemType,/,插入元素,SqList(const,SqList, ,/,复制构造函数,SqList, &operator =(const,SqList, ,/,赋值语句重载,;,17,顺序表辅助函数的实现,template ,bool,SqList,:Full() const,/,操作结果：如线性表已满，则返回,true,，否则返回,false,return count =,maxSize,;,18,template ,void,SqList,:,Init(int,size),/,操作结果：初始化线性表为最大元素个数为,size,的空线,/,性表,maxSize,= size;,/,最大元素个数,if (,elems,!= NULL) delete ,elems,;,/,释放存储空间,elems,= new,ElemTypemaxSize,;,/,分配存储空间,count = 0;,/,空线性表元素个数为,0,19,template ,SqList,:,SqList(int,size),/,操作结果：构造一个最大元素个数为,size,的空顺序表,elems,= NULL;,/,未分配存储空间前,elems,为空,Init(size,);,/,初始化线性表,template ,SqList,:,SqList,(),/,操作结果：销毁线性表,delete ,elems,;,/,释放存储空间,顺序表部分公共操作的实现,20,指在表的第,i(1in+1),个位置上，插入一个新结点,x,，,使长度为,n,的线性表变为长度为,n+1,的线性表：,（,a,1,a,2,a,i-1,a,i,a,n,）,（,a,1,a,2,a,i-1,x,a,i,a,n,）,1,、,插入,三、顺序表的基本操作,21,25 34 57 16 48 09 63,1 2 3 4 5 6 7,8,data,25 34 57,16 48 09 63,1 2 3 4 5 6 7,8,data,50,例如：在,i=4,的位置插入,x=50,i,09,63,48,16,22,template ,StatusCode,SqList,:,Insert(int,position,const,ElemType,&e),/,操作结果：在线性表的第,position,个位置前插入元素,e,/position,的的取值范围为,1positionLength()+1,/,如线性表已满,则返回,OVER_FLOW,/,如,position,合法,则返回,SUCCESS,否则函数返回,/RANGE_ERROR,int,len,= Length();,ElemType,tmp,;,插入算法,23,if (Full(),/,线性表已满返回,OVER_FLOW,return OVER_FLOW;,else if (position ,len,+ 1),/ position,范围错,return RANGE_ERROR;,插入算法,24,else,/,成功,count+;,/,插入后元素个数将自增,1,for (,int,curPosition,=,len,;,curPosition,= position;,curPosition,-),/,插入位置之后的元素右移,GetElem(curPosition,tmp,);,SetElem(curPosition,+ 1,tmp,);,SetElem(position, e);,/,将,e,赋值到,position,位置处,return SUCCESS;,/,插入成功,插入算法,25,上述算法,for,循环语句的执行次数为,n-i+1,；,若,i=1,，需移动全部,n,个结点（最坏：,O(n),）,若,i=n+1,（在表尾插入），无需移动结点，直接插入即可。（最好,: O(1),）,移动结点的平均次数：,插入算法分析,26,按等概率考虑：,可能的插入位置为,i=1,2,n,n+1,共,n+1,个，,则,p,i,= 1/(n+1),顺序表插入算法平均约需移动一半结点。,插入算法分析,27,将线性表的第,i(1in),个结点删除，,使长度为,n,的线性表变为长度为,n-1,的线性表：,（,a,1,a,2,a,i-1,a,i, a,i+1,a,n,）,（,a,1,a,2,a,i-1, a,i+1,a,n,）,2,、,删除,28,25 34 57 50 16 48 09 63,1 2 3 4 5 6 7,8,data,16,25 34 57 50,16,48 09 63,1 2 3 4 5 6 7,8,data,例如：删除第,i,个元素，,i=5,48,09,63,i,29,template ,StatusCode,SqList,:,Delete(int,position,ElemType,&e),/,操作结果：删除线性表的第,position,个位置的元素,并且,/,用,e,返回其值, position,的的取值范围为,/1positionLength(), position,合法时函数返回,/SUCCESS,否则函数返回,RANGE_ERROR,int,len,= Length();,ElemType,tmp,;,if (position ,len,),/ position,范围错,return RANGE_ERROR;,2,、,删除算法,30,else,/ position,合法,GetElem(position, e);,/,用,e,返回被删除元素的值,for (,int,curPosition,= position + 1;,curPosition,=,len,;,curPosition,+),/,被删除元素之后的元素依次左移,GetElem(curPosition,tmp,);,SetElem(curPosition,- 1,tmp,);,count-;,/,删除后元素个数将自减,1,return SUCCESS;,2,、,删除算法,31,上述算法,for,循环语句的执行次数为,n-i,;,若,i=1,，最坏：,O(n),若,i=n,，无需用移动结点，直接删除即可。,（最好,O(1),）,移动结点的平均次数：,2,、,删除算法分析,32,按等概率考虑：,可能的删除位置为,i=1,2,n,共,n,个，,则,q,i,=1/n,顺序表删除算法平均约需移动一半结点。,2,、,删除算法分析,33,四、顺序表的优缺点,优点：,无须为表示节点间的逻辑关系而增加额外的存储空间,逻辑相邻，物理相邻,;,可随机存取任一元素,缺点,:,插入、删除操作需要移动大量的元素,要求占用连续的存储空间，存储分配只能预先进行,预先分配空间需按最大空间分配，利用不充分,34,五、顺序表的应用,1,、设计顺序表存储的两个集合求差集的算法,25 34 57 50 16 48 09 63,1 2 3 4 5 6 7,8,la,12,50,23,79,04,34,25,1,3,lb,lc,35,/,文件路径名,:s2_1alg.h,template ,void,Difference(const,SqList, &la, const,SqList, &lb,SqList, &,lc,),/,操作结果,:,用,lc,返回,la,和,lb,表示的集合的差集,/,方法,:,在,la,中取出元素,在,lb,中进行查找,如果未在,lb,中,/,出现了,将其插入到,lc,ElemType,aItem,bItem,;,lc.Clear,();,/,清空,lc,算法实现,36,for (,int,aPosition,= 1;,aPosition,=,la.Length,();,aPosition,+),la.GetElem(aPosition,aItem,);,/,取出,la,的一个元素,aItem,bool,isExist,= false;,/,表示,aItem,是否在,lb,中出现,for (,int,bPosition,= 1;,bPosition,=,lb.Length,();,bPosition,+),lb.GetElem(bPosition,bItem,);,/,取出,lb,的一个元素,bItem,算法实现,37,if (,aItem,=,bItem,),isExist,= true;,/,aItem,同时在,la,和,lb,中,/,出现,置,isExist,为,true,break;,/,退出内层循环,if (!,isExist,),/,aItem,在,la,中出现,而未在,lb,中未出现,/,将其插入到,lc,中,lc.Insert(lc.Length,() + 1,aItem,);,算法实现,38,五、顺序表的应用,2,、已知顺序表,la,的元素类型为,int,，设计算法讲其调整为左右两部分，左边的所有元素为奇数，右边的为偶数，要求,T(n,)=,O(n,),。,39,1 2 3 4 5 6 7,8,la,leftPosition,rightPosition,25 34 57 50 16 48 09 6,2,25 34 57 50 16 48 09 6,2,la,leftPosition,rightPosition,25 34 57 50 16 48 09 6,2,la,leftPosition,rightPosition,40,25 34 57 50 16 48 09 6,2,la,leftPosition,rightPosition,09,34,交换,25,09,57 50 16 48,34,6,2,la,leftPosition,rightPosition,leftPosition,rightPosition,25,09,57 50 16 48,34,6,2,la,leftPosition,rightPosition,41,/,文件路径名,:s2_2alg.h,void,Adjust(SqList, &la),/,操作结果,:,将,la,调整为左右两部分，,/,左边所有元素为奇数，右边所有元素为偶数,/,并要求时间复杂度为,O(n,),int,leftPosition,=1,rightPosition,=,la.length,();,int,aItem,bItem,;,算法实现,42,while(leftPosition,rightPosition,),la.GetElem(leftPosition,aItem,);,lb.GetElem(rightPosition,bItem,);,if(aItem%2=1),leftPosition,+;,else if(bItem%2=0),rightPosition,-;,else ,la.SetElem(leftPosition+,bItem,);,lb.SetElem(rightPosition-,aItem,);,算法实现,43,类似：,北京理工大学,2000,年考研题,算法题（本题,8,分）,已知数组,A1.n,的元素类型为整形，设计算法调整,A,，使其左边的所有元素小于零，右边的所有元素大于等于零（要求算法的时间复杂度为,O,（,n,）。,44,3,、经典问题：约瑟夫环问题,n,个人围成一圈，从第,s,个人开始报数，报到,m,的人出列，从下一个人再重新报数，报到,m,的人出列，如此下去，直至所有人都出列。试编写算法，输出出列人的编号。,45,算法思想：,（,1,）把,n,个人看成一个环。,（,2,）设当前有,i,个人，下一出列的人为,s,。,s=,（,s+m-1,）,% i,（,3,）将出列的人删除。,1,2,3,4,5,6,7,8,9,s=1,i=9,46,1,2,3,4,5,6,7,8,9,s=1,s=(s+m-1)%i,i=9,m=4,for(j,=,s;j,=i-1;j+),L.listj,=L.listj+1;,4,print,47,1,2,3,4,5,6,7,8,9,n=9,i=9,1,2,3,4,5,6,7,8,9,s=,（,s+m-1,）,% i,m=4,s=1,4,print,1,2,3,5,6,7,8,9,4,t=4,计算出,s=4,1,2 3 4 5 6 7,8 9,48,1,2,3,5,6,7,8,9,i,减,1,i=8,i=8,1,2,3,5,6,7,8,9,4,s=,（,s+m-1,）,% i,m=4,s=4,t=4,计算出,s=7,8,1,2,3,5,6,7,9,4,t=8,1,2,3,5,6,7,9,8,4,i,减,1,i=7,1,2 3 4 5 6 7,8 9,49,1,2,3,5,6,7,9,8,4,i=7,s=,（,s+m-1,）,% i,m=4,s=7,计算出,s=3,1,2,5,6,7,9,8,4,t=3,3,1,2,5,6,7,9,3,8,4,i,减,1,i=6,1,2 3 4 5 6 7,8 9,50,1,2,5,6,7,9,3,8,4,i=6,s=,（,s+m-1,）,% i,s=3,m=4,计算出,s=0,1,2,5,6,7,3,8,4,t=9,9,1,2,5,6,7,9,3,8,4,i,减,1,i=5,则,s=i,即,s=6,1,2 3 4 5 6,7,8 9,51,1,2,5,6,7,9,3,8,4,i=5,s=,（,s+m-1,）,% i,s=6,m=4,计算出,s=4,1,2,5,7,9,3,8,4,6,i,减,1,i=4,t=6,1,2,5,7,6,9,3,8,4,1,2 3 4 5 6,7,8 9,52,i=4,1,2,5,7,6,9,3,8,4,1,2 3 4 5 6,7,8 9,s=,（,s+m-1,）,% i,s=4,m=4,计算出,s=3,i=3,1,2,7,5,6,9,3,8,4,s=,（,s+m-1,）,% i,s=3,m=4,计算出,s=0,则,s=i,即,s=3,i=2,1,2,7,5,6,9,3,8,4,s=,（,s+m-1,）,% i,s=3,m=4,计算出,s=0,则,s=i,即,s=2,i=1,1,2,7,5,6,9,3,8,4,53,/,文件路径名,:s2_Josephalg.h,void,Joseph(SqList, &la),/,约瑟夫环问题,int,Start=1; /,从,1,号开始报数,int,Mima,=4; /,密码是,4,int,tmp, tmp2;,int,i, j;,算法实现,54,for (i=,la.Length();i,1;i-),Start=(Start+Mima-1)%i;,if (Start = 0),/,余数为,0,Start=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,);,算法实现,55,本 讲 小 结,重点：,1,、线性表的基本概念,2,、顺序表的存储,难点：,1,、顺序表的插入、删除算法,2,、顺序表的应用,56,Homework:,1,、编写算法实,现线性顺序表的,就地,（不申请额外空间）,逆置,。,2,、,用线性表的顺序存储模式编写算法，实现两个顺序表的,并集,。,3,、已知,A,、,B,和,C,为,3,个元素值递增有序的顺序表，现要求对表,A,作如下运算：删去那些既在,B,中出现又在,C,中出现的元素。,上实验课时要求在机器上调试通过后再将核心代码打包提交。,57,see you later!,没有比人更高的山！,没有比脚更长的路！,58,