实验1.1 合并有序数组
//001合并有序数组
#include <bits/stdc++.h>
#define MAXSIZE 20 //数组的最大长度为20
typedef 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 < n; i++)
{
scanf("%d", &la->elem[i]);
la->last++;
}
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%d", &lb->elem[i]);
lb->last++;
}
}
void mergeList(SeqList *la, SeqList *lb, SeqList *lc) //合并数组
{
int ia, ib, ic; //三个数分别指向三个线性表中正在进行数据处理的位置
ia = 0;
ib = 0;
ic = 0; //从头开始处理
while (ia <= la->last && ib <= lb->last) //两个数组都没有处理完数据时
{
if (la->elem[ia] <= lb->elem[ib]) //比较当前的两个数，将较小数放入lc中
{
lc->elem[ic] = la->elem[ia];
ia++;
ic++;
}
else
{
lc->elem[ic] = lb->elem[ib];
ib++;
ic++;
}
}
while (ia <= la->last) //当有一个或两个数组完成了对所有数据的处理，则将没有完成数据处理的数组中剩余的元素依次放入lc中
{
lc->elem[ic] = la->elem[ia];
ia++;
ic++;
}
while (ib <= lb->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 < length; i++)
printf("%d\n", L->elem[i]);
}
int main()
{
SeqList la, lb, lc;
inputList(&la, &lb);
mergeList(&la, &lb, &lc);
printList(la.last + lb.last + 2, &lc);
return 0;
}
//002高精度计算PI值
#include <bits/stdc++.h>
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 < 1000; i++)
{
list *q = (list *)malloc(sizeof(list));
q->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)=2
sum->next->data = 2; //与上同理
a = 0, b = 0; //分别是用来暂时存储进位和余数
for (i = 1; i < 2500; i++) //循环两千次，确保精确度
{
p = number->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 < n; i++)
{
printf("%d", x->data);
x = x->next;
}
return 0;
}
//003稀疏矩阵转置：一次定位快速转置法
#include <bits/stdc++.h>
#define MAXSIZE 2000
typedef 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 <= A.t; p++) //完成转置
{
int col = A.data[p].c;
int q = pos[col];
B->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和输出矩阵B
initMatrixA(&A);
initMatrixB(&B, A.m, A.n, A.t);
transposeMatrix(A, &B);
printResult(B);
return 0;
}
//004 稀疏矩阵加法
#include <bits/stdc++.h>
#define MAXSIZE 20000
using 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 < A->t; i++)
{
scanf("%d%d%d", &A->data[i].x, &A->data[i].y, &A->data[i].e);
}
for (int i = 0; i < B->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 < B->t; i++)
{
for (int j = 0; j < A->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 < B->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 < A->t; i++) //行列递增排序
{
for (int j = 0; j < A->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;
}
//005 以十字链表为存储结构实现矩阵相加
#include <bits/stdc++.h>
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 < N->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 < N->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->m; i++) //初始化行列指针
M->rhead[i] = NULL;
for (int i = 1; i <= M->n; i++)
M->chead[i] = NULL;
for (int i = 1; i <= M->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 <= B->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 < temp1->y) || temp1->right == NULL) //如果temp2的列已经大于temp1的列，说明temp2没有遇到相同列数的temp1
{ //又或者已经遍历到尽头都没有相同列数
insertNode(A, temp2); //说明该列不可能存在相同位置了，直接插入
break;
}
else if (temp2->y > temp1->y && temp2->y < temp1->right->y) //如果temp2正好介于两者之间
{
insertNode(A, temp2);
break;
}
}
if (temp2->right == NULL)
break;
}
}
}
}
}
void printMatrix(Matrix *L)
{
int i;
Node *p;
for (i = 1; i <= L->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 2
1 1 1
1 3 1
2 2 2
1 2 1
2 2 3
*/
//006 稀疏矩阵的乘法
#include <bits/stdc++.h>
#define MAXSIZE 2000
typedef 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 <= B.t; q++) //内两层循环是遍历所有元素，找到能进行乘法的元素数对
{
if (A.data[p].r == i && B.data[q].c == j && A.data[p].c == B.data[q].r)
{
temp += A.data[p].e * B.data[q].e;
}
}
}
if (!temp)
continue;
else
{
C->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;
}
//007 哈夫曼编/译码器
#include <bits/stdc++.h>
#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; //编码长度最多为n
int c = i; //当前叶子结点序号
int p = ht[c].parent; //叶子结点双亲序号
while (p)
{
if (ht[p].lchild == c)
hc[i].bit[hc[i].start] = 0;
else
hc[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;
else
t = 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;
}
//求赋权图中一个结点到所有结点的最短路径长度
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000
int 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 < G->Vnum; i++)
{
for (int j = 0; j < G->Vnum; j++)
{
scanf("%d", &G->arc[i][j]);
}
}
}
void initDij(Graph *G, Dij *D)
{
for (int i = 0; i < G->Vnum; i++)
{
D->visited[i] = 0;
D->length[i] = INF;
}
D->visited[0] = 1;
D->length[0] = 0;
for (int i = 0; i < G->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 < G->Vnum; i++)
{
if (!D->visited[i] && D->length[i] < min)
{
min = D->length[i];
r = i;
}
}
D->visited[r] = true;
return r;
}
bool judgeFinished(Graph *G, Dij *D)
{
for (int i = 0; i < G->Vnum; i++)
{
if (!D->visited[i])
return false;
}
return true;
}
int min(int a, int b)
{
return a > b ? b : a;
}
void updateArcV(int V0, Graph *G, Dij *D)
{
for (int i = 0; i < G->Vnum; i++)
{
if (G->arc[V0][i] != 10000 && !D->visited[i])
{
D->length[i] = min(D->length[i], D->length[V0] + G->arc[V0][i]);
}
}
}
void findMinPath(Graph *G, Dij *D)
{
initDij(G, D);
for (int i = 0; i < G->Vnum - 1; i++)
{
int t = searchMinLengthV(G, D);
if (judgeFinished(G, D))
return;
updateArcV(t, G, D);
}
}
void printPath(Graph *G, Dij *D)
{
for (int i = 0; i < G->Vnum; i++)
{
printf("%d\n", D->length[i]);
}
}
int main()
{
Graph G;
Dij D;
initGraph(&G);
int ans[MAXSIZE] = {0};
findMinPath(&G, &D);
printPath(&G, &D);
return 0;
}
/*
6
0 1 4 10000 10000 10000
1 0 2 7 5 10000
4 2 0 10000 1 10000
10000 7 10000 0 3 2
10000 5 1 3 0 6
10000 10000 10000 2 6 0
*/
/*实验4.2：用迪杰斯特拉算法求赋权图中的最短路径
核心：
1.与上一题一样更新完成最短路径图
2.从目标结点向前寻找最短路径：按照结点的length递减的顺序；验证length-边长?=上一个结点length
*/
#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 105
typedef struct Graph
{
int Vnum;
int arc[MAXSIZE][MAXSIZE];
} Graph;
typedef struct Dij
{
bool visited[MAXSIZE];
int length[MAXSIZE];
} Dij;
typedef struct Stack
{
int top;
int data[MAXSIZE];
} Stack;
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 *G, Dij *D, Stack *S)
{
scanf("%d", &G->Vnum);
for (int i = 0; i < G->Vnum; i++)
{
for (int j = 0; j < G->Vnum; j++)
{
scanf("%d", &G->arc[i][j]);
}
}
for (int i = 0; i < G->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 < G->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 < G->Vnum; i++)
{
if (!D->visited[i] && D->length[i] < min)
{
min = D->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 < G->Vnum; i++)
{
if (!D->visited[i] && D->length[v] + G->arc[i][v] < D->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 < G->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 < G->Vnum; i++)
{
if (G->arc[i][end] != 10000 && D->length[i] < D->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;
}
/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
0 2
*/
//010用弗洛伊德算法求赋权图的两点间的最短路径长度
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000
using 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 < G->vnum; i++)
{
for (int j = 0; j < G->vnum; j++)
{
scanf("%d", &G->arc[i][j]);
G->path[i][j] = -1;
}
}
}
void floyd(Graph *G)
{
for (int m = 0; m < G->vnum; m++)
for (int a = 0; a < G->vnum; a++)
for (int b = 0; b < G->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 < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", G->arc[a][b]);
}
}
int main()
{
Graph G;
init_Graph(&G);
floyd(&G);
print_result(&G);
return 0;
}
/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
2
0 2
3 0
*/
//011用弗洛伊德算法求赋权图任意两点间的最短路径
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000
using 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 < G->vnum; i++)
{
for (int j = 0; j < G->vnum; j++)
{
scanf("%d", &G->arc[i][j]);
G->path[i][j] = -1;
}
}
}
void floyd(Graph *G)
{
for (int m = 0; m < G->vnum; m++)
for (int a = 0; a < G->vnum; a++)
for (int b = 0; b < G->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 < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
init_Stack(S);
find_path(G, S, a, b);
while (S->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;
}
/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
2
0 2
3 0
*/
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur
前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来
文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g