top b top a a top 空栈 a 进栈 b 进栈 top top e e e top d d d c c c b b b a a a e 进栈 f 进栈溢出 e 退栈

d top c c top b b b a a top a d 退栈 c 退栈 b 退栈 a top top a 退栈 空栈

双栈共享一个栈空间 0 maxSize-1 V b[0] t[0] t[1] b[1]

栈的应用 栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。 1.算术表达式的求值 算术表达式中包含了算术运算符和算术量(常量、变量、函数)，而运算符之间又存在着优先级，不能简单地进行从左到右运算，编译程序在求值时，不能简单从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右(C++中有些从右到左)。

因此，要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数（算术量），在进行表达式求值时，编译程序从左到右扫描，遇到操作数，一律进入操作数栈，遇到运算符，则应与运算符栈的栈顶比较，若运算符优先级高于栈顶则进栈，否则退栈，退栈后，在操作数栈中退出两个元素(先退出在运算符右，后退出在运算符左)，然后用运算符栈中退出的栈顶元素进行运算，运算的结果存入操作数栈中，直到扫描完毕。这时运算符栈为空，操作数栈中只有一个元素，即为运算的结果。 例求表达式1+2*3-4/2的值，栈的变化如下。

步骤 操作数栈 运算符栈 说明 开始 两栈均为空 1 1 1进入操作数栈 2 1 + +进入运算符栈 3 1 2 + 2进入操作数栈 4 1 2 + * *进入运算符栈 5 1 2 3 + * 3进入操作数栈 6 1 + 退栈 7 1 6 + 2*3进入操作数栈 8 退栈 1+6进入操作数栈 9 7

步骤 操作数栈 运算符栈 说明 10 7 - -进入运算符栈 11 7 4 - 4进入操作数栈 12 7 4 - / /进入运算符栈 13 7 4 2 - / 2进入操作数栈 14 7 - 退栈 15 7 2 - 4/2进入操作数栈 16 退栈 17 5 7-2进入操作数栈

当然，算术表达式除了简单求值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。刚才的例3-3中的表达式就是中缀表达式，中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律， 例如，对于下列各中缀表达式：（1）       3/5+8 （2）       18-9*(4+3) （3）       (25+x)*(a*(a+b)+b) 对应的后缀表达式为： (1)3 5 / 8 + (2)18 9 4 3 + * - (3)25 x + a a b + * b + *

2．中缀表达式变成等价的后缀表达式 将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。 将中缀表达式(1+2)*((8-2)/(7-4))变成等价的后缀表达式。  现在用栈来实现该运算，栈的变化及输出结果如 下

步骤 栈中元素 输出结果 说明 1 (   （进栈 2 输出1 3 ( + +进栈 4 1 2 输出2 5 1 2 + +退栈输出，退栈到（止 6 * *进栈 7 * ( 8 * ( ( 9 1 2 + 8 输出8 10 * ( ( - - 进栈

步骤 栈中元素 输出结果 说明 11 * ( ( - 1 2 + 8 2 输出2 12 * ( 1 2 + 8 2 - 步骤 栈中元素 输出结果 说明 11 * ( ( - 1 2 + 8 2 输出2 12 * ( 1 2 + 8 2 - -退栈输出，退栈到（止 13 * ( / / 进栈 14 * ( / ( （ 进栈 15 1 2 + 8 2 - 7 输出7 16 * ( / ( - - 进栈 17 1 2 + 8 2 - 7 4 输出4 18 1 2 + 8 2 - 7 4 - 19 * 1 2 + 8 2 - 7 4 - / /退栈输出，退栈到（止 20   1 2 + 8 2 - 7 4 - / * *退栈并输出

3．后缀表达式的求值 将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。 例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值， 栈的变化情如下：

步骤 栈中元素 说明 1 1进栈 2 1 2 2进栈 3   遇+号退栈2和1 4 1+2=3的结果3进栈 5 3 8 8进栈 6 3 8 2 7 遇-号退栈2和8 8 3 6 8-2=6的结果6进栈 9 3 6 7 7进栈 10 3 6 7 4 4进栈

从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。 步骤 栈中元素 说明 11 3 6 遇-号退栈4和7 12 3 6 3 7-4=3的结果3进栈 13 3 遇/号退栈3和6 14 3 2 6/3=2的结果2进栈 15   遇*号退栈2和3 16 6 3*2=6进栈 17 扫描完毕，运算结束 从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。

4．函数的嵌套调用 在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执行，因此必须用栈来保存函数中中断的地址，以便调用返回时能从断点继续往下执行。 例 设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）。

主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态，进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数a处于挂起状态，进入函数b中执行，函数b中调用函数c， 留下一个断点地址t进栈， 然后函数b处于挂起状态，进入函数c中执行，函数c执行完后，要返回断点处继续执行，但返回到那一个断点呢?根据栈顶元素来决定。返回时，执行退栈操作，先退出t，故返回t断点继续执行， 接着退栈退出s，故返回s断点继续执行，接着退栈退出r，返回r断点继续执行，最后栈为空，算法结束。

小型迷宫 迷宫问题 4 3 5 2 1 7 6 路口 动作 结果 1 (入口) 正向走 进到 2 2 左拐弯 进到 3 3 右拐弯 进到 4 4 (堵死) 回溯 退到 3 3 (堵死) 回溯 退到 2 2 正向走 进到 5 5 (堵死) 回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7 (出口) 6 左 0 直 2 右 0 行 3 行 5 行 6 0 0 4 0 0 0 7 0 0 7 小型迷宫的数据

迷宫的类定义 #include <iostream.h> #include <fstream.h> #include <stdlib.h> class Maze { private: int MazeSize; int EXIT; Intersection *intsec; public: Maze ( char *filename ); int TraverseMaze ( int CurrentPos ); }

Maze::Maze ( char *filename ) { //构造函数：从文件 filename 中读取各路口//和出口的数据 ifstream fin; fin.open ( filename, ios::in | ios::nocreate ); //为输入打开文件,文件不存在则打开失败 if ( !fin ) { cout << “迷宫数据文件” << filename << “打不开” << endl; exit (1); } fin >> MazeSize; //输入迷宫路口数

intsec = new Intersection[MazeSize+1]; //创建迷宫路口数组 for ( int i=1; i<=MazeSize; i++ ) fin>>intsec[i].left >> intsec[i].forward >> intsec[i].right; fin >> EXIT; //输入迷宫出口 fin.close ( ); } 迷宫漫游与求解算法 int Maze::TraverseMaze ( int CurrentPos ) { if ( CurrentPos > 0 ) { //路口从 1 开始

if ( CurrentPos == EXIT ) {. //出口处理 if ( CurrentPos == EXIT ) { //出口处理 cout << CurrentPos << " "; return 1; } else //递归向左搜寻可行 if (TraverseMaze(intsec[CurrentPos].left )) { cout << CurrentPos << “ ”; return 1; } else //递归向前搜寻可行 if (TraverseMaze(intsec[CurrentPos].forward)) { cout << CurrentPos << “ ”; return 1; } else //递归向右搜寻可行 if (TraverseMaze(intsec[CurrentPos].right)) { cout << CurrentPos << " "; return 1; } } return 0; }

递归与回溯 常用于搜索过程 n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。

    k = i+j k = n+i-j-1 0#次对角线 2#次对角线 1#次对角线 4#次对角线 3#次对角线 0 1 2 3 6#次对角线 k = i+j 1#次对角线 3#次对角线 5#次对角线 0 1 2 3 1 2 3    0#主对角线 2#主对角线 4#主对角线 6#主对角线 1#主对角线 3#主对角线 5#主对角线  k = n+i-j-1

解题思路 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 j 列安放一个皇后： 如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。

col [n] ：col[i] 标识第 i 列是否安放了皇后 设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列

void Queen( int i ) { for ( int j = 0; j < n; j++ ) { if ( 第 i 行第 j 列没有攻击 ) { 在第 i 行第 j 列安放皇后； if ( i == n-1 ) 输出一个布局； else Queen ( i+1 ); 撤消第 i 行第 j 列的皇后； }

算法求精 void Queen( int i ) { for ( int j = 0; j < n; j++ ) { if ( !col[j] && !md[n+i-j-1] && !sd[i+j] ) { /*第 i 行第 j 列没有攻击 */ col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; /*在第 i 行第 j 列安放皇后*/

for ( int k = 0; k < n; k++ ) cout << q[k] << ‘,’; if ( i == n-1 ) { /*输出一个布局*/ for ( int k = 0; k < n; k++ ) cout << q[k] << ‘,’; cout << endl; } else Queen ( i+1 ); col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; /*撤消第 i 行第 j 列的皇后*/

地图四染色问题 使地图中相邻的国家或行政区域不重色，最少可用四种颜色对地图着色。 说明此结论，利用栈采用回溯法对地图着色。 思想：对每个行政区编号：1-7 对颜色编号；a、b、c、d； 从第一号行政区开始逐一染色，每一个区域逐次用四种颜色进行试探，若所取颜色与周围不重，则用栈记下来该区域的色数，否则依次用下一色数进行试探。若出现a-d均与周围发生重色，则需退栈回溯，修改当前栈顶的色数。

Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I<=n) { while(( J<=4)&&(I<=n)) { k=1; // k表示已经着色的区域号 while(( K<I)&&(s[K]R[I,K]!=J)) K=K+1; // 若不相邻，或若相邻且不重色，对下一个区域判断。 IF (K<I) THEN J=J+1 ELSE{ s[I]=J; I=I+1; J=1; } } IF (J>4) THEN { I=I-1; J=s[I]+1 (7) 1# 粉色 2# 黄色 3# 红色 4# 绿色 (3) (2) (1) (6) (4) (5) S [ 1 : 7 ] 1 2 3 4 5 6 7 1 2 3 4 R [ 1: 7 , 1 : 7 ] 1 2 4 3 1 2 3 4 5 6 7 1 2 3 1 2 3 4 5 6 7   4、 地图四染色问题 “四染色”定理是计算机科学中著名定理之一1，即可以用不多于四色对地图着色，使相邻的行政区域不重色。下面是对一幅给定地图进行染色的回朔算法。 1 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4

while(( k<I)&&(s[k]R[I,k]!=J)) Void mapcolor(int R[][],int n,int s[]) { …… I=6; J=1; // I为区域号，J为染色号 while ( I<=n) { while(( J<=4)&&(I<=n)) { k=1; // k表示已经着色的区域号 while(( k<I)&&(s[k]R[I,k]!=J)) k=k+1; =4 // 若不相邻，或若相邻且不重色，对下一个区域判断。 IF (K<I) //相邻且重色 THEN J=J+1 =5 ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色 } IF (J>4) THEN { I=I-1; J=s[I]+1 }} 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7   4、 地图四染色问题 “四染色”定理是计算机科学中著名定理之一1，即可以用不多于四色对地图着色，使相邻的行政区域不重色。下面是对一幅给定地图进行染色的回朔算法。 3 4 2 1 k=4 I=6,J=5

a 粉色 b 黄色 c 红色 d 绿色 b c d a b d c (1) (2) (4) (7) (3) (5) (6) a b c a S [ 1 : 7 ] 1 2 3 4 5 6 7 a b c d a b d c (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) (1) (2) (4) (7) (3) (5) (6) a b c a b c a b c d a b c d a b c d

队列的进队和出队 A 空队列 A进队 A B A B C D B进队 C, D进队 B C D C D A退队 B退队 C D E F G front rear front rear A进队 A B A B C D front rear B进队 front rear C, D进队 B C D C D front rear A退队 front rear B退队 C D E F G C D E F G front rear E,F,G进队 front rear H进队,溢出

A A C B F G E H A D C B C B C 空队列 A进队 B, C进队 A退队 B退队 D,E,F,G,H进队 front 6 7 6 7 front 6 7 front rear 5 5 5 A A 4 1 4 1 4 1 C B rear 3 2 3 2 2 rear 3 空队列 A进队 B, C进队 6 7 6 7 6 7 rear F G 5 5 5 E H A D 4 1 4 1 4 1 C B C B C front 2 2 3 2 rear 3 rear 3 front front A退队 B退队 D,E,F,G,H进队

优先级队列 (Priority Queue) 优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素 例如下表：任务的优先权及执行顺序的关系 数字越小，优先权越高

优先队列的类定义 #include <assert.h> #include <iostream.h> $include <stdlib.h> const int maxPQSize = 50; //缺省元素个数 template <class Type> class PQueue { public: PQueue ( ); ~PQueue ( ) { delete [ ] pqelements; } void PQInsert ( const Type & item ); Type PQRemove ( );

void makeEmpty ( ) { count = -1; } int IsEmpty ( ) const { return count == -1; } int IsFull ( ) const { return count == maxPQSize; } int Length ( ) const { return count; } private: Type *pqelements; //存放数组 int count; //队列元素计数 }

优先队列部分成员函数的实现 template <class Type> PQueue<Type>::PQueue ( ) : count (-1) { pqelements = new Type[maxPQSize]; assert ( pqelements != 0 ); //分配断言 } template <class Type> void PQueue<Type> :: PQInsert ( const Type & item ) { assert ( !IsFull ( ) ); //判队满断言 count ++； pqelements[count] = item;

template <class Type> Type PQueue<Type>::PQRemove ( ) { assert ( !IsEmpty ( ) ); //判队空断言 Type min = pqelements[0]; int minindex = 0; for ( int i=1; i<count; i++ ) //寻找最小元素 if ( pqelements[i] < min ) //存于min { min = pqelements[i]; minindex = i; } pqelements[minindex] = pqelements[count-1]; count-- ; //删除 return min; }

除了栈和队列之外，还有一种限定性数据结构，它们是双端队列（double-ended queue）。 双端队列是限定插入和删除操作在线性表的两端进行，我们可以将它看成是栈底连在一起的两个栈，但它与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如图3-13所示。 端1 端2 插入 删除   图 双端队列的示意图 a1 a2 ai a0 an-1 … 在实际使用中，还有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入）；输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除）。如果限定双端队列从某个端点插入的元素只能从该端点删除，则双端队列就蜕变为两个栈底相邻接的栈了。 尽管双端队列看起来比栈和队列更灵活，但实际中并不比栈和队列实用，故在此不再深入讨论。

队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出若干例子来说明。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。

第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。

— 逐行打印二项展开式 (a + b)i 的系数 杨辉三角形 (Pascal’s triangle)

分析第 i 行元素与第 i+1行元素的关系 目的是从前一行的数据可以计算下一行的数据

从第 i 行数据计算并存放第 i+1 行数据

利用队列打印二项展开式系数的程序 #include <stdio.h> #include <iostream.h> #include "queue.h" void YANGVI ( int n ) { Queue q; //队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1); int s = 0;

for ( int i=1; i<=n; i++ ) { //逐行计算 cout << endl; q.EnQueue (0); for ( int j=1; j<=i+2; j++ ) { //下一行 int t = q.DeQueue ( ); q.EnQueue ( s+t ); s = t; if ( j != i+2 ) cout << s << ' '; }

划分子集问题 问题描述：已知集合A={a1,a2,……an}，及集合上的关系R={ (ai,aj) | ai,ajA, ij}，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少 例 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 }

算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组 所用数据结构 冲突关系矩阵 r[i][j]=1, i,j有冲突 r[i][j]=0, i,j无冲突 循环队列cq[n] 数组result[n]存放每个元素分组号 工作数组newr[n]

工作过程 初始状态：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,即队空，运算结束

算法描述 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) } 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 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 newr 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) } 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 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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 r f 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) } 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 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) } 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 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) } 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 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) } 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 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 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) } 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 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) } 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 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) } 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 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) } 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 1 0 0 0 1 1 0 1 1 R= 9 6 0 1 2 3 4 5 6 7 8 cq r f 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) } 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 1 0 0 0 1 1 0 1 1 R= 9 0 1 2 3 4 5 6 7 8 cq r f 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) } 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 1 0 0 0 1 1 0 1 1 R= 0 1 2 3 4 5 6 7 8 cq f r 0 1 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 可行的子集划分为： A1={ 1,3,4,8 } A2={ 2,7 } A3={ 5 } A4={ 6,9 }

void division(int r[][N],int n,int cq[], int newr[],int result[]) { int k,i,pre,group; for(k=0;k<n;k++) cq[k]=k+1; front=n-1; rear=n-1; newr[k]=0; group=1; pre=0; do{ front=(front+1)%n; i=cq[front]; if(i<pre) void division(int r[][N],int n,int cq[], int newr[],int result[]) { int k,i,pre,group; for(k=0;k<n;k++) cq[k]=k+1; front=n-1; rear=n-1; newr[k]=0; group=1; pre=0; do{ front=(front+1)%n; i=cq[front]; if(i<pre) { group++; result[i-1]=group; for(k=0;k<n;k++) newr[k]=r[i-1][k]; } else if(newr[i-1]!=0) { rear=(rear+1)%n; cq[rear]=i; else { result[i-1]=group; newr[k]=newr[k]+r[i-1][k]; pre=i; }while(rear!=front); { group++; result[i-1]=group; for(k=0;k<n;k++) newr[k]=r[i-1][k]; } else if(newr[i-1]!=0) { rear=(rear+1)%n; cq[rear]=i; else { result[i-1]=group; newr[k]=newr[k]+r[i-1][k]; pre=i; }while(rear!=front);

栈和队列小结 主要介绍了如下一些基本概念： 栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。 栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。 双向栈：使两个栈共享一维数组stack[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为-1和MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。

栈的链式存储结构：栈的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储栈中的数据元素，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。 队列：队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。因此，队列也被称为“先进先出”表。

队列的顺序存储结构：利用一组地址连续的存储单元依次存放队列中的数据元素，称为队列的顺序存储结构。 队列的链式存储结构：队列的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储队列中的数据元素，这种结构的队列称为链队列。在一个链队列中需设定两个指针(头指针和尾指针)分别指向队列的头和尾。 除上述基本概念以外，学生还应该了解：栈的基本操作（初始化、栈的非空判断、入栈、出栈、取栈元素、置栈空操作）、栈的顺序存储结构的表示、栈的链式存储结构的表示、队列的基本操作（初始化、队列非空判断、入队列、出队列、取队头元素、求队列长度）、队列的顺序存储结构、队列的链式存储结构，掌握顺序栈（入栈操作、出栈操作）、链栈（入栈操作、出栈操作）、顺序队列（入队列操作、出队列操作）、链队列（入队列操作、出队列操作）。