第二章 线性表及其顺序存储结构1.ppt

《第二章 线性表及其顺序存储结构1.ppt》由会员分享，可在线阅读，更多相关《第二章 线性表及其顺序存储结构1.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章第二章第二章 线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构1 1引引 言言线性表是一种线性数据结构，其用线性表是一种线性数据结构，其用途非常广泛，可用于信息检索、存途非常广泛，可用于信息检索、存储管理、模拟技术和通信等领域。储管理、模拟技术和通信等领域。2 2第二章第二章 l知知 识识 点点 n n线性数据结构的基本特征和基本运算线性数据结构的基本特征和基本运算n n顺序存储结构顺序存储结构n n线性数据结构的简单应用线性数据结构的简单应用 l难难 点点 n n利利用用本本章章的的基基本本知知识识，设设计计有有效效的的算算法法，解解决与线

2、性相关的应用问题决与线性相关的应用问题 3 3线性表线性表l要要 求求 n n 熟练掌握以下内容：熟练掌握以下内容：uu线性表的基本运算线性表的基本运算n n 了解以下内容：了解以下内容：uu线性表运算时间复杂性分析线性表运算时间复杂性分析4 4第第二二章章 目录目录2.1 线性表的基本概念 2.2 栈及其应用2.5 队列及其应用2.6 字符串小 结习题与练习5 5第二章第二章 线性表线性表l逻辑结构逻辑结构l关系关系-线性线性l存储结构存储结构-顺序存储顺序存储-顺序表顺序表6 6 2.1.12.1.1 线性表的基本概念线性表的基本概念 l线性表:是是n n个个(表表长长n0)n0)同同类类

3、型型数数据据元元素素的的有有限限序序列列。元元素素间间是是线线性性逻逻辑辑关关系系，排排成成线线性性序序列。列。线性体现在前后件关系上线性体现在前后件关系上。记作：记作：记作：记作：(a(a1 1，a a2 2，a an n)l特点：vv有且仅有一个根结点，它无前件；有且仅有一个根结点，它无前件；vv有且仅有一个终端结点，它无后件；有且仅有一个终端结点，它无后件；vv除根结点外，每个结点只有一个除根结点外，每个结点只有一个前件前件；vv除尾结点外，每个结点只有一个除尾结点外，每个结点只有一个后件后件。vvn n0 0的线性表为的线性表为空表空表。predecessorpredecessorsu

4、ccessorsuccessor7 7线性表实例线性表实例l 英文字母表：(A，B，C，D，X，Y，Z)l 某校1998-2003年计算机数量 (50，100，250，300，500，1200)l 学生信息表序号序号序号序号学号学号学号学号姓名姓名姓名姓名性别性别性别性别英语英语英语英语英语英语英语英语英语英语英语英语01010101990301990301990301990301李晓明李晓明李晓明李晓明男男男男数学数学数学数学数学数学数学数学数学数学数学数学02020202990302990302990302990302张国庆张国庆张国庆张国庆男男男男物理物理物理物理物理物理物理物理物理物理

5、物理物理30303030990330990330990330990330王薇薇王薇薇王薇薇王薇薇女女女女868686868686868686868686体现在体现在顺序关系上顺序关系上记录排列为记录排列为顺序关系顺序关系8 8线性表的基本运算线性表的基本运算 Length(L)Length(L)Get(1Get(1，i)i)Modify(LModify(L，i)i)Delete(LDelete(L，i)i)Insert(LInsert(L，i i，x)x)Sort(LSort(L，key)key)Index(LIndex(L，x)x)其中：其中：其中：其中：L-L-L-L-表，表，表，表，i-

6、i-i-i-位序，位序，位序，位序，x-x-x-x-数据元素数据元素数据元素数据元素 复杂运算复杂运算复杂运算复杂运算线性表的合并；对有序表的插入、删除等线性表的合并；对有序表的插入、删除等线性表的合并；对有序表的插入、删除等线性表的合并；对有序表的插入、删除等9 92.1.22.1.2 线性表的顺序存储结构线性表的顺序存储结构 l顺序存储结构(SequentialMapping)用用内内存存中中一一组组地地址址连连续续的的单单元元依依次次存存放放表表中中元元素素，每个元素的存储空间大小相同。每个元素的存储空间大小相同。n n计算元素计算元素 a ai i 的地址的地址 假假设设每每个个元元素

7、素占占k k个个字字节节，首首元元素素的的地地址址为为ADR(aADR(a1 1)，则则有有:l顺序存储结构是一种随机存取结构。顺序存储结构是一种随机存取结构。l在高级语言环境中，常用一维数组来存储线性表。在高级语言环境中，常用一维数组来存储线性表。ADR(ai)=ADR(a1)+(i-1)k10102.1.2 2.1.2 2.1.2 2.1.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构-顺序表顺序表顺序表顺序表长度为长度为n n的线性表的线性表:(a:(a1 1，a a2 2，a ai i，a an n).).顺序存储结构为顺序存储结构为:1111有一

8、个长度为有一个长度为8 8的线性表的线性表(29,18,56,63,35,24,31,47)(29,18,56,63,35,24,31,47)例如例如:1212顺序表类声明顺序表类声明l为更好体现信息隐蔽原则和数据抽象原则，把线性表封装起来。(使用类模板)templateclasssq_LListprivate:intm;/存储空间容量存储空间容量存储空间容量存储空间容量intn;/顺序表的长度顺序表的长度顺序表的长度顺序表的长度T*V;/顺序表存储空间首指针顺序表存储空间首指针顺序表存储空间首指针顺序表存储空间首指针;Vmmnn1313线性表类声明线性表类声明ltemplatetemplat

9、eclassclasssq_LListsq_LListpublic:public:sq_LListsq_LList()m=0;n=0()m=0;n=0sq_LListsq_LList(intint););VoidVoidPrt_sq_LListPrt_sq_LList();();intint flag_sq_LListflag_sq_LList()const;()const;VoidVoidIns_sq_LListIns_sq_LList(intint,T);,T);VoidVoidDel_sq_LListDel_sq_LList(intint););14142.1.3 2.1.3 线性表的基

10、本运算线性表的基本运算l 插入插入 l 删除删除 1515 a a a a0 0 0 0 a a a a1 1 1 1 a a a ai i i i1 1、数据元素的插入数据元素的插入l 插入操作插入操作插入操作插入操作 lins_sq_Listins_sq_Listins_sq_Listins_sq_List(T(T(T(T*V,int*V,int*V,int*V,int m,intm,intm,intm,int *n,int*n,int*n,int*n,int i,T x)i,T x)i,T x)i,T x)：在表中下标为在表中下标为在表中下标为在表中下标为i i i i的元素的元素的元素

11、的元素a a a ai i i i后后后后插入插入插入插入x x x x。后移后移后移后移n-i-1n-i-1n-i-1n-i-1个元素个元素个元素个元素0 1 0 1 0 1 0 1 i i+1 i+2 i i+1 i+2 i i+1 i+2 i i+1 i+2 n-1 n-1 n-1 n-1 m m m m-1-1-1-1a a a an-1n-1n-1n-1x xa a a ai+1i+1i+1i+1操作演示操作演示n-11616插入插入算法算法描述描述l（新元素插入到位置（新元素插入到位置 i i 之后处）之后处）n n 边界情况处理边界情况处理uu存储空间满存储空间满(nn=mmnn

12、=mm)，“上溢上溢”，不能插入，结，不能插入，结束束uu 若若 i i nnnn 时，插到表尾元素之后；时，插到表尾元素之后；(最后一个元最后一个元素素)uu 若若 i 1 i 1 时，插到首元素时，插到首元素(第第1 1个元素个元素)之前。之前。n n将尾元素将尾元素nn-1nn-1至至i+1i+1元素元素逐一逐一向后移动一个位置。向后移动一个位置。n n将新元素插入到第将新元素插入到第i i1 1的位置上，并将顺序表长度增的位置上，并将顺序表长度增加加1 1。1717顺序表的插入顺序表的插入(C+(C+描述描述)templatetemplateVoidVoidsq_LListsq_LLi

13、st:ins_sq_LListins_sq_LList(intinti,Tx)i,Tx)intintk;k;if(if(nnnn=mm)=mm)coutcoutOverFlowOverFlowendlendl;retrunretrun;if(i0)i=0;if(inn-1)i=if(inn-1)i=nnnn;for(for(intintk=nn-1;k=i;k-)vk+1=vk;k=nn-1;k=i;k-)vk+1=vk;vk=x;vk=x;n+;n+;return;return;18182 2、数据元素的删除、数据元素的删除 aia0ai-1l删除操作删除操作Delete(i)：删除元素删除

14、元素ai。前移前移n-i-1个元素个元素0i-1ii+1n-1m-1an-1删除它删除它ai+1ain-1操作演示操作演示1919删除删除l 算法描述（删除位置为i 元素）n n 边界情况处理uu 若存储空间空，为“下溢”，无删除，返回；uu 若 i n-1 时，待删除元素不在表中，无删除操作，返回；n n将表中i+1元素至尾元素逐一向前移动一个位置，并将顺序表长度减少1，返回。2020顺序表的删除顺序表的删除(C+C+描述描述)templatetemplateboolbool sq_LListsq_LList:Del_sq_LListDel_sq_LList(intinti)i)intint

15、k;k;if(nn=0)if(nn=0)coutcoutUnderFlowUnderFlowendlendl;return;return;if(inn-1)if(inn-1)coutcout“NotThisElement“NotThisElementendlendl;return;return;for(for(intintk=i+1;kk=i+1;knnnn;k+)vk-1=vk;k+)vk-1=vk;nnnn-;-;return;return;2121例例2.3 2.3 建立容量为建立容量为100100的空顺序表，表中的空顺序表，表中能插入多个新元素，也能删除若干元素，能插入多个新元素，也能

16、删除若干元素，并能顺序输出表中所有元素并能顺序输出表中所有元素l 线性表完整程序:l 书上P33-P34l C+程序22223 3、时间复杂度分析、时间复杂度分析 l在在在在顺顺顺顺序序序序存存存存储储储储结结结结构构构构的的的的线线线线性性性性表表表表中中中中插插插插入入入入或或或或删删删删除除除除一一一一个个个个元元元元素素素素，其其其其时时时时间间间间主主主主要要要要耗耗耗耗费费费费在在在在元元元元素素素素移移移移动动动动上上上上，其其其其次次次次数数数数取取取取决决决决于于于于插插插插入或删除元素的位置。入或删除元素的位置。入或删除元素的位置。入或删除元素的位置。l假设假设假设假设：P

17、 Pi i：表示表示表示表示在第在第在第在第i i个元素之后插入一个元素的概率个元素之后插入一个元素的概率个元素之后插入一个元素的概率个元素之后插入一个元素的概率nn：表示线性表长度表示线性表长度表示线性表长度表示线性表长度 则，插入一个元素需移动元素的平均次数为：则，插入一个元素需移动元素的平均次数为：则，插入一个元素需移动元素的平均次数为：则，插入一个元素需移动元素的平均次数为：n-1n-1A Ainsins P Pi i(n-i)(n-i)P Pi i*n+(n-1)+(n-2)+1*n+(n-1)+(n-2)+1i=0i=02323 时间复杂度分析时间复杂度分析假设假设假设假设：QQi

18、 i：是：是：是：是删除第删除第删除第删除第i i个元素的概率，个元素的概率，个元素的概率，个元素的概率，nn：为线性表的长度为线性表的长度为线性表的长度为线性表的长度则，删除一个元素时需移动元素的平均次数为：则，删除一个元素时需移动元素的平均次数为：则，删除一个元素时需移动元素的平均次数为：则，删除一个元素时需移动元素的平均次数为：n-1n-1A Adeldel QQi i(n-i-1)(n-i-1)i=0i=02424时间复杂度分析时间复杂度分析l如如如如果果果果在在在在线线线线性性性性表表表表的的的的任任任任何何何何位位位位置置置置插插插插入入入入或或或或删删删删除除除除元元元元素素素素

19、的的的的概概概概率率率率相相相相等，等，等，等，即即即即:P P P Pi i i i1/n1/n1/n1/n；Q Q Q Qi i i i 1/n1/n；则则则则:可见可见:在顺序表中插入或删除一个元素时，平均要移动在顺序表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。表中大约一半的数据元素。若表长为若表长为n n，前两个算法的时间复杂度为，前两个算法的时间复杂度为O(n)O(n)。25251 1、线性表采用顺序存储结构操作时，需线性表采用顺序存储结构操作时，需 大量移动数据元素，效率较低。大量移动数据元素，效率较低。2 2、由于是静态存储结构，需预先定义大由于是静态存储结构，需

20、预先定义大 小确定的数组，容量有限。小确定的数组，容量有限。3 3、适于直接适于直接(随机随机)存取操作。存取操作。结论结论结论结论26262.2 2.2 2.2 2.2 栈及其应用栈及其应用栈及其应用栈及其应用27272.2.1 2.2.1 栈的概念栈的概念l 栈（stackstack）的定义 栈栈是限定在一端进行插入或删除操作的线性表。是限定在一端进行插入或删除操作的线性表。是限定在一端进行插入或删除操作的线性表。是限定在一端进行插入或删除操作的线性表。先进后出先进后出(FirstInLastOut)的线性表的线性表 栈底栈顶进栈进栈出栈出栈a1a4a2a3NULL堆栈堆栈a528282.

21、22.22.22.2.1 .1 .1 .1 什么是栈什么是栈什么是栈什么是栈n n允许插入与删除的一允许插入与删除的一允许插入与删除的一允许插入与删除的一端称为端称为端称为端称为栈顶栈顶，n n不允许插入与删除的不允许插入与删除的不允许插入与删除的不允许插入与删除的另一端称为另一端称为另一端称为另一端称为栈底栈底。n n用指针用指针用指针用指针toptop来指示来指示来指示来指示栈栈栈栈顶顶顶顶的位置。的位置。的位置。的位置。n n用指针用指针用指针用指针bottombottom指向指向指向指向栈底栈底栈底栈底。29292.22.22.22.2.1 .1 .1 .1 什么是栈什么是栈什么是栈什

22、么是栈u栈是栈是“先进后出先进后出”表表 (FILO)(FILO)u栈是栈是“后进先出后进先出”表表 (LIFO)(LIFO)u栈具有记忆作用。栈具有记忆作用。30302.2.2 2.2.2 栈的顺序存储及运算栈的顺序存储及运算l栈的顺序存储结构（顺序栈）顺序栈）用一维数组来实现。用一维数组来实现。用一维数组来实现。用一维数组来实现。l当当当当toptop等于最大下标值时为栈满。等于最大下标值时为栈满。等于最大下标值时为栈满。等于最大下标值时为栈满。3131栈的基本运算栈的基本运算1.1.PUSHPUSH:往栈中插入一个元素称往栈中插入一个元素称为为入栈入栈运算运算2.2.POP:POP:从栈

23、中删除一个元素从栈中删除一个元素(即即删除栈顶元素删除栈顶元素)称为称为退栈退栈运运算。算。3.3.TOP:TOP:取栈顶元素取栈顶元素32322.2.2 2.2.2 栈的基本运算和操作栈的基本运算和操作 l lInitStackInitStack(S)(S)，初始化操作，设定一个空栈。初始化操作，设定一个空栈。初始化操作，设定一个空栈。初始化操作，设定一个空栈。l lEmptyStackEmptyStack(S)(S)，判空栈操作判空栈操作判空栈操作判空栈操作,返回值逻辑值。返回值逻辑值。返回值逻辑值。返回值逻辑值。l lPush(SPush(S，x)x)，入栈操作，在入栈操作，在入栈操作，

24、在入栈操作，在S S栈顶插入一个元素栈顶插入一个元素栈顶插入一个元素栈顶插入一个元素x x。l lPop(S)Pop(S)，出栈操作，若栈出栈操作，若栈出栈操作，若栈出栈操作，若栈S S不空在栈顶删除一个元素。不空在栈顶删除一个元素。不空在栈顶删除一个元素。不空在栈顶删除一个元素。l lGetTopGetTop(S)(S)，取栈顶元素，若栈取栈顶元素，若栈取栈顶元素，若栈取栈顶元素，若栈S S不空则取栈顶元素的值。不空则取栈顶元素的值。不空则取栈顶元素的值。不空则取栈顶元素的值。l lClearStackClearStack(S)(S)，清栈空操作。清栈空操作。清栈空操作。清栈空操作。l lC

25、urrentSizeCurrentSize(S)(S)，求当前栈中元素的个数。求当前栈中元素的个数。求当前栈中元素的个数。求当前栈中元素的个数。l lDestroyStackDestroyStack(S)(S)，销毁销毁销毁销毁S S栈。栈。栈。栈。33332.2.3 2.2.3 顺序栈类（顺序栈类（C+C+描述）描述）l栈类模板声明：templateclassStackpublic:virtualboolflag()const=0;virtualboolreadTop(T)const=0;virtualboolpush(T)=0;virtualboolpop()=0;virtualboolp

26、rint()const=0;3434ll 2.2.3 2.2.3 顺序栈类（顺序栈类（C+C+描述）描述）templatetemplateclassclassSqStackSqStack:publicStack:publicStackprivate:private:intintmm;mm;/栈容量栈容量栈容量栈容量intinttop;top;/总是指向栈顶元素总是指向栈顶元素总是指向栈顶元素总是指向栈顶元素TT*s*s;/线性表指针线性表指针线性表指针线性表指针 public:public:Sq_StackSq_Stack(intint););voidvoidPrt_sq_stackPrt_s

27、q_stack()()intint falg_sq_stackfalg_sq_stack();();voidvoidins_sq_stackins_sq_stack(T);(T);TTdel_sq_stackdel_sq_stack();();TTread_sq_stackread_sq_stack();();Push(T)Pop()top()3535 /入栈入栈templatetemplatevoidvoidsq_stacksq_stack:ins_sq_stackins_sq_stack(Tx)(Tx)if(if(top=mmtop=mm)/存储空间已满，上溢错误存储空间已满，上溢错误存储

28、空间已满，上溢错误存储空间已满，上溢错误 coutcoutstackoverflow!stackoverflow!endlendl;return;return;top=top+1;top=top+1;/栈顶指针进栈顶指针进栈顶指针进栈顶指针进1 1stop-1=x;stop-1=x;/新元素入栈新元素入栈新元素入栈新元素入栈return;return;3636 退栈退栈 template template T T sq_stacksq_stack:del_sq_stackdel_sq_stack()()T y;T y;if(top=0)if(top=0)/栈为空，下溢错误栈为空，下溢错误 co

29、utcout stack underflow!stack underflow!endlendl;return(0);return(0);y=sy=stop-1;top-1;/将栈顶元素赋给指定的变量将栈顶元素赋给指定的变量y y top=top-1;top=top-1;/栈顶指针退栈顶指针退1 1 return(y);return(y);/返回退出栈的元素返回退出栈的元素 3737 读栈顶元素读栈顶元素template T sq_stack:read_sq_stack()if(top=0)/栈为空 cout stack empty!endl;return(0);return(stop-1);/

30、返回栈顶元素3838例2.4：建立容量为10的空栈，将50、60、70、80、90、100入栈，然后输出栈顶指针与栈中的元素。l书中P41-P42lC+程序本课完39392.2.4 2.2.4 表达式计算表达式计算l表达式：由操作数、操作符和界限符组成。l分类：n n中缀式：操作符在两个操作数之间的表达式，中缀式：操作符在两个操作数之间的表达式，中缀式：操作符在两个操作数之间的表达式，中缀式：操作符在两个操作数之间的表达式，如：如：如：如：a/(bc)+d*ea/(bc)+d*en n前缀式：操作符在两个操作数之前的表达式，前缀式：操作符在两个操作数之前的表达式，前缀式：操作符在两个操作数之前

31、的表达式，前缀式：操作符在两个操作数之前的表达式，如：如：如：如：+/abc*de+/abc*den n后缀式：操作符在两个操作数之后的表达式后缀式：操作符在两个操作数之后的表达式后缀式：操作符在两个操作数之后的表达式后缀式：操作符在两个操作数之后的表达式（波兰表达式），如：（波兰表达式），如：（波兰表达式），如：（波兰表达式），如：abcabc-/de*+-/de*+4040表达式计算表达式计算l表达式的优先级表达式的优先级表表表表2-1 2-1 2-1 2-1 操作符的优先级操作符的优先级操作符的优先级操作符的优先级操作符操作符操作符操作符 优先级优先级优先级优先级-,!7-,!7-,!7

32、-,!7*,/,%6*,/,%6*,/,%6*,/,%6+,-5+,-5+,-5+,-5,=4,=4,=4,=4=,!=3=,!=3=,!=3=,!=3&2&2&2&2|1|1|1|14141例：中缀表达式及其对应的后缀表达式例：中缀表达式及其对应的后缀表达式例：中缀表达式及其对应的后缀表达式例：中缀表达式及其对应的后缀表达式a*b+ca*b+ca*b/ca*b/ca*b*c*d*e*fa*b*c*d*e*fa+(b*c+d)/ea+(b*c+d)/ea*(b+c)/(d-e)-f)a*(b+c)/(d-e)-f)a/(b-c)+d*ea/(b-c)+d*eab*c+ab*c+ab*cab*c

33、/ab*c*d*e*f*ab*c*d*e*f*abc*d+eabc*d+e/+/+abc+deabc+de-/f-*-/f-*abcabc-/de*+-/de*+表表2.2 2.2 中缀表达式和后缀表达式中缀表达式和后缀表达式中缀表达式中缀表达式后缀表达式后缀表达式4242 若是运算符，则：若是运算符，则：若（该运算符若（该运算符=;=;）&（top-top-运算符运算符=;=;），），则结束整个表达式的计算；则结束整个表达式的计算；若（该运算符若（该运算符 topptopp-运算符），则将该运运算符），则将该运算符压入运算符栈；算符压入运算符栈；否则，则从操作数栈连续弹出两个操作数，否则，则

34、从操作数栈连续弹出两个操作数，从运算符栈弹出从运算符栈弹出topptopp-运算符，做相应计算后，运算符，做相应计算后，将结果压入操作数栈；（注：当前读出的运算将结果压入操作数栈；（注：当前读出的运算符下次不再重读）。符下次不再重读）。4444A A A AB*CB*CB*CB*CD/ED/ED/ED/E计算过程计算过程计算过程计算过程4545A A A AB*CB*CB*CB*CD/ED/ED/ED/E计算过程计算过程计算过程计算过程4646A A A AB*CB*CB*CB*CD/ED/ED/ED/E计算过程计算过程计算过程计算过程4747A A A AB*CB*CB*CB*CD/ED/E

35、D/ED/E计算过程计算过程计算过程计算过程4848例：表达式例：表达式 A+B*C-D/E A+B*C-D/E 的计算过程的计算过程OPSOPSOVSOVS/-DECB*+A;TOPvTOPp+*?运算符比较：运算符比较：()表达式：表达式：表达式：表达式：真真-*假假计算：计算：T2=A+T1T1/T2T1=B*C；;-T3=D/ET3/T4=T2T3T4;=结果：结果：T4T4开始：构造堆栈开始：构造堆栈开始：构造堆栈开始：构造堆栈读符号进栈：读符号进栈：读符号进栈：读符号进栈：AA、+、B B读符号：读符号：读符号：读符号：*读符号：读符号：读符号：读符号：C C读符号：读符号：读符号

36、：读符号：-再判符号：再判符号：再判符号：再判符号：-读符号：读符号：读符号：读符号：D D、/读符号：读符号：读符号：读符号：E E、;再判符号：再判符号：再判符号：再判符号：;再次判别符号：再次判别符号：再次判别符号：再次判别符号：;4949带括号的表达式计算带括号的表达式计算l例：A*(B+C/D)E*F 请学生画出图，分析堆栈中数据变化。5050例2.5：编写一个程序，从键盘输入一个表达式字符串，其中包括数值子字符串以及+、-、*、/四个运算符号与左右括号，然后计算并输出该表达式的值。（假设，输入的字符串长度不超过60）。l书中P49-P50lC+程序51512.3 2.3 队列（队列

37、（QueueQueue）52522.3.1 2.3.1 队列概念队列概念 l队列的定义 队列(queue)是是是是在在在在一一一一端端端端进进进进行行行行插插插插入入入入，在在在在另另另另一一一一端端端端进进进进行行行行删删删删除操作的线性表。除操作的线性表。除操作的线性表。除操作的线性表。FirstInFirstOut-FIFOa1a2a3a4a5出队出队出队出队进队进队进队进队队头队头队头队头 队尾队尾队尾队尾Queue53532.3.22.3.2 队列的运算和声明队列的运算和声明lInsQ(x)：在队列尾部插入一个新元素x。lDelQ()：删除队列中队首元素。lEmptyQ()：测试队列

38、是否为空,为空时返回 一个真值，否则返回一个假值。lFrontQ()：取得队列中队首元素。lSetNULL(Q)：创建一个空队列Q。5454队列类模板（队列类模板（C+C+描述）描述）template class Queue public:virtual bool ins_Queue(const T)=0;virtual bool del_Queue()=0;virtual bool prt_Queue(T&)=0;virtual bool flag_Queue()const=0;5555顺序队列类模板顺序队列类模板template template class class sq_Queues

39、q_Queue :public Queue:public Queue public:public:sq_Queuesq_Queue(intint););boolbool flag_Queueflag_Queue()const()const；boolbool prt_Queueprt_Queue(T&x)const;(T&x)const;boolbool ins_Queueins_Queue(T x);(T x);boolbool del_Queuedel_Queue();();private:private:intint front,rear,n ;front,rear,n ;T *q;T *

40、q;56562.3.3 2.3.3 循环队列及其运算循环队列及其运算l把队列空间从把队列空间从把队列空间从把队列空间从逻辑逻辑逻辑逻辑上看成是一个首尾相连的环。上看成是一个首尾相连的环。上看成是一个首尾相连的环。上看成是一个首尾相连的环。l如何判断一个循环队列如何判断一个循环队列如何判断一个循环队列如何判断一个循环队列是满是满是满是满还还还还是空是空是空是空？frontfrontrearrear5 54 40 01 12 23 3a6a5a1a7a4a3a2队列空队列空队列满队列满l 逻辑上循环：front=(front+1)%6;fear=(rear+1)%65757如何判断循环队列如何判断

41、循环队列是空是空？是满是满？l判满条件判满条件(设设n=6)：l判空条件：判空条件：5 54 40 01 12 23 3frontrear5 54 40 01 12 23 3a1a2a3a4a5frontrearfront=rear(rear+1)%n=front(rear+1)%n=front5858循环队列存在的问题及解决方法循环队列存在的问题及解决方法l问题：在队列满时仍有一个元素的空间未使用在队列满时仍有一个元素的空间未使用在队列满时仍有一个元素的空间未使用在队列满时仍有一个元素的空间未使用l解决方法解决方法：启用该单元，并设置一标志启用该单元，并设置一标志启用该单元，并设置一标志启用

42、该单元，并设置一标志s s，定义如下：，定义如下：，定义如下：，定义如下：00（队列中无元素）（队列中无元素）（队列中无元素）（队列中无元素）11（队列中有元素）（队列中有元素）（队列中有元素）（队列中有元素）于是有：于是有：于是有：于是有：n n判空条件：判空条件：判空条件：判空条件：s=0&front=rear;s=0&front=rear;（可简化为：（可简化为：（可简化为：（可简化为：s=0s=0）n n判满条件：判满条件：判满条件：判满条件：s=1&front=rear;s=1&front=rear;S5959顺序循环队列类模板顺序循环队列类模板templatetemplatecla

43、ssclasssq_c_Queuesq_c_Queue:publicQueue:publicQueuepublic:public:sq_c_Queuesq_c_Queue(intint););boolbool flag_Queueflag_Queue()const()const；boolbool prt_Queueprt_Queue(T&x)const;(T&x)const;boolbool ins_Queueins_Queue(T x);(T x);boolbool del_Queuedel_Queue();();private:private:intintfront,rear,nfront

44、,rear,n，ss;/标志位标志位标志位标志位T*q;T*q;6060例例2.6 2.6 建立容量为建立容量为1010的循环空队列。输出的循环空队列。输出队列；再依次将队列；再依次将5050、6060、7070、8080、9090、100100等六个数入队，输出队列中元素；最等六个数入队，输出队列中元素；最后连续将三个元素出队，输出队列中元素。后连续将三个元素出队，输出队列中元素。lD:codec+DataStructsq_Queue.hlD:codec+DataStructL2_6.cpp61612.4字符串字符串62622.4.1 2.4.1 字符串的概念字符串的概念 l字符串 是由n(

45、n0)个字符组成的有限序列，记为：“a1 a2 a3 an”其中：n n用双引号括起来的字符序列是串的值；用双引号括起来的字符序列是串的值；n na ai i(1=i=n)(1=i=n)可以是字母、数字或其他字符；可以是字母、数字或其他字符；n nn n为串中字符的个数，称为串的长度；为串中字符的个数，称为串的长度；n nn=0n=0的串称为空串。的串称为空串。界定符界定符界定符界定符6363串的顺序存储结构串的顺序存储结构串的顺序存储结构串的顺序存储结构l将串的各个字符，按顺序存入连续的存储单将串的各个字符，按顺序存入连续的存储单元中，使逻辑上相邻的字符在内存中也相元中，使逻辑上相邻的字符在

46、内存中也相邻。也称为邻。也称为顺序串顺序串。6464串运算串运算l strlen(string)，求串的长度 l strcmp(string1，string2)，两个串比较l strcat(string1，string2)，两个串的联接l strstr(string1，string2)，子串查询l strcpy(string1，string2)，串拷贝 l replace(s，t，r)，置换l65652.4.2 2.4.2 字符串匹配字符串匹配l串的模式匹配串的模式匹配判断串判断串P是否在另一个串是否在另一个串S中，若在则给出中，若在则给出其在其在S串中的起始位置。串中的起始位置。串串S叫作叫

47、作“正文正文”，串，串P叫作叫作“模式模式”。lP是是S的子串的必要条件是的子串的必要条件是:strlen（P）strlen（S）66661 1、简单匹配算法（、简单匹配算法（Brute-Force Brute-Force BF)BF)ABABCACABABCBCCAi,0i,0j,0j,0AABCBACB Ai,1i,1j,1j,1j,0j,0i,2i,2AAi,3i,3j,1j,1i,4i,4j,2j,2BBi,5i,5j,3j,3CCi,6i,6j,4j,4串串S,n=10串串P,m=5匹配成功，匹配成功，耶！耶！演示j,0j,06767BFBF匹配算法描述匹配算法描述匹配算法描述匹配算

48、法描述l对于对于i=0，1，依次进行下面的匹配步骤（最，依次进行下面的匹配步骤（最多做多做n-m+1轮）。轮）。匹配步骤：用匹配步骤：用P0，P1，Pm-1依次与依次与Si，Si+1，Si+m-1进行比较；进行比较；uu如果如果如果如果P0=Si,P1=Si+1,Pm-1=Si+m-1,P0=Si,P1=Si+1,Pm-1=Si+m-1,那么匹配成功，整个算法结束；那么匹配成功，整个算法结束；那么匹配成功，整个算法结束；那么匹配成功，整个算法结束；uu否则，一定存在着某个整数否则，一定存在着某个整数否则，一定存在着某个整数否则，一定存在着某个整数k k，ikmikm，使得，使得，使得，使得Pk

49、Si+k-1PkSi+k-1，立即中止本轮后面的比较。，立即中止本轮后面的比较。，立即中止本轮后面的比较。，立即中止本轮后面的比较。i+i+，重新步骤重新步骤重新步骤重新步骤；l如果执行如果执行n-m+1轮匹配步骤之后，在轮匹配步骤之后，在S中没有找中没有找到等于到等于P的子串，那么匹配失败。的子串，那么匹配失败。6868BFBF匹配匹配 （C+C+描述）描述）intint zfppzfpp(chars,charp,(chars,charp,intintn,n,intintm)m)intinti=0,j,k,flag=0i=0,j,k,flag=0；while(in-m+1)&(flag=0)

50、while(in-m+1)&(flag=0)k=i;j=0;k=i;j=0;while(j=m-1)&(pj=sk)k+while(jm则运行时间为则运行时间为O(nm)。70702 2、KMPKMP匹配算法匹配算法lKMPKMP匹配算法匹配算法匹配算法匹配算法由由由由D.E.D.E.K Knuthnuth、J.H.J.H.MMorrisorris和和和和V.R.V.R.P Prattratt发现发现发现发现l问题的提出问题的提出问题的提出问题的提出0000000000000000000000000000000000000000001S S00000001P P由于每趟比较都是在p的最后一个字