首页 > 安全资讯 >

一步一步写算法(之线性堆栈)

11-10-23

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 前面我们讲到了队列,今天我们接着讨论另外一种数据结构:堆栈。堆栈几乎是程序设计的命脉,没有堆栈就没有函数调用,当...

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

 

 

 

   前面我们讲到了队列,今天我们接着讨论另外一种数据结构:堆栈。堆栈几乎是程序设计的命脉,没有堆栈就没有函数调用,当然也就没有软件设计。那么堆栈有什么特殊的属性呢?其实,堆栈的属性主要表现在下面两个方面:

 

    (1)堆栈的数据是先入后出

 

    (2)堆栈的长度取决于栈顶的高度

 

    那么,作为连续内存类型的堆栈应该怎么设计呢?大家可以自己先试一下:

 

    (1)设计堆栈节点

 

 

typedef struct _STACK_NODE 

    int* pData; 

    int length; 

    int top; 

}STACK_NODE; 

typedef struct _STACK_NODE

{

    int* pData;

       int length;

       int top;

}STACK_NODE;    (2)创建堆栈

 

STACK_NODE* alloca_stack(int number) 

    STACK_NODE* pStackNode = NULL; 

    if(0 == number) 

        return NULL; 

     

    pStackNode = (STACK_NODE*)malloc(sizeof(STACK_NODE)); 

    assert(NULL != pStackNode); 

    memset(pStackNode, 0, sizeof(STACK_NODE)); 

     

    pStackNode->pData = (int*)malloc(sizeof(int) * number); 

    if(NULL == pStackNode->pData){ 

        free(pStackNode); 

        return NULL; 

    } 

     

    memset(pStackNode->pData, 0, sizeof(int) * number); 

    pStackNode-> length = number; 

    pStackNode-> top= 0; 

    return pStackNode; 

STACK_NODE* alloca_stack(int number)

{

    STACK_NODE* pStackNode = NULL;

    if(0 == number)

           return NULL;

      

    pStackNode = (STACK_NODE*)malloc(sizeof(STACK_NODE));

    assert(NULL != pStackNode);

    memset(pStackNode, 0, sizeof(STACK_NODE));

      

    pStackNode->pData = (int*)malloc(sizeof(int) * number);

    if(NULL == pStackNode->pData){

           free(pStackNode);

        return NULL;

    }

      

    memset(pStackNode->pData, 0, sizeof(int) * number);

    pStackNode-> length = number;

    pStackNode-> top= 0;

    return pStackNode;

}    (3)释放堆栈

 

STATUS free_stack(const STACK_NODE* pStackNode) 

    if(NULL == pStackNode) 

        return FALSE; 

     

    assert(NULL != pStackNode->pData);    

         

    free(pStackNode->pData); 

    free((void*)pStackNode); 

    return TRUE; 

STATUS free_stack(const STACK_NODE* pStackNode)

{

    if(NULL == pStackNode)

        return FALSE;

      

    assert(NULL != pStackNode->pData); 

             

    free(pStackNode->pData);

    free((void*)pStackNode);

    return TRUE;

}    (4)堆栈压入数据

 

 

STATUS stack_push(STACK_NODE* pStackNode, int value) 

    if(NULL == pStackNode) 

        return FALSE; 

         

    if(pStackNode->length = pStackNode->top) 

        return FALSE; 

         

    pStackNode->pData[pStackNode->top ++] = value; 

    return TRUE; 

STATUS stack_push(STACK_NODE* pStackNode, int value)

{

    if(NULL == pStackNode)

        return FALSE;

             

    if(pStackNode->length = pStackNode->top)

        return FALSE;

             

    pStackNode->pData[pStackNode->top ++] = value;

    return TRUE;

}    (5)堆栈弹出数据

 

STATUS stack_pop(STACK_NODE* pStackNode, int* value) 

    if(NULL == pStackNode || NULL == value) 

        return FALSE; 

         

    if(0 == pStackNode->top) 

        return FALSE; 

         

    *value = pStackNode->pData[-- pStackNode->top]; 

    return TRUE; 

STATUS stack_pop(STACK_NODE* pStackNode, int* value)

{

    if(NULL == pStackNode || NULL == value)

        return FALSE;

             

    if(0 == pStackNode->top)

        return FALSE;

             

    *value = pStackNode->pData[-- pStackNode->top];

    return TRUE;

}    (6)统计当前堆栈中包含多少数据

 

 

int count_stack_number(const STACK_NODE* pStackNode) 

    return pStackNode->top; 

int count_stack_number(const STACK_NODE* pStackNode)

{

    return pStackNode->top;

}

    建议: 堆栈是函数调用的基础,是递归调用的基础,是很多问题的根源,建议朋友们平时有时间好好练习一下。

 

 

 

相关文章
最新文章
热点推荐