数据结构（C语言版）之栈及递归_栈和递归

目录

前言

正文

一、栈

1.栈的概念及术语

1.定义

2.逻辑结构

 3.存储结构

4.运算规则

5.实现方式

6.栈是一种特殊的线性表，它的逻辑结构和存储结构与线性表相同，其特殊性体现在“运算受限” 。

2.栈的特点

二、栈的表示及基本操作 

1.顺序栈

顺序栈的类型定义

 说明

顺序栈的算法实现

2.链栈 

链栈的类型定义

 说明

链栈的算法实现

三、栈与递归

递归的定义  

 以下三种情况常常用到递归方法

总结：

---

前言

●数据结构作为计算机专业基础课，综合性强，抽象性高，在一定程度上增加了学习难度，本次我们共同从数据结构的基础探讨，由浅入深进行数据结构的学习。 
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

●本文只浅显的探讨了栈的基本知识，作者相信随着学习课程的深入，我们将会对数据结构有更深的理解与收获！

正文
————————————————

一、栈

1.栈的概念及术语

 

1.定义

只能在表的一端（栈顶）进行插入和删除运算的线性表

2.逻辑结构

 与线性表相同，仍为一对一关系

 3.存储结构

用顺序栈或链栈存储均可，但以顺序栈更常见

4.运算规则

只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则

5.实现方式

关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同 基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

6.栈是一种特殊的线性表，它的逻辑结构和存储结构与线性表相同，其特殊性体现在“运算受限” 。

限制在表的一端进行插入和删除操作。 能够进行操作的一端是浮动端，称之为栈顶，通常用一个“栈顶指针”指示，它的位置会随着操作而发生变化；与此相对，表的另一端是固定端，称之为栈底。 如同线性表可以为空表一样，当栈中没有元素时称为空栈。往栈中插入元素的操作称为入栈，删除栈中元素的操作称栈 。

2.栈的特点

二、栈的表示及基本操作 

1.顺序栈

顺序栈的类型定义

#define MAXSIZE 100
typedef struct
{ 
	DataType data[MAXSIZE];
	int top;
}SqStack;

 

 说明

在顺序栈中，用于指示栈顶的当前位置的top是整型，它的实质是栈顶元素在数组中的下标。 栈顶指针top直接反映出栈的当前状态：空栈时，栈顶指针top为-1；

栈满时，栈顶指针top为MAXSIZE-1；

入栈时，栈顶指针top加1；

出栈时，栈顶指针top减1。

栈底位置固定不变，可以设置在数组的任意端，一般习惯上将数组低下标端作为栈底。

顺序栈的算法实现

 
(1)初始化栈(置栈空) 
初始化栈主要是分配存储空间，并将栈顶指针置为-1。 
int  InitStack(SqStack &S)
{   //构造一个空栈
	S.top= -1;
	return OK;
}
 
(2)判栈空
int  StackEmpty(SqStack S) 
//判栈为空栈时返回值为真，反之为假
{ return(S.top==-1? TRUE:FALSE);} 
 
(3)判栈满
int StackFull(SqStack S)
//判栈为满栈时返回值为真，反之为假
{   return(S.top==MAXSIZE-1?TRUE:FALSE);}
 
(4)进栈
进栈时应首先判栈满，若栈不满则将栈顶指针top上移，存入元素。
int Push(SqStack &S, DataType e)
{ //将元素e插入到栈中，作为的新栈顶
	if(StackFull(S))  return ERROR; //栈满
	S.top++;    // top加1，栈顶位置上移
	S.data[S.top]=e;   //数据e存入当前栈顶
	return  OK;
}
 
(5)出栈
出栈时应首先判断栈是否为空，若栈不为空，则取出栈顶元素，将栈顶指针top下移，再返回栈顶元素。
int Pop(SqStack &S,DataType &e)
{//若栈不为空，则删除栈顶元素
	if(StackEmpty(S)) return ERROR; //栈空
	e=S.data[S.top];   //取出数据放入e所指单元中
	S.top--;     // top减1，栈顶位置下移
	return OK;
}
 
(6)取栈顶元素1
int GetTop(SqStack S,DataType &e)
{//若栈不为空，则取栈顶元素
	if(StackEmpty(S)) return ERROR;  //栈空
	e=S.data[S.top];    //取出数据，top不变
	return OK;
}
 
(6)取栈顶元素2
DataType GetTop(SqStack S)
{//若栈不为空，则取栈顶元素
    DataType e;
	if(StackEmpty(S)) return ERROR;  //栈空
	e=S.data[S.top];    //取出数据，top不变
	return e;
}
 

2.链栈 

链栈的类型定义

链栈：通常用一个无头结点的单链表表示，其结点结构与单链表的结点结构相同。

typedef struct node
{ 
       DataType data;
       struct node* next;
} StackNode,*LinkStack;
LinkStack top;   //top为栈顶指针

 说明

对于单链表来说，在表头插入和删除结点要比在表尾相对简单，因此将单链表表头作为栈顶，则单链表的头指针即为栈顶指针。

 链栈的算法实现

链栈的本质是简化的单链表，top作为栈顶指针始终指向链表首结点。进栈操作就是在链表表头插入一个新的结点，出栈操作就是删除当前的表头结点并释放空间。

(1)初始化栈(置空栈)
LinkStack  InitStack()
//空栈的top指针为NULL
｛  return NULL;   ｝
(2)判栈空
int  StackEmpty(LinkStack top)      
//判栈为空栈时返回值为真，反之为假
{   return(top==NULL? TRUE:FALSE);  }
(3)进栈
void Push(LinkStack top, DataType e)
{   //将元素e进链栈,即在表头插入新的结点
	StackNode  *s;
	s=(StackNode*)malloc(sizeof(StackNode));
	s->data=e;
	s->next=top;
	top=s;
}
(4)出栈
int Pop(LinkStack top,DataType &e)
{   //若栈不为空将栈顶元素出栈，即为删除表头结点
	StackNode *p;
	if(StackEmpty(top)) return  ERROR;  //栈空
	e=top->data;
	p=top;
	top=top->next;
	free(p);
	retrun OK;
}

三、栈与递归

递归的定义  

若一个对象部分地包含它自己,  或用它自己给自己定义,  则称这个对象是递归的；

若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

long Fact ( long n ) {
    if ( n == 0) return 1;
    else return n * Fact (n-1); }

 以下三种情况常常用到递归方法

递归定义的数学函数

具有递归特性的数据结构

可递归求解的问题

 

 

 

 

 

总结：

本文共同探讨了栈的相关内容，在日常生活中有极其丰富的应用，作者认为要认真对待数据结构的学习，搭建基本知识框架，随着日积月累的学习逐渐填补总结，从脚踏实地做起，祝愿大家能够熟悉掌握这门课程，并将其能够熟悉的应用！

耐心看到这里的小伙伴一定很棒！加油！路在脚下，梦在前方！

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！