搜索到
58
篇与
的结果
-
图的邻接矩阵表示 图的邻接矩阵表示#include <stdio.h> // 8.3.1 图的邻接矩阵表示 #define INFINITY 10000 // 定义无穷大 #define V_MAX 100 // 顶点最大数 typedef char vertexType; // 顶点数据类型 typedef struct graph // 图的邻接矩阵表示 { int n, e; // 顶点和边总数 vertexType vertex[V_MAX]; // 顶点集合 int edge[V_MAX][V_MAX]; // 邻接矩阵 }graph; // 1. 创建邻接矩阵表示的图 void create(graph *g, int c) { int i,j,k,w; scanf("%d%d",&g->n,&g->e); for (i = 0; i < g->n; ++i) scanf("%1s",&g->vertex[i]); for (i = 0; i < g->n; ++i) // 初始化邻接矩阵 { for (j = 0; j < g->n; ++j) { if(i == j) g->edge[i][j] = 0; else g->edge[i][j] = INFINITY; } } for (k = 0; k < g->e; ++k) { scanf("%d%d%d",&i,&j,&w); g->edge[i][j] = w; if(c == 0) g->edge[j][i] = w; // 无向图 } } // 2. 输出邻接矩阵表示的图 void print(graph g) { if(g.n > 0) { for (int i = 0; i < g.n; ++i) { for (int j = 0; j < g.n; ++j) printf("%d\t",g.edge[i][j]); printf("\n"); } } printf("该图有%d个顶点，%d条边",g.n,g.e); } int main() { graph g; printf("请依次输入图的定点数、边数，顶点信息和边信息\n"); create(&g,0); // 0表示无向图，1表示有向图 printf("该图的邻接矩阵表示如下：\n"); print(g); return 0; } -
树形结构的其他运算 树形结构的其他运算#include <stdio.h> #include <stdlib.h> // 7.8 习题7 typedef char dataType; typedef struct treeNode { dataType data; // 数据域 struct treeNode *lChild,*rChild; // 左、右孩子指针域 }node,*binaryTree; // 顺序栈 #define MAX_SIZE 100 typedef struct stack { node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针 int top; // 栈顶指针 }seqStack; // 1.初始化栈 void init(seqStack *stack) { stack->top = 0; } // 2. 判断栈是否为空 int empty(seqStack stack) { return stack.top == 0; } // 3. 元素入栈 void push(seqStack *stack, node* n) { if(stack->top == MAX_SIZE-1) { printf("栈已满，无法入栈！\n"); exit(1); } stack->data[stack->top++] = n; } // 4. 读取栈顶元素 node *get(seqStack stack) { return stack.data[stack.top-1]; } // 5. 元素出栈 node* pop(seqStack *stack) { if(empty(*stack)) { printf("栈已空，无法出栈！\n"); exit(1); } return stack->data[--stack->top]; } // 6. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (node *) malloc(sizeof(node)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 7.1.13.1 递归方法求二叉树的叶子结点个数 int numLeaf(binaryTree tree) { if(!tree) return 0; // 空树 if(!tree->lChild && !tree->rChild) // 左右孩子都不存在 return 1; return numLeaf(tree->lChild) + numLeaf(tree->rChild); } // 7.1.13.2 非递归方法求二叉树的叶子结点个数 int numLeaf1(binaryTree tree) { int num = 0; seqStack stack; stack.top = 0; // 初始化栈 while (tree || !empty(stack)) // 树或栈非空 { if(tree) { if(!tree->lChild && !tree->rChild) num++; push(&stack,tree); // 进栈 tree = tree->lChild; // 一路向左 } else { tree = pop(&stack); // 出栈向右子树 tree = tree->rChild; } } return num; } // 7.1.14 求给定二叉树中序遍历序列的最后一个结点 node * inOrderLast(binaryTree tree) { while (tree && tree->rChild) tree = tree->rChild; return tree; } // 7.1.15 返回二叉树任意两结点p、q的共同祖先 node *seekAncestor(binaryTree t, node *p, node *q) { seqStack s, s1; // 声明顺序栈 init(&s), init(&s1); // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !empty(s)) // 树或栈非空 { if (t) // 一路向左直到左孩子为空 { push(&s,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = get(s); // 读取栈顶元素 if(t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&s); // 出栈 if(t == p || t == q) { if(empty(s1)) // 栈s复制给栈s1 for (int i = s.top-1; i >= 0; i--) push(&s1,s.data[i]); else break; // p、q的祖先都已找到，退出循环 } r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } while (!empty(s)) // 寻找共同祖先 { t = pop(&s); for (int j = s1.top-1; j >= 0; j--) if(t == s1.data[j]) return t; } return NULL; } int main() { binaryTree tree; printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## printf("该二叉树叶子结点有%d个\n",numLeaf(tree)); printf("该二叉树叶子结点有%d个\n", numLeaf1(tree)); node *n = inOrderLast(tree); if(n) printf("该二叉树中序遍历序列的最后一个结点是%c",n->data); else printf("该二叉树为空！"); return 0; }
-
中序穿线二叉树的实现 中序穿线二叉树的实现#include <stdio.h> #include <stdlib.h> // 7.6.3 中序穿线二叉树(线索二叉树)的实现 typedef char dataType; // 线索二叉树的结点结构 typedef struct node { dataType data; // 数据域 struct node *lChild, *rChild; // 左、右孩子指针 int lTag, rTag; // 左、右指针是否是线索的标志 }treeNode, *binaryTree; // 1. 按前序遍历顺序建立二叉树 treeNode *createTree() { treeNode *tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (treeNode *) malloc(sizeof(treeNode)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 2. 对二叉树中序线索化 treeNode *pre = NULL; // 初始化前驱结点指针 void inThread(binaryTree tree) { if(tree) { inThread(tree->lChild); // 左子树线索化 tree->lTag = tree->lChild ? 0:1; tree->rTag = tree->rChild ? 0:1; if(pre) // 对当前结点及前驱结点线索化 { if(tree->lTag) tree->lChild = pre; if(pre->rTag) pre->rChild = tree; } pre = tree; inThread(tree->rChild); // 右子树线索化 } } // 3. 建立中序线索二叉树 void createInThreadTree(binaryTree *tree) { *tree = createTree(); inThread(*tree); } // 4. 寻找中序线索二叉树中p结点的后继结点 treeNode *inNextNode(binaryTree p) { if(p->rTag == 1) return p->rChild; p = p->rChild; while (p->lTag == 0) p = p->lChild; return p; } // 5. 中序线索二叉树的中序遍历 void inOrder(binaryTree tree) { if(tree) { while (tree->lTag == 0) tree = tree->lChild; while (tree) { printf("%c ",tree->data); tree = inNextNode(tree); } } } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); createInThreadTree(&tree); //建立中序线索二叉树 ABD#E##FG###C## printf("中序线索二叉树的中序遍历\n"); inOrder(tree); return 0; }
-
二叉树其他运算的实现 二叉树其他运算的实现#include <stdio.h> #include <stdlib.h> // 7.5 二叉树其他运算的实现 typedef char dataType; typedef struct node { dataType data; // 数据域 struct node *lChild,*rChild; // 左、右孩子指针域 }treeNode,*binaryTree; // 1. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (treeNode *) malloc(sizeof(treeNode)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 2.二叉树的查找 treeNode *locate(binaryTree tree, dataType x) { treeNode *p; if(!tree) return NULL; // 如果是空树 if(tree->data == x) return tree; // 根结点符合条件 p = locate(tree->lChild,x); // 寻找左子树 if(p) return p; return locate(tree->rChild,x); // 寻找右子树 } // 3. 统计二叉树的结点个数 int numOfNode(binaryTree tree) { if(!tree) return 0; return numOfNode(tree->lChild) + numOfNode(tree->rChild) +1; } // 4. 判断两棵二叉树是否相等 int isEqual(binaryTree t1, binaryTree t2) { int t = 0; if(!t1 && !t2) t=1; else { if(t1->data == t2->data) { if(isEqual(t1->lChild,t2->lChild)) { t = isEqual(t1->rChild,t2->rChild); } } } return t; } // 5. 递归方式求二叉树的高度或深度 int depth(binaryTree tree) { int lh,rh; if(!tree) return 0; lh = depth(tree->lChild); rh = depth(tree->rChild); return lh>rh ? lh+1 :rh+1; } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## treeNode *node; char x = 'A'; node = locate(tree,x); if(node) printf("结点%c存在\n",node->data); int num = numOfNode(tree); printf("该二叉树共有%d个结点\n",num); int h = depth(tree); printf("该二叉树高度或深度是%d",h); return 0; }
-
二叉树的递归遍历 二叉树的递归遍历#include <stdio.h> #include <stdlib.h> // 7.4.2 二叉树的递归遍历 typedef char dataType; // 结点值的类型 typedef struct treeNode { dataType data; // 结点数据域 struct treeNode *lChild, *rChild; // 左、右孩子指针 }node, *binaryTree; // 1.按照前序遍历的顺序建立给定的二叉树 binaryTree createTree() { char c; binaryTree t; if((c = getchar()) == '#') t = NULL; else { t = (node *) malloc(sizeof(node)); t->data = c; t->lChild = createTree(); t->rChild = createTree(); } return t; } // 2. 前序遍历 void preOrder(binaryTree t) { if(t) { printf("%c ",t->data); preOrder(t->lChild); preOrder(t->rChild); } } // 3. 中序遍历 void inOrder(binaryTree t) { if(t) { inOrder(t->lChild); printf("%c ",t->data); inOrder(t->rChild); } } // 4. 后序遍历 void postOrder(binaryTree t) { if(t) { postOrder(t->lChild); postOrder(t->rChild); printf("%c ",t->data); } } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## printf("前序遍历\n"); preOrder(tree); printf("\n中序遍历\n"); inOrder(tree); printf("\n后序遍历\n"); postOrder(tree); return 0; }
