首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 编程技术
    3. 发新帖
[原创]C语言学习总结之自定义栈模拟函数调用
发表于: 2012-11-8 00:41 5078

[原创]C语言学习总结之自定义栈模拟函数调用

taohongtao 活跃值
2012-11-8 00:41
5078
/*================================StackTest.c===============================*/
/******************************************************************************
*这个例子揭示了函数调用的原理，包括
*1.如何实现一个我们自己的栈
*2.如何通过栈传递参数
*3.如何调用函数
*4.如何从栈里取得函数的参数
*5.如何在栈里为函数定义局部变量
*6.如何取得函数的返回值
*7.如何返回函数
********************************************************************************
*除了系统函数printf之外，所有其他函数的调用和返回都是我们自己实现的
*除了系统函数printf之外，所有的参数都是在我们自己的栈中进行传递的
*除了系统函数printf和main之外，所有的局部变量都是在我们自己的栈中定义的
*为了不影响对本例子的理解，main函数的局部变量没有定义在我们自己的栈中
*在看本例子时，应注意栈的变化
********************************************************************************/

#include <stdio.h>
#include "stack.h"//我们自己实现的一个栈的头文件，里面有很多我们需要用到的宏

int main(char *argc[],int argv)
{
  
  char *str1="taohongtao";
  char *str2="hongtaotao";
  int ret;

  PUSH(str2);//将参数str2压入我们自己的栈
  PUSH(str1);//将参数str1压入我们自己的栈  
  CALL(self_strcmp,main_label1);//调用函数self_strcmp
main_label1://调用self_strcmp函数完成后应该返回到这里
  ret=GET_RET();//取得函数返回值
  printf("the result of self_strcmp(%s,%s) is:%d\n",str1,str2,ret);//输出函数执行的结果

  /********************************************************************
  *在调用self_strcmp函数的过程中，栈的情况如下：
  *
  *    # # # # # # # # # # # # # # # # # # # #
  *    # 局部变量(1)       i               #
  *    # # # # # # # # # # # # # # # # # # # #
  *    # 进入函数时栈顶位置  stack_fun_top   #
  *    # # # # # # # # # # # # # # # # # # # #
  *    # 函数返回地址　      main_label1     #
  *    # # # # # # # # # # # # # # # # # # # #
  *    # 参数(1)         str1            #
  *　  # # # # # # # # # # # # # # # # # # # #
  *　　# 参数(2)         str2            #
  *    # # # # # # # # # # # # # # # # # # # #
  *
  *******************************************************************/

  /*总结，在调用一个函数的过程中，栈的情况如下
  *
  *    # # # # # # # # # # # #
  *    # 变量(n)         #
  *　　# # # # # # # # # # # #
  *　　# 变量(...)       #
  *    # # # # # # # # # # # # 
  *　　# 变量(2)         #
  *    # # # # # # # # # # # # 
  *　　# 变量(1)         #
  *    # # # # # # # # # # # # 
  *    # 进入函数时栈顶位置  #
  *    # # # # # # # # # # # #
  *    # 函数返回地址　      #
  *    # # # # # # # # # # # #
  *    # 参数(1)         #
  *　　# # # # # # # # # # # #
  *　　# 参数(2)         #
  *    # # # # # # # # # # # # 
  *　　# 参数(...)       #
  *    # # # # # # # # # # # # 
  *　　# 参数(n)         #
  *    # # # # # # # # # # # # 
    *
  ********************************************************************/

  CALL(bubbleSort,main_label2);//调用bubbleSort函数,bubbleSort函数没有返回值，所以不需要传参
main_label2://调用bubbleSort函数应该返回到这里

  getchar();
  goto MAIN_END;

  /*****************function max************************
  *这个函数用来比较两个字符串的大小
  *@param char *str1 要比较的第一个字符串
  *@param char *str2　要比较的第二个字符串
  *@return 如果str1大于str2,返回1,如果str1小于str2，返回-1，如果str1等于str2，返回0
  *****************************************************/
  //取得参数
  #undef str1
  #define str1 PARAM_PCHAR(0) //相当于char *str1;

  #undef str2
  #define str2 PARAM_PCHAR(1)//相当于char *str2;

  //参数的数量，这个函数有2个参数
  #undef param_count
  #define param_count 2

  //定义变量
  #undef i
  #define i VAR_INT(0) //相当于int i;

  //局部变量的数量,这个函数有1个变量
  #undef var_count
  #define var_count 1

  self_strcmp:
    {
      FUN_ENTER(var_count);//进入函数，初始化，在栈中分配var_count=1个变量
      
      i=0;
      while(1)
      {
        if(str1[i]>str2[i])
        {
          FUN_RET(1,param_count);//相当于return 1;
        }
        else if(str1[i]<str2[i])
        {
          FUN_RET(-1,param_count);//相当于return -1;
        }
        else 
        {
          if(str1[i]==0)
          {
            FUN_RET(0,param_count);//相当于return 0;
          }
        }
        i++;
        
      }  
    
    }

    
  /*****************function bubbleSort************************
  *用冒泡排序算法排列一个char*的数组
  *****************************************************/
  //定义变量
  #undef NAME_COUNT
  #define NAME_COUNT 5//name数组的大小为5

  #undef name
  #define name ((char**)&PARAM_PCHAR(0))//相当于char* name[5]

  #undef i
  #define i VAR_INT(5)//相当于int i;name占了5个空间,所以我们从5这个位置开始分配i的内存

  #undef j
  #define j VAR_INT(6)//相当于int j;

  #undef ret
  #define ret VAR_INT(7)//相当于int ret;

  #undef tmp 
  #define tmp VAR_PCHAR(8)//相当于char *tmp;

  //局部变量的数量,这个函数有1个变量
  #undef var_count
  #define var_count 9//有9个局部变量(5+1+1+1+1)

  bubbleSort:
    {
      FUN_ENTER(var_count);//进入函数，初始化,在栈中分配var_count=9个局部变量
      //初始化name数组
      name[0]="taohongtao";
      name[1]="hongtaotao";
      name[2]="taotaohong";
      name[3]="tht";
      name[4]="htaohongtao";

      printf("before sort,the name array is:");
      for(i=0;i<NAME_COUNT;i++)
      {
        printf("%s ",name[i]);
      }
      printf("\n");

      for(i=0;i<NAME_COUNT;i++)
      {
        for(j=0;j<NAME_COUNT-i-1;j++)
        {
          PUSH(name[j+1]);//传参
          PUSH(name[j]);//传参
          CALL(self_strcmp,bubbleSort_Label1);//调用self_strcmp函数
bubbleSort_Label1://调用函数self_strcmp完成之后，应该返回到这里
          ret=GET_RET();//获得返回值
          if(ret<0)
          {
            tmp=name[j];
            name[j]=name[j+1];
            name[j+1]=tmp;
          }
        }
      }

      printf("after sort,the name array is:");
      for(i=0;i<NAME_COUNT;i++)
      {
        printf("%s ",name[i]);
      }
      printf("\n");

      FUN_RET(0,param_count);//相当于return 0，不过这个函数不需要返回值，所以返回值无意义
    }

MAIN_END:
  return 0;//程序运行到这里，会出现一个错误，如果想解决这个问题请参见宏FUN_RET的定义
}

/*===============stack.h===========================*/
/*这个头文件封装了一个栈的结构，以及和函数调用相关的宏。
*包含以下功能:
*1.传递参数
*2.调用函数
*3.取得参数
*4.定义局部变量
*5.设置以及取得函数的返回值
*6.函数返回
*******************************************************/

/*****************栈的声明*****************/
extern int stack[81920];//声明一个大小为8M的栈
extern int stack_top;//栈顶的位置
extern int stack_fun_top;//stack_fun_top是进入函数时stack_top的值
extern int fun_ret_val;//用于保存函数的返回值
extern int fun_ret_addr;//用于暂存函数的返回地址

/*************函数调用和参数传递********************/

//传递参数，向栈中压入一个值
#define PUSH(param)\
  stack[stack_top]=((int)param);\
  --stack_top

//从栈中弹出一个值
#define POP(param)\
  ++stack_top;\
  param=stack[stack_top]

//在栈中为局部变量分配内存
#define VAR_MALLOC(n) stack_top-=n

//从栈里面取得变量stack[stack_fun_top-0]是第0个变量，stack[stack_fun_top-i]是第i个变量
#define VAR(i) stack[stack_fun_top-i]
//普通变量
#define VAR_CHAR(i) ((char)VAR(i))//在栈中定义一个char类型的变量
#define VAR_SHORT(i) ((short)VAR(i))//在栈中定义一个short类型的变量
#define VAR_INT(i) ((int)VAR(i))//在栈中定义一个int类型的变量

//指针变量
#define VAR_PCHAR(i) ((char*)VAR(i))//在栈中定义一个char*类型的变量
#define VAR_PSHORT(i) ((short*)VAR(i))//在栈中定义一个short*类型的变量
#define VAR_PINT(i) ((int*)VAR(i))//在栈中定义一个int*类型的变量

//二级指针变量
#define VAR_PPCHAR(i) ((char**)VAR(i))//在栈中定义一个char*类型的变量
#define VAR_PPSHORT(i) ((short**)VAR(i))//在栈中定义一个short*类型的变量
#define VAR_PPINT(i) ((int**)VAR(i))//在栈中定义一个int*类型的变量

//三级指针变量
#define VAR_PPPCHAR(i) ((char***)VAR(i))//在栈中定义一个char*类型的变量
#define VAR_PPPSHORT(i) ((short***)VAR(i))//在栈中定义一个short*类型的变量
#define VAR_PPPINT(i) ((int***)VAR(i))//在栈中定义一个int*类型的变量

//数组
#define VAR_ACHAR(i) ((char*)&VAR(i))//在栈中定义一个char array[]类型的数组
#define VAR_ASHORT(i) ((short*)&VAR(i))//在栈中定义一个short array[]类型的数组
#define VAR_AINT(i) ((int*)&VAR(i))//在栈中定义一个int array[]类型的数组

//一级指针数组
#define VAR_APCHAR(i) ((char**)&VAR(i))//在栈中定义一个char* array[]类型的数组
#define VAR_APSHORT(i) ((short**)&VAR(i))//在栈中定义一个short* array[]类型的数组
#define VAR_APINT(i) ((int**)&VAR(i))//在栈中定义一个int* array类型的数组

//二级指针数组
#define VAR_APPCHAR(i) ((char***)&VAR(i))//在栈中定义一个char** array[]类型的数组
#define VAR_APPSHORT(i) ((short***)&VAR(i))//在栈中定义一个short** array[]类型的数组
#define VAR_APPINT(i) ((int***)&VAR(i))//在栈中定义一个int** array[]类型的数组

//三级针数组
#define VAR_APPPCHAR(i) ((char****)&VAR(i))//在栈中定义一个char*** []array类型的数组
#define VAR_APPPSHORT(i) ((short****)&VAR(i))//在栈中定义一个short*** array[]类型的数组
#define VAR_APPPINT(i) ((int****)&VAR(i))//在栈中定义一个int*** array[]类型的数组

//从栈里面取得参数,stack[stack_fun_top+0]是第一个局部变星的值,stack[stack_fun_top+1]是进入函数时保存stack_fun_top的值，stack[stack_fun_top+2]是函数的返回地址,stack[stack_fun_top+3]是第0个参数，stack[stack_fun_top+3+i]是第i个参数
#define PARAM(i) stack[stack_fun_top+3+i]
#define PARAM_CHAR(i) ((char)PARAM(i))
#define PARAM_SHORT(i) ((short)PARAM(i))
#define PARAM_INT(i) ((int)PARAM(i))

#define PARAM_PCHAR(i) ((char*)PARAM(i))
#define PARAM_PSHORT(i) ((short*)PARAM(i))
#define PARAM_PINT(i) ((int*)PARAM(i)

#define PARAM_PPCHAR(i) ((char**)PARAM(i))
#define PARAM_PPSHORT(i) ((short**)PARAM(i))
#define PARAM_PPINT(i) ((int**)PARAM(i)

#define PARAM_PPPCHAR(i) ((char***)PARAM(i))
#define PARAM_PPPSHORT(i) ((short***)PARAM(i))
#define PARAM_PPPINT(i) ((int***)PARAM(i)

//设置函数返回值
#define SET_RET(val) fun_ret_val=val

//获得函数的返回值
#define GET_RET() fun_ret_val

/************************************************************************
*进入函数的第一句代码，用于将stack_fun_top入栈，把stack_top保存到stack_fun_top里,在栈中分配局部变量所需的空间
*每个函数在进入时都需要将stack_top保存在stack_fun_top中,以便在函数退出时恢复stack_top的值
*因为stack_fun_top是一个全局变量，为了不影响其他函数,
*所以我们在函数进入时把stack_fun_top的值保存到栈里，在函数离开时再从栈中恢复stack_fun_top的值
*@param var_count 局部变量的个数
*************************************************************************/
#define FUN_ENTER(var_count)\
  PUSH(stack_fun_top);\
  stack_fun_top=stack_top;\
  VAR_MALLOC(var_count)

/****************************************************
*用于函数返回，分为以下几步:
*1.恢复stack_top
*2.恢复stack_fun_top
*3.弹出调用时压入的参数
*4.设置返回值
*5.取得返回的地址，并返回
*@param ret_value 返回值
*@param param_count 参数的个数
*我们从栈中取得函数的返回地址，再将这个地址强制转换为一个函数
*再调用这个函数，这样函数就可以返回了
*由于函数在调用时，会将返回地址压入栈，同样，系统函数也是一样，
*这样我们的函数每次返回时都会向系统的栈里压入一个地址，
*在退出main函数时，系统检查到栈里面多了几个值，会报一个错
*不过这并不影响我们的程序正常运行，因为这时候程序已经运行完毕，马上就要退出了
*如果一定要解决这个问题，请使用下面那段汇编代码进行函数返回，
*这段汇编代码只转到函数返回地址，而不向系统的栈中压入任何值
*******************************************************/
#if 1

  #define FUN_RET(ret_value,param_count)\
  stack_top=stack_fun_top;\
  POP(stack_fun_top);\
  stack_top+=param_count+1;\
  SET_RET(ret_value);\
  ((void (*)())stack[stack_top-param_count])();

#else

  #define FUN_RET(ret_value,param_count)\
  stack_top=stack_fun_top;\
  POP(stack_fun_top);\
  stack_top+=param_count+1;\
  SET_RET(ret_value);\
  _asm{mov eax,stack_top}_asm{ sub eax,param_count} _asm{jmp dword ptr stack[4*eax]}  

#endif
  

/********************************************************
*获得一个标号的值，将结果存在全局变量fun_ret_addr里
*因为C语言无法取得标号的值，所以这个用了一段汇编代码来实现
*@param label 标号的名称
*************************************************/
#define GET_LABEL_VALUE(label)\
  _asm{push label}\
  _asm{pop fun_ret_addr}

/***********************************************************
*调用一个函数，分为3步:
*1.取得代表函数返回地址的标号的值
*2.将函数的返回地址压入栈，这样在返回时我们从栈中取得该值，即可实现函数返回
*3.调用函数
*@param fun_name 要调用的函数的名字
*@param fun_ret_label 代表函数返回地址的标号
***********************************************************/
#define CALL(fun_name,fun_ret_label)\
  GET_LABEL_VALUE(fun_ret_label)\
  PUSH(fun_ret_addr);\
  goto fun_name

  

/*============stack.c=====================*/
int stack[81920];//定义一个大小为8M的栈
int stack_top=81920-1;//栈顶的位置
int stack_fun_top;//stack_fun_top是进入函数时stack_top的值
int fun_ret_val;//用于保存函数的返回值
int fun_ret_addr;//用于暂存函数的返回地址

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

上传的附件：
收藏
免费 ・0
支持
分享
最新回复 (6)
邋遢鬼
雪    币： 31
活跃值： (48)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
2 楼
潜力贴留名，沙发。
2012-11-8 01:12
0
hrpirip
雪    币： 55
活跃值： (519)
能力值： ( LV6，RANK：80 )
在线值：
发帖
回帖
粉丝
私信
3 楼
不错，一直在找相关方面的好文。
2012-11-8 03:03
0
封心锁爱
雪    币： 239
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
4 楼
不错，留名以备
2012-11-8 08:12
0
孤单的狼
雪    币： 27
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
MARk 有空好好看
2012-11-8 09:06
0
xouou
雪    币： 90
活跃值： (91)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼 

俺来画蛇添足
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

//链式栈
typedef struct Node
{
	int data;	
	struct Node* pNext;
}NODE,*PNODE;

typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK,*PSTACK;

void init(PSTACK pStack); //初始化
void push(PSTACK pStack,int val); //压栈
void traverse(PSTACK pStack);    //遍历
bool pop(PSTACK pStack,int* pVal);//出栈
bool isEmpty(PSTACK pStack);     //栈空检测
void clear(PSTACK pStack);       //清空


int main(void)
{
	STACK s;
	int val=0;
	init(&s);	//初始化一个空栈,因为此时栈顶等于栈底
	push(&s,1); //压栈
	push(&s,2);
	push(&s,3);
	push(&s,4);
	if (pop(&s,&val))
	{
		printf("出栈元素值为:%d\n",val);
	}
	else
	{
		printf("pop出栈失败!");
	}
	printf("遍历输出:");
	traverse(&s); //遍历输出

	clear(&s);
	printf("清空后输出:\n");
	traverse(&s);
	return 0;
}

void clear(PSTACK pStack)
{
	if (isEmpty(pStack))
	{
		return ;
	}
	else
	{
		PNODE pTemp=NULL;
		while (pStack->pTop !=pStack->pBottom)
		{
			pTemp=pStack->pTop->pNext;
			free(pStack->pTop);
			pStack->pTop=pTemp;
		}
	}
}

bool isEmpty(PSTACK pStack)
{
	if (pStack->pBottom==pStack->pTop)
	{
		return true; //空
	}
	else
	{
		return false;
	}
}

bool pop(PSTACK pStack,int* pVal) //val接受出栈元素
{
	if (isEmpty(pStack))
	{
		return false; //出栈失败
	}
	else
	{
		PNODE pTemp  =	pStack->pTop;
		*pVal	 	 =	pTemp->data;
		pStack->pTop =	pTemp->pNext;
		free(pTemp);
		pTemp=NULL;
		return true;
	}
}

void traverse(PSTACK pStack)
{

	if (isEmpty(pStack))
	{
		printf("栈为空!\n");
		return;
	}
	PNODE p=pStack->pTop;
	while (p!=pStack->pBottom)
	{
		printf("%d,",p->data);
		p=p->pNext;
	}
	printf("\n遍历完成!\n");
}

void push(PSTACK pStack,int val)
{
	PNODE pNew=(PNODE)malloc(sizeof(NODE));
	pNew->data=val;
	pNew->pNext=pStack->pTop;//先将旧栈顶元素的地址保存到新元素的指针域
	pStack->pTop=pNew;	//将新元素标记为栈顶,这个就是新栈顶元素
	return ;

}

void init(PSTACK pStack)
{
	pStack->pTop=(PNODE)malloc(sizeof(NODE));
	if (NULL==pStack->pTop)
	{
		printf("失败1!\n");
		exit(-1);
	}
	else
	{
		pStack->pBottom=pStack->pTop;
		pStack->pTop->pNext=NULL;
	}
		
}
2012-11-8 11:51
0
cheryl
雪    币： 327
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
不错 好复杂 看不懂
2012-11-8 15:47
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//