基础数据结构_栈

顺序栈

头文件

#ifndef MY_SEQSTACK_H
#define MY_SEQSTACK_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

#define STACK_INIT_SIZE 100
#define STACKINC 1.5
typedef int SElemType;
typedef struct
{
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈的容量
}SeqStack;

Status InitStack(SeqStack *ps);
void DestroyStack(SeqStack *ps);
void ClearStack(SeqStack *ps);
int StackLength(const SeqStack *ps);
bool StackEmpty(const SeqStack *ps);
bool StackFull(const SeqStack *ps);
Status Push(SeqStack *ps, SElemType val);
Status GetTop(SeqStack *ps, SElemType *pval);
Status Pop(SeqStack *ps, SElemType *pval);


#endif

实现

//My_SeqStack.cpp
#include<stdlib.h>//malloc free
#include<assert.h>

#include"My_SeqStack.h"
Status InitStack(SeqStack *ps)
{
    assert(ps!=NULL);
    ps->base = (SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if(NULL==ps->base)
    {
        return OVERFLOW;
    }
    ps->top = ps->base;
    ps->stacksize = STACK_INIT_SIZE;
    return OK;
}
void DestroyStack(SeqStack *ps)
{
	assert(ps!=NULL);
    free(ps->base);
    ps->base = NULL;
    ps->top = NULL;
    ps->stacksize = 0;
}
void ClearStack(SeqStack *ps)
{
    assert(ps!=NULL);
    ps->top = ps->base;
}
int StackLength(const SeqStack *ps)
{
    assert(ps!=NULL);
    return ps->top - ps->base;
}
bool StackEmpty(const SeqStack *ps)
{
    assert(ps!=NULL);
    return ps->top == ps->base;
    //return StackLength(ps)==0;
}
bool StackFull(const SeqStack *ps)
{
    assert(ps!=NULL);
    return StackLength(ps)==ps->stacksize;
}
bool IncSize(SeqStack *ps)
{
    assert(ps!=NULL);
    int newsize = ps->stacksize * STACKINC;
    SElemType *newdata = (SElemType*)realloc(ps->base,sizeof(SElemType)*newsize);
    
    if(NULL==newdata)return false;
    ps->base = newdata;
    
    ps->top = ps->base + ps->stacksize;
    
    ps->stacksize = newsize;
    return true;
}
Status Push(SeqStack *ps, SElemType val)
{
    assert(ps!=NULL);
    if(StackFull(ps) && !IncSize(ps))
    {
        return OVERFLOW;
    }
    *(ps->top) = val;
    ps->top += 1;
    return OK;
}
Status GetTop(const SeqStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(StackEmpty(ps))
    {
        return ERROR;
    }
    if(NULL == pval)return NULLPTR;
    *pval = *(ps->top-1);
    return OK;
}
Status Pop(SeqStack *ps, SElemType *pval)
{
    assert(ps !=NULL);
    if(StackEmpty(ps))
    {
        return ERROR;
    }
    if(NULL==pval)return NULLPTR;
    
    ps->top -= 1;
    *pval = *(ps->top);
    return OK;
}

测试

//TestStack.cpp
#include<stdio.h>
#include"My_SeqStack.h"
int main()
{
    SeqStack mys;
    InitStack(&mys);
    for (int i = 0;i < 10;++i)
    {
        Push(&mys, i);
    }
    int val;
    while (!StackEmpty(&mys))
    {
        Pop(&mys, &val);
        printf("%d ", val);
    }
    DestroyStack(&mys);
}

链栈

头文件

//LinkStack.h
#ifndef LINKSTACK_H
#define LINKSTACK_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*PStackNode;
typedef struct
{
    StackNode *top;
    int cursize;
}LinkStack;

Status InitStack(LinkStack *ps);
void DestroyStack(LinkStack *ps);
void ClearStack(LinkStack *ps);
int StackLength(const LinkStack *ps);
bool StackEmpty(const LinkStack *ps);
bool StackFull(const LinkStack *ps);
Status Push(LinkStack *ps, SElemType val);
Status GetTop(LinkStack *ps, SElemType *pval);
Status Pop(LinkStack *ps, SElemType *pval);
#endif

实现

//LinkStack.cpp
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include"LinkStack.h"
StackNode* Buynode()
{
    StackNode *newnode = (StackNode*)malloc(sizeof(StackNode));
    if(NULL!=newnode)
    {
        memset(newnode,0,sizeof(StackNode));
    }
    return newnode;
}
Status InitStack(LinkStack *ps)
{
    assert(ps!=NULL);
    ps->top = Buynode();//头结点
    if(NULL == ps->top)return OVERFLOW;
    
    ps->cursize = 0;
    return OK;
}
void DestroyStack(LinkStack *ps)
{
    assert(ps!=NULL);
    ClearStack(ps);
    free(ps->top);
    ps->top = NULL;
    return OK;
}
void ClearStack(LinkStack *ps)
{
    assert(ps!=NULL);
    while(ps->cursize!=0)
    {
        DelFront(ps);
    }
    return OK;
}
int StackLength(const LinkStack *ps)
{
    assert(ps!=NULL);
    return ps->cursize;
}
bool StackEmpty(const LinkStack *ps)
{
    assert(ps!=NULL);
    return ps->cursize == 0;
}
Status Push(LinkStack *ps, SElemType val)
{
    assert(ps!=NULL);
    StackNode *newnode = Buynode();
    if(NULL==newnode)return OVERFLOW;
    
    newnode->next = ps->top->next;
    ps->top->next = newnode;
    
    newnode->data = val;
    
    ps->cursize +=1;
    return OK;
}
Status GetTop(LinkStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(pval==NULL)return NULLPTR;
    if(ps->cursize<=0)return false;
    *pval = ps->top->next->data;
    return OK;
}
Status Pop(LinkStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(pval==NULL)return NULLPTR;
    if(ps->cursize<=0)return ERROR;
    GetTop(ps,pval);
    DelNext(ps);
    return OK;
}
bool DelFront(LinkStack *ps)
{
    assert(ps!=NULL);
    if(ps->cursize<=0)return false;
    StackNode *p = ps->top->next;
    ps->top->next = p->next;
    free(p);
    ps->cursize-=1;
    return true;
}

测试