关于栈的Top操作的问题 c语言实现 链表实现 数据结构

问题描述:

头文件
struct Node{
int data;
struct Node *Next;
};
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
void MakeEmpty(Stack S);
Stack CreateStack(void);
void Push(int X,Stack S);
int Top(Stack S);
void Pop(Stack S);

#include
#include "stack.h"
#include

int IsEmpty(Stack S)
{
return S->Next == NULL;
}

void MakeEmpty(Stack S)
{
if(S == NULL)
printf("must");
else
while(!IsEmpty(S))
Pop(S);
}

Stack CreateStack(void)
{
Stack S;

S = malloc(sizeof(struct Node));
if(S == NULL)
    printf("Out of range");
S->Next = NULL;
MakeEmpty(S);
return S;

}

void Push(int X,Stack S)
{
PtrToNode TmpCell;

TmpCell = malloc(sizeof(struct Node));
if(TmpCell == NULL)
    printf("Out of range");
else
{
   TmpCell->data = X;
   TmpCell->Next = S->Next;
   S->Next = TmpCell;

}

}

int Top(Stack S)
{
if(!IsEmpty(S))
return S->Next->data;
printf("Out of range");
return 0;
}

void Pop(Stack S)
{
PtrToNode FirstCell;

if(IsEmpty(S))
    printf("Out of range");
else
{
    FirstCell = S->Next;
    S->Next = S->Next->Next;
    free(FirstCell);

}

}

这个基本上是照书一点一点打的,我不太懂关于Top操作
为什么知道了指向栈底部的指针S就可以用
S->Next->data 得知栈顶元素,这个我自己实验过是对的。
因为假如这个栈是由3个链表连起来的,S->Next->data应该得到的是第二个链表里面的元素啊。
S->Next->Next->data才是栈顶的元素。
我也曾怀疑过是不是Push操作改变了指针S指向的地方。。但打印出的S的地址都是一样啊。
顺便可以问一下,假如我要打印某个地址 是应该 用 %d 吗,我的文本编辑器总报warning。。
提一下我的文本编辑器是geany 编译器是gcc Linux下
我是小白。。求指教啊啊啊啊。。google后也不明白。。卡了好几天了
希望有人可以帮我一下..

S不是栈顶,S是栈顶的上面,S->Next指向的才是栈顶,你画个图就知道了,不要把S当做一个节点,S是个指针,不是一个节点,
是个Next指向栈顶的节点指针,S里面的data没用,就那个Next有用
所以S-Next->data是栈顶元素
push是在栈顶上面加的,所以,push实际上是加载了S和旧的栈顶之间,形成了新的栈顶

打印地址 int 类型,%d可以。

按你给出的堆栈的实现有些小问题:
1. Stack的定义是一个指向堆栈元素的指针,那定义一个这么样的指针变量或是分配一个能够保存指针变量的空间就可以作为栈顶指针用了,但偏偏在实现中直接将其当做一个栈中的元素来使用
2. 由于第一点的设计,所以在后面的所有实现中相当于把S指向的那个元素当做了一个哑元素,用一个哑元素来做栈顶表示,浪费了空间
3. 在32位系统中打印指针用“%d”没什么大的问题,但现在普遍都是64位系统,“%d”决不能用来打印指针,即使很多时候你看着好像没区别,当当遇到高位地址时就不能打印正确的地址。