【文章內(nèi)容簡介】 L。 } } //排序函數(shù) void Sort(Linklist L) { Linklist p。 p=L。 int i。 printf(請選擇通訊錄的幾種排序方式： \n)。 printf(1:按姓名排序 。2:按電話號碼排序 。3:按地址排序 。其他整數(shù) :退出 \n)。 scanf(%d,amp。i)。 switch(i) { case 1:SortName(p)。break。 11 case 2:SortTel(p)。break。 case 3:SortAddress(p)。break。 default:break。 } } //主函數(shù) void main() { int i,j,t。 Linklist L。 while(1){ printf(通訊錄功能如下： \n1．通訊錄鏈表的建立； \n2．通訊者結(jié)點的插入； \n3．通訊者結(jié)點的查詢； \n4．通訊者結(jié)點的刪除； \n5．通訊錄鏈表的輸出； \n0．退出管理系統(tǒng) :\n請選擇 05\n)。 scanf(%d,amp。t)。 if((t=0)||(t5)) break。 switch(t){ case 1:{L=CreatList()。Sort(L)。break。} case 2:{ printf(在第 i個聯(lián)系人前插入，請輸入 i值 \n)。 scanf(%d,amp。i)。 ListInsert(L,i)。break。} case 3:ListFind(L)。break。 case 4:{ printf(刪除第 j 個聯(lián)系人的信息，請輸入 j 值 \n)。 scanf(%d,amp。j)。 ListDelete(L,j)。break。} case 5:OutPut(L)。break。 } } printf(開始回收內(nèi)存！ )。 Release(L)。 printf(回收內(nèi)存結(jié)束 ！ )。 } 12 2 八皇后問題 問題簡介 利用棧結(jié)構(gòu)實現(xiàn)八皇后問題。 八皇后問題 19 世紀著名的數(shù)學(xué)家高斯于 1850年提出的。他的問題是：在 8*8的棋盤上放置 8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列、同一斜線上。請設(shè)計算法打印所有可能的擺放方法。 提示： 可以使用遞歸或非遞歸兩種方法實現(xiàn) 實現(xiàn)一個關(guān)鍵算法：判斷任意兩個皇后是否在同一行、同一列和同一斜線上 存儲結(jié)構(gòu) 存儲結(jié)構(gòu)：棧（遞歸） 關(guān)鍵算法分析 【設(shè)計思想】 由于八皇后問題，可以分解成算法相同的子問題，所以使用遞歸的方法 【偽代碼】 輸入皇后個數(shù) n k=1 判斷 k是否大于 n 是：打印一組可能 13 否：循環(huán)行位置 1~n 判斷該位置是否符合要求，若符合記錄 q[k]的坐標(biāo) y 值 k+1 重復(fù) 3 源代碼 include iostream using namespace std。 const int StackSize=8。 //定義棧的最大高度 int ans=0。 //初始化擺放方案計數(shù)器 template class T class SeqStack //定義順序棧模板類 { public: SeqStack(){top=1。} //構(gòu)造函數(shù)，初始化空棧 void Push(T x)。 //入棧 void Pop()。 //出棧 void PlaceQueen(int row)。 //擺放 8 皇后的遞歸函數(shù) bool Judgement()。 //判斷是否在同一行同一列同一斜線 void Output()。 //打印棋盤 bool Empty(){if(top==1) return true。else return false。}。 //判別棧是否為空 private: T data[StackSize]。 //定義數(shù)組 int top。 //棧頂指針 }。 template class T 14 void SeqStackT::Push(T x) //入棧操作 { if(top=StackSize1) throw error。 top++。 //棧頂指針上移 data[top]=x。 } template class T void SeqStackT::Pop() //出棧操作 { if(Empty()) throw error。 top。 //棧頂指針下移 } template class T void SeqStackT::PlaceQueen(int row) //在棧頂放置符合條件的值的操作 ,即擺放皇后 { for (int col=0。colStackSize。col++) //窮盡 0~7，即窮盡列 { Push(col)。 if (Judgement()) //判斷擺放皇后的位置是否安全 { if (rowStackSize1) //若還沒有放到第八個皇后，則進行下一個皇后的放置 PlaceQueen(row+1)。 else { ans++。 //解數(shù)加 1 Output()。 //打印成功的棋盤 } 15 } Pop()。 //若不符合條件則出棧 } } template class T bool SeqStackT::Judgement() { for(int i=0。itop。i++) //依次檢查前面各行的皇后位置 if(data[top]==data[i]||(abs(data[top]data[i]))==(topi)) //判斷是否在同一列同一斜線 return false。 return true。 } template class T void SeqStackT::Output() //將棧的數(shù)組形式打印成棋盤形式 { coutNO.ans:endl。 for(int i=0。iStackSize。i++) { for(int j=0。jdata[i]。j++) cout 。