栈的定义和操作名称
定义
- 栈是限定仅可在表尾进行删除和插入的线性表
- 后进先出形(LIFO)的线性表
基本概念
- 栈顶(top)
- 栈底(bottom)
- 空栈
操作
- 插入
- 删除
栈的ADT
1
2
3
4
5
6
7
8
9
10
11
12
|
Data
同线性表
Operation
IintStack(*S):初始化建立空栈
DestroyStack(*S): 摧毁一个栈
ClearStack(*S):清空栈
StackEmpty(S):栈为空，返回true,否则返回false
GetTop(S,*e):若栈存在且非空，用e返回S的栈顶元素
Push(*S,e):插入
Pop(*S,*e):删除，并用e返回被删除的元素
StackLength:返回栈S的元素个数
endADT
|
栈的顺序存储结构
结构定义
1
2
3
4
5
6
|
typedef int SElemType; //根据实际情况确定栈的元素类型
typedef struct
{
SElemType data[MAXSIZE];
int top;//用于栈顶指针
}SqStack;
|
入栈
1
2
3
4
5
6
7
8
|
Status Push(SqStack *S, SElemType e)
{
if (S->top==MAXSIZE-1)//栈满
return -1;
S->top++;
S->data[S->top]=e;
return 0;
}
|
出栈
1
2
3
4
5
6
7
8
|
Status Pop(SqStack *S, SElemType *e)
{
if (S->top==-1)//空栈
return -1;
*e = S->data[S->top];
S->top--;
return -1;
}
|
两栈共享空间
结构
结构代码
1
2
3
4
5
6
|
typedef struct
{
SElemType data[MAXSIZE];
int top1;
int top2;
}SqDoubleStack
|
操作
1
2
3
4
5
6
7
8
9
10
|
Status Push(SqDoubleStack *S, SElemType e, int StackNumber)
//StackNumber 用来判断插入栈1还是栈2
{
if(S->top1++=S->top2)//栈满
return -1;
if(StackNumber == 1)
S->data[++S->top1]=e;
if(StackNumber == 2)
S->data[--S->top2]=e;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
Status Pop(SqDoubleStack *S, SElemType *e,int StackNumber)
{
if (StackNumber == 1)
{
if (S->top1==-1)//空栈
return -1;
*e = S->data[S->top1];
top1++;
}
if (StackNumber == 2)
{
if (S->top2 == MAXSIZE)//空栈
return -1;
*e = S->data[S->top2];
top2--;
}
return 0;
}
|
栈的链式存储结构
定义
特点
结构代码
1
2
3
4
5
6
7
8
9
10
11
|
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
} StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;
|
操作
进栈
1
2
3
4
5
6
7
8
|
Status Push(LinkStack *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
s->data=e;
s->next=S->top;
S->count++;
return 0;
}
|
出栈
1
2
3
4
5
6
7
8
9
10
11
12
|
Status Pop(LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if (StackEmpty(*S))//空栈
return -1;
*e = S->top->data;
p = S->top;
S->top=S->top->next;
free(p);
S->count--;
return 0;
}
|
栈的应用
递归
斐波那契数列
- 数学定义
$$
F(n)=\begin{cases}0 & n=0 \\ 1 & n=1 \\ F(n-1)+F(n-2) & n \ge 2\end{cases}
$$
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int Fib(int n)
{
if (n == 0)
return 0;
else if (n==1)
return 1;
else
return F(n-1)+F(n-2);
}
int main()
{
int i = 0;
for(i=0;i<40;i++)
{
printf("%d",Fib(n));
}
return 0;
}
|
文字定义
调用自己的函数(包括直接和间接)称作递归函数
四则运算表达式求值
后缀表达式
- 原则
- 例
9 3 1 - 3 * + 10 2 / + = 20
中缀表达式转后缀表达式
-
中缀表达式就是平时用到的表达式
-
转换
队列(FIFO)
定义
只允许在一端插入，另一端删除的线性表
- 队尾
- 队头
ADT
1
2
3
4
|
Data
同线性表，有前驱和后继，元素类型相同
Operation
|
循环队列
定义
队列的头尾相连的顺序存储结构
结构 初始化 长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// 结构定义
typedef int QElemType;
typedef struct
{
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
// 初始化
Status Sqinit(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return 0;
}
// 长度
int QueueLegnth(SqQueue Q)
{
return ((Q.rear - Q.front + MAXSIZE) % MAXSIZE);
}
|
入列和出列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 入列
Status EnQueue(SqQueue *Q,QElemType e)
{
if ((Q->rear + 1) == Q->front)
return -1;
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return 0;
}
// 出列
Status DeQueue(SqQueue *Q, QElemType *e)
{
if (Q->rear == Q->front)
return -1;
*e=Q->data[Q->front];
Q->front = (Q->front + 1)% MAXSIZE;
}
|
队列的链式存储结构
定义
线性表的单链表，称为链队列
结构
1
2
3
4
5
6
7
8
9
10
|
typedef struct Node
{
QElemType data;
struct Node *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear;
}LinkQueue;
|
入列 出列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 入列
Status EnQueue (LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr) malloc (sizeof(Node));
if(!s)
exit(0);
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return 0;
}
// 出列
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
return -1;
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if(Q->rear = p)
Q->rear = Q->free;
free(p);
return 0;
}
|