数据结构实现

发表于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

导航
返回数据结构与算法分类

本篇记录了一些数据结构的实现。

章节目录

  1. 栈的实现
  2. 队列的实现

栈

栈的特点是后进先出，这里我们就用数组实现栈。

C++实现

下面以字符为栈元素，先定义类型和容量，再用结构体定义一个栈。各实现分别编译，不能把重名的push、pop直接拼在同一文件中。

1
2
3
4
5
6
7
using ElemType = char;
const int maxSize = 50;

typedef struct {
    ElemType data[maxSize];        //连续内存空间存放栈中元素
    int top;            //存放栈顶元素在data数组中的下标    
}SqStack;

然后初始化栈

1
2
3
void initStack(SqStack& st) {
    st.top = -1;
}

这是进栈函数

1
2
3
4
5
6
7
8
int push(SqStack& st, char x) {
    if (st.top == maxSize - 1) {//栈满
        return 0;
    }
    ++(st.top);
    st.data[st.top] = x;//先移动指针再进栈
    return 1;
}

这是出栈函数

1
2
3
4
5
6
7
8
int pop(SqStack& st, char& x) {
    if (st.top == -1) {
        return 0;
    }
    x = st.data[st.top];
    --(st.top);
    return 1;
}

这个函数调用inStack后要检查是否为NULL，使用结束后用free释放栈。

判断栈是否为空

1
2
3
4
5
6
7
8
int isEmpty(SqStack st) {
    if (st.top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}

C语言实现

因为要采用函数封装，结构体能在函数中传递更多参数，所以要定义一个结构体作为主函数与其他函数的桥梁。

栈的结构体

1
2
3
4
5
6
7
8
#include<stdlib.h>
typedef char ElemType;
#define maxStack 50

typedef struct Stack {
    ElemType data[maxStack];//栈空间大小为50
    int top;//栈顶位置
}crestack;

初始化栈

1
2
3
4
5
6
7
8
9
crestack* inStack(void) {
    crestack* st;
    st = (crestack*)malloc(sizeof(crestack));
    if (!st)
        return NULL;
    st->top = -1;

    return st;
}

调用inStack后要检查是否为NULL，使用结束后用free释放栈。

判断栈是否为空

1
2
3
4
5
6
7
int isStack(crestack* st) {
    if (st->top == -1) {
        return 1;//1为空
    }
    else
        return 0;//0为不空
}

入栈

1
2
3
4
5
6
7
8
9
10
int push(crestack* st, char *x) {
    if (st->top == maxStack - 1) {
        return 0;//栈满，入栈失败
    }
    else {
        st->top++;
        st->data[st->top] = *x;
    }
    return 1;
}

出栈

1
2
3
4
5
6
7
8
9
10
int pop(crestack* st, char *x) {
    if (st->top == -1) {
        return 0;//栈空，出栈失败
    }
    else {
        *x=st->data[st->top];
        st->top--;
    }
    return 1;//出栈成功
}

队列

队列的特点是先进先出。下面两个C示例都需要以下头文件和容量定义：

1
2
3
4
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxquere 50

数组实现队列

因为要采用函数封装，结构体能在函数中传递更多参数，所以要定义一个结构体作为主函数与其他函数的桥梁。

定义一个数组的结构体，用数组做队列，牺牲一个内存空间判断队满，形成环形逻辑。

数组结构体

1
2
3
4
typedef struct Quere {//数组结构体
    int a[maxquere];
    int end, front,input,output;
}Quere_s;

队列初始化

1
2
3
4
5
void enquere(Quere_s* quere) {
    memset(quere->a, 0, sizeof quere->a);
    quere->end = 0;
    quere->front = 0;
}

入队

1
2
3
4
5
6
7
8
9
10
int inquere(Quere_s* quere, int x) {
    quere->input = x;
    if ((quere->end + 1) % maxquere == quere->front % maxquere && quere->a[quere->front] == 1)
        return 1;//队列已满返回1
    quere->end = (quere->end + 1) % maxquere;
    quere->a[quere->front % maxquere] = 1;
    quere->a[quere->end % maxquere] = quere->input;

    return 0;//入队成功返回0
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
int outquere(Quere_s* quere) {
    if (quere->end % maxquere == quere->front % maxquere && quere->a[quere->front] == 0)
        return 1;//队列已空返回1
    quere->front = (quere->front + 1) % maxquere;
    quere->output = quere->a[quere->front % maxquere];
    if (quere->end % maxquere == quere->front % maxquere)
        quere->a[quere->front % maxquere] = 0;
    else
        quere->a[quere->front % maxquere] = 1;

    return 0;//出队成功返回0
}

队列的简单展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(void) {
    //数组实现队列
    Quere_s* quere;
    int i;
    quere = (Quere_s*)malloc(sizeof(Quere_s));
    if (!quere)
        return 1;
    enquere(quere);
    for (i = 1; i <= 100; i++) {
        if (inquere(quere,i)) {
            printf("队列已满\n");
            break;
        }
    }
    while (!outquere(quere)) {
        printf("%d\n", quere->output);
    }
    free(quere);
    
    return 0;
}

链表实现队列

因为要采用函数封装，结构体能在函数中传递更多参数，所以要定义一个结构体作为主函数与其他函数的桥梁。

两个结构体，第二个结构体是链表的结构体。

牺牲一个节点用来判断是否队满。

结构体

1
2
3
4
5
6
7
8
typedef struct lQuere {//链表结构体，功能
    struct LQuere* front, * end;
    int input, output;
}Quere_l;
typedef struct LQuere {//链表结构体,内容
    int a;
    struct LQuere* next;
}LQuEre;

队列初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int enquere_l(Quere_l* quere) {
    LQuEre* current;
    int i;
    quere->front = quere->end = (LQuEre*)malloc(sizeof(LQuEre));
    if (!quere->front)
        return 1;
    quere->front->a = 0;
    quere->front->next = NULL;
    current = quere->front;
    for (i = 0; i < maxquere - 1; i++) {
        current->next = (LQuEre*)malloc(sizeof(LQuEre));
        if (!current->next) {
            current = quere->front;
            while (current) {
                LQuEre* next = current->next;
                free(current);
                current = next;
            }
            quere->front = quere->end = NULL;
            return 1;
        }
        current = current->next;
        current->a = 0;
        current->next = NULL;
    }
    current->next = quere->front;
    return 0;
}

入队

1
2
3
4
5
6
7
8
9
10
int inquere_l(Quere_l* quere, int x) {
    quere->input = x;
    if (quere->end->next == quere->front && quere->front->a == 1)
        return 1;//队列已满返回1
    quere->end = quere->end->next;
    quere->front->a = 1;
    quere->end->a = quere->input;

    return 0;//入队成功返回0
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
int outquere_l(Quere_l* quere) {
    if (quere->end == quere->front && quere->front->a == 0)
        return 1;//队列已空返回1
    quere->front = quere->front->next;
    quere->output = quere->front->a;
    if (quere->end == quere->front)
        quere->front->a = 0;
    else
        quere->front->a = 1;

    return 0;//出队成功返回0
}

队列清空

这里要释放所有分配的节点和队列结构体。

1
2
3
4
5
6
7
8
9
10
11
12
void free_l(Quere_l* quere) {
    LQuEre* current, * prev;
    int i;
    current = quere->front;
    for (i = 0; i < maxquere - 1; i++) {
        prev = current->next;
        free(current);
        current = prev;
    }
    free(current);
    free(quere);
}

队列的简单展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(void) {
    Quere_l* quere;
    int i;
    quere = (Quere_l*)malloc(sizeof(Quere_l));
    if (!quere)
        return 1;
    if (enquere_l(quere)) {
        free(quere);
        return 1;
    }
    for (i = 1; i <= 100; i++) {
        if (inquere_l(quere, i)) {
            printf("队列已满\n");
            break;
        }
    }
    while (!outquere_l(quere)) {
        printf("%d\n", quere->output);
    }
    free_l(quere);

    return 0;
}