分类:
2011-10-17 16:36:24
原文地址:【总结】数据结构-栈 作者:zollty
栈即后进先出(LIFO)的线性表。
栈的常用算法有置栈空、判栈空、进栈、出栈、取栈顶等。
1.顺序栈
结构如下:
typedef struct
{
DataType data[MAXSIZE];
int top;
}SeqStack;
即,它需要一个栈顶top。
相关算法的关键步骤如下
//置栈空
void Initial(SeqStack *S)
{ S->top=-1; }
//判栈空
int IsEmpty(SeqStack *S)
{ return S->top==-1; }
//进栈
void Push(SeqStack *S,DataType x)
{ S->data[++S->top]=x; }
//出栈
DataType Pop(SeqStack *S)
{ return S->data[S->top--]; } //栈顶减1,返回已经出栈的元素
2. 链栈
结构如下:
typedef struct node
{
DataType data;
struct node *next; //知道结构名称的作用了吧,这里就要用到node
}LinkStack;
typedef struct
{
LinkStack *top;
}TopNode;
我们需要一个专门指向栈顶的指针(注意不是栈顶指针,而是指向栈顶的指针)。所以我们定义一个结构体TopNode,T.top就是指向栈顶的指针。或者我们用一个数组也行:
LinkStack * TopNode[1];
那么TopNode[0]就用来作指向栈顶的指针,函数的形参写成LinkStack * TopNode[],传实参的时候用数组名TopNode,在函数内部就可以使用TopNode[0]。这种方面类似于函数形参是一个结构体TopNode *T,那么传实参的时候传&T,在函数内部使用T->top。
至于用数组和用结构哪个好,我觉得用结构还要用typedef定义类型,效率可能稍低。所以,用结构含义清楚,用数组效率更高。
/*头插法特点:无头结点,top指针始终指向最后插入的那个元素*/
LinkStack *CreListTou()
{ int x; LinkStack *S; TopNode T;
T.top=NULL;
scanf("%d",&x);
while(x!=-1) //输入-1代表结束
{
S=malloc(sizeof(LinkStack));
S->data=x;
/*关键代码: S->next等于T.top ,然后T.top反转来等于S*/
S->next=T.top;
T.top=S; //修改top指向
scanf("%d",&x);
}
return T.top;
}
//置栈空
void Initial(TopNode *T)
{ T->top=NULL; }
//进栈
void Push(TopNode *T,DataType x)
{
LinkStack *S;
S=malloc(sizeof(LinkStack));
S->data=x;
//与建栈时相同,将S的后继设置为原栈顶,S成为新的栈顶
S->next=T->top;
T->top=S;
}
//出栈
DataType Pop(TopNode *T)
{
LinkStack *p;
DataType x;
/*关键算法:先把T.top指向原栈顶的next,然后free掉原栈顶*/
p=T->top;
x=p->data;
T->top=p->next;// T.top指向原栈顶的next
free(p);
return x;
}
注意上面列出的只是算法的关键部分,并不完整,删减了一些“栈空”“栈满”的判断。