数据结构其它线性结构.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,数据结构,其它线性结构,其它线性结构,栈,队列,串,数组,广义表,1,栈,栈（,Stack,）,是只允许在表的同一端进行插入和删除操作的特殊的线性表。,（进栈、压入）,（退栈、弹出）,当栈中没有任何元素时称为空栈。,1,栈,由于栈的,插入和,删除,操作,总是在栈顶进行，所以,，,后进去的元素一定先出来。因而，栈又被称为后进先出（,Last In First Out,）的线性表，简称,LIFO,表。,1,3,2,1,2,3,2,1,3,3,2,1,2,3,1,若输入序列是,1,2,3,，,则可能的输出序列有,哪些？,思考：,1,栈,栈的抽象数据类型定义,栈的存储结构及操作实现,栈的应用举例,1.1,栈的抽象数据类型定义,ADT Stack,数据对象：,D=,a,i,|,a,i,ElemType,i,=1,2,n,n,0,数据关系：,R1=|,a,i,-1,a,i,D,i,=2,3,n,基本操作：,Init(&S),操作结果：构造一个空的栈,S,Destroy(&S),初始条件：栈,S,已存在,操作结果：销毁栈,S,Clear(&S),初始条件：栈,S已存在,操作结果：将栈,S,清空,Empty(S),初始条件：栈,S,已存在。,操作结果：若,S,为空栈，则返回,true,，否则返回,false,。,Length(S),初始条件：栈,S,已存在。,操作结果：返回栈,S,的长度。,Top(S),初始条件：栈,S,已存在，且,S,非空。,操作结果：返回栈顶元素的值。,Push(&S,e),初始条件：栈,S,已存在，且,S,未满。,操作结果：插入新的元素,e,到栈顶。,Pop(&S),初始条件：栈,S,已存在，且,S,非空。,操作结果：删除栈顶元素。,1.2 栈的存储结构及操作实现,栈是一种操作受限的特殊的线性表。因此，线性表的存储结构同样适用于栈，故栈也可以采用顺序存储结构和链式存储结构。,顺序栈,链栈,栈的顺序存储表示,顺序栈,栈的顺序存储表示顺序栈,用一维数组来模拟连续的存储空间。将,0,下标端设为栈底，栈的第,i,个元素存放在,i,-1,下标位置。,设置一个栈顶指针（或称指示器）,top,来指示栈顶位置。初始时，栈为空，置,top=0,；入栈时，,top,加,1,；出栈时，,top,减,1,；当栈满时，,top,等于数组空间大小。因此，,top,总是指在栈顶元素的后一个下标位置。,顺序栈,类定义,template /,声明一个类模板,class SqStack /,顺序栈类,public:,SqStack(int m);/,构造函数,SqStack();/,析构函数,void Clear();/,清空栈,bool Empty()const;/,判栈空,int Length()const;/,求长度,ElemType /,取栈顶元素,void Push(const ElemType /,入栈,void Pop();/,出栈,private:,ElemType*m_base;/,基地址指针,int m_top;/,栈顶指针,int m_size;/,向量空间大小,;,顺序栈的基本操作的实现,1.,栈初始化,/,构造函数，分配,m,个结点的顺序空间，构造一个空的顺序栈,template,SqStack:SqStack(int m),m_top=0;,m_base=new ElemTypem;,m_size=m;,m_top,m_base,(,栈底,),(,栈顶,),m_size,顺序栈的基本操作的实现,2.,销毁栈,/,析构函数，将栈结构销毁,template,SqStack:SqStack(),if(m_base!=NULL)delete m_base;,顺序栈的基本操作的实现,3.,清空栈,/,清空栈,template,void SqStack:Clear(),m_top=0;,顺序栈的基本操作的实现,4.,判栈空,/,若栈为空，则返回,true,，否则返回,false,template,bool SqStack:Empty()const,return m_top=0;,顺序栈的基本操作的实现,5.,求长度,/,求栈中元素的个数,template,int SqStack:Length()const,return m_top;,顺序栈的基本操作的实现,6.,取栈顶元素的值,/,取栈顶元素的值。先决条件是栈不空,template,ElemType&SqStack:Top()const,return m_basem_top-1;,顺序栈的基本操作的实现,7.,入栈,/,入栈，若栈满，则先扩展空间。插入,e,到栈顶,template,void SqStack:Push(const ElemType&e),if(m_top=m_size)/,若栈满，则扩展空间,ElemType*newbase;,newbase=new ElemTypem_size+10;/,扩大,10,个元素空间,for(int j=0;j next;,delete p;,链,栈的基本操作的实现,4.,判栈空,/,若栈为空，则返回,true,，否则返回,false,template,bool LinkStack:Empty()const,return top=NULL;,链,栈的基本操作的实现,5.,求长度,/,返回栈中元素个数,template,int LinkStack:Length()const,int i=0;,LinkNode *p=top;,while(p)/,对链表中的结点计数,i+;,p=p-next;,return i;,/,链,栈的基本操作的实现,6.,取栈顶元素的值,/,取栈顶元素的值。先决条件是栈不空,template,ElemType&LinkStack:Top()const,return top-data;,链,栈的基本操作的实现,7.,入栈,/,入栈,template,void LinkStack:Push(const ElemType&e),LinkNode *p;,p=new LinkNode;,p-data=e;,p-next=top;/,新结点插在链表的头部,top=p;链,栈的基本操作的实现,8.,出栈,/,出栈。先决条件是栈不空,template,void LinkStack:Pop(),LinkNode *p=top;/,删除并释放第一个结点,top=top-next;,delete p;,在链栈中，由于元素的存储空间是在需要时通过,new,运算符动态分配的，因此，正常情况下，不会出现栈满的情形，除非内存中没有空闲的存储空间可供分配。,在链栈的操作中，栈的销毁、清空、求长度操作的时间复杂度为,O,(,n,),，因为需要对链表的每一个元素结点进行处理。其余操作的时间复杂度为,O,(1),。,链,栈,1.3 栈的应用举例,回文判断,迷宫问题,表达式求值,递归和汉诺塔问题,1.3 栈的应用举例,回文判断,【,例,3.1】,回文判断,所谓回文，是指一个字符串的字符序列（不包括空格）顺读和逆读是一样的。,例如,：,dad,、,mum,、,noon,、,was it a cat i saw,都是回文，而,good,，,so so,则不是。,本例,读入一个字符串，过滤字符串中的空格，然后检查其是否回文。,可以用栈来处理。对去掉了空格的串通过两遍扫描来检查其是否回文。第一遍扫描，将每个字符压入栈，形成一个逆序的串。第二遍扫描，将原串中的每一个字符与从栈中弹出的字符作比较，若字符不同，则结束处理，该串不是回文。若直到栈空每一对比较的字符都相同，则该串是回文。程序请见教程,P.55,1.3 栈的应用举例,迷宫问题,【,例,3.2】迷宫问题,找出一条,从,迷宫,的入口到,出口,的,通路（如果存在通路）。,用一个二维数组模拟迷宫地图，如图,(A),所示，,0,表示可以通行，,1,表示墙壁，无法通过。为了方便处理边界，可以在迷宫的四周加设围墙，如图,(B),所示。,图,(A),迷宫地图,图,(B),加设围墙后的迷宫地图,迷宫问题,在迷宫中行进时必须遵循三个原则：,1.,每一步只走一格；,2.,遇到死胡同时退回一步，看是否有其他的路可以走；,3.,走过的路不会再走第二次。,用回溯法来求解迷宫问题,:,首先从入口出发，按东南西北的次序依次向下一步探索，若未走过且能通过，则前进一步进入下一位置；否则试探下一个方向。若所有的方向均没有通路，则将该点标为死胡同并沿原路退回到前一步，再换下一个方向继续试探。直到找到一条通路，或无路可走返回到入口。,为此，程序在搜索迷宫出口的过程中不但要记录走过的路径，还必须判断下一步应该往哪个方向走，可以选择的方向有,4,个，分别为东（右）、南（下）、西（左）、北（上）。,迷宫问题,在求解过程中，为了能够退回到前一步以便继续向下一个方向探索前进，需要用一个,栈,来保存当前所走线路沿途的每一个位置的,坐标,以及从该位置前进的,方向,，而栈顶的位置便是当前的位置。当到达出口时，栈中从底到顶即为一条由入口到出口的通路。路径上的每一步到达的位置用序号（从,1,开始）编排，称为足迹。若存在从入口到出口的路径，则程序以足迹的形式输出一条路径。,程序请见教程,P.57,1.3 栈的应用举例,表达式求值,【,例,3.3】表达式求值,求一个表达式的值是程序设计语言编译程序中的一个基本问题，实现表达式的求值是栈的一个典型应用。,在这里，仅讨论最基本的算术四则运算：（加）、（减）、（乘）、（除），以及为了强调优先计算的括号。,表达式可定义为（“,:=,”为定义符）：,表达式,:=,运算数,:=,无符号整数,|,表达式,|(,表达式,),运算符,:=+|*|/|(|)|=,表达式求值,在此，把一个运算数或一个运算符均称为一个元素。算术四则运算的规则为：,（,1,）先乘除、后加减；,（,2,）同级运算时先左后右；,（,3,）先括号内，后括号外。,算法设置了两个栈：,(1),运算数栈,（,OPRD,）：存放处理表达式过程中的操作数。,(2),运算符栈,（,OPTR,）：存放处理表达式过程中的运算符。,表达式求值,假设表达式语法正确，并以,“,=,”,结束。算术表达式求值的算法如下：,1.,初始化运算数栈和运算符栈,；将运算符,“,=,”,压入运算符栈；,2.读入一个元素；,3.当元素,不,为,“,=,”,或,运算符栈顶,不,为,“,=,”,时，循环执行：,若元素是一个运算数，则将其压入运算数栈，读入下一个元素；,若元素是运算符(op2)，则将运算符栈的栈顶运算符(op1),之,比较,优先级（运算符间的优先关系见P.62 表3.1）：,若,op1op2,，则从运算符栈弹出运算符给,op,，并先后从运算数栈,中弹出两个运算数给,y,和,x,，计算,xy,（如果是除运算且除数,为,0,，则报错并结束算法）的值并将结果压入运算数栈。,直到,op1,和,op2,均为,“,=,”,。,4.,运算数栈的栈顶元素就是求得的表达式的值。,程序请见教程,P.62,表达式求值,算法的计算过程举例,:,5+(6-4/2)*3=,运算数栈,运算符栈,_,5,=,_,+,_,(,_,6,_,-,_,4,_,/,_,_,/,2,4,2,=2,2,-,2,6,=,4,4,_,*,_,3,_,*,3,4,=,12,12,+,7,12,5,=,17,17,1.3 栈的应用举例,递归和汉诺塔,在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自身（即递归）。,函数的调用和返回是利用栈来完成的。系统为运行的程序设置一个工作栈，当执行调用语句时，系统先把有关当前函数的必要信息（包括返回地址、实参、局部变量等信息）组成一个活动记录，保存到栈中，然后才去执行被调函数。当被调函数执行完后，再从栈中弹出一个活动记录，根据其中的返回地址，将控制转移回调用函数，并恢复当前信息。当有多个函数嵌套调用时，按照“后调用先返回”的原则来处理。,递归和汉诺塔,以下是,函数调用和返回时工作栈的变化,示意图：,一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调函数是同一个函数。,递归和汉诺塔,【,例,3.4】,汉诺塔问题,传说婆罗门圣殿（,Temple of Brahman,）里有一个塔台，台上立有,3,根钻石柱子,A,，,B,和,C,，在,A,柱上插了,64,个金圆盘，每一个圆盘都比其下面的略小一些。教士们需要将,A,柱上的圆盘移到,C,柱上。,移动的规则是：,1.,一次只能移动一个圆盘；,2.,圆盘可以移到,A,、,B,和,C,中的任一个柱子上；,3.,任何时候大盘都不能放到小盘的上面。,汉诺塔问题,这样，问题就变成了将,n,1,个圆盘从,B,柱移到,C,柱了。这个问题与,n,个圆盘的问题具有相同的特性，只是问题规模减小了,1,，因此可以用同样的方法求解。,用计算机来完成这个任务可以很方便地用递归来求解。设,A,柱上最初有,n,个圆盘，求解的方法是：,如果,n,=,1,，则将这个圆盘直接从,A,柱移到,C,柱。否则，执行以下,3,步：,1.,先将,A,柱的上面,n,-1,个圆盘移到,B,柱；,2.,将,A,柱上最大的圆盘移到,C,柱；,3.,将,B,柱上的,n,-1,个圆盘移到,C,柱。,汉诺塔问题,下面以,4,个圆盘为例，,移动过程,为：,汉诺塔问题,递归算法如下：,/,将,a,柱上按直径自上而下，由小到大编号为,1,至,n,的,n,个圆盘按规则搬到,c,柱上。,/b,用作辅助柱,void hanoi(int n,char a,char b,char c),/-(1),if(n=1)/-(2),move(1,a,c);/,将编号为,1,的圆盘从,a,移到,c -(3),else /-(4),hanoi(n-1,a,c,b);/,将,a,上编号为,1,至,n-1,的圆盘移到,b,，,c,作辅助柱,-(5),move(n,a,c);/,将编号为,n,的圆盘从,a,移到,c -(6),hanoi(n-1,b,a,c);/,将,b,上编号为,1,至,n-1,的圆盘移到,c,，,a,作辅助柱,-(7),/-(8),/-(9),汉诺塔问题,以,hanoi(3,a,b,c),为例，递归函数,hanoi,执行过程中递归工作栈的变化情况,为：,汉诺塔问题,递归和汉诺塔,递归函数结构清晰，易于理解，系统会自动实现和管理递归工作栈，给编程带来很大的方便。,从以上讨论可知，,递归函数的执行是通过栈来实现的。实际上，借助栈也可以将一个递归算法（函数）改写为一个非递归算法（函数）。,2,队列,队列（,Queue,）,是一种只允许在表的一端插入元素，在另一端删除元素的特殊的线性表。,当,队列,中没有任何元素时称为空,队列,。,3,2,1,2,3,1,对于队列，先进,入,的元素将先被删除出队列，因此队列又被称为先进先出（,First In First Out,）的线性表，简称,FIFO,表。,2,队列,队列的抽象数据类型定义,队列的存储结构及操作实现,队列的应用举例,2.1,队列,的抽象数据类型定义,ADT Queue,数据对象：,D=,a,i,|,a,i,ElemType,i,=1,2,n,n,0,数据关系：,R1=|,a,i,-1,a,i,D,i,=2,3,n,基本操作：,Init(&Q),操作结果：构造一个空的队列,Q,。,Destroy(&Q),初始条件：队列,Q,已存在。,操作结果：销毁队列,Q,。,Clear(&Q),初始条件：队列,Q已存在。,操作结果：将队列,Q,清空。,Empty(Q),初始条件：队列,Q,已存在。,操作结果：若,Q,为空队列，则返回,true,，否则,false,。,Length(Q),初始条件：队列,Q,已存在。,操作结果：返回队列的长度。,GetHead(Q),初始条件：队列,Q,已存在，且,Q,非空。,操作结果：返回队头元素的值。,GetLast(Q),初始条件：队列,Q,已存在，且,Q,非空。,操作结果：返回队尾元素的值。,Append(&Q,e),初始条件：队列,Q,已存在，且,Q,未满。,操作结果：插入新的元素,e,到队尾。,Remove(&Q),初始条件：队列,Q,已存在，且,Q,非空操作结果：删除队头元素。,2.2,队列,的存储结构及操作实现,和栈类似，队列也是一种操作受限的特殊的线性表，同样可以采用顺序存储结构和链式存储结构来表示队列。,循环队列,链队列,队列,的顺序存储表示,循环队列,队列,的顺序存储表示,循环队列,队列的顺序存储表示同样是利用一维数组来实现。为了方便队列的插入和删除操作，需要设置两个变量,front,，,rear,分别用来指示队列的队头和队尾元素的位置，称为队头指针和队尾指针（或称队头指示器和队尾指示器）。,约定：初始化队列时，置,front=rear=0,。,每当一个元素从队尾入队时，先将元素放在,rear,所指的位置，然后,rear,加；而每当一个元素从队头出队时，将,front,加。因此，当队列非空时，,rear,总是指向队尾元素的后一个位置，而,front,总是指向队头元素位置。,队列,的顺序存储表示,循环队列,队列,的入队、出队示意图：,从图中可以发现：,(1),在状态,(a),和,(d),时，队列,均,为空，,它们的共同特点是,front=rear,，,因此可以以此作为判断,队列空,的条件,。,(2),在状态,(e),下，,rear,已经到了数组的外面，说明队尾元素已经放到数组的最后一个元素位置了，如果再有元素入队就会出现数组越界。,但数组前端还有空余位置可以存放入队的元素。,这种现象称为“假溢出”,。,队列,的顺序存储表示,循环队列,解决假溢出的一种有效方法是将队列的数组看成头尾相接的环状空间，当队尾元素放到数组的最后一个位置时，如需入队就把新元素接着存放在数组的,0,下标位置，这样的队列称为循环队列。如,下,图所示,：,队列,的顺序存储表示,循环队列,假设用于存储队列的一维数组大小为,size,，,在这样的循环队列中，需要注意：,(1),前面已经提到，入队时,rear,需后移，而出队时,front,需后移。但它们都应在,0到size-1范围内移动，若,移到,size,位置时,应回到0位置,。分别可以用如下语句来实现：,rear=(rear+1)%size;,front=(front+1)%size;,(2)前面也已经提到，当,front=rear,时队列为空。而,在状态,(f),时，数组中还有一个空位置，如果继续将一个元素入队，,rear,会沿顺时针方向后移一个位置，此时，,front=rear,，数组空间全放满了。,这就出现了二义性。,队列,的顺序存储表示,循环队列,解决,front=rear,时的二义性，,对于队满可以有两种处理方法,：,(1),另设一个满否的标志位或者队列长度信息，用以区分,front=rear,时队列是,“,空,”,还是,“,满,”,。,(2),少用一个元素空间（即当队列中放了,size,1,个元素时就表示已满），以,“,front,在,rear,的顺时针下一个位置,”即,front=(rear+1)%size,作为队列满的判断条件。,下面的讨论将采用第二种方法。,循环队列,类定义,template/,声明一个类模板,class SqQueue,public:,SqQueue(int m=100);/,构造函数,SqQueue();/,析构函数,void Clear();/,清空队列,bool Empty()const;/,判队列空,int Length()const;/,求长度,ElemType/,取队头元素值,ElemType/,取队尾元素值,void Append(const ElemType /,入队,void Remove();/,出队,private:,ElemType*m_base;/,基地址指针,int m_front;/,队头指针,int m_rear;/,队尾指针,int m_size;/,向量空间大小,;,循环队列,的基本操作的实现,1.,队列,初始化,/,构造函数，分配,m,个结点的顺序空间，构造一个空的循环队列,template,SqQueue:SqQueue(int m),m_front=m_rear=0;,m_base=new ElemTypem;,m_size=m;,循环队列,的基本操作的实现,2.,销毁队列,/,析构函数，将队列结构销毁,template,SqQueue:SqQueue(),delete m_base;,循环队列,的基本操作的实现,3.,清空队列,/,清空队列,template,void SqQueue:Clear(),m_front=m_rear=0;,循环队列,的基本操作的实现,4.判队列空,/,判队列是否为空，若为空，则返回,true,，否则返回,false,template,bool SqQueue:Empty()const,return m_front=m_rear;,循环队列,的基本操作的实现,6.取队头元素,/,取队头元素的值。先决条件是队列非空,template,ElemType&SqQueue:GetHead()const,return m_basem_front循环队列,的基本操作的实现,7.取队尾元素,/,取队尾元素的值。先决条件是队列非空,template,ElemType&SqQueue:GetLast()const,return m_base(m_rear-1+m_size)%m_size;,循环队列,的基本操作的实现,8.入队,/,入队，插入,e,到队尾,template,void SqQueue:Append(const ElemType&e),int j,k;,if(m_front=(m_rear+1)%m_size)/,队满，则扩展空间。,ElemType*newbase;,newbase=new ElemTypem_size+10;/,分配新空间,for(j=m_front,k=0;j next=NULL;,链队列,的基本操作的实现,2.,销毁队列,/,析构函数，将队列结构销毁,template,LinkQueue:LinkQueue(),Clear();/,成员函数,Clear(),的功能是释放链表中的所有元素结点,delete m_front;/,释放头结点,链队列,的基本操作的实现,3.清空队列,/,将队列清空,template,void LinkQueue:Clear(),LinkNode *p;,while(m_front-next!=NULL),p=m_front-next;,m_front-next=pnext;,delete p;,m_rear=m_front;,链队列,的基本操作的实现,4.判队列空,/,判队列是否为空，若为空，则返回,true,，否则返回,false,template,bool LinkQueue:Empty()const,return m_front=m_rear;,链队列,的基本操作的实现,5.求队列的长度,/,返回队列中元素个数,template,int LinkQueue:Length()const,int i=0;,LinkNode *p=m_front-next;,while(p!=NULL),i+;,p=p-next;,return i;,链队列,的基本操作的实现,6.取队头元素,/,取队头元素。先决条件是队列不空,template,ElemType&LinkQueue:GetHead()const,return m_front-next-data;,链队列,的基本操作的实现,7.取队尾元素,/,取队尾元素的值。先决条件是队列不空,template,ElemType&LinkQueue:GetLast()const,return m_rear-data;,链队列,的基本操作的实现,8.入队,/,入队，插入,e,到队尾,template,void LinkQueue:Append(const ElemType&e),LinkNode *p;,pnew LinkNode;,p-data=e;,p-next=NULL;,m_rear-next=p;,m_rear=p;,链队列,的基本操作的实现,9.出队,/,出队。先决条件是队列不空,template,void LinkQueue:Remove(),LinkNode *p=m_front-next;,m_front-next=p-next;,if(p=m_rear),m_rear=m_front;/,若出队后队列为空，需修改,m_rear,delete p;,链队列,链队列的队空条件为,front=rear,，或者,front-next=NULL,，而队满只有在内存无可用空间时才发生，所以链队列特别适合于队列元素个数变化比较大的情况。,在链队列的操作中，队列的销毁、清空和求长度操作的时间复杂度为,O,(,n,),，因为需要对链表的每一个元素结点进行处理。队列的其余操作的时间复杂度为,O,(1),。,2.3,队列,应用举例,舞伴问题,火车车厢重排,2.3 队列应用举例,舞伴问题,【,例,3.1】,舞伴问题,在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队人数不相同，则较长的那一队中未配对者等待下一轮舞曲。模拟此舞伴配对问题。,该问题具有典型的先进先出特性，可用队列作为算法的数据结构。,假设进入舞厅的人员信息存放在一个数组中作为输入，然后依次扫描该数组的各个元素，并根据性别来决定是进入男队还是女队，构成两个队列。接着，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队列仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。,程序见,P.78,2.3 队列应用举例,火车车厢重排,【,例,3.6】,火车车厢重排,一列货运列车共有,n,节车厢，每节车厢将停放在不同的车站。假定,n,个车站的编号（由远到近）依次为,1,n,，即货运列车按照第,n,站至第,1,站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，使各车厢从前至后按编号,1,到,n,的次序排列，这样，在每个车站只需卸掉最后一节车厢即可。所以，给定任意次序的车厢，需要重新对它们进行排列。,该问题具有典型的先进先出特性，可用队列作为算法的数据结构。,火车车厢重排,可以通过转轨站完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和,k,个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，,n,节车厢从入轨进入转轨站，它们的序号依次为,0,n,-1,，,转轨结束时各车厢按照编号,1,至,n,的次序离开转轨站进入出轨。假定缓冲轨按先进先出的方式运作，可将它们视为队列，并且禁止将车厢从缓冲轨移至入轨，也禁止从出轨移至缓冲轨。,下,图给出了一个转轨站，其中有,3,个缓冲轨,H,1,，,H,2,和,H,3,。,火车车厢重排,在把车厢,i,移至缓冲轨时，车厢,i,应移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于,i,（如果有多个缓冲轨满足这一条件，则选择队尾车厢编号最大的缓冲轨）；若没有这样的缓冲轨，则选择一个空的缓冲轨。,设,有,k,个缓冲轨,H,1,H,k,，,其中,H,k,为可直接将车厢从入轨移动到出轨的通道。,火车车厢重排,假定重排,9,节车厢，其初始次序为,3,6,9,2,4,7,1,8,5,，同时令,k,=3,，车厢重排过程如,下,图所示。,火车车厢重排,假定重排,n,节车厢，可使用,k,个缓冲轨，将每个缓冲轨看成是一个队列，用,nowout,表示下一个输出至出轨的车厢编号。火车车厢重排的算法描述如下：,火车车厢重排,算法,1.,分别对,k,个队列初始化；,2.nowout=1；,入轨车厢序号,i=0,；,3.当nowout=n时，,如果入轨中第,i,节车厢编号,cari=nowout,，则,输出该车厢；,nowout+,；,i+,；,否则，,如果缓冲轨队列中有队头元素,=nowout,，则,输出该车厢；,nowout+,；,否则，将,cari,移至缓冲轨：,求小于,cari,的最大队尾元素所在队列的编号,j,；,如果,j,存在，则,把,cari,移至缓冲轨,j,；,否则，,如果至少有一个空缓冲轨，则,把,cari,移至一个空缓冲轨；,否则，车厢无法重排，算法结束。,i+,；,4.算法结束。,火车车厢重排,算法,程序见,P.80,3,串,串,即为字符串，它是一种特殊的线性表，其每个数据元素由一个字符组成。,串的基本概念和基本操作,串的存储结构,3.1,串的基本概念和基本操作,串,是由零个或多个字符组成的有限序列。一般记为：,S,a,1,a,2,a,n,其中，,S,是串名；,引号括起来的字符序列是串值；,a,i,（,1,i,n,）是串中的字符，字符,a,i,在串中的位置为,i,；,n,是串中的字符个数，称为串的长度。,长度为零的串称为,空串,，它不包含任何字符。记为,S=,“”,。,由一个或多个空格字符组成的串称为,空格串,，其长度是串中空格字符的个数。,3.1,串的基本概念和基本操作,串可以比较大小，串的比较是按照对应字符的,ASCII,码进行的。称两个串是,相等,的，当且仅当这两个串的长度相等且各对应位置上的字符都相同。,串中任意个连续的字符组成的子序列称为该串的,子串,，包含子串的串相应地称为,主串,。,子串在主串中第一次出现时，子串的第一个字符在主串中的位置即为该,子串在主串中的位置,。,特别地，空串是任意串的子串，任意串是其自身的子串,串的抽象数据类型定义,ADT String,数据对象：,D,a,i,|,a,i,CharacterSet,i,=1,2,n,n,0,数据关系：,R1=|,a,i,-1,a,i,D,i,=2,3,n,基本操作：,Assign(&T,chars),初始条件：,chars,是字符串常量。,操作结果：生成一个值为,chars,的串,T,。,Copy(&T,S),初始条件：串,S,存在。,操作结果：由串,S,复制得串,T,。,Destroy(&S),初始条件：串,S,存在。,操作结果：销毁串,S,。,Empty(S),初始条件：串,S,存在。,操作结果：若,S,为空串，则返回,true,，否则返回,false,。,Compare(S,T),初始条件：串,S,和,T,存在。,操作结果：若,S,T,，则返回值,0,；若,S=T,，则返回值,=0,；若,S,T,，则返回值,0,。,串的抽象数据类型定义,Length(S),初始条件：串,S,存在。,操作结果：返回,S,的字符个数，即串的长度。,Concat(&T,S1,S2),初始条件：串,S1,和,S2,存在。,操作结果：用,T,返回由,S1,和,S2,联接而成的新串。,SubString(&Sub,S,pos,len),初始条件：串,S,存在，,1posStrLength(S),，且,0lenStrLength(S),pos+1,。,操作结果：用,Sub,返回串,S,的第,pos,个字符起长度为,len,的子串。,Index(S,T,pos),初始条件：串,S,和,T,存在，,T是非空串，,1posStrLength(S),。,操作结果：若主串,S,中存在和串,T,值相同的子串，则返回,T,在主串,S,中第,pos,个字符之后第一,次出现的位置；否则返回,0,。,Replace(&S,T,V),初始条件：串,S,，,T,和,V,均已存在，且,T,是非空串。,操作结果：用,V,替换主串,S,中出现的所有与,T,相等的不重叠的子串。,Insert(&S,pos,T),初始条件：串,S,和,T,存在，,1posStrLength(S)+1,。,操作结果：在串,S,的第,pos,个字符之前插入串,串的抽象数据类型定义,Delete(&S,pos,len),初始条件：串,S,存在，,1posStrLength(S)-len+1,。,操作结果：从串,S,中删除第,pos,个字符起长度为,len,的子串。,Clear(&S),初始条件：串,S,存在。,操作结果：将,S,清为空串。,在上述抽象数据类型定义的,13,种操作中，,串赋值,StrAssign,、串复制,Strcopy,、,串比较,StrCompare,、求串长,StrLength,、,串联接,Concat,以及求子串,SubString,等六种操作构成串类型的最小操作子集。,即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除,ClearString,和串销毁,DestroyString,外）可在这个最小操作子 集上实现。,3.1,串的基本概念和基本操作,1.若s1=This is a string.，s2=is，,则Length(s1)=7，index(s1,s2,1)=3，index(s1,s2,4)=6。,例如：,2.若s1=class，s2=room，,则Concat(t,s1,s2)的结果为 t=classroom,“,。,3.,若,s1=this，s2=there，则Compare(s1,s2)0，即s1s2。,4.SubString(s,There is a book on the desk.,10,6),的结果为,s=a book,“,。,3.1,串的基本概念和基本操作,6.,若,s1=There are three books on the desk.,，,则,Delete(s1,11,6),的结果为,s1=There are books on the desk.,5.,若,s1=There is a book on the desk.,，,s2=note,，,则,Insert(s1,12,s2),的结果为,s1=There is a notebook on the desk.,“,。,比较串的基本操作与线性表的基本操作，可以发现，串的基本操作通常以串的整体作为操作对象，而线性表的基本操作大多以单个元素作为操作对象，这是串操作的特点。,3.1,串的基本概念和基本操作,在上述抽象数据类型定义的,13,种操作中，,串赋值,StrAssign,、串复制,Strcopy,、,串比较,StrCompare,、求串长,StrLength,、,串联接,Concat,以及求子串,SubString,等六种操作构成串类型的最小操作子集。,即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除,ClearString,和串销毁,DestroyString,外）可在这个最小操作子 集上实现。,int Index(String S,String T,int pos),/T,为非空串。若主串,S,中第,pos,个字符之后存在与,T,相等的子串，则返回第一个这样的子串在,S,中的位置，否则返回,0,if(pos 0),n=StrLength(S);m=StrLength(T);i=pos;,while(i 0,）称为数组的维数，,b,i,是数组第,i,维的长度，,j,i,是数组元素的第,i,维下标，,ElemSet,数据关系：,R,=,R,1,R,2,R,n,R,i,=|0,j,k,b,k,-1,1,k,n,且,k,i,0,j,i,b,i,-2,D,i,=1,2,n,基本操作：,Init(&A,n,bound1,boundn),操作结果：若维数,n,和各维长度合法，则构造相应的数组,A,。,Destroy(&A),初始条件：数组,A,已存在。,操