C 栈顺序存储

// seqstack.h

#ifndef _MY_SEQSTACK_H_

#define _MY_SEQSTACK_H_

typedef void SeqStack;

SeqStack* SeqStack_Create(int capacity);

void SeqStack_Destroy(SeqStack* stack);

void SeqStack_Clear(SeqStack* stack);

int SeqStack_Push(SeqStack* stack, void* item);

void* SeqStack_Pop(SeqStack* stack);

void* SeqStack_Top(SeqStack* stack);

int SeqStack_Size(SeqStack* stack);

int SeqStack_Capacity(SeqStack* stack);

#endif //_MY_SEQSTACK_H_

#define  _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include "seqstack.h"

#include "seqlist.h"  //顺序存储 链表

//创建栈 相当于 创建一个线性表

SeqStack* SeqStack_Create(int capacity)

{

    return SeqList_Create(capacity);

}

//销毁栈 相当于销毁链表

void SeqStack_Destroy(SeqStack* stack)

{

    SeqList_Destroy(stack);

}

//清空栈 相当于 清空线性表

void SeqStack_Clear(SeqStack* stack)

{

    SeqList_Clear(stack);

}

//栈插入元素 相当于 在线性表(数组)的尾部添加元素

int SeqStack_Push(SeqStack* stack, void* item)

{

    return SeqList_Insert(stack, item, SeqList_Length(stack)); //相当 尾插法

}

//栈 弹出元素  相当于 从线性表的尾部 删除元素

void* SeqStack_Pop(SeqStack* stack)

{

    return  SeqList_Delete(stack, SeqList_Length(stack)- );

}

//栈 获取栈顶元素 相当于 求链表的尾部元素

//获取栈顶元素 相当于 从链表的尾部拿元素;  尾部元素的下标=长度-1

void* SeqStack_Top(SeqStack* stack)

{

    return SeqList_Get(stack, SeqList_Length(stack) - );

}

//求栈的大小 相当于 链表的长度

int SeqStack_Size(SeqStack* stack)

{

    return SeqList_Length(stack);

}

//求栈的容量  相当于  求链表的容量

int SeqStack_Capacity(SeqStack* stack)

{

    return SeqList_Capacity(stack);

}

#ifndef  __MY_SEQLIST_H__

#define __MY_SEQLIST_H__

typedef void SeqList;

typedef void SeqListNode;

//链表 创建

SeqList* SeqList_Create(int capacity);

//链表 销毁

void SeqList_Destroy(SeqList* list);

////链表 清空

void SeqList_Clear(SeqList* list);

//链表 长度

int SeqList_Length(SeqList* list);

//链表 容量

int SeqList_Capacity(SeqList* list);

//链表 在某一个位置 插入元素

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

//获取某一个位置的链表结点

SeqListNode* SeqList_Get(SeqList* list, int pos);

//删除某一个位置的结点

SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif  //__MY_SEQLIST_H__

#define  _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include "seqlist.h"

//用数组来模拟线性表

typedef struct _tag_SeqList

{

    int        capacity;

    int        length;

    //int *node[100];

    int        **node;  //int node[capacity] //

                    //int *node[capacity];

    //int *node; //   int node[i]===> *(node+i)

}TSeqList;

//链表 创建

SeqList* SeqList_Create(int capacity) //O(1)

{

    int            ret;

    TSeqList    *tmp = NULL;

    tmp = (TSeqList *)malloc(sizeof(TSeqList));

    if (tmp == NULL)

    {

        ret =;

        printf("func SeqList_Create() err :%d \n", ret);

        return NULL;

    }

    memset(tmp, , sizeof(TSeqList));

    tmp->capacity = capacity;

    tmp->length = ;

    tmp->node = (int **)malloc(sizeof(void *) * capacity);

    if (tmp->node == NULL)

    {

        ret = ;

        printf("func SeqList_Create() malloc err :%d \n", ret);

        return NULL;

    }

    memset(tmp->node, , sizeof(void *) * capacity);

    return tmp;

}

//链表 创建

int SeqList_Create2(int capacity, SeqList**handle)

{

    int            ret = ;

    TSeqList    *tmp = NULL;

    tmp = (TSeqList *)malloc(sizeof(TSeqList));

    if (tmp == NULL)

    {

        ret =;

        printf("func SeqList_Create2() err :%d \n", ret);

        return ret;

    }

    memset(tmp, , sizeof(TSeqList));

    tmp->capacity = capacity;

    tmp->length = ;

    tmp->node = (int **)malloc(sizeof(void *) * capacity);

    if (tmp->node == NULL)

    {

        ret = ;

        printf("func SeqList_Create2() malloc err :%d \n", ret);

        return ret;

    }

    *handle = tmp;

    return ret;

}

//链表 销毁

void SeqList_Destroy(SeqList* list)  //O(1)

{

    TSeqList    *tmp = NULL;

    if (list == NULL)

    {

        return ;

    }

    tmp = (TSeqList *)list;

    if (tmp->node != NULL)

    {

        free(tmp->node);

    }

    free(tmp);

    return ;

}

////链表 清空

void SeqList_Clear(SeqList* list) //O(1)

{

    TSeqList    *tmp = NULL;

    if (list == NULL)

    {

        return ;

    }

    tmp = (TSeqList *)list;

    tmp->length = ;

    memset(tmp->node, , (tmp->capacity * sizeof(void *)) );

    return ;

}

//链表 长度

int SeqList_Length(SeqList* list) //O(1)

{

    TSeqList    *tmp = NULL;

    if (list == NULL)

    {

        return -;

    }

    tmp = (TSeqList *)list;

    return tmp->length;

}

//链表 容量

int SeqList_Capacity(SeqList* list) //O(1)

{

    TSeqList    *tmp = NULL;

    if (list == NULL)

    {

        return -;

    }

    tmp = (TSeqList *)list;

    return tmp->capacity;

}

//链表 在某一个位置 插入元素

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)  //O(n)

{

    TSeqList    *tList = NULL;

    int i = ;

    if (list == NULL ||  node==NULL)

    {

        return -;

    }

    tList = (TSeqList *)list;

    //如果满了

    if (tList->length >= tList->capacity)

    {

        return -;

    }

    //pos位置的容错处理

    if (pos > tList->length )

    {

        pos = tList->length;

    }

    for (i=tList->length; i>pos; i--)  //n

    {

        tList->node[i] = tList->node[i-];

    }

    tList->node[i] = (int* )node; //ok

    tList->length ++;

    return ;

}

//获取某一个位置的链表结点

SeqListNode* SeqList_Get(SeqList* list, int pos)  //O(1)

{

    TSeqList    *tList = NULL;

    SeqListNode *tmp = NULL;

    tList = (TSeqList *)list;

    if (list == NULL || pos< || pos >=tList->length )

    {

        return NULL;

    }

    tmp = tList->node[pos];

    return tmp;

}

//删除某一个位置的结点

SeqListNode* SeqList_Delete(SeqList* list, int pos)  ////O(n)

{

    int            i = ;

    TSeqList    *tList = NULL;

    SeqListNode *tmp = NULL; 

    tList = (TSeqList *)list;

    if (list == NULL || pos < || pos >= tList->length)

    {

        return NULL;

    }

    tmp = tList->node[pos];

    // pos = 3

    for (i=pos+; i<tList->length; i++)

    {

        tList->node[i-] = tList->node[i];

    }

    tList->length --;

    return tmp;

}

#define  _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include "seqstack.h"

void main()

{

    int i = ;

    SeqStack *stack = NULL;

    int  a[];

    for (i=; i<; i++)

    {

        a[i] = i+;

    }

    stack = SeqStack_Create();

    //入栈

    for (i=; i<; i++)

    {

        SeqStack_Push(stack, &a[i]);

    }

    //栈的属性

    printf("len:%d \n", SeqStack_Size(stack));

    printf("capacity:%d \n", SeqStack_Capacity(stack));

    printf("top:%d \n", *((int *)SeqStack_Top(stack) )   )  ;

    //元素出栈

    while (SeqStack_Size(stack) > )

    {

        printf("%d ",   *( (int *)SeqStack_Pop(stack) ) );

    }

    SeqStack_Destroy(stack);

    printf("hello...\n");

    system("pause");

    return ;

}

巴特西

C 栈顺序存储

最新文章

热门文章