栈和队列代码实现

Nuyoah2021-06-252022-11-21

栈代码的实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 10

typedef struct
{
    int *base; // 栈底指针
    int *top; // 栈顶指针

    int stacksize;
}SqStack;

typedef struct StackNode
{
    char name[20];

    struct StackNode * next;
}SNode;

int InitStack(SqStack *S);

int StackEmpty(SqStack S);

int StackLength(SqStack S);

int PushDate(SqStack *S);

int PopDate(SqStack *S);
void print(SqStack S);

int ClearStack(SqStack *S);

int DestroyStack(SqStack *S);

int PushDate1(SqStack *S, int n);

void conversion(SqStack *S);
void InitSNode(SNode *S);
void partner(SNode *S1, SNode *S2);
void PushSNode(SNode *S, char *m);


int main()
{

    SNode S1, S2;

    InitStack(&S);

    PushDate(&S);

    printf("%d\n", StackLength(S));


    PopDate(&S);

    return 0;
}


int InitStack(SqStack *S)
{
    S->base = (int *)malloc(sizeof(int)*MAXSIZE);
    if(!S)
    {
        return 0;
    }

    S->top = S->base;
    S->stacksize = MAXSIZE;
    return 1;
}

int PushDate(SqStack *S)
{
    int n;

    do
    {
        if(S->top - S->base == S->stacksize)
        {
            return 0;
        }
        printf("请输入要压入数据");
        scanf("%d", &n);

        *S->top = n;
        S->top++;
        printf("是否要继续压入(1是 ，0否 )");
        scanf("%d", &n);

    }while(n == 1);



    return 1;

}


int PopDate(SqStack *S)
{
    int n;
    do
    {
        if(S->top == S->base)
        {
            return 0;
        }
        n = *--S->top;
        printf("出栈元素%d\n", n);
        print(*S);
        printf("是否要继续出栈(1 是 ， 0 否)：");
        scanf("%d",&n);
    }while(n == 1);

    return n;
}


int StackEmpty(SqStack S)
{
    if(S.base == S.top)
    {
        return 1;
    }
    return 0;
}


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

}


void print(SqStack S)
{
    int *p;
    p = S.top;

    while(p!=S.base)
    {
        printf("%d",*--p);
    }
}

int ClearStack(SqStack *S)
{
    if(S->base==S->top)
    {
        return 0;
    }
    S->top = S->base;
    return 1;
}


int DestroyStack(SqStack *S)
{
    if(S->base)
    {
        free(S->base);
        S->base = NULL;
        S->top = NULL;
        S->stacksize = 0;
        return 1;
    }

}



void conversion(SqStack *S)
{
    int n, m, p, q;
    printf("请输入要转换的数据和期望");
    scanf("%d %d", &n, &m);
    InitStack(S);

    do
    {
        p = n/m;
        q = n%m;
        PushDate1(S, q);
        n = p;
    }while(p);

}

int PushDate1(SqStack *S, int n)
{


    if(S->top - S->base == S->stacksize)
    {
        return 0;
    }
    *S->top = n;
    S->top++;


    return 1;

}

void InitSNode(SNode *S)
{
    S->next = NULL;
}

void PushSNode(SNode *S, char *m)
{
    SNode p;
    strcpy(p.name, m);
    p.next = S;
    S = &p;
}

队列代码的实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 10

// 顺序队列
typedef struct
{
    int *base;

    int sfront;
    int srear;
}SqQueue;

typedef struct Qnode
{
    char name[20];
    struct Qnode *next;

}QNode;

// 链式队列
typedef struct
{
    QNode *sfront;
    QNode *srear;
}LinkQueue;


// 链式队列
void partner(LinkQueue *Q1, LinkQueue *Q2);
int EnQueue(LinkQueue *S, char name[20]);
void InitQueue(LinkQueue *Q);
int DeQueue(LinkQueue *Q);


// 顺序队列
void InitSqQueue(SqQueue *Q);
int LengthSqQueue(SqQueue Q);
int EnSqQueue(SqQueue *Q);
int DeSqQueue(SqQueue *Q);
int GetHead(SqQueue *Q);


int main()
{
    /* 舞伴问题
    LinkQueue Q1, Q2;
    InitQueue(&Q1);
    InitQueue(&Q2);

    partner(&Q1, &Q2);
    */
    int n = 0, p;
    SqQueue Q;

    InitSqQueue(&Q);
    EnSqQueue(&Q);
    print(Q);

    DeSqQueue(&Q);

    return 0;
}

void InitQueue(LinkQueue *Q)
{

    Q->sfront = (QNode *)malloc(sizeof(QNode));
    Q->srear = Q->sfront;
    Q->sfront->next = NULL;
}

int EnQueue(LinkQueue *Q, char name[20])
{
    QNode *p;


    p = (QNode *)malloc(sizeof(QNode));
    if(!p)
    {
        return 0;
    }

    strcpy(p->name, name);
    p->next = NULL;



    Q->srear->next = p;
    Q->srear = p;
    return 1;
}

int DeQueue(LinkQueue *Q)
{
    QNode *p;
    if(Q->sfront == Q->srear)
    {
        return 0;
    }

    p = Q->sfront->next;
    Q->sfront->next = p->next;

    if(Q->srear == p)
    {
        Q->srear = Q->sfront;
    }

    free(p);
    return 1;
}



void partner(LinkQueue *Q1, LinkQueue *Q2)
{
    char sex;
    char name[20];
    int n, p = 0, q = 0;
    QNode *p1, *p2, *p3;

    while(1)
    {
        printf("请输入本轮跳舞的人数：");
        scanf("%d", &n);
        getchar();
        printf("请输入参赛人员的姓名和性别（f 女， m 男）\n");
        for(; n > 0; n--)
        {
            scanf("%s %c", name, &sex);
            if(sex == 'f')
            {
                EnQueue(Q1, name);
            }
            else
            {
                EnQueue(Q2, name);
            }
        }
        printf("配对结果：\n");
        printf("男\t女\n");
        p1 = Q1->sfront->next;
        p2 = Q2->sfront->next;
        while(p1 && p2)
        {
            printf("%s\t%s\n", p2->name, p1->name);
            DeQueue(Q1);
            DeQueue(Q2);
            p2 = p2->next;
            p1 = p1->next;
        }
        if(p1)
        {
            printf("女生有剩余，下一轮女生队伍第一个是%s \n", p1->name);
        }
        else if(p2)
        {
            printf("男生有剩余，下一轮男生队伍第一个是%s \n", p2->name);
        }
        else
        {
            printf("本轮无剩余\n");
        }

        printf("是否要继续进行（1是 0否）:");
        scanf("%d", &n);
        if( !n )
        {
            break;
        }
    }
    printf("跳舞结束");
}




void InitSqQueue(SqQueue *Q)
{
    Q->base = (int *)malloc(sizeof(int)*MAXSIZE);

    Q->sfront = Q->srear = 0;
}
int LengthSqQueue(SqQueue Q)
{
    return (Q.sfront + MAXSIZE - Q.srear)%MAXSIZE;
}
int EnSqQueue(SqQueue *Q)
{
    int n, p;

    while(1)
    {
        printf("请输入元素的数值：\n");

        scanf("%d", &p);
        if((Q->srear + 1 ) % MAXSIZE == Q->sfront)
        {
            return 0;
        }
        Q->base[Q->srear] = p;
        Q->srear = (Q->srear+1)%MAXSIZE;

        printf("是否要继续添加（0否， 1是）");
        scanf("%d", &n);
        if(!n)
        {
            break;
        }
    }

    return 1;
}
int DeSqQueue(SqQueue *Q)
{
    int n;
    while(1)
    {
        if(Q->sfront == Q->srear)
        {
            return 0;
        }

        Q->sfront = (Q->sfront + 1)%MAXSIZE;
        print(*Q);
        printf("是否继续删除（1是 0 否）");
        scanf("%d", &n);
        if(!n)
        {
            break;
        }
    }


}

void print(SqQueue Q)
{
    int p = Q.sfront;

    printf("\n");
    while( p % MAXSIZE != Q.srear)
    {
        printf("%d ", Q.base[p]);
        p++;
    }

}