搜索到
57
篇与
的结果
-
稀疏矩阵的三元组表示法及转置 稀疏矩阵的三元组表示法及转置#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; }
-
字符串的链式存储和操作 字符串的链式存储和操作#include <stdio.h> #include <stdlib.h> typedef struct linkNode { char data; struct linkNode *next; }node, *linkStr; // 1.初始化字符串 void init(linkStr *s) { *s = NULL; } // 2.输出字符串 void display(linkStr s) { if(!s) { printf("字符串为空！\n"); return; } while (s) { printf("%c",s->data); s = s->next; } printf("\n"); } // 3.根据用户输入构造字符串 void strCreate(linkStr *s) { char c; node *p, *r = *s; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n') { p = (node*) malloc(sizeof(node)); p->data = c; if(!*s) *s = p; else r->next = p; r = p; } if(r) r->next = NULL; } // 4.查找第i个字符 node *find(linkStr s, int i) { if(i < 1 || !s) return NULL; if(i == 1) return s; int j = 1; while (s && i!=j) { s = s->next; j++; } return s; } // 5.将字符串t插入字符串s中第i个字符开始的位置上 void strInsert(linkStr *s, int i, linkStr t) { if(!t) return; if(i < 1) { printf("非法的插入操作！\n"); return; } node *p = find(*s,i-1),*r = t; while (r->next) r = r->next; if(i == 1) { r->next = *s; *s = t; return; } if(p) { r->next = p->next; p->next = t; // t还需删除 } else printf("非法的插入操作！\n"); } // 6.将串s从第i个字符起删除len个长度的子串 void strDel(linkStr *s, int i, int len) { if(!*s) { printf("字符串为空，无法删除！\n"); return; } if(i < 1 || len < 1) { printf("非法的删除操作！\n"); return; } node *pre = *s,*r,*q; int j = 1; while (pre && j < i-1) // 找到删除的前驱结点 { pre = pre->next; j++; } j = 0; r = pre; while (r && j < len) // 找到删除的最后一个结点 { j++; if(pre == *s && j == 1) continue; r = r->next; } if(r) { if(pre == *s) { q = pre; *s = r->next; free(q); } else { pre->next = r->next; pre = pre->next; while (pre != r->next) { q = pre; free(q); pre = pre->next; } } } else printf("非法的删除操作！\n"); } // 7.字符串的连接运算 void strConcat(linkStr *s,linkStr t) { node *p = *s; if(!t) // t为空串时 return; if(!*s) // s为空串时 *s = t; else { while (p->next) // 找到s的尾结点 p = p->next; p->next = t; } } // 8.截取子串 linkStr substring(linkStr s, int i, int len) { linkStr t; // 字串 init(&t); if(i < 1 || len < 1) { printf("非法的截取操作！\n"); return t; } node *p = s,*q,*r,*n; // p、q为主串工作指针，r指向字串尾指针 int j = 1; while (p && j < i) // 寻找第i个结点 { p = p->next; j++; } q = p,j = 1; while (q && j < len) // 寻找第i+len-1个结点 { j++; q = q->next; } if(!q) // 表示超过s的边界 { printf("非法的截取操作！\n"); return t; } while (p != q->next) { n = (node*) malloc(sizeof(node)); n->data = p->data; if(!t) // 处理首结点 t = n; else r->next = n; r = n; // 更新尾指针 p = p->next; } r->next = NULL; // 处理字串尾部 return t; } int main() { linkStr str,t,s; init(&str); init(&t); strCreate(&str); printf("字符串str: "); display(str); strCreate(&t); printf("字符串t: "); display(t); int i = 1,len = 5; printf("将字符t插到str中的第%d个字符开始的位置上\n",i); strInsert(&str,i,t); printf("字符串str: "); display(str); printf("将串str从第%d个字符起删除%d个长度的子串\n",i,len); strDel(&str,i,len); printf("字符串str: "); display(str); init(&t); strCreate(&t); printf("字符串t: "); display(t); printf("把字符串t拼接在str后\n"); strConcat(&str,t); printf("字符串str: "); display(str); s = substring(str,i,len); printf("字符串str从第%d个字符开始长度为%d的子串:\n",i,len); display(s); return 0; }
