C语言数据结构-2020级ICODING答案分享

客官°小女子只卖身不卖艺 2022-11-14 13:27 228阅读 0赞

详细学习版本请看[https://blog.csdn.net/aiqq136/article/details/114590856][https_blog.csdn.net_aiqq136_article_details_114590856]

**目录**

顺序表 删除指定范围

顺序表 删除重复

顺序表 数据调整

链表 删除范围内结点

链表 倒数查找

链表 合并

队列 循环链表表示队列

栈 后缀表达式计算

串-串比较

串-串替换

串-块链串

矩阵加法

十字链表

树与二叉树--先序遍历

树与二叉树--路径

树与二叉树--共同祖先

树与二叉树--树转二叉树

图-邻接矩阵

图-邻接表1

图-邻接表2

查找-哈希表创建

查找-哈希表添加

查找-AVL添加

排序-堆辅助函数

排序-堆初始化

排序-堆化

排序-数组合并

--------------------

# 顺序表 删除指定范围 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    void del_x2y(SeqList* L, ElemType x, ElemType y)
    {
        int i = 0, j = 0;
        for (i = 0; i <= L->last; i++) {
            if (L->elem[i] < x || L->elem[i] > y) {
                L->elem[j++] = L->elem[i]; //在范围外，则继续赋值
            }
        }
        L->last = j - 1; //储存下标位置
    }

# 顺序表 删除重复 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    void del_dupnum(SeqList* L)
    {
        int min = L->elem[0];
        int tmp = L->elem[0];
        for (int i = 1; i <= L->last; i++) {
            if (L->elem[i] == tmp)
                L->elem[i] = min;
            else
                tmp = L->elem[i];
        }
        int p = 1, q = 1;
        while (q <= L->last) {
            if (L->elem[q] != min) {
                L->elem[p] = L->elem[q];
                p++;
            }
            q++;
        }
        L->last = p - 1;
    }

# 顺序表 数据调整 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    //要求左奇数右偶数
    void odd_even(SeqList* L)
    {
        int* left = &(L->elem[0]);
        int* right = &(L->elem[L->last]);
        int tmp;
        while (left < right) {
            //左边是偶数
            if (*left % 2 == 0) {
                //右边是奇数
                if (*right % 2 == 1) {
                    //交换
                    tmp = *left;
                    *left = *right;
                    *right = tmp;
                    left++;
                    right--;
                } else {
                    right--;
                }
            } else {
                //左边是奇数
                left++;
            }
        }
    }

# 链表 删除范围内结点 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
    {
        LinkList left = NULL;
        LinkList right = NULL;
        LinkList tmp = NULL;
        //找到左指针
        while (L->next != NULL) {
            if ((L->next->data > mink) && (L->next->data < maxk)) {
                left = L;
                L = L->next;
                break;
            } else {
                L = L->next;
            }
        }
        //找到右指针
        while (L->next != NULL) {
            if ((L->data > mink) && (L->data < maxk)) {
                tmp = L;
                L = L->next;
                free(tmp);
            } else {
                right = L;
                break;
            }
        }
        if (right == NULL)
            return;
        left->next = right;
    }

# 链表 倒数查找 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    int lnk_search(LinkList L, int k, ElemType* p_ele)
    {
        //带计数器遍历链表,得到链表长度
        int count = 1;
        LinkList tmp = L;
        int i = 0;
        while (tmp->next != NULL) {
            tmp = tmp->next;
            count++;
        }
        tmp = L;
        //遍历count-k次链表
        if (k > count || k <= 0) {
            return 0;
        } else {
            for (i = 0; i < count - k; i++) {
                tmp = tmp->next;
            }
            *p_ele = tmp->data;
            return 1;
        }
    }

# 链表 合并 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    void lnk_merge(LinkList A, LinkList B, LinkList C)
    {
        LinkList tmp = C; //记录最末尾的位置
        LinkList tmpA = A->next;
        LinkList tmpB = B->next;
    
        while (1) {
            if (tmpA == NULL) {
                return C;
            } else {
                tmp->next = tmpA;
                tmp = tmp->next;
                tmpA = tmpA->next;
            }
    
            if (tmpB == NULL) {
                return C;
            } else {
                tmp->next = tmpB;
                tmp = tmp->next;
                tmpB = tmpB->next;
            }
        }
    }

# 队列 循环链表表示队列 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    bool init_queue(LinkQueue* LQ) //二重指针
    {
        *LQ = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
        if (*LQ == NULL)
            return false;
        (*LQ)->next = (*LQ);
        return true;
    }
    
    bool enter_queue(LinkQueue* LQ, ElemType x)
    {
        LinkQueue p = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
        if (p == NULL)
            return false;
        p->data = x;
        p->next = (*LQ)->next;
        (*LQ)->next = p;
        (*LQ) = p;
        return true;
    }
    
    bool leave_queue(LinkQueue* LQ, ElemType* x)
    {
        if ((*LQ)->next == (*LQ))
            return false;
        LinkQueue p = (*LQ)->next->next;
        *x = p->data;
        if ((*LQ)->next->next != (*LQ)) //多个节点
        {
            (*LQ)->next->next = (*LQ)->next->next->next;
        } else //两个节点
        {
            (*LQ) = (*LQ)->next;
            (*LQ)->next = (*LQ);
        }
        free(p);
        return true;
    }

# 栈 后缀表达式计算 #

#include "list.h" // 请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    int compute_reverse_polish_notation(char* str)
    {
        int i = 0;
        Stack S;
        init_stack(&S);
        ElemType number_to_push, num1, num2;
        while (str[i] != '\0') {
            if (str[i] != ' ') {
                if (str[i] >= '0' && str[i] <= '9') {
                    number_to_push = 0;
                    while (str[i] != ' ' && str[i]) {
                        number_to_push = number_to_push * 10 + (str[i] - '0');
                        i++;
                    }
                    push(&S, number_to_push);
                } else {
                    pop(&S, &num2);
                    pop(&S, &num1);
                    switch (str[i]) {
                    case '+': {
                        num1 += num2;
                        break;
                    }
                    case '-': {
                        num1 -= num2;
                        break;
                    }
                    case '*': {
                        num1 *= num2;
                        break;
                    }
                    case '/': {
                        num1 /= num2;
                        break;
                    }
                    case '%': {
                        num1 %= num2;
                        break;
                    }
                    }
                    push(&S, num1);
                }
            }
            i++;
        }
        pop(&S, &num1);
        return num1;
    }

# 串-串比较 #

#include "dsstring.h" //请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    //#include<assert.h>
    int str_compare(const char* ptr1, const char* ptr2)
    {
        //assert(ptr1 && ptr2); //防止传进来为空指针
        //ASCII中A为65，a为97，差32
        while (*ptr1 == *ptr2 || ((*ptr1) + 32 == *ptr2) || ((*ptr2) + 32 == *ptr1)) {
            if (*ptr1 == '\0') {
                return 0;
            }
            ptr1++;
            ptr2++;
        }
        return (*ptr1 - *ptr2);
    }

# 串-串替换 #

#include "dsstring.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    void* Memset(void* s, int c, size_t n)
    {
        if (NULL == s || n < 0)
            return NULL;
        char* tmpS = (char*)s;
        while (n-- > 0)
            *tmpS++ = c;
        return s;
    }
    
    char* Strncat(char* dest, const char* source, int num)
    {
        //assert(dest != NULL);
        //assert(source != NULL);
        char* ret = dest;
    
        while (*dest != '\0') {
            dest++;
        }
        while (num && (*dest++ = *source++)) {
            num--;
        }
        return ret;
    }
    
    char* Strcat(char* dest, const char* src)
    {
        //assert(dest != NULL);
        //assert(src != NULL);
        char* ret = dest;
        //1.找到目的字符串的'\0'
        while (*dest != '\0') {
            dest++;
        }
        //2.追加
        while (*dest++ = *src++) {
            ;
        }
        return ret;
    }
    
    int Strlen(char* str)
    {
        int count = 0;
        while (*str != '\0') {
            str++;
            count++;
        }
        return count;
    }
    
    int Strncmp(const char* str1, const char* str2, int size)
    {
        for (int i = 0; i < size; ++i) {
            if (*(str1 + i) > *(str2 + i)) {
                return 1;
            } else if (*(str1 + i) < *(str2 + i)) {
                return -1;
            }
            if (*(str1 + i) == 0 || *(str2 + i) == 0) {
                break;
            }
        }
        return 0;
    }
    
    int str_replace(const char* in, char* out, int outlen, const char* oldstr, const char* newstr)
    {
        //assert(in && out  && oldstr && newstr && outlen);
        Memset(out, 0, outlen);
        int count = 0;
        for (int i = 0; i < Strlen(in); i++) {
            if (!Strncmp(in + i, oldstr, Strlen(oldstr)) && (Strlen(out) + Strlen(newstr) < outlen)) {
                //查找到目标字符串
                Strcat(out, newstr);
                //把新字符串贴到缓冲字符串里
                i += Strlen(oldstr) - 1;
                count++;
            } else { //如果没有找到
                Strncat(out, in + i, 1); //将该字符写入缓冲字符串数组
            }
            if (Strlen(out) + 1 >= outlen)
                break;
        }
        return count;
    }

# 串-块链串 #

#include "dsstring.h" // 请不要删除，否则检查不通过
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    BLString* blstr_myinit(BLString* str, int length)
    {
        if (str == NULL) {
            str = (BLString*)malloc(sizeof(BLString));
            // assert(str);
        }
        blstr_init(str);
        // 分配空间
        str->len = length;
        if (length == 0)
            return str;
        int blk = length / BLOCK_SIZE;
        int offset = length % BLOCK_SIZE;
        str->head = (Block*)malloc(sizeof(Block));
        memset(str->head->ch, BLS_BLANK, sizeof(char) * BLOCK_SIZE);
        str->head->next = NULL;
        str->tail = str->head;
        Block* cnt = str->head;
        for (int i = 0; i < blk; i++) {
            if (i == blk - 1 && offset == 0)
                break;
            Block* p = (Block*)malloc(sizeof(Block));
            memset(p->ch, BLS_BLANK, sizeof(char) * BLOCK_SIZE);
            p->next = NULL;
            cnt->next = p;
            cnt = cnt->next;
        }
        str->tail = cnt;
        return str;
    }
    bool blstr_substr(BLString src, int pos, int len, BLString* sub)
    {
        if (len == 0)
            return false;
        if (pos > src.len)
            return false;
        if (len + pos > src.len)
            len = src.len - pos;
        blstr_myinit(sub, len);
        Block *cnt = src.head, *cnt1 = sub->head;
        int offset = pos % BLOCK_SIZE, offset1 = 0;
        for (int i = 0; i < pos / BLOCK_SIZE; i++)
            cnt = cnt->next;
        while (len-- && cnt->ch[offset] != BLS_BLANK) {
            cnt1->ch[offset1++] = cnt->ch[offset++];
            if (offset == BLOCK_SIZE) {
                offset = 0;
                cnt = cnt->next;
            }
            if (offset1 == BLOCK_SIZE) {
                offset1 = 0;
                cnt1 = cnt1->next;
            }
        }
        return true;
    }

# 矩阵加法 #

#include "tsmatrix.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    bool add_matrix(const TSMatrix* pM, const TSMatrix* pN, TSMatrix* pQ)
    {
    
        int i_M, j_M, i_N, j_N, M, N, Q;
    
        pQ->m = pM->m;
        pQ->n = pM->n;
    
        if (pM->m != pN->m || pM->n != pN->n) {
            return false;
        }
    
        //同时遍历两个三元组，当pM或者pN中其一元素取完循环终止
        for (M = 0, N = 0, Q = 0; M < pM->len && N < pN->len;) {
    
            i_M = pM->data[M].i; //M矩阵元素的行号
            i_N = pN->data[N].i; //N矩阵元素的行号
            j_M = pM->data[M].j; //M矩阵元素的列号
            j_N = pN->data[N].j; //N矩阵元素的列号
    
            //因为三元组是按行和列排好序的所以比较行数先判断是否来自同一行
            if (i_M > i_N) //N的行号小于M直接将N中元素加入Q矩阵
            {
                //复制N到Q
                pQ->data[Q].i = pN->data[N].i;
                pQ->data[Q].j = pN->data[N].j;
                pQ->data[Q].e = pN->data[N].e;
                N++; //N矩阵地址加一表示向后取一个元素
                Q++; //Q矩阵地址加一表示下一元素存放的地址
            } else if (i_M < i_N) //B的行号大于A直接将A中元素加入C矩阵
            {
                //复制M到Q
                pQ->data[Q].i = pM->data[M].i;
                pQ->data[Q].j = pM->data[M].j;
                pQ->data[Q].e = pM->data[M].e;
                M++; //M矩阵地址加一表示向后取一个元素
                Q++; //Q矩阵地址加一表示下一元素存放的地址
            } else //行号相同时
            {
                //在判断列好号是否来自同一行
                if (j_M > j_N) //B的列号小于A直接将B中元素加入C矩阵
                {
                    //复制N到Q
                    pQ->data[Q].i = pN->data[N].i;
                    pQ->data[Q].j = pN->data[N].j;
                    pQ->data[Q].e = pN->data[N].e;
                    N++; //N矩阵地址加一表示向后取一个元素
                    Q++; //Q矩阵地址加一表示下一元素存放的地址
                } else if (j_M < j_N) //B的列号小于A直接将B中元素加入C矩
                {
                    //复制M到Q
                    pQ->data[Q].i = pM->data[M].i;
                    pQ->data[Q].j = pM->data[M].j;
                    pQ->data[Q].e = pM->data[M].e;
                    M++; //M矩阵地址加一表示向后取一个元素
                    Q++; //Q矩阵地址加一表示下一元素存放的地址
                } else //相等
                {
                    //判断元素相加是否为零
                    if ((pM->data[M].e + pN->data[N].e)) //相加不为零
                    {
                        pQ->data[Q].i = pM->data[M].i;
                        pQ->data[Q].j = pM->data[M].j;
                        pQ->data[Q].e = pM->data[M].e + pN->data[N].e;
                        Q++;
                    }
                    //无论相加是否为零都执行
                    M++;
                    N++;
                }
            }
        }
    
        while (M < pM->len) //N取完M未取完
        {
            //将M中所剩元素依次加入到Q中
            pQ->data[Q].i = pM->data[M].i;
            pQ->data[Q].j = pM->data[M].j;
            pQ->data[Q].e = pM->data[M].e;
            M++;
            Q++;
        }
    
        while (N < pN->len) //M取完N未取完
        {
            //复制N到Q
            pQ->data[Q].i = pN->data[N].i;
            pQ->data[Q].j = pN->data[N].j;
            pQ->data[Q].e = pN->data[N].e;
            N++;
            Q++;
        }
        pQ->len = Q;
        return true;
    }

# 十字链表 #

#include "crosslist.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    int init_cross_list(PCrossList L, const ElemType* A, int m, int n)
    {
        int i, j, sum = 0;
        OLNode *p, *q;
        L->rows = m;
        L->cols = n;
        if (!(L->rowhead = (OLink*)malloc((m + 1) * (sizeof(OLink)))))
            return 0;
        if (!(L->colhead = (OLink*)malloc((n + 1) * (sizeof(OLink)))))
            return 0;
        for (i = 0; i < m; i++) {
            L->rowhead[i] = NULL;
        }
        for (i = 0; i < n; i++) {
            L->colhead[i] = NULL;
        }
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (A[i * n + j] != 0) {
                    sum++;
                    if (!(p = (OLNode*)malloc(sizeof(OLNode))))
                        return 0;
                    p->row = i;
                    p->col = j;
                    p->value = A[i * n + j];
                    if (L->rowhead[i] == NULL || L->rowhead[i]->col > j) {
                        p->right = L->rowhead[i];
                        L->rowhead[i] = p;
                    } else {
                        for (q = L->rowhead[i]; (q->right) && (q->right->col < j); q = q->right)
                            ;
                        p->right = q->right;
                        q->right = p;
                    }
                    if (L->colhead[j] == NULL || L->colhead[j]->row > i) {
                        p->down = L->colhead[j];
                        L->colhead[j] = p;
                    } else {
                        for (q = L->colhead[j]; (q->down) && (q->down->row < i); q = q->down)
                            ;
                        p->down = q->down;
                        q->down = p;
                    }
                }
            }
        }
        L->nums = sum;
        return sum;
    }
    void delete_crossList(PCrossList clist, int row, int col, int k)
    {
        OLNode* tmp = NULL;
        OLNode* tmp1 = NULL;
        OLNode* tmp2 = NULL;
    
        OLNode* t = NULL;
        OLNode* t1 = NULL;
        OLNode* t2 = NULL;
    
        //删除一个结点需要修改行结点指针和列结点指针
        tmp = clist->rowhead[row];
        t = clist->colhead[col];
        if (tmp->value == k) {
            clist->rowhead[row] = tmp->right;
        }
        if (t->value == k) {
            clist->colhead[col] = t->down;
        }
        if (t->value == k) {
            free(t);
            return;
        }
        //行遍历元素
        while (tmp) {
            tmp1 = tmp;
            tmp = tmp->right;
            if (tmp && tmp->row == row && tmp->col == col) {
                tmp2 = tmp;
                tmp1->right = tmp2->right;
                break;
            }
        }
        //列遍历元素
        while (t) {
            t1 = t;
            t = t->down;
            if (t && t->row == row && t->col == col) {
                t2 = t;
                t1->down = t2->down;
                break;
            }
        }
        free(t);
        clist->nums--;
    }
    int del_cross_list(PCrossList L, ElemType k)
    {
        OLink pt;
        int i, j;
        int sum = 0;
        for (i = 0; i < L->rows; i++) {
            pt = L->rowhead[i];
            for (j = 0; j < L->cols; j++) {
                if (pt && pt->col == j) {
                    if (pt->value == k) {
                        delete_crossList(L, i, j, k);
                        sum++;
                    }
                    pt = pt->right;
                }
            }
            printf("\n");
        }
        return sum;
    }

# 树与二叉树--先序遍历 #

#include "bitree.h" //请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    void pre_order(BiTree root)
    {
        Stack S[Stack_Size];
        BiTree T = root;
        init_stack(S);
        while (T || !is_empty(S)) {
            while (T) {
                visit_node(T);
                push(S, T);
                T = T->left;
            }
            pop(S, &T);
            T = T->right;
        }
    }

# 树与二叉树--路径 #

#include "bitree.h" //请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    bool path(BiTNode* root, BiTNode* node, Stack* s)
    {
        BiTree T = root, p = NULL;
        if (T == NULL || node == NULL || !is_empty(s))
            return false;
        while (T || !is_empty(s)) {
            while (T) {
                push(s, T);
                if (T == node)
                    return true;
                T = T->left;
            }
            top(s, &T);
            if (!T->right || T->right == p) {
                p = T;
                pop(s, &T);
                T = NULL;
            } else {
                T = T->right;
            }
        }
        return false;
    }

# 树与二叉树--共同祖先 #

#include "bitree.h" //请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    BiTNode* nearest_ancestor(BiTree root, BiTNode* p, BiTNode* q)
    {
        Stack s1, s2;
        BiTNode* ancNode;
        init_stack(&s1);
        init_stack(&s2);
    
        path(root, p, &s1);
        path(root, q, &s2);
    
        if (s1.elem[0] != s2.elem[0])
            return NULL;
    
        ancNode = s1.elem[0];
    
        for (int i = 1; i < s1.top && i < s2.top; i++) {
            if (s1.elem[i] != s2.elem[i])
                return ancNode;
            ancNode = s1.elem[i];
        }
        return ancNode;
    }

# 树与二叉树--树转二叉树 #

#include "bitree.h" //请不要删除，否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
    
    BiTNode* transform(CSNode* root)
    {
        if (root == NULL)
            return NULL;
    
        //初始化二叉树的根节点
        BiTree broot = (BiTree)malloc(sizeof(struct Node));
        broot->data = root->data;
        broot->left = broot->right = NULL;
    
        //普通树、二叉树初始化、加入队列
        Queue* queue = create_queue();
        Queue* bqueue = create_queue();
        add_queue(queue, root);
        add_queue(bqueue, broot);
    
        while (!is_empty_queue(queue)) {
            //从普通数和二叉树中分别取出一个结点
            CSNode* node = del_queue(queue);
            BiTree bTreeNode = del_queue(bqueue);
    
            int i;
            BiTree former = NULL;
            //遍历普通树结点的所有孩子结点，将孩子加入队列
            for (i = 0; i < MAX_CHILDREN_NUM; i++) {
                //孩子非空
                if (node->children[i]) {
                    //二叉树节点初始化并赋值
                    BiTree bnode = (BiTree)malloc(sizeof(struct Node));
                    bnode->left = bnode->right = NULL;
                    bnode->data = node->children[i]->data;
    
                    if (i == 0) //普通树的第一个孩子作为二叉树的左孩子
                        bTreeNode->left = bnode;
                    else //后面的孩子结点作为前面结点的右孩子
                        former->right = bnode;
                    former = bnode;
    
                    add_queue(queue, node->children[i]);
                    add_queue(bqueue, bnode);
                }
            }
        }
        free(queue->array);
        free(queue);
        free(bqueue->array);
        free(bqueue);
        return broot;
    }

# 图-邻接矩阵 #

#include <stdio.h>
    #include "graph.h" // 请不要删除，否则检查不通过
     
    bool matrix_insert_vertex(MatrixGraph* G, VertexType v)
    {
        //如果v存在或超出最大顶点数
        if (matrix_locate_vertex(G, v) != -1 || G->vexnum + 1 >= MAX_VERTEX_NUM)
            return false;
        G->vertex[G->vexnum] = v;
        G->vexnum++;
    	//邻接矩阵增加v的行列
        for (int i = 0; i < G->vexnum; i++)
    	{
    		G->arcs[i][G->vexnum - 1] = 0;
    		G->arcs[G->vexnum - 1][i] = 0;
    	}       
        return true;
    }
     
    bool matrix_insert_arc(MatrixGraph* G, VertexType v, VertexType w)
    {
        int V = matrix_locate_vertex(G, v);
        int W = matrix_locate_vertex(G, w);
        if (V == -1 || W == -1)
            return false;
    	//有向图
        if (G->type == "DG") 
        {
            if (G->arcs[V][W] == 1)
                return false;
            G->arcs[V][W] = 1;
        } 
        else {
    	//无向图
            if (G->arcs[V][W] == 1 || G->arcs[W][V] == 1)
                return false;
            G->arcs[V][W] = 1;
    	G->arcs[W][V] = 1;
        }
        G->arcnum++;
        return true;
    }

# 图-邻接表1 #

bool insert_vertex(ListGraph* G, VertexType v)
    {
        if (locate_vertex(G, v) != -1 || G->vexnum + 1 >= MAX_VERTEX_NUM)
            return false;
        G->vertex[G->vexnum].data = v;
        G->vertex[G->vexnum].firstarc = NULL;
        G->vexnum++;
        return true;
    }
    
    bool insert_arc(ListGraph* G, VertexType v, VertexType w)
    {
        if (locate_vertex(G, v) == -1 || locate_vertex(G, w) == -1)
            return false;
     
        int V = locate_vertex(G, v);
        int W = locate_vertex(G, w);
     
        if (G->type == "DG")
        {
            ArcNode* p = G->vertex[V].firstarc;
            ArcNode* NewNodeV = (ArcNode*)malloc(sizeof(struct ArcNode));
            while (p->nextarc != NULL) {
                p = p->nextarc;
            }
            p->nextarc = NewNodeV;
            NewNodeV->adjvex = W;
            NewNodeV->nextarc = NULL;
            G->arcnum ++;
        }
        else
        {
            ArcNode* p = G->vertex[V].firstarc;
            ArcNode* q = G->vertex[W].firstarc;
            ArcNode* NewNodeV = (ArcNode*)malloc(sizeof(struct ArcNode));
            ArcNode* NewNodeW = (ArcNode*)malloc(sizeof(struct ArcNode));
            while (p->nextarc != NULL) {
                p = p->nextarc;
            }
            while (q->nextarc != NULL) {
                q = q->nextarc;
            }
            p->nextarc = NewNodeV;
            NewNodeV->adjvex = W;
            NewNodeV->nextarc = NULL;
     
            q->nextarc = NewNodeV;
            NewNodeV->adjvex = V;
            NewNodeV->nextarc = NULL;
            G->arcnum+=2;
        }
        return true;
    }

# 图-邻接表2 #

bool del_vertex(ListGraph* G, VertexType v)
    {
        int i;
    	int V = locate_vertex(G, v);
    	//检查是否存在该节点
        if (V == -1) 
            return false; 
        
        //先删除从该节点出发的边和该节点
        while (G->vertex[V].firstarc)
    	{ 
            ArcNode* P = G->vertex[V].firstarc;
            if (P->nextarc)
    		{ //先free表头结点后面的
                ArcNode* temp = P->nextarc;
                P->nextarc = temp->nextarc;
                free(temp);
            } 
    		else {
                free(P); //free表头结点
                G->vertex[V].firstarc = NULL;
            }
            G->arcnum--; //边的数量-1
        }
        G->vexnum--; //结点的数量-1
        for (i = V; i < G->vexnum; i++) 
    	{ //表头结点中，后面的向前移动
            G->vertex[i] = G->vertex[i + 1];
        }
        
        //再删除到该节点的边
        for (i = 0; i < G->vexnum; i++) 
    	{
            ArcNode *P = G->vertex[i].firstarc, *pNode = NULL;
            ArcNode* temp; //存储要被删掉的结点
            while (P)
    		{
                if (V == P->adjvex) 
    			{ //P的下个结点是V
                    if (!pNode) 
    				{ //P是表头结点
                        temp = G->vertex[i].firstarc;
                        G->vertex[i].firstarc = P->nextarc;
                    }
                    else {
                        pNode->nextarc = P->nextarc;
                        temp = P;
                    }
                    P = P->nextarc;
                    free(temp);
                    G->arcnum--;
                } 
    			else {
                    pNode = P;
                    P = P->nextarc;
                }
            }
        }
        return true;
    }

# 查找-哈希表创建 #

#include <stdio.h>
    #include <stdlib.h>
    #include "hash.h"
    #include <string.h>
     
    HashTable* create_hash(int size)
    {
    	HashTable* H;
    	H = (HashTable*)malloc(1 * sizeof(HashTable));
    	if (H == NULL)
    		return NULL;
    	H->bucket = (HashEntry**)malloc(size * sizeof(HashEntry*));
    	if (H->bucket == NULL) {
    		free(H);
    		return NULL;
    	}
    	memset(H->bucket, 0, size * sizeof(HashEntry*));
    	H->size = size;
    	H->last_error = HASH_OK;
    	return H;
    }

# 查找-哈希表添加 #

#include <stdio.h>
    #include "stdlib.h"
    #include "hash.h"
     
    #include <string.h>
     
    int Find(HashTable* table, const char* key, int value, long keyhash)
    {
        HashEntry* Head = table->bucket[keyhash];
        
        while (Head && strcmp(Head->key.str_value, key)) {
            Head = Head->next;
        }
        
        if (!Head)
            return -1;
        else if (Head->value.int_value == value)
            return 1;
        else {
            Head->value.int_value = value;
            return 0;
        }
    }
     
    HASH_RESULT hash_add_int(HashTable* table, const char* key, int value)
    {
        int p;
        long keyhash = hash_string(key) % table->size;
        p = Find(table, key, value, keyhash);
        
        if (p == -1) {
            HashEntry* Node = (HashEntry*)malloc(sizeof(HashEntry));
            if (!Node)
                return HASH_ERROR;
            Node->key.str_value = (char*)malloc(100);
            if (Node->key.str_value == NULL) {
                return HASH_ERROR;
            }
            Node->key.str_value = (char*)key;
            Node->value.int_value = value;
            //Node->next = table->bucket[keyhash]; //？
            table->bucket[keyhash] = Node;
            return HASH_ADDED;
        } else if (p == 0)
            return HASH_REPLACED_VALUE;
        else
            return HASH_ALREADY_ADDED;
    }

# 查找-AVL添加 #

#include "avl.h"
    #include <stdio.h>
    #include <stdlib.h>
     
    void update(node_t* root)
    {
        if (root == NULL)
            return;
        int h = 1;
        if (root->left) {
            int lh = root->left->height + 1;
            h = lh > h ? lh : h;
            root->left->parent = root;
        }
        if (root->right) {
            int rh = root->right->height + 1;
            h = rh > h ? rh : h;
            root->right->parent = root;
        }
     
        root->height = h;
    }
    void LL(node_t** t)
    {
        node_t* tmp = (*t)->left;
        (*t)->left = tmp->right;
        tmp->right = (*t);
        (*t) = tmp;
     
        update((*t)->right->left);
        update((*t)->right);
        update((*t));
    }
    void RR(node_t** t)
    {
        node_t* tmp = (*t)->right;
        (*t)->right = tmp->left;
        tmp->left = (*t);
        (*t) = tmp;
     
        update((*t)->left->right);
        update((*t)->left);
        update((*t));
    }
     
    void LR(node_t** t)
    {
        RR(&(*t)->left);
        LL(t);
    }
    void RL(node_t** t)
    {
        LL(&(*t)->right);
        RR(t);
    }
     
    node_t* avl_insert(node_t* root, int val)
    {
        if (root == NULL) {
            node_t* rt = (node_t*)malloc(sizeof(node_t));
            rt->left = rt->right = rt->parent = NULL;
            rt->height = 1;
            rt->val = val;
     
            return rt;
        }
     
        if (val <= root->val) {
            root->left = avl_insert(root->left, val);
            int left_h = root->left->height;
            int right_h = root->right ? root->right->height : 0;
     
            if (left_h - right_h > 1) {
                if (val <= root->left->val) {
                    LL(&root);
                } else {
                    LR(&root);
                }
            }
        } else {
            root->right = avl_insert(root->right, val);
            int left_h = root->left ? root->left->height : 0;
            int right_h = root->right->height;
     
            if (right_h - left_h > 1) {
                if (val > root->right->val) {
                    RR(&root);
                } else {
                    RL(&root);
                }
            }
        }
     
        update(root);
        return root;
    }

# 排序-堆辅助函数 #

#include <stdio.h>
    #include <stdlib.h>
    #include "minbinheap.h" // 请不要删除，否则检查不通过
     
    //返回堆元素的父节点下标
    //n->2n+1  2n+2
    int parent(int i) {
    	return (i-1) / 2;
    }
     
    //返回左子节点
    int left(int i){
    	return 2 * i + 1;
    }
     
    int right(int j) {
    	return 2 * j + 2;
    }
     
    //交换两个堆元素的值
    void swap_node(MinHeapNode* x, MinHeapNode* y) {
    	int value;
    	int i, j;
     
    	value = y->value;
    	i = y->otherInfo.i;
    	j = y->otherInfo.j;
     
    	y->value = x->value;
    	y->otherInfo.i = x->otherInfo.i;
    	y->otherInfo.j = x->otherInfo.j;
     
    	x->value = value;
    	x->otherInfo.i = i;
    	x->otherInfo.j = j;
    }

# 排序-堆初始化 #

#include <stdio.h>
    #include <stdlib.h>
    #include "minbinheap.h"
     
     
    //pq指向堆,capacity为堆元素数组的初始化大小
    void init_min_heap(PMinHeap pq, int capacity){
    	pq->capacity = capacity;
    	pq->heap_size = 0;
    	pq->heap_array = (PMinHeapNode)malloc(sizeof(MinHeapNode) * pq->capacity);
    	return;
    }

# 排序-堆化 #

#include <stdio.h>
    #include <stdlib.h>
    #include "minbinheap.h"
     
    void min_heapify(PMinHeap pq, int i){
    	int j = 2 * i + 1;
    	MinHeapNode* p = pq->heap_array;
    	while (j <= pq->heap_size - 1){
    		//j为最小值的堆
    		if (p[j + 1].value < p[j].value)
    			j = j + 1;
    		if (p[j].value < p[i].value) {
    			swap_node(&p[j], &p[i]);
    			i = j;
    			j = 2 * i + 1;
    		}
    		else return;
    	}
    }

# 排序-数组合并 #

#include<stdio.h>
    #include<stdlib.h>
     
    void max_heapify(int* p, int i, int size) {
     
        int j = 2 * i + 1, t=p[i];
        while (j <= size - 1) {
            if (j + 1 <= size - 1 && p[j] < p[j + 1])j = j + 1;
            if (p[j] > t) {
     
                p[i] = p[j];
                i = j;
                j = 2 * i + 1;
            }
            else break;
        }
        p[i] = t;
    }//假设i之后都是大根堆，调整i使从i开始都是大根堆
     
     
    void merge_arrays(const int* arr, int n,int k,int* output) {
        int size=n*k;
        int x, i, *array;
        array = (int*)malloc(size * sizeof(int));
        
        for (i = 0; i <= size - 1; i++) {
            array[i] = arr[i];
        }
     
         for (i=size/2-1; i >=0 ; i--) {
            max_heapify(array, i, size);
        }//将整个堆大根堆化
        for (i = size-1; i >= 1; --i) {
            x = array[0];
            array[0] = array[i];
            array[i] = x;
            max_heapify(array, 0, i);
        }
        for (i = 0; i <= size - 1; i++) {
            output[i] = array[i];
        }
     
    }

[https_blog.csdn.net_aiqq136_article_details_114590856]: https://blog.csdn.net/aiqq136/article/details/114590856