算法--栈的应用(数制转换和人工模拟栈代替系统栈)

1、数制转换


实现十进制N转其他d进制数,简单的算法基于:

1
N = (N div d) x d + N mod d   //其中div:整除运算,mod:取余运算

例如:(1348)10 = (2504)8

N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
1
2
3
4
5
6
7
8
9
10
11
12
13
/*  输入任意的一个非负的十进制整数,输出其对应的八进制数*/
void conversion(){
InitStack(S); //初始化一个栈S
scanf("%d",N);
while(N){
Push(S, N % 8);
N = N / 8;
}
while(){
Pop(S,e);
printf("%d",e);
}
}

图示:

Alt text


2、人工模拟栈代替系统栈

2.1什么是系统栈?

说起系统栈,不得不提一下在操作系统中内存的用途,不管什么操作系统,进程调用的内存一般分成四个部分:

1
2
3
4
代码区:存储被装入执行的二进制机器代码,处理器到这个区域读取指令
数据区:存储全局变量
堆区: 进程可以在堆区动态申请一部分内存,用完之后归还给堆区。动态分配和回收是堆区的特定。
栈区:用于动态的存储函数之间的调用关系。保证调用函数返回时恢复到母函数中继续执行。

这里的栈区就是指的系统栈。系统栈对于高级编程语言是透明的,它主要实现高级语言中的函数调用。如果你还没明白,不要紧。现在以这个C语言的例子来简单说一下系统栈的作用。

1
2
3
4
5
6
7
8
9
10
# include<stdio.h>
int func_a()
{
//return
}
int main()
{
int var_num = 0;
func_a();
return 0;

  当CPU执行func_a函数的时候,需要在main函数中的代码区找到跳转到func_a函数的机器指令,取指并执行后,func_a函数执行完毕之后,它是怎么返回到main函数中的呢?
  这些函数之间的跳转都是通过系统栈的配合来完成的,当函数被调用时,系统栈会为这个函数开辟一个新的栈帧,并压入系统栈中,当函数返回时系统栈会弹出该函数对应的栈帧。

2.2 人工模拟栈

1
2
3
4
5
6
7
8
int func(int n)
{
if (n <= 1)
{
return 1;
}
return n * func(n -1);
}

  这个递归的例子,函数不断的递归,需要不断的调用系统栈。 下面来实现人工模拟系统栈实现这个递归函数的运行过程。

1
2
3
4
5
6
7
8
9
10
11
12
do{
if(! back) {
if(n <= 1) {
back = ture, ret = 1; //判断是不是该返回了
continue;
}
n进栈; //将n的值存到栈中
--n;
}else{
ret *= 出栈; //这里是栈返回的时候执行的。
}
}while(栈不为空)

参考资料

栈:
  严, 蔚敏, 吴, 伟民. 数据结构(C语言版)[J]. 计算机教育, 2012, No.168(12):62-62.
系统栈:
  佚名. 0day安全:软件漏洞分析技术(第2版)[J]. 信息安全与通信保密, 2013(11).