Chinaunix首页 | 论坛 | 博客
  • 博客访问: 196897
  • 博文数量: 26
  • 博客积分: 567
  • 博客等级: 中士
  • 技术积分: 420
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-05 18:48
文章分类

全部博文(26)

文章存档

2011年(26)

分类: C/C++

2011-10-15 18:36:48

即后进先出(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;

       我们需要一个专门指向栈顶的指针(注意不是栈顶指针,而是指向栈顶的指针)。所以我们定义一个结构体TopNodeT.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;

}

 

注意上面列出的只是算法的关键部分,并不完整,删减了一些“栈空”“栈满”的判断。

 

阅读(4262) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~