3.3栈与递归的实现-N皇后问题 3.3栈与递归的实现-N皇后问题 ·数据结构设计 ,数据结构设计 :标识每一列是否巴整安放了重后 。标汉每一列是否已经安放了皇后 线性表，表长为N —顺序表col,表长为N ,标议各条主对角战是否已经安放了复后 标识各条主对角线是否已经安放了直后 一线性表，表长为2N-1 一顺序表md,表长为2N-1 ,标识各条次对角线是香已经安放了重后 线性表，表长为2N-1 ,桥识各条次对角线是否已经安放了重后 。记录当前各行的皇后在第几列一布局状况 —顺序表sd,表长为2N-1 一线性表，表长为N ,花录当前各行的皇后在第几列一布局状况 。存储结构的选择 -顺序表q,表长为N 表长田定，有随机歌的要求—顺序表 回 38/50 图 3.3栈与递归的实现-N皇后问题 3.4队列 ,算法 ■定义 colljl-1; Queen(int i,int n){ colljl 特珠的线性表：操作受限 &&!mdln+i-j-1] mdln+i-j-1l-1; (int j=0;j<n;j+) 只允许在一端进行插入，而在另一端测除元素 &&sd[i+jl sdli+jl-1; (第i行第j列没有攻击 允许插入的一端为队尾(rear),允许测除的一端为队头(head) qlil-j: 在第i行第j列安放皇后： ,双端队列：限定插入和副除绿作在表的两端进行 if(i=n-1)输出一个布局， ■逻辑特征：先进先出(FIFO) else Queen (i+1,n); 输出q 撒消第i行第j列的皇后； ■ADT Queue:初雄化空队、入队、出队、判断队空、判嘶 队满、取队头 colljl=0; mdln+i-j-11-0; 三44口4二入队 出队 sdli+jl-0; 图 队头 队尾 39/150 40/50 图 ADT Queuef 数据对象：D=a周∈ElemSet,=12,一n,n≥0 GetElem(L i,&e) 数据关系：R-R1R1-长1>%t,a∈D,2,3,…n} GetHead(Q.&e 基本操作： 切蹈条件：风列Q已存在且垂空 InitQueue(&Q) 操作结果：用：返回Q中队头元素 操作结果：构造一个空队列Q 切路条件：队列Q已存在Listinsert(&L,山c EnQueue(&Q.eD DestroyQueue(&Q) 初始条件：队列Q已存在 操作结果：插入元素•为Q的新的队尾元素 操作结果：销级队列Q ClearQueue(&Q) 初始条种：队列Q已存在且非空ListDelete(&L,i&e】 初始条件：队列Q已存在 操作结果：副除Q的队头元素，并用。返国其值 操作结果：将队列Q重置为空队列 Queue Traverse(Q.visit() 初始条件：队列Q已存在且非空 QueueEmpty(QD 初需桑件：队列Q己存在 操作结果：从队头到队尾依次对Q的每个数据元素调用函数0， 操作结果：若Q为空队列，则返回TRE,否则返回FALSE 旦0失，则操作失 ADT Queue. QueueLength(Q) 初始条件：队列Q已存在 操作结果：返回队列Q中数据元素的个 41/50 图 42/50 回 77 37/50 3.3 栈与递归的实现–N皇后问题 „ 数据结构设计 „ 标识每一列是否已经安放了皇后 ——线性表，表长为N „ 标识各条主对角线是否已经安放了皇后 ——线性表，表长为2N-1 „ 标识各条次对角线是否已经安放了皇后 ——线性表，表长为2N-1 „ 记录当前各行的皇后在第几列—布局状况 ——线性表，表长为N „ 存储结构的选择 表长固定，有随机存取的要求——顺序表 38/50 3.3 栈与递归的实现–N皇后问题 „ 数据结构设计 „ 标识每一列是否已经安放了皇后 ——顺序表col，表长为N „ 标识各条主对角线是否已经安放了皇后 ——顺序表md，表长为2N-1 „ 标识各条次对角线是否已经安放了皇后 ——顺序表sd，表长为2N-1 „ 记录当前各行的皇后在第几列—布局状况 ——顺序表q，表长为N 39/50 3.3 栈与递归的实现–N皇后问题 „ 算法 void Queen( int i, int n ) { for ( int j = 0; j < n; j++ ) { if ( 第 i 行第 j 列没有攻击 ) { 在第 i 行第 j 列安放皇后; if ( i == n-1 ) 输出一个布局; else Queen ( i+1, n ); 撤消第 i 行第 j 列的皇后; } } } !col[j] && !md[n+i-j-1] && !sd[i+j] col[j]= 1; md[n+i-j-1]=1; sd[i+j]=1; q[i] = j; 输出q col[j]= 0; md[n+i-j-1]=0; sd[i+j]=0; q[i] = 0; 40/50 3.4 队列 „ 定义 特殊的线性表：操作受限 只允许在一端进行插入，而在另一端删除元素 允许插入的一端为队尾(rear),允许删除的一端为队头(head) „ 双端队列：限定插入和删除操作在表的两端进行 „ 逻辑特征：先进先出(FIFO) „ ADT Queue：初始化空队、入队、出队、判断队空、判断 队满、取队头 队头 出队 入队 a1 a2 a3 … … an 队尾 41/50 42/50 GetElem(L, i, &e) ListInsert(&L, i, e) ListDelete(&L, i, &e)