HXD的DS

1.线性表的增删改查

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

typedef struct node
{
	int element;//数据域
	struct node * link;//指针域
}Node;

typedef struct headerList
{
	Node * head;
	int n;
}HeaderList;

int Init(HeaderList * h);//单链表初始化
int Find(HeaderList h, int i, int *x);//单链表的查找
int Insert(HeaderList * h, int i, int x);//单链表的插入
int Delete(HeaderList * h, int i);//单链表的删除
int Output(HeaderList * h);//单链表的输出
void Change(HeaderList * h, int i, int x);//修改元素
void Destroy(HeaderList * h);//单链表的撤销

HeaderList list;

int main()
{
	Init(&list);//初始化
	for (int i = 0; i < 9; i++) Insert(&list, i - 1, i);

	printf("THE LIST IS:
");
	Output(&list);

	Delete(&list, 0);
	printf("
AFTER DELETE THE LIST IS:
");
	Output(&list);

	Change(&list, 3, 22);
	printf("
AFTER CHANGE
");
	Output(&list);

	int temp;
	Find(list, 0, &temp);
	printf("
FIND VALUE: %d
", temp);

	Destroy(&list);

	system("pause");
	return 0;
}

int Init(HeaderList * h)
{
	h->head = (Node *)malloc(sizeof(Node));

	if (!h->head) return 0;

	h->head->link = NULL;
	h->n = 0;

	return 1;
}

int Find(HeaderList h, int i, int *x)
{
	Node *p;

	if (i < 0 || i > h.n - 1) return 0;//判断下标越界

	p = h.head;//c从头节点查找
	for (int j = 0; j <= i; j++) p = p->link;

	*x = p->element;
	return 1;
}

int Insert(HeaderList * h, int i, int x)
{
	Node *p, *q;

	if (i < -1 || i > h->n - 1) return 0;//判断越界

	p = h->head;
	for (int j = 0; j <= i; j++) p = p->link;

	q = (Node *)malloc(sizeof(Node));
	q->element = x;
	q->link = p->link;
	p->link = q;
	h->n++;

	return 1;
}

int Delete(HeaderList * h, int i)
{
	Node *p, *q;

	if (!h->n) return 0;//判断是否为空
	if (i < 0 || i > h->n - 1) return 0;//判断越界

	q = h->head;
	for (int j = 0; j < i; j++) q = q->link;
	p = q->link;
	q->link = p->link;
	free(p);
	h->n--;

	return 1;
}

int Output(HeaderList * h)
{
	Node *p;

	if (!h->n) return 0;//判断是否为空

	p = h->head->link;

	while (p)
	{
		printf("%d ", p->element);
		p = p->link;
	}

	return 1;
}

void Destroy(HeaderList * h)
{
	Node *p;
	while (h->head)
	{
		p = h->head->link;
		free(h->head);
		h->head = p;
	}
}

void Change(HeaderList * h, int i, int x)
{
	Node *p;

	if (i < 0 || i > h->n - 1) return;//判断下标越界

	p = h->head;//c从头节点查找
	for (int j = 0; j <= i; j++) p = p->link;

	p->element = x;
}

2.两个有序单向链表的归并(数组模拟的静态链表实现)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;

int h[3], e[N], ne[N], idx;//h数组为头指针,h[0], h[1]为两个有序链表，归并后的链表是h[2]

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    memset(h, -1, sizeof h);//初始化头指针
    
    //构造两条降序链表
    for (int i = 0; i < 10; i ++ )
    {
        add(0, i);
        add(1, i * i);
    }
    
    puts("");
    
    int i = h[0], j = h[1];
    for ( ; ~i && ~j; )
    {
        int a = e[i], b = e[j];
        
        if (e[i] >= e[j])
        {
            add(2, e[i]);
            i = ne[i];//指向下一个结点
        }
        else
        {
            add(2, e[j]);
            j = ne[j];//指向下一个结点
        }
    }
    
    //扫尾
    while (~i) add(2, e[i]), i = ne[i];
    while (~j) add(2, e[j]), j = ne[j];
    
    for (int i = h[2]; ~i; i = ne[i])
        cout << e[i] << ' ';
    
    puts("");
    
    return 0;
}

3.栈与队列

#include <iostream>

using namespace std;

const int N = 1010;

int q[N];
int cnt = 20;//假设有20张票

int main()
{
    int hh = 0, tt = -1;
    int i = 1;//队列中人的序号
    
    for (int j = 1; j <= 3; j ++ )
        q[ ++ tt] = i ++ ;//假设初始队伍中有3个人
    
    cnt -= 3;
    
    while (hh <= tt)
    {
        auto t = q[hh ++ ];//队头买完票出队
        
        cnt -- ;//票余量减一
        if (cnt >= 0)//如果还有余票
            q[ ++ tt] = i ++ ;
            
        cout << t << ' ';//输出队伍
    }
    
    return 0;
}

4.二叉树的遍历（先，中，后，BFS层次遍历）

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>

using namespace std;

typedef struct btnode
{
	char element;
	struct btnode * lc, *rc;
}BTNode;

BTNode * PreCreateBT(BTNode * t);//先序遍历构建二叉树
void PreOrderTraversal(BTNode * t);//先序遍历二叉树，DFS递归做法
void InOrderTraversal(BTNode * t);//中序遍历二叉树
void PostOrderTraversal(BTNode * t);//后序遍历二叉树
void BFS(BTNode * t);//层次遍历二叉树，BFS宽搜

int main()
{
	BTNode * root = NULL;
	root = PreCreateBT(root);

	//先序遍历二叉树
	cout << "PreOrderTraversal BT tree is :" << endl;
	PreOrderTraversal(root);
	puts("");

	//中序遍历二叉树
	cout << "InOrderTraversal BT tree is :" << endl;
	InOrderTraversal(root);
	puts("");

	//后序遍历二叉树
	cout << "PostOrderTraversal BT tree is :" << endl;
	PostOrderTraversal(root);
	puts("");

	//宽度优先遍历二叉树
	cout << "宽度遍历二叉树：" << endl;
	BFS(root);
	puts("");

	system("pause");
	return 0;
}

BTNode * PreCreateBT(BTNode * t)
{
	char ch;
	ch = getchar();

	if (ch == '#')
		t = NULL;//空结点
	else
	{
		t = (BTNode *)malloc(sizeof(BTNode));
		t->element = ch;
		t->lc = PreCreateBT(t->lc);//构造左儿子
		t->rc = PreCreateBT(t->rc);//构造右儿子
	}

	return t;
}

void PreOrderTraversal(BTNode * t)
{
	if (!t)//树空返回
		return;

	cout << t->element;
	PreOrderTraversal(t->lc);//递归左儿子
	PreOrderTraversal(t->rc);//递归右儿子
}

void InOrderTraversal(BTNode * t)
{
	if (!t)//树空返回
		return;

	InOrderTraversal(t->lc);//递归左儿子
	cout << t->element;
	InOrderTraversal(t->rc);//递归右儿子
}

void PostOrderTraversal(BTNode * t)
{
	if (!t)//树空返回
		return;

	PostOrderTraversal(t->lc);//递归左儿子
	PostOrderTraversal(t->rc);//递归右儿子
	cout << t->element;
}

void BFS(BTNode * t)
{
	queue<BTNode *> q;
	q.push(t);//根结点入队

	while (q.size())
	{
		auto t = q.front();//取队头
		q.pop();//队头出队

		cout << t->element;

		if (t->lc) q.push(t->lc);//如果存在左儿子，入队
		if (t->rc) q.push(t->rc);//如果存在右儿子，入队
	}
}

5.哈夫曼树的搭建，编码与解码的实现

#include <iostream>
#include <map>
#include <algorithm>
#include <string>

using namespace std;

const int N = 30;

struct leaf
{
	int value;
	int parent, lc, rc;//存放父节点，左儿子，右儿子的下标
};

map<int, char> m1;//权重与字符的映射
map<int, int> m2;//权重与对应结构体下标的映射
map<int, int> m3;//权重与对应结构体下标的反映射
int h[N], idx;//数组模拟的小根堆
int cnt;//字符的数量
leaf *root = new leaf[N << 1];//申请哈夫曼树所需的空间,结构体数组
string s;//存放字符的哈夫曼编码

void down(int u);//小根堆的down操作
void up(int u);//小根堆的up操作
void PrintTree(int t);//打印字符和对应的哈夫曼编码
void CrackCode(string str);//解码

int main()
{
	char ch;//字符
	int rank;//权重

	for (int i = 0; i < 2 * N; i++)
		root[i].parent = root[i].lc = root[i].rc = -1;

	while (cin >> ch >> rank && ch != '#')
	{
		root[cnt].value = rank;//初始化只有根结点的森林
		m1[rank] = ch;//构造权重与字符的映射
		m3[cnt] = rank;//构造权重与结构体下标的映射
		m2[rank] = cnt++;//构造权重与结构体下标的反映射
		h[++idx] = rank;//权重入堆
	}
	for (int i = idx / 2; i; i--) down(i);//O(n)的建堆方式，从倒数第二层开始down下去

	int n = cnt;
	for (int i = n; i < 2 * n - 1; i++)
	{
		int lchild, rchild;

		if (idx >= 2)
		{
			lchild = m2[h[1]];//取出权重最小的权重下标作为左儿子
			h[1] = h[idx--], down(1);//出堆并维持小根堆
			rchild = m2[h[1]];

			h[1] = h[idx--], down(1);//出堆并维持小根堆

									 //找父结点
			root[lchild].parent = i;
			root[rchild].parent = i;

			//找左右儿子
			root[i].lc = lchild;
			root[i].rc = rchild;

			//父结点权重为左右儿子权重和
			root[i].value = root[lchild].value + root[rchild].value;

			//构造父结点和对应结构体数组下标的映射
			m3[cnt] = root[i].value;
			m2[root[i].value] = cnt++;

			h[++idx] = root[i].value;//新的结点入堆
			up(idx);//维持小根堆

		}
	}

	cout << endl << "字符编码:" << endl;
	PrintTree(m2[h[1]]);

	string str;
	cout << endl << "Input a string :(二进制字符串)" << endl;
	cin >> str;

	CrackCode(str);//解码

	delete[] root;

	system("pause");
	return 0;
}

void down(int u)
{
	int t = u;
	if (u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;
	if (u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;

	if (u != t)
	{
		swap(h[t], h[u]);
		down(t);
	}
}

void up(int u)
{
	while (u / 2 && h[u] < h[u / 2])
	{
		swap(h[u / 2], h[u]);
		u /= 2;
	}
}

void PrintTree(int t)
{
	if (root[t].lc < 0)//打印叶子结点
	{
		cout << m1[root[t].value] << ' ';
		cout << s << endl;
		return;
	}
	string temp;
	temp = s;

	s += '0';
	PrintTree(root[t].lc);
	s = temp;//恢复到递归前的状态
	s += '1';
	PrintTree(root[t].rc);
	s = temp;//恢复到递归前的状态
}

void CrackCode(string str)
{
	int ini = m2[h[1]];//从根结点开始找
	for (int i = 0; str[i]; i++)
	{
		int t = str[i] - '0';

		if (!t)//t为0，向左儿子移动
			ini = root[ini].lc;
		else//否则向右儿子移动
			ini = root[ini].rc;

		if (root[ini].lc < 0)//到达叶结点
		{
			cout << m1[root[ini].value];
			ini = m2[h[1]];//重新从根结点搜索
		}
	}
}

6.Prim求最小生成树

n个点m条边，接下来m行的三个数a b c表示存在从a到b权值为c的一条边

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N];
bool st[N];
int n, m;

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];
        
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }
    
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);
    
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    int t = prim();
    
    if(t == INF) puts("impossible");
    else printf("%d
", t);
    
    return 0;
}

7.最短路算法(适用于稠密图的朴素版Dijkstra与堆优化版适用于稀疏图的Dijkstra算法)

1.适用于稠密图的朴素版Dijkstra算法(O(n²))

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 510;

int g[N][N], dist[N];
int n, m;
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
            
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        
        st[t] = true;
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(g, 0x3f, sizeof g);
    
    cin >> n >> m;
    
    while ( m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        
        g[a][b] = min(g[a][b], c);
    }
    
    printf("%d
", dijkstra());
    
    return 0;
}

2.堆优化版适用于稀疏图的Dijkstra(O(mlogn))(m边数 ，n点数)

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

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

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

8.归并排序+快速排序+堆排序

三个排序的输入一致，第一行为n表示数字个数，第二行输入n个数字

(1).归并排序

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int q[N], temp[N], n;

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;
    
    int mid = l + r >> 1;
    
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    
    while (i <= mid && j <= r)
        if(q[i] <= q[j]) temp[k ++ ] = q[i ++ ];
        else temp[k ++ ] = q[j ++ ];
    
    while (i <= mid) temp[k ++ ] = q[i ++ ];
    while (j <= r) temp[k ++ ] = q[j ++ ];
    
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = temp[j];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", q + i);
    
    merge_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    
    return 0;
}

(2).快速排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int q[N], n;

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;
    
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++ ; while(q[i] < x);
        do j -- ; while(q[j] > x);
        
        if(i < j) swap(q[i], q[j]);
    }
    
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", q + i);
    
    quick_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    
    return 0;
}

(3).堆排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int h[N], idx;
int n;


void down(int u)
{
    int t = u;
    if(u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
    if(u != t)
    {
        swap(h[t], h[u]);
        down(t);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", h + i);
    idx = n;
    
    for (int i = n / 2; i; i -- ) down(i);
    
    while (n -- )
    {
        printf("%d ", h[1]);
        h[1] = h[idx -- ];
        down(1);
    }
    puts("");
    
    return 0;
}