求树的应用实现树与二叉树的转换的实现
#include #include #define M 100#define Null 0typedef struct node { int data; struct node *lchild,*rchild;}bitree;bitree *que[M];int front=0,rear=0;bitree *create(){ bitree * t; int x; scanf("%d",&x); if (x==0) t=Null; else { t= (bitree *) malloc (sizeof(bitree)); t->data=x; t->lchild=create(); ...全部
#include #include #define M 100#define Null 0typedef struct node { int data; struct node *lchild,*rchild;}bitree;bitree *que[M];int front=0,rear=0;bitree *create(){ bitree * t; int x; scanf("%d",&x); if (x==0) t=Null; else { t= (bitree *) malloc (sizeof(bitree)); t->data=x; t->lchild=create(); t->rchild=create(); }return t;}void prvorder(bitree * t){ //前序遍历 if (t!=Null){ printf("M",t->data); prvorder(t->lchild); prvorder(t->rchild); }}void PreOrderUnrec(bitree *t) //先序遍历非递归算法;{ bitree *p = t,*Stack[M]; int top = -1; while (p != Null || top != -1) { while (p!=Null) //遍历左子树; { printf("M",p->data); Stack[ top] = p; p=p->lchild; } if (top != -1) //下次while内循环中实现右子树遍历; { p = Stack[top--]; p=p->rchild; } } }void inorder(bitree * t){ //中序遍历 if (t!=Null){ inorder(t->lchild); printf("M",t->data); inorder(t->rchild); }}void InOrderUnrec(bitree *t) //中序遍历非递归算法;{ bitree *p = t,*Stack[M]; int top = -1; while (p != Null || top != -1) { while (p!=Null) //遍历左子树; { Stack[ top] = p; p=p->lchild; } if (top != -1) //下次while内循环中实现右子树遍历; { p = Stack[top--]; printf("M",p->data); p=p->rchild; } } }void postorder(bitree * t){ //后序遍历 if (t!=Null){ postorder(t->lchild); postorder(t->rchild); printf("M",t->data); }}void PostOrderUnrec(bitree *t) //后序遍历非递归算法;{ bitree *p = t,*Stack[M]; int top = -1; char flag[M];//标识,若为'R'则说明左右孩子均已遍历,防止再次走过,形成死循环; while(p != Null || top != -1) { while(p != Null) { Stack[ top] = p; flag[top] = 'L'; p = p->lchild; } while(top != -1 && flag[top] == 'R') { printf("M",Stack[top--]->data); //flag='R',在此退栈; } if(top != -1) {flag[top] = 'R'; p = Stack[top]->rchild;} }}void enqueue(bitree *t){ if (front!=((rear 1)%M)) { rear=(rear 1)%M; que[rear]=t; }}bitree *delqueue(){ if(front==rear) return Null; front=(front 1)%M; return que[front];}void levorder(bitree *t){ bitree *p; if(t!=Null){ enqueue(t); while (front!=rear) { p=delqueue(); printf("M",p->data); if (p->lchild!=Null) enqueue(p->lchild); if (p->rchild!=Null) enqueue(p->rchild); } }}void LevelOrderUnrec(bitree *t) //层次遍历非递归算法;{ bitree *p,*Queue[M]; //定义队列,存储树结点指针; int front,rear; //定义队首和队尾指针; front = rear = 0; //初始化置0,空队列; if(t != NULL) { rear = (rear 1)%M; //队尾指针后移; Queue[rear] = t; //树根结点入队; } while (front != rear) //队列非空时; { front = (front 1)%M; //队首指针后移; p = Queue[front]; //删除队首结点; printf("%c ",p->data); //输出队首结点的值; if(p->lchild != NULL) //若存在左孩子,则左孩子指针入队; { rear = (rear 1)%M; Queue[rear] = p->lchild; } if(p->rchild != NULL) //若存在右孩子,则右孩子指针入队; { rear = (rear 1)%M; Queue[rear] = p->rchild; } }}int main(){ bitree *root; printf("
"); root=create(); inorder(root); printf("
"); InOrderUnrec(root); printf("
"); prvorder(root); printf("
"); PreOrderUnrec(root); printf("
"); postorder(root); printf("
"); PostOrderUnrec(root); printf("
"); levorder(root); return 0;} 下面是马踏棋盘(另外给你的·):一、实验目的1、加深对图的理解,培养解决实际问题的编程能力。
2、根据数据对象的特性,学会数据组织的方法,把现实世界中的实际问题在计算机内部表示出来。3、培养基本的、良好的程序设计技能。二、实验内容,1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。
2) 在1)的基础上给出从该位置出发的所有遍历路径 三、使用仪器,材料电脑,windowx XP Visual Studio C 6。0 四、实验方法与步骤1、设计思想:整个棋盘可表示为一个M×N的二维数组。
假若马目前在位置(i,j)则马下一步可移动的位置0、1、……、7可分别表示为(i-2,j 1),(i-1,j 2),(i 1,j 2),(i 2,j 1),(i 2,j-1),(i 1,j-2), (i-1,j-2), (i-2,j-1)。
当然,这些位置一定在棋盘边界以内(保证下一步移动位置坐标(i,j),有0#include "conio。h"using namespace std;#define edgetype int#define vextype int#define MAX 8typedef struct node{ int vextex;//序号 struct node *next;}edgenode; typedef struct { int vextex; int x,y; edgenode *link;}vexnode; const int px[8]={1,2,2,1,-1,-2,-2,-1};const int py[8]={2,1,-1,-2,-2,-1,1,2}; const int L=8,H=8; vexnode ga[L*H]; //图int visited[L*H]={0}; //全局地图标志是否走过 typedef struct /*顺序栈的结构体类型定义*/ { int stack[L*H]; int top; }seqstack; seqstack s; //全局栈 void setnull(seqstack *s) {s->top=-1;} /*置空栈-由于c语言的数组下标是从0开始的,所以置空栈操作时将栈顶指针放在下标为0之前,即-1处。
*/ int empty(seqstack *s) /*判断当前栈是否为空栈*/ { if(s->toptop>L*H-1) { printf("stack overflow!
"); /*发生上溢*/ return 0; } else { s->stack[ s->top] = x; /*栈顶指针上移,数据元素入栈*/ return 1; } } int pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ { if(s->toptop--; return(s->stack[s->top 1]); }/*由于return语句的特点,必须先使top减1,然后再执行return语句。
而此时栈顶元素的表示应该为s->top 1。*/ } void init(){ int n; for (int i=0;i=L||ty>=H) continue; //出界了 else //采用前插法 { p=(edgenode*)malloc(sizeof(edgenode)); p->vextex=ty*L tx; p->next=ga[i]。
link; ga[i]。link=p; // printf("%d ",ga[i]。link->vextex); } } }}void show() //打印邻接表{ int i; printf("
"); for (i=0;i",ga[i]。
vextex); edgenode *p; p=(edgenode*)malloc(sizeof(edgenode)); p=ga[i]。link; while (p!=NULL) { printf("%d ",p->vextex); p=p->next; } printf("
"); }} void showanswer() //打印路径矩形图{ int rank[L*H]; int tag=s。
top; for (int i=L*H-1;i>=0;i--) { rank[s。stack[tag--]]=i; //rank[pop(&s)]=i; } for (i=0;i",n); push(&s,ga[n]。
vextex); //结点入栈 p=ga[n]。link; visited[n]=1; while (p!=NULL) { if (!visited[p->vextex]) { //printf("%d,",p->vextex); //if(HFS(p->vextex)) return 1; HFS(p->vextex); } p=p->next; } if (s。
top==L*H-1) //找到路径 { printf("answer %d:
",sum ); //统计有一点出发的路径个数 showanswer(); printf("
"); //return 1; } visited[s。
stack[s。top]]=0; pop(&s); if (empty(&s)) //没有 { return 0; } return 0; } int main(){ int n; for (n=0;n 3、结果分析:程序由于算法的不足,只能计算出从第0格子出发的路径,其他格子出发的路径无法算出来…… 六、总结:通过本次综合实验,我加强了对以往学习的知识的巩固,如栈、链表等。加深了对图的理解,培养解决实际问题的编程能力。
根据数据对象的特性,学会了数据组织的方法,把现实世界中的实际问题在计算机内部表示出来。培养了基本的、良好的程序设计技能。同时体会到算法的高效性永远是程序设计的难点和重点,只有高效的算法才能更好更快的得到满意的答案。
收起