第3章 简单数据结构.pptVIP

链栈的基本概念利用链式存储结构实现的栈称作链栈（linkstack）。链栈中的每个数据元素用一个结点表示，其结构形式与单链表完全相同。链栈从本质上讲就是单链表，无非是限制了插入和删除运算只能在链头进行，所以可以说链栈就是限制插入和删除运算只能在链头进行的单链表。由于在链头运算，所以不用象单链表那样附加头结点，更方便运算，如右图所示。第94页，共175页，星期日，2025年，2月5日链栈的类型定义链栈的类型定义如下：typedefstructnode{elemtypedata;structnode*next;}linkstack;linkstack*top;/*栈顶指针，即链头指针*/第95页，共175页，星期日，2025年，2月5日链栈的基本运算——空栈操作置空栈算法voidsetnull(linkstack*top){top=NULL;}/*只要置top为空即可*/判栈空算法intempty(linkstack*top)/*栈空返回1否则返回0*/{if(top==NULL)return1;elsereturn0;}第96页，共175页，星期日，2025年，2月5日链栈的基本运算——进栈进栈算法voidpush(linkstack*top,elemtypex)/*注意：链栈不会发生上溢！*/{linkstack*p;p=(linkstack*)malloc(sizeof(linkstack));p-data=x;p-next=top;top=p;}第97页，共175页，星期日，2025年，2月5日链栈的基本运算——出栈出栈算法elemtypepop(linkstack*top){linkstack*p;elemtypex;if(top==NULL)returnNULL;/*栈为空无元素弹出*/else{p=top;/*保存栈顶指针于P中*/x=top-data;top=top-next;free(p);returnx;/*返回弹出元素的值*/}}第98页，共175页，星期日，2025年，2月5日链栈的基本运算——读栈顶元素读栈顶元素算法elemtypegettop(linkstack*top){if(top==NULL)returnNULL;/*若栈为空返回空*/elsereturntop-data;/*否则返回栈顶元素的值*/}第99页，共175页，星期日，2025年，2月5日3.3栈3.3.1栈的概念及运算3.3.2顺序栈及运算实现3.3.3链栈及运算实现3.3.4栈的应用举例——递归的实现第100页，共175页，星期日，2025年，2月5日栈的应用栈在计算机学科有着许多重要的应用。例如：把十进制整数转换为二进制整数的方法是“除2取余，逆序排列”，利用栈来记下每次余数最后输出栈中内容即可；在语言翻译中要把十进制表达式的中缀形式先转换成后缀形式，然后把后缀表达式翻译成为一条条运算指令，在后续课程《编译原理》中大家会看到都得使用栈结构来完成；在算法设计中的需要回溯处理的问题如迷宫问题、二叉树的遍历、图的遍历等非递归算法的设计需要借助栈来完成，把递归过程转换为非递归过程也需要借助栈结构；还有语言翻译中的函数调用，过程调用，递归子程序处理等等都离不开栈的应用。第101页，共175页，星期日，2025年，2月5日栈的应用举例——递归的实现递归是算法和程序设计中的一个重要概念，也是算法和程序设计的一种重要方法和手段。在高级程序设计语言中有过程、函数和子程序等程序模块的概念，这些程序模块是架构结构化程序的基本单位。当这些模块直接或间接地在程序中调用了自身，就称作递归程序模块；直接调用自身的称为直接递归，间接调用自身的称为间接递归。递归的概念对于程序模块而存在，即递归过程、递归函数、递归子程序等，其前提是问题定义的递归特性和数据结构的递归特性。而问题定义的递归特性主要靠我们在对求解问题本身的分析和理解的过程中去发现。第102页，共175页，星期日，2025年，2月5日栈的应用举例—递归的实现(续)在C语言中，当一个函数体内出现了自身的函数名（即直接调用自身），就称该函数为直接递归函数；