C语言栈顺序结构实现代码

代码如下:

/**
* @brief C语言实现的顺序结构类型的栈
* @author wid
* @date 2013-10-29
*
* @note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢!
*/

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

#define TRUE 1
#define FALSE 0

typedef struct Point2D
{
    int x;
    int y;
}ElemType;      //栈元素结构

typedef struct
{
    ElemType *btm;      //栈底
    ElemType *top;      //栈顶
    int height;         //栈高
    int size;           //栈总大小
}ArrStack;      //栈结构

//栈方法声明
ArrStack *CreateStack( int nSize );             ///创建一个大小为nSize的栈
void DestroyStack( ArrStack *pStack );          ///销毁栈 pStack
void ClearStack( ArrStack *pStack );            ///清空栈 pStack 内的元素
int GetHeight( ArrStack *pStack );              ///获取栈 pStack 的高度
int GetSize( ArrStack *pStack );                ///获取栈 pStack 的总容量
int IsEmpty( ArrStack *pStack );                ///检测栈 pStack 是否为空栈
int Push( ArrStack *pStack, ElemType *pt );     ///将元素 pt 压入栈 pStack
int Pop( ArrStack *pStack, ElemType *pt );      ///将栈顶元素出栈到 pt
int GetTop( ArrStack *pStack, ElemType *pt );   ///获取栈顶元素到 pt
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) );      ///从栈底到栈顶的每个元素依次执行 func 函数
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) );    ///从栈顶到栈底的每个元素依次执行 func 函数

//栈方法实现

/**
* @brief 创建一个大小为 nSize 的栈
*
* @param nSize 栈的初始大小
*
* @return 返回指向创建的栈的指针
*
* @note nSize 初始大小需大于0
*/
ArrStack *CreateStack( int nSize )
{
    //根据栈结构创建一个栈
    ArrStack *pStack = (ArrStack *)malloc( sizeof(ArrStack) );

//申请栈初始空间
    pStack->btm = (ElemType *)calloc( nSize, sizeof(ElemType) );

//令栈顶指向栈底元素
    pStack->top = &pStack->btm[0];

//初始化栈高度为 0
    pStack->height = 0;

//初始化栈大小为初始大小
    pStack->size = nSize;

return pStack;
}

/**
* @brief 销毁栈 pStack
*
* @param pStack 指向待销毁的栈的指针
*
* @return void
*/
void DestroyStack( ArrStack *pStack )
{
    //释放栈内元素
    free( pStack->btm );

//释放栈
    free( pStack );
}

/**
* @brief 清空栈内元素
*
* @param pStack 指向待清空元素的栈的指针
*
* @return void
*/
void ClearStack( ArrStack *pStack )
{
    //令栈顶指向栈底
    pStack->top = &pStack->btm[0];

//将栈高度置为 0
    pStack->height = 0;
}

/**
* @brief 获取栈 pStack 的高度
*
* @param pStack 指向待获取高度的栈的指针
*
* @param 返回当前栈的高度
*/
int GetHeight( ArrStack *pStack )
{
    return pStack->height;
}

/**
* @brief 获取栈 pStack 的总容量
*
* @param pStack 指向待获取总容量的栈的指针
*
* @return 返回栈的当前总容量
*/
int GetSize( ArrStack *pStack )
{
    return pStack->size;
}

/**
* @brief 检测栈 pStack 是否为空栈
*
* @param pStack 指向待检测的栈的指针
*
* @return 若栈为空, 则返回 TRUE, 否则返回 FALSE
*/
int IsEmpty( ArrStack *pStack )
{
    return pStack->height == 0 ? TRUE : FALSE;
}

/**
* @brief 将元素 pt 压入栈 pStack
*
* @param pStack 指向待压入元素的栈的指针
* @param pt 指向待压入元素的指针
*
* @return 返回成功压入后栈的高度
*/
int Push( ArrStack *pStack, ElemType *pt )
{
    ///检测是否需要扩容
    if( pStack->height == pStack->size )
    {   //需要扩容

//重新申请于原栈大小2倍大小的栈空间
        ElemType *pe = (ElemType *)calloc( pStack->size * 2, sizeof(ElemType) );

//将旧栈内容拷贝到新栈内容
        memcpy( pe, pStack->btm, pStack->size * sizeof(ElemType) );

//重置栈总容量大小
        pStack->size = pStack->size * 2;

//释放旧栈空间
        free( pStack->btm );

//将栈底指向新开辟的栈空间
        pStack->btm = pe;

//栈顶指向新栈最后一个元素
        pStack->top = &pe[pStack->height-1];
    }

//将新元素压入栈
    pStack->btm[pStack->height].x = pt->x;
    pStack->btm[pStack->height].y = pt->y;

//栈高度自增一
    ++pStack->height;

//栈顶指向最新栈元素
    pStack->top = &pStack->btm[pStack->height-1];

return pStack->height;
}

/**
* @brief 将栈顶元素出栈 到 pt
*
* @param pStack 指向待弹出元素的栈的指针
* @param pt 指向接收弹出的元素的指针
*
* @return 出栈成功则返回出栈后栈的高度, 否则返回 -1
*/
int Pop( ArrStack *pStack, ElemType *pt )
{
    ///是否为空栈
    if( pStack->height == 0 )
        return -1;

//将栈顶元素赋值到 pt
    pt->x = pStack->top->x;
    pt->y = pStack->top->y;

//栈高度减一
    --pStack->height;

//栈顶指向栈顶元素的上一个元素
    pStack->top = &pStack->btm[pStack->height-1];

return pStack->height;
}

/**
* @brief 获取栈顶元素到 pt
*
* @param pStack 指向待弹出元素的栈的指针
* @param pt 指向接收弹出的元素的指针
*
* @return 获取成功则返回栈顶元素的位置, 否则返回 -1
*
* @note 元素位置由 0 计起
*/
int GetTop( ArrStack *pStack, ElemType *pt )
{
    pt->x = pStack->top->x;
    pt->y = pStack->top->y;

return pStack->height;
}

/**
* @brief 从栈底到栈顶的每个元素依次执行 func 函数
*
* @param pStack 指向待处理的栈的指针
* @param func 需要执行的函数的指针
*
* @return void
*/
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
    int i = 0;
    for( i = 0; i <  pStack->height; ++i )
    {
        func( &pStack->btm[i] );
    }
}

/**
* @brief 从栈顶到栈底的每个元素依次执行 func 函数
*
* @param pStack 指向待处理的栈的指针
* @param func 需要执行的函数的指针
*
* @return void
*/
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
    int i = pStack->height - 1;
    for( i; i >= 0; --i )
    {
        func( &pStack->btm[i] );
    }
}

//测试

void display( ElemType *pt )
{
    printf( "(%d,%d) ", pt->x, pt->y );
}

int main()
{
    ///测试创建初始大小为 5 的栈
    ArrStack *psk = CreateStack( 5 );

///测试 IsEmpty、GetSize、GetHeight
    if( IsEmpty(psk) == TRUE )
        printf( "Stack Size=%d, Stack Height=%d\n", GetSize(psk), GetHeight(psk) );

ElemType pt;

int i = 0;
    ///测试Push, 向栈内压入8个元素
    printf( "\n向栈内压入8个元素后:\n" );
    for( i = 0; i < 8; ++i )
    {
        pt.x = pt.y = i;
        Push( psk, &pt );
    }
    //输出压入8个元素后的栈状态
    printf( "Is empty = %d\n", IsEmpty(psk) );
    printf( "Stack size = %d\n", GetSize(psk) );
    printf( "Stack height = %d\n", GetHeight(psk) );

///测试 ForEachStack、ReForEachStack
    printf( "\n测试 ForEachStack、ReForEachStack:\n" );
    ForEachStack( psk, display );
    putchar('\n');
    ReForEachStack( psk, display );
    putchar('\n');

///测试getTop
    GetTop( psk, &pt );
    printf( "\n栈顶元素为: (%d,%d)\n", pt.x, pt.y );

///测试 Pop
    Pop( psk, &pt );
    printf( "\nPop弹出的元素为(%d,%d), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );
    Pop( psk, &pt );
    printf( "\nPop弹出的元素为(%d,%d), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );

///测试Push
    pt.x = pt.y = 100;
    Push( psk, &pt );
    printf( "\nPop压入的元素为(%d,%d), 压入后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );

///执行全面出栈操作
    printf( "\n执行全面出栈:\n" );
    int n = GetHeight(psk);
    for( i = 0; i < n; ++i )
    {
        Pop( psk, &pt );
        printf( "Pop弹出的元素为(%d,%d), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );
    }

///销毁栈
    DestroyStack( psk );

return 0;
}

测试结果:

(0)

相关推荐

  • C语言中网络地址与二进制数之间转换的函数小结

    C语言inet_ntoa()函数:将网络二进制的数字转换成网络地址 头文件: #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> 定义函数: char * inet_ntoa(struct in_addr in); 函数说明:inet_ntoa()用来将参数in 所指的网络二进制的数字转换成网络地址, 然后将指向此网络地址字符串的指针返回. 返回值:成功则返回字符串指针, 失败则返

  • C语言对栈的实现基本操作

    c语言中栈是一种数据结构,后进先出,即最后进入栈的数据最先弹出.c语言中没有栈这种数据类型,需要自己编程构建.下面我们就一起来了解一下c语言中栈的基本操作. C语言对栈的实现基本操作,操作如下: #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <stdbool.h> typedef struct Node { int data; struct Node * pNext;

  • C语言堆栈入门指南

    C语言堆栈入门指南 在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到.但对于很多的初学着来说,堆栈是一个很模糊的概念.堆栈:一种数据结构.一个在程序运行时用于存放的地方,这可能是很多初学者的认识,因为我曾经就是这么想的和汇编语言中的堆栈一词混为一谈.我身边的一些编程的朋友以及在网上看帖遇到的朋友中有好多也说不清堆栈,所以我想有必要给大家分享一下我对堆栈的看法,有说的不对的地方请朋友们不吝赐教,这对于大家学习会有很大帮助. 首先在数据结构上要知道堆栈,尽管我们这么称呼它,

  • C语言栈的表示与实现实例详解

    1.基本概念: C语言的栈是指限定仅在表尾进行插入和删除操作的线性表. 栈作为C语言中一种常用的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表.它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来).栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针. 栈是允许在同一端进行插入和删除操作的特殊线性表.允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom):栈底固定,而栈顶浮动

  • c语言stack(栈)和heap(堆)的使用详解

    一.预备知识-程序的内存分配 一个由C/C++编译的程序占用的内存分为以下几个部分 1.栈区(stack)-由编译器自动分配释放,存放函数的参数值,局部变量的值等.其操作方式类似于数据结构中的栈.2.堆区(heap)-一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收.注意它与数据结构中的堆是两回事,分配方式倒是类似于链表.3.全局区(静态区)(static)-全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另

  • C语言用栈实现十进制转换为二进制的方法示例

    本文实例讲述了C语言用栈实现十进制转换为二进制的方法.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h> #include<math.h> #include<string.h> #include "process.h" #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRU

  • 编写C语言程序进行进制转换的问题实例

    题目 题目描述:      将M进制的数X转换为N进制的数输出.      输入:      输入的第一行包括两个整数:M和N(2<=M,N<=36).      下面的一行输入一个数X,X是M进制的数,现在要求你将M进制的数X转换成N进制的数输出.      输出:      输出X的N进制表示的数.      样例输入:      16 10      F      样例输出:      15      提示:      输入时字母部分为大写,输出时为小写,并且有大数据. 思路 大整数乘法

  • C语言实现颠倒栈的方法

    本文实例讲述了C语言实现颠倒栈的方法,很实用的技巧.分享给大家供大家参考之用. 具体实现方法如下: #include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <stack> using namespace std; void initializeStack(stack<int> &st) { for(int i

  • 详解C语言中的字符串拼接(堆与栈)

    首先来看一个demo: int do_sth(int type) { char *errstr; switch(type) { case 1: errstr = "Error";break case 2: errstr = "Warn";break case 3: errstr = "Info";break case 4: errstr = "Debug";break default: return 0; } if (...)

  • C语言进制转换代码分享

    代码很简单,功能也很简单,这里就不多废话了 #include<stdio.h> int main() { char ku[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; int zh[32],i=0,w,j; long int b,y; printf("请输入一个十进制数,我能帮您把它转换成2~16任意进制数:\n"); scanf("%d",&y);

  • 深入浅析C语言中堆栈和队列

    1.堆和栈 (1)数据结构的堆和栈 堆栈是两种数据结构. 栈(栈像装数据的桶或箱子):是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取.这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体). 堆(堆像一棵倒过来的树):是一种经过排序的树形数据结构,每个结点都有一个值.通常所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆.由于堆的这个特性,常用来实现优先队列,堆的存取是随意,

随机推荐