13518219792
写了一个链式栈，你看看
专注于为中小企业提供网站设计制作、成都网站设计服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业新和免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了1000多家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
# include stdio.h
# include malloc.h
# include stdlib.h
typedef struct Node
{
int data;
struct Node *pNext;
}NODE, *PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;//pBottem是指向栈底下一个没有实际意义的元素
}STACK, *PSTACK;
void init( PSTACK );
void push( PSTACK, int );
void traverse( PSTACK );
int pop( PSTACK, int * );
int empty( PSTACK pS );
int main( void )
{
STACK S;//STACK等价于struct Stack
int val;
init( S );//目的是造出一个空栈
push( S, 1 );//压栈
push( S, 2 );
push( S, 3 );
push( S, 4 );
push( S, 5 );
push( S, 6 );
push( S, 7 );
traverse( S );//遍历输出
// clear( S ); //清空数据
// traverse( S );//遍历输出
if( pop( S, val ) )
{
printf( "出栈成功,出栈的元素是%d\n", val );
}
else
{
printf( "出栈失败" );
}
traverse( S );//遍历输出出栈之后的元素
return 0;
}
void init( PSTACK pS )
{
pS-pTop = ( PNODE )malloc( sizeof( NODE ) );
if( NULL == pS-pTop )
{
printf( "动态内存分配失败!\n" );
exit( -1 );
}
else
{
pS-pBottom = pS-pTop;
pS-pTop-pNext = NULL;//或是pS-pBottom = NULL;
}
}
void push( PSTACK pS, int val )
{
PNODE pNew = ( PNODE )malloc( sizeof( NODE ) );
pNew-data = val;
pNew-pNext = pS-pTop;//pS-Top不能改为pS-pBottom
pS-pTop = pNew;
}
void traverse( PSTACK pS )
{
PNODE p = pS-pTop;
while( p != pS-pBottom )
{
printf( "%d ", p-data );
p = p-pNext;
}
printf( "\n" );
}
int empty( PSTACK pS )
{
if( pS-pTop == pS-pBottom )
return 1;
else
return 0;
}
//把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中,如果出栈失败,则返回false,否则true
int pop( PSTACK pS, int *pVal)
{
if( empty( pS ) )//pS本身存放的就是S的地址
{
return 0;
}
else
{
PNODE r = pS-pTop;
*pVal = r-data;
pS-pTop = r-pNext;
free( r );
r = NULL; //为什么要把r赋给NULL呢??
return 1;
}
}
//clear清空
void clear( PSTACK pS )
{
if( empty( pS ) )
{
return ;
}
else
{
PNODE p = pS-pTop;
PNODE q = p-pNext;
while( p != pS-pBottom )
{
q = p-pNext;
free( p );
p = q;
}
pS-pTop = pS-pBottom;
}
}
栈，是硬件。主要作用表现为一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为先进后出表。 栈可以用来在函数调用的时候存储断点，做递归时要用到栈！ 以上定义是在经典计算机科学中的解释。 在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。 栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息： 1. 函数的返回地址和参数 2. 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。
二、基本算法
1、进栈（PUSH）算法 ①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②置TOP=TOP+1（栈指针加1，指向进栈地址）； ③S(TOP)=X，结束（X为新进栈的元素）； 2、退栈（POP）算法 ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)； ②X=S(TOP)，（退栈后的元素赋给X）： ③TOP=TOP-1，结束（栈指针减1，指向栈顶）。
三、栈的实现
栈分顺序栈和链式栈，下面程序介绍了顺序栈的实现。
#includestdio.h #includemalloc.h #define DataType int #define MAXSIZE 1024 typedef struct { DataType data[MAXSIZE]; int top; }SeqStack; SeqStack *Init_SeqStack()//栈初始化 { SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); if(!s) { printf("空间不足\n"); return NULL; } else { s-top=-1; return s; } } int Empty_SeqStack(SeqStack *s)//判栈空 { if(s-top==-1) return 1; else return 0; } int Push_SeqStack(SeqStack *s,DataType x)//入栈 { if(s-top==MAXSIZE-1) return 0;//栈满不能入栈 else { s-top++; s-data[s-top]=x; return 1; } } int Pop_SeqStack(SeqStack *s,DataType *x)//出栈 { if(Empty_SeqStack(s)) return 0;//栈空不能出栈 else { *x=s-data[s-top]; s-top--; return 1; }//栈顶元素存入*x，返回 } DataType Top_SeqStack(SeqStack *s)//取栈顶元素 { if(Empty_SeqStack(s)) return 0;//栈空 else return s-data[s-top]; } int Print_SeqStack(SeqStack *s) { int i; printf("当前栈中的元素:\n"); for(i=s-top;i=0;i--) printf("%3d",s-data[i]); printf("\n"); return 0; } int main() { SeqStack *L; int n,num,m; int i; L=Init_SeqStack(); printf("初始化完成\n"); printf("栈空：%d\n",Empty_SeqStack(L)); printf("请输入入栈元素个数:\n"); scanf("%d",n); printf("请输入要入栈的%d个元素：\n",n); for(i=0;in;i++) { scanf("%d",num); Push_SeqStack(L,num); } Print_SeqStack(L); printf("栈顶元素:%d\n",Top_SeqStack(L)); printf("请输入要出栈的元素个数（不能超过%d个）:\n",n); scanf("%d",n); printf("依次出栈的%d个元素:\n",n); for(i=0;in;i++) { Pop_SeqStack(L,m); printf("%3d",m); } printf("\n"); Print_SeqStack(L); printf("栈顶元素:%d\n",Top_SeqStack(L)); return 0; }
//顺序栈
#includestdio.h
#includestdlib.h
#includemalloc.h
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
typedef int ElemType;
int InitStack(SqStack S) //为栈S分配存储空间，并置S为空栈
{
int size = STACK_INIT_SIZE;
S.base=(int *)malloc(size*sizeof(ElemType));
if(!S.base)
return 0;
S.top=S.base; //置栈S为空栈
S.stacksize=STACK_INIT_SIZE;
return 1;
}
int GetTop(SqStack S,int e) //若栈不空，则用e返回S的栈顶元素
{
if(S.top==S.base) return 0;
e=*(S.top-1);
return 1;
}
int Push(SqStack S, int e) /*进栈函数,将e插入栈S中,并使之成为栈顶元素*/
{ if(S.top-S.base=S.stacksize) /*栈满，追加存储空间*/
{
int stackinvrement = STACKINCREMENT;
S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));
if(!S.base)
return 0; /*存储分配失败*/
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}
int Pop(SqStack S,int e)/*出栈函数,若栈S不空,则删除S的栈顶元素,用e返回其值*/
{ if(S.top==S.base) return 0;
e=*--S.top;
return 1;
}
void OutputStack(SqStack S)
{int *q;
q=S.top-1;
for(int i=0;iS.top-S.base;i++)
{
printf("%3d ",*q);q--;}
}
void main()
{
int a,b,c ;
char m;
SqStack s;
InitStack(s);
printf("请输入要进栈的元素个数是:");
scanf("%d",a);
printf("\n请输入要进栈的%d个元素:",a);
for(b=0;ba;b++) {
scanf("%d",c);
Push(s,c); }
do { printf("\n");
printf("*********** 1.输出栈的元素**********\n");
printf("*********** 2.取栈顶元素************\n");
printf("*********** 3.删除栈顶元素**********\n");
printf("*********** 4.退出程序**********\n");
printf("\n请选择一个字符:");
getchar();
scanf("%c",m);
switch(m) {
case '1': printf("\n输出的栈为:");
OutputStack(s);
break;
case '2': GetTop(s,c);
printf("\n栈顶元素为:%d",c);
printf("\n输出的栈为:");
OutputStack(s);
break;
case '3': Pop(s,c);
printf("\n删除的栈顶元素:%d",c);
printf("\n输出的栈为:");
OutputStack(s);
printf("\n");
break;
case '4':break;
default: printf("输入的数字有错，请重新选择!\n"); break;
}
}while(m!='4');
}
//链栈
#includestdio.h
#includestdlib.h
typedef struct SNode
{
int data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack top;
LinkStack PushStack(LinkStack top,int x) //入栈
{
LinkStack s;
s=(LinkStack)malloc(sizeof(SNode));
s-data=x;
s-next=top;
top=s;
return top;
}
LinkStack PopStack(LinkStack top) //退栈
{
LinkStack p;
if(top!=NULL)
{
p=top;
top=top-next;
free(p);
printf("退栈已完成\n");
return top;
}
else printf("栈是空的，无法退栈！\n"); return 0;
}
int GetStackTop(LinkStack top) //取栈顶元素
{
return top-data;
}
bool IsEmpty()//bool取值false和true，是0和1的区别,bool只有一个字节,BOOL为int型,bool为布尔型
{
return top==NULL ? true:false;
}
void Print()
{
SNode *p;
p=top;
if(IsEmpty())
{
printf("The stack is empty!\n");
return;
}
while(p)
{
printf("%d ", p-data);
p=p-next;
}
printf("\n");
}
void main()
{
int x,a,b;
char m;
do { printf("\n");
printf("###############链栈的基本操作##################\n");
printf("××××××××1.置空栈××××××××××\n");
printf("××××××××2.进栈×××××××××××\n");
printf("××××××××3.退栈×××××××××××\n");
printf("××××××××4.取栈顶元素××××××××\n");
printf("××××××××5.退出程序×××××××××\n");
printf("##############################################\n");
printf("\n请选择一个字符:");
scanf("%c",m);
switch(m){
case '1':
top=NULL;
printf("\n栈已置空!");
break;
case '2':
printf("\n请输入要进栈的元素个数是:");
scanf("%d",a);
printf("\n请输入要进栈的%d个元素:",a);
for(b=0;ba;b++) {
scanf("%d",x);
top=PushStack(top,x); }
printf("进栈已完成！\n");
printf("\n输出栈为:");
Print();
break;
case '3':
printf("\n操作之前的输出栈为:");
Print();
top=PopStack(top);
printf("\n操作过后的输出栈为:");
Print();
break;
case '4':
printf("\n输出栈为:");
Print();
if(top!=NULL)
printf("\n栈顶元素是：%d\n",GetStackTop(top));
else
printf("\n栈是空的，没有元素！");
break;
case '5':break;
default:
printf("\n输入的字符不对，请重新输入!");
break;
}
getchar();
}while(m!='5');
}
程序的执行过程可看作连续的函数调用。当一个函数执行完毕时，程序要回到调用指令的下一条指令(紧接call指令)处继续执行。函数调用过程通常使用堆栈实现，每个用户态进程对应一个调用栈结构(call stack)。编译器使用堆栈传递函数参数、保存返回地址、临时保存寄存器原有值(即函数调用的上下文)以备恢复以及存储本地局部变量。
不同处理器和编译器的堆栈布局、函数调用方法都可能不同，但堆栈的基本概念是一样的。
寄存器是处理器加工数据或运行程序的重要载体，用于存放程序执行中用到的数据和指令。因此函数调用栈的实现与处理器寄存器组密切相关。
AX(AH、AL)：累加器。有些指令约定以AX(或AL)为源或目的寄存器。输入/输出指令必须通过AX或AL实现，例如：端口地址为43H的内容读入CPU的指令为INAL，43H或INAX，43H。目的操作数只能是AL/AX，而不能是其他的寄存器。 [5]
BX(BH、BL)： 基址寄存器 。BX可用作间接寻址的地址寄存器和 基地址寄存器 ，BH、BL可用作8位通用数据寄存器。 [5]
CX(CH、CL)：计数寄存器。CX在循环和串操作中充当计数器，指令执行后CX内容自动修改，因此称为计数寄存器。 [5]
DX(DH、DL)：数据寄存器。除用作通用寄存器外，在 I/O指令 中可用作端口 地址寄存器 ，乘除指令中用作辅助累加器。 [5]
2.指针和 变址寄存器
BP( Base Pointer Register)：基址指针寄存器。 [5]
SP( Stack Pointer Register)： 堆栈指针寄存器 。 [5]
SI( Source Index Register)：源变址寄存器。 [5]
DI( Destination Index Register)：目的变址寄存器。 [5]
函数调用栈的典型内存布局如下图所示：
图中给出主调函数(caller)和被调函数(callee)的栈帧布局，"m(%ebp)"表示以EBP为基地址、偏移量为m字节的内存空间(中的内容)。该图基于两个假设：第一，函数返回值不是结构体或联合体，否则第一个参数将位于"12(%ebp)" 处；第二，每个参数都是4字节大小(栈的粒度为4字节)。在本文后续章节将就参数的传递和大小问题做进一步的探讨。 此外，函数可以没有参数和局部变量，故图中“Argument(参数)”和“Local Variable(局部变量)”不是函数栈帧结构的必需部分。
其中，主调函数将参数按照调用约定依次入栈(图中为从右到左)，然后将指令指针EIP入栈以保存主调函数的返回地址(下一条待执行指令的地址)。进入被调函数时，被调函数将主调函数的帧基指针EBP入栈，并将主调函数的栈顶指针ESP值赋给被调函数的EBP(作为被调函数的栈底)，接着改变ESP值来为函数局部变量预留空间。此时被调函数帧基指针指向被调函数的栈底。以该地址为基准，向上(栈底方向)可获取主调函数的返回地址、参数值，向下(栈顶方向)能获取被调函数的局部变量值，而该地址处又存放着上一层主调函数的帧基指针值。本级调用结束后，将EBP指针值赋给ESP，使ESP再次指向被调函数栈底以释放局部变量；再将已压栈的主调函数帧基指针弹出到EBP，并弹出返回地址到EIP。ESP继续上移越过参数，最终回到函数调用前的状态，即恢复原来主调函数的栈帧。如此递归便形成函数调用栈。
EBP指针在当前函数运行过程中(未调用其他函数时)保持不变。在函数调用前，ESP指针指向栈顶地址，也是栈底地址。在函数完成现场保护之类的初始化工作后，ESP会始终指向当前函数栈帧的栈顶，此时，若
