遞歸的概念遞歸過程與遞歸工作棧遞歸與回溯廣義表(編輯修改稿)
2024-08-17 13:45 本頁面
【文章內(nèi)容簡介】 2 3 0 1 2 3 k = i+j k = n+ij1 解題思路 ? 安放 第 i 行 皇后時，需要在列的方向從 0 到 n1 試探 ( j = 0, …, n 1 ) ? 在 第 j 列 安放一個皇后： ? 如果在 列 、 主對角線 、 次對角線 方向有其它皇后，則出現(xiàn)攻擊，撤消在 第 j 列 安放的皇后。 ? 如果沒有出現(xiàn)攻擊，在 第 j 列 安放的皇后不動，遞歸安放第 i+1行皇后。 ? 設(shè)置 4 個數(shù)組 ? col[n] :col[i] 標識第 i 列是否安放了皇后 ? md[2n1] : md[k] 標識第 k 條主對角線是否安放了皇后 ? sd[2n1] : 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 == n1 ) 輸出一個布局 ； else Queen ( i+1 )。 } 撤消 第 i 行第 j 列的皇后 ； } } 算法求精 void Queen( int i ) { for ( int j = 0。 j n。 j++ ) { if ( !col[j] amp。amp。 !md[n+ij1] amp。amp。 !sd[i+j] ) { /*第 i 行第 j 列沒有攻擊 */ col[j] = md[n+ij1] = sd[i+j] = 1。 q[i] = j。 /*在 第 i 行第 j 列安放皇后 */ if ( i == n1 ) { /*輸出一個布局 */ for ( j = 0。 j n。 j++ ) cout q[j] ‘,’。 cout endl。 } else Queen ( i+1 )。 } col[j] = md[n+ij1] = sd[i+j] = 0。 q[i] = 0。 /*撤消 第 i 行第 j 列的皇后 */ } } 廣義表 (General Lists ) ? 廣義表的概念 n ( ? 0 )個表元素組成的有 限序列 ，記作 LS = (a0, a1, a2, …, an1) LS是表名， ai 是表元素，它可以是表 (稱 為 子表 )，可以是數(shù)據(jù)元素 (稱為 原子 )。 ? n為表的長度。 n = 0 的廣義表為空表。 ? n 0時， 表的 第一個表元素 稱為廣義表 的 表頭 (head)，除此之外， 其它表元素組 成的表 稱為廣義表的 表尾 (tail)。 廣義表的特性 ? 有次序性 ? 有長度 A = ( ) B = ( 6, 2 ) C = ( ‘a(chǎn)’, ( 5, 3, ‘x’ ) ) D = ( B, C, A ) E = ( B, D ) F = ( 4, F ) ? 有深度 ? 可共享 ? 可遞歸 廣義表的表示 只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示 表中套表情形下的廣義表鏈表表示 5 2 3 2 4 3 6 10 3 9 14 ? ? ? ? ? list2 5 list1 ? 12 47 ‘a(chǎn)’ ‘s’ 廣義表結(jié)點定義 ? 結(jié)點類型 utype = 0, 表頭； = 1, 整型原子；= 2, 字符型原子； = 3, 子表 ? 值 value utype=0時 , 存放引用計數(shù) (ref)；utype=1時 , 存放整數(shù)值 (intinfo)； utype=2時 , 存放字符型數(shù)據(jù) (charinfo)； utype=3時 , 存放指向子表表頭的指針 (hlink) ? 尾指針 tlink utype=0時 , 指向該表第一個結(jié)點； utype?0時 , 指向同一層下一個結(jié)點 utype value tlink 廣義表的存儲表示 E B F 0 1 1 4 3 0 1 3 3 D ? ? 0 1 1 5 1 3 2 ‘x’ ? 0 1 2 ‘a(chǎn)’ 3 ? C ? 0 1 3 3 3 0 1 1 6 D B B C A 1 2 ? 0 1 A ? 廣義表的類定義 class GenList。 //GenList類的前視聲明 class GenListNode { //廣義表結(jié)點類的前視聲明 struct Items { //僅有結(jié)點信息的項 friend class GenlistNode。 friend class Genlist。 int utype。 //＝ 0 / 1 / 2 / 3 union { //聯(lián)合 int ref。 //utype=0, 存放引用計數(shù) int intinfo。 //utype=1, 存放整數(shù)值 char charinfo。 //utype =2, 存放字符 GenListNode *hlink。 //utype =3, 存放指向子表的指針 } } class GenListNode { //
公司管理相關(guān)推薦
鄂ICP備17016276號-1