首页 > 其他 > 详细

关于栈及其应用示例

时间:2014-06-15 15:00:55      阅读:197      评论:0      收藏:0      [点我收藏+]

转载请注明出处

http://blog.csdn.net/pony_maggie/article/details/30802249


作者:小马



作为一种常用的数据结构, 了解栈对于算法的学习是非常必要的。栈有先进后出的特点,栈底指向数据表中的第一个元素,栈顶指向最后一个元素的下一个位置。如下图所示:

 bubuko.com,布布扣

 

栈和线性表类似,也是有两种存储结构,分别为顺序结构和链式结构。大部分情况下,栈使用前者,这和它的使用场景有关,因为通常情况下我们不会对栈进行频繁地,随机地插入,删除操作。下面是我用顺序结构实现的栈,这个栈有个特点就是它的通用性,因为我并没有限制它所存储的数据类型,代码如下:

//void**其为双指针,意味入栈和出栈的将只是对应数据的地址,而不需要对数据本身进行拷贝
typedef struct 
{
	char *base;
	char *top;
	int elementSize; //元素所点字节大小
	int stackSize;	//当前已分配的空间(注意不是元素的实际个数)
}ponyStack;

int InitStack(ponyStack *stack, int elementSize)
{
	stack->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)*elementSize);
	if (!stack->base)
	{
		return RET_ERROR;
	}

	stack->top = stack->base; //为空
	stack->stackSize = STACK_INIT_SIZE;
	stack->elementSize = elementSize;

	return RET_OK;
}

int ClearStack(ponyStack *stack)
{
	stack->top = stack->base;
	return RET_OK;
}

bool IsEmptyStack(ponyStack stack)
{
	if (stack.top == stack.base)
	{
		return true;
	}
	return false;
}

这里没有贴出全部的代码,更完整的可以从最后的地址那里下载。注意elementSize,这个是栈可以做到通用的核心。不理解的可以再研究一下代码。

 

 

看一个栈的使用示例,数制转换。十进制转八进制。例如(1348)十进制= (2504)八进制,它基于如下的原理:

   N             N/8             N%8

  1348        168               4

  168           21                0

   21             2                  5

   2               0                   2

 

所以很明显,N不断的除8,每次的余数就是结果的其中一个因子,注意先出来的因子是低位的数,可以考虑用栈来保存每次取余的结果,那么出栈的顺序就是实际的结果顺序。代码很简单:

int decimalToOctonary(int decimalNumber)
{
	double octNumber = 0;
	int nCount = 0;
	int nTemp = 0;
	ponyStack numberStack;
	InitStack(&numberStack, 4);


	while (decimalNumber)
	{
		nTemp = (int)decimalNumber%8;
		Push(&numberStack, &nTemp);
		decimalNumber = decimalNumber/8;
	}

	nCount = CountOfStack(numberStack);//元素个数也就是位数
	while(!IsEmptyStack(numberStack))
	{
		Pop(&numberStack, &nTemp);
		octNumber += (nTemp*pow(10.0, --nCount));
	}
	
	DestroyStack(&numberStack);

	return (int)octNumber;
}


再来看一个行编辑程序的示例,用户在终端输入字符,完成后保存用户的数据区, 因为在输入的过程中可能出错,需要修改,所以不可能每输入一个字符就存入数据区。比较好的做法是先在内存里开一个输入的缓冲区,当用户输入完成一行后,再存入数据区。在行内可以修改。例如,当用户发现刚输入的一个字符是错的之后,可以再输入一个‘#‘,表示前一个字符是错的,如果发现当前行输入的错误太多,可以输入一个退行符‘@‘,表示当前行都无效,举个例子:

whli#ilr#e(s#*s)

outcha@putchar(*s=#++)

实际有效的字符是这样的:

while(*s)

putchar(*s++)


可以把内存里这个输入缓冲区定为栈,正常情况下每输入一个字符直接入栈,如果发现字符是‘#‘,就栈顶pop一次,如果是‘@‘就清空栈.代码实现如下:

void lineEdit()
{
	char ch = 0;
	char chTemp = 0;
	ponyStack lineStack;
	InitStack(&lineStack, 1);

	ch = getchar();
	while (ch != EOF)
	{

		while (ch != EOF && ch != '\n')
		{
			switch (ch)
			{
			case '#':
				Pop(&lineStack, &chTemp);
				break;
			case '@':
				ClearStack(&lineStack);
				break;
			default:
				Push(&lineStack, &ch);
				break;
			}
			ch = getchar();
		}

		writeToFile(lineStack);//存数据
		ClearStack(&lineStack);//准备接收下一行
		if (ch != EOF)
		{
			ch = getchar();
		}
	}

	DestroyStack(&lineStack);

}


最后一个例子是表达式求值的算法,这个在计算器应用中比较多用到。比如,

求+4*9-16/4

建两个栈,一个存操作数,一个存运算符.为简单起,在运算符栈会预先存一个‘#‘,表示表达式开始,然后以‘#‘结束。运算规则是这样的:

输入字符,如果是‘#‘,则结束,如果是操作数,直接进操作数栈。如果是运算符,则跟栈顶的运算符比较,如果栈顶的优先级低,直接进栈,接收下一字符,如果相等,脱括号,接收下一个字符,如果栈顶的优先级高,pop两个操作数,pop栈内操作符,运算,然后运算的结果进操作数栈。当前运算符继续跟栈顶比较。


要实现这个代码,首先要有一个表格,存储我们操作符之间的优先级关系,如下所示:

static char priority[7][7] = {
	'>','>','<','<','<','>','>',   // +
	'>','>','<','<','<','>','>',   // -
	'>','>','>','>','<','>','>',   // *
	'>','>','>','>','<','>','>',   // /
	'<','<','<','<','<','=',' ',   // (
	'>','>','>','>',' ','>','>',   // )
	'<','<','<','<','<',' ','=',   // #
};// +   -   *   /   (   )   #


然后实现根据上面的思路,实现起来就比较容易了:

int evaluateExpression()
{
	char chCurrent = 0;
	char chOnTop = 0;

	char chTemp = 0;
	int nResult = 0;
	int nTemp = 0;
	int a,b;
	int nOperandFlag = 0;

	ponyStack operatorStack;//运算符栈
	ponyStack operandStack; //操作数栈

	InitStack(&operatorStack, 1);
	chTemp = '#';
	Push(&operatorStack, &chTemp);

	InitStack(&operandStack, 4);

	chCurrent = getchar();
	GetTop(operatorStack, &chOnTop);

	while ((chCurrent != '#')||(chOnTop != '#'))
	{
		if (!isOperator(chCurrent))//是操作数,要考虑多位整型数的情况
		{
			nTemp = nTemp * (int)pow(10.0, nOperandFlag);
			nTemp += (int)(chCurrent - '0');
			chCurrent = getchar();
			nOperandFlag = 1;
		}
		else
		{
			if (nOperandFlag == 1)
			{
				Push(&operandStack, &nTemp);//操作数输入结束,入栈
				nOperandFlag = 0;
				nTemp = 0;
			}
			
			GetTop(operatorStack, &chOnTop);
			switch (precede(chOnTop, chCurrent))//比较优先级
			{
			case '<':		//栈顶的优先级小
				Push(&operatorStack, &chCurrent);
				chCurrent = getchar();
				GetTop(operatorStack, &chOnTop);
				break;
			case '=':		//脱括号,接收下个字符
				Pop(&operatorStack, &chTemp);
				chCurrent = getchar();
				GetTop(operatorStack, &chOnTop);
				break;
			case '>':		//栈顶的优先级大,出栈运算,结果入栈
				{
					Pop(&operandStack, &a);
					Pop(&operandStack, &b);
					Pop(&operatorStack, &chTemp);
					nTemp = operate(a, chTemp, b);
					Push(&operandStack, &nTemp);
					nTemp = 0;//重置
					GetTop(operatorStack, &chOnTop);
				}
				break;
			default:
				break;
			}
			
		}
	}


	GetTop(operandStack, &nResult);
	
	DestroyStack(&operatorStack);
	DestroyStack(&operandStack);

	return nResult;
}


代码下载地址:

https://github.com/pony-maggie/StackDemo

http://download.csdn.net/detail/pony_maggie/7499167

关于栈及其应用示例,布布扣,bubuko.com

关于栈及其应用示例

原文:http://blog.csdn.net/pony_maggie/article/details/30802249

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!