数据结构刷题

山理工数据结构刷题

专题1--顺序表

专题2--栈和队列

专题3--串和数组

专题4--二叉树

专题5--二叉查找树和平衡二叉树

树结构练习——排序二叉树的中序遍历

#include <bits/stdc++.h>
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
typedef pair<int, int> PII;
const int N = 100008;
typedef struct BSNode {
	int data;
	struct BSNode* lchild;
	struct BSNode* rchild;
} BSNode, *BSTree;

void BSinsert(BSTree &T, int key) {
	if (T == NULL) {
		T = new BSNode;
		T->lchild = NULL;
		T->rchild = NULL;
		T->data = key;
	}

	else if (key < T->data) {
		BSinsert(T->lchild, key);
	} else {
		BSinsert(T->rchild, key);
	}
}

void LDR(BSTree T) {
	if (T == NULL) {
		return;
	}
	LDR(T->lchild);
	cout << T->data << ' ';
	LDR(T->rchild);
}
int main () {
	int n;
	while (scanf("%d", &n) != EOF) {
		BSTree T = NULL;
		for (int i = 1; i <= n; i++) {
			int key;
			cin >> key;
			BSinsert(T, key);
		}
		LDR(T);
		printf("\n");
	}



	return 0;
}

专题6--堆、哈夫曼树

专题9--图的遍历DFS&BFS

数据结构实验之图论二：图的深度遍历

#include <bits/stdc++.h>

using namespace std;
const int N = 200;
int g[N][N] = {0};//邻接矩阵存图
bool vis[N] = {false};//标记数组
int k, m;
void dfs(int x) {
	cout << x << ' ';//打印结果
	vis[x] = true;//标记为已经访问
	for (int i = 0; i < k; i++) {//从0遍历到k
		if (vis[i] == false && g[x][i] == 1) { //该点没被访问过,并且该点可以联通
			dfs(i); //递归调用这个函数
		}
	}
}
int main () {
	int t;
	cin >> t;
	while (t--) {
		memset(g, 0, sizeof(g));
		memset(vis, false, sizeof (vis));//每次对数组进行初始化
		cin >> k >> m;
		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			g[u][v] = 1; //建立无向图
			g[v][u] = 1; //建立无向图
		}
		dfs(0);//开始搜索
		cout << '\n';
	}
	return 0;
}

数据结构实验之图论二：图的深度遍历

#include <bits/stdc++.h>
using namespace std;
const int N = 120;

struct Node {
	int data;//数据域
	struct Node* next;//指针域
};
//typedef struct node Node;

Node* head[N];//头指针数组
bool vis[N];//标记数组
int n, m, s;
Node* p = NULL;
void bfs(int s) {
	for (int i = 0; i < m; i++) {//冒泡排序
		for (Node *p = head[i] -> next; p; p = p -> next) {
			for (Node *q = p -> next; q; q = q -> next) {
				if (p -> data > q -> data) {
					int tmp = p -> data;
					p -> data = q -> data;
					q -> data = tmp;
				}
			}
		}
	}
	//下面开始bfs
	int q = 0;
	queue <int > Q;
	Q.push(s);//将起点放入队列
	vis[s] = true; //将起点标记为已经访问
	while (!Q.empty()) { //只要队列不为空
		q = Q.front();
		cout << q << ' ';
		Q.pop();
		for (p = head[q]->next; p != NULL; p = p->next) {
			if (vis[p->data] == false) { //如果未访问过
				vis[p->data] = true; //现在进行访问
				Q.push(p->data);
			}

		}

	}


}
int main () {
	int k;
	cin >> k;
	for (int i = 0; i < N; i++) {
		head[i] = new Node; //初始化头指针数组
	}
	while (k--) {
		memset(vis, 0, sizeof vis); //初始化标记数组
		cin >> n >> m >> s;

		for (int i = 0; i < n; i++) {
			head[i]->next = NULL; //初始化头指针数组
		}

		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			p = new Node; //建立新节点
			p->data = v;
			p->next = head[u]->next; //让新节点指向首元节点
			head[u]->next = p; //头插法
			p = new Node;
			p->data = u;
			p->next = head[v]->next;
			head[v]->next = p; //头插法
		}
		bfs(s);//从开始搜索
		printf("\n");

	}
	return 0;
}