 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》栈【讲解】 |
|
1.栈的概述：
学了线性表后我们知道，可以在表的任意位置插入一个元素，也可以删除任意一个元素。如果我们把线性表的操作限制一下，插入操作只能插在表的最后，删除操作也只能删除表的最后一个元素。具备这种特殊性质的线性表，我们称它为栈(stack)。在栈中，指向第一个元素的指针我们称做栈底(base)，指向最后一个元素的指针我们称做栈顶(top)。当栈底和栈顶都指向第一个元素时，我们称此时的栈为空栈。对于栈的操作，我们把向栈顶插入元素的操作叫做入栈(push stack)，从栈顶删除元素的操作叫做出栈(pop stack)。 既然栈是线性表，那么栈的存储方式和线性表一样分为顺序存储和链式存储两种。下面我们结合栈的具体操作分别对这两种存储方式进行一下介绍。 顺序存储的栈和顺序的线性表一样在物理和逻辑上都是连续的，入栈操作首先将要插入的数据(insert_data)放到栈顶所指的空间中，然后将栈顶指针向后移动一个数据类型占的空间(elemtype_length)即可。可表示如下： *s->top=insert_data; s->top+=elemtype_length; 出栈操作正好相反，首先得到栈顶元素的值(栈顶数据由变量temp保存)，然后将栈顶指针向前移动一个数据类型占的空间即可。可表示如下： temp=*s->top; s->top-=elemtype_length; 链式存储栈的数据结构是由数据域(data)和指向前驱结点的指针域(next)组成。对于链式的入栈操作，我们首先申请一个栈结点空间并用辅助指针(p)指向此结点，将要插入的数据放入此结点的数据域中，然后将新结点的前驱结点指针域指向栈顶，最后用新结点的地址修改栈顶指针。入栈操作完毕。可表示如下： p->data=insert_data; p->next=s->top; s->top=p; 出栈操作过程，首先得到栈顶元素的值(栈顶数据由变量temp保存)，然后将当前结点前驱结点指针域修改栈顶指针即可。可表示如下： temp=*s->top; s->top=p->next; 因为栈的操作都是对栈顶进行操作，位置是固定的，不需要进行查找操作，所以栈的时间复杂度和空间复杂度都为O(1)。 栈除了入栈和出栈操作外，还有一些其它基本操作，如初始化栈、获得栈顶元素的值、获得栈的长度、清空栈、销毁栈等，读者可自行练习。 2. 栈的练习任务： 因为栈的特殊性，栈有它自己的应用方面，如数制转换、括号匹配的检验、行编辑器的实现、迷宫求解、表达式求值等等。读者可以根据自己的兴趣自行练习一下，巩固对栈的掌握。 [07/09/25] |