搜索到
41
篇与
的结果
-
树的遍历(指针方式孩子表示法) 树的遍历(指针方式孩子表示法)#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 typedef char dadaType; // 6.4.1 树的遍历(指针方式孩子表示法) #define m 3 //树的度 typedef struct node { dadaType data; struct node *child[m]; // 指向孩子的指针数组 }node, *tree; typedef struct queue // 用于层序遍历的队列 { node data[MAX_SIZE]; int front, rear; // 对头指针和队尾指针 }queue; // 1. 初始化循环队列 void init(queue *q) { q->front = q->rear = 0; } // 2. 判断队列是否为空 int empty(queue q) { return q.rear == q.front; } // 3. 入队 void insert(queue *q, node x) { if((q->rear + 1)%MAX_SIZE == q->front) { printf("队列已满，无法入队！\n"); exit(1); } q->data[q->rear] = x; q->rear = (q->rear + 1)%MAX_SIZE; } // 4. 队列出队 node del(queue *q) { int front = q->front; if(q->rear == front) { printf("队列为空，无法出队！\n"); exit(1); } q->front = (front + 1)%MAX_SIZE; return q->data[front]; } // 5. 树的前序遍历 void preOrder(tree p) { if(p) { printf("%c ",p->data); for (int i = 0; i < m; i++) preOrder(p->child[i]); } } // 6. 树的后序遍历 void postOrder(tree p) { if(p) { for (int i = 0; i < m; i++) postOrder(p->child[i]); printf("%c ",p->data); } } // 7. 树的层序遍历 void leverOrder(tree t) { queue q; init(&q); if(t) // 树非空时 insert(&q,*t); // 队列初始为根结点 while (!empty(q)) // 当队列非空 { node n = del(&q); // 出队并访问 printf("%c ",n.data); for (int i = 0; i < m; ++i) { if(n.child[i]) insert(&q,*n.child[i]); // 每个结点的非空孩子入队 } } } // 8.按前序遍历顺序建立一棵度为3的树 tree creatTree() { char c; tree t; if((c = getchar()) == '#') t = NULL; else { t = (tree) malloc(sizeof(node)); t->data = c; for (int i = 0; i < m; ++i) t->child[i] = creatTree(); } return t; } int main() { tree root; // 声明一棵度为3的树 // AB###CE###FH###I####G###D###(样例) printf("创建一颗度为3的树，请输入结点，#表示空结点:\n"); root = creatTree(); printf("前序遍历为：\n"); preOrder(root); printf("\n后序遍历为：\n"); postOrder(root); printf("\n层序遍历为：\n"); leverOrder(root); return 0; } -
树的存储结构 树的存储结构1.双亲表示法#define MAX_SIZE 100 typedef char dadaType; /** * 6.3 树的存储结构 * 1.双亲表示法 * 2.孩子表示法(指针方式孩子表示法；数组方式孩子表示法；链表方式孩子表示法) * 3.孩子兄弟表示法 */ // 6.3.1 双亲表示法 typedef struct node { dadaType data; int parent; }node; //双亲表示法的结点 typedef struct parentTree { node treeList[MAX_SIZE]; int root, length; // 根节点的位置及树结点个数 }tree; //双亲表示法的树 2.孩子表示法(指针方式孩子表示法；数组方式孩子表示法；链表方式孩子表示法)typedef char dadaType; // 6.3.2.1 指针方式孩子表示法 #define m 3 //树的度 typedef struct node { dadaType data; struct node *child[m]; // 指向孩子的指针数组 }node, *tree; tree root;#define MAX_SIZE 100 typedef char dadaType; // 6.3.2.2 数组方式孩子表示法 #define m 3 //树的度 typedef struct node { dadaType data; int child[m]; // 指向孩子的指针数组 }node; typedef struct tree { node treeList[MAX_SIZE]; int root, length; // 根节点的位置及树结点个数 }tree; #define MAX_SIZE 100 typedef char dadaType; // 6.3.2.3 链表方式孩子表示法 typedef struct chNode // 孩子结点类型(孩子链表) { int child; // 结点位置 struct chNode *next; }chNode,*chPoint; typedef struct node // 树中的结点类型 { dadaType data; chPoint firstChild; // 指向第一个孩子的指针 }node; typedef struct tree { node treeList[MAX_SIZE]; int root, length; // 根节点的位置及树结点个数 }tree; 3.孩子兄弟表示法typedef char dadaType; // 3.孩子兄弟表示法 typedef struct node // 树中每个结点类型 { dadaType data; struct node *firstChild, *rightSibling; }node, *tree; tree root;
-
递归的基本概念与递归程序设计以及常见的递归算法 递归的基本概念与递归程序设计以及常见的递归算法#include <stdio.h> // 1. 求n! int fact(int n) { if(n <= 1) return 1; return n * fact(n-1); } // 2.Fibonacci数列，前两项为1，第三项开始每项等于前两项的和 int fibonacci(int n) { if(n == 1 || n == 2) return 1; return fibonacci(n-1) + fibonacci(n-2); } // 3.打印数字三角形 void print(int n) { if(n > 0) { print(n-1); for (int i = 1; i <= n; ++i) printf("%d ",n); printf("\n"); } } // 4. 递归求数组的最大值 int max(int a[], int left, int right) { int lMax, rMax, mid; if(left == right) return a[left]; else { mid = (left+right)/2; lMax = max(a,left,mid); rMax = max(a,mid+1,right); return lMax > rMax ? lMax : rMax; } } int main() { int n = 5; printf("%d! = %d\n",n,fact(n)); printf("fibonacci数列的第%d项为%d\n",n,fibonacci(n)); print(5); int a[10] = {1,2,3,4,5,11,7,8,9,10}; printf("数组最大的数是：%d", max(a,0,9)); return 0; }
-
稀疏矩阵的三元组表示法及转置 稀疏矩阵的三元组表示法及转置#include <stdio.h> // 4.5.2 稀疏矩阵的顺序存储：三元组表示法 typedef int dataType; typedef struct { dataType data[100][100]; // 存放稀疏矩阵 int m, n; // 稀疏矩阵的行、列 }matrix; typedef dataType spMatrix[100][3]; // 存放稀疏矩阵的三元组 // 1.稀疏矩阵转换成三元组存储 void compressMatrix(matrix A,spMatrix B) { int k = 1; for (int i = 0; i < A.m; ++i) { for (int j = 0; j < A.n; ++j) { if(A.data[i][j] != 0) { B[k][0] = i; B[k][1] = j; B[k][2] = A.data[i][j]; k++; } } } B[0][0] = A.m; B[0][1] = A.n; B[0][2] = k-1; } // 三元组表示的稀疏矩阵的转置 void transSpMatrix(spMatrix B,spMatrix C) { // 1.首先统计三元组B表示的原矩阵每列非零元素个数； // 2.计算出转置后的矩阵的每行元素的三元组表示法的起始位置 // 3.交换行、列号并把元素放到新的三元组的最终位置上 int x[100], y[100]; int m = B[0][0],n = B[0][1], t = B[0][2], j; C[0][0] = n,C[0][1] = m,C[0][2] = t; for (int i = 0; i < n; ++i) x[i] = 0; // 初始化数组x for (int i = 1; i <= t; ++i) // 1.步骤1 x[B[i][1]] += 1; y[0] = 1; // 表示第一行起始位置是1 for (int i = 1; i < n; ++i) // 2.步骤2 y[i] = y[i-1] + x[i-1]; for (int i = 1; i <= t; ++i) // 3.步骤3 { j = y[B[i][1]]; // j为三元组最终位置 C[j][0] = B[i][1]; C[j][1] = B[i][0]; C[j][2] = B[i][2]; y[B[i][1]] = j+1; // 同行的下一个元素的最终位置要递增 } } int main() { matrix A,D; spMatrix B,C; B[0][2] = 0; A.m = 7,A.n = 6; // 声明7行6列矩阵A D.m = 6,D.n = 7; // 转置后的矩阵D for (int i = 0; i < A.m; ++i) // 初始化矩阵A { for (int j = 0; j < A.n; ++j) A.data[i][j] = 0; } for (int i = 0; i < D.m; ++i) // 初始化矩阵D { for (int j = 0; j < D.n; ++j) A.data[i][j] = 0; } A.data[0][2] = -5,A.data[0][4] = 1; A.data[1][3] = 2; A.data[2][0] = 3; A.data[4][0] = 12; A.data[5][5] = 4; A.data[6][2] = 21; printf("矩阵A如下所示：\n"); for (int i = 0; i < A.m; ++i) { for (int j = 0; j < A.n; ++j) printf("%d\t",A.data[i][j]); printf("\n"); } compressMatrix(A,B); printf("稀疏矩阵有%d行%d列\n",B[0][0],B[0][1]); printf("第%d行第%d列的值是%d\n",B[1][0]+1,B[1][1]+1,B[1][2]); printf("矩阵A的三元组表示法如下所示：\n"); for (int i = 0; i <= B[0][2]; ++i) printf("%d\t%d\t%d\t%d\n",i,B[i][0],B[i][1],B[i][2]); printf("矩阵A的转置的三元组表示法如下所示：\n"); transSpMatrix(B,C); for (int i = 0; i <= C[0][2]; ++i) { D.data[C[i][0]][C[i][1]] = C[i][2]; // 三元组转为普通矩阵 printf("%d\t%d\t%d\t%d\n",i,C[i][0],C[i][1],C[i][2]); } printf("矩阵A的转置矩阵D如下所示：\n"); for (int i = 0; i < D.m; ++i) { for (int j = 0; j < D.n; ++j) printf("%d\t",D.data[i][j]); printf("\n"); } return 0; }
-
多维数组及其实现 多维数组及其实现(以三维数组为例)#include <stdio.h> #include <stdlib.h> typedef int dataType; // 4.3 数组的存储和相关操作，以三维数组为例 typedef struct { dataType *base; int index[3]; int c[3]; }array; // 1. 三位数组的初始化 int initArray(array *A, int a,int b, int c) { if(a<0 || b<0 || c<0) { printf("非法的数组声明操作！\n"); return 0; } // 给数组分配一片连续的空间 A->base = (dataType *) malloc(a*b*c*sizeof(dataType)); if(!A->base) return 0; // 空间分配失败 A->index[0] = a,A->index[1] = b,A->index[2] = c; A->c[0] = b*c,A->c[1] = c,A->c[2] = 1; return 1; } // 2.三维数组的赋值 int setValue(array *A,int a,int b, int c, dataType x) { int offset; // 地址偏移量 if(a<0 || b<0 || c<0 || a>=A->index[0] || b>=A->index[1] || c>=A->index[2]) return 0; // 数组索引越界 offset = a*A->c[0] + b*A->c[1] + c*A->c[2]; *(A->base + offset) = x; return 1; } // 3.三维数组的取值 int getValue(array A,int a,int b, int c, dataType *x) { int offset; // 地址偏移量 if(a<0 || b<0 || c<0 || a>=A.index[0] || b>=A.index[1] || c>=A.index[2]) return 0; // 数组索引越界 offset = a*A.c[0] + b*A.c[1] + c*A.c[2]; *x = *(A.base + offset); return 1; } int main() { array A; // 声明三维数组 int a = 2, b = 3, c = 4; initArray(&A,a,b,c); // 初始化2*3*4的三位数组 dataType x = 10,y; if(setValue(&A,a-1,b-1,c-1,x)) printf("给数组A[%d][%d][%d]赋值%d\n",a-1,b-1,c-1,x); else printf("数组索引越界！"); if(getValue(A,a-1,b-1,c-1,&y)) printf("数组A[%d][%d][%d]的值为%d",a-1,b-1,c-1,y); else printf("数组索引越界！"); return 0; }
