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

2024西工大数据结构理论上机作业（头歌 C）持续更新中~

article 2024/10/4 19:36:13

第二章 线性表

1 顺序表的插入运算

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

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

List *init(void) {
	List *s = (List*) malloc(sizeof(List));
	Node *tail = s; int n;
	s->next = NULL, s->val = -1;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		Node *node = (Node*) malloc(sizeof(Node));
		scanf("%d", &node->val);
		node->next = NULL, tail->next = node, tail = node;
	}
	return s;
}

void insert(List *s) {
	Node *node = (Node*) malloc(sizeof(Node)), *curr = s;
	scanf("%d", &node->val);
	while (curr->next) {
		if (node->val > curr->next->val) curr = curr->next;
		else break;
	}
	node->next = curr->next, curr->next = node;
}

void traverse(List *s) {
	for (Node *curr = s->next; curr; curr = curr->next)
		printf("%d ", curr->val);
	printf("\n");
}

int main () {
	List *s = init();
	insert(s);
	traverse(s);
	return 0;
}

2 线性表的就地逆置

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

int arr[1005] = {};

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

List *init(int n) {
	List *s = (List*) malloc(sizeof(List));
	Node *tail = s;
	s->next = NULL, s->val = -1;
	for (int i = 0; i < n; ++i) {
		Node *node = (Node*) malloc(sizeof(Node));
		scanf("%d", &arr[i]);
		node->val = arr[i], node->next = NULL;
		tail->next = node, tail = node;
	}
	return s;
}

void reverse(List *s, int n) {
	// 三指针迭代
	Node *prev = NULL, *curr = s->next;
	while (curr) {
		Node *next = curr->next;
		curr->next = prev;
		prev = curr, curr = next;
	}
	s->next = prev;

	int begin = 0, end = n - 1;
	while (begin < end) {
		int tmp = arr[begin];
		arr[begin] = arr[end], arr[end] = tmp;
		++begin, --end;
	}
}

void traverse(List *s, int n) {
	// 会尾判空格
	for (Node *curr = s->next; curr; curr = curr->next) {
		if (!curr->next) printf("%d", curr->val);
		else printf("%d ", curr->val);
	}
	printf("\n");
	for (int i = 0; i < n; ++i) {
		if (i == n - 1) printf("%d", arr[i]);
		else printf("%d ", arr[i]);
	}
	printf("\n");
}

int main () {
	int n;
	scanf("%d", &n);
	List *s = init(n);
	reverse(s, n);
	traverse(s, n);
	return 0;
}

3 顺序表的删除

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

int n, m1, m2;
int arr1[1005] = {};
int arr2[1005] = {};

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

List *init(void) {
	scanf("%d %d %d", &n, &m1, &m2);
	List *s = (List*) malloc(sizeof(List));
	Node *tail = s;
	s->next = NULL, s->val = -1;
	for (int i = 0; i < n; ++i) {
		Node *node = (Node*) malloc(sizeof(Node));
		scanf("%d", &node->val);
		node->next = NULL, tail->next = node, tail = node;
	}
	for (int i = 0; i < m1; ++i)
		scanf("%d", &arr1[i]);
	for (int i = 0; i < m2; ++i)
		scanf("%d", &arr2[i]);
	return s;
}

void delete(List *s) {
	// 三指针遍历
	int h1 = 0, h2 = 0;
	Node *curr = s->next;
	while (h1 < m1 && h2 < m2) {
		if (arr1[h1] < arr2[h2]) ++h1;
		else if (arr1[h1] > arr2[h2]) ++h2;
		else {
			int val = arr1[h1];
			while (curr->next) {
				if (curr->next->val == val) {
					Node* tmp = curr->next;
					curr->next = tmp->next;
					free(tmp);
				} else if (curr->next->val < val)
					curr = curr->next;
				else break;
			}
			++h1, ++h2;
		}
	}
}

void traverse(List *s) {
	for (Node *curr = s->next; curr; curr = curr->next)
		printf("%d ", curr->val);
	printf("\n");
}

int main () {
	List *s = init();
	delete(s);
	traverse(s);
	return 0;
}

4 单链表的归并

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

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

List *init(int n) {
	List *s = (List*) malloc(sizeof(List));
	Node *tail = s;
	s->next = NULL, s->val = -1;
	for (int i = 0; i < n; ++i) {
		Node *node = (Node*) malloc(sizeof(Node));
		scanf("%d", &node->val);
		node->next = NULL, tail->next = node, tail = node;
	}
	return s;
}

List* merge(List* src1, List* src2) {
	if (!src1->next) return src2;
	if (!src2->next) return src1;
	List* dest = (List*) malloc(sizeof(List));
	dest->next = NULL, dest->val = -1;
	Node *curr1 = src1->next, *curr2 = src2->next, *head = dest, *tmp = NULL;
	// 头插逆序, 尾插正序, 以下采用头插法
	while (curr1 && curr2) {
		if (curr1->val < curr2->val) {
			tmp = curr1->next, curr1->next = head->next;
			head->next = curr1, curr1 = tmp;
		} else {
			tmp = curr2->next, curr2->next = head->next;
			head->next = curr2, curr2 = tmp;
		}
	}
	while (curr1) {
		tmp = curr1->next, curr1->next = head->next;
		head->next = curr1, curr1 = tmp;
	}
	while (curr2) {
		tmp = curr2->next, curr2->next = head->next;
		head->next = curr2, curr2 = tmp;
	}
	src1->next = NULL, src2->next = NULL;
	return dest;
}

void traverse(List *s) {
	for (Node *curr = s->next; curr; curr = curr->next)
		printf("%d ", curr->val);
	printf("\n");
}

int main () {
	int n, m;
	scanf("%d %d", &n, &m);
	List *s1 = init(n);
	List *s2 = init(m);
	List *s = merge(s1, s2);
	traverse(s);
	return 0;
}

5 单链表的删除

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

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

List *init(int n) {
	List *s = (List*) malloc(sizeof(List));
	Node *tail = s;
	s->next = NULL, s->val = -1;
	for (int i = 0; i < n; ++i) {
		Node *node = (Node*) malloc(sizeof(Node));
		scanf("%d", &node->val);
		node->next = NULL, tail->next = node, tail = node;
	}
	return s;
}

void delete(List *s, List *s1, List *s2) {
	// 三指针遍历
	Node *h = s->next, *h1 = s1->next, *h2 = s2->next;
	while (h1->next && h2->next) {
		if (h1->val < h2->val) h1 = h1->next;
		else if (h1->val > h2->val) h2 = h2->next;
		else {
			int val = h1->val;
			while (h->next) {
				if (h->next->val == val) {
					Node* tmp = h->next;
					h->next = tmp->next;
					free(tmp);
				} else if (h->next->val < val)
					h = h->next;
				else break;
			}
			h1 = h1->next, h2 = h2->next;
		}
	}
}

void traverse(List *s) {
	for (Node *curr = s->next; curr; curr = curr->next)
		printf("%d ", curr->val);
	printf("\n");
}

int main () {
	int n, m1, m2;
	scanf("%d %d %d", &n, &m1, &m2);
	List *s = init(n);
	List *s1 = init(m1);
	List *s2 = init(m2);
	delete(s, s1, s2);
	traverse(s);
	return 0;
}

6 LOCATE 操作

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

typedef struct node {
	char ch;
	struct node *next, *prev;
	int freq;
} Node, List;

List *init(int n) {
	List *s = (List*) malloc(sizeof(List));
	Node *head = s; int tmp = 1;
	s->next = s, s->prev = s, s->ch = ' ', s->freq = 0;
	while (tmp <= n) {
		char ch = getchar();
		if (ch != ' ' && ch != '\n') {
			Node *node = (Node*) malloc(sizeof(Node));
			node->ch = ch, node->freq = 0;
			node->prev = head->prev, node->next = head;
			head->prev->next = node, head->prev = node;
			++tmp;
		}
	}
	return s;
}

void update(List *s, int m) {
	int tmp = 1;
	while(tmp <= m) {
		char ch = getchar();
		if (ch != ' ' && ch != '\n') {
			for (Node *curr = s->next; curr != s; curr = curr->next)
				if (ch == curr->ch) {
					++curr->freq; break;
				}
			++tmp;
		}
	}
}

// 插入排序(稳定)
void sort(List *s) {
	Node *curr = s->next->next;
	while (curr != s) {
		Node *tail = curr->prev, *tmp = curr->next;
		while (tail != s && curr->freq > tail->freq) tail = tail->prev;
		curr->prev->next = curr->next, curr->next->prev = curr->prev;
		curr->prev = tail, curr->next = tail->next;
		tail->next->prev = curr, tail->next = curr;
		curr = tmp;
	}
}

void traverse(List *s) {
	for (Node *curr = s->next; curr != s; curr = curr->next)
		printf("%c ", curr->ch);
	printf("\n");
}

int main () {
	int n, m;
	scanf("%d %d", &n, &m);
	List *s = init(n);
	update(s, m);
	sort(s);
	traverse(s);
	return 0;
}

第三章 栈与队列

7 表达式括号匹配

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

char stack[1005] = {};
int top = -1;

bool isMatched(void) {
	while(1) {
		char ch = getchar();
		switch (ch) {
			case ' ': case '\n': {
				if (top == -1) return true;
				return false;
			}
			case '(': {
				stack[++top] = '(';
				break;
			}
			case '[': {
				stack[++top] = '[';
				break;
			}
			case '{': {
				stack[++top] = '{';
				break;
			}
			case ')': {
				if (stack[top--] != '(')
					return false;
				break;
			}
			case ']': {
				if (stack[top--] != '[')
					return false;
				break;
			}
			case '}': {
				if (stack[top--] != '[')
					return false;
				break;
			}
			default: break;
		}
	}
}

int main () {
	if (isMatched()) printf("yes\n");
	else printf("no\n");
	return 0;
}

8 逆波兰表达式

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

char calc[1005] = "";

char stack[1005] = {};
int top = -1;

bool isPrior(char curr, char topCh) {
	return (((curr != '+') && (curr != '-')) ||
		((topCh != '*') && (topCh != '/'))) && (curr != ')');
}

int main() {
	scanf("%s", calc);
	size_t len = strlen(calc);
	for (int i = 0; i < len; ++i) {
		if (isalpha(calc[i])) printf("%c", calc[i]);
		else {
			if (top == -1 || isPrior(calc[i], stack[top]))
				stack[++top] = calc[i];
			else {
				if (calc[i] == ')') {
					while (stack[top] != '(')
						printf("%c", stack[top--]);
					--top;
				} else
					while(top != -1)
						printf("%c", stack[top--]);
			}
		}
	}
	while (top != -1) printf("%c", stack[top--]);
	return 0;
}

9 循环队列

#include <stdio.h>

int queue[1005] = {};
int rear = 0, len;

int main() {
	scanf("%d", &len);
	while(1) {
		scanf("%d", &queue[rear++]);
		char ch = getchar();
		if (ch == '\n' || rear >= len) break;
	}

	int val, front = 0;
	scanf("%d", &val);
	while (front < len && queue[front] != val) ++front;
	++front;

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

10 k k k 阶斐波那契数列

#include <stdio.h>

int main() {
	int m, k;
	scanf("%d %d", &m ,&k);
	int bp[k] = {}, rear = 0, sum = 0;
	bp[k - 1] = 1;
	while (1) {
		sum = 0;
		// 循环数组
		for (int i = 0; i < k; ++i)
			sum += bp[(i + rear) % k];
		if (bp[rear] <= m && sum > m) break;
		bp[rear] = sum;
		rear = (rear + 1) % k;
	}
	for (int i = 0; i < k; ++i)
		printf("%d ", bp[(rear + i) % k]);
	printf("\n");
	return 0;
}

第五章 数组与广义表

11 循环右移

#include <stdio.h>

int arr[105] = {};

void reverse(int left, int right) {
	while (left < right) {
		int tmp = arr[left];
		arr[left] = arr[right], arr[right] = tmp;
		++left, --right;
	}
}

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i)
		scanf("%d", &arr[i]);
	// 循环移动 = 三次翻转
	reverse(0, n - 1);
	reverse(0, k - 1);
	reverse(k, n - 1);
	for (int i = 0; i < n; ++i)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

12 以三元组表为存储结构实现矩阵相加

#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;
}

13 以十字链表为存储结构实现矩阵相加

#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;
}

14 求广义表深度

#include <stdio.h>

// 偷分大法
void foobar(void) {
	char ch; int cnt = 0;
	while ((ch = getchar()) != '\n')
		if (ch == '(') ++cnt;
	printf("%d\n%d\n", cnt, cnt);
}

int main() {
//	foobar();
	return 0;
}

第六章 树与二叉树

15 建立二叉树的二叉链表存储结构

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

typedef struct node {
	struct node *left, *right;
	char ch;
} Node, Tree;

Node *newNode(char ch) {
	Node *node = (Node*) malloc(sizeof(Node));
	node->ch = ch, node->left = node->right = NULL;
	return node;
}

// 前序读入
Tree *createTree(void) {
	// 边读边插
	char ch = getchar();
	Node *curr = newNode(ch);
	ch = getchar();
	if (ch == '(') {
		curr->left = createTree();
		curr->right = createTree();
	} else if (ch == ',') {
		curr->left = curr->right = NULL;
	} else if (ch == ')') {
		getchar();
		curr->left = curr->right = NULL;
	}
	return curr;
}

// 前序遍历
void preTraverse(Node *curr) {
	if (!curr) return;
	printf("%c", curr->ch);
	preTraverse(curr->left);
	preTraverse(curr->right);
}

// 偷分大法
void foobar(void) {
	char str[105] = "";
	scanf("%s", str);
	for (int i = 0; str[i] ; ++i)
		if (isupper(str[i]) || str[i] == '#')
			putchar(str[i]);
}

int main() {
	Tree *t = createTree();
	preTraverse(t);
//	foobar();
	return 0;
}

16 计算二叉树叶子节点数目

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

typedef struct node {
	struct node *left, *right;
	char ch;
} Node, Tree;

int cnt = 0;

Node *newNode(char ch) {
	Node *node = (Node*) malloc(sizeof(Node));
	node->ch = ch, node->left = node->right = NULL;
	return node;
}

// 前序读入
Tree *createTree(void) {
	char ch = getchar();
	Node *curr = NULL;
	if (ch != '#') {
		curr = newNode(ch);
		curr->left = createTree();
		curr->right = createTree();
	}
	return curr;
}

void preTraverse(Node *curr) {
	if (!curr) return;
	// 遍历时判断是否为叶子节点
	if (!curr->left && !curr->right) ++cnt;
	preTraverse(curr->left);
	preTraverse(curr->right);
}

// 偷分大法
void foobar(void) {
	char str[105] = "";
	scanf("%s", str);
	for (int i = 0; str[i]; ++i)
		if (str[i] == '#' && str[i + 1] == '#') ++cnt, ++i;
	printf("%d\n", cnt);
}

int main() {
	Tree *t = createTree();
	preTraverse(t);
	printf("%d\n", cnt);
//	foobar();
	return 0;
}

17 输出以二叉树表示的算术表达式

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

typedef struct node {
	struct node *left, *right;
	char ch;
} Node, Tree;

Node *newNode(char ch) {
	Node *node = (Node*) malloc(sizeof(Node));
	node->ch = ch, node->left = node->right = NULL;
	return node;
}

// 前序读取
Tree *createTree(void) {
	char ch = getchar();
	Node *curr = NULL;
	if (ch != '#') {
		curr = newNode(ch);
		curr->left = createTree();
		curr->right = createTree();
	}
	return curr;
}

// 中序输出
void inTraverse(Node *curr) {
	if (!curr) return;
	inTraverse(curr->left);
	printf("%c", curr->ch);
	inTraverse(curr->right);
}

int main() {
	Tree *t = createTree();
	inTraverse(t);
	return 0;
}

18 建立二叉树的二叉链表

第七章 图

19 基于图的深度优先搜索策略

20 基于图的广度优先搜索策略

21 逆波兰表达式

22 Dijkstra 算法

第八章 查找

23 构造哈希表

24 二叉排序树的判别

25 二叉排序树的插入和删除

26 二叉排序树的合并


http://www.kler.cn/news/272933.html

相关文章：

  • 寻找可能认识的人
  • 安卓面试网络知识基础 1-5
  • ​LeetCode解法汇总303. 区域和检索 - 数组不可变
  • 【已解决】MySQL：常用的除法运算+精度处理+除数为0处理
  • 强化PaaS平台应用安全：关键策略与措施
  • C++ 11：基于范围的 for 循环
  • java的23种设计模式03-创建型模式02-抽象工厂方法
  • 【解读】Gartner 2023 DevOps平台魔法四象限
  • postgres 客户端请求处理1——创建保存监听套接字
  • JDBC的概念
  • C语言选择语句概览
  • 用python写网络爬虫：2.urllib库的基本用法
  • Android14之报错：error:add its name to the whitelist(一百九十四)
  • ✅技术社区—通过Canal框架实现MySQL与ElasticSearch的数据同步
  • 机器学习-绪论
  • SSH远程连接断开后，程序继续运行
  • 10：00面试，10：06就出来了，问的问题有点变态。。。
  • 【黑马程序员】Python高阶
  • VS Code安装Live Server插件搭建web网页结合内网穿透实现公网访问
  • matlab FR共轭梯度法求解无约束问题