C說話棧次序構造完成代碼。本站提示廣大學習愛好者:(C說話棧次序構造完成代碼)文章只能為提供參考,不一定能成為您想要的結果。以下是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;
}
測試成果: