搜索到
58
篇与
的结果
-
递归的基本概念与递归程序设计以及常见的递归算法 递归的基本概念与递归程序设计以及常见的递归算法#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; }
-
字符串的快速模式匹配(KMP算法) 字符串的快速模式匹配(KMP算法)#include <stdio.h> // 顺序存储的字符串 #define MAX_SIZE 100 typedef struct { char str[MAX_SIZE]; int length; }seqString; // 1.顺序字符串的初始化 void init(seqString *str) { str->length = 0; } // 2.根据用户输入构造字符串 void insert(seqString *str) { char c; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n' && str->length < MAX_SIZE) str->str[str->length++] = c; } // 根据模式串求对应的next数组 void getNext(seqString p,int next[]) { int i = 0, j = -1; next[0] = -1; while (i < p.length) { if(j == -1 || p.str[i] == p.str[j]) { i++; j++; next[i] = j; } else j = next[j]; } } // 4.2.2 字符串的KMP模式匹配算法 // 如果成功则返回p在t中首次出现的起始位置，否则返回-1 int kmp(seqString t, seqString p,int next[]) { int i = 0,j = 0; while (i < t.length && j <p.length) { if(j == -1 || t.str[i] == p.str[j]) { i++; j++; } else j = next[j]; } if(j == p.length) return i-p.length; return -1; } int main() { seqString t,p; init(&t); init(&p); insert(&t); insert(&p); int next[p.length]; getNext(p,next); // 求p的next数组 int i = kmp(t,p,next); if(i == -1) printf("模式串匹配失败！\n"); else printf("模式串在主串中首次出现的起始位置是%d",i); return 0; }
-
字符串的朴素模式匹配 字符串的朴素模式匹配#include <stdio.h> // 顺序存储的字符串 #define MAX_SIZE 100 typedef struct { char str[MAX_SIZE]; int length; }seqString; // 1.顺序字符串的初始化 void init(seqString *str) { str->length = 0; } // 2.根据用户输入构造字符串 void insert(seqString *str) { char c; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n' && str->length < MAX_SIZE) str->str[str->length++] = c; } // 4.2.1 字符串的朴素模式匹配算法 // 如果成功则返回p在t中首次出现的起始位置，否则返回-1 int getIndex(seqString t, seqString p) { int i = 0,j,flag = 0;// flag为成功的标识 while (i <= t.length - p.length && !flag) { j = 0; flag = 1; // 每次匹配结束后j回溯，flag设置为真 while (j < p.length && flag) { if(p.str[j] == t.str[j+i]) // 对应相等则继续 j++; else flag = 0; // 否则退出当前循环 } i++; } if(flag) return i-1; return -1; } int main() { seqString t,p; init(&t); init(&p); insert(&t); insert(&p); int i = getIndex(t,p); if(i == -1) printf("模式串匹配失败！\n"); else printf("1模式串在主串中首次出现的起始位置是%d\n",i); return 0; }
