目的
这一系列博客的目的在于复习巩固数据结构的基础知识，为考研面试笔试做准备，所以重在原理，代码实践不是重点。 参考书籍有严蔚敏老师的《数据结构（C语言版）》，《C/C++数据结构与算法速学速用大辞典》
栈
顺序栈 在pop，push时，注意： 因为数据实际上是存储在DataType stack数组中，下标从0开始，所以top=0表示空栈，top=i表示栈顶元素存储在stack[i-1]中。
#define StackSize 100
typedef int DataType;
typedef struct{
DataType
stack[StackSize];
int top;
}SeqStack;
void InitStack(SeqStack *s)
{
s->top =
0;
}
int PushStack(SeqStack *s, DataType e)
{
if(s->top >= StackSize)
{
printf(
"stack is full!\n");
return 0;
}
else
{
s->
stack[s->top] = e;
s->top ++;
return 1;
}
}
int PopStack(SeqStack *s, DataType *e)
{
if(s->top ==
0)
{
printf(
"stack is empty!\n");
return 0;
}
else
{
s->top --;
*e = s->
stack[s->top];
return 1;
}
}
链式栈 为降低插入删除的时间复杂度，链式栈插入删除都在栈顶指针的位置进行。
typedef DataType
int;
typedef struct node
{
DataType data;
struct node
*next;
}LStackNode,
*LinkStack;
void InitStack(LinkStack
*top)
{
if((
*top=(LinkStack)malloc(sizeof(LStackNode))) == NULL)
exit(-
1);
*top->
next = NULL;
}
int StackEmpty(LinkStack top)
{
if(top->
next == NULL)
return 1;
else
return 0;
}
int PushStack(LinkStack top, DataType e)
{
LStackNode
*p;
if((p=(LStackNode
*)malloc(sizeof(LStackNode))) == NULL)
{
printf(
"内存分配失败\n");
exit(-
1);
}
p->data = e;
p->
next = top->
next;
top->
next = p;
return 1;
}
共享栈
表达式求值
