数据结构实现

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

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

栈

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

C++实现

先用结构体定义一个栈

1
2
3
4
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;
}

这个函数判断栈是否为空

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
typedef struct Stack {
    ElemType data[maxStack];//栈空间大小为50
    int top;//栈顶位置
}crestack;

初始化栈

1
2
3
4
5
6
7
crestack* inStack(void) {
    crestack* st;
    st = (crestack*)malloc(sizeof(crestack));
    st->top = -1;

    return st;
}

判断栈是否为空

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;//出栈成功
}

队列

队列的特点是先进先出。

数组实现队列

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

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

数组结构体

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, 4 * maxquere);
    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->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->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
int main(void) {
    //数组实现队列
    Quere_s* quere;
    int i;
    quere = (Quere_s*)malloc(sizeof(Quere_s));
    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
void enquere_l(Quere_l* quere) {
    LQuEre* current;
    int i;
    quere->front = quere->end = (LQuEre*)malloc(sizeof(LQuEre));
    quere->front->a = 0;
    quere->front->next = NULL;
    current = quere->front;
    for (i = 0; i < maxquere - 1; i++) {
        current->next = (LQuEre*)malloc(sizeof(LQuEre));
        current = current->next;
        current->a = 0;
        current->next = NULL;
    }
    current->next = quere->front;
}

入队

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
}

对列清空

这里要注意free掉所有的指针

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
LQUere* quere;
    int i;
    quere = (LQUere*)malloc(sizeof(LQUere));
    lenquere(quere);
    for (i = 1; i <= 100; i++) {
        if (linquere(quere, i)) {
            printf("队列已满\n");
            break;
        }
    }
    while (!loutquere(quere)) {
        printf("%d\n", quere->output);
    }
    lfree(quere);

    return 0;