影响网站排名的因素 权重,鹤壁网站建设优化,留学生做留服证明在哪个网站,拉新平台目录 1. 前言2. 结构及基本操作函数#xff1a;2.1 栈的结构类型 Stack2.2 初始化栈 InitStack2.3 销毁栈 DestroyStack2.4 清空栈 ClearStack2.5 判断栈是否为空 StackEmpty2.6 获取stack的长度 StackLength2.7 获取栈顶元素 GetTop2.8 入栈 Push2.9 出栈 Pop2.10 访问元素2.… 目录 1. 前言2. 结构及基本操作函数2.1 栈的结构类型 Stack2.2 初始化栈 InitStack2.3 销毁栈 DestroyStack2.4 清空栈 ClearStack2.5 判断栈是否为空 StackEmpty2.6 获取stack的长度 StackLength2.7 获取栈顶元素 GetTop2.8 入栈 Push2.9 出栈 Pop2.10 访问元素2.11 遍历栈的所有元素 3. 严蔚敏版完整测试代码:3.1 代码3.2 运行结果: 4. 简易版完整测试代码4.1 完整代码4.2 运行结果 5. 栈的应用 进制转化5.1 转化函数5.2 进制转化完整代码5.3 运行结果 1. 前言
栈的操作思想先进后出 本文的基本操作函数使用 严蔚敏版的《数据结构与算法》中的实现方式。此方式可以实现动态的分配栈空间内存。 本文还有一个更为简单的栈操作方式虽简单但是就失去了动态分配栈空间内存的优势。栈空间的最大值会被限制。 对比之下严教授的编程思想还是比一般人厉害。
入栈和出栈的示意图 2. 结构及基本操作函数
2.1 栈的结构类型 Stack
typedef struct Stack{SElemType * base; //栈底指针SElemType * top; //栈顶指针int stacksize; //当前已分配的存储空间
} SqStack;2.2 初始化栈 InitStack
功能 初始化栈 分配栈底内存空间栈空间大小设置初始值
/*初始化栈*/
Status InitStack(SqStack * stack)
{stack-base (SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-topstack-base; // 栈顶指针初始 指向栈底;stack-stacksizeSTACK_INIT_SIZE;return TRUE;
}2.3 销毁栈 DestroyStack
功能销毁栈释放内存空间
/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack-base);stack-topstack-baseNULL;stack-stacksize0;return TRUE;
}2.4 清空栈 ClearStack
功能 清空栈内数据区别于销毁栈的释放内存。只需要将栈顶指针等于栈底指针
/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack-topstack-base;return TRUE;
}2.5 判断栈是否为空 StackEmpty
功能 判断栈是否为空在实际应用中这个函数经常要用到
/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base stack.top)return TRUE;else return FALSE;
}2.6 获取stack的长度 StackLength
/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}2.7 获取栈顶元素 GetTop
功能 获取栈顶元素并将值传递给 e注意区别于下面的pop函数,GetTop是不改变栈的元素。
/* 获取栈顶元素并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e *--stack.top;
}2.8 入栈 Push
功能 入栈, 将元素e压入栈中。这里面就涉及到一个扩容问题如果栈的空间不够可以增加栈的内存空间。
/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack-top - stack-base stack-stacksize)//如果空间不够的话扩容{stack-base (SElemType *) realloc(stack-base,(stack-stacksizeSTACKINCREMENT)* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-stacksize STACKINCREMENT;}*stack-top e;return TRUE;
}示意图 :
2.9 出栈 Pop
/*出栈 从栈顶弹出元素并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)
{if(!stack-base)return FALSE;if(stack-base stack-top) //空栈return FALSE;*e *(--stack-top);return TRUE;
}示意图
以上的函数在各类实际应用中基本都不用修改可以直接使用。下面还有两个函数栈元素的访问一般在实际应用中根据需要自行的灵活修改。
2.10 访问元素
功能 访问元素因为是测试用的所以打印就行了
/* 访问元素 */
void Visit(SElemType e)
{printf(%d\t, e);
}2.11 遍历栈的所有元素
功能遍历stack,对stack的每一个元素调用visit函数。
/* 遍历stack,对stack的每一个元素调用visit函数 */
Status StackTraverse(SqStack stack,void (*visit)(SElemType e))
{SElemType * curElemstack.base;if(StackEmpty(stack))return FALSE;while(curElem!stack.top)visit(*curElem);return TRUE;
}3. 严蔚敏版完整测试代码:
3.1 代码
/*此版本为严蔚敏老师版本此版本栈的空间大小可以*/#include stdio.h
#include stdlib.h#define STACK_INIT_SIZE 100 //初始内存空间
#define STACKINCREMENT 10 // 内存空间增量#define TRUE 1
#define FALSE 0typedef int SElemType;typedef struct Stack{SElemType *base; //栈底指针SElemType * top; //栈顶指针int stacksize; //当前已分配的存储空间
} SqStack;typedef int Status;Status InitStack(SqStack * stack);
Status DestroyStack(SqStack * stack);
Status ClearStack(SqStack * stack);
Status StackEmpty(SqStack stack);
int StackLength(SqStack stack);
Status GetTop(SqStack stack, SElemType * e);
Status Push(SqStack * stack,SElemType e);
Status Pop(SqStack * stack, SElemType *e);
void Visit(SElemType e);
Status StackTraverse(SqStack stack,void (*visit)(SElemType));/*初始化栈*/
Status InitStack(SqStack * stack)
{stack-base (SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-topstack-base; // 栈顶指针初始 指向栈底;stack-stacksizeSTACK_INIT_SIZE;return TRUE;
}/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack-base);stack-topstack-baseNULL;stack-stacksize0;return TRUE;
}
/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack-topstack-base;return TRUE;
}/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base stack.top)return TRUE;else return FALSE;
}/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}/* 获取栈顶元素并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e *--stack.top;
}/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack-top - stack-base stack-stacksize)//如果空间不够的话扩容{stack-base (SElemType *) realloc(stack-base,(stack-stacksizeSTACKINCREMENT)* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-stacksize STACKINCREMENT;}*stack-top e;return TRUE;
}
/*出栈 从栈顶弹出元素并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)
{if(!stack-base)return FALSE;if(stack-base stack-top) //空栈return FALSE;*e *(--stack-top);return TRUE;
}/* 访问元素 */
void Visit(SElemType e)
{printf(%d\t, e);
}/* 遍历stack,对stack的每一个元素调用visit函数 */
Status StackTraverse(SqStack stack,void (*visit)(SElemType e))
{SElemType * curElemstack.base;if(StackEmpty(stack))return FALSE;while(curElem!stack.top)visit(*curElem);return TRUE;}int main()
{SqStack stack;SElemType elem;InitStack(stack);printf(压入数字1、2、3\n);Push(stack,1);Push(stack,2);Push(stack,3);printf(当前栈的容量:%d\n,StackLength(stack));GetTop(stack,elem);printf(栈顶元素为:%d\n,elem);printf(将4、5压入栈中\n);Push(stack,4);Push(stack,5);Pop(stack,elem);printf(弹出栈顶元素为:%d\n,elem);printf(当前栈的容量:%d\n,StackLength(stack));printf(遍历栈:);StackTraverse(stack,Visit);printf(\n);DestroyStack(stack);getchar();return 0;
}3.2 运行结果: 4. 简易版完整测试代码
简易版无法动态的给栈扩容
4.1 完整代码
/*此版本为简易版本*/#include stdio.h
#include stdlib.h#define TRUE 1
#define FALSE 0
#define MAXSIZE 30typedef int Status;typedef int ElemType; //定义元素类型为整型
typedef struct{ElemType * base; //在栈构造之前和销毁之后base的值均为NULLint top;
}SqStack;/*初始化栈为栈分配空间*/
Status InitStack(SqStack * stack)
{stack-base(ElemType*) malloc(sizeof(ElemType)*MAXSIZE);if(stack-baseNULL)return FALSE;stack-top -1; //初始值可以是-1,也可以设置为0。//如果设置为-1那么当栈不为空时 栈顶元素为 stack-base[top]//如果设置为0 那么当栈不为空时 栈顶元素为 stack-base[top-1]return TRUE;
}/*销毁栈释放栈的数据空间*/
void DestroyStack(SqStack *stack)
{free(stack-base);stack-baseNULL;stack-top -1;
}/* 获取栈顶元素 */
Status GetTop(SqStack stack, ElemType * elem)
{if(stack.top0)return FALSE;*elemstack.base[stack.top];return TRUE;
}/* 压栈将元素elem 插入栈顶 */
Status Push(SqStack * stack,ElemType elem)
{if(stack-top MAXSIZE-1) /*栈已经满了实际应用中可以动态扩展栈的空间*/return FALSE;stack-base[stack-top]elem;return TRUE;
}/*出栈将栈顶元素elem出栈相当于删除栈顶元素 */
Status Pop(SqStack * stack,ElemType * elem)
{if(stack-top0)return FALSE;*elemstack-base[stack-top--];return TRUE;
}int main ()
{SqStack stack;ElemType * elem(ElemType*)malloc(sizeof(ElemType));InitStack(stack);printf(压入数字1、2、3\n);Push(stack,1);Push(stack,2);Push(stack,3);printf(当前栈的容量:%d\n,stack.top1);GetTop(stack,elem);printf(栈顶元素为:%d\n,*elem);printf(将4、5压入栈中\n);Push(stack,4);Push(stack,5);Pop(stack,elem);printf(弹出栈顶元素为:%d\n,*elem);printf(当前栈的容量:%d\n,stack.top1);printf(\n);DestroyStack(stack);free(elem);getchar();return 0;
}4.2 运行结果 5. 栈的应用 进制转化
5.1 转化函数
此函数是将10进制的数据 转化为2进制或者8进制 。/* 十进制制转换成8进制或2进制* 参数radix 进制数如果要转换成2进制则输入2如果转换成8进制则radix8* 参数n 待转换的十进制数 */
void conversion(int radix,int n)
{SqStack stack;int elem;InitStack(stack);while(n){Push(stack,n%radix); // 将余数入栈nn/radix; // 商做为被除数进行下一个循环只要商不为0就继续除下去)}while(!StackEmpty(stack)){ //从栈中将余数依次取出。Pop(stack ,elem);printf(%d,elem);}printf(\n);
}5.2 进制转化完整代码
#include stdio.h
#include stdlib.h#define STACK_INIT_SIZE 100 //初始内存空间
#define STACKINCREMENT 10 // 内存空间增量#define TRUE 1
#define FALSE 0typedef int Status;typedef int SElemType;typedef struct Stack{SElemType *base; //栈底指针SElemType * top; //栈顶指针int stacksize; //当前已分配的存储空间
} SqStack;Status InitStack(SqStack * stack);
Status DestroyStack(SqStack * stack);
Status ClearStack(SqStack * stack);
Status StackEmpty(SqStack stack);
int StackLength(SqStack stack);
Status GetTop(SqStack stack, SElemType * e);
Status Push(SqStack * stack,SElemType e);
Status Pop(SqStack * stack, SElemType *e);
void Visit(SElemType e);
Status StackTraverse(SqStack stack,void (*visit)(SElemType));/*初始化栈*/
Status InitStack(SqStack * stack)
{stack-base (SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-topstack-base; // 栈顶指针初始 指向栈底;stack-stacksizeSTACK_INIT_SIZE;return TRUE;
}/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack-base);stack-topstack-baseNULL;stack-stacksize0;return TRUE;
}
/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack-topstack-base;return TRUE;
}/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base stack.top)return TRUE;else return FALSE;
}/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}/* 获取栈顶元素并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e *--stack.top;
}/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack-top - stack-base stack-stacksize)//如果空间不够的话扩容{stack-base (SElemType *) realloc(stack-base,(stack-stacksizeSTACKINCREMENT)* sizeof(SElemType));if(!stack-base)exit(EXIT_FAILURE);stack-stacksize STACKINCREMENT;}*stack-top e;return TRUE;
}
/*出栈 从栈顶弹出元素并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)
{if(!stack-base)return FALSE;if(stack-base stack-top) //空栈return FALSE;*e *(--stack-top);return TRUE;
}/* 十进制制转换成8进制或2进制* 参数radix 进制数如果要转换成2进制则输入2如果转换成8进制则radix8* 参数n 待转换的十进制数 */
void conversion(int radix,int n)
{SqStack stack;int elem;InitStack(stack);while(n){Push(stack,n%radix); // 将余数入栈nn/radix; // 商做为被除数进行下一个循环只要商不为0就继续除下去)}while(!StackEmpty(stack)){Pop(stack ,elem);printf(%d,elem);}printf(\n);}int main ()
{printf(将4转换为2进制);conversion(2,4);printf(将20转换为8进制);conversion(8,20);getchar();return 0;
}
5.3 运行结果
