c++栈和队列PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,栈,栈的应用,队列,队列的应用,第三章 栈和队列,1,栈和队列是两种特殊的线性表，是,操作受限,的线性表，称限定性,DS,3.1,栈（,stack,）,1.,栈的定义和特点,定义：,限定仅在,表尾,进行插入或删除操作的,线性表,，,通常,称插入、删除的这一端,，即,表尾为,栈顶,(Top)，另一端表头为,栈底,(B,ase,)，不含元素的空表称空栈,。,特点：,先进后出,（,FILO,）,或后进先出（,LIFO,）,2,a,n,a,1,a,2,.,栈底,栈顶,.,出栈,进栈,栈,s=(a1,a2,an),2.,栈的存储结构,(1),顺序栈,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。,因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个,变量,top,来指示当前栈顶的位置，通常称,top,为,栈顶指针,。,3,栈顶指针,top,指向实际栈顶,后的空位置,top,1,2,3,4,5,0,进栈,A,top,出栈,栈满,B,C,D,E,F,top,top,top,top,top,1,2,3,4,5,0,A,B,C,D,E,F,top,top,top,top,top,top,栈空,base,base,栈空,top,base,0,1,2,3,4,5,设栈的初始容量为,Stacksize,top=base,栈空，此时出栈则,下溢,（,underflow),top-base=,Stacksize,栈满，此时入栈则,上溢,（,overflow),顺序栈的存储,4,顺序存储栈的结点类型的定义：,#define,STACK_INIT_SIZE 100;,/,存储空间初始分配量,#define,STACKINCREMENT 10;,/,存储空间分配,增,量,typedef struct,SElemType *base;,/,栈底指针,SElemType *top;,/,栈顶指针,int stacksize,；,/,当前已分配的存储空间,sqStack,;,5,顺序栈入栈算法,Push(sqStack&s,SElemType e),if(s.top-s.base=s.stacksize),s.base=(SElemtype*),realloc,(s.base,(s.stacksize+,STACKINCREMENT,)*sizeof(SElemType);,if(!s.base)exit(“,失败）；,s.top=s.base+s.stacksize;,s.stacksize+=STACKINCREMENT;,*s.top+=e;,6,0,M-1,栈,1,底,栈,1,顶,栈,2,底,栈,2,顶,在一个程序中同时使用两个栈,顺序栈出栈算法,Status Pop(sqStack&s,SElemType&e),if(s.top=s.base)return ERROR,；,-s.top;,*e=*s.top;,return OK;,7,例,1,：,多进制输出：,例 把十进制数,159,转换成八进制数,(159),10,=(237),8,159,8,19,8,2,8,0,2 3 7,余,7,余,3,余,2,top,top,7,top,7,3,top,7,3,2,8,例,1,的解法：,n n div 8 n mod 8,159 19 7,19 2 3,2 0 2,9,void conversion()/,教材,48,页,initstack,(s);/,构造空栈，见教材,47,页,scanf(“%”,n);,while(n),push,(s,n%8);/,入栈,n=n/8;,while(!,Stackempty,(s)/,判断是否为空栈，见教材,46,页,pop,(s,e);/,出栈,e,为出栈元素,printf(“%d”,e);,10,例,2,：,假设以,I,和,O,分别表示入栈和出栈，栈的初态和终栈均为空，入栈和出栈的操作序列可表示为仅由,I,和,O,组成的序列，下列所示的序列中，不合法的是,(),A.IOIIOIOO B.IOOIOIIO,C.IIOOIOIO D.IIIOOIOO,B,11,例,3:,一个栈的入栈序列为,a,，,b,，,c,，,d,，,e,，则出栈的不可能序列为（）。,A,、,e d c b a B,、,d e c b a,C,、,d c e a b D,、,a b c d e,C,12,例,4:,设有一顺序栈,S,，元素,s1,、,s2,、,s3,、,s4,、,s5,、,s6,依次入栈，如果,6,个元素出栈的顺序是,s2,、,s4,、,s3,、,s6,、,s5,、,s1,，则栈的容量至少应该是（）,A,、,2 B,、,3 C,、,5 D,、,6,B,13,2.,栈的存储结构,(2),链栈,栈顶,.,top,data,link,栈底,链栈无栈满问题，空间可扩充,插入与删除仅在栈顶处执行,链栈的栈顶在链头,适合于多栈操作,结点定义：,typedef,int datatype;,typedef,struct node,datatype data;,struct node *link;,JD,;,14,入栈算法,出栈算法,.,栈底,top,top,x,p,top,.,栈底,top,q,15,回文游戏,：顺读与逆读字符串一样（不含空格）,d,a,d,top,1.,读入字符串,2.,去掉空格（原串）,3.,压入栈,4.,原串字符与出栈字符依次比较,若不等，非回文,若直到栈空都相等，回文,字符串：“,madam im adam”,3.,栈的应用,16,表达式求值,（前提规则见教材,52,、,53,页）,读一个字符，如为操作数，直接入到操作数栈；否则即为运算符，需判断：,1,、如当前运算符高于栈顶运算符，入到运算符栈；,2,、如当前运算符低于栈顶运算符，栈顶运算符出栈，同时操作数栈出栈两个数与运算符计算，并将结果入栈；,并输出到队列，当前运算符再与栈顶运算符比较；,3,、如当前运算符等于栈顶运算符，且栈顶运算符为,“,（,”,，当前运算符为,“,）,”,，则脱去括号继续读下一字符；,4,、如当前运算符等于栈顶运算符，且栈顶运算符为,“,#,”,，当前运算符也为,“,#,”,，则表达式求值完毕。,表达式求值的处理规则,17,运算符的优先级,(,),#,(,#,=,当前运算符,栈顶运算符,18,设两个栈：操作数栈,OPND,和运算符栈,OPTR,操作数,运算符,4,操作数,运算符,2,操作数,运算符,6,3,6,*,操作数,运算符,6,18,操作数,运算符,6,操作数,运算符,-12,例,:,计算,2+4-3*6,参考书,54,页例,3*,（,7-2,）,19,r,主程序,s,r,r,r,s,子过程,1,r,s,t,子过程,2,r,s,t,子过程,3,过程的嵌套调用,4.,栈的递归和嵌套应用,20,递归过程及其实现,递归：函数直接或间接的调用自身叫,实现：建立递归工作栈,优 点,缺 点,递归程序,程序简短明确,递归调用时参数须存储在栈中，访问时需要额外的时间，执行时间较长,非递归程序,较节省执行时间,(,无参数存取之问题,),程序较长,补充：,递归的种类,1,、直接递归,(direct recursion),：在子程序中直接调用本身，就称为直接递归。,2,、间接递归：在子程序中调用了另外的子程序，再从另外子程序中调用原来的子程序，则称为间接递归。,补充：,递归程序和非递归程序的比较,21,例 递归的执行情况分析,void write(int w),int i;,if(w!=0),write(w-1);,for(i=1;i1,时，先把上面,n-1,个圆盘从,A,移到,B,然后将,n,号盘从,A,移到,C,再将,n-1,个盘从,B,移到,C,。,即把求解,n,个圆盘的,Hanoi,问题转化为求解,n-1,个圆盘的,Hanoi,问题，依次类推，直至转化成只有一个圆盘的,Hanoi,问题,算法：,执行情况：,递归工作栈,保存内容：形参,n,x,y,z,和返回地址,返回地址用行编号表示,n x y z,返回地址,25,/*Hanoi.txt*/,main(),int m;,printf(Input the number of disks:);,scanf(%d,printf(The steps to moving%3d disks:n,m);,hanoi(m,A,B,C);,void hanoi(int n,char x,char y,char z),if(n=1)move(1,x,z);/,将第,1,号盘子从,A,移到,C,上,else,hanoi(n-1,x,z,y);/,将,n-1,个盘子从,A,移到,B,上，借助于,C,move(n,x,z);/,将第,n,号盘子从,A,移到,C,上,hanoi(n-1,y,x,z);/,将剩下的,n-1,个盘子从,B,移到,C,上，借助于,A,void move(int h,char c,char f),printf(%d:%c%cn,h,c,f);,26,3.2,队列,队列的定义及特点,定义：队列是限定只能在表的一端进行,插入,，在表的,另,一端进行,删除,的线性表,队尾,(rear),允许插入的一端,队头,(front),允许删除的一端,队列特点：,先进先出,(FIFO),a1 a2 a3.an,入队,出队,front,rear,队列,Q=(a1,a2,an),27,链队列,结点定义,typedef struct node,int data;,struct node,*link,;,JD;,头结点,.,front,队头,队尾,rear,设队首、队尾指针,front,和,rear,front,指向头结点，,rear,指向队尾,28,front,rear,x,入,队,x,front,rear,y,入,队,x,y,front,rear,x,出,队,x,y,front,rear,空队,front,rear,y,出,队,29,入队算法,出队算法,30,队列的顺序存储结构,实现：用一维数组实现,sqM,front=0,rear=0,1,2,3,4,5,0,队空,1,2,3,4,5,0,front,J1,J2,J3,入队,J1,J2,J3,rear,rear,1,2,3,4,5,0,J4,J5,J6,入队,J4,J5,J6,front,设两个指针,front,rear,约定：,rear,指示队尾元素,的下一个位置,；,front,指示队头元素,；,初值,front=rear=0,空队列条件：,front=rear,入队列：,sqrear+=x;,出队列：,x=sqfront+;,rear,rear,front,rear,1,2,3,4,5,0,J1,J2,J3,出队,J1,J2,J3,front,front,front,rear,31,存在问题,设数组维数为,M,，,则：,当,front=0,rear=M,时，再有元素入队发生溢出,真溢出,当,front0,rear=M,时，再有元素入队发生溢出,假溢出,解决方案,队首固定，每次出队剩余元素向下移动,浪费时间,循环队列,基本思想：把队列,设想成环形,，让,sq0,接在,sqM-1,之后，若,rear+1=M,则令,rear=0;,实现：利用“模”运算,入队：,sq rear=x;,rear=(rear+1)%M;,出队：,x=sq front;front=(front+1)%M;,队满、队空判定条件,0,maxsize-1,1,front,rear,.,.,32,0,1,2,3,4,5,rear,front,J5,J6,J7,0,1,2,3,4,5,rear,front,J4,J9,J8,J4,J5,J6,0,1,2,3,4,5,rear,front,初始状态,J4,J5,J6,出队,J7,J8,J9,入队,队空：,front=rear,队满：,front=rear,解决方案：,1.,另外,设一个标志,以区别队空、队满,2,.,队列中留一个空位,：,队空：,front=rear,队满：(,rear+1)%,M,=front,33,入队算法：,void en_cycque(int sq,int front,int rear,int x),if,(,(rear+1)%M)=front,)/,对满,printf(overflow);,else,sqrear=x;,rear=(rear+1)%M;/,尾指针后移,34,出队算法：,int dl_cycque(int sq,int front,int rear,int*q),if(,front=rear,)/,对空,return(0);/,返回出队失败标志,else,*q=sqfront;/,存储出队元素,front=(front+1)%M;/,头指针后移一位,return(1);/,返回出队成功标志,35,例,5:,在具有,n,个单元的循环队列中，队满时共有,_,个元素。,n-1,例,6:,若用单链表来表示队列，则应该选用,(),带尾指针的循环链表,带头指针的循环链表,C.,带尾指针的非循环链表,D.,带头指针的非循环链表,A,36,队列应用举例,划分子集问题,问题描述：已知集合,A=a1,a2,an,，,及集合上的关系,R=(ai,aj)|ai,aj,A,ij,，,其中(,ai,aj),表示,ai,与,aj,间存在冲突关系。要求将,A,划分成,互不相交,的子集,A1,A2,Ak,(kn),，,使任何子集中的元素均无冲突关系，同时要求,分子集个数尽可能少,例,A=1,2,3,4,5,6,7,8,9,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),可行的子集划分为：,A1=1,3,4,8,A2=2,7,A3=5,A4=6,9,37,算法思想：利用,循环筛选,。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组,所用数据结构,冲突关系矩阵,rij=1,i,j,有冲突,rij=0,i,j,无冲突,循环队列,cqn,数组,resultn,存放每个元素分组号,工作数组,newrn,38,工作过程,初始状态：,A,中元素放于,cq,中，,result,和,newr,数组清零，组号,group=1,第一个元素出队，将,r,矩阵中第一行“1”拷入,newr,中对应位置，这样，凡与第一个元素有冲突的元素在,newr,中对应位置处均为“1”,下一个元素出队,若其在,newr,中对应位置为“1”，有冲突，重新插入,cq,队尾，参加下一次分组,若其在,newr,中对应位置为“0”,无冲突，可划归本组；再将,r,矩阵中该元素对应行中的“1”拷入,newr,中,如此反复，直到9个元素依次出队，由,newr,中为“0”的单元对应的元素构成第1组,将组号,group,值“1”写入,result,对应单元中,令,group=2,newr,清零，对,cq,中元素重复上述操作，直到,cq,中,front=rear,即队空，运算结束,39,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0 0 0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,newr,0 0 0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,初始,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),40,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,newr,1,0 0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),41,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,newr,1,0 0 0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),42,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,4 5 6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0 0,1,1,0 0,0 1 2 3 4 5 6 7 8,newr,1,0,1,0 0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),43,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5 6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),44,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5,6 7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),45,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5,6,7 8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),46,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5,6,7,8 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0 0 0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),47,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5,6,7,9,0 1 2 3 4 5 6 7 8,cq,f,r,0,2,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),48,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,2,5,6,7,9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0 0,1,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,0,1,1,0 0 0,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),49,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,5,6,7,9,0 1 2 3 4 5 6 7 8,cq,f,r,1,0 0 0,1,1,0,1,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,0 0 0,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),50,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,6,7,9,5,0 1 2 3 4 5 6 7 8,cq,f,r,1,0 0 0,1,1,0,1,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,0 0 0,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),51,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,7,9,5 6,0 1 2 3 4 5 6 7 8,cq,f,r,1,0 0 0,1,1,0,1,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,0 0 0,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),52,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,9,5 6,0 1 2 3 4 5 6 7 8,cq,f,r,1,0,1,0,2,2,0,1,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,0 0,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),53,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,5 6 9,0 1 2 3 4 5 6 7 8,cq,f,r,1,0,1,0,1,1,0,1,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,0 0,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),54,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,6 9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0,1,0,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,3,0,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),55,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,9 6,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0,1,0,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,3,0,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),56,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,9,6,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,0,1,0,1,1,0,1,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,3,0,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),57,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,9,0 1 2 3 4 5 6 7 8,cq,f,r,0,1,1,0,1,0,1,0 0,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,3,4,2,1,0,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),58,算法描述,0 1 0 0 0 0 0 0 0,0 1 0 1 1 0 0 0 0,0 0 0 0 0 1 1 0 0,0 0 0 0 1 0 0 0 1,0 1 0 1 0 1 1 0 1,0 1 1 0 1 0 1 0 0,0 0 1 0 1 1 0 0 0,0 1 0 0 0 0 0 0 0,1 0 0 0 1 1 0 1 1,R=,0 1 2 3 4 5 6 7 8,cq,f,r,0,2,1,1,1,0,1,0 0,0 1 2 3 4 5 6 7 8,newr,1,2,1,1,3,4,2,1,4,0 1 2 3 4 5 6 7 8,result,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),Ch3_9.c,可行的子集划分为：,A1=1,3,4,8,A2=2,7,A3=5,A4=6,9,59,优先级队列,离散时间模拟,图的广度优先遍历,基数排序,60,