数据结构课程设计参考答案a组

职教高考

二叉树分层遍历/

#include<； stdio.h>； #include<； stdlib.h>； #include<； conio.h>； #include<； string.h>；

typedef struct node{ char data；

struct node *lchild； struct node *rchild； } Node； //递归构造二叉树

Node *CreateBT () { Node *t； char x； scanf("%c "，&； x )； flush(stdin；

if(x=='# ' ) t=NULL； else {

t=new Node； t->； data=x；

printf((t ) t )是%c节点的左子节点)，t->； 请输入data )。

职教本科

返回t； //递归先遍历二叉树

voidpreorder(node*t ) if ) t )

printf (" <"，T->； data )； preorder(t->； lchild )； preorder(t->； rchild )； }

//递归遍历二叉树

voidinorder(node*t ) if ) t )

norder(t->； lchild )； printf (" <"，T->； data )； norder(t->； rchild )； }

//递归遍历二叉树

voidpostorder(node*t ) if ) t )

postorder(t->； lchild； postorder(t->； rchild )；

职中

//非递归先遍历二叉树

voidnorecursivepreorder(node*t ) { Node *St[TREEMAX]，*p； int top=-1； if(t！=NULL ) {

top；

St[top]=T； wile(top )-1 ) {p=ST[top]； top----；

printf("%c "，p->； data )； if(p ) >； rchild！=空(% 09%09top%2B%2B%3B%0A%09%09%09%09St%5Btop%5D%3Dp-%3Erchild%3B%09%09%09%7D%09%09%09if%28p-%3Elchild%21%3DNULL%29%09%09%09%7B%09%09%09%09top%2B%2B%3B%0A%09%09%09%09St%5Btop%5D%3Dp-%3Elchild%3B%09%09%09%7D%09%09%7D%0A%09%09printf%28%22%5Cn%22%29%3B%09%7D%7D%0A//%20%E9%9D%9E%E9%80%92%E5%BD%92%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%0Avoid%20noRecursiveInorder%28Node%20%2AT%29%7B%09Node%20%2ASt%5BTREEMAX%5D%2C%2Ap%3B%09int%20top%3D-1%3B%09if%28T%21%3DNULL%29%09%7B%0A%09%09p%3DT%3B%0A%09%09while%28top%3E-1%7C%7Cp%21%3DNULL%29%09%09%7B%09%09%09while%28p%21%3DNULL%29%09%09%09%7B%09%09%09%09top%2B%2B%3B%0A%09%09%09%09St%5Btop%5D%3Dp%3B%09%09%09%09p%3Dp-%3Elchild%3B%09%09%09%7D%09%09%09if%28top%3E-1%29%09%09%09%7B%0A%09%09%09%09p%3DSt%5Btop%5D%3B%09%09%09%09top--%3B%0A%09%09%09%09printf%28%22%25c%22%2Cp-%3Edata%29%3B%09%09%09%09p%3Dp-%3Erchild%3B%09%09%09%7D%09%09%7D%0A%09%09printf%28%22%5Cn%22%29%3B%09%7D%7D%0A//%20%E9%9D%9E%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%0Avoid%20noRecursivePostorder%28Node%20%2AT%29%7B%0A%09Node%20%2ASt%5BTREEMAX%5D%2C%2Ap%3B%09int%20flag%2Ctop%3D-1%3B%09if%28T%21%3DNULL%29%09%7B%09%09do%09%09%7B%0A%09%09%09while%28T%21%3DNULL%29%09%09%09%7B%09%09%09%09top%2B%2B%3B%0A%09%09%09%09St%5Btop%5D%3DT%3B%09%09%09%09T%3DT-%3Elchild%3B%09%09%09%7D%09%09%09p%3DNULL%3B%09%09%09flag%3D1%3B%0A%09%09%09while%28top%21%3D-1%26%26flag%29%09%09%09%7B%09%09%09%09T%3DSt%5Btop%5D%3B%0A%09%09%09%09if%28T-%3Erchild%3D%3Dp%29%09%09%09%09%7B%0A%09%09%09%09%09printf%28%22%25c%22%2CT-%3Edata%29%3B%09%09%09%09%09top--%3B%09%09%09%09%09p%3DT%3B%09%09%09%09%7D%0A%09%09%09%09else%09%09%09%09%7B%0A%09%09%09%09%09T%3DT-%3Erchild%3B%09%09%09%09%09flag%3D0%3B%09%09%09%09%7D%09%09%09%7D%0A%09%09%7Dwhile%28top%21%3D-1%29%3B%09%09printf%28%22%5Cn%22%29%3B%09%7D%7D%0A//%20%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E7%94%A8queue%E6%95%B0%E7%BB%84%E5%85%85%E5%BD%93%E9%A1%BA%E5%BA%8F%E9%98%9F%E5%88%97void%20LevelOrder%28Node%20%2AT%29%7B%09Node%20%2Aqueue%5BTREEMAX%5D%2C%20%2Ap%3B%09int%20pre%3D-1%2C%20rear%3D-1%3B%09//%20%E6%A0%91%E6%A0%B9%E7%BB%93%E7%82%B9%E5%85%88%E8%BF%9B%E9%98%9F%0A%09queue%5B%2B%2Bpre%5D%3DT%3B%0A%09//%20%E5%BD%93%E9%98%9F%E5%88%97%E4%B8%8D%E4%B8%BA%E7%A9%BA%E6%97%B6%EF%BC%8C%E5%87%BA%E9%98%9F%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9%E7%9A%84%E5%90%8C%E6%97%B6%E5%B0%86%E5%85%B6%E5%B7%A6%E5%8F%B3%E5%AD%A9%E5%AD%90%E8%BF%9B%E9%98%9F%0A%09while%28%28pre-rear%2BTREEMAX%29%25TREEMAX%21%3D0%29%09%09%09%7B%0A%09%09p%3Dqueue%5B%2B%2Brear%5D%3B%09%09//%20%E5%87%BA%E9%98%9F%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9%E5%B9%B6%E8%BE%93%E5%87%BA%09%09printf%28%22%253c%22%2C%20p-%3Edata%29%3B%09%09%09if%28p-%3Elchild%21%3DNULL%29%09%09//%20%E5%B7%A6%E5%AD%A9%E5%AD%90%E5%AD%98%E5%9C%A8%E5%88%99%E8%BF%9B%E9%98%9F%09%09%09queue%5B%2B%2Bpre%5D%3Dp-%3Elchild%3B%09%09if%28p-%3Erchild%21%3DNULL%29%09%09//%20%E5%8F%B3%E5%AD%A9%E5%AD%90%E5%AD%98%E5%9C%A8%E5%88%99%E8%BF%9B%E9%98%9F%09%09%09queue%5B%2B%2Bpre%5D%3Dp-%3Erchild%3B%09%7D%7D%0Avoid%20list%28%29%7B%09printf%28%22%5Cn%22%29%3B%0A%09printf%28%22%5Cn%5Ct%5Ct%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E4%BA%8C%E5%8F%89%E9%93%BE%E8%A1%A8%22%29%3B%0A%09printf%28%22%5Cn%5Ct%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%201.%E5%BB%BA%E7%AB%8B%E4%BA%8C%E5%8F%89%E6%A0%91%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%202.%E9%80%92%E5%BD%92%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%203.%E9%80%92%E5%BD%92%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%204.%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%205.%E9%9D%9E%E9%80%92%E5%BD%92%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%206.%E9%9D%9E%E9%80%92%E5%BD%92%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%207.%E9%9D%9E%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%208.%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%209.%E6%B8%85%E5%B1%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%200.%E9%80%80%E5%87%BA%E7%A8%8B%E5%BA%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%B7%E8%BE%93%E5%85%A5%E8%8F%9C%E5%8D%95%E9%A1%B9%EF%BC%9A%22%29%3B%7D%0Avoid%20main%28%29%7B%0A%09Node%20%2AT%3DNULL%3B%09char%20a%2Cb%3B%09b%3D%27m%27%3B%09while%28b%3D%3D%27m%27%7C%7Cb%3D%3D%27M%27%29%09%7B%09%09list%28%29%3B%0A%09%09scanf%28%22%25c%22%2C%20%26a%29%3B%09%09fflush%28stdin%29%3B%09%09switch%28a%29%09%09%7B%0A%09%09case%271%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%B7%E6%8C%89%E5%85%88%E5%BA%8F%E5%BA%8F%E5%88%97%E8%BE%93%E5%85%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%93%E7%82%B9%EF%BC%88%E8%BE%93%E5%85%A5%23%E8%A1%A8%E7%A4%BA%E7%BB%93%E7%82%B9%E4%B8%BA%E7%A9%BA%EF%BC%89%EF%BC%9A%5Cn%22%29%3B%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%B7%E8%BE%93%E5%85%A5%E6%A0%B9%E7%BB%93%E7%82%B9%EF%BC%9A%22%29%3B%09%09%09T%3DCreateBT%28%29%3B%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E4%BA%8C%E5%8F%89%E6%A0%91%E6%88%90%E5%8A%9F%E5%BB%BA%E7%AB%8B%5E-%5E%5Cn%22%29%3B%09%09%09break%3B%09%09case%272%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%80%92%E5%BD%92%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09Preorder%28T%29%3B%09%09%09break%3B%09%09case%273%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%80%92%E5%BD%92%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09Inorder%28T%29%3B%09%09%09break%3B%09%09case%274%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09Postorder%28T%29%3B%09%09%09break%3B%09%09case%275%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%9D%9E%E9%80%92%E5%BD%92%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09noRecursivePreorder%28T%29%3B%09%09%09break%3B%09%09case%276%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%9D%9E%E9%80%92%E5%BD%92%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09noRecursiveInorder%28T%29%3B%09%09%09break%3B%09%09case%277%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E9%9D%9E%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09noRecursivePostorder%28T%29%3B%09%09%09break%3B%09%09case%278%27%3A%0A%09%09%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E4%B8%BA%EF%BC%9A%22%29%3B%09%09%09LevelOrder%28T%29%3B%09%09%09break%3B%09%09case%279%27%3A%0A%09%09%09system%28%22cls%22%29%3B%09%09%09break%3B%0A%09%09case%270%27%3A%09%09%09b%3D%27n%27%3B%09%09%09break%3B%09%09default%3A%09%09%09printf%28%22%5Cn%5Ct%5Ct%2A%2A%2A%E5%AF%B9%E4%B8%8D%E8%B5%B7%EF%BC%8C%E8%BE%93%E5%85%A5%E6%9C%89%E8%AF%AF%EF%BC%81%2A%2A%2A%22%29%3B%09%09%7D%09%7D%7D%0A/%2A%20%0A%E5%A4%9A%E9%A1%B9%E5%BC%8F%E8%BF%90%E7%AE%97%E3%80%90%E9%93%BE%E5%BC%8F%E7%BB%93%E6%9E%84%E3%80%91%2A/%0A%23include%20%22stdio.h%22%23include%20%22stdlib.h%22typedef%20struct%20_node%7B%20%20%0A%09float%20%20coe%3B%20%20%09int%20%20%20index%3B%09%0A%09struct%20%20_node%20%20%2Anext%3B%20%7DNode%2C%20%2ANodePtr%3B%0A//%20%E6%95%B4%E7%90%86%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%EF%BC%8C%E5%B0%86%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E7%BB%93%E7%82%B9%E6%A0%B9%E6%8D%AE%E5%90%84%E9%A1%B9%E6%8C%87%E6%95%B0%E8%BF%9B%E8%A1%8C%E5%8D%87%E5%BA%8F%E6%8E%92%E5%88%97void%20sortPoly%28NodePtr%20list%29%7B%09%09NodePtr%20p%3Dlist-%3Enext%2C%20q%3Dlist%2C%20r%2C%20ptr%3B%0A%09//%20%E8%AE%A9p%E6%8C%87%E5%90%91%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%BA%8C%E4%B8%AA%E6%95%B0%E6%8D%AE%E7%BB%93%E7%82%B9%EF%BC%8C%09//%20p%E4%B8%BA%E7%A9%BA%E5%88%99%E8%AF%B4%E6%98%8E%E9%93%BE%E8%A1%A8%E4%B8%BA%E7%A9%BA%EF%BC%8C%E4%B8%8D%E7%94%A8%E6%95%B4%E7%90%86%E4%BA%86%E3%80%82%09if%28p%29%09%09p%3Dp-%3Enext%3B%09else%20%0A%09%09return%3B%0A%09//%20%E5%85%88%E4%BB%8E%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E6%95%B0%E6%8D%AE%E7%BB%93%E7%82%B9%E5%90%8E%E6%96%AD%E5%BC%80%E9%93%BE%E8%A1%A8%09ptr%3Dq-%3Enext%3B%09ptr-%3Enext%3DNULL%3B%0A%09//%20%E5%86%8D%E5%B0%86%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%BA%8C%E4%B8%AA%E7%9B%B4%E8%87%B3%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E6%95%B0%E6%8D%AE%E7%BB%93%E7%82%B9%E4%BE%9D%E6%AC%A1%E6%8F%92%E5%85%A5%E9%93%BE%E8%A1%A8%09while%28p%29%09%7B%09%0A%09%09q%3Dlist%3B%0A%09%09ptr%3Dq-%3Enext%3B%0A%09%09while%28ptr-%3Eindex%20%3C%20p-%3Eindex%29%09%09%7B%09%09%09q%3Dptr%3B%0A%09%09%09ptr%3Dptr-%3Enext%3B%0A%09%09%09if%28ptr%3D%3DNULL%29%09%09%09%09break%3B%09%09%7D%0A%09%09if%28ptr%3D%3DNULL%29%09%09%7B%09%09%09q-%3Enext%3Dp%3B%09%09%09ptr%3Dp%3B%09%09%09p%3Dp-%3Enext%3B%0A%09%09%09ptr-%3Enext%3DNULL%3B%09%09%7D%0A%09%09else%20if%28ptr-%3Eindex%20%3D%3D%20p-%3Eindex%29%09%09%7B%09%09%09ptr-%3Ecoe%20%2B%3D%20p-%3Ecoe%3B%09%09%09r%3Dp-%3Enext%3B%09%09%09free%28p%29%3B%09%09%09p%3Dr%3B%0A%09%09%7D%0A%09%09else%20if%28ptr-%3Eindex%20%3E%20p-%3Eindex%29%09%09%7B%0A%09%09%09r%3Dp-%3Enext%3B%09%09%09p-%3Enext%3Dptr%3B%09%09%09q-%3Enext%3Dp%3B%09%09%09p%3Dr%3B%09%09%7D%09%7D%0A%7D%0A/%2A%20%E5%88%9B%E5%BB%BA%E4%B8%80%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%EF%BC%8C%E8%BF%94%E5%9B%9E%E5%88%9B%E5%BB%BA%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%B4%E6%8C%87%E9%92%88%20%2A/NodePtr%20createPoly%28%29%7B%20%20%20%09int%20i%3D1%2C%20index%3B%09float%20coe%3B%0A%09NodePtr%20resultPtr%2C%20q%3B%09%09//%20%E5%BC%80%E8%BE%9F%E5%A4%B4%E7%BB%93%E7%82%B9%E7%A9%BA%E9%97%B4%0A%09resultPtr%20%3D%20%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09resultPtr-%3Enext%3DNULL%3B%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%AC%AC%25d%E9%A1%B9%E7%9A%84%E7%B3%BB%E6%95%B0%E5%92%8C%E6%8C%87%E6%95%B0%28%E8%BE%93%E5%85%A50%200%E6%97%B6%E7%BB%93%E6%9D%9F%29%EF%BC%9A%22%2C%20i%2B%2B%29%3B%09scanf%28%22%25f%25d%22%2C%20%26coe%2C%20%26index%29%3B%09while%281%29%09%7B%09%0A%09%09if%28index%20%26%26%20coe%3D%3D0%29%09%09%09printf%28%22%E7%B3%BB%E6%95%B0%E4%B8%8D%E8%83%BD%E4%B8%BA0%EF%BC%81%5Cn%22%29%3B%09%09else%20if%28index%3D%3D0%20%26%26%20coe%3D%3D0%29%09%09%09break%3B%09%09else%0A%09%09%7B%09//%20%E5%BC%80%E8%BE%9F%E6%96%B0%E7%BB%93%E7%82%B9%E7%A9%BA%E9%97%B4%0A%09%09%09q%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09q-%3Ecoe%3Dcoe%3B%09%09%09q-%3Eindex%3Dindex%3B%09%09%09q-%3Enext%3DNULL%3B%0A%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%0A%09%09%09q-%3Enext%3DresultPtr-%3Enext%3B%09%09%09%09resultPtr-%3Enext%3Dq%3B%09%09%09%09%09%09//%20%E8%BE%93%E5%85%A5%E4%B8%8B%E4%B8%80%E9%A1%B9%0A%09%09%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%AC%AC%25d%E9%A1%B9%E7%9A%84%E7%B3%BB%E6%95%B0%E5%92%8C%E6%8C%87%E6%95%B0%28%E8%BE%93%E5%85%A50%200%E6%97%B6%E7%BB%93%E6%9D%9F%29%EF%BC%9A%22%2C%20i%2B%2B%29%3B%09%09%09scanf%28%22%25f%25d%22%2C%20%26coe%2C%20%26index%29%3B%09%09%09%7D%09%7D%0A%09//%20%E5%B0%86%E8%BE%93%E5%85%A5%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%E6%95%B4%E7%90%86%E5%90%8E%E8%BF%94%E5%9B%9E%09sortPoly%28resultPtr%29%3B%09return%20resultPtr%3B%7D//%20%E5%88%A4%E6%96%AD%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E5%B7%B2%E8%BE%93%E5%85%A5%E6%88%96%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%0Aint%20isEmpty%28NodePtr%20list1%2C%20NodePtr%20list2%29%7B%09if%28list1%3D%3DNULL%29%09%09return%201%3B%0A%09else%20if%28list2%3D%3DNULL%29%09%09return%202%3B%09else%20if%28list1-%3Enext%3D%3DNULL%29%09%09return%20-1%3B%09else%20if%28list2-%3Enext%3D%3DNULL%29%09%09return%20-2%3B%09else%0A%09%09return%200%3B%7D//%20%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E5%8A%A0%0ANodePtr%20addPoly%28NodePtr%20list1%2C%20NodePtr%20list2%29%7B%09%09NodePtr%20resultPtr%2C%20p%3Dlist1-%3Enext%2C%20q%3Dlist2-%3Enext%2C%20r%3B%09%09if%28isEmpty%28list1%2C%20list2%29%3D%3D1%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L1%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%951%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09else%20if%28isEmpty%28list1%2C%20list2%29%3D%3D2%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L2%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%952%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09//%20%E5%88%9B%E5%BB%BA%E7%BB%93%E6%9E%9C%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E5%A4%B4%E7%BB%93%E7%82%B9%0A%09resultPtr%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09resultPtr-%3Enext%3DNULL%3B%09while%28p%21%3DNULL%20%26%26%20q%21%3DNULL%29%09%7B%09%0A%09%09if%28p-%3Eindex%20%3E%20q-%3Eindex%29%09%09%7B%09%09%09//%20%E5%88%9B%E5%BB%BA%E6%96%B0%E7%BB%93%E7%82%B9%0A%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09r-%3Ecoe%3Dq-%3Ecoe%3B%09%09%09r-%3Eindex%3Dq-%3Eindex%3B%09%09%09r-%3Enext%3DNULL%3B%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09q%3Dq-%3Enext%3B%09%09%7D%0A%09%09else%20if%28p-%3Eindex%20%3C%20q-%3Eindex%29%09%09%7B%0A%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09r-%3Ecoe%3Dp-%3Ecoe%3B%09%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09%09r-%3Enext%3DNULL%3B%09%09%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09p%3Dp-%3Enext%3B%09%09%7D%0A%09%09else%09%09%7B%09%0A%09%09%09//%20%E5%AF%B9%E5%BA%94%E9%A1%B9%E7%9B%B8%E5%8A%A0%E7%B3%BB%E6%95%B0%E4%B8%8D%E4%B8%BA0%0A%09%09%09if%28p-%3Ecoe%2Bq-%3Ecoe%21%3D0%29%09%09%09%7B%09%09%09%09//%20%E5%88%9B%E5%BB%BA%E6%96%B0%E7%BB%93%E7%82%B9%0A%09%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09%09r-%3Ecoe%3Dp-%3Ecoe%2Bq-%3Ecoe%3B%09%09%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09%09%09r-%3Enext%3DNULL%3B%0A%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09%09%7D%09%09%09%09%0A%09%09%09p%3Dp-%3Enext%3B%09%09%09q%3Dq-%3Enext%3B%09%09%7D%09%7D%0A%09//%20%E5%A6%82%E6%9E%9C%E6%9F%90%E4%B8%AA%E9%93%BE%E8%A1%A8%E4%B8%AD%E5%B0%9A%E6%9C%89%E5%A4%9A%E4%BD%99%E7%BB%93%E7%82%B9%E5%B0%9A%E6%9C%AA%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%EF%BC%8C%09//%20%E5%88%99%E5%B0%86%E5%89%A9%E4%BD%99%E7%BB%93%E7%82%B9%E4%BE%9D%E6%AC%A1%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%09while%28p%21%3DNULL%29%20%09%7B%0A%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09r-%3Ecoe%3Dp-%3Ecoe%3B%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09r-%3Enext%3DNULL%3B%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09resultPtr-%3Enext%3Dr%3B%09%09p%3Dp-%3Enext%3B%09%7D%0A%09while%28q%21%3DNULL%29%20%09%7B%0A%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09r-%3Ecoe%3Dq-%3Ecoe%3B%09%09r-%3Eindex%3Dq-%3Eindex%3B%09%09r-%3Enext%3DNULL%3B%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09resultPtr-%3Enext%3Dr%3B%09%09q%3Dq-%3Enext%3B%09%7D%0A%09return%20resultPtr%3B%7D//%20%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E5%87%8F%0ANodePtr%20subPoly%28NodePtr%20list1%2C%20NodePtr%20list2%29%7B%09%09NodePtr%20resultPtr%2C%20p%3Dlist1-%3Enext%2C%20q%3Dlist2-%3Enext%2C%20r%3B%09%09if%28isEmpty%28list1%2C%20list2%29%3D%3D1%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L1%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%951%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09else%20if%28isEmpty%28list1%2C%20list2%29%3D%3D2%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L2%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%952%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09//%20%E5%88%9B%E5%BB%BA%E7%BB%93%E6%9E%9C%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E5%A4%B4%E7%BB%93%E7%82%B9%0A%09resultPtr%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09resultPtr-%3Enext%3DNULL%3B%09while%28p%21%3DNULL%20%26%26%20q%21%3DNULL%29%09%7B%09%0A%09%09if%28p-%3Eindex%20%3E%20q-%3Eindex%29%09%09%7B%09%09%09//%20%E5%88%9B%E5%BB%BA%E6%96%B0%E7%BB%93%E7%82%B9%0A%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09r-%3Ecoe%3D-1%2Aq-%3Ecoe%3B%09%09%09r-%3Eindex%3Dq-%3Eindex%3B%09%09%09r-%3Enext%3DNULL%3B%0A%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09q%3Dq-%3Enext%3B%09%09%7D%0A%09%09else%20if%28p-%3Eindex%20%3C%20q-%3Eindex%29%09%09%7B%0A%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09r-%3Ecoe%3Dp-%3Ecoe%3B%09%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09%09r-%3Enext%3DNULL%3B%09%09%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09p%3Dp-%3Enext%3B%09%09%7D%0A%09%09else%09%09%7B%09%0A%09%09%09//%20%E5%AF%B9%E5%BA%94%E9%A1%B9%E7%9B%B8%E5%87%8F%E7%B3%BB%E6%95%B0%E4%B8%8D%E4%B8%BA0%0A%09%09%09if%28p-%3Ecoe-q-%3Ecoe%21%3D0%29%09%09%09%7B%09%09%09%09//%20%E5%88%9B%E5%BB%BA%E6%96%B0%E7%BB%93%E7%82%B9%0A%09%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09%09r-%3Ecoe%3Dp-%3Ecoe-q-%3Ecoe%3B%09%09%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09%09%09r-%3Enext%3DNULL%3B%0A%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09%09%7D%09%09%09%09%0A%09%09%09p%3Dp-%3Enext%3B%09%09%09q%3Dq-%3Enext%3B%09%09%7D%09%7D%0A%09//%20%E5%A6%82%E6%9E%9C%E6%9F%90%E4%B8%AA%E9%93%BE%E8%A1%A8%E4%B8%AD%E5%B0%9A%E6%9C%89%E5%A4%9A%E4%BD%99%E7%BB%93%E7%82%B9%E5%B0%9A%E6%9C%AA%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%EF%BC%8C%09//%20%E5%88%99%E5%B0%86%E5%89%A9%E4%BD%99%E7%BB%93%E7%82%B9%E4%BE%9D%E6%AC%A1%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%09while%28p%21%3DNULL%29%20%09%7B%0A%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09r-%3Ecoe%3Dp-%3Ecoe%3B%09%09r-%3Eindex%3Dp-%3Eindex%3B%09%09r-%3Enext%3DNULL%3B%09%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09resultPtr-%3Enext%3Dr%3B%09%09p%3Dp-%3Enext%3B%09%7D%0A%09while%28q%21%3DNULL%29%20%09%7B%0A%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09r-%3Ecoe%3D-1%2Aq-%3Ecoe%3B%09%09r-%3Eindex%3Dq-%3Eindex%3B%09%09r-%3Enext%3DNULL%3B%09%09%0A%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%0A%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09resultPtr-%3Enext%3Dr%3B%09%09q%3Dq-%3Enext%3B%09%7D%0A%09return%20resultPtr%3B%7D//%20%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E4%B9%98%0ANodePtr%20multiPoly%28NodePtr%20list1%2C%20NodePtr%20list2%29%7B%09%09NodePtr%20p%2C%20q%2C%20r%2C%20resultPtr%3B%09%0A%09if%28isEmpty%28list1%2C%20list2%29%3D%3D1%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L1%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%951%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09else%20if%28isEmpty%28list1%2C%20list2%29%3D%3D2%29%09%7B%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8L2%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E5%85%88%E9%80%89%E6%8B%A9%E8%8F%9C%E5%8D%952%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%EF%BC%81%5Cn%22%29%3B%09%09return%20NULL%3B%09%7D%0A%09else%20if%28isEmpty%28list1%2C%20list2%29%3D%3D-1%20%7C%7C%20isEmpty%28list1%2C%20list2%29%3D%3D-2%29%09%7B%09%09//%20%E7%BB%99%E7%9B%B8%E4%B9%98%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%E5%BC%80%E8%BE%9F%E5%A4%B4%E7%BB%93%E7%82%B9%0A%09%09resultPtr%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09resultPtr-%3Enext%3DNULL%3B%09%09return%20resultPtr%3B%09%7D%0A%09//%20%E7%BB%99%E7%9B%B8%E4%B9%98%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%E5%BC%80%E8%BE%9F%E5%A4%B4%E7%BB%93%E7%82%B9%0A%09resultPtr%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%20%20%20%20resultPtr-%3Enext%3DNULL%3B%20%20%20%20p%3Dlist1-%3Enext%3B%09q%3Dlist2-%3Enext%3B%20%20%20%20while%28p%29%09%7B%09%0A%09%09//%20%E5%8F%AA%E8%A6%81p%E4%B8%8D%E4%B8%BA%E7%A9%BA%EF%BC%8C%E5%88%99%E5%B0%86p%E6%8C%87%E5%90%91%E7%9A%84%E7%BB%93%E7%82%B9%E5%92%8C%E5%8F%A6%E4%B8%80%E9%93%BE%E8%A1%A8%E7%9A%84%E6%89%80%E6%9C%89%E7%BB%93%E7%82%B9%E7%9B%B8%E4%B9%98%EF%BC%8C%09%09//%20%E5%B9%B6%E5%B0%86%E7%9B%B8%E4%B9%98%E7%9A%84%E6%AF%8F%E4%B8%AA%E7%BB%93%E7%82%B9%E6%8F%92%E5%85%A5%E5%88%B0%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8resultPtr%E4%B8%AD%09%09while%28q%29%09%09%7B%0A%09%09%09//%20%E6%9E%84%E9%80%A0%E4%B8%80%E4%B8%AA%E6%96%B0%E7%BB%93%E7%82%B9%0A%09%09%09r%3D%28NodePtr%29malloc%28sizeof%28Node%29%29%3B%09%09%09r-%3Ecoe%3Dp-%3Ecoe%2Aq-%3Ecoe%3B%09%09%09r-%3Eindex%3Dp-%3Eindex%2Bq-%3Eindex%3B%09%09%09r-%3Enext%3DNULL%3B%0A%09%09%09//%20%E5%B0%86%E6%96%B0%E7%BB%93%E7%82%B9r%E4%BB%8E%E5%89%8D%E6%8F%92%E5%85%A5%E5%88%B0%E9%93%BE%E8%A1%A8resultPtr%09%09%09r-%3Enext%3DresultPtr-%3Enext%3B%09%09%09resultPtr-%3Enext%3Dr%3B%09%09%09q%3Dq-%3Enext%3B%09%09%7D%0A%09%09//%20%E5%8F%96list1%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9%E5%87%86%E5%A4%87%E5%86%8D%E6%AC%A1%E5%92%8Clist2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%BB%93%E7%82%B9%E7%9B%B8%E4%B9%98%09%09p%3Dp-%3Enext%3B%09%09q%3Dlist2-%3Enext%3B%20%20%20%20%7D%0A%09//%20%E6%9C%80%E5%90%8E%E5%AF%B9%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8resultPtr%E8%BF%9B%E8%A1%8C%E6%95%B4%E7%90%86%E5%90%8E%E8%BF%94%E5%9B%9E%09sortPoly%28resultPtr%29%3B%20%20%20%20return%20resultPtr%3B%7D%0A/%2A%20%E6%89%93%E5%8D%B0%E5%B8%A6%E5%A4%B4%E7%BB%93%E7%82%B9%E7%9A%84%E9%93%BE%E5%BC%8F%E7%BB%93%E6%9E%84%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8F%20%2A/%0Avoid%20printPoly%28NodePtr%20list%29%7B%09%09NodePtr%20p%3B%09%0A%09if%28list%3D%3DNULL%29%0A%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%93%BE%E8%A1%A8%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E8%AF%B7%E8%BE%93%E5%85%A5%E8%AF%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%EF%BC%81%5Cn%22%29%3B%09else%20if%28list-%3Enext%3D%3DNULL%29%09%09printf%28%22%E9%93%BE%E8%A1%A8%E4%B8%BA%E7%A9%BA%EF%BC%8C%E8%AF%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%E4%B8%BA0%EF%BC%81%5Cn%22%29%3B%09%09else%09%7B%09%0A%09%09p%3Dlist-%3Enext%3B%0A%09%09//%20%E8%BE%93%E5%85%A5%E7%AC%AC%E4%B8%80%E9%A1%B9%E6%97%B6%EF%BC%8C%E7%B3%BB%E6%95%B0%E6%97%A0%E8%AE%BA%E6%AD%A3%E8%B4%9F%EF%BC%8C%E5%89%8D%E9%9D%A2%E5%9D%87%E4%B8%8D%E6%B7%BB%E5%8A%A0%E7%AC%A6%E5%8F%B7%09%09if%28p%29%09%09%7B%0A%09%09%09if%28p-%3Eindex%21%3D0%20%26%26%20p-%3Eindex%21%3D1%29%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%8D%E4%B8%BA%E9%9B%B6%EF%BC%8C%E4%B9%9F%E4%B8%8D%E4%B8%BA1%09%09%09%09printf%28%22%25.2fx%5E%25d%22%2C%20p-%3Ecoe%2C%20p-%3Eindex%29%3B%09%09%09else%20if%28p-%3Eindex%21%3D0%29%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA1%09%09%09%09printf%28%22%25.2fx%22%2C%20p-%3Ecoe%29%3B%09%09%09else%09%09%09%09%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA%E9%9B%B6%09%09%09%09printf%28%22%25.2f%22%2C%20p-%3Ecoe%29%3B%09%09%09p%3Dp-%3Enext%3B%09%09%7D%0A%09%09while%28p%29%09%09%7B%09%0A%09%09%09if%28p-%3Ecoe%3E0%29%09%09%09%7B%0A%09%09%09%09if%28p-%3Eindex%21%3D0%20%26%26%20p-%3Eindex%21%3D1%29%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%8D%E4%B8%BA%E9%9B%B6%EF%BC%8C%E4%B9%9F%E4%B8%8D%E4%B8%BA1%09%09%09%09%09printf%28%22%2B%25.2fx%5E%25d%22%2C%20p-%3Ecoe%2C%20p-%3Eindex%29%3B%09%09%09%09else%20if%28p-%3Eindex%21%3D0%29%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA1%09%09%09%09%09printf%28%22%2B%25.2fx%22%2C%20p-%3Ecoe%29%3B%09%09%09%09else%09%09%09%09%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA%E9%9B%B6%09%09%09%09%09printf%28%22%2B%25.2f%22%2C%20p-%3Ecoe%29%3B%09%09%09%7D%09%09%09else%09%09%09%7B%0A%09%09%09%09if%28p-%3Eindex%21%3D0%20%26%26%20p-%3Eindex%21%3D1%29%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%8D%E4%B8%BA%E9%9B%B6%EF%BC%8C%E4%B9%9F%E4%B8%8D%E4%B8%BA1%09%09%09%09%09printf%28%22%25.2fx%5E%25d%22%2C%20p-%3Ecoe%2C%20p-%3Eindex%29%3B%09%09%09%09else%20if%28p-%3Eindex%21%3D0%29%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA1%09%09%09%09%09printf%28%22%25.2fx%22%2C%20p-%3Ecoe%29%3B%09%09%09%09else%09%09%09%09%09%09%09%09//%20%E6%8C%87%E6%95%B0%E4%B8%BA%E9%9B%B6%09%09%09%09%09printf%28%22%25.2f%22%2C%20p-%3Ecoe%29%3B%09%09%09%7D%09%09%09p%3Dp-%3Enext%3B%09%09%7D%0A%09%09printf%28%22%5Cn%22%29%3B%09%7D%7D%0A/%2A%20%E9%94%80%E6%AF%81%E5%B8%A6%E5%A4%B4%E7%BB%93%E7%82%B9%E7%9A%84%E9%93%BE%E5%BC%8F%E7%BB%93%E6%9E%84%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8F%20%2A/%0ANodePtr%20destoryPoly%28NodePtr%20list%29%7B%09%09NodePtr%20p%3Dlist%2C%20q%3B%09%0A%09while%28p%29%09%7B%09%0A%09%09q%3Dp-%3Enext%3B%09%09free%28p%29%3B%09%09p%3Dq%3B%09%7D%0A%09return%20NULL%3B%7D%0A/%2A%20%E8%8F%9C%E5%8D%95%E5%87%BD%E6%95%B0%20%2A/void%20menu%28%29%7B%0A%09printf%28%22%5Cn%5Cn%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%E4%B8%80%E5%85%83%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E7%AE%80%E5%8D%95%E8%BF%90%E7%AE%97%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%20%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%20%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%203%20%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%2BL2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%204%20%E5%A4%9A%E9%A1%B9%E5%BC%8FL1-L2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%205%20%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%C3%97L2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%206%20%E6%98%BE%E7%A4%BA%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%207%20%E6%98%BE%E7%A4%BA%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%208%20%E9%94%80%E6%AF%81%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%209%20%E9%94%80%E6%AF%81%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%200%20%E9%80%80%E5%87%BA%E7%A8%8B%E5%BA%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%5Cn%22%29%3B%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E4%BD%A0%E8%A6%81%E8%BF%9B%E8%A1%8C%E7%9A%84%E6%93%8D%E4%BD%9C%280-9%29%EF%BC%9A%22%29%3B%7D%0Avoid%20main%28%29%7B%09%09int%20select%3B%0A%09NodePtr%20L1%2C%20L2%2C%20L%3B%09while%281%29%09%7B%0A%09%09menu%28%29%3B%0A%09%09scanf%28%22%25d%22%2C%20%26select%29%3B%09%09switch%28select%29%09%09%7B%0A%09%09case%200%3A%09%09%09exit%280%29%3B%09%09case%201%3A%0A%09%09%09printf%28%22%E5%BC%80%E5%A7%8B%E8%BE%93%E5%85%A5%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%21%5Cn%22%29%3B%09%09%09L1%20%3D%20createPoly%28%29%3B%20%09%09%09break%3B%09%09case%202%3A%0A%09%09%09printf%28%22%E5%BC%80%E5%A7%8B%E8%BE%93%E5%85%A5%E7%AC%AC%E4%BA%8C%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%21%5Cn%22%29%3B%09%09%09L2%20%3D%20createPoly%28%29%3B%09%09%09break%3B%09%09case%203%3A%0A%09%09%09L%20%3D%20addPoly%28L1%2C%20L2%29%3B%09%09%09if%28L%21%3DNULL%29%09%09%09%7B%0A%09%09%09%09//%20%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%E8%BE%93%E5%87%BA%E5%90%8E%E5%8D%B3%E9%94%80%E6%AF%81%0A%09%09%09%09printf%28%22%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E5%8A%A0%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A6%82%E4%B8%8B%EF%BC%9A%5Cn%22%29%3B%09%09%09%09printPoly%28L%29%3B%09%09%09%09destoryPoly%28L%29%3B%09%09%09%7D%0A%09%09%09break%3B%09%09case%204%3A%0A%09%09%09L%20%3D%20subPoly%28L1%2C%20L2%29%3B%09%09%09if%28L%21%3DNULL%29%09%09%09%7B%0A%09%09%09%09//%20%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%E8%BE%93%E5%87%BA%E5%90%8E%E5%8D%B3%E9%94%80%E6%AF%81%0A%09%09%09%09printf%28%22%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E5%87%8F%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A6%82%E4%B8%8B%EF%BC%9A%5Cn%22%29%3B%09%09%09%09printPoly%28L%29%3B%09%09%09%09destoryPoly%28L%29%3B%09%09%09%7D%0A%09%09%09break%3B%09%09case%205%3A%0A%09%09%09L%20%3D%20multiPoly%28L1%2C%20L2%29%3B%09%09%09if%28L%21%3DNULL%29%09%09%09%7B%0A%09%09%09%09//%20%E7%BB%93%E6%9E%9C%E9%93%BE%E8%A1%A8%E8%BE%93%E5%87%BA%E5%90%8E%E5%8D%B3%E9%94%80%E6%AF%81%0A%09%09%09%09printf%28%22%E4%B8%A4%E4%B8%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9B%B8%E4%B9%98%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A6%82%E4%B8%8B%EF%BC%9A%5Cn%22%29%3B%09%09%09%09printPoly%28L%29%3B%09%09%09%09destoryPoly%28L%29%3B%09%09%09%7D%0A%09%09%09break%3B%09%09case%206%3A%0A%09%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%3D%22%29%3B%09%09%09printPoly%28L1%29%3B%09%09%09break%3B%09%09case%207%3A%0A%09%09%09printf%28%22%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%3D%22%29%3B%09%09%09printPoly%28L2%29%3B%09%09%09break%3B%09%09case%208%3A%0A%09%09%09printf%28%22%E6%AD%A3%E5%9C%A8%E5%9B%9E%E6%94%B6%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%E7%9A%84%E7%A9%BA%E9%97%B4......%5Cn%22%29%3B%09%09%09L1%3DdestoryPoly%28L1%29%3B%09%09%09printf%28%22%E6%88%90%E5%8A%9F%E9%94%80%E6%AF%81%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%EF%BC%8C%E6%82%A8%E5%8F%AF%E4%BB%A5%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL1%21%22%29%3B%09%09%09break%3B%09%09case%209%3A%0A%09%09%09printf%28%22%E6%AD%A3%E5%9C%A8%E5%9B%9E%E6%94%B6%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%E7%9A%84%E7%A9%BA%E9%97%B4......%5Cn%22%29%3B%09%09%09L2%3DdestoryPoly%28L2%29%3B%09%09%09printf%28%22%E6%88%90%E5%8A%9F%E9%94%80%E6%AF%81%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%EF%BC%8C%E6%82%A8%E5%8F%AF%E4%BB%A5%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8FL2%21%22%29%3B%09%09%09break%3B%09%09default%3A%0A%09%09%09printf%28%22%E8%8F%9C%E5%8D%95%E9%80%89%E6%8B%A9%E9%94%99%E8%AF%AF%EF%BC%8C%E8%AF%B7%E9%87%8D%E6%96%B0%E9%80%89%E6%8B%A9%EF%BC%81%5Cn%22%29%3B%09%09%7D%09%0A%09%7D%7D/%2A%20%0A%E6%B1%82%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E3%80%90%E5%9F%BA%E4%BA%8E%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E5%AD%98%E5%82%A8%E3%80%91%2A/%0A%23include%20%3Cstdio.h%3E%23include%20%3Cstdlib.h%3E%23include%20%3Cstring.h%3E%23include%3Cctype.h%3E%23define%20MAX_VERTEX_NUM%2020%20%23define%20INFINITY%200x7ffffffftypedef%20struct%7B%0A%09char%20%2Avexs%3B%09%09%09%09//%20%E9%A1%B6%E7%82%B9%E6%95%B0%E7%BB%84%E7%9A%84%E8%B5%B7%E5%A7%8B%E5%9C%B0%E5%9D%80%09int%20%2Aedges%3B%09%09%09%09//%20%E8%BE%B9%E7%9F%A9%E9%98%B5%E7%9A%84%E8%B5%B7%E5%A7%8B%E5%9C%B0%E5%9D%80%09int%20vexNum%2C%20edgeNum%3B%7DMGraph%3Btypedef%20struct%7B%20%0A%09char%20adjvex%3B%09%09%09//%20%E5%BD%93%E5%89%8D%E9%A1%B6%E7%82%B9%E7%9A%84%E9%82%BB%E6%8E%A5%E9%A1%B6%E7%82%B9%EF%BC%8C%E5%BD%93%E5%89%8D%E9%A1%B6%E7%82%B9%E5%88%B0%E8%AF%A5%E9%82%BB%E6%8E%A5%E9%A1%B6%E7%82%B9%E7%9A%84%E6%9D%83%E5%80%BC%E6%9C%80%E5%B0%8F%09int%20lowcost%3B%09%09%09//%20%E6%9C%80%E5%B0%8F%E6%9D%83%E5%80%BC%7DMinSide%3B%0A//%20%E6%9F%A5%E6%89%BE%E9%A1%B6%E7%82%B9v%E5%9C%A8%E9%A1%B6%E7%82%B9%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E4%B8%8B%E6%A0%87%0Aint%20locateVex%28MGraph%20G%2C%20char%20v%29%20%20%20%20%7B%20%09int%20i%3B%0A%09for%28i%3D0%3B%20i%3CG.vexNum%3B%20i%2B%2B%29%09%09if%28v%3D%3DG.vexs%5Bi%5D%29%09%09%09return%20i%3B%09return%20-1%3B%7D%0A//%20%E8%BE%93%E5%87%BA%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%0Avoid%20printAdjMatrix%28MGraph%20G%29%7B%09int%20i%2C%20j%3B%0A%09printf%28%22%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E7%9A%84%E5%80%BC%E4%B8%BA%3A%20%5Cn%22%29%3B%09for%28i%3D0%3B%20i%3CG.vexNum%3B%20i%2B%2B%29%09%7B%20%20%20%09%09for%28j%3D0%3B%20j%3CG.vexNum%3B%20j%2B%2B%29%09%09%7B%0A%09%09%09if%28G.edges%5Bi%2AG.vexNum%2Bj%5D%3D%3DINFINITY%29%09%09%09%09printf%28%22%E2%88%9E%5Ct%22%29%3B%09%09%09else%0A%09%09%09%09printf%28%22%25d%5Ct%22%2C%20G.edges%5Bi%2AG.vexNum%2Bj%5D%29%3B%20%20%20%20%20%20%09%09%7D%09%09printf%28%22%5Cn%22%29%3B%09%7D%0A%7D%0A//%20%E8%BE%93%E5%85%A5%E5%9B%BE%EF%BC%8C%E5%88%9B%E5%BB%BA%E7%9B%B8%E5%BA%94%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84%0Avoid%20createGraph%28MGraph%20%26G%29%7B%09int%20i%2C%20j%2C%20k%2C%20weight%3B%09char%20v1%2C%20v2%3B%0A%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E6%97%A0%E5%90%91%E7%BD%91G%E7%9A%84%E9%A1%B6%E7%82%B9%E6%95%B0%E5%92%8C%E8%BE%B9%E6%95%B0%EF%BC%88%E4%BB%A5%E7%A9%BA%E7%99%BD%E7%AC%A6%E6%88%96%E5%9B%9E%E8%BD%A6%E5%88%86%E9%9A%94%EF%BC%89%EF%BC%9A%22%29%3B%09scanf%28%22%25d%25d%22%2C%20%26G.vexNum%2C%20%26G.edgeNum%29%3B%09//%20%E6%A0%B9%E6%8D%AE%E9%A1%B6%E7%82%B9%E6%95%B0%E5%92%8C%E8%BE%B9%E6%95%B0%E6%9D%A5%E5%BC%80%E8%BE%9F%E7%A9%BA%E9%97%B4%0A%09G.vexs%20%3D%20%28char%20%2A%29malloc%28sizeof%28char%29%2AG.vexNum%29%3B%09G.edges%20%3D%20%28int%20%2A%29malloc%28sizeof%28int%29%2AG.vexNum%2AG.vexNum%29%3B%09//%20%E8%BE%93%E5%85%A5%E9%A1%B6%E7%82%B9%E6%A0%87%E8%AF%86%0A%09for%28i%3D0%3B%20i%3CG.vexNum%3B%20i%2B%2B%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09%7B%20%20%20%09%09fflush%28stdin%29%3B%0A%09%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%25d%E4%B8%AA%E9%A1%B6%E7%82%B9%E7%9A%84%E6%A0%87%E8%AF%86%EF%BC%88%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D%EF%BC%89%EF%BC%9A%22%2C%20i%2B1%29%3B%09%09%09%09scanf%28%22%25c%22%2C%20%26G.vexs%5Bi%5D%29%3B%09%09//%20%E5%A6%82%E6%9E%9C%E4%B8%8D%E6%98%AF%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D%EF%BC%8C%E5%88%99%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%E8%AF%A5%E9%A1%B6%E7%82%B9%E6%A0%87%E8%AF%86%09%09if%28%21isalpha%28G.vexs%5Bi%5D%29%29%09%09%09i--%3B%09%7D%0A%09//%20%E5%88%9D%E5%A7%8B%E5%8C%96%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%0A%09for%28i%3D0%3B%20i%3CG.vexNum%3B%20i%2B%2B%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09%09for%28j%3D0%3B%20j%3CG.vexNum%3B%20j%2B%2B%29%09%09%09G.edges%5Bi%2AG.vexNum%2Bj%5D%3DINFINITY%3B%20%0A%09%0A%09for%28k%3D0%3B%20k%3CG.edgeNum%3B%20k%2B%2B%29%09%7B%09%09fflush%28stdin%29%3B%0A%09%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E7%AC%AC%25d%E6%9D%A1%E8%BE%B9%E7%9A%84%E6%9D%83%E5%80%BC%EF%BC%88v1%2Cv2%2Cweight%EF%BC%89%3A%20%22%2C%20k%2B1%29%3B%09%09scanf%28%22%25c%2C%25c%2C%25d%22%2C%20%26v1%2C%20%26v2%2C%20%26weight%29%3B%20%09%09i%3DlocateVex%28G%2C%20v1%29%3B%09%09j%3DlocateVex%28G%2C%20v2%29%3B%0A%09%09if%28i%3E%3D0%20%26%26%20i%3CG.vexNum%20%26%26%20j%3E%3D0%20%26%26%20j%3CG.vexNum%29%0A%09%09%09G.edges%5Bi%2AG.vexNum%2Bj%5D%3DG.edges%5Bj%2AG.vexNum%2Bi%5D%3Dweight%3B%09%09//%20%E6%97%A0%E5%90%91%E5%9B%BE%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E4%B8%BA%E5%AF%B9%E7%A7%B0%E7%9F%A9%E9%98%B5%09%09else%09%09%7B%0A%09%09%09printf%28%22%E8%BE%93%E5%85%A5%E7%9A%84%E8%BE%B9%E4%B8%AD%E6%9C%89%E4%B8%8D%E5%AD%98%E5%9C%A8%E7%9A%84%E9%A1%B6%E7%82%B9%EF%BC%8C%E8%AF%B7%E6%A3%80%E6%9F%A5%E5%90%8E%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%21%5Cn%22%29%3B%09%09%09k--%3B%09%09%7D%09%7D%0A%7D%0A//%20%E4%BB%8E%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E4%B9%8B%E5%A4%96%E7%9A%84%E5%85%B6%E5%AE%83%E9%A1%B6%E7%82%B9%E4%B8%AD%E6%89%BE%E4%B8%80%E4%B8%AA%EF%BC%8C//%20%E4%BD%BF%E5%BE%97%E5%AE%83%E5%88%B0%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E7%9A%84%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E9%A1%B6%E7%82%B9%EF%BC%8C%E8%BF%94%E5%9B%9E%E5%85%B6%E4%B8%8B%E6%A0%87int%20getMinPathVexPoi%28MinSide%20closedge%5B%5D%2C%20MGraph%20G%29%7B%09int%20i%3D0%2C%20j%2C%20k%2C%20min%3B%0A%09//%20%E6%9D%83%E5%80%BC%E5%A6%82%E6%9E%9C%E4%B8%BA0%EF%BC%8C%E5%88%99%E7%9C%8B%E4%B8%8B%E4%B8%80%E6%9D%A1%0A%09while%28%21closedge%5Bi%5D.lowcost%29%09%09%20i%2B%2B%3B%0A%09//%20min%E7%9A%84%E5%88%9D%E5%A7%8B%E5%80%BC%E4%B8%BA%E7%AC%AC%E4%B8%80%E6%9D%A1%E6%9D%83%E5%80%BC%E4%B8%8D%E4%B8%BA0%E7%9A%84%E8%BE%B9%E7%9A%84%E6%9D%83%E5%80%BC%09min%3Dclosedge%5Bi%5D.lowcost%3B%20%09k%3Di%3B%0A%09for%28j%3Di%2B1%3B%20j%3CG.vexNum%3B%20j%2B%2B%29%0A%09%09if%28closedge%5Bj%5D.lowcost%3E0%20%26%26%20min%3Eclosedge%5Bj%5D.lowcost%29%20%09%09%7B%09%09%09min%3Dclosedge%5Bj%5D.lowcost%3B%09%09%09k%3Dj%3B%0A%09%09%7D%0A%09return%20k； }

用Prim算法求最小生成树

voidgetminspantreebyprim (mgraphg，char v ) { int i，j，k，weight，m； MinSide *closedge； closedge=(minside* ) malloc ) sizeof ) minside ) *G.vexNum； k=locatevex(g，v )；

//closedge[]存储尚未添加最小生成树的顶点。

//最小生成树整体的连接分量(最初只有顶点v )的最小权重)直接边不与v连接的为无限大) for ) ) j=0； j<； G.vexNum； j ) {

closed ge [ j ].low cost=g.edges [ k * g.vex num j ]； (//v到v的自己的权重标记为0

closedge[k].lowcost=0；

printf ("最小生成树的每条边如下： \n" //合计G.vexNum-1边for(I=1； i<； G.vexNum； I ) {

//从最小生成树连接成分以外其他顶点中，到一个//最小生成树连接成分的路径长度为最小的顶点g.vexs [ m ] m=getminpathvexpoi (closed ge，g )； weight=closedge[m].lowcost； printf("%c--%c，权重： %d\n "，closedge[m].adjvex，G.vexs[m]，weight )；

//G.vexs[m]和最小生成树的分量已经相同%EF%BC%8C%E6%89%80%E4%BB%A5%E5%B0%86%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6%E6%B8%85%E9%9B%B6%EF%BC%88%E4%BB%A5%E5%90%8E%E5%B0%B1%E4%B8%8D%E4%BC%9A%E9%80%89%E6%8B%A9%E8%AF%A5%E9%A1%B6%E7%82%B9%E4%BA%86%EF%BC%89%09%09closedge%5Bm%5D.lowcost%3D0%3B%20%09%09//%20G.vexs%5Bm%5D%E5%8A%A0%E5%85%A5%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E5%90%8E%EF%BC%8C%E5%8F%AF%E8%83%BD%E7%BC%A9%E5%B0%8F%E5%85%B6%E5%AE%83%E5%B0%9A%E6%9C%AA%E5%8A%A0%E5%85%A5%E9%A1%B6%E7%82%B9%E5%88%B0%E6%95%B4%E4%B8%AA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E7%9A%84%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6%09%09for%28j%3D0%3B%20j%3CG.vexNum%3B%20j%2B%2B%29%09%09%09if%28G.edges%5Bm%2AG.vexNum%2Bj%5D%20%3C%20closedge%5Bj%5D.lowcost%29%09%09%09%7B%20%0A%09%09%09%09//%20%E5%A6%82%E6%9E%9C%E6%9F%90%E4%B8%AA%E9%A1%B6%E7%82%B9G.vexs%5Bj%5D%E5%88%B0%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E4%B8%AD%E7%9A%84%E9%A1%B6%E7%82%B9G.vexs%5Bm%5D%E7%9A%84%E8%BE%B9%E6%9D%83%E6%9B%B4%E5%B0%8F%EF%BC%8C%09%09%09%09//%20%E5%88%99%E6%9B%B4%E6%96%B0%E9%A1%B6%E7%82%B9G.vexs%5Bj%5D%E5%88%B0%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E7%9A%84%E9%82%BB%E6%8E%A5%E9%A1%B6%E7%82%B9%E5%92%8C%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6%09%09%09%09closedge%5Bj%5D.adjvex%3DG.vexs%5Bm%5D%3B%09%09%09%09closedge%5Bj%5D.lowcost%3DG.edges%5Bm%2AG.vexNum%2Bj%5D%3B%09%09%09%7D%0A%09%7D%7D%0Avoid%20menu%28%29%7B%09printf%28%22%5Cn%22%29%3B%0A%09printf%28%22%5Cn%5Ct%5Ct%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E6%B1%82%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%20%20%20%20%20%20%20%20%20%20%20%20%20%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%201%20%E8%BE%93%E5%85%A5%E6%97%A0%E5%90%91%E7%BD%91%EF%BC%8C%E5%88%9B%E5%BB%BA%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%202%20Prim%E7%AE%97%E6%B3%95%E6%B1%82%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%203%20%E6%B8%85%E5%B1%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%20%20%20%20%200%20%E9%80%80%E5%87%BA%E7%A8%8B%E5%BA%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%22%29%3B%09printf%28%22%5Cn%5Ct%5Ct%E8%AF%B7%E8%BE%93%E5%85%A5%E8%8F%9C%E5%8D%95%E9%A1%B9%EF%BC%9A%22%29%3B%7D%0Avoid%20main%28%29%7B%0A%09MGraph%20G%3B%09int%20select%3B%09while%281%29%09%7B%0A%09%09menu%28%29%3B%0A%09%09scanf%28%22%25d%22%2C%20%26select%29%3B%09%09switch%28select%29%09%09%7B%09%09case%201%3A%0A%09%09%09createGraph%28G%29%3B%09%09%09break%3B%09%09case%202%3A%0A%09%09%09getMinSpanTreeByPrim%28G%2C%20G.vexs%5B0%5D%29%3B%09%09%09break%3B%09%09case%203%3A%0A%09%09%09system%28%22cls%22%29%3B%09%09%09break%3B%09%09case%200%3A%09%09%09exit%281%29%3B%09%09default%3A%09%09%09printf%28%22%E8%8F%9C%E5%8D%95%E8%BE%93%E5%85%A5%E9%94%99%E8%AF%AF%EF%BC%8C%E8%AF%B7%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%21%5Cn%22%29%3B%09%09%7D%09%7D%7D%0A/%2A%20%0A%E9%9D%9E%E9%80%92%E5%BD%92%E6%B1%82%E8%A7%A3Hanoi%E9%97%AE%E9%A2%98%E3%80%90%E9%93%BE%E6%A0%88%E3%80%91%2A/%23include%20%22stdio.h%22typedef%20struct%7B%09int%20n%3B%0A%09char%20source%3B%09char%20temp%3B%09char%20target%3B%7DNode%3Btypedef%20struct%20stacknode%7B%0A%09Node%20data%3B%0A%09struct%20stacknode%20%2Anext%3B%7DStackNode%3Btypedef%20struct%7B%0A%09StackNode%20%2Atop%3B%20%7DLinkStack%3B//%20%E5%88%9D%E5%A7%8B%E5%8C%96%E9%93%BE%E6%A0%88%0Avoid%20Init%28LinkStack%20%26s%29%7B%09s.top%20%3D%20NULL%3B%7D%0A//%20%E5%88%A4%E6%A0%88%E7%A9%BA%0Abool%20IsEmpty%28LinkStack%20s%29%7B%0A%09if%28%20NULL%20%3D%3D%20s.top%20%29%09%09return%20true%3B%09else%20%09%09return%20false%3B%7D%0A//%20%E8%BF%9B%E6%A0%88%0Avoid%20Push%28LinkStack%20%26s%2C%20Node%20x%29%7B%09StackNode%20%2Ap%3B%09//%E5%BC%80%E8%BE%9F%E7%A9%BA%E9%97%B4%EF%BC%8C%E6%9E%84%E9%80%A0%E7%BB%93%E7%82%B9%09p%20%3D%20new%20StackNode%3B%0A%09p-%3Edata%20%3D%20x%3B%09p-%3Enext%20%3D%20NULL%3B%09//%E5%B0%86%E6%9E%84%E9%80%A0%E5%A5%BD%E7%9A%84%E7%BB%93%E7%82%B9%E5%85%A5%E6%A0%88%0A%09p-%3Enext%20%3D%20s.top%3B%09s.top%20%3D%20p%3B%7D%0A//%20%E5%87%BA%E6%A0%88%0Abool%20Pop%28LinkStack%20%26s%2C%20Node%20%26x%29%7B%09%09StackNode%20%2Ap%3B%0A%09if%28%20IsEmpty%28s%29%20%29%0A%09%09return%20false%3B%09%09//%E8%BF%94%E5%9B%9Efalse%E4%BB%A3%E8%A1%A8%E5%87%BA%E6%A0%88%E6%B2%A1%E6%9C%89%E6%88%90%E5%8A%9F%EF%BC%81%09else%09%7B%0A%09%09x%20%3D%20s.top-%3Edata%3B%09%09p%20%3D%20s.top%3B%09%09s.top%20%3D%20s.top-%3Enext%3B%09%09return%20true%3B%09%7D%7D%0A//%20hanoi%E5%87%BD%E6%95%B0%E8%BE%93%E5%87%BA%E7%9B%98%E5%AD%90%E7%A7%BB%E5%8A%A8%E6%AD%A5%E9%AA%A4%0Avoid%20hanoi%28int%20num%2C%20char%20x%2C%20char%20y%2C%20char%20z%29%7B%09LinkStack%20stack%3B%09Node%20snode%3B%0A%09Node%20step1%2Cstep2%2Cstep3%3B%09Node%20tmp%3B%09static%20int%20m%3B%0A%09Init%28%20stack%20%29%3B%09//%E6%9E%84%E9%80%A0%E7%BB%93%E7%82%B9%E8%BF%9B%E6%A0%88%0A%09snode.n%20%3D%20num%3B%09snode.source%20%3D%20x%3B%09snode.temp%20%3D%20y%3B%09snode.target%20%3D%20z%3B%09Push%28%20stack%2C%20snode%20%29%3B%09%0A%09while%28%20false%20%3D%3D%20IsEmpty%28stack%29%20%29%09%7B%09%09Pop%28%20stack%2C%20tmp%20%29%3B%09%0A%09%09if%28%20tmp.n%20%3E1%20%29%09%09%7B%09%09%09//%E5%B0%86%20tmp%20%E9%97%AE%E9%A2%98%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%B8%89%E4%B8%AA%E7%BB%93%E7%82%B9%E8%BF%9B%E6%A0%88%0A%09%09%09step1.n%20%3D%20tmp.n%20-%201%3B%09%09//%20%E4%B8%8D%E8%83%BD%E5%86%99%E6%88%90%20%20step1.n%20%3D%20num%20-%201%3B%09%09%09%09step1.source%20%3D%20tmp.source%3B%09%09%09step1.target%20%3D%20tmp.temp%3B%09%09%09step1.temp%20%3D%20tmp.target%3B%0A%09%09%09step2.n%20%3D%201%3B%0A%09%09%09step2.source%20%3D%20tmp.source%3B%09%09%09step2.target%20%3D%20tmp.target%3B%09%09%09step2.temp%20%3D%20tmp.temp%3B%09%09%09step3.n%20%3D%20tmp.n%20-%201%3B%09%09%09step3.source%20%3D%20tmp.temp%3B%09%09%09step3.temp%20%3D%20tmp.source%3B%09%09%09step3.target%20%3D%20tmp.target%3B%09%09%09Push%28%20stack%2C%20step3%20%29%3B%09%09%09Push%28%20stack%2C%20step2%20%29%3B%09%09%09Push%28%20stack%2C%20step1%20%29%3B%09%09%0A%09%09%7D%0A%09%09else%0A%09%09%09printf%28%22%5Cn%25d%3A%25c--%3E%25c%22%2C%20%2B%2Bm%2C%20tmp.source%2C%20tmp.target%20%29%3B%09%09%7D%7D%0Avoid%20main%28%29%7B%09int%20n%3B%0A%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E7%9B%98%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0%3A%5Cn%22%29%3B%09scanf%28%22%25d%22%2C%26n%29%3B%09printf%28%22%E7%9B%98%E5%AD%90%E7%9A%84%E7%A7%BB%E5%8A%A8%E9%A1%BA%E5%BA%8F%E4%B8%BA%3A%22%29%3B%09hanoi%28n%2C%20%27A%27%2C%20%27B%27%2C%20%27C%27%29%3B%09printf%28%22%5Cn%5Cn%22%29%3B%7D%0A/%2A%20%0A%E9%9D%9E%E9%80%92%E5%BD%92%E6%B1%82%E8%A7%A3Hanoi%E9%97%AE%E9%A2%98%E3%80%90%E9%A1%BA%E5%BA%8F%E6%A0%88%E3%80%91%2A/%23include%20%22stdio.h%22%23define%20MAXLEN%2030typedef%20struct%7B%09int%20n%3B%0A%09char%20source%3B%09char%20temp%3B%09char%20target%3B%7DNode%3Btypedef%20struct%7B%0A%09Node%20data%5BMAXLEN%5D%3B%09int%20top%3B%20%7DSeqStack%3B%0A//%20%E5%88%9D%E5%A7%8B%E5%8C%96%E9%A1%BA%E5%BA%8F%E6%A0%88%0Avoid%20Init%28SeqStack%20%26s%29%7B%09s.top%20%3D%20-1%3B%7D%0A//%20%E5%88%A4%E6%A0%88%E7%A9%BA%0Abool%20IsEmpty%28SeqStack%20s%29%7B%0A%09if%28%20-1%20%3D%3D%20s.top%20%29%09%09return%20true%3B%09else%20%09%09return%20false%3B%7D%0A//%20%E5%88%A4%E6%A0%88%E6%BB%A1%0Abool%20IsFull%28SeqStack%20s%29%7B%0A%09if%28%20MAXLEN%20-%201%20%3D%3D%20s.top%20%29%09%09%09return%20true%3B%09else%0A%09%09return%20false%3B%7D//%20%E8%BF%9B%E6%A0%88%0Abool%20Push%28SeqStack%20%26s%2C%20Node%20x%29%7B%09if%28%20%20IsFull%28s%29%20%29%0A%09%09return%20false%3B%09%09//%E8%BF%94%E5%9B%9Efalse%E4%BB%A3%E8%A1%A8%E5%85%A5%E6%A0%88%E6%B2%A1%E6%9C%89%E6%88%90%E5%8A%9F%EF%BC%81%09else%09%7B%0A%09%09s.top%20%2B%2B%3B%0A%09%09s.data%5B%20s.top%20%5D%20%3D%20x%3B%09%09return%20true%3B%09%7D%7D%0A//%20%E5%87%BA%E6%A0%88%0Abool%20Pop%28SeqStack%20%26s%2C%20Node%20%26x%29%7B%09if%28%20IsEmpty%28s%29%20%29%0A%09%09return%20false%3B%09%09//%E8%BF%94%E5%9B%9Efalse%E4%BB%A3%E8%A1%A8%E5%87%BA%E6%A0%88%E6%B2%A1%E6%9C%89%E6%88%90%E5%8A%9F%EF%BC%81%09else%09%7B%0A%09%09x%20%3D%20s.data%5B%20s.top%20%5D%3B%09%09s.top%20--%3B%09%09return%20true%3B%09%7D%0A%7D%0A//%20hanoi%E5%87%BD%E6%95%B0%E8%BE%93%E5%87%BA%E7%9B%98%E5%AD%90%E7%A7%BB%E5%8A%A8%E6%AD%A5%E9%AA%A4%0Avoid%20hanoi%28int%20num%2C%20char%20x%2C%20char%20y%2C%20char%20z%29%7B%09SeqStack%20stack%3B%09Node%20snode%3B%0A%09Node%20step1%2Cstep2%2Cstep3%3B%09Node%20tmp%3B%09static%20int%20m%3B%0A%09Init%28%20stack%20%29%3B%09//%E6%9E%84%E9%80%A0%E7%BB%93%E7%82%B9%E8%BF%9B%E6%A0%88%0A%09snode.n%20%3D%20num%3B%09snode.source%20%3D%20x%3B%09snode.temp%20%3D%20y%3B%09snode.target%20%3D%20z%3B%09Push%28%20stack%2C%20snode%20%29%3B%09%0A%09while%28%20false%20%3D%3D%20IsEmpty%28stack%29%20%29%09%7B%09%09Pop%28%20stack%2C%20tmp%20%29%3B%09%0A%09%09if%28%20tmp.n%20%3E1%20%29%09%09%7B%09%09%09//%E5%B0%86%20tmp%20%E9%97%AE%E9%A2%98%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%B8%89%E4%B8%AA%E7%BB%93%E7%82%B9%E8%BF%9B%E6%A0%88%0A%09%09%09step1.n%20%3D%20tmp.n%20-%201%3B%09%09//%20%E4%B8%8D%E8%83%BD%E5%86%99%E6%88%90%20%20step1.n%20%3D%20num%20-%201%3B%09%09%09%09step1.source%20%3D%20tmp.source%3B%09%09%09step1.target%20%3D%20tmp.temp%3B%09%09%09step1.temp%20%3D%20tmp.target%3B%0A%09%09%09step2.n%20%3D%201%3B%0A%09%09%09step2.source%20%3D%20tmp.source%3B%09%09%09step2.target%20%3D%20tmp.target%3B%09%09%09step2.temp%20%3D%20tmp.temp%3B%09%09%09step3.n%20%3D%20tmp.n%20-%201%3B%09%09%09step3.source%20%3D%20tmp.temp%3B%09%09%09step3.temp%20%3D%20tmp.source%3B%09%09%09step3.target%20%3D%20tmp.target%3B%09%09%09Push%28%20stack%2C%20step3%20%29%3B%09%09%09Push%28%20stack%2C%20step2%20%29%3B%09%09%09Push%28%20stack%2C%20step1%20%29%3B%09%09%0A%09%09%7D%0A%09%09else%0A%09%09%09printf%28%22%5Cn%25d%3A%25c--%3E%25c%22%2C%20%2B%2Bm%2C%20tmp.source%2C%20tmp.target%20%29%3B%09%09%7D%7D%0Avoid%20main%28%29%7B%09int%20n%3B%0A%09printf%28%22%E8%AF%B7%E8%BE%93%E5%85%A5%E7%9B%98%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0%3A%5Cn%22%29%3B%09scanf%28%22%25d%22%2C%26n%29%3B%09printf%28%22%E7%9B%98%E5%AD%90%E7%9A%84%E7%A7%BB%E5%8A%A8%E9%A1%BA%E5%BA%8F%E4%B8%BA%3A%22%29%3B%09hanoi%28n%2C%20%27A%27%2C%20%27B%27%2C%20%27C%27%29%3B%09printf%28%22%5Cn%5Cn%22%29%3B%7D%0A/%2A%20%0A%E8%BF%B7%E5%AE%AB%E9%97%AE%E9%A2%98%2A/%0A%23include%20%3Ciostream%3E%23include%20%3Cfstream%3E%23include%20%3Cstring%3Eusing%20namespace%20std%3B//%20%E5%AE%9A%E4%B9%89%E6%8F%8F%E8%BF%B0%E8%BF%B7%E5%AE%AB%E4%B8%AD%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E7%9A%84%E7%B1%BBclass%20T%20%20%20%20%20%20%20%7B%0Apublic%3A%0A%20%20%20%20int%20x%3B%20%20%20%20%20%20%20%20%20%20//%20x%E4%BB%A3%E8%A1%A8%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E7%9A%84%E8%A1%8C%E5%9D%90%E6%A0%87%20%20%20%20int%20y%3B%20%20%20%20%20%20%20%20%20%20//%20y%E4%BB%A3%E8%A1%A8%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E7%9A%84%E5%88%97%E5%9D%90%E6%A0%87%20%20%20%20int%20dir%3B%20%20%20%20%20%20%20%20//%200--%E4%B8%9C%EF%BC%9B1--%E5%8D%97%EF%BC%9B2--%E8%A5%BF%EF%BC%9B3--%E5%8C%97%EF%BC%9B4--%E4%B8%8D%E9%80%9A%7D%3B//%20%E9%93%BE%E6%A0%88%E7%9A%84%E7%BB%93%E7%82%B9%E7%B1%BB%0Aclass%20LinkNode%20%20%20%20%20%20%7B%0A%20%20%20%20friend%20class%20Stack%3Bpublic%3A%20%20%20%20T%20data%3B%0A%20%20%20%20LinkNode%20%2Anext%3B%7D%3Bclass%20Stack%20%7B%0Aprivate%3A%0A%20%20%20%20LinkNode%20%2Atop%3B%09%09%09//%20%E6%8C%87%E5%90%91%E7%AC%AC%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9%E7%9A%84%E6%A0%88%E9%A1%B6%E6%8C%87%E9%92%88public%3A%20%20%20%20Stack%28%29%3B%09%09%09%09//%20%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0%EF%BC%8C%E7%BD%AE%E7%A9%BA%E6%A0%88%20%20%20%20~Stack%28%29%3B%09%09%09%09//%20%E6%9E%90%E6%9E%84%E5%87%BD%E6%95%B0%0A%20%20%20%20void%20push%28T%20e%29%3B%09%09%09//%20%E6%8A%8A%E5%85%83%E7%B4%A0e%E5%8E%8B%E5%85%A5%E6%A0%88%E4%B8%AD%20%20%20%20T%20pop%28%29%3B%09%09%09%09//%20%E4%BD%BF%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%E5%87%BA%E6%A0%88%20%20%20%20T%20getTop%28%29%3B%09%09%09%09//%20%E5%BE%97%E5%88%B0%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%20%20%20%20void%20Clear%28%29%3B%09%09%09//%20%E6%8A%8A%E6%A0%88%E6%B8%85%E7%A9%BA%09void%20addTopDir%28%29%3B%09%09//%20%E6%A0%88%E9%A1%B6%E7%BB%93%E7%82%B9%E7%9A%84%E6%96%B9%E5%90%91%E5%8A%A01%20%20%20%20bool%20isEmpty%28%29%3B%09%09%09//%20%E5%88%A4%E6%96%AD%E6%A0%88%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%EF%BC%8C%E5%A6%82%E6%9E%9C%E4%B8%BA%E7%A9%BA%E5%88%99%E8%BF%94%E5%9B%9E1%EF%BC%8C%E5%90%A6%E5%88%99%E8%BF%94%E5%9B%9E0%7D%3B%0A//%20%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0%EF%BC%8C%E7%BD%AE%E7%A9%BA%E6%A0%88%0AStack%3A%3AStack%28%29%20%20%20%20%20%20%20%20%20%20%7B%20%20%20%20top%3DNULL%3B%7D%0A//%20%E6%9E%90%E6%9E%84%E5%87%BD%E6%95%B0%0AStack%3A%3A~Stack%28%29%20%20%20%20%20%20%20%20%20%7B%7D%0A//%20%E6%8A%8A%E5%85%83%E7%B4%A0e%E5%8E%8B%E5%85%A5%E6%A0%88%E4%B8%AD%0Avoid%20Stack%3A%3Apush%28T%20e%29%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20LinkNode%20%2Ap%3B%20%20%20%20p%3Dnew%20LinkNode%3B%20%20%20%20p-%3Edata%3De%3B%20%20%20%20p-%3Enext%3Dtop%3B%20%20%20%20top%3Dp%3B%7D%0A//%20%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%E5%87%BA%E6%A0%88%0AT%20Stack%3A%3Apop%28%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%20%20T%20tmp%3B%0A%20%20%20%20LinkNode%20%2Ap%3B%20%20%20%20p%3Dtop%3B%0A%20%20%20%20top%3Dtop-%3Enext%3B%20%20%20%20tmp%3Dp-%3Edata%3B%20%20%20%20delete%20p%3B%20%20%20%20return%20tmp%3B%7D%0A//%20%E5%BE%97%E5%88%B0%E5%87%BA%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%0AT%20Stack%3A%3AgetTop%28%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%20%20return%20top-%3Edata%3B%7D%0A//%E6%8A%8A%E6%A0%88%E6%B8%85%E7%A9%BA%0Avoid%20Stack%3A%3AClear%28%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%09LinkNode%20%2Ap%3B%0A%09while%28top%29%09%7B%09%09p%3Dtop%3B%0A%09%09top%3Dtop-%3Enext%3B%09%09delete%20p%3B%09%7D%7D%0Avoid%20Stack%3A%3AaddTopDir%28%29%7B%09top-%3Edata.dir%2B%2B%3B%7D%0A//%20%E5%88%A4%E6%96%AD%E6%A0%88%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%EF%BC%8C%E5%A6%82%E6%9E%9C%E4%B8%8D%E4%B8%BA%E7%A9%BA%E5%88%99%E8%BF%94%E5%9B%9Efalse%EF%BC%8C%E5%90%A6%E5%88%99%E8%BF%94%E5%9B%9Etruebool%20Stack%3A%3AisEmpty%28%29%20%20%20%20%20%20%20%20%7B%20%20%20%20if%28top%29%20%09%09return%20false%3B%20%20%20%20else%20%0A%09%09return%20true%3B%7D//%20%E8%AF%BB%E5%8F%96%E8%BF%B7%E5%AE%AB%0Achar%2A%2A%20getMaze%28int%20%26rowNum%2C%20int%20%26colNum%29%7B%20%20%20%20char%20%2A%2Amaze%3B%09%09%09%09%09%09//%20%E5%AE%9A%E4%B9%89%E4%BA%8C%E7%BB%B4%E6%8C%87%E9%92%88%E5%AD%98%E5%8F%96%E8%BF%B7%E5%AE%AB%20%20%20%20int%20i%3D0%2C%20j%3D0%3B%09fstream%20rs%3B%0A%09rs.open%28%22mazeInfo.txt%22%2C%20ios_base%3A%3Ain%29%3B%09//%20%E8%AF%BB%E5%88%B0%E8%BF%B7%E5%AE%AB%E7%9A%84%E8%A1%8C%E6%95%B0%E5%92%8C%E5%88%97%E6%95%B0%0A%09rs%3E%3ErowNum%3E%3EcolNum%3B%20%20%09%0A%09maze%3Dnew%20char%20%2A%5BrowNum%5D%3B%09%09//%20%E7%94%B3%E8%AF%B7%E9%95%BF%E5%BA%A6%E7%AD%89%E4%BA%8E%E8%A1%8C%E6%95%B0%E7%9A%84%E6%95%B4%E5%9E%8B%E6%8C%87%E9%92%88%E5%8F%98%E9%87%8F%E7%A9%BA%E9%97%B4%0A%20%20%20%20for%28i%3D0%3B%20i%3CrowNum%3B%20i%2B%2B%29%09%09%09//%20%E7%94%B3%E8%AF%B7%E6%AF%8F%E8%A1%8C%E7%9A%84%E7%A9%BA%E9%97%B4%20%20%20%20%20%20%20%20maze%5Bi%5D%3Dnew%20char%5BcolNum%5D%3B%09//%20%E8%AF%BB%E5%85%A5%E8%BF%B7%E5%AE%AB%E7%9A%84%E5%86%85%E5%AE%B9%EF%BC%88%E5%8C%85%E6%8B%AC%E5%9B%B4%E6%A0%8F%EF%BC%89%EF%BC%8C%2A%E4%BB%A3%E8%A1%A8%E5%8F%AF%E9%80%9A%EF%BC%8C%23%E4%BB%A3%E8%A1%A8%E4%B8%8D%E9%80%9A%20%20%20%20for%28i%3D0%3B%20i%3CrowNum%3B%20i%2B%2B%29%09%09%7B%20%20%20%20%20%20%20%20for%28j%3D0%3B%20j%3CcolNum%3B%20j%2B%2B%29%20%20%20%20%20%20%20%20%20%20%20%20rs%3E%3Emaze%5Bi%5D%5Bj%5D%3B%20%09%7D%09cout%3C%3C%22%E8%BF%B7%E5%AE%AB%E6%95%B0%E6%8D%AE%E8%AF%BB%E5%8F%96%E6%88%90%E5%8A%9F%21%22%3C%3Cendl%3B%0A%20%20%20%20return%20maze%3B%09%09%09%09%09//%20%E8%BF%94%E5%9B%9E%E5%AD%98%E8%B4%AE%E8%BF%B7%E5%AE%AB%E7%9A%84%E4%BA%8C%E7%BB%B4%E6%8C%87%E9%92%88maze%7D%3B//%20%E8%BE%93%E5%87%BA%E8%B7%AF%E5%BE%84%0Avoid%20printPath%28Stack%20s%29%20%20%20%20%20%20%20%20%7B%20%20%20%20%09//%20%E5%AE%9A%E4%B9%89%E4%B8%80%E4%B8%AA%E6%A0%88%EF%BC%8C%E6%8C%89%E4%BB%8E%E5%87%BA%E5%8F%A3%E5%88%B0%E5%85%A5%E5%8F%A3%E4%BE%9D%E6%AC%A1%E8%BF%9B%E6%A0%88%EF%BC%8C%E5%87%BA%E6%A0%88%E8%BE%93%E5%87%BA%E5%8D%B3%E5%8F%AF%E5%BE%97%E5%88%B0%E8%B7%AF%E5%BE%84%09Stack%20t%3B%20%09T%20tmp%3B%09%0A%09//%20%E7%94%B1%E4%BA%8Es%E7%9A%84%E6%A0%88%E9%A1%B6%E6%97%B6%E7%9B%AE%E6%A0%87%EF%BC%8C%E6%89%80%E4%BB%A5%E5%85%88%E6%8A%8As%E4%B8%AD%E7%9A%84%E7%BB%93%E7%82%B9%E5%85%A8%E9%83%A8%E5%AF%BC%E5%85%A5%E5%88%B0t%09while%28%21s.isEmpty%28%29%29%09%09t.push%28s.pop%28%29%29%3B%0A%09cout%3C%3C%22%E8%BF%B7%E5%AE%AB%E4%B8%AD%E7%9A%84%E9%80%9A%E9%81%93%E8%B7%AF%E5%BE%84%E4%B8%BA%EF%BC%9A%5Cn%22%3B%20%20%20%20//%E8%BE%93%E5%87%BA%E8%B7%AF%E5%BE%84%EF%BC%8C%E5%8C%85%E6%8B%AC%E8%A1%8C%E5%9D%90%E6%A0%87%EF%BC%8C%E5%88%97%E5%9D%90%E6%A0%87%EF%BC%8C%E4%B8%8B%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%E6%96%B9%E5%90%91%0A%20%20%20%20while%28%21t.isEmpty%28%29%29%20%20%20%20%20%20%20%20%20//%20%E6%A0%88%E9%9D%9E%E7%A9%BA%EF%BC%8C%E7%BB%A7%E7%BB%AD%E8%BE%93%E5%87%BA%20%20%20%20%7B%20%20%20%20%20%20%20%20tmp%3Dt.pop%28%29%3B%0A%20%20%20%20%20%20%20%20cout%3C%3C%22%EF%BC%88%22%3C%3Ctmp.x%3C%3C%22%EF%BC%8C%22%3C%3Ctmp.y%3C%3C%22%EF%BC%8C%22%3B%20%20//%E8%BE%93%E5%87%BA%E8%A1%8C%E5%9D%90%E6%A0%87%EF%BC%8C%E5%88%97%E5%9D%90%E6%A0%87%09%09switch%28tmp.dir%29%20%20%20//%E8%BE%93%E5%87%BA%E7%9B%B8%E5%BA%94%E7%9A%84%E6%96%B9%E5%90%91%20%20%20%20%20%20%20%20%7B%20%20%20%20%20%20%20%20%20%20%20%20%09%09case%200%3A%09%09%09cout%3C%3C%22%E2%86%92%EF%BC%89%5Cn%22%3B%09%09%09break%3B%0A%09%09case%201%3A%0A%09%09%09cout%3C%3C%22%E2%86%93%EF%BC%89%5Cn%22%3B%09%09%09break%3B%09%09case%202%3A%0A%09%09%09cout%3C%3C%22%E2%86%90%EF%BC%89%5Cn%22%3B%09%09%09break%3B%09%09case%203%3A%0A%09%09%09cout%3C%3C%22%E2%86%91%EF%BC%89%5Cn%22%3B%09%09%09break%3B%20%20%20%20%20%20%20%20%7D%20%20%20%20%7D%0A%7D%0A//%20%E5%AF%BB%E6%89%BE%E8%BF%B7%E5%AE%ABmaze%E4%B8%AD%E4%BB%8E%E5%85%A5%E5%8F%A3%E5%88%B0%E5%87%BA%E5%8F%A3%E7%9A%84%E8%B7%AF%E5%BE%84//%20%E6%89%BE%E5%88%B0%E5%88%B0%E5%88%99%E8%BF%94%E5%9B%9Etrue%EF%BC%8C%E5%90%A6%E5%88%99%E8%BF%94%E5%9B%9Efalse%0Abool%20searchMazePath%28char%20%2A%2Amaze%2C%20int%20rowNum%2C%20int%20colNum%29%09%7B%09Stack%20s%3B%0A%20%20%20%20T%20start%2C%20tmp%2C%20obj%3B%20%20%20%20int%20i%3B%09//%E5%AE%9A%E4%B9%89%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E7%A7%BB%E5%8A%A8%E7%9A%844%E4%B8%AA%E6%96%B9%E5%90%91%0A%09int%20move%5B4%5D%5B2%5D%3D%7B%7B0%2C%201%7D%2C%20%7B1%2C%200%7D%2C%20%7B0%2C%20-1%7D%2C%20%7B-1%2C%200%7D%7D%3B%20%20%20%09%09start.x%3D1%3B%09start.y%3D1%3B%0A//%09cout%3C%3C%22%E8%AF%B7%E8%BE%93%E5%85%A5%E8%BF%B7%E5%AE%AB%E5%85%A5%E5%8F%A3%EF%BC%8C%E7%BC%BA%E7%9C%81%E4%B8%BA%E5%9D%90%E6%A0%87%281%2C1%29%E4%BD%8D%E7%BD%AE%E5%A4%84%EF%BC%9A%22%3B//%09cin%3E%3Estart.x%3B//%09cin%3E%3Estart.y%3B%0A%09//%20%E9%BB%98%E8%AE%A4%E6%96%B9%E5%90%91%E4%BB%8E%E4%B8%9C%E5%BC%80%E5%A7%8B%09start.dir%3D0%3B%09s.push%28start%29%3B%09%09%09%09%09%09//%20%E5%B0%86%E5%85%A5%E5%8F%A3%E4%BD%8D%E7%BD%AE%E5%85%A5%E6%A0%88%0A%20%20%20%20maze%5Bstart.x%5D%5Bstart.y%5D%3D%27Y%27%3B%09%09%09//%20%E6%A0%87%E5%BF%97%E5%85%A5%E5%8F%A3%E4%BD%8D%E7%BD%AE%E5%B7%B2%E5%88%B0%E8%BE%BE%E8%BF%87%20%20%20%20while%28%21s.isEmpty%28%29%29%09%09//%20%E6%A0%88s%E9%9D%9E%E7%A9%BA%EF%BC%8C%E5%88%99%E8%8E%B7%E5%8F%96%E6%A0%88%E9%A1%B6%E7%BB%93%E7%82%B9%EF%BC%8C%E6%8C%89%E8%AF%A5%E7%BB%93%E7%82%B9%E6%8C%87%E5%AE%9A%E6%96%B9%E5%90%91%E8%B5%B0%E4%B8%8B%E4%B8%80%E6%AD%A5%20%20%20%20%7B%20%20%20%20%20%20%20%20tmp%3Ds.getTop%28%29%3B%09%09//%20%E5%BE%97%E5%88%B0%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%0A%20%20%20%20%20%20%20%20//%20%E6%8E%A2%E7%B4%A2%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E7%9A%844%E4%B8%AA%E7%9B%B8%E9%82%BB%E4%BD%8D%E7%BD%AE%EF%BC%8C%E6%B5%8B%E8%AF%95%E6%96%B0%E4%BD%8D%E7%BD%AE%E6%98%AF%E5%90%A6%E5%8F%AF%E4%BB%A5%E5%85%A5%E6%A0%88%20%20%20%20%20%20%20%20for%28i%3Dtmp.dir%3B%20i%3C4%3B%20i%2B%2B%29%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%20%20%20%20%20%20%20%20%20%20obj.x%3Dtmp.x%2Bmove%5Bi%5D%5B0%5D%3B%09%09%09//%20%E8%AE%A1%E7%AE%97%E5%87%BA%E6%96%B0%E4%BD%8D%E7%BD%AEobj%E7%9A%84%E6%88%90%E5%91%98%E5%80%BC%20%20%20%20%20%20%20%20%20%20%20%20obj.y%3Dtmp.y%2Bmove%5Bi%5D%5B1%5D%3B%09%09%09%09obj.dir%3D0%3B%09%09%09%09%09%09//%20%E8%AE%BE%E7%BD%AE%E7%9B%AE%E6%A0%87%E4%BD%8D%E7%BD%AE%E7%9A%84%E6%96%B9%E5%90%91%E4%BB%8E0%E5%BC%80%E5%A7%8B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%28maze%5Bobj.x%5D%5Bobj.y%5D%3D%3D%27%2A%27%29%09%09//%20%E5%88%A4%E6%96%AD%E7%9B%AE%E6%A0%87%E4%BD%8D%E7%BD%AE%E6%98%AF%E5%90%A6%E5%8F%AF%E4%BB%A5%E9%80%9A%E8%BF%87%EF%BC%8C%E5%B9%B6%E4%B8%94%E5%B0%9A%E6%9C%AA%E8%B5%B0%E8%BF%87%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maze%5Bobj.x%5D%5Bobj.y%5D%3D%27Y%27%3B%09%09//%20%E6%A0%87%E5%BF%97%E7%9B%AE%E6%A0%87%E4%BD%8D%E7%BD%AE%E5%B7%B2%E5%88%B0%E8%BE%BE%E8%BF%87%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s.push%28obj%29%3B%09%09%09%09//%20%E7%9B%AE%E6%A0%87%E4%BD%8D%E7%BD%AE%E5%85%A5%E6%A0%88%09%09%09%09//%20%28rowNum-1%2C%20colNum-1%29%E5%AD%98%E7%9A%84%E8%BE%B9%E7%95%8C%EF%BC%8C%28rowNum-2%2C%20colNum-2%29%E5%AD%98%E7%9A%84%E6%89%8D%E6%98%AF%E5%87%BA%E5%8F%A3%09%09%09%09%09%09%09//%20%E5%A6%82%E6%9E%9C%E5%BD%93%E5%89%8D%E7%BB%93%E7%82%B9%E7%AD%89%E4%BA%8E%E7%BB%88%E7%82%B9%E4%BA%86%EF%BC%8C%E8%A1%A8%E7%A4%BA%E6%88%90%E5%8A%9F%E5%88%B0%E8%BE%BE%E5%87%BA%E5%8F%A3%09%09%09%09if%28%28obj.x%3D%3DrowNum-2%29%20%26%26%20%28obj.y%3D%3DcolNum-2%29%29%20%20%09%09%09%09%7B%0A%09%09%09%09%09printPath%28s%29%3B%09%09%09//%E8%BE%93%E5%87%BA%E8%B7%AF%E5%BE%84%09%09%09%09%09return%20true%3B%09%09%09//%E8%A1%A8%E7%A4%BA%E6%88%90%E5%8A%9F%E6%89%BE%E5%88%B0%E8%B7%AF%E5%BE%84%09%09%09%09%7D%09%09%09%09break%3B%20%20%20%20%20%20%20%20%20%20%20%20%7D%09%09%09else%0A%09%09%09%7B%0A%09%09%09%09//%20%E5%89%8D%E4%B8%80%E6%96%B9%E5%90%91%E7%9A%84%E4%B8%8D%E9%80%9A%EF%BC%8C%E5%88%99%E6%A0%88%E9%A1%B6%E7%BB%93%E7%82%B9%E7%9A%84%E6%96%B9%E5%90%91%E5%8A%A01%09%09%09%09s.addTopDir%28%29%3B%09%09%09%7D%20%20%20%20%20%20%20%20%7D%09%09%0A%09%09//%20%E5%A6%82%E6%9E%9C%E5%BD%93%E5%89%8D%E6%A0%88%E9%A1%B6%E7%9A%84%E5%9B%9B%E4%B8%AA%E6%96%B9%E5%90%91%E5%9D%87%E6%97%A0%E9%80%9A%E8%B7%AF%EF%BC%8C%E5%88%99%E5%87%BA%E6%A0%88%EF%BC%8C%E5%8D%B3%E9%80%80%E5%9B%9E%E5%88%B0%E4%B8%8A%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%09%09//%20%E4%B8%8A%E4%B8%80%E4%BD%8D%E7%BD%AE%E7%9A%84%E6%96%B9%E5%90%91%E8%A6%81%E5%8A%A01%20%20%20%20%20%20%20%20if%28i%3D%3D4%29%20%20%20%20%09%09%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20s.pop%28%29%3B%09%09%09if%28%21s.isEmpty%28%29%29%09%09%09%7B%09%09%09%09//%20%E5%89%8D%E4%B8%80%E6%96%B9%E5%90%91%E7%9A%84%E4%B8%8D%E9%80%9A%EF%BC%8C%E9%87%8D%E6%96%B0%E9%80%80%E5%9B%9E%E5%88%B0%E8%AF%A5%E7%BB%93%E7%82%B9%EF%BC%8C%E5%88%99%E8%AF%A5%E6%A0%88%E9%A1%B6%E7%BB%93%E7%82%B9%E7%9A%84%E6%96%B9%E5%90%91%E5%8A%A01%09%09%09%09s.addTopDir%28%29%3B%09%09%09%09%7D%09%09%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20false%3B%20%20%20%20%20%20%20%20%20%20%20//%E8%A1%A8%E7%A4%BA%E6%9F%A5%E6%89%BE%E5%A4%B1%E8%B4%A5%EF%BC%8C%E5%8D%B3%E8%BF%B7%E5%AE%AB%E6%97%A0%E8%B7%AF%E5%BE%84%7D//%20%E7%A8%8B%E5%BA%8F%E8%8F%9C%E5%8D%95%0Avoid%20menu%28%29%7B%0A%09printf%28%22%5Cn%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%E8%BF%B7%E5%AE%AB%E9%97%AE%E9%A2%98%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%201%20%E4%BB%8Emaze.txt%E8%AF%BB%E5%85%A5%E8%BF%B7%E5%AE%AB%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%202%20%E4%BB%8E%E5%85%A5%E5%8F%A3%E5%9D%90%E6%A0%87%281%2C1%29%E5%AF%BB%E6%89%BE%E5%88%B0%E5%87%BA%E5%8F%A3%E7%9A%84%E9%80%9A%E8%B7%AF%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%203%20%E6%B8%85%E5%B1%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%20%20%20%20%20%20%20%20%20%20%20%20%200%20%E9%80%80%E5%87%BA%E7%A8%8B%E5%BA%8F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2A%5Cn%22%29%3B%09printf%28%22%5Ct%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%2A%5Cn%22%29%3B%09printf%28%22%5Ct%E8%AF%B7%E8%BE%93%E5%85%A5%E8%8F%9C%E5%8D%95%E9%A1%B9%EF%BC%9A%22%29%3B%7D%0A//%20%E4%B8%BB%E5%87%BD%E6%95%B0%0Avoid%20main%28%29%20%7B%0A%20%20%20%20int%20rowNum%3D0%2C%20colNum%3D0%3B%09%09%09//%E5%AE%9A%E4%B9%89%E8%BF%B7%E5%AE%AB%E7%9A%84%E9%95%BF%E5%92%8C%E5%AE%BD%20%20%20%20char%20%2A%2Amaze%3B%09%09%09%09%09//%E5%AE%9A%E4%B9%89%E4%BA%8C%E7%BB%B4%E6%8C%87%E9%92%88%E5%AD%98%E5%8F%96%E8%BF%B7%E5%AE%AB%09int%20choice%3B%09while%281%29%09%7B%0A%09%09menu%28%29%3B%0A%09%09scanf%28%22%25d%22%2C%20%26choice%29%3B%09%09switch%28choice%29%09%09%7B%09%09case%201%3A%0A%09%09%09//%20%E8%AF%BB%E5%8F%96%E8%BF%B7%E5%AE%AB%E4%BF%A1%E6%81%AF%0A%09%09%09maze%3DgetMaze%28rowNum%2C%20colNum%29%3B%20%20%09%09%09break%3B%09%09case%202%3A%0A%09%09%09//%20%E6%B1%82%E8%BF%B7%E5%AE%AB%E5%85%A5%E5%8F%A3%E5%88%B0%E5%87%BA%E5%8F%A3%E7%9A%84%E8%B7%AF%E5%BE%84%0A%09%09%09if%28%21searchMazePath%28maze%2C%20rowNum%2C%20colNum%29%29%0A%09%09%09%09cout%3C%3C%22%E8%BF%B7%E5%AE%AB%E4%B8%AD%E4%BB%8E%EF%BC%881%2C1%EF%BC%89%E5%88%B0%EF%BC%88%22%3C%3CrowNum-2%3C%3C%22%2C%22%3C%3CcolNum-2%3C%3C%22%EF%BC%89%E4%B8%8D%E5%AD%98%E5%9C%A8%E9%80%9A%E8%B7%AF%21%5Cn%22%3B%09%09%09break%3B%09%09case%203%3A%0A%09%09%09system%28%22cls%22%29%3B%09%09%09break%3B%09%09case%200%3A%0A%09%09%09exit%28-1%29%3B%09%09%09break%3B%09%09default%3A%0A%09%09%09printf%28%22%E8%8F%9C%E5%8D%95%E9%80%89%E6%8B%A9%E9%94%99%E8%AF%AF%EF%BC%8C%E8%AF%B7%E9%87%8D%E6%96%B0%E8%BE%93%E5%85%A5%21%5Cn%22%29%3B%09%09%7D%09%09%0A%09%7D%7D/%2A%20%0A%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%BD%AC%E5%90%8E%E7%BC%80%E5%B9%B6%E6%B1%82%E5%80%BC%E3%80%90%E8%BF%90%E7%AE%97%E5%AF%B9%E8%B1%A1%E4%B8%BA%E4%B8%AA%E4%BD%8D%E6%95%B0%E3%80%91%2A/%0A%23include%3Cstdio.h%3E%23define%20MAXLEN%20100typedef%20struct%20%20%20%20%20%20%20%20%20%20%20//%E5%AE%9A%E4%B9%89%E4%B8%80%E4%B8%AA%E7%BB%93%E6%9E%84%E4%BD%93%EF%BC%8C%E5%85%85%E5%BD%93%E8%BF%90%E7%AE%97%E7%AC%A6%E5%8F%B7%E6%A0%88%7B%20%20%09char%20data%5BMAXLEN%5D%3B%20%0A%09int%20top%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7DOperatorStack%3B%20%20typedef%20struct%20%20%20%20%20%20%20%20%20%20//%E5%86%8D%E5%AE%9A%E4%B9%89%E4%B8%80%E4%B8%AA%E7%BB%93%E6%9E%84%E4%BD%93%EF%BC%8C%E5%85%85%E5%BD%93%E8%BF%90%E7%AE%97%E5%AF%B9%E8%B1%A1%E6%A0%88%7B%20%20%09float%20data%5BMAXLEN%5D%3B%09int%20top%3B%0A%7DObjectStack%3B%0A//%20%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%BD%AC%E5%90%8E%E7%BC%80%EF%BC%8C%E9%9C%80%E8%A6%81%E7%94%A8%E5%88%B0%E8%BF%90%E7%AE%97%E7%AC%A6%E5%8F%B7%E6%A0%88%0Avoid%20trans%28char%20infix%5B%5D%2C%20char%20suffix%5B%5D%29%20%20%20%20%20%20%20%20%20%20%7B%20%20%09OperatorStack%20opStack%3B%09char%20ch%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%09int%20i%3D0%2C%20j%3D0%3B%09//%20%E5%88%9D%E5%A7%8B%E5%8C%96%E8%BF%90%E7%AE%97%E7%AC%A6%E5%8F%B7%E6%A0%88opStack%09opStack.top%3D-1%3B%0A%09//%20%E5%8F%96%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%0A%09ch%3Dinfix%5Bi%2B%2B%5D%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09while%28ch%21%3D%27%5C0%27%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09%7B%09%09switch%28ch%29%09%09%7B%0A%09%09case%20%27%28%27%3A%09%09%09//%20%E9%81%87%E5%88%B0%27%28%27%EF%BC%8C%E5%88%99%E7%9B%B4%E6%8E%A5%E5%85%A5%E6%A0%88%09%09%09opStack.top%2B%2B%3B%09%09%09%09%09%09%09opStack.data%5BopStack.top%5D%3Dch%3B%09%09%09%09%09break%3B%0A%09%09case%20%27%29%27%3A%09%09%09//%20%E9%81%87%E5%88%B0%27%29%27%EF%BC%8C%E4%B8%80%E7%9B%B4%E5%87%BA%E6%A0%88%E5%B9%B6%E8%BE%93%E5%87%BA%EF%BC%8C%E7%9B%B4%E5%88%B0%27%28%27%E5%87%BA%E6%A0%88%09%09%09while%28opStack.data%5BopStack.top%5D%21%3D%27%28%27%29%20%20%20%09%09%09%7B%20%09%09%09%09suffix%5Bj%2B%2B%5D%3DopStack.data%5BopStack.top--%5D%3B%09%09%09%7D%0A%09%09%09opStack.top--%3B%09//%20%27%28%27%E5%87%BA%E6%A0%88%EF%BC%8C%E4%BD%86%E4%B8%8D%E8%BE%93%E5%87%BA%09%09%09break%3B%09%09case%20%27%2B%27%3A%0A%09%09case%20%27-%27%3A%09%09%09//%20%E9%81%87%E5%88%B0%27%2B%27%E6%88%96%E8%80%85%27-%27%EF%BC%8C%E5%88%99%E4%B8%80%E7%9B%B4%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B4%E5%88%B0%E6%A0%88%E4%B8%BA%E7%A9%BA%E6%88%96%E8%80%85%E6%A0%88%E9%A1%B6%E4%B8%BA%27%28%27%0A%09%09%09%20%20while%28opStack.top%21%3D-1%20%26%26%20opStack.data%5BopStack.top%5D%21%3D%27%28%27%29%09%09%09%09%20%20%7B%20%20%09%09%09%09%09suffix%5Bj%2B%2B%5D%3DopStack.data%5BopStack.top--%5D%3B%20%20%09%09%09%20%20%7D%0A%09%09%09%20%20opStack.top%2B%2B%3B%09%09//%20%E7%84%B6%E5%90%8Ech%E5%86%8D%E5%85%A5%E6%A0%88%09%09%09%20%20opStack.data%5BopStack.top%5D%3Dch%3B%09%09%09%20%20break%3B%09%09case%20%27%2A%27%3A%0A%09%09case%20%27/%27%3A%09%09%09//%20%E9%81%87%E5%88%B0%27%2A%27%E6%88%96%E8%80%85%27/%27%EF%BC%8C%E5%88%99%E4%B8%80%E7%9B%B4%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B4%E5%88%B0%E6%A0%88%E9%A1%B6%E4%B8%8D%E4%B8%BA%27%2A%27%E6%88%96%27/%27%E6%97%B6%0A%09%09%09while%28opStack.data%5BopStack.top%5D%3D%3D%27/%27%20%7C%7C%20opStack.data%5BopStack.top%5D%3D%3D%27%2A%27%29%09%09%09%7B%09%09%09%09suffix%5Bj%2B%2B%5D%3DopStack.data%5BopStack.top--%5D%3B%20%09%09%09%7D%0A%09%09%09opStack.top%2B%2B%3B%09%09//%20%E7%84%B6%E5%90%8Ech%E5%86%8D%E5%85%A5%E6%A0%88%09%09%09opStack.data%5BopStack.top%5D%3Dch%3B%09%09%09break%3B%09%09case%20%27%20%27%3A%09%09%09//%20%E9%81%87%E5%88%B0%E7%A9%BA%E6%A0%BC%EF%BC%8C%E5%88%99%E7%9B%B4%E6%8E%A5%E8%B7%B3%E8%BF%87%EF%BC%8Cch%E5%8F%96%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%AD%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%09%09%09break%3B%09%0A%09%09case%20%270%27%3A%09%09case%20%271%27%3A%09%09case%20%272%27%3A%09%09case%20%273%27%3A%09%09case%20%274%27%3A%09%09case%20%275%27%3A%09%09case%20%276%27%3A%09%09case%20%277%27%3A%09%09case%20%278%27%3A%09%09case%20%279%27%3A%09//%20%E9%81%87%E5%88%B0%E6%95%B0%E5%AD%97%EF%BC%8C%E5%88%99%E7%9B%B4%E6%8E%A5%E8%BE%93%E5%87%BA%E5%88%B0%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%09%09%09suffix%5Bj%2B%2B%5D%3Dch%3B%0A%09%09%7D%09%09%0A%09%09//%20%E5%86%8D%E8%AF%BB%E5%85%A5infix%5B%5D%E4%B8%AD%E7%9A%84%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%E5%88%B0ch%09%09ch%3Dinfix%5Bi%2B%2B%5D%3B%09%09%09%09%7D%09while%28opStack.top%21%3D-1%29%09%09%09//%20%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%AD%E6%89%80%E6%9C%89%E5%AD%97%E7%AC%A6%E5%A4%84%E7%90%86%E5%AE%8C%EF%BC%8C%E5%BD%93%E6%A0%88%E4%B8%8D%E4%B8%BA%E7%A9%BA%E6%97%B6%09%7B%20%0A%09%09suffix%5Bj%2B%2B%5D%3DopStack.data%5BopStack.top--%5D%3B%09//%20%E5%B0%86%E6%A0%88%E4%B8%AD%E5%89%A9%E4%BD%99%E7%9A%84%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BE%9D%E6%AC%A1%E5%87%BA%E6%A0%88%E5%88%B0suffix%5B%5D%E4%B8%AD%09%7D%09suffix%5Bj%5D%3D%27%5C0%27%3B%09%09%09%09//%20%E6%9C%80%E5%90%8Esuffix%5B%5D%E4%BB%A5%27%5C0%27%E7%BB%93%E6%9D%9F%7D%0A/%2A%20%E6%A0%B9%E6%8D%AE%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC%EF%BC%8C%E9%9C%80%E8%A6%81%E7%94%A8%E5%88%B0%E8%BF%90%E7%AE%97%E5%AF%B9%E8%B1%A1%E6%A0%88%20%2A/float%20compute%28char%20suffix%5B%5D%29%20%20%7B%20%20%09ObjectStack%20objStack%3B%09char%20ch%3B%0A%09int%20j%3D0%3B%0A%09//%20%E5%88%9D%E5%A7%8B%E5%8C%96%E8%BF%90%E7%AE%97%E5%AF%B9%E8%B1%A1%E6%A0%88%0A%09objStack.top%3D-1%3B%0A%09//%20%E5%8F%96%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%AD%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%09ch%3Dsuffix%5Bj%2B%2B%5D%3B%09//%20%E5%BC%80%E5%A7%8B%E6%B1%82%E5%80%BC%0A%09while%28ch%21%3D%27%5C0%27%29%20%09%7B%20%0A%09%09if%28ch%3D%3D%27%2B%27%29%09%09%09//%20%E5%A6%82%E6%9E%9C%E6%98%AF%E5%8A%A0%E5%8F%B7%EF%BC%8C%E5%B0%862%E4%B8%AA%E6%95%B0%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B8%E5%8A%A0%E7%9A%84%E7%BB%93%E6%9E%9C%E5%86%8D%E8%BF%9B%E6%A0%88%09%09%7B%0A%09%09%09objStack.data%5BobjStack.top-1%5D%3DobjStack.data%5BobjStack.top-1%5D%2BobjStack.data%5BobjStack.top%5D%3B%09%09%09objStack.top--%3B%09%09%7D%0A%09%09else%20if%28ch%3D%3D%27-%27%29%20%20%20//%20%E5%A6%82%E6%9E%9C%E6%98%AF%E5%87%8F%E5%8F%B7%EF%BC%8C%E5%B0%862%E4%B8%AA%E6%95%B0%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B8%E5%87%8F%E7%9A%84%E7%BB%93%E6%9E%9C%E5%86%8D%E8%BF%9B%E6%A0%88%09%09%7B%0A%09%09%09objStack.data%5BobjStack.top-1%5D%3DobjStack.data%5BobjStack.top-1%5D-objStack.data%5BobjStack.top%5D%3B%09%09%09objStack.top--%3B%09%09%7D%0A%09%09else%20if%28ch%3D%3D%27%2A%27%29%20%20%20//%E5%A6%82%E6%9E%9C%E6%98%AF%E4%B9%98%E5%8F%B7%EF%BC%8C%E5%B0%862%E4%B8%AA%E6%95%B0%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B8%E4%B9%98%E7%9A%84%E7%BB%93%E6%9E%9C%E5%86%8D%E8%BF%9B%E6%A0%88%09%09%7B%0A%09%09%09objStack.data%5BobjStack.top-1%5D%3DobjStack.data%5BobjStack.top-1%5D%2AobjStack.data%5BobjStack.top%5D%3B%09%09%09objStack.top--%3B%09%09%7D%0A%09%09else%20if%28ch%3D%3D%27/%27%29%20%20%20//%E5%A6%82%E6%9E%9C%E6%98%AF%E9%99%A4%E5%8F%B7%EF%BC%8C%E5%B0%862%E4%B8%AA%E6%95%B0%E5%87%BA%E6%A0%88%EF%BC%8C%E7%9B%B8%E9%99%A4%E7%9A%84%E7%BB%93%E6%9E%9C%E5%86%8D%E8%BF%9B%E6%A0%88%09%09%7B%09%09%09if%28objStack.data%5BobjStack.top%5D%21%3D0%29%09%09%09%7B%20%20%20%0A%09%09%09%09objStack.data%5BobjStack.top-1%5D%3DobjStack.data%5BobjStack.top-1%5D/objStack.data%5BobjStack.top%5D%3B%09%09%09%09objStack.top--%3B%09%09%09%7D%0A%09%09%09else%0A%09%09%09%09printf%28%22%5Cn%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%AD%E6%9C%89%E9%99%A4%E6%95%B0%E4%B8%BA%E9%9B%B6%EF%BC%8C%E8%AE%A1%E7%AE%97%E6%97%A0%E6%95%88%21%5Cn%20%22%29%3B%09%09%7D%09%09else%20if%28ch%3E%3D%270%27%20%26%26%20ch%3C%3D%279%27%29%09%09%7B%09%09%09objStack.top%2B%2B%3B%0A%09%09%09objStack.data%5BobjStack.top%5D%3D%28float%29%28ch-%270%27%29%3B%20%20//%20%E6%9C%80%E5%90%8E%E5%B0%86%E7%AE%97%E5%A5%BD%E7%9A%84num%E5%8E%8B%E5%85%A5%E6%A0%88%09%09%7D%09%09//%20%E8%AF%BB%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%AD%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%09%09ch%3Dsuffix%5Bj%2B%2B%5D%3B%20%20%09%7D%0A%09return%20objStack.data%5BobjStack.top%5D%3B%20%20%7Dvoid%20main%28%29%20%20%20%20%7B%20%20%20%20%0A%09char%20infix%5BMAXLEN%5D%2C%20suffix%5BMAXLEN%5D%3B%0A%09printf%28%22%5Cn%E8%AF%B7%E8%BE%93%E5%85%A5%E4%B8%80%E4%B8%AA%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%EF%BC%8C%E5%85%B6%E4%B8%AD%E5%8F%AA%E8%83%BD%E5%90%AB%E6%9C%89%2B%2C-%2C%2A%2C/%2C%28%2C%29%E7%AD%89%E8%BF%90%E7%AE%97%E7%AC%A6%EF%BC%9A%22%29%3B%09gets%28infix%29%3B%20%09%0A%09trans%28infix%2C%20suffix%29%3B%20%20%20%20%20%20%20%20%20%09%09printf%28%22%5Cn%E8%BD%AC%E6%8D%A2%E4%B9%8B%E5%90%8E%E7%9A%84%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%BA%EF%BC%9A%25s%5Cn%22%2C%20suffix%29%3B%0A%09printf%28%22%5Cn%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%BE%97%E7%9A%84%E5%80%BC%E4%B8%BA%EF%BC%9A%25.3f%5Cn%5Cn%22%2C%20compute%28suffix%29%29%3B%7D%0A