当前位置： 首页 > article >正文

2024西工大数据结构实验（C）

article 2024/11/5 12:20:28

11 道无聊题，什么时候实验课能出一些有意思的题目。

1 线性表

1.1 合并有序数组

经典题目，双指针法，有序链表类似。

#include <stdio.h>

int main () {
	int n, m;
	scanf("%d", &n);
	int arr1[n];
	for (int i = 0; i < n; ++i) scanf("%d", &arr1[i]);
	scanf("%d", &m);
	int arr2[m];
	for (int i = 0; i < m; ++i) scanf("%d", &arr2[i]);

	int arr[n + m], head1 = 0, head2 = 0, head = 0;
	while (head1 < n && head2 < m) {
		if (arr1[head1] < arr2[head2]) arr[head++] = arr1[head1++];
		else arr[head++] = arr2[head2++];
	}
	while (head1 < n) arr[head++] = arr1[head1++];
	while (head2 < m) arr[head++] = arr2[head2++];

	for (int i = 0; i < n + m; ++i) printf("%d\n", arr[i]);
	return 0;
}

1.2 高精度计算 Pi 值

考察高精度 a x ax ax, x a \frac{x}{a} ax​, x + y x+y x+y。数组就能做，题目要求用双向链表，闲得蛋疼。
考虑级数： π = ∑ i = 0 ∞ R ( n ) \pi=\sum_{i=0}^\infty R(n) π=∑i=0∞​R(n), R ( n + 1 ) = n R ( n ) 2 n + 1 R(n+1)=\frac{nR(n)}{2n+1} R(n+1)=2n+1nR(n)​, R ( 1 ) = 2 R(1)=2 R(1)=2.

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int val;
	struct node *prev, *next;
} Node, List;

List* init(void) {
 	Node *s = (Node*) malloc(sizeof(Node));
	s->val = -1, s->prev = s->next = s;
	return s;
}

void pushBack(List *head, int val) {
	Node *curr = (Node*) malloc(sizeof(Node));
	curr->val = val, curr->prev = head->prev, curr->next = head;
	head->prev = head->prev->next = curr;
}

List* createList(size_t size, int val) {
	List *s = init();
	for (int i = 0; i < size; ++i) pushBack(s, val);
	return s;
}

void traverse_n(List *head, size_t cnt) {
	printf("%d.", head->next->val);
	for (Node* curr = head->next->next; curr != head && cnt > 0; curr = curr->next, --cnt)
		printf("%d", curr->val);
	printf("\n");
}

int main () {
	List *Rn = createList(550, 0);
	List *Sn = createList(550, 0);

	Rn->next->val = 2, Sn->next->val = 2;
	for (int n = 1; n <= 2000; ++n) {
		// R(n) = R(n) * n
		int carry = 0;
		for (Node *curr = Rn->prev; curr != Rn; curr = curr->prev) {
			int res = curr->val * n + carry;
			carry = res / 10; curr->val = res % 10;
		}

		// R(n) = R(n) / (2n + 1)
		carry = 0;
		for (Node *curr = Rn->next; curr != Rn; curr = curr->next) {
			int div = (n << 1) + 1;
			int res = curr->val + carry * 10;
			curr->val = res / div; carry = res - curr->val * div;
		}

		// S(n) += R(n)
		carry = 0;
		for (Node *curr1 = Sn->prev, *curr2 = Rn->prev; curr1 != Sn && curr2 != Rn;
		curr1 = curr1->prev, curr2 = curr2->prev) {
			int res = curr1->val + curr2->val + carry;
			curr1->val = res % 10; carry = res / 10;
		}
	}

	int cnt;
	scanf("%d", &cnt);
	traverse_n(Sn, cnt);
	return 0;
}

2 广义表

2.1 稀疏矩阵转置

交换行与列后插入排序（稳定排序算法，不改变原有行顺序——即交换后列顺序）。

#include <stdio.h>
#define MAXSIZE 400

int S[MAXSIZE][3] = {};

void transpose(int cnt) {
	for (int i = 0; i < cnt; ++i) {
		int tmp = S[i][0];
		S[i][0] = S[i][1], S[i][1] = tmp;
	}
	// insertion: stable
	for (int i = 1; i < cnt; ++i) {
		int raw = S[i][0], col = S[i][1], val = S[i][2];
		int j = i - 1;
		while ((j >= 0) && raw < S[0][j]) {
			S[j + 1][0] = S[j][0], S[j + 1][1] = S[j][1], S[j + 1][2] = S[j][2];
			--j;
		}
		S[j + 1][0] = raw, S[j + 1][1] = col, S[j + 1][2] = val;
	}
}

int main () {
	int n, m;
	scanf("%d %d", &n, &m);
	int cnt = 0;
	while(scanf("%d %d %d", &S[cnt][0], &S[cnt][1], &S[cnt][2])) {
		if (S[cnt][0] == 0) break;
		++cnt;
	}

	transpose(cnt);
	for (int i = 0; i < cnt; ++i)
		printf("%d %d %d\n", S[i][0], S[i][1], S[i][2]);
	return 0;
}

2.2 稀疏矩阵加法

双指针法就是好用啊。

#include <stdio.h>

int main () {
	int n, m, t1, t2;
	scanf("%d %d %d %d", &n, &m, &t1, &t2);

	int S1[t1][3] = {}, S2[t2][3] = {}, S[t1 + t2][3] = {};
	for (int i = 0; i < t1; ++i)
		scanf("%d %d %d", &S1[i][0], &S1[i][1], &S1[i][2]);
	for (int i = 0; i < t2; ++i)
		scanf("%d %d %d", &S2[i][0], &S2[i][1], &S2[i][2]);

	int h1 = 0, h2 = 0, h = 0;
	while (h1 < t1 && h2 <t2) {
		if (S1[h1][0] < S2[h2][0]) {
			S[h][0] = S1[h1][0], S[h][1] = S1[h1][1], S[h][2] = S1[h1][2];
			++h1, ++h;
		}
		else if (S1[h1][0] > S2[h2][0]) {
			S[h][0] = S2[h2][0], S[h][1] = S2[h2][1], S[h][2] = S2[h2][2];
			++h2, ++h;
		}
		else {
			if (S1[h1][1] < S2[h2][1]) {
				S[h][0] = S1[h1][0], S[h][1] = S1[h1][1], S[h][2] = S1[h1][2];
				++h1, ++h;
			}
			else if (S1[h1][1] > S2[h2][1]) {
				S[h][0] = S2[h2][0], S[h][1] = S2[h2][1], S[h][2] = S2[h2][2];
				++h2, ++h;
			}
			else {
				S[h][0] = S1[h1][0], S[h][1] = S1[h1][1], S[h][2] = S1[h1][2] + S2[h2][2];
				++h1, ++h2, ++h;
			}
		}
	}

	for (int i = 0; i < t1 + t2 && S[i][0]; ++i)
		printf("%d %d %d\n", S[i][0], S[i][1], S[i][2]);
	return 0;
}

2.3 稀疏矩阵加法（十字链表）

十字链表纯纯炫技的（循环链表套娃），唯一优点是写起来很麻烦可以锻炼耐心（嗯，优点）。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int raw, col, val;
	struct Node *down, *right;
} Node, CList;

CList *createCList(int raw, int col) {
	CList *c = (CList*) malloc(sizeof(CList));
	c->raw = raw, c->col = col, c->val = -1;
	c->down = c->right = c;
	for (int i = raw; i > 0; --i) {
		Node *tmp = (Node*) malloc(sizeof(Node));
		tmp->val = -1, tmp->raw = i, tmp->col = 0;
		tmp->right = tmp, tmp->down = c->down, c->down = tmp;
	}
	for (int i = col; i > 0; --i) {
		Node *tmp = (Node*) malloc(sizeof(Node));
		tmp->val = -1, tmp->raw = 0, tmp->col = i;
		tmp->down = tmp, tmp->right = c->right, c->right = tmp;
	}
	return c;
}

void insertOrAdd(CList *head, int raw, int col, int val) {
	Node *node = (Node*) malloc(sizeof(Node)), *curr = head;
	for (int i = 1; i <= raw; ++i) curr = curr->down;
	while (curr->right->col < col && curr->right->col != 0) curr = curr->right;
	// 狠狠地偷懒, 把插入和加法逻辑写在一起, 不需要额外写加法了.
	if (curr->right->col == col) {
		curr->right->val += val;
		free(node);
		return;
	}
	node->right = curr->right, curr->right = node;
	curr = head;
	for (int i = 1; i <= col; ++i) curr = curr->right;
	while (curr->down->raw < raw && curr->down->raw != 0) curr = curr->down;
	node->down = curr->down, curr->down = node;
	node->raw = raw, node->col = col, node->val = val;
}

void traverse(CList *S) {
	for (Node *r = S->down; r != S; r = r->down) {
		for (Node *c = r->right; c != r; c = c->right) {
			printf("%d %d %d\n", c->raw, c->col, c->val);
		}
	}
}

int main () {
	int n, m, t1, t2, r, c, v;
	scanf("%d %d %d %d", &n, &m, &t1, &t2);
	CList *S1 = createCList(n, m);
	for (int i = t1; i > 0 ; --i) {
		scanf("%d %d %d", &r, &c, &v);
		insertOrAdd(S1, r, c, v);
	}
	for (int i = t2; i > 0 ; --i) {
		scanf("%d %d %d", &r, &c, &v);
		insertOrAdd(S1, r, c, v);
	}
	traverse(S1);
	return 0;
}

2.4 稀疏矩阵乘法

双指针还要写回溯，不如直接遍历了。

// multiplication of spare matrix
#include <stdio.h>

#define MAXSIZE 400

int S1[MAXSIZE][3] = {};
int S2[MAXSIZE][3] = {};
int S[MAXSIZE][3] = {};

int main () {
	int r1, c1, r2, c2, t1 = 0, t2 = 0, sum = 0, h = 0;
	scanf("%d %d", &r1, &c1);
	while(scanf("%d %d %d", &S1[t1][0], &S1[t1][1], &S1[t1][2])) {
		if (S1[t1][0] == 0) break;
		++t1;
	}
	scanf("%d %d", &r2, &c2);
	while(scanf("%d %d %d", &S2[t2][0], &S2[t2][1], &S2[t2][2])) {
		if (S2[t2][0] == 0) break;
		++t2;
	}

	for (int i = 1; i <= r1; ++i) {
		for (int j = 1; j <= c2; ++j) {
			for (int h1 = 0; h1 <= t1; ++h1) {
				for (int h2 = 0; h2 <= t2; ++h2) {
					if (S1[h1][0] == i && S2[h2][1] == j && S1[h1][1] == S2[h2][0])
						sum += S1[h1][2] * S2[h2][2];
				}
			}
			if (!sum) continue;
			S[h][0] = i, S[h][1] = j, S[h][2] = sum; sum = 0; ++h;
		}
	}

	for (int i = 0; i < h; ++i)
		printf("%d %d %d\n", S[i][0], S[i][1], S[i][2]);
	return 0;
}

3 树

3.1 哈夫曼编码器

贪心策略构建哈夫曼树，叶节点上溯得到逆序编码。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>

typedef struct {
	int ch, weight;
	int parent, left, right;
} HTree;

typedef struct {
	bool bit [128];
	char ch, begin;
} HCode;

HTree *createHTree(int n) {
	HTree *ht = (HTree*) calloc(2 * n, sizeof(HTree));
	// 限制于多种因素, 只能采用这种读入方式.
	int tmp = 1;
	while(tmp <= n) {
		char ch = getchar();
		if (ch != ' ' && ch != '\n') ht[tmp++].ch = ch;
	}
	for (int i = 1; i <= n; ++i) scanf("%d", &ht[i].weight);

	int min1, min2, rn, ln;
	for (int i = n + 1; i <= 2 * n - 1; ++i) {
		min1 = min2 = INT_MAX; rn = ln = 0;
		for (int j = 1; j <= i - 1; ++j) {
			if (ht[j].weight < min1 && !ht[j].parent)
				min2 = min1, rn = ln, min1 = ht[j].weight, ln = j;
			else if (ht[j].weight < min2 && !ht[j].parent)
				min2 = ht[j].weight, rn = j;
		}
		ht[ln].parent = ht[rn].parent = i;
		ht[i].left = ln, ht[i].right = rn;
		ht[i].weight = ht[ln].weight + ht[rn].weight;
	}
	return ht;
}

HCode *createHCode(HTree *ht, int n) {
	HCode *hc = (HCode*) calloc(n + 1, sizeof(HCode));
	for (int i = 1; i <= n; ++i) {
		hc[i].begin = n; hc[i].ch = ht[i].ch;
		int cn = i, pn = ht[cn].parent;
		while (pn) {
			if (ht[pn].left == cn) hc[i].bit[hc[i].begin] = 0;
			else hc[i].bit[hc[i].begin] = 1;
			--hc[i].begin, cn = pn, pn = ht[cn].parent;
		}
		++hc[i].begin;
	}
	return hc;
}

void encode(HCode *hc, int n) {
	char text[1001] = "";
	scanf("%s", text);
	for (int i = 0; i < strlen(text); ++i) {
		for (int j = 1; j <= n; ++j) {
			if (text[i] == hc[j].ch) {
				for (int k = hc[j].begin; k <= n; ++k) {
					printf("%d", hc[j].bit[k]);
				}
			}
		}
	}
	// 什么? 你问为什么不写译码? 别问, 问就是偷懒.
	// 要是能用cpp字典就写译码了.
	printf("\n%s\n", text);
}

int main () {
	int n;
	scanf("%d", &n);

	HTree *ht = createHTree(n);
	HCode *hc = createHCode(ht, n);
	encode(hc, n);
	return 0;
}

4 图

4.1 Dijkstra 最短路径长度

从一个顶点开始逐次找路径最短的下一个节点并更新最短路径长度表。

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 105
#define INF 10000

int vn = 0;
int dist[MAXSIZE][MAXSIZE] = {};

bool isVisited[MAXSIZE] = {};
int len[MAXSIZE] = {};

void init(void) {
	scanf("%d", &vn);
	for (int i = 0; i < vn; ++i)
		for (int j = 0; j < vn; ++j)
			scanf("%d", &dist[i][j]);
}

void dijkstra(void) {
	for (int i = 0; i < vn; ++i) len[i] = INF;
	isVisited[0] = true; len[0] = 0;
	for (int i = 0; i < vn; ++i)
		if (dist[0][i] != INF) len[i] = dist[0][i];

	for (int i = 0; i < vn - 1; ++i) {
		int minLen = INF, next;
		for (int j = 0; j < vn; ++j)
			if (!isVisited[j] && len[j] < minLen)
				minLen = len[j], next = j;
		isVisited[next] = true;

		for (int j = 0; j < vn; ++j)
			if (!isVisited[j] && dist[next][j] != INF) {
				int tmp = len[next] + dist[next][j];
				len[j] = len[j] < tmp ? len[j] : tmp;
			}

	}
}

void printLen(void) {
	for (int i = 0; i < vn; ++i)
		printf("%d\n", len[i]);
}

int main () {
	init();
	dijkstra();
	printLen();
	return 0;
}

4.2 Dijkstra 最短路径

在前一题基础上用栈记录。

// shortest path (dijkstra)
#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 105
#define INF 10000

int vn = 0;
int dist[MAXSIZE][MAXSIZE] = {};

bool isVisited[MAXSIZE] = {};
int len[MAXSIZE] = {};

int stack[MAXSIZE] = {};
int top = -1;

void init(void) {
	scanf("%d", &vn);
	for (int i = 0; i < vn; ++i)
		for (int j = 0; j < vn; ++j)
			scanf("%d", &dist[i][j]);
}

void dijkstra(void) {
	for (int i = 0; i < vn; ++i) len[i] = INF;
	isVisited[0] = true; len[0] = 0;
	for (int i = 0; i < vn; ++i)
		if (dist[0][i] != INF) len[i] = dist[0][i];

	for (int i = 0; i < vn - 1; ++i) {
		int minLen = INF, next;
		for (int j = 0; j < vn; ++j)
			if (!isVisited[j] && len[j] < minLen)
				minLen = len[j], next = j;
		isVisited[next] = true;

		for (int j = 0; j < vn; ++j)
			if (!isVisited[j] && dist[next][j] != INF) {
				int tmp = len[next] + dist[next][j];
				len[j] = len[j] < tmp ? len[j] : tmp;
			}

	}
}

void printPath(void) {
	int a, b;
	scanf("%d %d", &a, &b);
	stack[++top] = b;
	while (b != a)
		for (int i = 0; i < vn; ++i)
			if (dist[i][b] != INF && len[i] < len[b] &&
			len[i] + dist[i][b] == len[b])
				stack[++top] = b = i;

	while(top > -1) printf("%d\n", stack[top--]);
}

int main () {
	init();
	dijkstra();
	printPath();
	return 0;
}

4.3 Floyd 最短路径长度

不断以下一个顶点为中间顶点更新邻接矩阵即可。

#include <stdio.h>

#define MAXSIZE 105

int vn = 0;
int dist[MAXSIZE][MAXSIZE] = {};

void init(void) {
	scanf("%d", &vn);
	for (int i = 0; i < vn; ++i)
		for (int j = 0; j < vn; ++j)
			scanf("%d", &dist[i][j]);
}

void floyd(void) {
	for (int n = 0; n < vn; ++n)
		for (int i = 0; i < vn; ++i)
			for (int j = 0; j < vn; ++j)
				if (dist[i][n] + dist[n][j] < dist[i][j])
					dist[i][j] = dist[i][n] + dist[n][j];
}

void printLen(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", dist[a][b]);
	}
}

int main () {
	init();
	floyd();
	printLen();
	return 0;
}

4.4 Floyd 最短路径

在前一题基础上用栈回溯。

#include <stdio.h>

#define MAXSIZE 105

int vn = 0;
int dist[MAXSIZE][MAXSIZE] = {};
int path[MAXSIZE][MAXSIZE] = {};

int stack[MAXSIZE] = {};
int top = -1;

void init(void) {
	scanf("%d", &vn);
	for (int i = 0; i < vn; ++i)
		for (int j = 0; j < vn; ++j) {
			scanf("%d", &dist[i][j]);
			path[i][j] = -1;
		}
}

void floyd(void) {
	for (int n = 0; n < vn; ++n)
		for (int i = 0; i < vn; ++i)
			for (int j = 0; j < vn; ++j)
				if (dist[i][n] + dist[n][j] < dist[i][j]) {
					dist[i][j] = dist[i][n] + dist[n][j];
					path[i][j] = n;
				}
}

void findPath(int a, int b) {
	stack[++top] = b;
	if (path[a][b] == -1) {
		stack[++top] = a;
		return;
	}
	findPath(a, path[a][b]);
}

void printPath(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		top = -1;
		findPath(a, b);
		while (top > -1) printf("%d\n", stack[top--]);
	}
}

int main () {
	init();
	floyd();
	printPath();
	return 0;
}

http://www.kler.cn/a/273460.html

相关文章：

  • WordPress之generatepress主题安装
  • andrular输入框input监听值传递
  • Optimizing Medical Image Segmentation with Advanced Decoder
  • 什么是 OpenTelemetry？
  • Spring1(初始Spring 解耦实现 SpringIOC SpringDI Spring常见面试题)
  • 应用层知识点总结2
  • Monoxer Programming Contest 2024（AtCoder Beginner Contest 345）（A~C）
  • 外贸网站文章批量生成器
  • Linux ftpwho命令教程：如何查看并管理FTP会话(附实例详解和注意事项)
  • pta 7-29 删除字符串中的子串 C语言
  • java kafka客户端何时设置的kafka消费者默认值
  • Git 常用命令总结
  • 【Selenium（一）】
  • Java语言: 多线程
  • 信号处理--基于正则化聚合的共空间模态（CSP）脑电信号分类
  • 功能齐全的免费 IDE Visual Studio 2022 社区版
  • 基于yolov2深度学习网络的人脸检测matlab仿真,图像来自UMass数据集
  • const，static深度总结——c++穿透式分析
  • 统计-R(相关系数)与R^2(决定系数)
  • [数据集][目标检测]番茄成熟度检测数据集VOC+YOLO格式277张3类别
  • 机器人可反向驱动能力与力控架构
  • 蓝桥杯-python-递归
  • 算法练习第二十五天| 216.组合总和III、17.电话号码的字母组合
  • 云手机的数据安全有保障吗？
  • 信息系统项目管理师019：存储和数据库（2信息技术发展—2.1信息技术及其发展—2.1.3存储和数据库）
  • 语音识别：whisper部署服务器（远程访问，语音实时识别文字）