数据结构代码常用模板

线性表

顺序表

#include <iostream>
#include <stdlib.h>
using namespace std;
#define ll long long
#define InitSize 10000 // 默认最大长度
ll t, ans;

typedef struct
{
    int *data;   // 指示动态分配数组的指针
    int MaxSize; // 顺序表的最大容量
    int length;  // 顺序表的当前长度
} SeqList;

void InitList(SeqList &L) // 初始化顺序表
{
    L.data = (int *)malloc(InitSize * sizeof(int)); // data理解为数组
    L.length = 0;                                   // 记录长度
    L.MaxSize = InitSize;                           // 最大尺寸
}

void IncreaseSize(SeqList &L, int len) // 顺序表扩容
{
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int)); // 重新开辟新容量给data
    for (int i = 0; i < L.length; i++)                       // 数据移动
    {
        L.data[i] = p[i];
    }
    L.MaxSize = L.MaxSize + len;
    free(p); // 清理临时数据p
}

int Insert(SeqList *L, int i, int x) // 顺序表输入
{
    int j;
    if (i < -1 || i > L->length - 1)
        return 0;
    if (L->length == L->MaxSize)
        return 0;
    for (j = L->length - 1; j > i; j--)
    {
        L->data[j + 1] = L->data[j];
    }
    L->data[i + 1] = x;
    L->length = L->length + 1;
    return 1;
}

void Inverse(SeqList *L, int length) // 顺序表逆置
{
    int i, temp;
    for (i = 0; i < length / 2; i++)
    {
        temp = L->data[i];
        L->data[i] = L->data[length - 1 - i];
        L->data[length - 1 - i] = temp;
    }
}

int Output(SeqList L) // 顺序表输出
{
    int i;
    if (!L.length)
        return 0;
    for (i = 0; i <= L.length - 1; i++)
        printf("%d ", L.data[i]); // 从前往后逐个输出元素
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    ll t, n, x, y, num;
    cin >> t;
    while (t--)
    {
        SeqList L;
        InitList(L);
        cin >> n >> x >> y;
        for (int i = 0; i < n; i++)
        {
            cin >> num;
            Insert(&L, i - 1, num);
        }
        Inverse(&L, n);
        Output(L);
    }

    return 0;
}

单链表

指针L指向头结点

#include <stdlib.h>
#include <iostream>
using namespace std;
int n, k;

typedef struct LNode
{                       // 定义单链表结点类型
    int data;           // 数据域
    struct LNode *next; // 指针域
} LNode, *LinkList;     // LNode *L == LinkList L
// 设p为指向链表结点的结构体指针,则*p表示结点本身,可以用p->data或(*p).data访问*p这个结点的数据域

// 初始化单链表
bool InitList(LinkList &L) // 带&可以将传入的L修改后带回,不带&会对一个L的复制品进行操作
{
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    return true;
}

// 头插法建立单链表
LinkList HeadInsert(LinkList &L, int n) // 插入n个元素
{
    int x;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        LNode *s = (LNode *)malloc(sizeof(LNode)); // 新插入结点s
        s->data = x;
        s->next = L->next;
        L->next = s;
    }
    return L;
}

// 尾插法建立单链表
LinkList TailInsert(LinkList &L, int n)
{
    LNode *s, *r = L; // r为尾指针
    int x;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return L;
}

// 单链表遍历
void PrintList(LinkList L)
{
    LNode *p = L->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 求单链表的长度
int Length(LinkList L)
{
    LNode *p = L->next;
    int len = 0;
    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}

// 按值查找:查找x在L中的位置,返回一个结点
LinkList LocateElem(LinkList L, int x)
{
    LNode *p = L->next;
    while (p && p->data != x)
    {
        p = p->next;
    }
    return p;
}

// 删除指定值k
void DeleteChange(LinkList &L, int k)
{
    LNode *p = L;
    LNode *s;
    while (p)
    {
        if (p->data == k)
        {
            if (p == L)
            {
                L = p->next; // 更该首地址
            }
            else
                s->next = p->next; // 删除,让上一个节点的next直接链接到下一个节点
        }
        else
            s = p; // s表示上一个节点
        p = p->next;
    }
}

// 按位查找:查找在单链表L中第i个位置的结点
LNode *GetElem(LinkList L, int i)
{
    int j = 1;
    LNode *p = L->next;
    if (i == 0)
        return L;
    if (i < 1)
        return NULL;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    return p; // 如果i大于表长,p=NULL,直接返回p即可
}

// 将x插入到单链表L的第i个位置上
void Insert(LinkList &L, int i, int x)
{
    LNode *p = GetElem(L, i - 1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
}

// 删除操作:将单链表中的第i个结点删除
void Delete(LinkList &L, int i)
{
    if (i < 1 || i > Length(L))
        cout << "删除失败" << endl;
    return;
    LNode *p = GetElem(L, i - 1);
    LNode *q = p->next;
    p->next = q->next;
    free(q);
}

// 判空操作
bool Empty(LinkList L)
{
    if (L->next == NULL)
    {
        // cout << "空表" << endl;
        return true;
    }
    else
    {
        // cout << "不是空表" << endl;
        return false;
    }
}

int main()
{
    cin >> n;             // n个数据
    LinkList L;           // 定义链表
    InitList(L);          // 初始化链表
    L = TailInsert(L, n); // 尾插法建立单链表
    PrintList(L);         // 输出单链表
    return 0;
}

循环单链表

题目:循环单链表的基本运算
http://qdacm.openjudge.cn/ds202402/07/

#include <iostream>
using namespace std;

typedef struct LNode
{
    char data;
    struct LNode *next;
} LNode, *LinkList;

void init(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    L->next = L;
}

void push(LinkList &L)
{
    int n;
    cin >> n;
    if (n == 0)
        return;
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode));
    cin >> p->data;
    p->next = L;
    L->next = p;
    n--;
    while (n--)
    {
        LNode *p1;
        p1 = (LNode *)malloc(sizeof(LNode));
        cin >> p1->data;
        p1->next = L;
        p->next = p1;
        p = p1;
    }
}

void print(LinkList L)
{
    LNode *p = L->next;
    if (p == L)
    {
        return;
    }
    while (p != L)
    {
        if (p->next != L)
            cout << p->data << " ";
        else
            cout << p->data << endl;
        p = p->next;
    }
}

void length(LinkList L)
{
    LNode *p = L->next;
    int res = 0;
    while (p != L)
    {
        p = p->next;
        res++;
    }
    cout << res << endl;
}

void empty_(LinkList L)
{
    if (L->next == L)
        cout << "yes" << endl;
    else
        cout << "no" << endl;
}

void three(LinkList L, int n)
{
    LNode *p = L;
    while (n--)
    {
        p = p->next;
    }
    cout << p->data << endl;
}

void zifu(LinkList L, char c)
{
    LNode *p = L->next;
    int res = 1;
    while (1)
    {
        if (p->data == c)
        {
            cout << res << endl;
            return;
        }
        p = p->next;
        res++;
    }
}

void push_(LinkList &L, char c, int n)
{
    LNode *p = L;
    n--;
    while (n--)
    {
        p = p->next;
    }
    LNode *p1;
    p1 = (LNode *)malloc(sizeof(LNode));
    p1->data = c;
    p1->next = p->next;
    p->next = p1;
}

void delete_(LinkList &L, int n)
{
    LNode *p = L;
    n--;
    while (n--)
    {
        p = p->next;
    }
    p->next = p->next->next;
}

int main()
{
    LinkList L;
    init(L);
    push(L);
    print(L);
    length(L);
    empty_(L);
    three(L, 3);
    zifu(L, 'a');
    push_(L, 'w', 4);
    print(L);
    delete_(L, 5);
    print(L);
    free(L);
    return 0;
}

栈和队列

顺序栈

#include <iostream>
#include <stdio.h>
using namespace std;
#define ll long long
#define MAX 10000007
#define MaxSize 1000000 // 定义栈中最大元素的个数
ll n;

typedef struct
{
    char data[MaxSize]; // 静态数组存放栈中元素,销毁栈时不必手动释放空间
    int top;            // 定义栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack &S)
{
    S.top = -1;
}
void testStack()
{
    SqStack S; // 声明一个顺序栈(分配空间)
    InitStack(S);
}

// 判空
bool StackEmpty(SqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}

// 新元素入栈
bool Push(SqStack &S, char x)
{
    if (S.top == MaxSize - 1)
        return false;    // 栈满,报错
    S.data[++S.top] = x; // 指针先加1再让新元素入栈
    return true;
}

// 出栈操作
bool Pop(SqStack &S, char &x)
{
    if (S.top == -1)
        return false; // 栈为空
    x = S.data[S.top--];
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S, char &x)
{
    if (S.top == -1)
        return false; // 栈为空
    x = S.data[S.top];
    return true;
}

int main()
{
    // (1)初始化顺序栈S;
    SqStack S;
    InitStack(S);
    // (2)判断顺序栈S是否为空;
    if (StackEmpty(S))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (3)依次进栈元素a,b,c,d,e;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        Push(S, c);
    }
    // (4)判断顺序栈S是否为空;
    if (StackEmpty(S))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (5)输出顺序栈长度;
    cout << S.top + 1 << endl;
    // (6)输出从栈顶到栈底的元素;
    for (int i = S.top; i >= 0; i--)
        cout << S.data[i] << " ";
    cout << endl;
    // (7)输出出栈序列;
    for (int i = S.top; i >= 0; i--)
    {
        char c;
        Pop(S, c);
        cout << c << " ";
    }
    cout << endl;
    // (8)判断顺序栈S是否为空;
    if (StackEmpty(S))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (9)释放顺序栈。
    return 0;
}

链栈

#include <iostream>
#include <stdio.h>
using namespace std;

typedef char ElemType; // 修改栈中存储什么类型的元素
typedef struct Lnode   // 新建链栈
{
    ElemType data;
    struct Lnode *next;
} Lnode, *Linkstack;

void init(Linkstack &s) // 初始化链栈
{
    s = NULL;
}

bool empty(Linkstack s) // 链栈判空
{
    return s == NULL;
}

void push(Linkstack &s, ElemType e) // 入栈
{
    Lnode *p = new Lnode;
    p->data = e;
    p->next = s;
    s = p;
}

void display(Linkstack s) // 输出栈中元素
{
    for (Lnode *p = s; p; p = p->next)
    {
        cout << p->data << " ";
    }
    cout << endl;
}

void pop(Linkstack &s) // 出栈
{
    if (empty(s))
        return;
    Lnode *p = s;
    s = s->next;
    delete p;
}

ElemType top(Linkstack s) // 输出栈顶
{
    return s->data;
}

int size(Linkstack s) // 输出栈中元素个数
{
    int n = 0;
    Lnode *p = s;
    while (p)
    {
        n++;
        p = p->next;
    }
    return n;
}

void destroy(Linkstack &s) // 释放栈
{
    Lnode *p = s;
    while (p)
    {
        Lnode *tmp = p;
        p = p->next;
        delete tmp;
    }
}

int main(void)
{
    Linkstack s;
    int n;
    cin >> n;
    // (1)初始化链栈S;
    init(s);
    // (2)判断链栈S是否为空;
    if (empty(s))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (3)依次进栈元素a,b,c,d,e;
    for (int i = 0; i < n; i++)
    {
        ElemType e;
        cin >> e;
        push(s, e);
    }
    // (4)判断链栈S是否为空;
    if (empty(s))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (5)输出链栈长度;
    cout << size(s) << endl;
    // (6)输出从栈顶到栈底的元素;
    display(s);
    // (7)输出出栈序列;
    while (!empty(s))
    {
        cout << top(s) << " ";
        pop(s);
    }
    cout << endl;
    // (8)判断链栈S是否为空;
    if (empty(s))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    // (9)释放链栈。
    destroy(s);
    return 0;
}

队列

#include <iostream>
#include <stdio.h>
using namespace std;
int n;

typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct
{
    LinkNode *front, *rear;
} LinkQueue;

// 初始化
void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 判队空
bool IsEmpty(LinkQueue Q)
{
    if (Q.front == Q.rear)
    {
        printf("队空\n");
        return true;
    }
    else
    {
        printf("队不空\n");
        return false;
    }
}

// 入队
void EnQueue(LinkQueue &L, int x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    L.rear->next = s; // 将新节点入队
    L.rear = s;       // 将尾指针后移
}

// 出队
bool DeQueue(LinkQueue &L, int &x)
{
    if (L.front == L.rear)
        return false;            // 空队
    LinkNode *p = L.front->next; // 查到队头元素
    x = p->data;
    L.front->next = p->next;
    if (p == L.rear)
    {
        L.front = L.rear;
    }
    free(p);
    return true;
}

// 输出队列
void PrintQueue(LinkQueue &L)
{

    LinkNode *p = L.front->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkQueue p;
    InitQueue(p);
    while (cin >> n)
    {
        if (n >= 10 && n <= 99)
        {
            EnQueue(p, n);
        }
        else if (n == -1)
        {
            DeQueue(p, n);
        }
        else if (n == -2)
        {
            PrintQueue(p);
        }
        else if (n == -3)
            break;
    }
    return 0;
}

树与二叉树

二叉树的遍历

题目:二叉树的遍历问题
http://qdacm.openjudge.cn/dsweeks/33/

// 输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。
//  思路:
//  前序序列的第一个值是根节点,将中序序列分成两部分。左边是左子树,右边是右子树
//  在左子树中,对应的前序序列的第二,是左子树的根节点,左边是其左子树,右边是其右子树
//  在右子树中,同理
//  当左子树为空,右子树为空时,结束
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
struct Node // 树的一个节点
{
    char data;
    Node *lChild, *rChild;
};

void postOrder(Node *root) // 树的后序遍历序列输出
{
    if (root == nullptr)
        return;

    postOrder(root->lChild);
    postOrder(root->rChild);
    cout << root->data;
}

int search(int num, char *in, int len) // 寻找中序序列中总根的位置
{

    for (int i = 0; i < len; i++)
        if (in[i] == num)
            return i;
    return -1;
}

Node *msn(char *pre, char *in, int len) // 递归构建树
{
    if (len <= 0)    // 当前中序遍历长度为零
        return NULL; // 树为空
    Node *root;
    root = new Node;
    int index = search(*pre, in, len);                                    // (先序遍历中的第一个数为根,当前中序序列,当前中序序列的长度)
    root->data = *pre;                                                    // 先序遍历中的第一个数为根
    root->lChild = msn(pre + 1, in, index);                               // 构建左树(先序遍历中的下一个数为根,整个中序序列,中序序列中对应左树的长度)
    root->rChild = msn(pre + index + 1, in + index + 1, len - index - 1); // 构建右树(先序遍历中的右半第一个数为根,中序序列右半,中序序列中对应右树的长度)
    return root;                                                          // 返回树的主根
}
int main()
{
    char *pre, *in;
    pre = new char[N];
    in = new char[N];
    cin >> pre;                      // 输入树的先序遍历,貌似这样写输入字符数组可以不用for
    cin >> in;                       // 输入树的中序遍历
    Node *root;                      // 树的根节点
    root = msn(pre, in, strlen(in)); // 构建出一棵树
    postOrder(root);                 // 输出后序遍历
    cout << endl;
    return 0;
}

并查集

题目:宗教信仰
http://bailian.openjudge.cn/practice/2524/

// 并查集
#include <iostream>
#include <stdio.h>
using namespace std;
#define ll long long
#define MAX 10000007
ll n, m, i, x, y, fa[1000000], ans, num = 1;

int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x != y)
        fa[x] = y;
}

int main()
{
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
        {
            break;
        }
        ans = n;
        for (int l = 1; l <= n; ++l)
        {
            fa[l] = l;
        }
        for (i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            x = find(x);
            y = find(y);
            if (x != y)
            {
                merge(x, y);
                ans -= 1;
            }
        }
        cout << "Case " << num++ << ": " << ans << endl;
    }

    return 0;
}

哈夫曼树

题目:Huffman编码树
http://bailian.openjudge.cn/practice/4080/

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define ll long long
#define MAX 10000007
ll n, node[200], ans, t;
// 哈夫曼树,不断从森林中选取权值最小的两棵树组合成新树
int main()
{
    cin >> t;
    while (t--)
    {
        ans = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> node[i];
        sort(node + 1, node + n + 1);
        for (int i = n; i >= 2; i--)
        {
            sort(node + 1, node + n + 1);
            ans += (node[1] + node[2]);
            node[1] = (node[1] + node[2]);
            node[2] = 1000000000;
        }
        cout << ans << endl;
    }
    return 0;
}

KMP

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;


const int N = 10000;
int cnt, ans[N];

int main()
{
    int n, m, q;
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s >> m >> q;
        cnt = 0;
        for (int i = 0; i <= (int)s.size() - m; i++)
        {
            int sum = 0;
            for (int j = i; j < i + m; j++)
                sum += s[j] - 'a' + 1;
            if (sum == q)
                ans[cnt++] = i;
        }
        cout << cnt << endl;
        for (int i = 0; i < cnt; i++)
        {
            for (int j = ans[i]; j < ans[i] + m; j++)
                cout << s[j];
            cout << endl;
        }
    }

    return 0;
}

深度优先搜索与广度优先搜索

题目:图的深度优先遍历与广度优先遍历
http://qdacm.openjudge.cn/ds2024006/02/

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;

int mapp[1000][1000], num, flag[1000], ans[1000];
int m, n, idx;

void dfs(int x) // 深搜
{
	if (flag[x])
	{
		return;
	}
	flag[x] = 1;
	ans[++idx] = x;
	for (int i = m; i >= 1; i--)
	{
		if (mapp[x][i])
			dfs(i);
	}
}

void bfs(int x) // 广搜
{
	if (flag[x])
		return;
	queue<int> q;
	q.push(x);
	ans[++idx] = x;
	flag[x] = 1;
	while (!q.empty())
	{
		for (int i = m; i >= 1; i--)
		{
			if (!flag[i] && mapp[q.front()][i])
			{
				ans[++idx] = i;
				flag[i] = 1;
				q.push(i);
			}
		}
		q.pop();
	}
}

int main()
{
	cin >> m >> n;				 // m个顶点和n条边
	char c;						 // 接收无用字符
	for (int i = 1; i <= m; i++) // 存入m个点,作用存疑
	{
		cin >> c >> num;
	}
	for (int i = 1; i <= n; i++) // 存入n条边
	{
		int x, y;
		cin >> c >> x >> c >> y;
		mapp[x][y] = mapp[y][x] = 1; // 邻接矩阵存图
	}
	for (int i = 1; i <= m; i++)
	{
		dfs(i);
	}
	for (int i = 1; i <= idx; i++) // 输出深搜序列
	{
		cout << "v" << ans[i] << " ";
	}
	cout << endl;

	// 将存储信息的数组初始化防止造成干扰
	idx = 0;
	memset(ans, 0, sizeof(ans));
	memset(flag, 0, sizeof(flag));

	for (int i = 1; i <= m; i++)
	{
		bfs(i);
	}
	for (int i = 1; i <= idx; i++) // 输出广搜序列
	{
		cout << "v" << ans[i] << " ";
	}
	return 0;
}

拓扑排序

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
using namespace std;

int n, m;
vector<vector<int>> ALgraph; // vector二维动态数组模拟邻接表,第一维为顶点表,第二维为边表
vector<int> ans, Indegree;   // ans中存放拓扑序列,Indegree存储各节点的入度
void TopsortbyQueue()
{
    priority_queue<int, vector<int>, greater<int>> q; // 递增优先队列,储存入度为0的顶点
    for (int i = 1; i <= n; ++i)
    { // 将入度为零的顶点放入队列中
        if (Indegree[i] == 0)
        {   
            q.push(i);
        }
    }
    while (!q.empty()) // 所有入度为零的点都被放进拓扑排序序列后结束
    {
        int u = q.top(); // 队头元素序号最小,拿出进行排序
        q.pop();
        ans.push_back(u);        // 队头放进拓扑排序序列
        for (int i : ALgraph[u]) // 遍历边表
        {
            Indegree[i]--;
            if (Indegree[i] == 0) // 入度为零入队
            {
                q.push(i);
            }
        }
    }
}

int main()
{
    cin >> n >> m;         // 顶点数n和弧数m
    ALgraph.resize(n + 1); // 一次性修改动态数组的空间大小,降低时间复杂度
    Indegree.resize(n + 1);
    for (int i = 1; i <= m; ++i) // 该条弧所关联的两个顶点编号
    {
        int u, v;
        cin >> u >> v;
        ALgraph[u].push_back(v); // 存入邻接表
        Indegree[v]++;           // 入度+1
    }
    TopsortbyQueue();
    for (int i : ans) // 输出拓扑排序后的序列
    {
        cout << "v" << i << " ";
    }
    return 0;
}

克洛斯卡尔最小生成树

题目:丛林中的路
http://bailian.openjudge.cn/practice/1251/

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int n, i, j, sum, cnt, fa[27], a;

struct E // 存储道路信息
{
    int a, b; // 起点和终点
    int w;    // 修路价格
} ed[10000];

bool cmp(E m, E n) // 结构体排序sort参数,以价格为关键字递减
{
    return m.w < n.w;
}

int find(int x) // 并查集查找x的父节点
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    while (cin >> n) // 村落数目n
    {
        sum = 0;
        cnt = 0;
        a = 0;
        int index = 0;
        if (n == 0)
            break;

        while (n-- > 1)
        {
            char x;
            int k;
            cin >> x >> k;          // x为村号,k为与该村庄连接的其他村庄个数
            a = x - 'A' + 1;        // 字母村号转化为数字编号
            for (j = 0; j < k; j++) // k个村庄的编号以及各自到起始村庄的道路维修费用
            {
                ed[++index].a = a; // 从1开始
                char y;
                cin >> y; // 村号
                ed[index].b = y - 'A' + 1;
                int w;
                cin >> w; // 道路价格
                ed[index].w = w;
            }
            // n--;
        }
        // 初始化并查集,所有点的父节点是它自己
        for (i = 1; i <= 27; i++)
            fa[i] = i;

        sort(ed + 1, ed + index + 1, cmp); // 将所有路按照价格从小到大排序

        for (i = 1; i <= index; i++) // 克洛斯卡尔构造最小生成树
        {
            int m = find(ed[i].a);
            int n = find(ed[i].b);
            if (m != n)
            {
                fa[m] = n;
                sum += ed[i].w;
                cnt++;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

弗洛伊德最短路

题目:兔子与樱花
http://qdacm.openjudge.cn/ds2024006/04/

#include <iostream>
#include <map>
#include <cstring>
#include <stdio.h>
using namespace std;
#define ll long long
#define MAX 10000007

map<string, int> map1;
map<int, string> map2;
ll step[35][35];
ll point[35][35];
ll p, q, r, d;
string t1, t2;

// 弗洛伊德最短路
void floyd()
{
    for (int k = 0; k < p; k++)
    {
        for (int i = 0; i < p; i++)
        {
            for (int j = 0; j < p; j++)
            {
                if (step[i][j] > step[i][k] + step[k][j]) // 点k与i,j任意一点不相连时为false,不是目前最短路径时为false,i,j不相连时为false
                {
                    step[i][j] = step[i][k] + step[k][j];
                    point[i][j] = point[i][k];
                }
            }
        }
    }
}

int main()
{
    // dist[i][j]表示i到j的最短距离,距离极大表示两个地点不连通
    for (int i = 0; i < 35; i++)
    {
        for (int j = 0; j < 35; j++)
        {
            step[i][j] = MAX;
        }
        step[i][i] = 0; // 一个地点到自身的距离为零
    }

    // point[i][j]表示从i到j的最短路线中从i出发的下一个结点,记录最短路径
    for (int i = 0; i < 35; i++)
    {
        for (int j = 0; j < 35; j++)
        {
            point[i][j] = j;
        }
    }

    cin >> p; // 存入p个地点
    for (int i = 0; i < p; i++)
    {
        cin >> t1;
        map1[t1] = i; // 将地名映射为数字编号
        map2[i] = t1;
    }

    cin >> q;
    for (int i = 0; i < q; i++) // 存入两个点之间的距离
    {
        cin >> t1 >> t2 >> d;
        step[map1[t1]][map1[t2]] = step[map1[t2]][map1[t1]] = d;
    }

    floyd(); // 弗洛伊德求最短路

    cin >> r; // R次询问最短路径
    while (r--)
    {
        cin >> t1 >> t2;
        if (t1 != t2)
        {
            int x = point[map1[t1]][map1[t2]];
            cout << t1 << "->(" << step[map1[t1]][x] << ")->";
            while (x != map1[t2])
            {
                cout << map2[x] << "->(" << step[x][point[x][map1[t2]]] << ")->";
                // 更新下一结点
                x = point[x][map1[t2]];
            }
        }
        cout << t2 << endl;
    }
    return 0;
}

排序

快速排序

void QuickSort(int array[], int low, int high) {
    int i = low; 
    int j = high;
    if(i >= j) {
        return;
    }
 
    int temp = array[low];
    while(i != j) {
        while(array[j] >= temp && i < j) {
            j--;
        }
	while(array[i] <= temp && i < j) {
            i++;
        }
	if(i < j) {
            swap(array[i], array[j]);
        }
    }
 
    //将基准temp放于自己的位置,(第i个位置)
    swap(array[low], array[i]);
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

直接插入排序

#include<bits/stdc++.h>

using namespace std;

void InsertSort(int a[],int l)
{
    int temp;
    int j;
    for(int i=1;i<l;i++)
    {
        if(a[i]<a[i-1])
        {
            temp=a[i];
            for(j=i-1;j>=0&&temp<a[j];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;

        }
        for(int k=0;k<l;k++)
            cout<<a[k]<<" ";
        cout<<endl;

    }
}


int main()
{
    int a[10]={2,5,8,3,6,9,1,4,7};
    int b[10]={1,2,3,4,5,6,7,8,9};
    int len=9;
    InsertSort(a,len);
    return 0;
}

希尔排序

template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

简单选择排序

void selectSort(int arr[], int len)
{
	int i, j;
	int min; //待排序数组中最小值的下标
	int tmp;
	for (i = 0; i < len - 1; ++i)//i = 0,第一次待排数组为所有数
	{   
		min = i;
		for (j = i + 1; j < len; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;//
			}
		}
		//将arr[i]与arr[min]交换位置
		tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
	}
}
void selectShow(int arr[], int len)
{
	for (int i = 0; i < len; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = {59,26,245,21,6,10,16};
	int len = sizeof(arr) / sizeof(arr[0]);
	selectShow(arr, len);
	selectSort(arr, len);
	selectShow(arr, len);
	return 0;
}

冒泡排序

#include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1])
                                swap(arr[j], arr[j + 1]);
}
int main() {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;
        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (float) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ' '<<endl;
        return 0;
}

热门相关:掘金人生   绝色符师:龙皇的狂傲妃   九星之主   美食萌后:皇上,休了你   翻天