第3章线性结构讲义课件

第3章 线性结构第2页2024年7月15日教学内容 线性表的逻辑结构、线性表的顺序存储、线性表的链式存储、顺序表和链表的比较;栈和队列的逻辑结构、存储实现及基本运算;字符串，数组，广义表的定义及运算。教学目的 理解线性表的定义及其运算,理解顺序表和链表的定义、组织形式、结构特征和类型说明,掌握在这两种表上实现的插入、删除和按值查找的算法,了解循环链表、双链表的结构特点;理解栈和队列的定义、特征及基本运算；掌握栈和队列的两种存储结构及基本运算的实现；了解串、数组、广义表几中特殊的线形表的定义，理解和领会串的存储方式和掌握常用的串运算，理解多维数组的结构特点和在内存中的两种顺序存储方式，领会稀疏矩阵的压缩方式和简单运算。第3页2024年7月15日教学重点 顺序表上插入、删除和定位运算的实现，单链表的结构特点及类型说明，头指针和头结点的作用及区别，定位、删除、插入运算在单链表上的实现，循环链表、双链表的结构特点，循环链表、双链表上删除与插入运算的实现；栈的定义、逻辑特点及基本运算，栈的顺序存储结构、链式存储结构及运算，队列的定义、逻辑特点及基本运算，队列的顺序存储结构、链式存储结构及运算；串和数组的逻辑结构、基本运算、存储方式，模式匹配算法，多维数组的存储方式，特殊矩阵的压缩存储，稀疏矩阵的表示方法。第4页2024年7月15日教学难点 线性表与线性结构的联系与区别，头结点在链表中的作用、指针操作，删除、插入运算中的指针操作顺序，双链表上指针的操作顺序；顺序栈的溢出判断条件，循环队列的队空、队满判断条件，循环队列上的插入、删除操作。第5页2024年7月15日 线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。线性表是最简单、最基本、也是最常用的线性结构，本章我们讨论这种最基本的线性结构，线性表有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。此外，本章还在基本线性结构的基础上讨论两种具有特殊操作规则的数据结构：堆栈和队列实现及其应用，以及以字符为元素的线性结构字符串的存储和操作实现。最后阐述多维数组和特殊矩阵与线性结构的对应关系。第6页2024年7月15日3.1 引言3.1.1 问题的提出 问题1：日常生活中看到的学生花名册、学生的成绩单、通讯录、单位的职工工资表以及图书馆的图书目录等等，这些表单具有一个共同的特点，都是由一行行结构相同的数据构成。对这些表单经常进行的操作是修改、查找、插入和删除。问题2：日常生活中我们将洗好的盘子由下而上摆放起来，使用的时候再从上至下依次取出，如果用计算机模拟这一过程，盘子之间的逻辑关系是线性结构，但处理盘子的摆放顺序需要遵循后摆放先取出的原则进行处理。问题3：日常生活中排队购物、汽车进站出站、到银行办理业务等事务处理过程，如果用计算机模拟，一般情况是一个需要遵循先来先服务的处理原则的线性结构。第7页2024年7月15日 3.1.2 线性表的定义 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，ai-1，ai，ai+1，an)其中n为表长，n0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。需 要 说 明 的 是：ai为 序 号 为 i的 数 据 元 素（i=1,2,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型；在字符串中，它是字符型；等等。第8页2024年7月15日3.1.4 线性表的基本运算 线性表初始化：Init_List(L)求线性表的长度：Length_List(L)取表元：Get_List(L,i)按值查找：Locate_List(L,x)插入操作：Insert_List(L,i,x)删除操作：Delete_List(L,i)第9页2024年7月15日在Java语言中可以用接口（Interface）的形式定义线性表的ADT中的公有方法。publicinterfaceList/线性结构的ADTpublicvoidInit_List(L);/初始化线性表LpublicintLength_List(L);/求线性表L当前的长度publicDataTypeGet_List(L,i);/查找线性表L中的第i个元素publicintLocate_List(L,x);/查找给定元素x在线性表L中的位置publicintInsert_List(L,i,x);/在线性表L中插入值为x的元素作为第i个元素publicintDelete_List(L,i);/删除线性表中第i个元素/interface第10页2024年7月15日3.2.1 顺序表 线性表的顺序存储是指在内存中用地址连续的一块存储空间依次顺序存放线性表各元素，用这种存储形式存储的线性表称其为顺序表。顺序存储可以按序号随机访问每一个数据元素：设 a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a)+(i-1)*d 1in3.2 线性表的顺序存储与实现第11页2024年7月15日用一维数组来示实现顺序表的数据存储区域。考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：dataMAXSIZE来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从data0开始依次存放，但当前线性表中的实际元素个数可能未达到MAXSIZE多个，因此需用一个变量last来记录当前线性表中最后一个元素在数组中的位置，即last起一个指示作用，始终指向线性表中最后一个元素的位置，因此，表空时last=-1。这种存储思想的具体描述可以是多样的。可以是：DataTypedata;intlast;第12页2024年7月15日在Java语言中可以定义一个顺序表类SeqList，将数据存储区data、位置last与顺序表中的基本操作封装在一起，作为对抽象数据类型接口List的实现。classSeqListimplementsListprivatestaticfinalintMAXSIZE=100;/定义数组的最大容量privateintlast;/用于存储顺序表最后一个元素的存储位置privateDataTypedata;/顺序表的存储空间SeqList()Init_SeqList(MAXSIZE);/构造函数，调用顺序表初始化函数，建立存储空间为/MAXSIZE的空表publicintLength_SeqList();/求顺序表的长度publicintInsert_SeqList(inti,datatypex);/将元素x插入到顺序表中作为第i个元素publicintDelete_SeqList(inti);/删除顺序表中的第i个元素publicintLocation_SeqList(datatypex);/在顺序表中查找元素x(其他成员函数)第13页2024年7月15日如下图所示的顺序表，L是一个引用类型的变量，是顺序表类SeqList的一个实例，是通过“SeqListL=newSeqList();”操作来获得顺序表的存储空间，L代表着一个具体的顺序表。线性表的表长表示为：L.last1线性表中数据元素顺序存储的基址为：L.data线性表中数据元素的存储或表示为：L.data0L.dataL.last。第14页2024年7月15日3.2.2 顺序表上基本运算的实现 顺序表的初始化 第15页2024年7月15日2.求顺序表的长度 第16页2024年7月15日3.插入运算第17页2024年7月15日 本算法中注意以下问题：顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。要检验插入位置的有效性，这里 i 的有效范围是：1in+1，其中 n 为原表长。注意数据的移动方向。表长的修改。第18页2024年7月15日插入算法的时间性能分析:平均移动数据元素的次数：设：Pi=1/(n+1)，即为等概率情况，则：这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。第19页2024年7月15日4.删除运算 第20页2024年7月15日本算法中注意以下问题：删除第i个元素，i的取值为 1in,否则第i个元素不存在，因此，要检查删除位置的有效性。当表空时不能做删除，因表空时 Llast的值为-1，条件（iLlast+1）也包括了对表空的检查。删除ai 之后，该数据已不存在，如果需要，先取出，再做删除。修改表长。第21页2024年7月15日删除算法的时间性能分析:平均移动数据元素的次数：在等概率情况下，pi=1/n，则：结论：顺序表上作删除运算时大约需要移动表中一半的元素。算法的时间复杂度为(n)。第22页2024年7月15日5.按值查找第23页2024年7月15日按值查找算法的时间性能分析:本算法的主要运算是给定值x与表中元素的比较。显然比较的次数与x在表中的位置有关，也与表长有关。当a1=x 时，比较一次成功。当an=x时，比较n次成功。等概率情况下，查找成功的平均比较次数为：即：平均比较次数为（n+1）/2，时间性能为O(n)。第24页2024年7月15日3.2.3 顺序表应用举例 例例3-13-1 将顺序表(a1，a2，.，an)重新排列为以a1为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比a1大。划分的方法有多种，下面介绍的划分算法其思路简单，性能较差。基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：当前数据元素 aI 比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。第25页2024年7月15日总的移动次数为：即最坏情况下移动数据时间性能为()。第26页2024年7月15日例例3-2 3-2 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。第27页2024年7月15日算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。第28页2024年7月15日2.3.1 单链表 链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继元素ai+1所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图所示：data next3.3 线性表的链式存储第29页2024年7月15日 线 性 表(a1,a2,a3,a4,a5,a6,a7,a8)对应的链式存储结构如右图所示。作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用下图的形式表示，而不用右图的形式表示。第30页2024年7月15日在Java语言中可以定义一个链表类LinkList，将链表中结点的存储与链表中的基本操作封装在一起，作为对抽象数据类型接口List的实现。classLinkListimplementsListprivateLinkNodeHead;/链表的表头LinkList()/构造函数，调用链表初始化函数，建立链表的头结点Init_LinkList();publicLinkListCreate_LinkList1()/在链表的头部插入结点建立单链表publicLinkListCreate_LinkList2()/在链表的尾部插入结点建立单链表publicintLength_LinkList();/求链表的长度publicLinkNodeGet_LinkList(inti);/在链表中查找第i个元素的位置publicintInsert_LinkList(inti,DataTypex);/将元素x插入链表中作为第i个元素publicintDelete_LinkList(inti);/删除链表中的第i个元素publicLinkNodeLocate_LinkList(DataTypex);/在链表中查找元素xPp.datap.next(其他成员函数)第31页2024年7月15日3.3.2 单链表上基本运算的实现1.链表的初始化第32页2024年7月15日(1)在链表的头部插入结点建立单链表2.建立单链表第33页2024年7月15日第34页2024年7月15日(2)在单链表的尾部插入结点建立单链表第35页2024年7月15日第36页2024年7月15日 头结点问题的说明：头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。第37页2024年7月15日3.求表长第38页2024年7月15日4.查找操作(1)按序号查找算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第个结点时返回空指针。第39页2024年7月15日(2)按值查找即定位 算法思路：从链表的第一个元素结点起，判断当前结点值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空指针。第40页2024年7月15日5.插入操作 (1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。操作如下：s.next=p.next;p.next=s;注意：两个指针的操作顺序不能交换。第41页2024年7月15日(2)前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下：q=L;while(q.next!=p)q=q.next;/*找*p的直接前驱*/s.next=q.next;q.next=s;第42页2024年7月15日(3)插入运算 算法思路：找到第i-1个结点；若存在继续2，否则结束；申请、填装新结点；将新结点插入，结束。第43页2024年7月15日6.删除操作(1)删除结点：设p指向单链表中某结点，删除*p。要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：q-next=p-next;free(p);显然找*p前驱的时间复杂性为O(n)。若要删除*p的后继结点(假设存在)，则可以直接完成：s=p-next;p-next=s-next;free(s);该操作的时间复杂性为O(1)。第44页2024年7月15日(2)删除运算 Del_LinkList(L,i)算法思路：找到第i-1个结点；若存在继续2，否则结束；若存在第i个结点则继续3，否则结束；删除第i个结点，结束。第45页2024年7月15日3.3.3 循环链表对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。第46页2024年7月15日例例：对两个单循环链表H1、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R、R2来标识，则时间性能为O(1)。操作如下：P=Rnext;/*保存第一个表的头结点指针*/R-next=R2-next-next;/*头尾连接*/free(R2-next);/*释放第二个表的头结点*/R2-next=P;/*组成循环链表*/第47页2024年7月15日3.3.4 双向链表 单链表的结点中只有一个指向其后继结点的指针域next，找后继的时间性能是O(1)，找前驱的时间性能是O(n)；可以付出空间的代价使得找前驱的时间性达到O(1)：每个结点再加一个指向前驱的指针域。用这种结点组成的链表称为双向链表。结点形式如下：第48页2024年7月15日 和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构。第49页2024年7月15日 在双向链表中，通过某结点的指针p既可以直接得到它的后继结点的指针p.next，也可以直接得到它的前驱结点的的指针p.prior。p.prior.next=p=p.next.prior第50页2024年7月15日在双向链表中插入一个结点：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面。操作如下：s.prior=p.prior;p.prior.next=s;s.next=p;p.prior=s;上面指针操作的顺序不是唯一的，但也不是任意的，操作必须要放到操作的前面完成，否则*p的前驱结点的指针就丢掉了。第51页2024年7月15日在双向链表中删除指定结点：设p指向双向链表中某结点，删除*p。操作如下：p.prior.next=p.next;p.next.prior=p.prior;free(p);第52页2024年7月15日3.3.5 单链表应用举例【例3-3】已知单链表H如下图所示，写一算法将其逆置。算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向原表中当前结点，p为空时结束。第53页2024年7月15日第54页2024年7月15日【例3-4】已知单链表H如下图所示，写一算法，删除其重复结点，即实现如下图所示的操作。算法思路：用指针p指向第一个数据元素结点，从它的后继结点开始到表的结束，查找与其值相同的结点并删除之；p指向下一个结点；依此类推，p指向最后结点时算法结束。第55页2024年7月15日第56页2024年7月15日 【例3-5】设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部，得到的C表则为递减有序的。第57页2024年7月15日第58页2024年7月15日2.4 顺序表和链表的比较 本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有3个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。第59页2024年7月15日顺序存储两个缺点：在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。第60页2024年7月15日 在实际中怎样选取存储结构呢？通常有以下几点考虑：基于存储的考虑基于运算的考虑基于环境的考虑总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。第61页2024年7月15日3.5.1 堆栈的定义及基本运算 堆栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。右图所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（Last In First Out），简称 LIFO表。3.5 堆栈第62页2024年7月15日堆栈的基本运算：栈初始化：Init_Stack(s)判栈空：Empty_Stack(s)入栈：Push_Stack(s，x)出栈：Pop_Stack(s)读栈顶元素：Top_Stack(s)第63页2024年7月15日在Java语言中可以用接口（Interface）的形式定义堆栈的ADT中的公有方法。publicinterfaceStack/堆栈的ADTpublicvoidInit_Stack(S);/初始化堆栈SpublicintEmpty_Stack(S);/判栈空publicintFull_Stack(S);/判栈满publicintPush_Stack(S,x);/入栈publicDataTypePop_Stack(S);/出栈publicDataTypeTop_Stack(S);/读栈顶元素/interface第64页2024年7月15日顺序栈在Java语言中可以定义一个顺序栈类SeqStack，将数据存储区data、栈顶位置top与顺序栈的基本操作封装在一起，作为对抽象数据类型接口Stack的实现。classSeqStackimplementsStackprivatestaticfinalintMAXSIZE=100;/定义顺序栈空间的最大容量privateinttop;/用于存储栈顶位置privateDataTypedata;/顺序栈的存储空间SeqStack()/构造函数，调用顺序栈初始化函数，/建立存储容量为MAXSIZE的空栈Init_SeqStack(MAXSIZE);publicintEmpty_SeqStack();/判栈空publicintFull_SeqStack();/判栈满publicintPush_SeqStack(DataTypex);/入栈publicDataTypePop_SeqStack();/出栈publicDataTypeTop_SeqStack();/读栈顶元素(其他成员函数)第65页2024年7月15日(a)：空栈；(c)：A、B、C、D、E 5个元素依次入栈之后；(d)：在图(c)之后E、D相继出栈，top指针已经指向了新的栈顶，则元素D、E已不属于栈中元素。栈操作的示意图：第66页2024年7月15日 置空栈第67页2024年7月15日判栈空第68页2024年7月15日判栈满第69页2024年7月15日入栈第70页2024年7月15日出栈第71页2024年7月15日取栈顶元素第72页2024年7月15日几点注意：(1)对于顺序栈，入栈时，首先判栈是否满了，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。(2)出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。(3)通常栈空时常作为一种控制转移的条件。第73页2024年7月15日链栈类的定义：classLinkStackimplementsStackprivateLinkNodetop;/用于表示栈顶LinkStack()top=NULL;/构造函数，建立链栈的栈顶指针publicintEmpty_LinkStack();/判栈空publicintPush_LinkStack(DataTypex);/入栈publicDataTypePop_LinkStack();/出栈publicDataTypeTop_LinkStack();/读栈顶元素(其他成员函数)链栈第74页2024年7月15日链栈基本操作的实现如下：置空栈仅是需要将栈顶指针置为空即可。判栈空第75页2024年7月15日入栈第76页2024年7月15日出栈第77页2024年7月15日(5)读栈顶元素第78页2024年7月15日3.2 堆栈的应用举例 由于栈的“后进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。第79页2024年7月15日例例 3-7 简单应用：数制转换问题简单应用：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3467）10=（6613）8将得到的余数一次放入栈中。算法思想如下：当N0时重复(1)，(2)(1)若N0，则将N%r压入栈s中，执行(2);若N=0，将栈s的内容依次出栈，算法结束。(2)用N/r代替N。第80页2024年7月15日第81页2024年7月15日例 3-8 利用栈实现迷宫的求解。利用栈实现迷宫的求解。问题：这是实验心理学中一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。第82页2024年7月15日表示迷宫的数据结构设迷宫为m行n列，利用mazemn来表示一个迷宫。mazeij=0或1，其中：0表示通路，1表示不通。迷宫的定义如下：#definem6/*迷宫的实际行*/#definen8/*迷宫的实际列*/intmazem+2n+2;如图表示的是一个68的迷宫。入口坐标为（1，1），出口坐标为（6，8）。第83页2024年7月15日试探方向在上述表示迷宫的情况下，每个点有8个方向去试探。为了简化问题，方便地求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move8中。Move数组定义如下：typedefstructintx，yitem;itemmove8;第84页2024年7月15日栈的设计栈中元素的设计如下：classDataTypeintx,y,d;/行列坐标及方向datatype;栈的定义仍然为：SeqStacks=newSeqStack();第85页2024年7月15日 对于上示迷宫，压入栈中的分别为：(1,1)1(2,2)1(3,3)0(3,4)0(3,5)0(3,6)0（下脚标表示方向）第86页2024年7月15日如何防止重复到达某点，以避免发生死循环 一种方法是另外设置一个标志数组markmn，它的所有元素都初始化为0，一旦到达了某一点(i,j)之后，使markij 置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点(i,j)后使mazeij 置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的，本书采用后者方法，算法结束前可恢复原迷宫。第87页2024年7月15日第88页2024年7月15日例3-9 表达式求值表达式求值是程序设计语言编译中一个最基本的问题，它的实现也用到栈。下面的算法是用算符优先法对表达式求值。表达式是由运算对象、运算符、括号组成的有意义的式子。运算符从运算对象的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。在此仅限于讨论只含二目运算符的算术表达式。第89页2024年7月15日(1)中缀表达式求值设运算规则为：运算符的优先级为：（）、/、%+、-；有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；乘方连续出现时先算最右面的。表达式作为一个满足表达式语法规则的串存储，如表达式“3*2（4+2*2-*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算。第90页2024年7月15日中缀表达式表达式“3*2（4+2*2-*3）-5”求值过程中两个栈的状态情况如图所示。第91页2024年7月15日(2）后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。第92页2024年7月15日第93页2024年7月15日(3)中缀表达式转换成后缀表达式 将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。第94页2024年7月15日3.3.1 队列的定义及基本运算 在实际问题中经常用到一种“先进先出”(FIFO-First In First Out)的数据结构：即插入在表一端进行，删除在表的另一端进行，这种数据结构称为队或队列，把允许插入的一端叫队尾(rear)，把允许删除的一端叫队头(front)。队列也是一种运算受限制的线性表，又叫先进先出表。3.6 队列第95页2024年7月15日在队列上进行的基本操作有：队列初始化：Init_Queue(q)入队操作：In_Queue(q,x)出队操作：Out_Queue(q,x)读队头元素：Front_Queue(q,x)判队空操作：Empty_Queue(q)第96页2024年7月15日在Java语言中可以用接口（Interface）的形式定义队列的ADT中的公有方法。public interface Queue /队列的ADT public void Init_ Queue(Q);/初始化队列Q public int Empty_Queue(Q);/判队列空 public int Full_ Queue(Q);/判队列满 public int In_ Queue(Q,x);/入队列 public DataType Out_ Queue(Q);/出队列 public DataType Front_ Queue(Q);/读队首元素/interface Queue第97页2024年7月15日3.6.2 队列的存储及运算实现顺序队列 顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。第98页2024年7月15日classSeqQueueimplementsQueueprivatestaticfinalintMAXSIZE=100;/定义顺序队列空间的最大容量privateintfront;/用于存储队头位置privateintrear;/用于存储队尾位置privateintnum;/用于存储队列的元素个数privateDataTypedata;/顺序队列的存储空间SeqQueue()/构造函数，调用顺序队列初始化函数，/建立存储容量为MAXSIZE的空队列Init_SeqQueue(MAXSIZE);publicintEmpty_SeqQueue();/判队空publicintFull_SeqQueue();/判队满publicintIn_SeqQueue(DataTypex);/入队publicDataTypeOut_SeqQueue();/出队publicDataTypeFront_SeqQueue();/读队首元素(其他成员函数)第99页2024年7月15日按照上述思想建立的空队及入队出队示意图如图所示，设MAXSIZE=10。第100页2024年7月15日“假溢出”现象：从图中可以看到，随着入队出队的进行，会使整个队列整体向后移动，这样就出现了图(d)中的现象：队尾指针已经移到了最后,再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于“队尾入队头出”这种受限制的操作所造成。解决假溢出的方法：之一是将队列的数据区data0.MAXSIZE-1看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”，“循环队列”如下图所示。第101页2024年7月15日l入队时的队尾指针加1操作修改为：Q.rear=(Q.rear+1)%MAXSIZE;出队时的队头指针加1操作修改为：Q.front=(Q.front+1)%MAXSIZE;第102页2024年7月15日从上图所示的循环队可以看出：可见在队满和队空情况下都有：front=rear，这显然是必须要解决的一个问题。方法之一是：附设一个存储队中元素个数的变量如num，当num=0时队空，当num=MAXSIZE时为队满。另一种方法是：少用一个元素空间，把图(d)所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1)%MAXSIZE=front，也能和空队区别开。第103页2024年7月15日置空队第104页2024年7月15日 判队空第105页2024年7月15日判队满第106页2024年7月15日入队第107页2024年7月15日出队第108页2024年7月15日判队空第109页2024年7月15日链队列链式存储的队称为链队。和链栈类似，用单链表来实现链队，根据队的FIFO原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如图所示。第110页2024年7月15日链队类的定义如下：class LinkQueue implements Queue private LinkNode front;/用于表示队首private LinkNode rear;/用于表示队尾LinkQueue()Init_LinkQueue;/构造函数，建立空的链队列public int Empty_LinkQueue();/判队列空public int In_LinkQueue(DataType x);/入队public DataType Out_LinkQueue();/出队public DataType Front_LinkQueue();/读队首元素 (其他成员函数)第111页2024年7月15日带头结点的链队如图所示：第112页2024年7月15日(1)创建一个带头结点的空队第113页2024年7月15日(2)判队空第114页2024年7月15日(3)入队第115页2024年7月15日(4)出队第116页2024年7月15日(5)读队头元素第117页2024年7月15日3.4 队列应用举例例3-11 设计算法找一条从迷宫入口到出口的最短路径。算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依依次次再从这些点出发，再记下所有一步能到达的坐标点，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。第118页2024年7月15日第119页2024年7月15日3.7.1 字符串1字符串的定义与相关术语字符串(简称为串)是数据元素为字符的线性表，它的是由零个或多个任意字符组成的字符序列。一般记作：s=”s1s2sn”。其中s是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；si(1=i=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号;n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为。3.7其他线性结构及扩展第120页2024年7月15日2.字符串的基本运算求串长StrLength(s)串赋值StrAssign(s1,s2)连接操作StrConcat(s1,s2,s)或StrConcat(s1,s2)求子串SubStr(s,i,len)串比较StrCmp(s1,s2)子串定位StrIndex(s,t)串插入StrInsert(s,i,t)串删除StrDelete(s,i,len)串替换StrRep(s,t,r)第121页2024年7月15日3.串的顺序存储线性表的存储方式仍适用于串，如顺序存或链式存储，通常采用顺序存储的方法，称为顺序串。也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。通常用一组地址连续的存储单元存储串值中的字符序列，可以定长来指明最大的字符个数，也叫定长串。如：staticfinalintMAXSIZE=256;/定义存放字符串的最大长度chars=newcharMAXSIZE;则s中存放的字符串的字符个数不能超过256。第122页2024年7月15日第123页2024年7月15日2 顺序串的基本运算主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。(1)求串长算法第124页2024年7月15日(2)串联接第125页2024年7月15日(3)求子串第126页2024年7月15日(4)串比较第127页2024年7月15日(5)模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中查找子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。t也称为模式。为了运算方便，设字符串采用定长存储，且用第3种方式表示串长，即串的长度存放在0号单元，串值从1号单元存放，这样字符序号与存储位置一致。第128页2024年7月15日算法思想如下：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t0，否则，匹配失败。设主串s=acabaabaabcacaabc，模式t=abaabcac，匹配过程如图所示。第129页2024年7月15日第130页2024年7月15日下面分析它的时间复杂度，设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种极端情况：在最好情况下每趟不成功的匹配都发生在第一对字符比较时：例如：s=”aaaaaaaaaabc”，t=”bc”设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：即最好情况下的时间复杂度是O(n+m)。第131页2024年7月15日最坏情况下，每趟不成功的匹配都发生在t的最后一个字符。设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。第132页2024年7月15日1.数组的逻辑结构数组是我们熟悉的一种数据结构。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推，所以可以看作是线性表的推广。3.7.2 数组第133页2024年7月15日 2 数组的内存映象通常，数组在内存被映象为向量，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。对于一维数组按下标顺序分配即可。对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序；一种是以列为主序。第134页2024年7月15日以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。第135页2024年7月15日设二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*l推广到一般的二维数组：Ac1.d1c2.d2，则aij的物理地址计算函数为：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+(j-c2)*l第136页2024年7月15日同理对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l推广到一般的三维数组：Ac1.d1c2.d2c3.d3，则aijk的物理地址为：LOC(i,j)=LOC(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)*l第137页2024年7月15日三维数组的逻辑结构和以行为主序的分配示意图如图所示。第138页2024年7月15日例3-12若矩阵Amn中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。第139页2024年7月15日第140页2024年7月15日3.7.3 特殊矩阵对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。第141页2024年7月15日1.对称矩阵对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1i,jn第142页2024年7月15日对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij。这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。第143页2024年7月15日如何只存储下三角部分？对下三角部分,以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SAn(n+1)/2中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。第144页2024年7月15日在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为：k=i*(i-1)/2+j-1(kn*(n+1)/2)当访问的元素在上三角中时(ij)，因为aij=aji，因此访问和它对应的aji即可，因此将上式中的行列下标交换就是上三角中的元素aij在SA中的对应关系：k=j*(j-1)/2+i-1(kn*(n+1)/2)第145页2024年7月15日2.三角矩阵形如下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。第146页2024年7月15日(1)下三角矩阵与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1个元素，设存入向量：SAn*(n+1)+1中，这种的存储方式可节约n*(n-1)-1个存储单元，sak与aji的对应关系为：第147页2024年7月15日(2)上三角矩阵对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个元素，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储：个元素，aij是它所在的行中要存储的第（j-i+1）个也就是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。sak与aji的对应关系为：第148页2024年7月15日3.带状矩阵n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当i-jm时，aij=0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由下图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中。第149页2024年7月15日一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。那么aij映射为bij，映射关系为：第150页2024年7月15日另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。如当w=3时，映象函数为：k=2*i+j-3第151页2024年7月15日3.7.4 稀疏矩阵设m*n矩阵中有t个非零元素且tm*n，这样的矩阵称为稀疏矩阵。基本思想史志存非零元素：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。下面讨论稀疏矩阵的压缩存储方法。第152页2024年7月15日1.稀疏矩阵的三元组表存储将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。如图(a)稀疏矩阵对应的三元组表为图(b)。第153页2024年7月15日采用三元组表存放稀疏矩阵可定义为如下的SPMatrix类。classSPMatrixprivatestaticfinalintMAXSIZE=100;/定义三元组表空间的最大容量privateintmu;/稀疏矩阵的行数privateintnu;/稀疏矩阵的列数privateinttu;/稀疏矩阵的非零元素个数privateSPNodedata;/三元组表的存储空间PMatrix()/构造函数1SPNodedata=newSPNodeMAXSIZE;tu=0;SPMatrix(intm,intn)/构造函数2，建立存储容量为MAXSIZE的三元组表空间SPNodedata=newSPNodeMAXSIZE;tu=0;mu=m;nu=n;(其他成员函数)第154页2024年7月15日(1)稀疏矩阵的转置 设SPMatrix A;表示一m*n的稀疏矩阵，其转置B则是一个n*m的稀疏矩阵，因此有 SPMatrix B;。由A求B需：A的行、列转化成B的列、行；将A.data中每一三元组的行列交换后转到B.data中；以上两点完成之后，并没有完成B。因为我们前面规定三元组的是按一行一行且每行中的元素是按列号从小到大的规律顺序存放的，因此B也必须按此规律实现，A的转置B如图(a)所示，图(b)是它对应的三元组存储，就是说，在A的三元组存储基础上得到B的三元组表存储（为了运算方便，矩阵的行列都从1算起，三元组表data也从1单元用起）。第155页2024年7月15日算法思路：A的行、列转化成B的列、行；在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。第156页2024年7月15日第157页2024年7月15日(1)引入两个向量：intnumn+1,cpotn+1;numcol表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起）;cpotcol初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。(2)cpot的初始值为：cpot1=1；cpotcol=cpotcol-1+numcol-1；2coln第158页2024年7月15日(3)算法实现：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpot