【正文】 data。 struct node *next。//定義結(jié)點指針 }ListNode。 typedef ListNode *Linklist。//自定義鏈表類型 ListNode *q,*p。 Linklist head=(Linklist)malloc(sizeof(ListNode))。//申請頭結(jié)點 /*******按將猴子數(shù)量編號并存入 鏈表 *******/ Linklist Create(int n) { int i。 p=head。 pnext=NULL。 for(i=1。i=n。i++) {//將猴子順序編號 q=(ListNode *)malloc(sizeof(ListNode))。 qdata=i。 pnext=q。 p=q。 pnext=NULL。 } return head。//返回鏈表頭指針 } /****************打印鏈表 ***************/ void printlist(Linklist head) { p=headnext。 while(p) {//打印鏈表直至鏈表結(jié)尾 coutpdata 。 p=pnext。 } } /**************刪除被選到的猴子 *****************/ void Delete(ListNode *b,ListNode *pb) /*pb為刪除結(jié)點的前驅(qū) */ { pbnext=bnext。 free(b)。 25 } /**************猴子選大王（數(shù) n個） **************/ int King(Linklist head,int n,int i) { int j,k。 ListNode *pp,*t。 /*刪除節(jié)點前驅(qū) */ p=head。 if(i==1) return i。 while(i!=1) { for(j=0。jn。j++) {//數(shù)到第 n個猴子 pp=p。 p=pnext。 if(!p) p=headnext。 } if(!pnext) t=head。//當刪除的結(jié)點為最后一個結(jié)點時， t指向頭結(jié)點 else t=pp。 Delete(p,pp)。 p=t。 i。 } k=ppdata。//將最后一只猴子的編號賦值給 k return k。//返回最后一只猴子編號 } void main() { int i,c,k,flag=0。 cout請輸入猴子數(shù)量 endl。 cini。 cout將猴子順序編號 endl。 printlist(Create(i))。//調(diào)用將猴子順序編號的函數(shù) coutendl編號結(jié)束 endl。 while(!flag) { cout第幾個猴子離開？ endl。 cinc。 if(ci) cout輸入數(shù)量大于猴子數(shù)量，請重新輸入 endl。 if(ci||c==i) flag=1。 } k=King(head,c,i)。//調(diào)用猴子先大王函數(shù) cout大王編號為 kendl。 26 } 四、 二叉樹 運算 2 1. 題目要求 設計一個算法，把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表。二叉樹 用二叉 鏈存儲，鏈接時用葉子結(jié)點的 rchild 域存放指針。 2. 應用程序功能 程序運行結(jié)果如下： 3. 輸入數(shù)據(jù)類型、格式和內(nèi)容限制 輸入數(shù)據(jù)為整型，切勿輸入整型以外數(shù)據(jù)類型，否則程序?qū)⑦M入循環(huán)。 4. 主要算法模塊描述 流程圖： 27 28 5. 源程序代碼 /*創(chuàng)建二叉樹時以輸入 9999 為結(jié)束標志 */ include include include iostream using namespace std。 define max 50 typedef struct liuyu { int data。 struct liuyu *lchild,*rchild。//定義結(jié)點的左、右指針 }test。 liuyu *root,*p,*q[max],*head,*first。 int sum=0。 int m=sizeof(test)。 /************生成二叉排序數(shù) ************/ void insert_data(int x) { liuyu *p,*q,*s。 s=(test*)malloc(m)。 sdata=x。 slchild=NULL。 srchild=NULL。 if(!root) { root=s。 } p=root。 29 while(p) /*如何接入二叉排序樹的適當位置 */ { q=p。 if(pdata==x) { printf(data already exist! \n)。 return。 } else if(xpdata) p=plchild。 else p=prchild。 } if(xqdata) qlchild=s。 else qrchild=s。 } /*=============將二叉樹葉子結(jié)點利用指針 rchild 生成單鏈表=====================*/ void PreOrderTraverse(liuyu *root) { liuyu *n。 n=root。 if(!n) return。 if(nlchild==NULL amp。amp。 nrchild==NULL) {//判斷葉子結(jié)點并利用指針 rchild 生成單鏈表 headrchild=n。 head=n。 30 return。 } if(nlchild) PreOrderTraverse(nlchild)。 if(nrchild) PreOrderTraverse(nrchild)。 return。 } /************查找二叉樹第最左邊第 一個葉子結(jié)點 ********/ liuyu FinFLea(liuyu *root) { liuyu *n。 n=root。 if(nlchild==NULL amp。amp。 nrchild==NULL) {//查找最左邊第一個葉子結(jié)點，在鏈表輸出時調(diào)用 first=n。 } if(nlchild) {n=nlchild。FinFLea(n)。} else if(nrchild) {n=nrchild。FinFLea(n)。} return *first。 } /******************遞歸輸出二叉樹 *****************/ void printtree(liuyu *root) { if(root) coutrootdata 。 if(rootlchild) printtree(rootlchild)。 if(rootrchild) printtree(rootrchild)。 } /**********按從左到右的順序打印葉子結(jié)點 *******/ 31 void printlist(liuyu *lea) { liuyu *n。 n=lea。 while(n) {//輸出鏈表 coutndata 。 n=nrchild。 } coutendl。 return。 } void main() /*先生成二叉排序樹 */ { int i,x。 i=1。 root=NULL。 /*千萬別忘了賦初值給 root!*/ do { printf(please input data%d:,i)。 i++。 scanf(%d,amp。x)。 /*從鍵盤采集數(shù)據(jù)，以 9999 表示輸入結(jié)束 */ if(x==9999){ printf(\nNow output data value:\n)。 } else 32 insert_data(x)。 /*調(diào)用插入數(shù)據(jù)元素的函數(shù) */ } while(x!=9999)。 cout***************創(chuàng)建二叉樹成功 ************endl。 coutendl。 printtree(root)。//打印二叉樹 coutendlendl。 FinFLea(root)。//調(diào)用查找最左邊的葉子結(jié)點函數(shù) head=(liuyu *)malloc(sizeof(liuyu))。//申請頭結(jié)點 PreOrderTraverse(root)。//調(diào)用將二叉樹按從左到右鏈成單鏈表函數(shù) cout葉子結(jié)點按從左到右鏈成單鏈表成功 endl。 printlist(first)。//打印二叉樹葉子結(jié)點鏈表 }