数据结构之线性关系的C语言实现过程

2023-12-09 18:52:57

线性表

栈

顺序栈

声明过程

#include "constants.h"

#define STACK_INIT_SIZE 20 //顺序栈存储空间的初始分配量
#define STACKINCREMENT 5   //顺序栈存储空间的分配增量

typedef int SElemType;

typedef struct
{
    SElemType *base; //栈底指针，始终指向存储空间的基地址
    SElemType *top;  //栈顶指针，指向栈顶元素的下一个位置
    int stacksize;   //数组存储空间的长度
} SqStack;

Status InitStack(SqStack &S); //构造一个空的栈S

Status StackEmpty(SqStack S); //判断栈S是否是空表，若是，则返回TURE，不是，则返回FALSE

Status StackFull(SqStack S); //判断栈S是否是已满，若是则返回TRUE，否则返回FALSE

int StackLength(SqStack &S); //返回栈S的长度

Status GetTop(SqStack S, SElemType &e); //得到栈S的栈顶元素，并且用变量e带回

Status Push(SqStack &S, SElemType e); //把元素e的值进行入栈操作

Status Pop(SqStack &S, SElemType &e); //出栈操作，出栈的元素用变量e来带回

Status ClearStack(SqStack &S); //重置栈S为空栈

Status StackTraverse(SqStack S, Status (*visit)(SElemType)); //依次对栈S中的每个元素调用visit进行访问

Status DestroyStack(SqStack &S); //销毁栈S，可能的话释放其空间

Status visit_read(SElemType e); //访问函数

Status Adjust(SqStack &S); //扩大栈S的最大存储空间

实现过程

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

Status InitStack(SqStack &S)
{
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    //栈的连续空间分配
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base; //空栈，初始化栈顶指针
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status StackEmpty(SqStack S)
{
    /* return S.top == S.base ? TRUE : FALSE; */
    return S.top == S.base;
}

Status StackFull(SqStack S)
{
    return S.top - S.base == S.stacksize;
}

int StackLength(SqStack &S)
{
    return S.top - S.base;
}

//Attention!!   top指针指向的是栈顶元素的下一个位置
Status GetTop(SqStack S, SElemType &e)
{
    /* if (!StackEmpty(S))
    {
        e = *(S.top - 1);
        return OK;
    }
    else
        return ERROR; */
    if (S.top == S.base)
        return ERROR;
    else
    {
        e = *(S.top - 1);
        return OK;
    }
}

//*和++运算符都是同级的，自右向左。
Status Push(SqStack &S, SElemType e)
{
    if (StackFull(S))
        Adjust(S);
    *S.top++ = e;
    return OK;
}

//不能用*S.top--,而应该用*--S.top。因为top指向栈顶元素的下一个元素
Status Pop(SqStack &S, SElemType &e)
{
    if (StackEmpty(S))
        return ERROR;
    else
    {
        e = *--S.top;
        return OK;
    }
}

Status ClearStack(SqStack &S)
{
    S.top = S.base;
    return OK;
}

Status StackTraverse(SqStack S, Status (*visit)(SElemType))
{
    /* if (StackEmpty(S))
        return ERROR;
    else
    {
        SElemType *p = S.base;
        while (p != S.top)
        {
            if (!visit(*p))
                return ERROR;
            p++;
        }
        return OK;
    } */
    SElemType *p;
    for (p = S.base; p < S.top; p++)
        if (!visit(*p))
            return ERROR;
    return OK;
}

Status DestroyStack(SqStack &S)
{
    if (S.base)
        free(S.base);
    S.base = NULL;
    return OK;
}

Status visit_read(SElemType e)
{
    printf("%d ", e);
    return OK;
}

Status Adjust(SqStack &S)
{
    S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
    return OK;
}

链栈

声明过程

#include "constants.h"

typedef int SElemType;

typedef struct Snode
{
    SElemType data;
    struct Snode *next;
} SNode, *LinkStack;

Status InitStack(LinkStack &S); //构造一个空的栈S

Status StackEmpty(LinkStack S); //判断栈S是否是空表，若是，则返回TURE，不是，则返回FALSE

int StackLength(LinkStack &S); //返回栈S的长度

Status GetTop(LinkStack S, SElemType &e); //得到栈S的栈顶元素，并且用变量e带回

Status Push(LinkStack &S, SElemType e); //把元素e的值进行入栈操作

Status Pop(LinkStack &S, SElemType &e); //出栈操作，出栈的元素用变量e来带回

Status ClearStack(LinkStack &S); //重置栈S为空栈

Status StackTraverse(LinkStack S, Status (*visit)(SElemType)); //依次对栈S中的每个元素调用visit进行访问

Status DestroyStack(LinkStack &S); //销毁栈S，可能的话释放其空间

Status visit_read(SElemType e); //访问函数

实现过程

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

//S（linkstack）是头指针（一个S代表一个链栈），它指向栈顶元素所在节点
Status InitStack(LinkStack &S)
{
    S = (LinkStack)malloc(sizeof(SNode *));
    if (!S)
        exit(OVERFLOW);
    S = NULL;
    return OK;
}

Status StackEmpty(LinkStack S)
{
    return S == NULL ? TRUE : FALSE;
}

int StackLength(LinkStack &S)
{
    int len = 0;
    SNode *p = S;
    while (p)
    {
        p = p->next;
        len++;
    }
    return len;
}

Status GetTop(LinkStack S, SElemType &e)
{
    if (!S)
        return ERROR;
    else
    {
        e = S->data;
        return OK;
    }
}

Status Push(LinkStack &S, SElemType e)
{
    SNode *p = (SNode *)malloc(sizeof(SNode));
    if (!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

Status Pop(LinkStack &S, SElemType &e)
{
    if (!S)
        return ERROR;
    else
    {
        SNode *p = S;
        e = p->data;
        S = p->next;
        free(p);
        return OK;
    }
}

Status ClearStack(LinkStack &S)
{
    while (S)
    {
        SNode *p = S;
        S = p->next;
        free(p);
    }
    return OK;
}

Status StackTraverse(LinkStack S, Status (*visit)(SElemType))
{
    SNode *p = S;
    while (p)
    {
        if (!visit(p->data))
            return ERROR;
        p = p->next;
    }
    return OK;
}

Status DestroyStack(LinkStack &S)
{
    ClearStack(S);
    free(S);
    return OK;
}

Status visit_read(SElemType e)
{
    printf("%d ", e);
    return OK;
}

顺序队列

声明过程

#include "constants.h"

#define MAXQSIZE 100

typedef int QElemType;

typedef struct
{
    QElemType *base; //存储空间基地址
    int front;       //队头指针，指向队头元素
    int rear;        //队尾指针，指向队尾元素的下一个位置
} SqQueue;

Status InitQueue(SqQueue &Q);//初始化一个顺序空队列

Status QueueEmpty(SqQueue Q);//判断该顺序队列是否为空

int QueueLength(SqQueue Q);//返回顺序队列的长度

Status GetHead(SqQueue Q, QElemType &e);//得到队头元素，并用e带回

Status EnQueue(SqQueue &Q, QElemType e);//入队

Status DeQueue(SqQueue &Q, QElemType &e);//出队

Status ClearQueue(SqQueue &Q);//清空队列

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType));//遍历队列

Status DestroyQueue(SqQueue &Q);//销毁队列

Status Visit(QElemType e);

实现过程

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

Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

Status QueueEmpty(SqQueue Q)
{
    return Q.rear == Q.front;
}

int QueueLength(SqQueue Q)
{
    return Q.rear - Q.front;
}

Status GetHead(SqQueue Q, QElemType &e)
{
    e = Q.base[Q.front];
    return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
    Q.base[Q.rear++] = e;
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    e = Q.base[Q.front++];
    return OK;
}

Status ClearQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;
    return OK;
}

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType))
{
    int i;
    for (i = Q.front; i < Q.rear; i++)
        if (!Visit(Q.base[i]))
            return ERROR;
    return OK;
}

Status DestroyQueue(SqQueue &Q)
{
    free(Q.base);
    return OK;
}

Status Visit(QElemType e)
{
    printf("%d ", e);
    return OK;
}

循环队列

假若循环队列的实现与顺序队列相同的话，那么在队列判空和判满时，条件相同，出现矛盾。为了解决这个问题，共有三种方案。

声明过程

#include "constants.h"

#define MAXQSIZE 100

typedef int QElemType;

typedef struct
{
    QElemType *base; //存储空间基地址
    int front;       //队头指针，指向队头元素
    int rear;        //队尾指针，指向队尾元素的下一个位置
} SqQueue;

Status InitQueue(SqQueue &Q);//初始化一个顺序空队列

Status QueueEmpty1(SqQueue Q);//判断该顺序队列是否为空

int QueueLength(SqQueue Q);//返回顺序队列的长度

Status GetHead(SqQueue Q, QElemType &e);//得到队头元素，并用e带回

Status EnQueue(SqQueue &Q, QElemType e);//入队

Status DeQueue(SqQueue &Q, QElemType &e);//出队

Status ClearQueue(SqQueue &Q);//清空队列

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType));//遍历队列

Status DestroyQueue(SqQueue &Q);//销毁队列

Status Visit(QElemType e);

Status QueueFull(SqQueue Q);//判断队列是否已满

实现过程

//方案一
#include "CSqQueue.h"
#include <stdio.h>
#include <stdlib.h>

Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

int QueueLength(SqQueue Q)
{
    return (Q.rear + MAXQSIZE - Q.front) % MAXQSIZE;
}

//基地址所指向的空间不存储数据
Status QueueEmpty1(SqQueue Q)
{
    return Q.front == Q.rear;
}

Status GetHead(SqQueue Q, QElemType &e)
{
    if (QueueEmpty1(Q))
        return ERROR;
    else
    {
        e = Q.base[Q.front];
        return OK;
    }
}

Status EnQueue(SqQueue &Q, QElemType e)
{
    if (QueueFull(Q))
        return ERROR;
    else
    {
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if (QueueEmpty1(Q))
        return ERROR;
    else
    {
        e = Q.base[Q.front];
        Q.front = (Q.front + 1) % MAXQSIZE;
        return OK;
    }
}

Status ClearQueue(SqQueue &Q)
{
    Q.front = Q.rear;
    return OK;
}

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType))
{
    int i = Q.front;
    while (i != Q.rear)
    {
        if (Visit(Q.base[i]))
            i = (i + 1) % MAXQSIZE;
        else
            return ERROR;
    }
    return OK;
}

/* free函数与malloc函数配对使用，释放malloc函数申请的动态内存。
对于free(p)这句语句，如果p时空指针，那么free对p无论操作多少次都不会出问题；
如果p不是NULL指针，那么free对p连续操作两次就会导致程序运行错误。 */
Status DestroyQueue(SqQueue &Q)
{
    if (Q.base)
        free(Q.base);
    Q.base = NULL;
    return OK;
}

Status Visit(QElemType e)
{
    printf("%d ", e);
    return OK;
}

Status QueueFull(SqQueue Q)
{
    return Q.front == (Q.rear + 1) % MAXQSIZE;
}

//方案二
#include "CSqQueue.h"
#include <stdlib.h>
#include <stdio.h>

Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    Q.tag = 0;
    return OK;
}

Status QueueEmpty2(SqQueue Q)
{
    return Q.front == Q.rear && Q.tag == 0;
}

int QueueLength(SqQueue Q)
{
    return (Q.rear + MAXQSIZE - Q.front) % MAXQSIZE;
}

Status GetHead(SqQueue Q, QElemType &e)
{
    if (QueueEmpty2(Q))
        return ERROR;
    e = Q.base[Q.front];
    return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
    if (QueueFull(Q))
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    Q.tag = 1;
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if (QueueEmpty2(Q))
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    Q.tag = 0;
    return OK;
}

Status ClearQueue(SqQueue &Q)
{
    Q.rear = Q.front;
    return OK;
}

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType))
{
    int i = Q.front;
    while (i != Q.rear)
    {
        if (Visit(Q.base[i]))
            i = (i + 1) % MAXQSIZE;
        else
            return ERROR;
    }
    return OK;
}

Status DestroyQueue(SqQueue &Q)
{
    if (!Q.base)
        free(Q.base);
    Q.base = NULL;
    return OK;
}

Status Visit(QElemType e)
{
    printf("%d ", e);
    return OK;
}

Status QueueFull(SqQueue Q)
{
    return Q.front == Q.rear && Q.tag == 1;
}

//方案三
#include "CSqQueue.h"
#include <stdio.h>
#include <stdlib.h>

Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = 0;
    Q.length = 0;
    return OK;
}

Status QueueEmpty3(SqQueue Q)
{
    return Q.length == 0;
}

int QueueLength(SqQueue Q)
{
    return Q.length;
}

Status GetHead(SqQueue Q, QElemType &e)
{
    if (QueueEmpty3(Q))
        return ERROR;
    e = Q.base[Q.front];
    return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
    if (QueueFull(Q))
        return ERROR;
    Q.base[Q.front] = e;
    Q.front = (Q.front + 1) % MAXQSIZE;
    Q.length++;
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if (QueueEmpty3(Q))
        return ERROR;
    e = Q.base[Q.front + Q.length - 1];
    Q.length--;
    return OK;
}

Status ClearQueue(SqQueue &Q)
{
    Q.length = 0;
    return OK;
}

Status QueueTraverse(SqQueue Q, Status (*Visit)(QElemType))
{
    int sign = Q.front;
    for (int i = 0; i < Q.length; i++)
    {
        if (Visit(Q.base[sign]))
            sign = (sign + 1) % MAXQSIZE;
        else
            return ERROR;
    }
    return OK;
}

Status DestroyQueue(SqQueue &Q)
{
    if (!Q.base)
        free(Q.base);
    Q.base = NULL;
    return OK;
}

Status Visit(QElemType e)
{
    printf("%d ", e);
    return OK;
}

Status QueueFull(SqQueue Q)
{
    return Q.length == MAXQSIZE;
}

链式队列

声明过程

//若无法估计所使用队列的长度，则使用链队列
#include "constants.h"

typedef int QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;//指向链式队列的头结点（链式队列的头结点的指针域指向队头结点）
    QueuePtr rear;//指向链式队列的尾结点
} LinkQueue;

Status InitQueue(LinkQueue &Q);//初始化一个空链队列

Status QueueEmpty(LinkQueue Q);//判断链队列是否为空

int QueueLength(LinkQueue Q);//返回链队列的长度

Status GetHead(LinkQueue Q, QElemType &e);//得到链队列的队头元素，并且用e来返回

Status EnQueue(LinkQueue &Q, QElemType e);//入队

Status DeQueue(LinkQueue &Q, QElemType &e);//出队

Status ClearQueue(LinkQueue &Q);//清空链队列

Status QueueTraverse(LinkQueue Q, Status (*Visit)(QElemType));//遍历链队列

Status DestroyQueue(LinkQueue &Q);//销毁链队列

Status visit(QElemType e);//读取函数

实现过程

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

Status InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

Status QueueEmpty(LinkQueue Q)
{
    return Q.front == Q.rear;
}

int QueueLength(LinkQueue Q)
{
    int len = 0;
    QueuePtr p = Q.front->next;
    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}

Status GetHead(LinkQueue Q, QElemType &e)
{
    if (QueueEmpty(Q))
        return ERROR;
    e = Q.front->next->data;
    return OK;
}

//当链式队列中有新结点加入时，我们要记得更新队列尾结点指针
Status EnQueue(LinkQueue &Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

//如果出队的结点是队尾结点，那么在出队操作前，需要更新队尾指针，让其等于队头指针，即均指向头结点
Status DeQueue(LinkQueue &Q, QElemType &e)
{
    if (QueueEmpty(Q))
        return ERROR;
    QueuePtr p = Q.front->next->next;
    e = Q.front->next->data;
    if (Q.front->next == Q.rear)
        Q.rear = Q.front;
    free(Q.front->next);
    Q.front->next = p;
    return OK;
}

Status ClearQueue(LinkQueue &Q)
{
    Q.front = Q.rear;
    return OK;
}

Status QueueTraverse(LinkQueue Q, Status (*Visit)(QElemType))
{
    QueuePtr p = Q.front->next;
    while (p)
    {
        Visit(p->data);
        p = p->next;
    }
    return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
    if (Q.front)
        free(Q.front);
    Q.front = NULL;
    return OK;
}

Status visit(QElemType e)
{
    printf("%d ", e);
    return OK;
}

码农公寓

相关文章