【数据结构】栈、队列和数组

栈

顺序栈

#define MaxSize 50
typedef struct
{
    int data[MaxSize];
    int top;
} SqStack;

// 1.(S.top == -1)
void InitStack(SqStack &S)
{
    S.top = -1;
}

// 2.(S.top == -1)
bool Push(SqStack &S, int x)
{
    if (S.top = MaxSize - 1)
        return false;
    S.data[++S.top] = x;
    return true;
}

// 3.(S.top == -1)
bool GetTop(SqStack &S, int &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top];
    return true;
}

// 4. (S.top == -1)
bool StackEmpty(SqStack &S)
{
    if (S.top == -1)
        return true;
    return false;
}

// 5.(S.top == -1)
bool Pop(SqStack *S, int &x)
{
    if (S->top == -1)
        return false;
    x = S->data[S->top--];
    return true;
}

// // 1.(S.top == 0)
// void InitStack(SqStack &S)
// {
//     S.top = 0;
// }

// // 2.(S.top == 0)
// bool Push(SqStack &S, int x)
// {
//     if (S.top = MaxSize)
//         return false;
//     S.data[S.top++] = x;
//     return true;
// }

// // 3.(S.top == 0)
// bool GetTop(SqStack &S, int &x)
// {
//     if (S.top == 0)
//         return false;
//     x = S.data[S.top];
//     return true;
// }

// // 4. (S.top == 0)
// bool StackEmpty(SqStack &S)
// {
//     if (S.top == 0)
//         return true;
//     return false;
// }

// // 5.(S.top == 0)
// bool Pop(SqStack *S, int &x)
// {
//     if (S->top == 0)
//         return false;
//     x = S->data[--S->top];
//     return true;
// }

链栈

typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
} LiStack;

共享栈

#define MaxSize 50
typedef struct
{
    int data[MaxSize];
    int top0;
    int top1;
} ShStack;

void InitStack(ShStack &S)
{
    S.top0 = -1;
    S.top1 = MaxSize;
}

队列

循环队列

#define MaxSize 50
typedef struct
{
    int data[MaxSize];
    int front, rear;
} SqQueue;

// 1.初始化
void InitQueue(SqQueue &Q)
{
    Q.rear = Q.front = 0;
}

// 2.循环队列入队
bool EnEmmpty(SqQueue &Q, int x)
{
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

// 3.判断队列为空
bool isEmpty(SqQueue &Q)
{
    if (Q.rear == Q.front)
        return true;
    return false;
}

// 4. 循环队列出队
bool DeEmpty(SqQueue &Q, int &x)
{
    if (Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

// 5. 获取队头元素值
bool Gethead(SqQueue Q, int &x)
{
    if (Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    return true;
}

带头结点的链式队列

typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct
{
    LinkNode *front, *rear;
} LinkNode;

// 带头结点的实现方式

// 1.初始化
void InitQueue(LinkNode &Q)
{
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{
    if (Q.front == Q.rear)
        return true;
    return false;
}

// 3.入队
bool EnEmpty(LinkNode &Q, int x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
    return true;
}

// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{
    if (Q.rear == Q.front)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = Q.front->next->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}

不带头结点的链式队列

typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct
{
    LinkNode *front, *rear;
} LinkNode;

//  不带头结点的实现方式

// 1.初始化
void InitQueue(LinkNode &Q)
{
    Q.front = Q.rear = NULL;
}

// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{
    if (Q.front == NULL)
        return true;
    return false;
}

// 3.入队
bool EnEmpty(LinkNode &Q, int x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if (Q.front == NULL)
    {
        Q.front = s;
        Q.rear = s;
    }
    else
    {
        Q.rear->next = s;
        Q.rear = s;
    }
    return true;
}

// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{
    if (Q.rear == NULL)
        return false;
    LinkNode *p = Q.front;
    x = p->data;
    Q.front = p->next;
    if (Q.rear == p)
    {
        Q.rear = NULL;
        Q.front = NULL;
    }
    free(p);
    return true;
}

串

顺序串

#define MAXSIZE 50
// 静态分配
typedef struct
{
    char str[MAXSIZE];
    int length;
} SeqString;

// 1.
void StrAssign(SeqString *S, char cstr[])
{
    int i = 0;
    for (i = 0; cstr[i] != '\0'; i++)
    {
        S->str[i] = cstr[i];
    }
    S->length = i;
}

// 2.
int StrEmpty(SeqString S)
{
    if (S.length == 0)
        return 1;
    return 0;
}

// 3.
int StrLength(SeqString S)
{
    return S.length;
}

// 4.
void StrCopy(SeqString *T, SeqString S)
{
    int i = 0;
    for (i = 0; i < S.length; i++)
    {
        T->str[i] = S.str[i];
    }
    T->length = S.length;
}

// 5. 比较两个串的大小
int StrCompare(SeqString S, SeqString T)
{
    int i;
    for (i = 0; i < S.length && i < T.length; i++)
    {
        if (S.str[i] == T.str[i])
            return (S.str[i] - T.str[i]);
    }
    return (S.length - T.length);
}

// 6. 在串S的第pos位置插入串T。若成功，返回1；失败，返回0
int StrInsert(SeqString *S, int pos, SeqString T)
{
    int i;
    if (pos < 0 || pos >= S->length)
    {
        printf("插入位置错误");
        return 0;
    }
    if (S->length + T.length <= MAXSIZE)
    {
        for (i = S->length + T.length - 1; i >= pos + T.length - 1; i--)
            S->str[i] = S->str[i - T.length];
        for (i = 0; i < T.length; i++)
            S->str[pos + i] = T.str[i];
        S->length += T.length;
        return 1;
    }
    else if (pos + T.length <= MAXSIZE) // 子串可以完整插入S中，但是S中的字符会被截掉
    {
        for (i = MAXSIZE - 1; i > T.length + pos - 1; i--)
            S->str[i] = S->str[i - T.length];
        for (i = 0; i < T.length; i++)
            S->str[i + pos - 1] = T.str[i];
        S->length = MAXSIZE;
        return 0;
    }
    else // 子串T不能被完全插入S中，T中会有字符被舍弃
    {
        for (i = 0; i < MAXSIZE - pos; i++)
            S->str[i + pos - 1] = T.str[i];
        S->length = MAXSIZE;
        return 0;
    }
}

// 7. 删除串S中pos开始的len个字符
int StrDelete(SeqString *S, int pos, int len)
{
    int i;
    if (pos < 0 || len < 0 || pos + len - 1 > S->length)
        return 0;
    else
    {
        for (i = pos + len - 1; i <= S->length - 1; i++)
            S->str[i - len] = S->str[i];
        S->length -= len;
        return 1;
    }
}

// 8.将串S连接到串T的末尾
int StrConcat(SeqString *T, SeqString S)
{
    int i, flag;
    if (T->length + S.length <= MAXSIZE)
    {
        for (i = T->length; i < T->length + S.length; i++)
            T->str[i] = S.str[i - S.length];
        T->length += S.length;
        flag = 1; // S完整连接到T后面
    }
    else if (T->length <= MAXSIZE)
    {
        for (i = T->length; i < MAXSIZE; i++)
            T->str[i] = S.str[i - T->length];
        T->length = MAXSIZE;
        flag = 0;
    }
    return flag;
}

// 9. 清空串
void StrClear(SeqString *S)
{
    S->length = 0;
}

模式匹配KMP

// 模式匹配KMP
void get_next(SeqString T, int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
    {
        if (j == 0 || T.str[i] == T.str[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int Index_KMP(SeqString S, SeqString T, int next[])
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.str[i] == T.str[j])
        {
            ++i;
            ++j;
        }
        else
            j = next[j];
    }
    if (j > T.length) // 匹配成功
        return i - T.length;
    return 0;
}