实验1.1 合并有序数组

//001合并有序数组#include #define MAXSIZE 20 //数组的最大长度为20typedef struct //定义线性表的顺序存储结构{int elem[MAXSIZE];int last = -1;} SeqList;void inputList(SeqList *la, SeqList *lb) //输入两个线性表{int n, m;scanf("%d", &n);for (int i = 0; i elem[i]);la->last++;}scanf("%d", &m);for (int i = 0; i elem[i]);lb->last++;}}void mergeList(SeqList *la, SeqList *lb, SeqList *lc) //合并数组{int ia, ib, ic; //三个数分别指向三个线性表中正在进行数据处理的位置ia = 0;ib = 0;ic = 0; //从头开始处理while (ia last && ib last) //两个数组都没有处理完数据时{if (la->elem[ia] elem[ib]) //比较当前的两个数，将较小数放入lc中{lc->elem[ic] = la->elem[ia];ia++;ic++;}else{lc->elem[ic] = lb->elem[ib];ib++;ic++;}}while (ia last) //当有一个或两个数组完成了对所有数据的处理，则将没有完成数据处理的数组中剩余的元素依次放入lc中{lc->elem[ic] = la->elem[ia];ia++;ic++;}while (ib last){lc->elem[ic] = lb->elem[ib];ib++;ic++;}lc->last = la->last + lb->last + 1;}void printList(int length, SeqList *L) //打印线性表{for (int i = 0; i elem[i]);}int main(){SeqList la, lb, lc;inputList(&la, &lb);mergeList(&la, &lb, &lc);printList(la.last + lb.last + 2, &lc);return 0;}

实验1.2高精度计算PI值

//002高精度计算PI值#include typedef struct list //定义双向链表{int data;struct list *next;struct list *prior;} list;list *Initlist() //初始化双向链表{list *head;head = (list *)malloc(sizeof(list));head->next = head->prior = head;return head;}list *Creatlist(list *head) //建立链表{int i;list *p;p = head;for (i = 0; i data = 0;q->prior = p;p->next = q;q->next = head; //第一次循环时此时的head和p是一个东西，目的为把链表画成一个圈head->prior = q;p = p->next;}return head;}int main(){int n, i, a, b;scanf("%d", &n);list *number, *sum;list *p, *q, *x;number = Initlist();sum = Initlist();number = Creatlist(number);sum = Creatlist(sum);number->next->data = 2;//第一位储存2，即2*R(1)=2sum->next->data = 2; //与上同理a = 0, b = 0;//分别是用来暂时存储进位和余数for (i = 1; i prior;//做大数乘法时从链表的后方开始while (p != number) //大于10则把10位的数字给b，个位数字放入data域中。{a = p->data * i + b;p->data = a % 10;b = a / 10;p = p->prior;}b = 0;//清空b,为除法做准备p = p->next;//大数除法从链表的前方开始while (p != number) //若计算出的数字为自然数，则直接放入data域；若等于0,或为小数，则要计算余数并给b。{a = p->data + b * 10;p->data = a / (2 * i + 1);b = a % (2 * i + 1);p = p->next;}b = 0; //清零p = number->prior; //大数加法均从末尾开始q = sum->prior;while (p != number) //大于10进位，并储存个位数，进位数字赋给b。{a = p->data + q->data + b;q->data = a % 10;b = a / 10;p = p->prior;q = q->prior;}}printf("3.");x = sum->next->next; //从小数开始输出。for (i = 0; i data);x = x->next;}return 0;}

实验2.1稀疏矩阵转置

//003稀疏矩阵转置：一次定位快速转置法#include #define MAXSIZE 2000typedef struct triple{ //定义三元组int r, c, e; //三元组的坐标和元素值} triple;typedef struct matrix{//定义稀疏矩阵int m, n, t;//稀疏矩阵的行列数和非零元素个数triple data[MAXSIZE]; //该稀疏矩阵中的三元组信息从下标1开始} matrix;void initMatrixA(matrix *M) //初始化矩阵A{scanf("%d%d", &M->m, &M->n); //输入矩阵信息M->t = 0;int temp_r, temp_c, temp_e;while (true) //输入三元组信息{scanf("%d", &temp_r);getchar();scanf("%d", &temp_c);getchar();scanf("%d", &temp_e);getchar();if (temp_r == 0 && temp_c == 0 && temp_e == 0){break;}M->t++;M->data[M->t].r = temp_r;M->data[M->t].c = temp_c;M->data[M->t].e = temp_e;}}void initMatrixB(matrix *M, int m, int n, int t) //初始化B矩阵{M->m = n;M->n = m;M->t = t;}void transposeMatrix(matrix A, matrix *B) //转置函数{int num[MAXSIZE], pos[MAXSIZE]; //num存储A中每一列非零元素个数，pos记录不同列号对应的开始位置for (int col = 0; col < A.n; col++){num[col] = 0;}for (int t = 1; t <= A.t; t++) //统计每一个列号对应的三元组个数{num[A.data[t].c]++;}pos[0] = 1;for (int col = 1; col < A.n; col++) //计算不同列号对应的开始位置{pos[col] = pos[col - 1] + num[col - 1];}for (int p = 1; p data[q].r = A.data[p].c;B->data[q].c = A.data[p].r;B->data[q].e = A.data[p].e;pos[col]++;}}void printResult(matrix M) //输出矩阵三元组{for (int i = 1; i <= M.t; i++){printf("%d %d %d\n", M.data[i].r, M.data[i].c, M.data[i].e);}}int main(){matrix A, B; //定义待转置矩阵A和输出矩阵BinitMatrixA(&A);initMatrixB(&B, A.m, A.n, A.t);transposeMatrix(A, &B);printResult(B);return 0;}

实验2.2稀疏矩阵加法，实现C=A+B

//004 稀疏矩阵加法#include #define MAXSIZE 20000using namespace std;typedef struct triple{int x, y; //非零元素的坐标int e;//非零元素的值} triple;typedef struct matrix{int row, col, t;//定义矩阵的长宽和非零元素个数triple data[MAXSIZE]; //存储矩阵的三元组} matrix;void inputTriple(matrix *A, matrix *B) //输入矩阵三元组{for (int i = 0; i t; i++){scanf("%d%d%d", &A->data[i].x, &A->data[i].y, &A->data[i].e);}for (int i = 0; i t; i++){scanf("%d%d%d", &B->data[i].x, &B->data[i].y, &B->data[i].e);}}void addMatrix(matrix *A, matrix *B) //矩阵相加{for (int i = 0; i t; i++){for (int j = 0; j t; j++){if (A->data[j].x == B->data[i].x && A->data[j].y == B->data[i].y) //相同位置有非零元素{A->data[j].e += B->data[i].e;B->data[i].x = -1; //标记已经用过的三元组}if (A->data[j].e == 0) //排除相加后为0的三元组{A->data[j].x = -1;}}}for (int i = 0; i t; i++) //对于B中没有用过的三元组进行遍历{if (B->data[i].x == -1)continue;A->data[A->t].x = B->data[i].x;A->data[A->t].y = B->data[i].y;A->data[A->t].e = B->data[i].e; //新建A的三元组A->t++;}}void sortTriple(matrix *A) //对A中三元组按照行递增和行内列递增的顺序进行排列{for (int i = 0; i t; i++) //行列递增排序{for (int j = 0; j t - i - 1; j++){if (A->data[j].x > A->data[j + 1].x || (A->data[j].x == A->data[j + 1].x && A->data[j].y > A->data[j + 1].y)){triple t = A->data[j];A->data[j] = A->data[j + 1];A->data[j + 1] = t;}}}}void printMatrix(matrix A){for (int i = 0; i < A.t; i++){if (A.data[i].x == -1)continue;printf("%d %d %d\n", A.data[i].x, A.data[i].y, A.data[i].e);}}int main(){matrix A, B;scanf("%d%d%d%d", &A.row, &A.col, &A.t, &B.t);B.row = A.row;B.col = A.col;inputTriple(&A, &B);addMatrix(&A, &B);sortTriple(&A);printMatrix(A);return 0;}

实验2.3稀疏矩阵加法，用十字链表实现C=A+B

//005 以十字链表为存储结构实现矩阵相加#include typedef struct Node{int x, y, e;Node *right, *down;} Node;typedef struct Matrix{Node **rhead, **chead;int m, n, t;} Matrix;void initMatrix(Matrix *A, Matrix *B){scanf("%d%d%d%d", &A->m, &A->n, &A->t, &B->t);B->m = A->m;B->n = A->n;}void insertNode(Matrix *L, Node *P) //插入节点{Node *temp, *N;N = (Node *)malloc(sizeof(Node)); //新建待插入节点N->y = P->y;N->x = P->x;N->e = P->e;//装载节点信息//插入行指针if (L->rhead[N->x] == NULL || L->rhead[N->x]->y > N->y) //需要插在头结点的情况{N->right = L->rhead[N->x];L->rhead[N->x] = N;}else{for (temp = L->rhead[N->x]; temp->right && temp->right->y y; temp = temp->right); //不断向右遍历找到正确插入位置N->right = temp->right;temp->right = N;}//插入列指针if (L->chead[N->y] == NULL || L->chead[N->y]->x > N->x){N->down = L->chead[N->y];L->chead[N->y] = N;}else{for (temp = L->chead[N->y]; temp->down && temp->down->x x; temp = temp->down);N->down = temp->down;temp->down = N;}}void createMatrix(Matrix *M){Node *p, q;M->rhead = (Node **)malloc((M->m + 1) * sizeof(Node));M->chead = (Node **)malloc((M->n + 1) * sizeof(Node)); //创建行列指针表for (int i = 1; i m; i++)//初始化行列指针M->rhead[i] = NULL;for (int i = 1; i n; i++)M->chead[i] = NULL;for (int i = 1; i t; i++) //开辟节点并装在数据域和插入十字链表{p = (Node *)malloc(sizeof(Node));scanf("%d%d%d", &p->x, &p->y, &p->e);insertNode(M, p);}}void addMatrix(Matrix *A, Matrix *B){Node *p, *temp1, *temp2;for (int i = 1; i m; i++) //枚举每一行的头指针{if (B->rhead[i] == NULL) //如果B矩阵的该行没有元素，直接跳过，不需要执行加法continue;else{if (A->rhead[i] == NULL) //如果B该行不空，但A空，问题转化为将B中节点插入A中{temp2 = B->rhead[i];while (temp2){insertNode(A, temp2);temp2 = temp2->right;}}else //如果A该行和B该行都不空{for (temp2 = B->rhead[i];; temp2 = temp2->right){for (temp1 = A->rhead[i];; temp1 = temp1->right) //对于该行某个B节点，枚举所有A节点{if (temp2->y == temp1->y) //如果两个节点位置重合，直接相加{temp1->e += temp2->e;break;}//如果位置不重合else if ((temp2->y y) || temp1->right == NULL) //如果temp2的列已经大于temp1的列，说明temp2没有遇到相同列数的temp1{ //又或者已经遍历到尽头都没有相同列数insertNode(A, temp2); //说明该列不可能存在相同位置了，直接插入break;}else if (temp2->y > temp1->y && temp2->y right->y) //如果temp2正好介于两者之间{insertNode(A, temp2);break;}}if (temp2->right == NULL)break;}}}}}void printMatrix(Matrix *L){int i;Node *p;for (i = 1; i m; i++){p = L->rhead[i];while (p != NULL){if (p->e != 0)printf("%d %d %d\n", p->x, p->y, p->e);p = p->right;}}}int main(){Matrix A, B;initMatrix(&A, &B);createMatrix(&A);createMatrix(&B);addMatrix(&A, &B);printMatrix(&A);return 0;}/*3 4 3 21 1 11 3 12 2 21 2 12 2 3*/

实验2.4稀疏矩阵的乘法

//006 稀疏矩阵的乘法#include #define MAXSIZE 2000typedef struct triple{ //定义三元组int r, c, e; //三元组的坐标和元素值} triple;typedef struct matrix{//定义稀疏矩阵int m, n, t;//稀疏矩阵的行列数和非零元素个数triple data[MAXSIZE]; //该稀疏矩阵中的三元组信息从下标1开始} matrix;void initMatrix(matrix *M) //初始化稀疏矩阵{scanf("%d", &M->m);getchar();scanf("%d", &M->n);while (true){triple *p = (triple *)malloc(sizeof(triple));scanf("%d", &p->r);getchar();scanf("%d", &p->c);getchar();scanf("%d", &p->e);if (!p->c)break;M->t++;M->data[M->t].r = p->r;M->data[M->t].c = p->c;M->data[M->t].e = p->e;}}void multiplyMatrix(matrix A, matrix B, matrix *C){int temp = 0; //temp用于累加当前行列相乘所得到的结果for (int i = 1; i <= A.m; i++){for (int j = 1; j <= B.n; j++) //外两层循环是分别遍历第一个矩阵的行号和第二个矩阵的列号，排列组合{for (int p = 1; p <= A.t; p++){for (int q = 1; q t++;C->data[C->t].r = i;C->data[C->t].c = j;C->data[C->t].e = temp;temp = 0;}}}}void printMatrix(matrix M) //输出矩阵三元组{for (int i = 1; i <= M.t; i++){printf("%d %d %d\n", M.data[i].r, M.data[i].c, M.data[i].e);}}int main(){matrix A, B, C;initMatrix(&A);initMatrix(&B);C.m = A.m;C.n = B.n;multiplyMatrix(A, B, &C);printMatrix(C);return 0;}

实验3.1哈夫曼编/译器

//007 哈夫曼编/译码器#include #define N 100//叶子结点最大数量#define M 2 * N - 1 //所有结点最大数量typedef struct HTNode //结点{int weight;//权重int parent, lchild, rchild; //双亲、左右孩子结点char data;//字符} HTNode, HT[M + 1];HT ht;typedef struct HCNode{int bit[200]; //编码int start;//该编码的末尾位置} HCNode, HC[100];HC hc;int str[1000] = {0};int len = 0;void select(int pos, int *x1, int *x2){int min = 100000;for (int i = 1; i <= pos; i++){if (ht[i].weight < min && ht[i].parent == 0) //注意判断该节点必须没有双亲节点{min = ht[i].weight;*x1 = i;}}min = 100000;for (int i = 1; i <= pos; i++){if (i == *x1)continue;if (ht[i].weight < min && ht[i].parent == 0) //注意判断该节点必须没有双亲节点{min = ht[i].weight;*x2 = i;}}}void initTree(int n){int x1, x2;for (int i = 1; i <= 2 * n - 1; i++) //对所有结点初始化{ht[i].weight = 0;ht[i].parent = 0;ht[i].lchild = 0;ht[i].rchild = 0;}for (int i = 1; i <= n; i++) //叶子结点的data域{getchar();scanf("%c", &ht[i].data);}for (int i = 1; i <= n; i++) //叶子结点的weight域{scanf("%d", &ht[i].weight);}for (int i = n; i < 2 * n - 1; i++){select(i, &x1, &x2); //找到序号为i的结点之前的两个最小权重结点//两个最小权重结点组成一棵树，以i处的结点为根节点，直至循环结束所有结点组成一棵树ht[i + 1].weight = ht[x1].weight + ht[x2].weight;ht[x1].parent = i + 1;ht[x2].parent = i + 1;ht[i + 1].lchild = x1;ht[i + 1].rchild = x2;}}void encode(int n){for (int i = 1; i <= n; i++){hc[i].start = n;//编码长度最多为nint c = i;//当前叶子结点序号int p = ht[c].parent; //叶子结点双亲序号while (p){if (ht[p].lchild == c)hc[i].bit[hc[i].start] = 0;elsehc[i].bit[hc[i].start] = 1;hc[i].start--;//准备录入下一位编码c = p;//上溯p = ht[c].parent; //上溯，直到while循环结束}hc[i].start++; //while循环中，start多退了一位。}}void printCode(int n){len = 0;char code[1000];scanf("%s", code);for (int i = 0; i < strlen(code); i++){for (int j = 1; j <= n; j++){if (code[i] == ht[j].data){for (int k = hc[j].start; k <= n; k++){printf("%d", hc[j].bit[k]);str[len] = hc[j].bit[k]; //存储待破解编码len++;}}}}printf("\n");}void decode(int n) //译码并输出{int t;for (int i = 0; i < len;){t = 2 * n - 1; //根节点while (ht[t].lchild != 0 && ht[t].rchild != 0) //当找到叶子节点时，退出循环{if (str[i] == 0)t = ht[t].lchild;elset = ht[t].rchild;i++;}printf("%c", ht[t].data);}}int main(){int n;scanf("%d", &n);initTree(n);encode(n);printCode(n);decode(n);return 0;}

实验4.1求赋权图中一个结点到所有结点的最短路径的长度

//求赋权图中一个结点到所有结点的最短路径长度#include #define MAXSIZE 105#define INF 10000int ans[MAXSIZE] = {0};typedef struct Graph{int data[MAXSIZE];int arc[MAXSIZE][MAXSIZE];int Vnum, Anum;} Graph;typedef struct dijkstra{bool visited[MAXSIZE];int length[MAXSIZE];} Dij;void initGraph(Graph *G){scanf("%d", &G->Vnum);for (int i = 0; i Vnum; i++){for (int j = 0; j Vnum; j++){scanf("%d", &G->arc[i][j]);}}}void initDij(Graph *G, Dij *D){for (int i = 0; i Vnum; i++){D->visited[i] = 0;D->length[i] = INF;}D->visited[0] = 1;D->length[0] = 0;for (int i = 0; i Vnum; i++){if (G->arc[0][i] != 10000){D->length[i] = G->arc[0][i];}}}int searchMinLengthV(Graph *G, Dij *D){int min = 10000;int r;for (int i = 0; i Vnum; i++){if (!D->visited[i] && D->length[i] length[i];r = i;}}D->visited[r] = true;return r;}bool judgeFinished(Graph *G, Dij *D){for (int i = 0; i Vnum; i++){if (!D->visited[i])return false;}return true;}int min(int a, int b){return a > b " />length[i]);}}int main(){Graph G;Dij D;initGraph(&G);int ans[MAXSIZE] = {0};findMinPath(&G, &D);printPath(&G, &D);return 0;}/*60 1 4 10000 10000 100001 0 2 7 5 100004 2 0 10000 1 1000010000 7 10000 0 3 210000 5 1 3 0 610000 10000 10000 2 6 0*/

实验4.2用迪杰斯特拉算法求赋权图中的最短路径

/*实验4.2：用迪杰斯特拉算法求赋权图中的最短路径核心：1.与上一题一样更新完成最短路径图2.从目标结点向前寻找最短路径：按照结点的length递减的顺序；验证length-边长" />Vnum);for (int i = 0; i Vnum; i++){for (int j = 0; j Vnum; j++){scanf("%d", &G->arc[i][j]);}}for (int i = 0; i Vnum; i++){D->visited[i] = 0;D->length[i] = G->arc[0][i];}D->visited[0] = 1;S->top = -1;}bool is_finished(Graph *G, Dij *D){for (int i = 0; i Vnum; i++){if (!D->visited[i]){return false;}}return true;}int find_minlength_V(Graph *G, Dij *D){int min = 10005;int min_V;for (int i = 0; i Vnum; i++){if (!D->visited[i] && D->length[i] length[i];min_V = i;}}return min_V;}void update_arc_V(Graph *G, Dij *D, int v){D->visited[v] = true;for (int i = 0; i Vnum; i++){if (!D->visited[i] && D->length[v] + G->arc[i][v] length[i]){D->length[i] = D->length[v] + G->arc[i][v];}}}void caculate_minlength_for_each_V(Graph *G, Dij *D){for (int i = 0; i Vnum; i++){if (is_finished(G, D)){return;}int v = find_minlength_V(G, D);update_arc_V(G, D, v);}}void find_path(Graph *G, Dij *D, Stack *S){int start, end;scanf("%d%d", &start, &end);push_stack(S, end);while (end != start){for (int i = 0; i Vnum; i++){if (G->arc[i][end] != 10000 && D->length[i] length[end] && D->length[i] + G->arc[i][end] == D->length[end]){push_stack(S, i);end = i;}}}}void print_path(Stack *S){while (S->top > -1){printf("%d\n", pop_stack(S));}}int main(){Graph G;Dij D;Stack S;init(&G, &D, &S);caculate_minlength_for_each_V(&G, &D);int path[MAXSIZE];find_path(&G, &D, &S);print_path(&S);return 0;}/*40 2 10 100002 0 7 310 7 0 610000 3 6 00 2*/

实验4.3用弗洛伊德算法求赋权图的两点间的最短路径的长度

//010用弗洛伊德算法求赋权图的两点间的最短路径长度#include #define MAXSIZE 105#define INF 10000using namespace std;typedef struct Graph{int vnum;int arc[MAXSIZE][MAXSIZE];int path[MAXSIZE][MAXSIZE];} Graph;void init_Graph(Graph *G){scanf("%d", &G->vnum);for (int i = 0; i vnum; i++){for (int j = 0; j vnum; j++){scanf("%d", &G->arc[i][j]);G->path[i][j] = -1;}}}void floyd(Graph *G){for (int m = 0; m vnum; m++)for (int a = 0; a vnum; a++)for (int b = 0; b vnum; b++){if (G->arc[a][b] > G->arc[a][m] + G->arc[m][b]){G->arc[a][b] = G->arc[a][m] + G->arc[m][b];G->path[a][b] = m;}}}void print_result(Graph *G){int n;scanf("%d", &n);for (int i = 0; i arc[a][b]);}}int main(){Graph G;init_Graph(&G);floyd(&G);print_result(&G);return 0;}/*40 2 10 100002 0 7 310 7 0 610000 3 6 020 23 0*/

实验4.4用弗洛伊德算法求赋权图中任意两点间的最短路径

//011用弗洛伊德算法求赋权图任意两点间的最短路径#include #define MAXSIZE 105#define INF 10000using namespace std;typedef struct Graph{int vnum;int arc[MAXSIZE][MAXSIZE];int path[MAXSIZE][MAXSIZE];} Graph;typedef struct Stack{int top;int data[MAXSIZE];} Stack;void init_Stack(Stack *S){S->top = -1;}void push_Stack(Stack *S, int e){S->top++;S->data[S->top] = e;}int pop_Stack(Stack *S){S->top--;return S->data[S->top + 1];}void init_Graph(Graph *G){scanf("%d", &G->vnum);for (int i = 0; i vnum; i++){for (int j = 0; j vnum; j++){scanf("%d", &G->arc[i][j]);G->path[i][j] = -1;}}}void floyd(Graph *G){for (int m = 0; m vnum; m++)for (int a = 0; a vnum; a++)for (int b = 0; b vnum; b++){if (G->arc[a][b] > G->arc[a][m] + G->arc[m][b]){G->arc[a][b] = G->arc[a][m] + G->arc[m][b];G->path[a][b] = m;}}}void find_path(Graph *G, Stack *S, int a, int b){push_Stack(S, b);if (G->path[a][b] == -1){push_Stack(S, a);return;}else{find_path(G, S, a, G->path[a][b]);}}void print_result(Graph *G, Stack *S){int n;scanf("%d", &n);for (int i = 0; i top > -1){printf("%d\n", pop_Stack(S));}}}int main(){Graph G;Stack S;init_Graph(&G);floyd(&G);print_result(&G, &S);return 0;}/*40 2 10 100002 0 7 310 7 0 610000 3 6 020 23 0*/