2022数据结构习题（知产）

函数题

01-复杂度3 二分查找

Position BinarySearch(List L,ElementType X){
    int l=1,r=L->Last;
    while(l<=r){
        int mid = l+(r-l)/2;
        if(L->Data[mid] == X) return mid;
        else if(L->Data[mid]<X) l = mid+1;
        else r = mid;
    }
    return NotFound;
}
1
2
3
4
5
6
7
8
9
10

02-线性结构2 在一个数组中实现两个堆栈

Stack CreateStack(int MaxSize){
    ElementType* data = (ElementType*)malloc(sizeof(ElementType)*MaxSize);
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = data;
    S->Top1 = -1;
    S->Top2= MaxSize;
    S->MaxSize = MaxSize;
    return S;
}
bool Push(Stack S,ElementType X,int Tag){
    if(S->Top2-S->Top1 == 1){
        printf("Stack Full\n");
        return false;
    }
    if (Tag == 1){
        S->Top1+=1;
        S->Data[S->Top1] = X;
    }else{
        S->Top2 -=1;
        S->Data[S->Top2] = X;
    }
    return true;
}
ElementType Pop(Stack S,int Tag){
    ElementType num;
    if(Tag == 1){
        if(S->Top1 == -1){
            printf("Stack 1 Empty\n");
            return ERROR;
        }
        num = S->Data[S->Top1];
        S->Top1--;
    }else{
        if(S->Top2 == S->MaxSize){
            printf("Stack 2 Empty\n");
            return ERROR;
        }
        num = S->Data[S->Top2];
        S->Top2++;
    }
    return num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

03-二叉树1 二叉树的遍历

void InorderTraversal(BinTree BT){
    if(BT == NULL) return;
    InorderTraversal(BT->Left);
    printf(" %c",BT->Data);
    InorderTraversal(BT->Right);
}
void PreorderTraversal(BinTree BT){
    if(BT == NULL) return;
    printf(" %c",BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}
void PostorderTraversal(BinTree BT){
    if(BT == NULL) return;
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf(" %c",BT->Data);
}
void LevelorderTraversal(BinTree BT){
    if(BT == NULL) return;
    BinTree queue[10000];
    ElementType head,tail;
    head = tail = 0;
    queue[tail++] = BT;
    while(head<tail){
        BinTree q = queue[head];
        printf(" %c",q->Data);
        if(q->Left != NULL) queue[tail++]=q->Left;
        if(q->Right != NULL) queue[tail++]=q->Right;
        head++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

05-散列1 线性探测法的查找函数

Position Find(HashTable H, ElementType Key){
    Position index = Hash(Key,H->TableSize);
    int cnt = 0;
    while(cnt < H->TableSize){
        if(H->Cells[index].Info != Legitimate ||
           H->Cells[index].Data == Key)
            return index;
        index = (index+1)%H->TableSize;
        cnt++;
    }
    return ERROR;
}
1
2
3
4
5
6
7
8
9
10
11
12

06-图1 邻接矩阵存储图的深度优先遍历

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ){
    Visit(V);
    Visited[V] = true;
    int i = 0;
    for(;i<Graph->Nv;++i){
        if(Visited[i]==false && Graph->G[V][i]!=INFINITY){
            DFS(Graph,i,Visit);
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12

编程题

01-复杂度1 最大子列和问题

#include
int main(){
    int n;
    scanf("%d",&n);
    int max_sum = 0,now_sum=0;
    int i = 0,num;
    for(;i<n;++i){
        scanf("%d",&num);
        now_sum += num;
        if(now_sum<0){
            now_sum=0;
        }
        max_sum = max_sum>now_sum?max_sum:now_sum;
    }
    printf("%d",max_sum);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

02-线性结构1 一元多项式的乘法与加法运算

#include
typedef struct Polynomial {
    int coef, exp;//coef是系数，exp是指数
} Poly;
/*崩纱卡拉卡*/
int mul_res[2024];
int add_res[2024];
void polyAdd(Poly a[], Poly b[], int n, int m) {
    int i;
    for (i = 0;i < n;++i)    add_res[a[i].exp] += a[i].coef;
    for (i = 0;i < m;++i)    add_res[b[i].exp] += b[i].coef;
}
void polyMulti(Poly a[], Poly b[], int n, int m) {
    int i, j;
    int coef, exp;
    for (i = 0;i < n;++i) {
        for (j = 0;j < m;++j) {
            coef = a[i].coef * b[j].coef;
            exp = a[i].exp + b[j].exp;
            mul_res[exp] += coef;
        }
    }
}
void output(int res[]) {
    int flag = 0;//判别是否出现0多项式
    int i;
    for (i = 2022;i >= 0;--i) {
        if (res[i] != 0) {
            if (flag == 1)    printf(" ");//除了第一次的输出，其余的都要先加空格
            printf("%d %d", res[i], i);
            flag = 1;
        }
    }
    if (flag == 0) printf("0 0");
    printf("\n");
}
int main() {
    int n, m, i;
    Poly poly1[1080], poly2[1080];
    memset(mul_res, 0, sizeof(mul_res));
    memset(add_res, 0, sizeof(add_res));
    scanf("%d", &n);
    for (i = 0;i < n;++i)     scanf("%d%d", &poly1[i].coef, &poly1[i].exp);
    scanf("%d", &m);
    for (i = 0;i < m;++i)     scanf("%d%d", &poly2[i].coef, &poly2[i].exp);
    polyAdd(poly1, poly2, n, m);
    polyMulti(poly1, poly2, n, m);
    output(mul_res);
    output(add_res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

02-线性结构3 列车调度

#include
#define N 100005
int binSearch(int* a, int len,int target) {
    int l = 0, r = len - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
int main() {
    int n,train;
    int rails[N];
    int rail_num = 0;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &train);
        if (rail_num == 0 || rails[rail_num - 1] < train) {
            rails[rail_num++] = train;
        }
        else {
            int t = binSearch(rails, rail_num, train);
            rails[t] = train;
        }
    }
    printf("%d\n", rail_num);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

03-树1 树的同构

#include
#include 
#define N 20
#define Null -1
typedef struct Node {
    char data;
    int lchild;
    int rchild;
}node;
node tree1[N], tree2[N];
int trans(char c) {
    if (c == '-') return Null;
    return c - '0';
}
int buildTree(node tree[]) {
    int n, i, sum = 0;
    char c, l, r;
    scanf("%d", &n);
    if (n == 0) return Null;
    for (i = 0;i < n;++i) {
        getchar();
        scanf("%c %c %c", &c, &l, &r);
        tree[i].data = c;
        tree[i].lchild = trans(l);
        tree[i].rchild = trans(r);
        sum += i;
        if (tree[i].lchild != Null) sum -= tree[i].lchild;
        if (tree[i].rchild != Null) sum -= tree[i].rchild;
    }
    return sum;
}
int isIsomorphic(int root1, int root2) {
    if (root1 == Null && root2 == Null) return 1;
    if (root1 == Null || root2 == Null) return 0;
    if (tree1[root1].data != tree2[root2].data) return 0;
    return (isIsomorphic(tree1[root1].lchild, tree2[root2].lchild) && isIsomorphic(tree1[root1].rchild, tree2[root2].rchild)) ||
        ((isIsomorphic(tree1[root1].lchild, tree2[root2].rchild) && isIsomorphic(tree1[root1].rchild, tree2[root2].lchild)));
    /*判断两种情况：1.左边=左边且右边=右边，
       2.或者交换一下，左边 = 右边，右边 = 左边
        满足一种情况就可以了，所以用||
    */
}
int main() {
    int root1 = buildTree(tree1);
    int root2 = buildTree(tree2);
    if (isIsomorphic(root1, root2)) printf("Yes\n");
    else printf("No\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

04-二叉搜索树1 是否同一棵二叉搜索树

#include
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;
typedef Node* binTree;
binTree insert(binTree root, int x) {
    if (root == NULL) {
        root = (Node*)malloc(sizeof(Node));
        root->data = x;
        root->left = root->right = NULL;
    }
    else if ((root->data) > x) root->left = insert(root->left, x);
    else root->right = insert(root->right, x);
    return root;
}
int judge(binTree a, binTree b) {
    if (a == NULL && b == NULL) return 1;
    if (a == NULL || b == NULL) return 0;
    return (a->data == b->data) && judge(a->left, b->left) && judge(a->right, b->right);
}
binTree buildBST(int n) {
    int x, i;
    binTree root = NULL;
    for (i = 0;i < n;++i) {
        scanf("%d", &x);
        root = insert(root, x);
    }
    return root;
}
int main() {
    int n, l, x;
    int i;
    while (scanf("%d", &n) && n) {
        scanf("%d", &l);
        binTree prim = buildBST(n);
        while (l--) {
            binTree tmp = buildBST(n);
            if (judge(prim, tmp)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

04-二叉平衡树1 Root of AVL Tree

#include 
#include
typedef struct node* nodePtr;
struct node {
    int val_;
    nodePtr left;
    nodePtr right;
};
nodePtr rotateLeft(nodePtr root) {//RR错误要左旋一次
    nodePtr t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}
nodePtr rotateRight(nodePtr root) {//ll错误就说右旋了
    nodePtr t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}
nodePtr rotateLeftRight(nodePtr root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
nodePtr rotateRightLeft(nodePtr root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
int max(int a, int b) {
    return a > b ? a : b;
}
int getHeight(nodePtr root) {
    if (root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
nodePtr insert(nodePtr root, int val) {
    if (root == NULL) {
        root = (nodePtr)malloc(sizeof(struct node));
        root->val_ = val;
        root->left = root->right = NULL;
    }
    else if (val < root->val_) {
        root->left = insert(root->left, val);
        if (getHeight(root->left) - getHeight(root->right) == 2)
            root = val < root->left->val_ ? rotateRight(root) : rotateLeftRight(root);
    }
    else {
        root->right = insert(root->right, val);
        if (getHeight(root->left) - getHeight(root->right) == -2)
            root = val > root->right->val_ ? rotateLeft(root) : rotateRightLeft(root);
    }
    return root;
}
int main() {
    int n, val;
    scanf("%d", &n);
    nodePtr root = NULL;
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d", root->val_);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

05-堆 堆中的路径

#include
#define Max 1024
#define Min -10024
int H[Max], size = 0;

void insert(int x) {
    int i;
    for (i = size;H[i / 2] > x;i /= 2)
        H[i] = H[i / 2];
    H[i] = x;
    size++;
}
int main() {
    int n, m, i, x, k;
    scanf("%d%d", &n, &m);
    H[size++] = Min;/*从1开始放，0是空缺的，岗哨*/
    for (i = 0;i < n;++i) {
        scanf("%d", &x);
        insert(x);
    }
    for (i = 0;i < m;++i) {
        scanf("%d", &k);
        printf("%d", H[k]);
        while (k > 1) {
            k /= 2;
            printf(" %d", H[k]);
        }
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

05-哈夫曼编码 哈夫曼编码

#include
#include
#include
#define MAXSIZE 64
typedef struct TNode* HuffmanTree;
/*我也不会，blog:https://blog.csdn.net/m0_37149062/article/details/105641639*/
struct TNode {
    int weight_;
    HuffmanTree Left;
    HuffmanTree Right;
};//哈夫曼树标准定义
typedef struct HeapNode* MinHeap;
struct HeapNode {
    HuffmanTree Elements[MAXSIZE];
    int size_;
};
char ch[MAXSIZE];//输入的字符
int N, w[MAXSIZE], total_codes;//编码中含字符个数，以及频率 最优编码长度
MinHeap createHeap() {
    MinHeap H;
    H = (MinHeap)malloc(sizeof(struct HeapNode));
    H->size_ = 0;
    H->Elements[0] = (HuffmanTree)malloc(sizeof(struct TNode));
    H->Elements[0]->weight_ = -1;
    H->Elements[0]->Left = H->Elements[0]->Right = NULL;
    return H;
}
//创建哈夫曼树结点，这里注意初始化其权重和左右儿子
HuffmanTree createHuffman() {
    HuffmanTree  T;
    T = (HuffmanTree)malloc(sizeof(struct TNode));
    T->Left = T->Right = NULL;
    T->weight_ = 0;
    return T;
}
//最小堆的插入
void insert(MinHeap H, HuffmanTree X) {
    int i = ++H->size_;
    for (;H->Elements[i / 2]->weight_ > X->weight_;i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}
//最小堆删除元素
HuffmanTree deleteMin(MinHeap H) {
    HuffmanTree MinTtem, temp;
    int Parent, Child;
    MinTtem = H->Elements[1];
    temp = H->Elements[H->size_--];
    for (Parent = 1;Parent * 2 <= H->size_;Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->size_) && (H->Elements[Child]->weight_ > H->Elements[Child + 1]->weight_))
            Child++;
        if (temp->weight_ <= H->Elements[Child]->weight_)
            break;
        else
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
    return MinTtem;
}
//构建哈夫曼树
HuffmanTree buildHuffman(MinHeap H) {
    HuffmanTree T;
    int num = H->size_;
    for (int i = 1;i < num;i++) {
        T = createHuffman();
        T->Left = deleteMin(H);
        T->Right = deleteMin(H);
        T->weight_ = T->Left->weight_ + T->Right->weight_;
        insert(H, T);
    }
    T = deleteMin(H);
    return T;
}
//根据哈夫曼树，计算最优编码长度并返回
int WPL(HuffmanTree root, int depth) {
    if ((root->Left == NULL) && (root->Right == NULL))
        return depth * root->weight_;
    else
        return WPL(root->Left, depth + 1) + WPL(root->Right, depth + 1);
}

//判断是否为最优编码;
int judge() {
    HuffmanTree T, p;
    char chl, * codes;
    codes = (char*)malloc(sizeof(char) * MAXSIZE);
    int length = 0, flag = 1, wgh, j;
    T = createHuffman();

    for (int i = 0;i < N;i++) {
        getchar();
        scanf("%c %s", &chl, codes);
        if (strlen(codes) >= N)
            flag = 0;
        else {
            for (j = 0;chl != ch[j];j++);
            wgh = w[j];
            p = T;
            for (j = 0;j < strlen(codes);j++) {
                if (codes[j] == '0') {
                    if (!p->Left)
                        p->Left = createHuffman();
                    p = p->Left;

                }
                else if (codes[j] == '1') {
                    if (!p->Right)
                        p->Right = createHuffman();
                    p = p->Right;
                }
                if (p->weight_) flag = 0;
            }
            if (p->Left || p->Right)
                flag = 0;
            else
                p->weight_ = wgh;
        }
        length += strlen(codes) * p->weight_;
    }
    if (length != total_codes)
        flag = 0;
    return flag;
}

int main() {
    int M;
    HuffmanTree tmp, ROOT;
    scanf("%d", &N);
    MinHeap H = createHeap();
    //根据输入的字符已经其频率，一个个插入构建最小堆
    for (int i = 0;i < N;i++) {
        getchar();
        scanf("%c %d", &ch[i], &w[i]);
        tmp = createHuffman();
        tmp->weight_ = w[i];
        insert(H, tmp);
    }
    ROOT = buildHuffman(H);
    total_codes = WPL(ROOT, 0);
    scanf("%d", &M);
    for (int i = 0;i < M;i++) {
        if (judge())    printf("Yes\n");
        else    printf("No\n");
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

06-散列查找1 电话聊天狂人

#include
#include
#include
#define KEYLEN 11
typedef char ElementType[KEYLEN + 1];
#define MAXD 5/*参与散列映射计算的字符个数，就是最后5位*/
typedef int Index;

typedef struct LNode* ptr_LNode;
struct LNode
{
    ElementType data_;
    ptr_LNode next;
    int count_;
};
typedef ptr_LNode Position;
typedef ptr_LNode List;

typedef struct Tb1Node* HashTable;
struct Tb1Node
{
    int size_;
    List Heads;
};
int isPrime(int x) {
    int i;
    for (i = 2;i < (int)sqrt(x) + 1;++i) {
        if ((x % i) == 0) return 0;
    }
    return 1;
}
int nextPrime(int n) {
    int i;
    int p = (n % 2 == 0) ? n + 1 : n + 2;
    for (i = p;;i=i+2) {
        if (isPrime(i)) return i;
    }
    return -1;
}
HashTable createHashTable(int table_size) {
    HashTable H;
    int i;
    H = (HashTable)malloc(sizeof(struct Tb1Node));
    H->size_ = nextPrime(table_size);
    H->Heads = (List)malloc(H->size_ * sizeof(struct LNode));
    for (i = 0;i < H->size_;++i) {
        H->Heads[i].data_[0] = '\0';
        H->Heads[i].next = NULL;
        H->Heads[i].count_ = 0;
    }
    return H;
}
int Hash(int key, int p) {
    /*除留余数法散列函数*/
    return key % p;
}
Position find(HashTable H, ElementType key) {
    Index pos = Hash(atoi(key+KEYLEN-MAXD), H->size_);
    Position p = H->Heads[pos].next;
    while (p&&strcmp(p->data_,key))
        p = p->next;
    return p;
}
int insert(HashTable H, ElementType key) {
    Position p, new_cell;
    Index pos;
    p = find(H, key);
    if (!p) {/*没找到就插入*/
        new_cell = (Position)malloc(sizeof(struct LNode));
        strcpy(new_cell->data_, key);
        new_cell->count_ = 1;
        pos = Hash(atoi(key + KEYLEN - MAXD), H->size_);
        new_cell->next = H->Heads[pos].next;
        H->Heads[pos].next = new_cell;
        return 1;
    }
    else {
        p->count_++;
        return 0;
    }
}
void scanAndOutput(HashTable H) {
    int i, max_cnt, person_cnt;
    max_cnt = person_cnt = 0;
    List ptr;
    ElementType min_phone;
    min_phone[0] = '\0';
    for (i = 0;i < H->size_;++i) {
        ptr = H->Heads[i].next;
        while (ptr)
        {
            if (ptr->count_ > max_cnt) {
                max_cnt = ptr->count_;
                strcpy(min_phone, ptr->data_);
                person_cnt = 1;
            }
            else if (ptr->count_ == max_cnt) {
                person_cnt++;
                if (strcmp(min_phone, ptr->data_) > 0)
                    strcpy(min_phone, ptr->data_);
            }
            ptr = ptr->next;
        }
    }
    printf("%s %d", min_phone, max_cnt);
    if (person_cnt > 1) printf(" %d", person_cnt);
    printf("\n");
}
void destroyHashTable(HashTable H) {
    Position pos, tmp;
    int i;
    for (i = 0;i < H->size_;++i) {
        pos = H->Heads[i].next;
        while (pos)
        {
            tmp = pos->next;
            free(pos);
            pos=tmp;
        }
    }
    free(H->Heads);
    free(H);
}
int main() {
    // printf("%d", nextPrime(7));
    int n, i;
    ElementType key;
    scanf("%d", &n);
    //创建散列表
    HashTable H = createHashTable(2*n);
    //读入号码，插入表中
    for (i = 0;i < n;++i) {
        scanf("%s", key);insert(H, key);
        scanf("%s", key);insert(H, key);
    }
    //扫描输出狂人
    scanAndOutput(H);
    destroyHashTable(H); 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

07-图的遍历 列出连通集

#include
#include
#define N 20
#define INF 0x3f3f3f3f
int G[N][N];
//DFS
int vis[N];
int ans[N];
void DFS(int n, int v) {
    int i;
    printf("%d ", v);
    vis[v] = 1;
    for (i = 1;i < n;++i) {
        if (!vis[i] && G[v][i] == 1) {
            DFS(n, i);
        }
    }
}
int queue[N];
int head = 0, tail = 0;
void BFS(int n, int v) {
    int i;
    printf("%d ", v);
    vis[v] = 1;
    queue[tail++] = v;
    while (head < tail) {
        int tmp = queue[head++];
        for (i = 0;i < n;++i) {
            if (!vis[i] && G[tmp][i] == 1) {
                printf("%d ", i);
                vis[i] = 1;
                queue[tail++] = i;
            }
        }
    }
}
void init() {
    int i, j;
    memset(vis, 0, sizeof(vis));
    for (i = 0;i < N;++i)
        for (j = 0;j < N;++j)
            G[i][j] == (i == j) ? 0 : INF;
}
int main() {
    int n, e, i, v1, v2;
    init();
    scanf("%d%d", &n, &e);
    for (i = 0;i < e;++i) {
        scanf("%d%d", &v1, &v2);
        G[v1][v2] = G[v2][v1] = 1;
    }
    for (i = 0;i < n;++i) {
        if (!vis[i]) {
            printf("{ ");
            DFS(n, i);
            printf("}\n");
        }
    }
    memset(vis, 0, sizeof(vis));
    for (i = 0;i < n;++i) {
        if (!vis[i]) {
            printf("{ ");
            BFS(n, i);
            printf("}\n");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

08-最短路径 哈利·波特的考试（方法一 floyd）

#include
#include
#define N 201
#define INF 0X3F3F3F3F
int G[N][N];
void floyd(int n) {
    int i, j, k;
    for (k = 1;k <= n;++k)
        for (i = 1;i <= n;++i)
            for (j = 1;j <= n;++j)
                if (G[i][j] > G[i][k] + G[k][j])
                    G[i][j] = G[i][k] + G[k][j];
}
int main() {
    int n, m, i, j, v1, v2, w, k;
    for (i = 0;i < N;++i)
        for (j = 0;j < N;++j)
            G[i][j] = (i == j) ? 0 : INF;
    scanf("%d%d", &n, &m);
    for (i = 0;i < m;++i) {
        scanf("%d%d%d", &v1, &v2, &w);
        G[v1][v2] = G[v2][v1] = w;
    }
    floyd(n);
    int min_v=0, max_path=INF;
    for (i = 1;i <= n;++i) {
        int tmp_path = 0;
        for (j = 1;j <= n;++j) {
            if (G[i][j] == INF) {
                printf("0\n");
                return 0;
            }
            tmp_path = tmp_path > G[i][j] ? tmp_path : G[i][j];
        }
        if (tmp_path < max_path) {
            min_v = i;
            max_path = tmp_path;
        }
    }
    printf("%d %d\n", min_v, max_path);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

08-最短路径 哈利·波特的考试（方法二 dijkstra）

#include
#include
#define N 201
#define INF 0X3F3F3F3F
int G[N][N];
int vis[N];
int dis[N];
void init() {
    int i;
    memset(vis, 0, sizeof(vis));
    for (i = 0;i < N;++i) dis[i] = INF;
}
int dijkstra(int n, int v) {
    int i, j;
    vis[v] = 1;
    for (i = 0;i < n;++i) dis[i] = G[v][i];
    for (i = 1;i < n;++i) {
        int min_dis = INF;
        int min_v = 0;
        for (j = 0;j < n;++j) {
            if (!vis[j] && dis[j] < min_dis) {
                min_dis = dis[j];
                min_v = j;
            }
        }
        if (min_dis == INF) break;
        vis[min_v] = 1;
        for (j = 0;j < n;++j) {
            if (!vis[j] && dis[j] > min_dis + G[min_v][j]) {
                dis[j] = min_dis + G[min_v][j];
            }
        }
    }
    if (i == n) {
        int max_path = 0;
        for (j = 0;j < n;++j) {
            max_path = (max_path > dis[j]) ? max_path : dis[j];
        }
        return max_path;
    }
    else  return -1;
}
void findMinV(int n) {
    int i,min_v = 0, max_path = INF;
    for (i = 0;i < n;++i) {
        init();
        int path = dijkstra(n, i);
        if (path == -1) {
            printf("0\n");
            return;
        }
        if (max_path > path) {
            min_v = i;
            max_path = path;
        }
    }
    printf("%d %d\n", min_v+1, max_path);
}
int main() {
    int n, m, i, j;
    int v1, v2, w;
    for (i = 0;i < N;++i)
        for (j = 0;j < N;++j)
            G[i][j] = (i == j) ? 0 : INF;
    scanf("%d%d", &n, &m);
    for (i = 0;i < m;++i) {
        scanf("%d%d%d", &v1, &v2, &w);
        G[v1 - 1][v2 - 1] = G[v2 - 1][v1 - 1] = w;
    }
    findMinV(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

09-最小生成树 公路村村通

#include
#include
#define N 1005
#define INF 0x3f3f3f3f
int G[N][N];//图
int vis[N];//第i个顶点是否加入点集
int dis[N];//当前点集到所有点的最短距离
void init() {//初始化相关参数
    int i, j;
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    for (i = 0;i < N;++i) {
        for (j = 0;j < N;++j)
            G[i][j] = (i == j) ? 0 : INF;
    }
}
void prim(int n) {
    int i, j, next_v;
    vis[0] = 1;//加入顶点0
    for (i = 0;i < n;++i)//加入顶点0后，更新距离
        dis[i] = G[0][i];
    for (i = 1;i < n;++i) {//继续找n-1个点
        int Min = INF;
        for (j = 1;j < n;++j) {//找到未加入点集的点，该点dis距离最小
            if (!vis[j] && Min > dis[j]) {
                Min = dis[j];
                next_v = j;
            }
        }
        if (Min == INF)   break;//说明没找到，即无法生成MST
        vis[next_v] = 1;//记得标记，已加入的点
        for (j = 0;j < n;++j) {//更新距离
            if (!vis[j] && dis[j] > G[next_v][j])
                dis[j] = G[next_v][j];
        }
    }
    int ans = 0;
    if (i == n) {
        for (i = 0;i < n;++i) ans += dis[i];
        printf("%d\n", ans);
    }
    else    printf("-1\n");
}
int main() {
    int n, m;
    int v1, v2, w;
    init();
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d", &v1, &v2, &w);
        G[v1 - 1][v2 - 1] = G[v2 - 1][v1 - 1] = w;
    }
    prim(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

09-拓扑排序 任务调度的合理性

#include
#include
#define N 105
int G[N][N];
int in[N];
int queue[N];
int canTopoSort(int n) {
    int head, tail,i;
    int cnt = 0;
    head = tail = 0;
    for (i = 0;i < n;++i) {
        if (in[i] == 0) {
            queue[tail++] = i;
        }
    }
    while (head < tail) {
        int v = queue[head++];
        cnt++;
        for (i = 0;i < n;++i) {
            if (G[v][i]) {
                in[i]--;
                if (in[i] == 0) queue[tail++] = i;
            }
        }
    }
    return cnt == n;
}
int main() {
    int n, i, k, j, v;
    memset(in, 0, sizeof(in));
    scanf("%d", &n);
    for (i = 0;i < n;++i) {
        scanf("%d", &k);
        for (j = 0;j < k;++j) {
            scanf("%d", &v);
            G[i][v - 1] = 1;
            in[v - 1]++;
        }
    }
    if (canTopoSort(n)) printf("1\n");
    else printf("0\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

如果各位同学有哪里不明白可以与我一起讨论，预祝各位数据结构考试顺利通过！