栈和队列课件.ppt

1、队列的应用队列的应用1ppt课件 栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（栈（stack）1.栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，通常称插入、删除的这一端，即表尾为栈顶(Top)，另一端表头为栈底(Base)，不含元素的空表称空栈。特点：先进后出先进后出（FILO）或后进先出（LIFO）2ppt课件ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)2.栈的存储结构(1)顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置

2、设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。3ppt课件栈顶指针top,指向实际栈顶后的空位置top123450进栈Atop出栈栈满BCDEFtoptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空basebase栈空topbase012345 设栈的初始容量为Stacksize top=base,栈空，此时出栈则下溢（underflow)top-base=Stacksize,栈满，此时入栈则上溢（overflow)顺序栈的存储顺序栈的存储4ppt课件顺序存储栈的结

3、点类型的定义：#define STACK_INIT_SIZE 100;/存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量typedef struct SElemType *base;/栈底指针 SElemType *top;/栈顶指针 int stacksize；/当前已分配的存储空间 sqStack;5ppt课件顺序栈入栈算法顺序栈入栈算法 Push(sqStack&s,SElemType e)if(s.top-s.base=s.stacksize)s.base=(SElemtype*)realloc(s.base,(s.stacksize+STACK

4、INCREMENT)*sizeof(SElemType);if(!s.base)exit(“失败）；s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;6ppt课件0M-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;7ppt课件例例1：多进制输出：多进制输出：例 把十进制数159转换成八进制数(159)10=(2

5、37)815981982802 3 7 余 7余 3余 2toptop7top73top7328ppt课件 例1的解法：n n div 8 n mod 8 159 19 7 19 2 3 2 0 2 9ppt课件 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”

6、,e);10ppt课件 例2：假设以I和O分别表示入栈和出栈，栈的初态和终栈均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，下列所示的序列中，不合法的是()A.IOIIOIOO B.IOOIOIIO C.IIOOIOIO D.IIIOOIOO11ppt课件例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 e12ppt课件例4:设有一顺序栈S，元素s1、s2、s3、s4、s5、s6依次入栈，如果6个元素出栈的顺序是s2、s4、s3、s6、s5、s1，则栈的容量至少应该是（）A

7、、2 B、3 C、5 D、613ppt课件2.栈的存储结构(2)链栈链栈栈顶 .topdata link栈底 链栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链栈的栈顶在链头 适合于多栈操作结点定义：结点定义：typedef int datatype;typedef struct node datatype data;struct node *link;JD;14ppt课件入栈算法出栈算法 .栈底toptopxptop .栈底topq15ppt课件回文游戏回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不

8、等，非回文 若直到栈空都相等，回文字符串：“madam im adam”3.栈的应用16ppt课件表达式求值表达式求值（前提规则见教材（前提规则见教材52、53页）页）读一个字符，如为操作数，直接入到操作数栈；否则即为读一个字符，如为操作数，直接入到操作数栈；否则即为运算符，需判断：运算符，需判断：1、如当前运算符高于栈顶运算符，入到运算符栈；、如当前运算符高于栈顶运算符，入到运算符栈；2、如当前运算符低于栈顶运算符，栈顶运算符出栈，同时操、如当前运算符低于栈顶运算符，栈顶运算符出栈，同时操作数栈出栈两个数与运算符计算，并将结果入栈；作数栈出栈两个数与运算符计算，并将结果入栈；并输出到队列，当

9、前运算符再与栈顶运算符比较；并输出到队列，当前运算符再与栈顶运算符比较；3、如当前运算符等于栈顶运算符，且栈顶运算符为、如当前运算符等于栈顶运算符，且栈顶运算符为 “（”，当前运算符为，当前运算符为“）”，则脱去括号继续读下一字，则脱去括号继续读下一字符；符；4、如当前运算符等于栈顶运算符，且栈顶运算符为、如当前运算符等于栈顶运算符，且栈顶运算符为 “#”，当前运算符也为，当前运算符也为“#”，则表达式求值完毕。，则表达式求值完毕。表达式求值的处理规则表达式求值的处理规则17ppt课件运算符的优先级运算符的优先级()#(#=当前运算符当前运算符栈顶运算符栈顶运算符18ppt课件设两个栈：操作数

10、栈OPND和运算符栈OPTR操作数运算符4操作数运算符2操作数运算符636*操作数运算符618操作数运算符6操作数运算符-12例例:计算计算 2+4-3*6 参考书参考书54页例页例 3*（7-2）19ppt课件r主程序主程序srrrs子过程子过程1rst子过程子过程2rst子过程子过程3过程的嵌套调用4.栈的递归和嵌套应用20ppt课件递归过程及其实现递归：函数直接或间接的调用自身叫实现：建立递归工作栈优 点缺 点递归程序程序简短明确递归调用时参数须存储在栈中，访问时需要额外的时间，执行时间较长非递归程序较节省执行时间(无参数存取之问题)程序较长补充：递归的种类1、直接递归(direct r

11、ecursion)：在子程序中直接调用本身，就称为直接递归。2、间接递归：在子程序中调用了另外的子程序，再从另外子程序中调用原来的子程序，则称为间接递归。补充：补充：递归程序和非递归程序的比较递归程序和非递归程序的比较21ppt课件例例 递归的执行情况分析递归的执行情况分析 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问题算法：执行情况

12、：递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示n x y z 返回地址 25ppt课件/*Hanoi.txt*/main()int m;printf(Input the number of disks:);scanf(%d,&m);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 mo

13、ve(n,x,z);/将第n号盘子从A移到C上 hanoi(n-1,y,x,z);/将剩下的n-1个盘子从B移到C上，借助于Avoid move(int h,char c,char f)printf(%d:%c%cn,h,c,f);26ppt课件3.2 队列队列队列的定义及特点定义：队列是限定只能在表的一端进行插入插入，在表的另一端进行删除删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)27ppt课件链队列结点定义typedef struct node

14、int data;struct node *link;JD;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾28ppt课件frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队29ppt课件入队算法出队算法30ppt课件队列的顺序存储结构v实现：用一维数组实现sqMfront=0rear=0123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,re

15、ar,约定：rear指示队尾元素的下一个位置；front指示队头元素；初值front=rear=0空队列条件：front=rear入队列：sqrear+=x;出队列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontrear31ppt课件存在问题设数组维数为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,

16、则令rear=0;实现：利用“模”运算 入队：sq rear=x;rear=(rear+1)%M;出队：x=sq front;front=(front+1)%M;队满、队空判定条件0maxsize-11frontrear.32ppt课件012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志以区别队空、队满2.队列中留一个空位：队空：front=rear 队满：(rear+1)%M=front33p

17、pt课件入队算法：入队算法：void en_cycque(int sq,int front,int rear,intvoid en_cycque(int sq,int front,int rear,int x)x)if if(rear+1)%M)=front(rear+1)%M)=front)/)/对满对满 printf(overflowprintf(overflow););else else sqrear sqrear=x;=x;rear=(rear+1)%M;/rear=(rear+1)%M;/尾指针后移尾指针后移 34ppt课件出队算法：出队算法：int dl_cycque(int sq

18、,int front,int rear,int*q)if(front=rear)/对空 return(0);/返回出队失败标志 else *q=sqfront;/存储出队元素 front=(front+1)%M;/头指针后移一位 return(1);/返回出队成功标志 35ppt课件例5:在具有n个单元的循环队列中，队满时共有 _个元素。例6:若用单链表来表示队列，则应该选用()A.带尾指针的循环链表 B.带头指针的循环链表 C.带尾指针的非循环链表 D.带头指针的非循环链表36ppt课件队列应用举例 划分子集问题问题描述：已知集合A=a1,a2,an，及集合上的关系R=(ai,aj)|ai,

19、ajA,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 37ppt课件算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有

20、元素进组所用数据结构冲突关系矩阵 rij=1,i,j有冲突 rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrn38ppt课件工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队 若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组 若其在newr中对应位置为“0”,无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中如此反复，直到9个元素依

21、次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束39ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 90 1 2 3 4 5

22、 6 7 8 cqf r0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr0 0 0 0 0 0 0 0 00 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)40ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0

23、0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)41ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0

24、 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)42p

25、pt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 1 1 0 00 1 2 3 4 5 6 7 8 newr1 0 1 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(2,8),(9,4),(2,9),(2

26、,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)43ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1

27、 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)44ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3

28、4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)45ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0

29、0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)46ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0

30、 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)47ppt课件算法描述

31、0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 2 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6

32、,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)48ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00

33、1 2 3 4 5 6 7 8 resultR=(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)49ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 7 90 1 2 3 4 5 6 7 8 cqfr1 0

34、0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)50ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0

35、 01 0 0 0 1 1 0 1 1R=6 7 9 50 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)51ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1

36、1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=7 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)52ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1

37、 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 1 0 2 2 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7

38、,6),(3,7),(6,3)53ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 90 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(2,8),(9,4

39、),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)54ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 90 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2

40、 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)55ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 60 1 2 3 4 5 6

41、7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)56ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1

42、 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)57ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1

43、0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=90 1 2 3 4 5 6 7 8 cqfr0 1 1 0 1 0 1 0 00 1 2 3 4 5 6 7 8 newr1 2 1 1 3 4 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)58ppt课件算法描述0 1 0 0 0 0 0 0 00 1 0 1

44、 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=0 1 2 3 4 5 6 7 8 cqfr0 2 1 1 1 0 1 0 00 1 2 3 4 5 6 7 8 newr1 2 1 1 3 4 2 1 40 1 2 3 4 5 6 7 8 resultR=(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 59ppt课件优先级队列离散时间模拟图的广度优先遍历基数排序60ppt课件