Question

用C语言实现栈的操作，包括创建空栈，PUSH，和POP。用标准C，就是能在TC上运行的。

发现那本严蔚敏的东西里面的算法都是不能实现的，我初学数据结构，希望能看到个能运行的例子，请高手指教！
忘了说了，是顺序栈，要配合严蔚敏那本数据结构里对栈的描述。
谢谢ICE，和无中生有何时明。不过无中生有你给的算法在TC里通不过，就是那个&，例如int InitStack(SqStack &S);里面的&S，C语言里面是不能这么写的吧，不要再用这种伪码，我就是给这些伪码搞的很晕~

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

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

int InitStack(SqStack &S);
int Push(SqStack &S, SElemtype e);
int GetTop(SqStack S, SElemtype &e);
int Pop(SqStack &S, SElemtype &e);

int main()
{
SElemtype e, f = 0, g = 0;
int c;

SqStack S;
if (!InitStack(S))
return 0;

printf("栈已初始化好,输入一个数据入栈.\n");
scanf("%c", &e);
if (!Push(S, e))
return 0;

if (!GetTop(S, f))
return 0;
printf("栈顶元素是:%c\n", f);

if (!Pop(S, g))
return 0;
printf("栈顶元素出栈,它是:%c\n", g);

scanf("%d", &c);
return 1;
}

int InitStack(SqStack &S)
{
S.base = (SElemtype *)malloc(STACK_INIT_SIZE * sizeof (SElemtype));
if (!S.base)
return 0;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
}

int Push(SqStack &S, SElemtype e)
{
if (S.top - S.base == S.stacksize)
{
S.base = (SElemtype *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemtype));
if (!S.base)
return 0;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return 1;
}

int GetTop(SqStack S, SElemtype &e)
{
if (S.top == S.base)
return 0;
e = *(S.top - 1);
return 1;
}

int Pop(SqStack &S, SElemtype &e)
{
if (S.top == S.base)
return 0;
e = *--S.top;
return 1;
}

我学这本书时写的，刚好给你。

针对补充问题：
&不是伪代码，是C++的传引用，你看的那本书上都是这样用的。
楼上的顺序栈实质就是一个数组。。
TC不能建C++项目吗？ 不能的话你还是装个VC吧，你若听了老师的话就应该知道在这里传引用是什么意思，且看下面：
int InitStack(SqStack &S);
int Push(SqStack &S, SElemtype e);
int GetTop(SqStack S, SElemtype &e);
int Pop(SqStack &S, SElemtype &e);
有没有发现GetTop()的参数没有使用&S,因为它对S只读，不改变S。
如果不使用传引用的话，那么InitStack(),Push()等将要返回一个S,若要保存还要把它赋给另一个SqStack类型的变量S1，这样做浪费时间还浪费空间，且之前的S也就没用了，如果反复地调用Push()的话，这样的浪费可想而知。
所以，为了节省时间跟空间，以及按大多数情况下的需要，我们还是得始终只用一个S保存我们要的数据。
至于传引用是什么意思，跟指针有点像，你若不想翻书就再补充问题吧。。

Answer 2

顺序栈:
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX 100
typedef int DT;

typedef struct{
int size;
int top;
DT data[STACK_MAX];
} stack;
void init(stack *st) /*初始化顺序栈*/
{
st->size=0;
st->top=-1;
}

DT pop(stack *a) /*出栈*/
{
if (a->size==0) {
fprintf(stderr,"STACK IS EMPTY");
exit(-1);
}
a->size--;
return a->data[a->top--];
}

void push(stack *a,DT tdata) /*入栈*/
{
if (a->size==STACK_MAX) {
fprintf(stderr,"STACK IS FULL");
exit(1);
}
a->size++;
a->data[++(a->top)]=tdata;
}
int main(void) /*试验*/
{
stack st;
init(&st);
push(&st,5);
push(&st,6);
printf("%d",pop(&st));
return 0;
}
//---------------------------------------------------------------------------

链栈:
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
typedef int DT;
typedef struct node{
DT data;
struct node *next;
} node;
typedef struct{
unsigned int cnt;
node *top;
} stack;

stack *create(void) /*创建空栈*/
{
stack *rt=(stack*)malloc(sizeof(stack));
rt->cnt=0;
rt->top=NULL;
return rt;
}

DT pop(stack *s) /*出栈*/
{
node *dl=s->top;
DT rt;
if (dl==NULL) {
fprintf(stderr,"ERROR! STACK IS EMPTY\n");
exit(-1);
}
s->top=dl->next;
s->cnt--;
rt=dl->data;
free(dl);
return rt;
}

void push(stack *s,DT tdata) /*入栈*/
{
node *td=(node *)malloc(sizeof(node));
td->data=tdata;
td->next=s->top;
s->top=td;
s->cnt++;
}

int main(void) /*试验*/
{
stack *st=create();
push(st,5);
push(st,6);
printf("%d",pop(st));
return 0;
}
//---------------------------------------------------------------------------

Answer 3

#define MAX_SIZE 100
typedef struct
{
int position;
int buf[MAX_SIZE];
}Stack,*pStack;
pStack CreateStack()
{
pStack pst;
pst = (pStack)malloc(sizeof(Stack));
return pst;
}
void FreeStack(pStack pst)
{
free(pst);
}
void InitStack(pStack pst)
{
pst->position = 0;
return;
}
bool Push(pStack pst,int par)
{
int tmp = pst->position;
if(tmp < MAX_SIZE)
{
pst->buf[tmp] = par;
pst->position++;
return true;
}
return false;
}
bool Pop(pStack pst,int * par)
{
int tmp = pst->position;
if(tmp>0)
{
pst->position--;
*par = pst->buf[tmp-1];
return true;
}
return false;
}
void main()
{
pStack p_mystack = NULL;
int num;
p_mystack = CreateStack();
if(p_mystack != NULL)
{
InitStack(p_mystack);
Push(p_mystack,1);
Push(p_mystack,2);
Push(p_mystack,3);
Push(p_mystack,4);
Push(p_mystack,5);
Pop(p_mystack,&num);
printf("%d ",num);
Pop(p_mystack,&num);
printf("%d ",num);
Pop(p_mystack,&num);
printf("%d ",num);
Pop(p_mystack,&num);
printf("%d ",num);
Pop(p_mystack,&num);
printf("%d ",num);
FreeStack(p_mystack);
}
}

Answer 4

...中国出的这些书太应试化了,如果真心想学买一本机械工业出版社的数据结构(C语言版)写的很好,算法都是有C描述的包括你需要的东西...我懒得打那么长的算法程序了...

Answer 5

我也正在学，三楼的专业可用，其它两位的实质就是个数组。