数据结构：C_顺序栈的实现

时间：2023-02-03 10:24:30

数据结构顺序栈的实现（C语言版）

1.写在前面

　　栈是一种遵循元素先进(Push)后出(Pop)规则的线性表，它的实现可以用数组或者链表。

　　.....

 

2.代码分解

2.1对栈的结构定义：

typedef struct
{
int *base; 
int *top; 
int stacksize;    
}SqStack;

　　|说明：

　　　　1.base表示栈底指针，在判断出栈、初始化和重新分配空间的时候需要用到。

　　　　2.top表示栈顶指针，是栈最关键和核心的组成，入栈时top向上移动，出栈时top向下移动。

　　　　3.此处的stacksize并不表示当前的栈中的元素数量，而是表示栈的容量，也就是能装多少个元素。

 

2.2初始化栈：

int initStack(SqSatck *S)
{
    S->base=(int*)malloc(100*sizeof(int));
if(!S)
return 0; //0代表操作失败
    S->top=S->base;
    stacksize=100;
return 1; //1代表操作完成
}

　　|说明：

　　　　1.顺序栈初始化无非就是给栈分配连续的内存空间，base是栈底指针，在上面提到过，它用来指示一段连续的内存空间的首地址，也就是用来初始化。

　　　　2.分配空间不意味着一定会有那么多空间，所以判断也不可缺少。

　　　　3.分配空间后，base和top的地址应该一致，此时top还没有移动。

 

2.3压栈

int push(SqStack * S,int elem)
{
if(S->top-S->base>=S->stacksize)
  {
        S->base=(SElemType *)
                realloc(S->base,(S->stacksize+10)*sizeof(SElemType)); //10代表增量，你可以使用宏定义，方便后续修改。
if(!S->base)
return 0;
        S->top=S->base+S->stacksize;
        S->stacksize+=10
  }
*S->top++=elem;
return 1;
}

　　　|说明：

　　　　1.压栈是栈的核心操作，关键步骤无非是*S->top++=elem;但是在进行此步操作时，一定要判断栈是否超出容量。

　　　　2.如果栈超出容量，则要在进行原空间的基础上重新分配空间，realloc是关键的命令。

　　realloc 
　　　　原型：extern void *realloc(void *mem_address, unsigned int newsize); 
　　　　用法：#include <stdlib.h> 有些编译器需要#include <alloc.h> 
　　　　功能：改变mem_address所指内存区域的大小为newsize长度。 
　　　　说明：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 
　　　　当内存不再使用时，应使用free()函数将内存块释放。 

　　　　3.分配空间以后，在修改stacksize之前，top应该保持在容量顶端，S->top=S->base+S->stacksize;

 

2.4出栈

int pop(SqStack *q)
{
if(S->top==S->base)
return 0;
return *S->--top;;
}

　　|说明：

　　　　1.出栈是简单操作，其实这里并没有完美的实现这个效果，你应该考虑到如果在扩容后又迅速减小，会造成大量的空间浪费。

 

2.5遍历栈

int printfStack(SqStack *S)
{
int *p=S->base;
    puts("输出栈");
for(p;p!=S->top;p++)
    {
        printf("***%d",*p);
    }
}

 

标签：

相关文章