[数据结构与算法]算法基础——数据结构队列/链表/图的实现

算法基础——数据结构队列/链表/图的实现

本文中的数据结构非常简单，且具有非常实用的特点，利于初学者快速实现以上结构。实际项目中，在以上数据结构的上增加对数据信息描述就是工程中使用的数据结构了。

1.队列

queue.h

    //ADT: Queue
    typedef struct _stQueue stQueue;
    struct _stQueue
    {
        int data;
        stQueue* next;
    };

    stQueue* initQueue();
    void destroyQueue(stQueue* queue);
    int pop(stQueue* queue);
    void enter(stQueue* one, int data);

queue.c

stQueue * initQueue()
{
    stQueue* q = (stQueue*)malloc(sizeof(stQueue));
    memset(q, 0, sizeof(stQueue));
    return q;
}

void destroyQueue(stQueue* queue)
{
    if (queue == NULL)
        return;
    stQueue* del;
    while (queue->next != NULL)
    {
        del = queue->next;
        queue->next = queue->next->next;
        free(del);
    }
    free(queue);
}

int pop(stQueue * queue)
{
    int data = -1;
    stQueue* del;
    if (queue != NULL && queue->next != NULL) {
        data = queue->next->data;
        del = queue->next;
        queue->next = queue->next->next;
        free(del);
    }
    return data;
}

void enter(stQueue * queue, int data)
{
    stQueue* one;
    if (queue != NULL) {
        one = (stQueue*)malloc(sizeof(stQueue));
        one->data = data;
        one->next = queue->next;
        queue->next = one;
    }
}

2.链表

link.h

// ADT: Link
    typedef struct _stNode stNode;
    struct _stNode {
        int data;
        stNode* next;
    };
    typedef struct _stLink
    {
        stNode* header;
        stNode* tail;
    }stLink;

    stLink* initLink();
    void destroyLink(stLink* link);
    void addNode(stLink* link, int data);
    stNode delNode(stLink* link, int data);

link.c

stLink * initLink()
{
    stLink* link = (stLink*)malloc(sizeof(stLink));
    if (NULL != link) {
        memset(link, 0, sizeof(stLink));
        link->header = (stNode*)malloc(sizeof(stNode));
        memset(link->header, 0, sizeof(stNode));
    }
    return link;
}

void destroyLink(stLink * link)
{
    stNode *cur = NULL;
    stNode *del = NULL;

    if (NULL == link) {
        return;
    }
    cur = link->header;
    while (cur != NULL)
    {
        del = cur;
        cur = del->next;
        free(del);
    }
    free(link);
}

void addNode(stLink * link, int data)
{
    stNode* node;
    if (link == NULL)
        return;
    node = (stNode*)malloc(sizeof(stNode));
    memset(node, 0, sizeof(stNode));
    node->data = data;
    if (link->tail == NULL && link->header->next == NULL) {
        link->header->next = node;
        link->tail = node;
    }
    else
    {
        link->tail->next = node;
        link->tail = node;
    }
}

stNode delNode(stLink * link, int data)
{
    stNode node = {0};
    if (link == NULL) {
        return node;
    }
    stNode* cur = link->header;
    while (cur->next) {
        if (cur->next->data == data) {
            node.data = cur->next->data;
            node.next = cur->next->next;
            if (link->tail == cur->next) {
                link->tail = cur;
                if (link->tail == link->header) {
                    link->tail = NULL;
                }
            }
            free(cur->next);
            cur->next = node.next;
            break;
        }
        cur = cur->next;
    }

    return node;
}

3.图

graph.h

//ADT: Graph
#define MAX_VERTEX_NUM 20
    int visited[MAX_VERTEX_NUM];
    typedef struct _stArcNode stArcNode;
    struct _stArcNode
    {
        int index;        //this vertex's index in graph
        int data;         //the relationship about last vertex and this vertex
        stArcNode* next;  // next vertex
    };
    typedef struct _stVertex {
        int data;         // the data in first vertex
        stArcNode* first;  // the first vertex in ver[MAX_VERTEX_NUM]
    }stVertex;
    typedef struct _stGraph{
        int num;          // the number of vertexes
        stVertex vex[MAX_VERTEX_NUM];
    }stGraph;

    stGraph* creatGraph();
    void destroyGraph(stGraph* G);
    void dfs(stGraph * G, int index);
    void searchGraph(stGraph* G);

graph.c

stGraph * creatGraph()
{
    stGraph* graph = (stGraph*)malloc(sizeof(stGraph));
    memset(graph, 0, sizeof(stGraph));

    //for example
    /* 
    vertex[0] : 0->3(arc=13)
    vertex[1] : 1->0(arc=10), 1->2(arc=12)
    vertex[2] : 2->0(arc=20), 2->1(arc=21)
    vertex[3] : null 
    */
    graph->num = 4;
    for (int i = 0; i < graph->num; i++) {
        stVertex* vertex = graph->vex + i;
        vertex->data = i;
        vertex->first = (stArcNode*)malloc(sizeof(stArcNode));
        switch (i)
        {
        case 0:
            vertex->first->data = 13;
            vertex->first->index = 3;
            vertex->first->next = NULL;
            break;
        case 1:
            vertex->first->data = 10;
            vertex->first->index = 0;
            vertex->first->next = (stArcNode*)malloc(sizeof(stArcNode));
            vertex->first->next->data = 12;
            vertex->first->next->index = 2;
            vertex->first->next->next = NULL;
            break;
        case 2:
            vertex->first->data = 20;
            vertex->first->index = 0;
            vertex->first->next = (stArcNode*)malloc(sizeof(stArcNode));
            vertex->first->next->data = 21;
            vertex->first->next->index = 1;
            vertex->first->next->next = NULL;
            break;
        case 3:
            free(vertex->first);
            vertex->first = NULL;
        default:
            break;
        }
    }

    return graph;
}

void destroyGraph(stGraph* graph)
{
    if (graph == NULL) {
        return;
    }
    for (int i = 0; i < graph->num; i++) {
        stVertex* vertex =  graph->vex + i;
        stArcNode* del;
        stArcNode* cur = vertex->first;
        while (cur) {
            del = cur;
            cur = del->next;
            free(del);
        }
    }
    free(graph);
}

void dfs(stGraph * G, int index)
{
    stVertex vertex= G->vex[index];
    // node
    printf("%d ", vertex.data);
    visited[index] = 1;
    stArcNode* arcNode = vertex.first;
    while (arcNode) {
        // pointed node
        if (visited[arcNode->index] == 0) {
            dfs(G, arcNode->index);
        }
        arcNode = arcNode->next;
    }
}

void searchGraph(stGraph * G)
{
    if (G == NULL)
        return;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < G->num; i++) {
        if (visited[i] == 0) {
            dfs(G, i);
        }
    }
}

4.24点经典算法

采用递归求解24点，非常暴力，但是容易理解。

twenty_four.h

#ifndef _TWENTY_FOUR_H_
#define _TWENTY_FOUR_H_

#define COUNT_OF_NUMBER  (4)
#define NUMBER_TO_BE_CAL (24)
#define PRECISION (1e-6)

extern double number[COUNT_OF_NUMBER];

int search(int n);


#endif // !_TWENTY_FOUR_H_

twenty_four.c

#include "twenty_four.h"
#include <math.h>

double number[COUNT_OF_NUMBER] = {0};

int search(int n)
{
    if (n == 1) {
        if (fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION) {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double a, b;
            a = number[i];
            b = number[j];
            number[j] = number[n - 1];//change recursive scene
            number[i] = a + b;        //change recursive scene
            if (search(n - 1)) return 1;
            number[i] = a - b;        //change recursive scene
            if (search(n - 1)) return 1;
            number[i] = b - a;        //change recursive scene
            if (search(n - 1)) return 1;
            number[i] = a * b;        //change recursive scene
            if (search(n - 1)) return 1;
            if (b != 0) {
                number[i] = a / b;    //change recursive scene
                if (search(n - 1)) return 1;
            }
            if (a != 0) {
                number[i] = b / a;    //change recursive scene
                if (search(n - 1)) return 1;
            }
            number[i] = a;//reserve recursive scene
            number[j] = b;//reserve recursive scene
        }
    }

    return 0;
}

5. 四则运算的后缀表达式计算

arithmatic.h

#include "queue.h"
    // arithmatic, for example: 1+3*(2+5)
    int calculate(char expression[]);

arithmatic.c

static int isoperate(char ch) {
    if (ch == '+')
        return 1;
    else if (ch == '-')
        return 1;
    else if (ch == '/')
        return 1;
    else if (ch == '*')
        return 1;
    else
    {
        return 0;
    }
}

static int operate(char ch, int right, int left) {
    if (ch == '+')
        return (right + left);
    else if (ch == '-')
        return (right - left);
    else if (ch == '/')
        return (left / right);
    else if (ch == '*')
        return (left * right);
    else
    {
        return 0;
    }
}

int calculate(char exp[])
{
    stQueue* queue =  initQueue();
    int i = 0;
    int j, num;
    char a[32] = { 0 };
    int right, left, res;

    while (exp[i] !='\0') {
        if (isdigit(exp[i])) {
            j = 0;
            while (isdigit(exp[i]))
            {
                a[j] = exp[i];
                i++; j++;
            }
            num = atoi(a);
            memset(a, 0, sizeof(a));
            enter(queue, num);
        }
        else if(exp[i] == ' ')
        {
            continue;
        }
        else if(isoperate(exp[i]))
        {
            right = pop(queue);
            left = pop(queue);
            res = operate(exp[i], right, left);
            enter(queue, res);
        }
        i++;
    }
    res = pop(queue);
    destroyQueue(queue);
    return res;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖