当前位置：移动技术网 > IT编程>开发语言>C/C++ > 栈的c语言实现

栈的c语言实现

2018年10月15日 | 移动技术网IT编程 | 我要评论

睫毛不翘,三打白骨精故事简介,南国影城宝安店

栈的基本概念

栈是限定仅在表尾进行插入或删除的操作.因此,对于栈来说,表尾端有其特殊的含义,称为栈顶(top),相应的表头端称为栈底(bottom).不含元素的空表称为空栈.
栈的修改是按照后进先出的原则进行的,又成为lifo结构.插入元素的操作称为入栈,删除栈顶元素的操作成为出栈.

栈的基本操作有:

插入删除初始化判空取栈顶元素清除栈销毁栈遍历栈栈的长度

栈的表示和实现

栈有两种表示方式:

1. 顺序栈

使用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置.
一般实现方法:
    先为 栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时在逐段增大.
    顺序栈的定义如下:
    typedef struct{
        selemtype *base;
        selemtype *top;
        int stacksize;
    }
其中stacksize指示栈的当前可使用的最大容量,base称为栈底指针,始终指向栈底位置.top为栈顶指针,当top=base时,栈为空.当base=null时,栈结构不存在.

2. 链式栈

链式栈就是一个特殊的只能对第一个结点进行操作的单链表.这里不在做过多的论述

代码实现

顺序栈

基本上参考严蔚敏老师的《数据结构》（版）代码实现

/* 接口的定义文件 */
/* stack 顺序存储的结构定义和接口声明 */

/* 存储空间的初始分配量 */
#define stack_init_size 100
/* 存储空间分配增量 */
#define stackincrement 10

#define true 1
#define false 0



/* 定义数据类型 */
typedef int datatype;

/* 栈的数据结构定义 */
typedef struct{
    /* 在构造之前和销毁之后base的值为null */
    datatype *base;
    /* 栈顶指针 */
    datatype *top;
    /* 当前已分配的存储空间 */
    int stacksize;
}stack,*sp_stack;

/* 基本操作的函数原型说明 */

/* 构造一个空栈s */
sp_stack stack_init(sp_stack s);

/* 销毁栈s,s不再存在 */
void stack_destroy(sp_stack s);

/* 置栈为空 */
void stack_clear(sp_stack s);

/* 判断栈是否为空
 * 若为空,返回true
 * 否则返回false
*/
int stack_empty(sp_stack s);


/* 返回栈中元素的个数 */
int stack_length(sp_stack s);

/* 若栈不空
 * 用e返回s的栈顶元素,并返回true
 * 否则返回false
*/
int get_top(sp_stack s, datatype *e);


/* 插入元素e为新的栈顶元素 */
void push(sp_stack s, datatype e);

/* 若栈不空
 * 删除栈顶元素,用e返回其值,并返回true
 * 否则返回false
*/
int pop(sp_stack s, datatype *e);



/* 从栈底到栈顶依次对栈中每个元素调用visit()函数.
 * 一旦visit()失败,则操作失败
*/
 void stack_traverse(sp_stack s, void(*visit)(sp_stack));

/* 遍历处理函数 */
void visit(sp_stack s);

 /* 接口的实现文件 */
 #include
#include
#include"sp_stack.h"



sp_stack stack_init(sp_stack s)
{
    /* 申请内存空间 */
    s -> base = (datatype *)malloc(sizeof(datatype) * stack_init_size);
    /* 申请内存失败 */
    if (!s -> base)
        exit(0);
    s -> stacksize = stack_init_size;
    s -> top = s -> base;
    return s;
}


void stack_destory(sp_stack s)
{
    free(s -> base);
    free(s);
    s = null;
}



void stack_clear(sp_stack s)
{
    s -> top = s -> base;
}


int stack_length(sp_stack s)
{
    int l = s -> top - s -> base;
    return l;
}


int get_top(sp_stack s, datatype *e)
{
    if (s -> top == s -> base)
        return false;
    *e = *(s -> top);
    return true;
}

void push(sp_stack s, datatype e)
{
    /* 内存已满 */
    if ( (s -> top - s -> base) >= s -> stacksize)
    {
        s -> base = (datatype *) realloc(s -> base, (s -> stacksize + stackincrement) * sizeof(datatype));
        /* 申请内存失败 */
        if (!s -> base)
            exit(0);
        s -> top = s -> base + s -> stacksize;
        s -> stacksize = s -> stacksize + stackincrement;

    }
    s -> top = s -> top + 1;
    *s -> top = e;
}


int pop(sp_stack s, datatype *e)
{
    /* 栈为空 */
    if(s -> top == s -> base)
        return false;
    *e = *s -> top;
    s -> top = s -> top - 1;
    return true;
}


void stack_traverse(sp_stack s, void (*visit)(sp_stack s))
{
    visit(s);
}


void visit(sp_stack s)
{
    datatype *temp = s -> base + 1;
    while(true)
    {
        if(temp  top)
        {
            printf("%d ", *temp);
            temp = temp + 1;
        }
        else
        {
            printf("\n");
            break;
        }
    }

}



int main()
{
    sp_stack s = (sp_stack)malloc(sizeof(stack));
    s = stack_init(s);
    printf("length:%d\n", stack_length(s));
    push(s, 1);
    printf("length:%d\n", stack_length(s));
    push(s, 2);
    printf("length:%d\n", stack_length(s));
    push(s, 3);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
    datatype *e;
    get_top(s, e);
    printf("get_top:%d\n", *e);
    stack_traverse(s, visit);   
    pop(s, e);
    printf("pop:%d\n", *e);
    stack_clear(s);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
}

链式栈

参考严蔚敏老师的《数据结构》（c语言版）的接口，接口的实现有自己完成。

/* 接口的定义文件 */
/* stack 链式存储的结构定义和接口声明 */


#define true 1
#define false 0



/* 定义数据类型 */
typedef int datatype;

/* 栈的数据结构定义 */
typedef struct stack{
    /* 数据域 */
    datatype data;
    /* 指针域 */
    struct stack *next;
}stack,*lp_stack;

/* 基本操作的函数原型说明 */

/* 构造一个空栈s */
lp_stack stack_init(lp_stack s);

/* 销毁栈s,s不再存在 */
void stack_destroy(lp_stack s);

/* 置栈为空 */
void stack_clear(lp_stack s);

/* 判断栈是否为空
 * 若为空,返回true
 * 否则返回false
*/
int stack_empty(lp_stack s);


/* 返回栈中元素的个数 */
int stack_length(lp_stack s);

/* 若栈不空
 * 用e返回s的栈顶元素,并返回true
 * 否则返回false
*/
int get_top(lp_stack s, datatype *e);


/* 插入元素e为新的栈顶元素 */
void push(lp_stack s, datatype e);

/* 若栈不空
 * 删除栈顶元素,用e返回其值,并返回true
 * 否则返回false
*/
int pop(lp_stack s, datatype *e);



/* 从栈底到栈顶依次对栈中每个元素调用visit()函数.
 * 一旦visit()失败,则操作失败
*/
 void stack_traverse(lp_stack s, void(*visit)(lp_stack));

/* 遍历处理函数 */
void visit(lp_stack s);


/* 接口的实现文件 */
#include
#include
#include"lp_stack.h"



lp_stack stack_init(lp_stack s)
{

    s -> next = null;
    return s;
}


void stack_destroy(lp_stack s)
{
    lp_stack temp = s;
    while(s)
    {
        s = s -> next;
        free(temp);
        temp = s;
    }
}



void stack_clear(lp_stack s)
{
    lp_stack temp = s -> next;
    while(s -> next)
    {
        s -> next = s -> next -> next;
        free(temp);
        temp = s -> next;
    }
}


int stack_empty(lp_stack s)
{
    if(s -> next = null)
        return true;
    return false;

}


int stack_length(lp_stack s)
{
    /* 栈的当前结点 */
    lp_stack top = s -> next;
    /* 计数器 */
    int count = 0;
    while(top)
    {
        count += 1;
        top = top -> next;
    }
    return count;
}

int get_top(lp_stack s, datatype *e)
{
    if (s -> next == null)
        return false;
    *e = s -> next -> data;
    return true;
}

void push(lp_stack s, datatype e)
{
    lp_stack new_node = (lp_stack)malloc(sizeof(stack));
    new_node -> data = e;
    new_node -> next = s -> next;
    s -> next = new_node;
}


int pop(lp_stack s, datatype *e)
{
    if(s -> next == null)
        return false;
    *e = s -> next -> data;
    lp_stack node = s -> next;
    s -> next = s -> next -> next;
    free(node);
    return true;
}

void stack_traverse(lp_stack s, void (*visit)(lp_stack))
{
    visit(s);
}


void visit(lp_stack s)
{
    lp_stack node = s -> next;
    while(node)
    {
        printf("%d ",node -> data);
        node = node -> next;
    }
}

int main()
{
    lp_stack s = (lp_stack)malloc(sizeof(stack));
    s = stack_init(s);
    printf("length:%d\n", stack_length(s));
    push(s, 1);
    printf("length:%d\n", stack_length(s));
    push(s, 2);
    printf("length:%d\n", stack_length(s));
    push(s, 3);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
    datatype *e;
    get_top(s, e);
    printf("get_top:%d\n", *e);
    stack_traverse(s, visit);   
    pop(s, e);
    printf("pop:%d\n", *e);
    stack_traverse(s, visit);
    stack_clear(s);
    printf("length:%d\n", stack_length(s));
    stack_traverse(s, visit);
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！点击进行留言回复

C++ 作用域

作用域：名称在翻译单元（包括文件）的可见范围局部：只在定义它的代码块中可用，如自动变量全局（文件作用域）：从定义位置到文件结尾都可用注意：静... [阅读全文]
Prim计算最小生成树权值 C语言

题目描述现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先，你会给定在区域里面的一系列结点，和连接这些结点的一组线路。对于每条可能使用... [阅读全文]
C打印楼梯，同时在楼梯上方打印两个笑脸

题目：打印楼梯，同时在楼梯上方打印两个笑脸。程序分析：用 ASCII 1 来输出笑脸；用i控制行，j来控制列，j根据i的变化来控制输出黑方格的个数。 ... [阅读全文]
算法笔记刷题6 ( PAT 1003我要通过 )

算法笔记刷题6 ( PAT1003我要通过 ) 题目本体 “ 答案正确 ”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“ 答案正确 ”大派... [阅读全文]
聚合类型与POD类型

Lippman在《深度探索C++对象模型》的前言中写道： I have heard a number of people over the years ... [阅读全文]
GetAsyncKeyState 获取键盘按键消息

1 #include <Windows.h> 2 #include <iostream> 3 using namespace s... [阅读全文]
c primer plus(中文版)第一章的一处错误

c primer plus(中文版)1.8.8 第三段第三段第一句：“UNIX系统内置Mac OS X”。这句话讲不通，UNIX系统内置MAC OS ... [阅读全文]
如何在没有core文件的情况下用dmesg+addr2line定位段错误

前言在现网环境下，程序奔溃后不一定会留下core文件，原因有很多，比如存储空间不足就是其中一个常见的原因。此时我们只能依据linux记录的错误日志来定位... [阅读全文]
用QT制作3D点云显示器——QtDataVisualization

因为QT的三维显示模块QtDataVisualization已经对个人开发免费开放了，所以在制作点云，地图，表格之类的东西的时候，其实我们都不需要使用Q... [阅读全文]
判断一个数是否为素数（质数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 ... [阅读全文]

网友评论


验证码：