第021讲顺序表

《第021讲顺序表》由会员分享，可在线阅读，更多相关《第021讲顺序表（53页珍藏版）》请在装配图网上搜索。

1、第第02-1讲顺序表讲顺序表Essential of Lecture TwoEssential of Lecture Two：一、线性表的定义一、线性表的定义 二、线性表二、线性表-顺序表顺序表 三、顺序表的基本操作三、顺序表的基本操作 四、顺序表的优缺点四、顺序表的优缺点 五、顺序表的应用五、顺序表的应用重点重点难点难点2 2【定义定义定义定义】：由：由n(n 0)个数据元素个数据元素(结点结点)a1，a2，an组组成的有限序列。其中数据元素的个数成的有限序列。其中数据元素的个数n定义为表的长度。定义为表的长度。当当n=0时称为空表，常常将非空的线性表时称为空表，常常将非空的线性表(n0)记

2、作：记作：(a1，a2，.，an)一、线性表的定义一、线性表的定义 (Linear List)(Linear List)例例例例1 1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C，.，Z）例例例例2 2、某校从、某校从1978年到年到1983年各种型号的计算机拥有年各种型号的计算机拥有量的变化情况。量的变化情况。（6，17，28，50，92，188）3 3例例例例3 3、学生健康情况登记表、学生健康情况登记表姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林020631男男 18 健康健康陈陈 红红020632女女 20 一般一般刘建平刘建平020633男

3、男 21 健康健康张立立张立立020634男男 17 神经衰弱神经衰弱.4 4 设设 A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表，是一线性表，（1 1）线性表的数据元素可以是各种各样的，但同一线线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是性表中的元素必须是同一类型同一类型同一类型同一类型的；的；（2 2）在表中在表中 ai-1 领先于领先于ai，ai 领先于领先于ai+1，称，称ai-1 是是ai 的的直接前驱直接前驱直接前驱直接前驱，ai+1 是是ai 的的直接后继直接后继直接后继直接后继；几点说明：几点说明：（3 3）在线性表中，除第一个元素和最后一个

4、元素在线性表中，除第一个元素和最后一个元素之外，其他元素都之外，其他元素都有且仅有有且仅有有且仅有有且仅有一个直接前驱，一个直接前驱，有且仅有有且仅有有且仅有有且仅有一个直接后继，具有这种结构特征的数据结构称为一个直接后继，具有这种结构特征的数据结构称为线线线线性结构性结构性结构性结构；a1a2a3a4a5a65 5（4 4）线性表中元素的个数线性表中元素的个数n 称为线性表的长度，称为线性表的长度，n=0 时称为时称为空表空表空表空表；（5 5）ai是线性表的第是线性表的第i 个元素，称个元素，称i 为数据元素为数据元素ai 的的序号，每一个元素在线性表中的位置，仅取决于它的序序号，每一个元

5、素在线性表中的位置，仅取决于它的序号。号。几点说明：几点说明：a1a2a3a4a5a66 6线性表的基本操作线性表的基本操作 n1 1 intint Length()const Length()const 初始条件：线性表已存在。初始条件：线性表已存在。初始条件：线性表已存在。初始条件：线性表已存在。操作结果：返回线性表元素个数。操作结果：返回线性表元素个数。操作结果：返回线性表元素个数。操作结果：返回线性表元素个数。n2 2boolbool Empty()Empty()初始条件：线性表已存在。初始条件：线性表已存在。初始条件：线性表已存在。初始条件：线性表已存在。操作结果：如线性表为空，则返

6、回操作结果：如线性表为空，则返回操作结果：如线性表为空，则返回操作结果：如线性表为空，则返回truetrue，否则返回，否则返回，否则返回，否则返回falsefalse。P427 7如何在计算机中存储线性表？如何在计算机中存储线性表？如何在计算机中实现线性表的如何在计算机中实现线性表的基本操作？基本操作？为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；）线性表中的数据元素；2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；8 8线性表按存储分类：线性表按存储分类：

7、1）顺序表）顺序表 SqList2）链表）链表单链表单链表 SimpleLinkList循环链表循环链表 SimpleCircLinkList双向链表双向链表 SimpleDblLinkList静态链表静态链表 StLinkList9 9顺序表的定义和特点顺序表的定义和特点 定义定义:将线性表中的元素相继存放在一将线性表中的元素相继存放在一个连续的存储空间中。个连续的存储空间中。可利用一维数组描述存储结构可利用一维数组描述存储结构 特点特点:线性表的顺序存储方式线性表的顺序存储方式 遍历遍历:顺序访问顺序访问 二、顺序表二、顺序表 Sequential ListSequential List1

8、010 线性表的线性表的顺序表示顺序表示顺序表示顺序表示，就是，就是用一组地址连续的内存单元依用一组地址连续的内存单元依次存放线性表的数据元素。次存放线性表的数据元素。a1a2ai-1aiai+1an 线性表（线性表（a1,a2,a3,.an）的顺序存储结构的顺序存储结构 Loc(a1)Loc(ai)Loc(ai)=Loc(a1)+(i-1)*LL L个单元个单元二、顺序表二、顺序表 Sequential ListSequential List1111顺序表顺序表(SqList)(SqList)类的定义类的定义/顺序表类顺序表类template class SqList protected:/

9、顺序表实现的数据成员顺序表实现的数据成员:int count;/元素个数元素个数int maxSize;/顺序表最大元素个数顺序表最大元素个数elemType*elems;/元素存储空间元素存储空间程序实现见文件夹程序实现见文件夹test_sq_list1212/辅助函数辅助函数bool Full()const;/判断线性表是否已满判断线性表是否已满void Init(int size);/初始化线性表初始化线性表public:/抽象数据类型方法声明及重载编译系统默认抽象数据类型方法声明及重载编译系统默认/方法声明方法声明:SqList(int size=DEFAULT_SIZE);/构造函数

10、构造函数virtual SqList();/析构函数析构函数int Length()const;/求线性表长度求线性表长度bool Empty()const;/判断线性表是否为空判断线性表是否为空void Clear();/将线性表清空将线性表清空1313void Traverse(void(*Visit)(const elemType&)const;/遍历线性表遍历线性表StatusCode GetElem(int position,elemType&e)const;/求指定位置的元素求指定位置的元素StatusCode SetElem(int position,const elemType

11、&e);/设置指定位置的元素值设置指定位置的元素值StatusCode Delete(int position,elemType&e);/删除元素删除元素StatusCode Insert(int position,const elemType&e);/插入元素插入元素SqList(const SqList©);/复制构造函数复制构造函数SqList&operator=(const SqList©);/赋值语句重载赋值语句重载;1414n 指在表的第指在表的第i(1 i n+1)个位置上，插入个位置上，插入一个新结点一个新结点x，使长度为使长度为n的线性表变为长的线性表变为长度

12、为度为n+1的线性表：的线性表：（a1,a2,ai-1,ai,an）（a1,a2,ai-1,x,ai,an）1、插入插入三、顺序表的基本操作三、顺序表的基本操作程序实现见文件夹程序实现见文件夹test_sq_list151525 34 57 16 48 09 63 1 2 3 4 5 6 7 8data25 34 57 16 48 09 63 1 2 3 4 5 6 7 8data50例如：在例如：在i=4的位置插入的位置插入 x=50i09 634816序号序号序号序号1616template StatusCode SqList:Insert(int position,const ElemT

13、ype&e)/操作结果：在线性表的第操作结果：在线性表的第position个位置前插入元素个位置前插入元素e,/position的的取值范围为的的取值范围为1positionLength()+1/如线性表已满如线性表已满,则返回则返回OVER_FLOW,/如如position合法合法,则返回则返回SUCCESS,否则函数返回否则函数返回/RANGE_ERRORint len=Length();ElemType tmp;ElemType tmp;插入算法插入算法1717if(Full()/线性表已满返回线性表已满返回OVER_FLOWreturn OVER_FLOW;else if(positi

14、on len+1)/position范围错范围错return RANGE_ERROR;插入算法插入算法1818 else else /成功成功成功成功count+;count+;/插入后元素个数将自增插入后元素个数将自增插入后元素个数将自增插入后元素个数将自增1 1for(int curPosition=len;for(int curPosition=len;curPosition=position;curPosition-)curPosition=position;curPosition-)/插入位置之后的元素右移插入位置之后的元素右移插入位置之后的元素右移插入位置之后的元素右移GetEle

15、m(curPosition,tmp);GetElem(curPosition,tmp);SetElem(curPosition+1,tmp);SetElem(curPosition+1,tmp);SetElem(position,e);SetElem(position,e);/将将将将e e赋值到赋值到赋值到赋值到positionposition位置处位置处位置处位置处return SUCCESS;return SUCCESS;/插入成功插入成功插入成功插入成功 插入算法插入算法1919 上述算法上述算法for循环语句的执行次数为循环语句的执行次数为n-i+1；若若i=1，需移动全部，需移动全

16、部n个结点（最坏：个结点（最坏：O(n)）若若i=n+1（在表尾插入），无需移动结点，直接（在表尾插入），无需移动结点，直接插入即可。（最好插入即可。（最好:O(1)）移动结点的平均次数：移动结点的平均次数：插入算法分析插入算法分析2020 按等概率考虑：按等概率考虑：可能的插入位置为可能的插入位置为i=1,2,n,n+1共共n+1个，个，则则pi=1/(n+1)顺序表插入算法平均约需移动一半结点。顺序表插入算法平均约需移动一半结点。插入算法分析插入算法分析2121 将线性表的第将线性表的第i(1 i n)个结点删除，个结点删除，使使长度为长度为n的线性表变为长度为的线性表变为长度为n-1的线

17、性表：的线性表：（a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an）2、删除删除222225 34 57 50 16 48 09 63 1 2 3 4 5 6 7 8data1625 34 57 50 16 48 09 63 1 2 3 4 5 6 7 8data例如：删除第例如：删除第 i个元素，个元素，i=548 09 63 i序号序号序号序号2323template template StatusCode SqList:Delete(int position,StatusCode SqList:Delete(int position,ElemType&e

18、)ElemType&e)/操作结果：删除线性表的第操作结果：删除线性表的第操作结果：删除线性表的第操作结果：删除线性表的第positionposition个位置的元素个位置的元素个位置的元素个位置的元素,并且并且并且并且/用用用用e e返回其值返回其值返回其值返回其值,position,position的的取值范围为的的取值范围为的的取值范围为的的取值范围为/1positionLength(),position1positionLength(),position合法时函数返回合法时函数返回合法时函数返回合法时函数返回/SUCCESS,SUCCESS,否则函数返回否则函数返回否则函数返回否则函数

19、返回RANGE_ERRORRANGE_ERROR int len=Length();int len=Length();ElemType tmp;ElemType tmp;if(position len)if(position len)/position/position范围错范围错范围错范围错return RANGE_ERROR;return RANGE_ERROR;2、删除算法删除算法2424elseelse/position/position合法合法合法合法GetElem(position,e);GetElem(position,e);/用用用用e e返回被删除元素的值返回被删除元素的值返

20、回被删除元素的值返回被删除元素的值for(int curPosition=position+1;for(int curPosition=position+1;curPosition=len;curPosition+)curPosition=len;curPosition+)/被删除元素之后的元素依次左移被删除元素之后的元素依次左移被删除元素之后的元素依次左移被删除元素之后的元素依次左移GetElem(curPosition,tmp);GetElem(curPosition,tmp);SetElem(curPosition-1,tmp);SetElem(curPosition-1,tmp);co

21、unt-;count-;/删除后元素个数将自减删除后元素个数将自减删除后元素个数将自减删除后元素个数将自减1 1return SUCCESS;return SUCCESS;2、删除算法删除算法2525 上述算法上述算法for循环语句的执行次数为循环语句的执行次数为n-i;若若i=1，最坏：，最坏：O(n)若若i=n，无需用移动结点，直接删除即可。，无需用移动结点，直接删除即可。（最好（最好O(1)）移动结点的平均次数：移动结点的平均次数：2、删除算法分析删除算法分析2626 按等概率考虑：按等概率考虑：可能的删除位置为可能的删除位置为i=1,2,n共共n个，个，则则qi=1/n顺序表删除算法平

22、均约需移动一半结点。顺序表删除算法平均约需移动一半结点。2、删除算法分析删除算法分析2727四、顺序表的优缺点四、顺序表的优缺点 优点：优点：无须为表示节点间的逻辑关系而增加额外的存储空间无须为表示节点间的逻辑关系而增加额外的存储空间 逻辑相邻，物理相邻逻辑相邻，物理相邻;可随机存取任一元素可随机存取任一元素 缺点缺点:插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素 要求占用连续的存储空间，存储分配只能预先进行要求占用连续的存储空间，存储分配只能预先进行 预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间分配，利用不充分2828五、顺序表的应用五、顺序表的应用1

23、 1、设计顺序表存储的两个集合求差集的算法、设计顺序表存储的两个集合求差集的算法、设计顺序表存储的两个集合求差集的算法、设计顺序表存储的两个集合求差集的算法25 33 57 50 16 48 09 63 1 2 3 4 5 6 7 8la12 50 23 79 04 34 25 13 lblc程序实现见文件夹程序实现见文件夹s2_1292925 33 57 50 16 48 09 63 1 2 3 4 5 6 7la12 50 23 79 04 34 25 13 lblc下标下标aPositionbPosition3030/文件路径名文件路径名文件路径名文件路径名:s2_1alg.h:s2_1

24、alg.h template template void Difference(const SqList&la,const void Difference(const SqList&la,const SqList&lb,SqList&lc)SqList&lb,SqList&lc)/操作结果操作结果操作结果操作结果:用用用用lclc返回返回返回返回lala和和和和lblb表示的集合的差集表示的集合的差集表示的集合的差集表示的集合的差集/方法方法方法方法:在在在在lala中取出元素中取出元素中取出元素中取出元素,在在在在lblb中进行查找中进行查找中进行查找中进行查找,如果未在如果未在如果未在如果

25、未在lblb中中中中/出现了出现了出现了出现了,将其插入到将其插入到将其插入到将其插入到lclc ElemType aItem,bItem;ElemType aItem,bItem;lc.Clear();lc.Clear();/清空清空清空清空lclc算法实现算法实现3131for(int aPosition=1;aPosition=la.Length();for(int aPosition=1;aPosition=la.Length();aPosition+)aPosition+)la.GetElem(aPosition,aItem);la.GetElem(aPosition,aItem);

26、/取出取出取出取出lala的一个元素的一个元素的一个元素的一个元素aItemaItembool isExist=false;bool isExist=false;/表示表示表示表示aItemaItem是否在是否在是否在是否在lblb中出现中出现中出现中出现for(int bPosition=1;bPosition=for(int bPosition=1;bPosition=lb.Length();bPosition+)lb.Length();bPosition+)lb.GetElem(bPosition,bItem);lb.GetElem(bPosition,bItem);/取出取出取出取出l

27、blb的一个元素的一个元素的一个元素的一个元素bItembItem算法实现算法实现3232if(aItem=bItem)if(aItem=bItem)isExist=true;isExist=true;/aItem/aItem同时在同时在同时在同时在lala和和和和lblb中中中中/出现出现出现出现,置置置置isExistisExist为为为为truetruebreak;break;/退出内层循环退出内层循环退出内层循环退出内层循环 if(!isExist)if(!isExist)/aItem/aItem在在在在lala中出现中出现中出现中出现,而未在而未在而未在而未在lblb中未出现中未出现

28、中未出现中未出现,/将其插入到将其插入到将其插入到将其插入到lclc中中中中lc.Insert(lc.Length()+1,aItem);lc.Insert(lc.Length()+1,aItem);算法实现算法实现3333五、顺序表的应用五、顺序表的应用2 2、已知顺序表、已知顺序表、已知顺序表、已知顺序表lala的元素类型为的元素类型为的元素类型为的元素类型为intint，设计算法，设计算法，设计算法，设计算法讲其调整为左右两部分，左边的所有元素为奇讲其调整为左右两部分，左边的所有元素为奇讲其调整为左右两部分，左边的所有元素为奇讲其调整为左右两部分，左边的所有元素为奇数，右边的为偶数，要求

29、数，右边的为偶数，要求数，右边的为偶数，要求数，右边的为偶数，要求T(nT(n)=)=O(nO(n)。中科院研究所中科院研究所中科院研究所中科院研究所20012001年考研题年考研题年考研题年考研题程序实现见文件夹程序实现见文件夹s2_234341 2 3 4 5 6 7 8laleftPositionrightPosition25 34 57 50 16 48 09 6225 34 57 50 16 48 09 62laleftPositionrightPosition25 34 57 50 16 48 09 62laleftPositionrightPosition353525 34 57

30、 50 16 48 09 62laleftPositionrightPosition0934交换交换25 09 57 50 16 48 34 62laleftPositionrightPositionleftPositionrightPosition25 09 57 50 16 48 34 62laleftPositionrightPositionrightPositionleftPosition3636/文件路径名文件路径名文件路径名文件路径名:s2_2alg.h:s2_2alg.h void Adjust(SqList&la)void Adjust(SqList&la)/操作结果操作结果操

31、作结果操作结果:将将将将lala调整为左右两部分，调整为左右两部分，调整为左右两部分，调整为左右两部分，/左边所有元素为奇数，右边所有元素为偶数左边所有元素为奇数，右边所有元素为偶数左边所有元素为奇数，右边所有元素为偶数左边所有元素为奇数，右边所有元素为偶数/并要求时间复杂度为并要求时间复杂度为并要求时间复杂度为并要求时间复杂度为O(n)O(n)int leftPosition=1,rightPosition=la.length();int leftPosition=1,rightPosition=la.length();int aItem,bItem;int aItem,bItem;算法实现

32、算法实现3737 while(leftPositionrightPosition)while(leftPositionrightPosition)la.GetElem(leftPosition,aItem);la.GetElem(leftPosition,aItem);lb.GetElem(rightPosition,bItem);lb.GetElem(rightPosition,bItem);if(aItem%2=1)if(aItem%2=1)leftPosition+;leftPosition+;else if(bItem%2=0)else if(bItem%2=0)rightPositi

33、on-;rightPosition-;else else la.SetElem(leftPosition+,bItem);la.SetElem(leftPosition+,bItem);lb.SetElem(rightPosition-,aItem);lb.SetElem(rightPosition-,aItem);算法实现算法实现3838类似：类似：北京理工大学北京理工大学北京理工大学北京理工大学20002000年考研题年考研题年考研题年考研题 算法题（本题算法题（本题算法题（本题算法题（本题8 8分）分）分）分）已知数组已知数组已知数组已知数组A1.nA1.n的元素类型为整形，设计算的元素

34、类型为整形，设计算的元素类型为整形，设计算的元素类型为整形，设计算法调整法调整法调整法调整A A，使其左边的所有元素小于零，右边，使其左边的所有元素小于零，右边，使其左边的所有元素小于零，右边，使其左边的所有元素小于零，右边的所有元素大于等于零（要求算法的时间复杂的所有元素大于等于零（要求算法的时间复杂的所有元素大于等于零（要求算法的时间复杂的所有元素大于等于零（要求算法的时间复杂度为度为度为度为OO（n n）。）。）。）。39393、经典问题：约瑟夫环问题、经典问题：约瑟夫环问题 n n个人围成一圈，从第个人围成一圈，从第个人围成一圈，从第个人围成一圈，从第s s个人开始报数，报到个人开始报

35、数，报到个人开始报数，报到个人开始报数，报到mm的人出列，从下一个人再重新报数，报到的人出列，从下一个人再重新报数，报到的人出列，从下一个人再重新报数，报到的人出列，从下一个人再重新报数，报到mm的人出列，如此下去，直至所有人都出列。试的人出列，如此下去，直至所有人都出列。试的人出列，如此下去，直至所有人都出列。试的人出列，如此下去，直至所有人都出列。试编写算法，输出出列人的编号。编写算法，输出出列人的编号。编写算法，输出出列人的编号。编写算法，输出出列人的编号。程序实现见文件夹程序实现见文件夹s2_Joseph4040 算法思想：算法思想：算法思想：算法思想：（1 1）把）把）把）把n n个

36、人看成一个环。个人看成一个环。个人看成一个环。个人看成一个环。（2 2）设当前有）设当前有）设当前有）设当前有 i i 个人，下一出列的人为个人，下一出列的人为个人，下一出列的人为个人，下一出列的人为s s。s=s=（s+m-1s+m-1）%i%i（3 3）将出列的人删除。）将出列的人删除。）将出列的人删除。）将出列的人删除。123456789s=1i=94141123456789s=1s=(s+m-1)%i i=9 m=4for(j=s;j=i-1;j+)L.elemj=L.elemj+1;4print4242123456789n=9i=9123456789s=（s+m-1）%im=4s=1

37、4print123567894t=4计算出计算出s=41 2 3 4 5 6 7 8 9434312356789i减减1i=8i=8123567894s=（s+m-1）%im=4s=4t=4计算出计算出s=7812356794t=8123567984i减减1i=71 2 3 4 5 6 7 8 94444123567984i=7s=（s+m-1）%im=4s=7计算出计算出s=312567984t=33125679384i减减1i=61 2 3 4 5 6 7 8 94545125679384i=6s=（s+m-1）%is=3m=4计算出计算出s=012567384t=99125679384i

38、减减1i=5则则 s=i 即即s=61 2 3 4 5 6 7 8 94646125679384i=5s=（s+m-1）%is=6m=4计算出计算出s=4125793846i减减1i=4t=61257693841 2 3 4 5 6 7 8 94747i=41257693841 2 3 4 5 6 7 8 9s=（s+m-1）%is=4m=4计算出计算出s=3i=3127569384s=（s+m-1）%is=3m=4计算出计算出s=0则则 s=i 即即s=3i=2127569384s=（s+m-1）%is=3m=4计算出计算出s=0则则 s=i 即即s=2i=11275693844848/文件

39、路径名文件路径名文件路径名文件路径名:s2_Josephalg.h:s2_Josephalg.h void Joseph(SqList&la)void Joseph(SqList&la)/约瑟夫环问题约瑟夫环问题约瑟夫环问题约瑟夫环问题 int Start=1;/从从1号开始报数号开始报数int Mima=4;/密码是密码是4int tmp,tmp2;int i,j;算法实现算法实现4949for(i=la.Length();i1;i-)for(i=la.Length();i1;i-)Start=(Start+Mima-1)%i;Start=(Start+Mima-1)%i;if(Start=

40、0)if(Start=0)/余数为余数为余数为余数为0 0Start=i;Start=i;la.GetElem(Start,tmp);la.GetElem(Start,tmp);for(j=Start;j=i-1;j+)for(j=Start;j=i-1;j+)la.GetElem(j+1,tmp2);la.GetElem(j+1,tmp2);la.SetElem(j,tmp2);la.SetElem(j,tmp2);la.SetElem(i,tmp);la.SetElem(i,tmp);算法实现算法实现5050本本 讲讲 小小 结结重点：重点：1、线性表的基本概念、线性表的基本概念 2、顺序

41、表的存储、顺序表的存储难点：难点：1、顺序表的插入、删除算法、顺序表的插入、删除算法 2、顺序表的应用、顺序表的应用5151Homework:1 1、程序填空：本算法用线性表的顺序存储模、程序填空：本算法用线性表的顺序存储模式实现两个顺序表的并集。式实现两个顺序表的并集。2 2、程序填空：已知、程序填空：已知la la、lb lb和和lc lc为为3 3个元素值递个元素值递增有序的顺序表，本算法实现了对表增有序的顺序表，本算法实现了对表la la作如作如下运算：删去那些既在下运算：删去那些既在lb lb中出现又在中出现又在lc lc中出现中出现的元素。的元素。参见文件参见文件:02-1:02-1讲顺序表作业讲顺序表作业.pdfpdf将算法代码抄写到作业本上，并填空。将算法代码抄写到作业本上，并填空。52525353