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

/* 二叉树的层次遍历*/#include#include#include #include#define TREEMAX 50typedef struct nodechar data;struct node *lchild;struct node *rchild; Node;/ 递归创建二叉树Node *CreateBT()Node *t;char x;scanf(“%c“, fflush(stdin);if(x=#)t=NULL;elset=new Node;t-data=x;printf(“tt请输入%c 结点的左子结点: “,t-data);t-lchild=CreateBT();printf(“tt请输入%c 结点的右子结点: “,t-data);t-rchild=CreateBT();return t;/ 递归先序遍历二叉树void Preorder(Node *T)if(T)printf(“%3c“,T-data);Preorder(T-lchild);Preorder(T-rchild);/ 递归中序遍历二叉树void Inorder(Node *T)if(T)Inorder(T-lchild);printf(“%3c“,T-data);Inorder(T-rchild);/ 递归后序遍历二叉树void Postorder(Node *T)if(T)Postorder(T-lchild);Postorder(T-rchild);printf(“%3c“,T-data);/ 非递归先序遍历二叉树void noRecursivePreorder(Node *T)Node *StTREEMAX,*p;int top=-1;if(T!=NULL)top+;Sttop=T;while(top-1)p=Sttop;top-;printf(“%c“,p-data);if(p-rchild!=NULL)top+;Sttop=p-rchild;if(p-lchild!=NULL)top+;Sttop=p-lchild;printf(“n“);/ 非递归中序遍历二叉树void noRecursiveInorder(Node *T)Node *StTREEMAX,*p;int top=-1;if(T!=NULL)p=T;while(top-1|p!=NULL)while(p!=NULL)top+;Sttop=p;p=p-lchild;if(top-1)p=Sttop;top-;printf(“%c“,p-data);p=p-rchild;printf(“n“);/ 非递归后序遍历二叉树void noRecursivePostorder(Node *T)Node *StTREEMAX,*p;int flag,top=-1;if(T!=NULL)dowhile(T!=NULL)top+;Sttop=T;T=T-lchild;p=NULL;flag=1;while(top!=-1if(T-rchild=p)printf(“%c“,T-data);top-;p=T;elseT=T-rchild;flag=0;while(top!=-1);printf(“n“);/ 层次遍历二叉树，用 queue数组充当顺序队列void LevelOrder(Node *T)Node *queueTREEMAX, *p;int pre=-1, rear=-1;/ 树根结点先进队queue+pre=T;/ 当队列不为空时，出队一个结点的同时将其左右孩子进队while(pre-rear+TREEMAX)%TREEMAX!=0)p=queue+rear; / 出队一个结点并输出printf(“%3c“, p-data);if(p-lchild!=NULL) / 左孩子存在则进队queue+pre=p-lchild;if(p-rchild!=NULL) / 右孩子存在则进队queue+pre=p-rchild;void list()printf(“n“);printf(“ntt 二叉链表“);printf(“ntt*“);printf(“ntt* 1.建立二叉树 *“);printf(“ntt* 2.递归前序遍历 *“);printf(“ntt* 3.递归中序遍历 *“);printf(“ntt* 4.递归后序遍历 *“);printf(“ntt* 5.非递归前序遍历 *“);printf(“ntt* 6.非递归中序遍历 *“);printf(“ntt* 7.非递归后序遍历 *“);printf(“ntt* 8.层次遍历 *“);printf(“ntt* 9.清屏 *“);printf(“ntt* 0.退出程序 *“);printf(“ntt*“);printf(“ntt请输入菜单项：“);void main()Node *T=NULL;char a,b;b=m;while(b=m|b=M)list();scanf(“%c“, fflush(stdin);switch(a)case1:printf(“ntt请按先序序列输入二叉树的结点（输入#表示结点为空）：n“);printf(“ntt请输入根结点：“);T=CreateBT();printf(“ntt二叉树成功建立-n“);break;case2:printf(“ntt该二叉树递归前序遍历为：“);Preorder(T);break;case3:printf(“ntt该二叉树递归中序遍历为：“);Inorder(T);break;case4:printf(“ntt该二叉树递归后序遍历为：“);Postorder(T);break;case5:printf(“ntt该二叉树非递归前序遍历为：“);noRecursivePreorder(T);break;case6:printf(“ntt该二叉树非递归中序遍历为：“);noRecursiveInorder(T);break;case7:printf(“ntt该二叉树非递归后序遍历为：“);noRecursivePostorder(T);break;case8:printf(“ntt该二叉树的层次遍历序列为：“);LevelOrder(T);break;case9:system(“cls“);break;case0:b=n;break;default:printf(“ntt*对不起，输入有误！*“);/* 多项式运算【链式结构】*/#include “stdio.h“#include “stdlib.h“typedef struct _node float coe; int index;struct _node *next; Node, *NodePtr;/ 整理多项式链表，将链表中的结点根据各项指数进行升序排列void sortPoly(NodePtr list)NodePtr p=list-next, q=list, r, ptr;/ 让 p指向链表的第二个数据结点，/ p为空则说明链表为空，不用整理了。if(p)p=p-next;else return;/ 先从链表的第一个数据结点后断开链表ptr=q-next;ptr-next=NULL;/ 再将链表的第二个直至最后一个数据结点依次插入链表while(p)q=list;ptr=q-next;while(ptr-index index)q=ptr;ptr=ptr-next;if(ptr=NULL)break;if(ptr=NULL)q-next=p;ptr=p;p=p-next;ptr-next=NULL;else if(ptr-index = p-index)ptr-coe += p-coe;r=p-next;free(p);p=r;else if(ptr-index p-index)r=p-next;p-next=ptr;q-next=p;p=r;/* 创建一个多项式链表，返回创建链表的头指针 */NodePtr createPoly() int i=1, index;float coe;NodePtr resultPtr, q;/ 开辟头结点空间resultPtr = (NodePtr)malloc(sizeof(Node);resultPtr-next=NULL;printf(“请输入多项式第%d 项的系数和指数(输入 0 0时结束)：“, i+);scanf(“%f%d“, while(1)if(index else if(index=0 else / 开辟新结点空间q=(NodePtr)malloc(sizeof(Node);q-coe=coe;q-index=index;q-next=NULL;/ 将新结点插入多项式链表q-next=resultPtr-next;resultPtr-next=q;/ 输入下一项printf(“请输入多项式第%d 项的系数和指数(输入 0 0时结束)：“, i+);scanf(“%f%d“, / 将输入的多项式链表整理后返回sortPoly(resultPtr);return resultPtr;/ 判断多项式链表是否已输入或是否为空int isEmpty(NodePtr list1, NodePtr list2)if(list1=NULL)return 1;else if(list2=NULL)return 2;else if(list1-next=NULL)return -1;else if(list2-next=NULL)return -2;elsereturn 0;/ 两个多项式相加NodePtr addPoly(NodePtr list1, NodePtr list2)NodePtr resultPtr, p=list1-next, q=list2-next, r;if(isEmpty(list1, list2)=1)printf(“多项式链表 L1不存在，请先选择菜单 1输入多项式 L1！n“);return NULL;else if(isEmpty(list1, list2)=2)printf(“多项式链表 L2不存在，请先选择菜单 2输入多项式 L2！n“);return NULL;/ 创建结果多项式的头结点resultPtr=(NodePtr)malloc(sizeof(Node);r