【笔记】C 数据结构的实现

C September 9, 2021

《大话数据结构》学习笔记，已完结

线性表

#include <stdio.h>

//Status
#define OK 1
#define ERROR 0

//线性表（顺序储存）
#define MAX 20 //最大长度
typedef int ElemType;
typedef struct
{
    ElemType data[MAX];
    int len;//当前长度
}SqList;

//位置参数均从0开始
//获取元素
int GetElem(const SqList * L, int i, ElemType * e)
{
    if(i < 0 || i >= L->len)
        return ERROR;
    *e = L->data[i];
    return OK;
}

//插入元素
int InsertElem(SqList * L, int i, ElemType e)
{
    if(MAX == L->len || i < 0 || i > L->len)
        return ERROR;
    for (int n = L->len; n > i; n--)
    {
        L->data[n] = L->data[n - 1];
    }
    L->data[i] = e;
    L->len++;
    return OK;
}

//删除元素
int DelElem(SqList * L, int i, ElemType * e)
{
    if(i < 0 || i >= L->len)
        return ERROR;
    *e = L->data[i];
    for(int n = i; n < L->len - 1; n++)
        L->data[n] = L->data[n + 1];
    L->len--;
    return OK;
}

链表

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//Status
#define OK 1
#define ERROR 0

//单链表
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;

int GetElem(Node * Head, int i, ElemType * e)
{
    Node * n = Head;
    while(i > 0)
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    *e = n->data;
    return OK;
}

//不能插入到头节点之前
int InsertElem(Node * Head, int i, ElemType e)
{
    Node * n = Head;
    //找到欲插入位置的前一个节点
    while(i > 1)
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    Node * s = malloc(sizeof(Node));
    s->data = e;
    s->next = n->next;
    n->next = s;
    return OK;
}

//不能删除头节点
int DelElem(Node * Head, int i, ElemType * e)
{
    
    Node * n = Head;
    //找到欲删除节点的前一个节点
    while(i > 1) 
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    Node * q = n->next;
    n->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

void CreateList(Node * Head, int n)
{
    srand(time(0));
    Node * s = Head;
    do
    {
        s->next = malloc(sizeof(Node));
        s->next->data = rand() % 100 + 1;
        s = s->next;

    }while(--n > 0);
    s->next = NULL;

}

//只保留头结点
void ClearList(Node * Head)
{
    Node * s = Head->next;
    Node * n;
    while(s)
    {
        n = s->next;
        free(s);
        s = n;
    }
    Head->next = NULL;
}

int GetLength(Node * Head)
{
    int i = 1;
    Node * s = Head;
    while(s->next)
    {
        i++;
        s = s->next;
    }
    return i;
}

链栈

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

//Status
#define OK 1
#define ERROR 0

//链栈
typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode * next;

}StackNode;

typedef struct 
{
    StackNode * top;
    int count;//栈的长度
}LinkStack;


//进栈
int Push(LinkStack * S, SElemType e)
{
    StackNode * n = (StackNode *)malloc(sizeof(StackNode));
    n->data = e;
    n->next = S->top;
    S->count++;
    S->top = n;
    return OK;
}


//出栈
int Pop(LinkStack * S, SElemType * e)
{
    if(!S->count)
        return ERROR;
    *e = S->top->data;
    StackNode * t = S->top;
    S->top = S->top->next;
    free(t);
    S->count--;
    return OK;

}

//获取栈顶元素
int GetTop(LinkStack * S, SElemType * e)
{
    if(!S->count)
        return ERROR;
    *e = S->top->data;
    return OK;
}


//创建空栈
LinkStack * CreateStack()
{
    LinkStack * S = (LinkStack *)malloc(sizeof(LinkStack));
    S->top = NULL;
    S->count = 0;
    return S;
}

//销毁
void DestroyStack(LinkStack * S)
{
    SElemType e;
    while(S->count)
    {
        Pop(S, &e);
        S->count--;
    }
    free(S);
}

循环队列

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

#define MAX_SIZE 100
//Status
#define OK 1
#define ERROR 0

//循环队列（顺序储存）
typedef int QElemType;
typedef struct Queue
{
    QElemType data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void InitQueue(Queue * Q)
{
    Q->front = 0;
    Q->rear = 0;
}

int QueueLength(Queue * Q)
{
    return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}

int EnQueue(Queue * Q, QElemType e)
{
    if((Q->rear + 1) % MAX_SIZE == Q->front)
        return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return OK;
}

int DeQueue(Queue * Q, QElemType * e)
{
    if(Q->rear == Q->front)
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return OK;
}

int GetHead(Queue * Q, QElemType * e)
{
    if(Q->rear == Q->front)
        return ERROR;
    *e = Q->data[Q->front];
    return OK;
}

链队列

#include <stdio.h>
#include <stdlib.h>
//Status
#define OK 1
#define ERROR 0

//链队列
typedef int QElemType;
typedef struct QNode
{                                            
    QElemType data;
    struct QNode * next;
} QNode;

typedef struct LinkQueue
{
    //队头指针、队尾指针
   QNode * front, * rear; 
}LinkQueue;


//入队
int EnQueue(LinkQueue * Q, QElemType e)
{
    QNode * n = malloc(sizeof(QNode));
    if(!n)  return ERROR;
    n->data = e;
    n->next = NULL;
    Q->rear->next = n;
    Q->rear = n;
    return OK;
}


//出队                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
int DeQueue(LinkQueue * Q, QElemType * e)
{
    if(Q->front == Q->rear)
        return ERROR;
    *e = Q->front->next->data;
    QNode * n = Q->front->next;
    Q->front->next = n->next;
    if(Q->rear == n)//出队元素刚好在队尾
        Q->rear = Q->front;
    free(n);
    return 0;
}

//获取队列长度
int QueueLength(LinkQueue *Q)
{
    return (Q->rear - Q->front) / sizeof(QElemType);
}

//清空队列
void ClearQueue(LinkQueue * Q)
{
    while(Q->front->next)
    {
        QNode * n = Q->front->next;
        Q->front->next = n->next;
        free(n);
    }
    Q->rear = Q->front;
}

LinkQueue * CreateQueue()
{
    LinkQueue * Q = malloc(sizeof(LinkQueue));
    QNode * n = malloc(sizeof(QNode));
    n->data = -1;
    n->next = NULL;
    Q->front = n;
    Q->rear = n;
    return Q;
}

KMP模式匹配

//Donald Knuth(K), James H. Morris(M), Vaughan Pratt(P). 

#include <stdio.h>
#include <string.h>


int bruteForce(char * str, char * fstr)
{
    int len = strlen(str);
    int flen = strlen(fstr);
    if(0 == len || 0 == flen || flen > len)
    {
        return -1;
    }
    for(int i = 0; i < len - flen + 1; i++)
    {
        int n;
        for(n = 0; n < flen; n++)
        {
            if(str[i + n] != fstr[n])
                break;
        }
        if(n == flen)
            return i;
    }

    return -1;
}

void getNext(char * str, int * next)
{
    //首位必定为0，故i从1开始
    next[0] = 0; 
    int i = 1;
    int now = 0;
    int len = strlen(str);
    while(i < len)
    {
        if(str[now] == str[i])
        {
            now++;
            next[i++] = now;
        }
        else if(now)
        {
            now = next[now - 1];
        }
        else
        {
            next[i++] = 0;
        }
    }

}

int kmp(char * fstr, char * str, int * next)
{
    int i = 0;
    int pos = 0;
    int len = strlen(str);
    int flen = strlen(fstr);
    while(i < len)
    {
        if(str[i] == fstr[pos])
        {
            i++;
            pos++;
        }
        else if(pos)
        {
            pos = next[pos - 1];
        }
        else
        {
            i++;
        }

        if(pos == flen)
        {
            return i - pos;
            //pos = next[pos - 1];
        }
    }

}

int main(void)
{   
    char s[] = "WhatWhereWhy";
    char f[] = "Why";
    int next[strlen(f)];
    getNext(f, next);
    printf("Next:");
    for(int i = 0; i < sizeof(next) / sizeof(next[0]); i++)
    {
        printf("%d,", next[i]);
    }
    printf("\nKMP:%d", kmp(f, s, next));
    printf("\nBF:%d", bruteForce(s, f));
    getchar();

}

树

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

#define ERROR 0;
#define OK 1;

typedef int TElemType;
//树 链式结构
typedef struct TNode  
{
    TElemType data;
    struct TNode *parent, *firstChild, *rightSib;
}TNode, *Tree;

//创建一个只含根节点的树
Tree CreateTree(TElemType e)
{
    Tree n = malloc(sizeof(TNode));
    n->data = e;
    n->firstChild = NULL;
    n->parent = NULL;
    n->rightSib = NULL;
    return n;
}

//获取树的深度
int TreeDepth(Tree t)
{
    if(!t)
        return 0;
    TNode * n = t->firstChild;
    if(!n)
        return 1;
    int max = -1;
    while(n)
    {
        int dep = TreeDepth(n);
        if(dep > max)
            max = dep;
        n = n->rightSib;
    }
    return 1 + max;
}

//获取第i个子节点
TNode * GetChild(TNode * n, int i)
{
    TNode * s = n->firstChild;
    if(!s)
        return NULL;
    for(int n = 1; n < i; n++)
    {
        s = s->rightSib;
        if(!s)
            return NULL;
    }
    return s;
}

//插入第i个子节点
int InsertChild(TNode * n, int i, TElemType e)
{
    //无子节点，忽略i
    if(!n->firstChild)
    {
        TNode * c = malloc(sizeof(TNode));
        c->data = e;
        c->parent = n;
        c->firstChild = NULL;
        c->rightSib = NULL;
        n->firstChild = c;
        return OK;
    }
    else
    {
        TNode * c = n->firstChild;
        while(i-- > 2)
        {
            c = c->rightSib;
            if(!c)
                return ERROR;
        }
        TNode * s = malloc(sizeof(TNode));
        s->data = e;
        s->parent = n;
        s->firstChild = NULL;
        s->rightSib = c->rightSib;
        c->rightSib = s;
        return OK;
    }
}


//删除第i个子节点
int DeleteChild(TNode * n, int i)
{
    TNode * s = n->firstChild;
    TNode * child;
    if(!s)
        return ERROR;

    //若删除第一个节点
    if(i == 1)
    {
        while(child = s->firstChild)
        {
            DeleteChild(s, 1);
        }
        n->firstChild = s->rightSib;
        free(s);
        return OK;
    }

    //获取第i-1个节点
    for(int n = 1; n < i - 1; n++)
    {
        s = s->rightSib;
        if(!s)
            return ERROR
    }

    //验证第i个节点存在
    if(!s->rightSib)
        return ERROR;

    //递归销毁子节点
    while(child = s->rightSib->firstChild)
    {
        DeleteChild(s->rightSib, 1);
    }
    child = s->rightSib;
    s->rightSib = s->rightSib->rightSib;
    free(child);
    return OK;
}

//输出树
void printTree(TNode * n)
{
    TNode * s = n->firstChild;
    if(!s)
    {
        return;
    }
    do
    {
        printf("%d, ", s->data);
        printTree(s);
        s = s->rightSib;
    } while(s); 
    printf("\n");
}

int main()
{
    Tree t = CreateTree(9);
    TNode * n;
    for(int i = 0; i < 5; i++)
    {
        InsertChild(t, i + 1, i);
        n = GetChild(t, i + 1);
        InsertChild(n, 1, i + 10);
        InsertChild(n, 2, i + 20);
    }
    DeleteChild(t->firstChild, 1);
    DeleteChild(t->firstChild->rightSib, 2);
    printf("DEPTH: %d\n", TreeDepth(t));
    printf("ROOT: %d\n", t->data);
    printTree(t);
    getchar();
}


//——树的其他表示法
//树 父节点表示法
#define MAX_SIZE 100
typedef struct PTNode
{
    TElemType data;
    //父节点的下标
    int parent;

    //改进：
    //首个子节点的下标
    //int firstChild;
    //右节点的下标
    //int rightSib;
}PTNode;

typedef struct PTree
{
    PTNode nodes[MAX_SIZE];
    //结点数
    int count;
    //根的下标
    int root;
}PTree;


//树 子节点表示法
//考虑到每个节点的度不同，可以使用链表结构储存子节点
typedef struct CTNode
{
    //当前子节点的下标
    int child;
    //下一个字节点
    struct CTNode *next;
}CTNode;

typedef struct CTBox
{
    TElemType data;
    //父节点的下标
    int parent;
    //第一个子节点
    CTNode *firstChild;
}CTBox;

typedef struct CTree
{
    CTBox nodes[MAX_SIZE];   
    int root;
    int count;
}CTree;

二叉树

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

//二叉树
typedef char BTElemType;
typedef struct BTNode
{
    BTElemType data;
    struct BTNode * left, * right;
}BTNode, *BTree;

//前序遍历
void NLR(BTree T)
{
    if(!T)
        return;
    printf("%c", T->data);
    NLR(T->left);
    NLR(T->right);
}

//中序遍历
void LNR(BTree T)
{
    if(!T)
        return;
    LNR(T->left);
    printf("%c", T->data);
    LNR(T->right);
}

//后序遍历
void RNL(BTree T)
{
    if(!T)
        return;
    RNL(T->left);
    RNL(T->right);
    printf("%c", T->data);
}

//前序建立二叉树，#代表无节点
static int index;
void CreateBTree(BTree * T, char str[])
{
    BTElemType e;
    e = str[index++];
    if(!e)
        return;
    if(e == '#')
        *T = NULL;
    else
    {
        *T = malloc(sizeof(BTNode));
        if(!*T)
            return;
        (*T)->data = e;
        CreateBTree(&(*T)->left, str);       
        CreateBTree(&(*T)->right, str);   
    }

}

//销毁二叉树
void DestroyBTree(BTree * T)
{
    if(!(*T))
        return;
    DestroyBTree(&(*T)->left);
    DestroyBTree(&(*T)->right);
    free((*T));
}

int main()
{
    BTree T;
    index = 0;
    CreateBTree(&T, "AB#D##C##");
    DestroyBTree(&T);
    index = 0;
    CreateBTree(&T, "XY#Z##9##");
    NLR(T);
    printf("\n");
    LNR(T);
    printf("\n");
    RNL(T);
    getchar();
    return 0;
}

线索二叉树

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

typedef char TElemType;
typedef enum {Link, Thread} Tag;
typedef struct ThrNode
{
    TElemType data;
    struct ThrNode * left, * right;
    Tag ltag, rtag;
}ThrNode, *ThrTree;

//前序建立线索二叉树，#代表无节点
static int index;
void CreateThrTree(ThrTree * T, char str[])
{
    
    TElemType e;
    e = str[index++];
    if(!e)
        return;
    if(e == '#')
        *T = NULL;
    else
    {
        *T = malloc(sizeof(ThrNode));
        if(!*T)
            return;
        (*T)->data = e;
        CreateThrTree(&(*T)->left, str);       
        CreateThrTree(&(*T)->right, str);   
    }

}

//销毁线索二叉树
void DestroyThrTree(ThrTree * T)
{
    if(!(*T))
        return;
    if((*T)->ltag == Link)
        DestroyThrTree(&(*T)->left);
    if((*T)->rtag == Link)
        DestroyThrTree(&(*T)->right);
    free((*T));
}

//中序遍历线索化
ThrNode * pre;
void InThreading(ThrTree T)
{
    if(T)
    {
        InThreading(T->left);
        if(!T->left)
        {
            T->ltag = Thread;
            T->left = pre;
        }
        else
            T->ltag = Link;

        if(pre)
        {
            if(!pre->right)
            {
                pre->rtag = Thread;
                pre->right = T;
            }   
            else
                pre->rtag = Link;
        }    
        
        pre = T;
        InThreading(T->right);
    }
}

//普通中序遍历
void LNR(ThrTree T)
{
    if(!T)
        return;
    if(T->ltag == Link)
        LNR(T->left);
    printf("%c", T->data);
    if(T->rtag == Link)
        LNR(T->right);
}

//线索中序遍历
void ThrLNR(ThrTree T)
{
    ThrNode * n = T;
    while(n)
    {
        //到达最左下节点
        while(n->ltag == Link)
            n = n->left;

        printf("%c", n->data);
        while(n->rtag == Thread && n->right)
        {
            n = n->right;
            printf("%c", n->data);
        }
        n = n->right;
    }
    
}

int main()
{
    ThrTree T;
    //创建线索二叉树
    CreateThrTree(&T, "ABDH##I##EJ###CF##G##");
    //线索化
    InThreading(T);
    //普通中序遍历
    LNR(T);
    printf("\n");
    //线索中序遍历（非递归，效率更高）
    ThrLNR(T);
    //销毁
    DestroyThrTree(&T);
    getchar();

}

图的结构

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

//基于数组（邻接矩阵）的图结构
//使用二维数组储存顶点之间的邻接关系
typedef char NodeType;
typedef int EdgeType;
#define NODE_MAX 100
#define INFINITE 65535
//在邻接矩阵中，INFINITE表示顶点间无邻接关系
typedef struct GraphArray{
    NodeType nodes[NODE_MAX];
    EdgeType arc[NODE_MAX][NODE_MAX];
    int numNodes, numEdges;
    
}GraphArray;

void CreateGraph(GraphArray *G)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    G->numEdges = e;
    G->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &G->nodes[i]);
    }
    for(int i = 0; i < n; i++)
        for(int m = 0; m < n; m++)
            G->arc[i][m] = i == m ? 0 : INFINITE;
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        //以有向图为例
        G->arc[start][end] = weight;
    }

}

void PrintGraph(GraphArray *G)
{
    int n = G->numNodes;
    for(int i = 0; i < n; i++)
    {
        printf("%3c", G->nodes[i]);
    }
    printf("\n\n");
    for(int i = -1; i < n; i++)
            printf("%3d", i);
    printf("\n");
    for(int i = 0; i < n; i++)
    {
        printf("%3d", i);
        for(int m = 0; m < n; m++)
        {
            if(G->arc[i][m] == INFINITE)
                printf("%3c", '-');
            else printf("%3d", G->arc[i][m]);
        }
        printf("\n");
    }
        
}

//基于链表（邻接表）的图结构
//与基于数组（邻接矩阵）的图结构相比，比较灵活，浪费空间显著减少
typedef struct EdgeNodeL{
    int index;
    EdgeType weight;
    struct EdgeNodeL *next;
} EdgeNodeL;

typedef struct GraphNodeL{
    NodeType value;
    EdgeNodeL *first;
} GraphNodeL;

typedef struct GraphList{
    GraphNodeL nodes[NODE_MAX];
    int numNodes, numEdges;
} GraphList;

void CreateGraphL(GraphList *GL)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    GL->numEdges = e;
    GL->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &GL->nodes[i].value);
        GL->nodes[i].first = NULL;
    }       
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);

        //头插法，以无向图为例
        EdgeNodeL *edge = malloc(sizeof(EdgeNodeL));
        edge->index = end;
        edge->weight = weight;
        edge->next = GL->nodes[start].first;
        GL->nodes[start].first = edge;
        edge = malloc(sizeof(EdgeNodeL));
        edge->index = start;
        edge->weight = weight;
        edge->next = GL->nodes[end].first;
        GL->nodes[end].first = edge;
    }
}

void PrintGraphL(GraphList *GL)
{
    for(int i = 0; i < GL->numNodes; i++)
    {
        printf("[%d] %c:", i, GL->nodes[i].value);
        EdgeNodeL *edge = GL->nodes[i].first;
        while(edge != NULL)
        {
            printf("[%2d]%3d", edge->index, edge->weight);
            edge = edge->next;
        }
        printf("\n");
    }
}

void FreeGraphL(GraphList *GL)
{
    for(int i = 0; i < GL->numNodes; i++)
    {
        EdgeNodeL *edge = GL->nodes[i].first;
        EdgeNodeL *next = NULL;
        while(edge != NULL)
        {
            next = edge->next;
            free(edge);
            edge = next;
        }
    }
    free(GL);
}

//基于十字链表的有向图结构
//与基于链表（邻接表）的有向图结构相比，可以非常快速地获取某一顶点的出入弧情况
typedef struct EdgeNodeC{
    int start;
    int end;
    EdgeType weight;
    struct EdgeNodeC *nextIn;
    struct EdgeNodeC *nextOut;
}EdgeNodeC;

typedef struct GraphNodeC {
    NodeType value;
    EdgeNodeC *firstIn;
    EdgeNodeC *firstOut;
}GraphNodeC;

typedef struct GraphCross{
    GraphNodeC nodes[NODE_MAX];
    int numNodes, numEdges;
}GraphCross;

void CreateGraphC(GraphCross *GC)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和弧数：\n");
    scanf("%d %d", &n, &e);
    GC->numEdges = e;
    GC->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &GC->nodes[i].value);
        GC->nodes[i].firstIn = NULL;
        GC->nodes[i].firstOut = NULL;
    }       
    
    printf("输入弧的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        //头插法
        EdgeNodeC *edge = malloc(sizeof(EdgeNodeC));
        edge->start = start;
        edge->end = end;
        edge->weight = weight;
        edge->nextOut = GC->nodes[start].firstOut;
        edge->nextIn = GC->nodes[end].firstIn;
        GC->nodes[start].firstOut = edge;     
        GC->nodes[end].firstIn = edge;
    }
}

void PrintGraphC(GraphCross *GC)
{
    printf("出弧链表:\n");
    for(int i = 0; i < GC->numNodes; i++)
    {
        printf("[%d]%c:", i, GC->nodes[i].value);
        EdgeNodeC *edge = GC->nodes[i].firstOut;
        while(edge != NULL)
        {
            printf("\n   [%p] start:%d, end:%d, nextIn:%p, nextOut:%p", edge,
             edge->start, edge->end, edge->nextIn, edge->nextOut);
            edge = edge->nextOut;
        }
        printf("\n");
    }

    printf("入弧链表:\n");
    for(int i = 0; i < GC->numNodes; i++)
    {
        printf("[%d]%c:", i, GC->nodes[i].value);
        EdgeNodeC *edge = GC->nodes[i].firstIn;
        while(edge != NULL)
        {
            printf("\n   [%p] start:%d, end:%d, nextIn:%p, nextOut:%p", edge,
             edge->start, edge->end, edge->nextIn, edge->nextOut);
            edge = edge->nextIn;
        }
        printf("\n");
    }
}

void FreeGraphC(GraphCross *GC)
{
    for(int i = 0; i < GC->numNodes; i++)
    {
        EdgeNodeC *edge = GC->nodes[i].firstOut;
        EdgeNodeC *next = NULL;
        while(edge != NULL)
        {
            next = edge->nextOut;
            free(edge);
            edge = next;
        }
    }
    free(GC);
}

//基于链表（邻接多重表）的无向图结构
//与基于链表（邻接表）的无向图结构相比，同一条边只用一个节点储存，便于对边进行修改
typedef struct EdgeNodeLC{
    int i;
    int j;
    EdgeType weight;
    struct EdgeNodeLC *iLink;
    struct EdgeNodeLC *jLink;
} EdgeNodeLC;

typedef struct GraphNodeLC{
    NodeType value;
    EdgeNodeLC *first;
} GraphNodeLC;

typedef struct GraphListCross{
    GraphNodeLC nodes[NODE_MAX];
    int numNodes, numEdges;
} GraphListCross;

void CreateGraphLC(GraphListCross *GLC)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    GLC->numEdges = e;
    GLC->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &GLC->nodes[i].value);
        GLC->nodes[i].first = NULL;
    }       
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        EdgeNodeLC *edge = malloc(sizeof(EdgeNodeLC));
        edge->i = start;
        edge->j = end;
        edge->weight = weight;
        edge->iLink = GLC->nodes[start].first;
        edge->jLink = GLC->nodes[end].first;
        GLC->nodes[start].first = edge;
        GLC->nodes[end].first = edge;
    }
}

void PrintGraphLC(GraphListCross *GLC)
{
    for(int i = 0; i < GLC->numNodes; i++)
    {
        printf("[%d] %c:", i, GLC->nodes[i].value);
        EdgeNodeLC *edge = GLC->nodes[i].first;
        while(edge != NULL)
        {
            printf("\n   [%p] (%d, %d), iLink:%p, jLink:%p, weight:%d"
            , edge, edge->i, edge->j, edge->iLink, edge->jLink, edge->weight);
            edge = edge->iLink;
        }
        printf("\n");
    }
}

void FreeGraphLC(GraphListCross *GLC)
{
    //后续补充
}

//基于数组（边集数组）的图结构
//和基于数组（邻接矩阵）的图结构相比，使用一维数组直接储存边数据，更侧重于边的操作
#define EDGE_MAX 100
typedef struct Edge{
    int start;
    int end;
    EdgeType weight;
}Edge;

typedef struct GraphArrayEdge{
    NodeType nodes[NODE_MAX];
    Edge egdes[EDGE_MAX];
    int numNodes, numEdges;
}GraphArrayEdge;

void CreateGraphE(GraphArrayEdge *GE)
{
    int n,e;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    GE->numEdges = e;
    GE->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &GE->nodes[i]);
    }
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &GE->egdes[i].start, &GE->egdes[i].end, &GE->egdes[i].weight);
    }

}

void PrintGraphE(GraphArrayEdge *GE)
{
    for(int i = 0; i < GE->numNodes; i++)
    {
        printf("%3c", GE->nodes[i]);
    }
    printf("\n\n");
    for(int i = 0; i < GE->numEdges; i++)
    {
        printf("%3d %3d %3d\n", GE->egdes[i].start, GE->egdes[i].end, GE->egdes[i].weight);
    }     
}


int main()
{
    /*GraphArray *G = malloc(sizeof(GraphArray));
    CreateGraph(G);
    PrintGraph(G);
    free(G);*/

    /*GraphList *GL = malloc(sizeof(GraphList));
    CreateGraphL(GL);
    PrintGraphL(GL);
    FreeGraphL(GL);*/

    /*GraphCross *GC = malloc(sizeof(GraphCross));
    CreateGraphC(GC);
    PrintGraphC(GC);
    FreeGraphC(GC);*/

    /*GraphListCross *GLC = malloc(sizeof(GraphListCross));
    CreateGraphLC(GLC);
    PrintGraphLC(GLC);
    FreeGraphLC(GLC);*/

    GraphArrayEdge *GE = malloc(sizeof(GraphArrayEdge));
    CreateGraphE(GE);
    PrintGraphE(GE);
    free(GE);
    system("pause");
}

图的遍历

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

//以使用邻接矩阵的图为例
typedef char NodeType;
typedef int EdgeType;
#define NODE_MAX 100
#define INFINITE 65535
typedef struct GraphArray{
    NodeType nodes[NODE_MAX];
    EdgeType arc[NODE_MAX][NODE_MAX];
    int numNodes, numEdges;
    
}GraphArray;

//访问标记
bool visited[NODE_MAX];


void CreateGraph(GraphArray *G)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    G->numEdges = e;
    G->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &G->nodes[i]);
    }
    for(int i = 0; i < n; i++)
        for(int m = 0; m < n; m++)
            G->arc[i][m] = i == m ? 0 : INFINITE;
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        //以有向图为例
        G->arc[start][end] = weight;
    }

}

//深度优先遍历（DFS）
//顶点递归函数
void DepthFirstSearchNode(GraphArray *G, int nodeIndex)
{
    //设置标记
    visited[nodeIndex] = true;
    //遍历时的操作，这里以输出顶点值为例
    printf("%3c", G->nodes[nodeIndex]);
    //寻找邻接点
    for(int i = 0; i < G->numNodes; i++)
    {
        //寻找未访问过的邻接点
        if(G->arc[nodeIndex][i] != INFINITE && !visited[i])
        {
            //递归
            DepthFirstSearchNode(G, i);
        }
    }
}

//遍历函数
void DepthFirstSearch(GraphArray *G)
{
    //初始标记均为假
    for(int i = 0; i < G->numNodes; i++)
        visited[i] = false;

    //连通图扫描一次即可，非连通图只需将所有连通分量各扫描一次
    for(int i = 0; i < G->numNodes; i++)
    {
        //可能在之前的遍历中被访问过，此时跳过
        if(!visited[i])
            DepthFirstSearchNode(G, i);
    }
}

//广度优先遍历BFS
//借助队列，代码可见上文
void BreadthFirstSearch(GraphArray *G)
{
    LinkQueue *Q = CreateQueue();
    int index;
    //初始标记均为假
    for(int i = 0; i < G->numNodes; i++)
    {
        visited[i] = false;
    }

    //开始遍历，此处循环是为了遍历到所有连通分量，如果是连通图循环可以去掉
    for(int i = 0; i < G->numNodes; i++)
    {
        //跳过已经访问过的顶点
        if(visited[i]) continue;
        //入列
        EnQueue(Q, i);
        //设置访问标记并输出
        visited[i] = true;
        printf("%3c", G->nodes[i]);
        while(QueueLength(Q) != 0)
        {
            //出列
            DeQueue(Q, &index);
            //寻找邻接点，并将未访问过的邻接点入列
            for(int n = 0; n < G->numNodes; n++)
            {
                if(G->arc[index][n] != INFINITE && !visited[n])
                {
                    EnQueue(Q, n);
                    visited[n] = true;
                    printf("%3c", G->nodes[n]);
                }       
            }
        }
    }
    ClearQueue(Q);

}

int main()
{
    GraphArray *G = malloc(sizeof(GraphArray));
    CreateGraph(G);

    //邻接矩阵，时间复杂度O(n²)
    //如果使用邻接表，时间复杂度O(n+e)
    DepthFirstSearch(G);
    printf("\n");
    BreadthFirstSearch(G);
    free(G);
    system("pause");
}

图的最小生成树

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

//使用邻接矩阵的无向图
typedef char NodeType;
typedef int EdgeType;
#define NODE_MAX 100
#define INFINITE 65535
typedef struct GraphArray{
    NodeType nodes[NODE_MAX];
    EdgeType arc[NODE_MAX][NODE_MAX];
    int numNodes, numEdges;
    
}GraphArray;

void CreateGraph(GraphArray *G)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    G->numEdges = e;
    G->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &G->nodes[i]);
    }
    for(int i = 0; i < n; i++)
        for(int m = 0; m < n; m++)
            G->arc[i][m] = i == m ? 0 : INFINITE;
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        //无向图
        G->arc[start][end] = weight;
        G->arc[end][start] = weight;
    }

}

//基于边集数组的无向图结构
#define EDGE_MAX 100
typedef struct Edge{
    int start;
    int end;
    EdgeType weight;
}Edge;

typedef struct GraphArrayEdge{
    NodeType nodes[NODE_MAX];
    Edge egdes[EDGE_MAX];
    int numNodes, numEdges;
}GraphArrayEdge;

void CreateGraphE(GraphArrayEdge *GE)
{
    int n,e;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    GE->numEdges = e;
    GE->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &GE->nodes[i]);
    }
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &GE->egdes[i].start, &GE->egdes[i].end, &GE->egdes[i].weight);
    }

}

//Prim算法
void Prim(GraphArray *G)
{
    //储存最小生成树到树之外的顶点的边的最低权值
    //INFINITE表示无法连接到此顶点
    //0表示顶点已经被选中到最小生成树中
    int lowWeight[G->numNodes];

    //储存lowWeight中最小权值的边相关联的最小生成树中的顶点的下标
    //lowWeight和lowIndex使用了VLA特性
    int lowIndex[G->numNodes];

    //最初时，最小生成树放入一个顶点，这里以第一个顶点为例
    lowIndex[0] = 0;
    lowWeight[0] = 0;

    int min;
    int minIndex;

    //此时生成树只有一个顶点，直接赋值即可
    for(int i = 1; i < G->numNodes; i++)
    {
        lowWeight[i] = G->arc[0][i];
        lowIndex[i] = 0;
    }
   
    //因为第一个顶点已经被选中，所以循环从1开始
    //每次循环获取一条边，共获取n-1条边，构成最小生成树
    for(int i = 1; i < G->numNodes; i++)
    {
        //开始寻找最小生成树当前可选择的的权值最低的边
        min = INFINITE;
        minIndex = 0;
        for(int j = 1; j < G->numNodes; j++)
        {
            //遍历未选中的点，并找到权值最低的那个
            if(lowWeight[j] != 0 && lowWeight[j] < min)
            {
                //储存最低权值以及对应的关联顶点下标
                min = lowWeight[j];
                minIndex = j;
            }

        }
        //此时已经找到了权值最低的边，即为最小生成树的新一条边
        printf("(%d,%d)\n", lowIndex[minIndex], minIndex);
        //将关联顶点标记为已选中
        lowWeight[minIndex] = 0;
        
        //接下来是刷新lowWeight和lowIndex数组，以便下一轮遍历
        //只需检索新顶点给最小生成树带来的新的边
        for(int j = 1; j < G->numNodes; j++)
        {
            //如果未选中，且新顶点关联的边权值更低，则刷新之前的数据
            if(lowWeight[j] != 0 && G->arc[minIndex][j] < lowWeight[j])
            {
                lowWeight[j] = G->arc[minIndex][j];
                lowIndex[j] = minIndex;
            }
        }
    }
}

//冒泡排序边集数组，可自由替换为其他排序算法
void SortEdges(Edge* a, int len) 
{
    int i, j;
    Edge temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        {
                if (a[j].weight > a[j+1].weight) //从小到大
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
                
        }
}

int Kruskal_Root(int *parent, int index)
{
    while(parent[index] > 0)
    {
        index = parent[index];
    }
    return index;
}

void Kruskal(GraphArrayEdge *GE)
{
    //储存最小生成树当前顶点间的邻接情况，用于判断是否会成环
    int parent[GE->numNodes];

    //储存最小生成树当前边的起点和终点的连通最末端点，用于判断是否会成环
    int n,m;

    //排序边集数组
    SortEdges(GE->egdes, GE->numEdges);

    //初始化
    for(int i = 0; i < GE->numNodes; i++)
        parent[i] = 0;

    //遍历每一条边
    for(int i = 0; i < GE->numEdges; i++)
    {
        //通过Kruskal_Root函数获取起点和终点的连通最末端点
        n = Kruskal_Root(parent, GE->egdes[i].start);
        m = Kruskal_Root(parent, GE->egdes[i].end);

        //最末端点不同，说明连通后不会成环
        if(n != m)
        {
            //连通两顶点，构成最小生成树的一条边
            parent[n] = m;
            printf("(%d,%d)\n", GE->egdes[i].start, GE->egdes[i].end);
        }
    }

}

int main()
{
    /*演示Prim算法
    GraphArray *G = malloc(sizeof(GraphArray));
    CreateGraph(G);
    Prim(G);
    free(G);*/

    //演示Kruskal算法
    GraphArrayEdge *GE = malloc(sizeof(GraphArrayEdge));
    CreateGraphE(GE);
    Kruskal(GE);
    free(GE);
    system("pause");

}

图的最短路径

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

//基于数组（邻接矩阵）的图结构
//使用二维数组储存顶点之间的邻接关系
typedef char NodeType;
typedef int EdgeType;
#define NODE_MAX 100
#define INFINITE 65535
//在邻接矩阵中，INFINITE表示顶点间无邻接关系
typedef struct GraphArray{
    NodeType nodes[NODE_MAX];
    EdgeType arc[NODE_MAX][NODE_MAX];
    int numNodes, numEdges;
    
}GraphArray;

void CreateGraph(GraphArray *G)
{
    int n,e;
    int start, end, weight;
    printf("输入顶点个数和边/弧数：\n");
    scanf("%d %d", &n, &e);
    G->numEdges = e;
    G->numNodes = n;
    while(getchar() != '\n');
    printf("输入顶点值：\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &G->nodes[i]);
    }
    for(int i = 0; i < n; i++)
        for(int m = 0; m < n; m++)
            G->arc[i][m] = i == m ? 0 : INFINITE;
    
    printf("输入边的起点、终点和权：\n");
    for(int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &start, &end, &weight);
        G->arc[start][end] = weight;
        G->arc[end][start] = weight;
    }

}


//Dijkstra算法，时间复杂度O(n²)
//求某一个顶点到其余所有顶点的最短路径
void Dijkstra(GraphArray *G, int start, int * patharc, int * shortDistances)
{
    bool selected[G->numNodes];
    int min;
    int minIndex;

    //初始化
    for(int i = 0; i < G->numNodes; i++)
    {
        //所有顶点未选中
        selected[i] = false;

        //初始化时储存源点到其他各点的距离（权）
        //INFINITE表示不可到达
        //0表示已经连接
        //之后该数组将储存当前最短路径选中的顶点到其余点的最短距离
        //并在每次有新的顶点被选中后更新数据
        //以此确保路径是距离最短的
        shortDistances[i] = G->arc[start][i];

        //储存最短路径经过的顶点
        patharc[i] = -1;
        
    }

    //选中源点
    shortDistances[start] = 0;
    selected[start] = true;

    //开始遍历
    for(int i = 1; i < G->numNodes; i++)
    {

        //寻找当前可选择的最短（权值最低）邻接点
        min = INFINITE;
        for(int j = 0; j < G->numNodes; j++)
        {
            if(!selected[j] && shortDistances[j] < min)
            {
                //记录当前可选择的最短路径的距离和该点下标
                min = shortDistances[j];
                minIndex = j;
            }
        }

        //选中该点，构成最短路径中的其中一条
        selected[minIndex] = 1;


        //更新数据
        for(int j = 0; j < G->numNodes; j++)
        {
            //遍历未选中的点，更新shortDistances数组
            //此处 min + G.arc[minIndex][j] 是基于新加入的点计算到各点的距离
            //shortDistances[j] 是选中新的点之前到各点的最短距离
            if(!selected[j] && (min + G->arc[minIndex][j] < shortDistances[j]))
            {
                shortDistances[j] = min + G->arc[minIndex][j];

                //由于shortDistances只储存了最短距离，而没有具体储存路径经过的点
                //故通过patharc数组储存每一次更新最短距离时到该顶点的前驱顶点
                //即源点到第 j 个顶点的最短路径的倒数第二个顶点为 patharc[j]
                //倒数第三个顶点为patharc[patharc[j]]，以此类推，直到源点
                patharc[j] = minIndex;
            }
        }
    }
    
}

//Floyd算法，时间复杂度O(n³)
//求所有顶点之间的最短路径
void Floyd(GraphArray *G, 
    int pathMatrix[G->numNodes][G->numNodes], int distanceMatrix[G->numNodes][G->numNodes])
{
    //初始化
    for(int i = 0; i < G->numNodes; i++)
    {
        for(int j = 0; j < G->numNodes; j++)
        {
            pathMatrix[i][j] = j;
            distanceMatrix[i][j] = G->arc[i][j];
        }
    }   

    for(int k = 0; k < G->numNodes; k++)
    {
        for(int i = 0; i < G->numNodes; i++)
        {
            for(int j = 0; j < G->numNodes; j++)
            {
                if(distanceMatrix[i][k] + distanceMatrix[k][j] < distanceMatrix[i][j])
                {
                    distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
                    pathMatrix[i][j] = pathMatrix[i][k];
                }
            }
        }   

    }

}

int main()
{
    GraphArray *G = malloc(sizeof(GraphArray));
    CreateGraph(G);
    int patharc[G->numNodes];
    int shortPathTable[G->numNodes];
    int start = 0;
    Dijkstra(G, start, patharc, shortPathTable);
    printf("\nDijkstra算法：\n");
    for(int i = 0; i < G->numNodes; i++)
    {
        int j = i;
        printf("The shortest distance between %d and %d is %d. \tThe path is:  ", start, i, shortPathTable[i]);
        printf("\t%d < ", i);
        do
        {
            j = patharc[j];
            if(j == -1)
                printf("%d", start);
            else
                printf("%d < ", j);
        }while(j != -1);
        printf("\n");
    }

    //Floyd算法
    printf("\nFloyd算法：\n");
    int pathMatrix[G->numNodes][G->numNodes];
    int distanceMatrix[G->numNodes][G->numNodes];
    Floyd(G, pathMatrix, distanceMatrix);
    for(int i = 0; i < G->numNodes; i++)
    {
        for(int j = i + 1; j < G->numNodes; j++)
        {
            printf("The shortest distance between %d and %d is %d. \tThe path is:  ", i, j, distanceMatrix[i][j]);
            printf("\t%d > ", i);
            int k = i;
            do
            {
                k = pathMatrix[k][j];
                printf(k == j ? "%d" : "%d > ", k);
            } while (k != j);
            printf("\n");
            
        }
    }
    free(G);
    system("pause");
    return 0;
}

有序表查询

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

//逐一查询
int search(int * array, int len, int key)
{
    for(int i = 0; i < len; i++)
    {
        if(array[i] == key)
            return i;
    }
    return -1;
}

//含哨兵的逐一查询
//可以省去下标越界检查，提高效率
int search_sentinel(int * array, int len, int key)
{
    //在第一个成员处设置哨兵，此时查询数据应开始于第二个成员
    //若返回0，则表示查询失败
    array[0] = key;
    int i = len - 1;
    while(array[i] != key)
    {
        i--;
    }
    return i;
}

//二分查询
int search_binary(int * array, int len, int key)
{
    int low, high, mid;
    low = 0;
    high = len - 1;
    while(low <= high)
    {
        mid = low + (high - low)/2;
        if(array[mid] < key)
            low = mid + 1;
        else if(array[mid] > key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

//插值查询
//适合数据较为均匀的有序表
int search_interpolation(int * array, int len, int key)
{
    int low, high, mid;
    low = 0;
    high = len - 1;
    while(low <= high)
    {
        mid = low + (key - array[low]) / (array[high] - array[low]) * (high - low);
        if(array[mid] < key)
            low = mid + 1;
        else if(array[mid] > key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}


//斐波那契查询
int search_fibonacci(int * array, int len, int key)
{
    //构造斐波那契数列，这一步可以提前做好
    int fibonacci[len];
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for(int i = 2; i < len; i++)
    {
        fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1]; 
    }

    /*for(int i = 0; i < len; i++)
        printf("%d,", fibonacci[i]);
    printf("\n");*/

    //扩充数组
    int low, high, mid, k = 0;
    low = 0;
    high = len - 1;
    while(len > fibonacci[k])
        k++;
    int array_fib[fibonacci[k]];
    memcpy(array_fib, array, sizeof(int) * len);
    for(int i = len; i < fibonacci[k]; i++)
        array_fib[i] = array[high];
    
    /*for(int i = 0; i < fibonacci[k]; i++)
        printf("%d,", array_fib[i]);*/

    //开始查找
    while(low <= high)
    {
        mid = low + fibonacci[k - 1] - 1;
        if(key < array_fib[mid])
        {
            high = mid - 1;
            k -= 1;
        }
        else if(key > array_fib[mid])
        {
            low = mid + 1;
            k -= 2;
        }
        else
        {
            //判断查询结果是否为扩充成员，如果是则校正返回的索引
            return mid <= high ? mid : high;
        }
    }
    return -1;
}

int main()
{
    int array[] = {0, 1, 4, 7, 10, 15, 20, 33, 55, 78};
    int key = 10;
    int index = search_fibonacci(array, sizeof(array) / sizeof(int), key);
    printf("%d", index);
    system("pause");
    return 0;
}

二叉排序树

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

//二叉排序树
typedef struct BinarySortTreeNode
{
    int data;
    struct BinarySortTree * left, * right;
}BinarySortTreeNode, *BinarySortTree;


//二叉排序树查找元素
//fore  ：传递（实际上是一个指针，但本身作为形参）上一次查找的节点（无论最终查找是否成功），调用函数时传递NULL即可
//ret   ：返回查找成功时元素所在的结点，或者查找失败前最后查询的节点，注意这里需要使用指针传递
//查找失败时，实际上将fore赋值给ret即为最后查找的节点，用于确定该元素插入二叉排序树时的位置
bool SearchBinarySortTree(BinarySortTree T, int key, BinarySortTree fore, BinarySortTree *ret)
{
    //若T为NULL，表示查找结束，并且未查找到该元素
    //特别地，若一开始T就为NULL，即根节点为NULL，则ret返回NULL
    if(!T)
    {
        //返回最后查询的节点
        *ret = fore;
        return false;
    }

    //查找到该元素，返回当前节点
    if(key == T->data)
    {
        *ret = T;
        return true;
    }
    else if(key > T->data)
    {
        //查找未结束，继续递归
        return SearchBinarySortTree(T->right, key, T, ret);
    }
    else
    {
        return SearchBinarySortTree(T->left, key, T, ret);
    }
        
}

//二叉排序树插入元素
bool InsertBinarySortTree(BinarySortTree *T, int key)
{
    BinarySortTree p, s;

    //查找该元素，若元素已经存在，则返回假
    //若元素不存在，则p即为元素应该插入的节点
    if(SearchBinarySortTree(*T, key, NULL, &p))
        return false;
    
    //创建结点，并赋相关数据
    s = malloc(sizeof(BinarySortTreeNode));
    s->data = key;
    s->left = NULL;
    s->right = NULL;

    //判断用户传入的T（根节点）是否为NULL，如果是则直接赋值根节点
    //否则插入元素到合适的位置
    if(!p)
        *T = s;
    else if(key < p->data)
        p->left = s;
    else
        p->right = s;
    return true;
}

//二叉排序树删除元素 节点删除函数
bool DeleteBinarySortTree_Delete(BinarySortTree *T)
{
    BinarySortTree s, t;

    //子树有一个为空时，直接将非空的子树转移到待删除节点的父节点即可
    if((*T)->left == NULL)
    {
        s = *T;
        *T = (*T)->right;
        free(s);
    }
    else if((*T)->right == NULL)
    {
        s = *T;
        *T = (*T)->left;
        free(s);
    }
    else
    {
        //子树均不为空的情况
        //先获取待删除节点的前驱节点（小于它的最大节点）
        s = *T;
        t = s->left;
        while(t->right)
        {
            s  = t;
            t = t->right;
        }
        //此时t指向待删除节点的前驱节点，其右子树必定为空，s指向前驱节点的父节点
        //接下来用前驱节点替换待删除节点
        (*T)->data = t->data;

        //若前驱节点的父节点恰为待删除节点，说明前驱节点恰好是待删除节点的左子树
        //此时将前驱节点的左子树（可能也为空）替换其父节点（也是待删除节点）的左子树即可
        //否则，说明前驱节点的左子树节点 大于 前驱节点的父节点
        //此时将前驱节点的左子树（可能也为空）替换其父节点（和待删除节点不同）的右子树即可
        if(*T == s)
            s->left = t->left;
        else
            s->right = t->left;
    }
    return true;
}

//二叉排序树删除元素
//采用递归，不断判断当前结点是否为待删除节点
bool DeleteBinarySortTree(BinarySortTree *T, int key)
{
    //查找结束，且未找到待删除元素
    if(!*T)
        return false;
    else
    {
        //查找到待删除元素，执行节点删除函数
        //否则继续递归
        if(key == (*T)->data)
            return DeleteBinarySortTree_Delete(T);
        else if(key > (*T)->data)
            return DeleteBinarySortTree(&(*T)->right, key);
        else
            return DeleteBinarySortTree(&(*T)->left, key);
    }
}

//二叉排序树销毁
void FreeBinarySortTree(BinarySortTree *T)
{
    if(!(*T))
        return;
    FreeBinarySortTree(&(*T)->left);
    FreeBinarySortTree(&(*T)->right);
    printf("node freed: %d\n", (*T)->data);
    free(*T);
}

int main()
{
    int array[] = {1, 11, 24, 5, 77, 12, 99, 10, 45, 33};
    //构造二叉排序树，此方法构造的二叉排序树不一定是平衡二叉树（AVL）
    //特别是插入的数据若是按大小排列的，所构造的二叉排序树退化成链表，效率很低
    BinarySortTree T, p;
    int key = 10;
    for(int i = 0; i < sizeof(array) / sizeof(int); i++)
    {
        if(InsertBinarySortTree(&T, array[i]))
            printf("element inserted: %d\n", array[i]);
    }
    //查找元素
    if(SearchBinarySortTree(T, key, NULL, &p))
        printf("element found: %d\n", p->data);

    //删除元素
    if(DeleteBinarySortTree(&T, key))
        printf("element delete: %d\n", key);
    if(!SearchBinarySortTree(T, key, NULL, &p))
        printf("element not found: %d\n", key);

    //销毁
    FreeBinarySortTree(&T);
    system("pause");
    return 0;   
}

AVL树

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//平衡因子
enum BalanceFactor{
    RightHigher = -1,
    LeftHigher = 1,
    EqualHigh = 0,
};

//AVL树结构定义
typedef struct AVLTreeNode
{
    int data;
    enum BalanceFactor balanceFactor;
    struct AVLTreeNode *left, *right;
}AVLTreeNode, *AVLTree;

//AVL 右旋子树
void AVL_RotateR(AVLTree *T)
{
    AVLTree s;
    s = (*T)->left;
    (*T)->left = s->right;
    s->right = *T;
    *T = s;
}

//AVL 左旋子树
void AVL_RotateL(AVLTree *T)
{
    AVLTree s;
    s = (*T)->right;
    (*T)->right = s->left;
    s->left = *T;
    *T = s;
}

//AVL 平衡LeftOverHigher
void AVL_BalanceLOH(AVLTree *T)
{
    AVLTree s, sr;
    s = (*T)->left;
    switch (s->balanceFactor)
    {
        case LeftHigher:
            (*T)->balanceFactor = EqualHigh;
            s->balanceFactor = EqualHigh;
            AVL_RotateR(T);
            break;

        case RightHigher:
            sr = s->right;
            switch (sr->balanceFactor)
            {
            case LeftHigher:
                (*T)->balanceFactor = RightHigher;
                s->balanceFactor = EqualHigh;
                break;

            case RightHigher:
                (*T)->balanceFactor = EqualHigh;
                s->balanceFactor = LeftHigher;
                break;

            case EqualHigh:
                (*T)->balanceFactor = EqualHigh;
                s->balanceFactor = EqualHigh;
                break;
        }
        sr->balanceFactor = EqualHigh;
        AVL_RotateL(&(*T)->left);
        AVL_RotateR(T);
    }
}

//AVL 平衡RightOverHigher
void AVL_BalanceROH(AVLTree *T)
{
    AVLTree s, sl;
    s = (*T)->right;
    switch (s->balanceFactor)
    {
        case RightHigher:
            (*T)->balanceFactor = EqualHigh;
            s->balanceFactor = EqualHigh;
            AVL_RotateL(T);
            break;

        case LeftHigher:
            sl = s->left;
            switch (sl->balanceFactor)
            {
                case LeftHigher:
                    (*T)->balanceFactor = EqualHigh;
                    s->balanceFactor = RightHigher;
                    break;

                case RightHigher:
                    (*T)->balanceFactor = LeftHigher;
                    s->balanceFactor = EqualHigh;
                    break;

                case EqualHigh:
                    (*T)->balanceFactor = EqualHigh;
                    s->balanceFactor = EqualHigh;
                    break;
            }
            sl->balanceFactor = EqualHigh;
            AVL_RotateR(&(*T)->right);
            AVL_RotateL(T);
    }
}

bool AVLInsert(AVLTree *T, int key, bool * taller)
{
    if(!*T)
    {
        *T = malloc(sizeof(AVLTreeNode));
        (*T)->data = key;
        (*T)->left = NULL;
        (*T)->right = NULL;
        (*T)->balanceFactor = EqualHigh;
        *taller = true;
        return true;
    }

    if(key == (*T)->data)
    {
        *taller = false;
        return false;
    }

    if(key < (*T)->data)
    {
        if(!AVLInsert(&(*T)->left, key, taller))
            return false;

        if(*taller)
        {
            switch ((*T)->balanceFactor)
            {
                case LeftHigher:
                    AVL_BalanceLeftHigher(T);
                    *taller = false;
                    break;
                
                case RightHigher:
                    (*T)->balanceFactor = EqualHigh;
                    *taller = false;

                case EqualHigh:
                    (*T)->balanceFactor = LeftHigher;
                    *taller = true;
                    break;
            }
        }
    }
    else
    {
        if(!AVLInsert(&(*T)->right, key, taller))
            return false;
        
        if(*taller)
        {
            switch((*T)->balanceFactor)
            {
                case LeftHigher:
                    (*T)->balanceFactor = EqualHigh;
                    *taller = false;
                    break;
                case RightHigher:
                    AVL_BalanceRightHigher(T);
                    *taller = false;
                    break;
                case EqualHigh:
                    (*T)->balanceFactor = RightHigher;
                    *taller = true;
                    break;
            }
        }

    }
    return true;
}

//AVL 输出
void AVLPrint(AVLTree *T)
{
    if(!*T)
        return;
    printf("%d,", (*T)->data);
    AVLPrint(&(*T)->left);
    AVLPrint(&(*T)->right);
}

int main()
{
    int array[] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
    AVLTree T = NULL;
    bool taller;
    for(int i = 0; i < sizeof(array) / sizeof(int); i++)
    {
        AVLInsert(&T, array[i], &taller);
    }
    AVLPrint(&T);
    system("pause");
    return 0;
}

 

哈希表（HashTable）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define HASH_TABLE_SIZE 100

typedef struct HashTableNode
{
    const char * key;
    const char * value;
    struct HashTableNode * next;
}HashTableNode;

typedef struct HashTable
{
    HashTableNode * nodes[HASH_TABLE_SIZE];
    int count;
} HashTable;

void HashTableInit(HashTable *H)
{
    H->count = HASH_TABLE_SIZE;
    for(int i = 0; i < H->count; i++)
    {
        H->nodes[i] = NULL;
    }
}

unsigned int Hash(const char * key)
{
    unsigned long hash = 0;
    for(int i = 0; i < strlen(key); i++)
        hash = hash * 33 + key[i];
    return hash % HASH_TABLE_SIZE;
}

bool HashSearch(HashTable * H, const char * key, HashTableNode ** ret)
{
    HashTableNode *node;
    unsigned int index = Hash(key);
    for(node = H->nodes[index]; node; node = node->next)
    {
        if(strcmp(key, node->key) == 0)
        {
            *ret = node;
            return true;
        }
    }
    *ret = NULL;
    return false;
}

void HashSet(HashTable * H, const char * key, const char * value)
{
    HashTableNode *node;
    if(HashSearch(H, key, &node))
        node->value = value;
    else
    {
        unsigned int index = Hash(key);
        node = malloc(sizeof(HashTableNode));
        node->key = key;
        node->value = value;
        node->next = H->nodes[index];
        H->nodes[index] = node;
    }
}

int main()
{
    HashTable *H = malloc(sizeof(HashTable));
    HashTableNode *node;
    char key[100][5];
    char value[100][5];

    HashTableInit(H);
    for(int i = 0; i < 100; i++)
    {
        HashSet(H, itoa(i + 1000, key[i], 10), itoa(i, value[i], 10));
    }
    for(int i = 0; i < 100; i++)
    {
        bool ret = HashSearch(H, itoa(i + 1000, key[i], 10), &node);
        if(ret)
            printf("%s = %s\n", node->key, node->value);
        else
            printf("%s not found\n", key[i]);
    }
    system("pause");
    return 0;
}

冒泡排序和选择排序

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

//交换数组两个成员的值
void swap(int a[], int i, int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

//冒泡排序 O(n^2)
//a[0]保留不用
void BubbleSort(int * a, int len)
{
    int temp;
    //交换标记，如果某一轮比较中未发生任何交换，则排序已经结束
    //初始时为true，以便开始循环
    bool exchanged = true;
    for(int i = 1; i < len && exchanged; i++)
    {
        exchanged = false;
        //每一轮排序结束，就有一个位置的元素被确定，这些确定的位置不再参与比较
        //优化空间：记录每轮最后交换的位置，以便下一轮缩小要比较的区间
        for(int j = len; j > i; j--)
        {
            if(a[j] < a[j-1])
            {
                swap(a, j, j-1);
                exchanged = true;
            }
        }
    }
}

//简单选择排序 O(n^2)
//a[0]保留不用
void SelectionSort(int * a, int len)
{
    int min;
    for(int i = 1; i < len; i++)
    {
        min = i;
        for(int j = i + 1; j <= len; j++)
        {
            if(a[j] < a[min])
                min = j;
        }
        if(min != i)
            swap(a, min, i);
    }
}

插入排序和希尔排序

//直接插入排序 O(n^2)
//a[0]保留，用作哨兵
void InsertionSort(int * a, int len)
{
    //从a[1]开始比较，将相邻元素插入其左右两侧
    int j;
    for(int i = 2; i <= len; i++)
    {
        if(a[i] < a[i - 1])
        {
            //将a[i]储存在a[0]
            a[0] = a[i];
            //将a[i]之前的比a[i]大的元素右移
            //并找到右移前 a[i]之前的最后一个比a[i]大的元素的下标
            for(j = i - 1; a[j] > a[0]; j--)
            {
                a[j + 1] = a[j];
            }
            //最后将a[i]放入该下标，注意该下标应该是j + 1
            //因为j在最后一次for循环条件判断中被减了1
            a[j + 1] = a[0];
        }
    }
}

//希尔排序 时间复杂度小于O(n^2) 取决于增量序列
//a[0]保留，用作哨兵
void ShellSort(int * a, int len)
{
    int delta = len - 1;
    int i,j;
    do
    {
        //增量算法，也可以先求出增量序列
        delta = delta / 3 + 1;
        for(i = delta + 1; i < len; i++)
        {
            //排序子列，本质上是一种插入排序
            if(a[i] < a[i - delta])
            {
                a[0] = a[i];
                for(j = i - delta; j > 0 && a[0] < a[j]; j -= delta)
                    a[j + delta] = a[j];
                a[j + delta] = a[0];
            }
        }
    } while (delta > 1);
    
}

堆排序和归并排序

//堆排序 堆构造函数
//用数组start~end的元素构造大顶堆，并按层序调整
void HeapSort_Adjust(int * array, int start, int end)
{
    
    int temp,j;
    temp = array[start];

    //此处运用了完全二叉树的性质
    //按层序索引，节点start的左子节点为 2 * start
    //节点start的右子节点为2 * start + 1
    for(j = 2 * start; j <= end; j*= 2)
    {
        // j < end是为了保证j不是最后一个节点，否则j+1会越界
        //此处是判断左子节点和右子节点哪个大，并让j指向较大的那个
        if(j < end && array[j] < array[j+1])
            j++;

        //start节点的值大于两个子节点，说明满足大顶堆，直接跳出循环
        if(temp >= array[j])
            break;
        
        //否则，交换start节点和其较大的子节点的值
        array[start] = array[j];
        start = j;
    }
    array[start] = temp;
}

//堆排序 O(nlogn)
//a[0]保留不用
void HeapSort(int * array, int len)
{
    int i;

    //此处运用了完全二叉树的性质
    //len / 2 是该大顶堆最后一个（按层序索引）有子节点的节点
    //索引小于等于 len / 2 的节点均有子节点，并对这些有子节点的节点构造大顶堆
    //循环结束后，整个数组的大顶堆便构造完成了
    for(int i = len / 2; i > 0; i--)
        HeapSort_Adjust(array, i, len);
    
    //构造的大顶堆，其根节点即为最大的元素
    //每次排除最大元素，并将剩下元素再次构造大顶堆，直到排序结束
    for(int i = len; i > 1; i--)
    {
        swap(array, i, 1);
        HeapSort_Adjust(array, 1, i-1);
    }
}

//归并排序 合并函数
void MergingSort_Merge(int sorted[], int dst[], int start, int m, int end)
{
    //将 sorted[start .. m] 与 sorted[m + 1 .. end] 的元素按顺序合并到 dst
    //此时 sorted[start .. m] 与 sorted[m + 1 .. end] 分别有序
    int i,j,k = start;
    for(i = start, j = m + 1; i <= m && j <= end; k++)
    {
        if(sorted[i] < sorted[j])
            dst[k] = sorted[i++];
        else
            dst[k] = sorted[j++];
    }

    //合并多余元素
    while(i <= m)
    {
        dst[k++] = sorted[i++];
    }

    while(j <= end)
    {
        dst[k++] = sorted[j++];
    }
}

//归并排序 递归函数
void MergingSort_Sort(int src[], int dst[], int start, int end, int arrayLen)
{
    int m;
    int sorted[arrayLen];

    //分割直到只有单个元素
    if(start == end)
        dst[start] = src[start];
    else
    {
        //递归，继续分割
        m = (start + end) / 2;
        MergingSort_Sort(src, sorted, start, m, arrayLen);
        MergingSort_Sort(src, sorted, m + 1, end, arrayLen);
        //最终自下向顶合并
        MergingSort_Merge(sorted, dst, start, m, end);
    }
}

//归并排序 递归版 O(nlogn)
//空间复杂度为O(n+logn)
//a[0]保留不用
void MergingSort(int * array, int len)
{
    MergingSort_Sort(array, array, 1, len, len + 1);
}

//归并排序 非递归版 两两合并函数
//将数列中长度为blockLen的子列两两合并
//剩下不足blokenLen的子列也将合并
void MergingSort_MergeBinary(int array[], int dst[], int blockLen, int len)
{
    int i;
    //处理前面k对子列，每对子列长度为 2 * blockLen
    //循环结束后余下总长小于 2 * blockLen
    for(i = 1; i + 2 * blockLen - 1 <= len; i += blockLen * 2)
        MergingSort_Merge(array, dst, i, i + blockLen - 1, i + 2 * blockLen - 1);

    //如果余下总长大于 blockLen，则可以将其分为两个子列进行合并
    //其中第一个子列长为 blockLen，第二个子列长小于 blockLen
    if(i + blockLen - 1 < len)
        MergingSort_Merge(array, dst, i, i + blockLen - 1, len);
    else
    {
        //如果余下总长小于等于 blockLen，则直接复制即可
        for(int j = i; j <= len; j++)
            dst[j] = array[j];
    }
}

//归并排序 非递归版 O(nlogn)
//空间复杂度为O(n)
//a[0]保留不用
void MergingSort2(int * array, int len)
{
    int dst[len + 1];
    int k = 1;
    while(k < len)
    {
        MergingSort_MergeBinary(array, dst, k, len);
        k *= 2;
        MergingSort_MergeBinary(dst, array, k, len);
        k *= 2;
    }
}

快速排序

//快速排序 获取枢轴(Pivot)
int QuickSort_Partition(int * array, int low, int high)
{
    int m = (low + high) / 2;
    if(array[low] > array[high])
        swap(array, low, high);
    if(array[m] > array[high])
        swap(array, m, high);
    if(array[low] < array[m])
        swap(array, low, m);

    int pivotKey = array[low];
    array[0] = pivotKey;
    while(low < high)
    {
        while(low < high && array[high] >= pivotKey)
            high--;          
        array[low] = array[high];
        while(low < high && array[low] <= pivotKey)
            low++;
        array[high] = array[low];
    }
    array[low] = array[0];
    return low;
}

//快速排序 递归函数
void QuickSort_Sort(int * array, int low, int high)
{
    int pivot;
    if(low < high)
    {
        while(low < high)
        {
            pivot = QuickSort_Partition(array, low, high);
            QuickSort_Sort(array, low, pivot - 1);
            //QuickSort_Sort(array, pivot + 1, high);
            //尾递归优化
            low = pivot + 1;
        }
    }
}

//快速排序 O(nlogn)
//空间复杂度 O(logn)
//a[0]保留用作临时变量
void QuickSort(int * array, int len)
{
    QuickSort_Sort(array, 1, len);
}

排序算法测试

相关代码见上文

void PrintArray(int * array, int len, const char * prefix)
{
    printf("%s  ", prefix);
    for(int i = 1; i <= len; i++)
        printf("%d, ", array[i]);
    printf("\n\n");
}

void RandArray(int * array, int len)
{
    for(int i = 1; i <= len; i++)
    {
        array[i] = rand();
    }
}


int main()
{
    //int array[] = {9, 1, 5, 8, 3, 7, 4, 6, 2, 5};
    //int array[] = {2, 1, 3, 4, 5, 6, 7, 8, 9,10};
    int array[21];
    int len = sizeof(array) / sizeof(int) - 1;
    srand(time(NULL));

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    BubbleSort(array, len);
    PrintArray(array, len, "冒泡排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    SelectionSort(array, len);
    PrintArray(array, len, "选择排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    InsertionSort(array, len);
    PrintArray(array, len, "插入排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    ShellSort(array, len);
    PrintArray(array, len, "希尔排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    HeapSort(array, len);
    PrintArray(array, len, "堆排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    MergingSort2(array, len);
    PrintArray(array, len, "归并排序");

    RandArray(array, len);
    PrintArray(array, len, "随机数组");
    QuickSort(array, len);
    PrintArray(array, len, "快速排序");

    system("pause");
    return 0;
}

 

You may also like...