栈的相关笔记

柔情只为你懂 2022-12-26 15:28 139阅读 0赞

栈和队列  
3.1 栈的抽象数据类型定义与实现  
3.2 栈的应用举例  
3.3 栈的应用–栈与递归  
3.4 队列的抽象数据类型定义和实现  
3.5 队列的应用–离散事件模拟

3.1 栈的抽象数据类型定义与实现

1.  栈的相关概念  
    概念:  
    栈是定义在线性结构上的抽象数据类型,其操作类似线性表操作  
    但元素的插入,删除和访问都必须在表的一端进行,  
    为形象期间,称允许操作端为栈顶(Top),另一端为栈底(base)  
    注意Top指向的不是最后一个元素的位置,而是指向待插入位置

特性:Last In First Out 后进先出  
应用:进制转换 括号匹配 迷宫求解

1.  栈的ADT定义

ADT Stack
    {
        
    	数据对象: D = {
        ai|ai∈ ElemSet }
    	数据元素关系: R = {
        <ai-1,ai>}
    	基本操作:
    	InitStack(&S)
    	
    	DestroyStack(&S)
    	增
    	Push(&S, e)
    	删
    	Pop(&s, &e)
    	查
    	GetTop(S, &e)
    	其他常用操作:
    	ClearStack(&S)
    	
    	StackEmpty(S)
    	
    	StackLength(S)
    	
    	StackTraverse(S, visit())
    	
    }ADT Stack
    
    3. 顺序栈的定义: 
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    typedef * SElemType;
    typedef struct 
    {
        
    	SElemType *base; //栈底指针
    	SElemType *top; //栈顶指针
    	int stacksize;
    }SqStack;
    
    顺序栈的基本操作实现--初始化/销毁/置空
    Status InitStack(SqStack &S)
    {
        
    	S.base = (SElemType*)malloc(sizeof(SElemType));
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    	return OK;
    }
    
    Status DestroyStack(SqStack &S)
    {
        
    	free(S.base);
    	S.base = NULL;
    	S.top = NULL;
    	S.stacksize = 0;
    	return OK;
    }
    Status ClearStack(SqStack &S)
    {
        
    	S.top = S.base;
    	return OK;
    }
    
    入栈和出栈
    Status Push(SqStack &S, SElemType e)
    {
        
    	//实际上此时S.top 已经指向 内存区的 其他部分了
    	if (S.top - S.base == S.stacksize)
    	{
        
    		S.base = (SElemType*)realloc(sizeof(SElemType) * (S.stacksize +  STACKINCREMENT));
    		if (S.base == NULl) exit(OVERFLOW);
    		S.top = S.S.base + S.stacksize;
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top++ = e;
    	return OK;
    }
    Status Pop(SqStack &S, SElemType &e)
    {
        
    	if (S.top == S.base) return ERROR;
    	e = *(--S.top);
    	return OK;
    }
    
    引用型操作
    Status StackEmpty(SqStack S)
    {
        
    	if (S.top == S.base) return TRUE;
    	else return FALSE;
    }
    
    int StackLength(SqStack S)
    {
        
    	return S.top - S.base;
    }
    Status GetTop(SqStack S, SElemType &e)
    {
        
    	if (S.top == S.base) return ERROR;
    	e = *(S.top - 1);
    	return OK;
    }
    Status StackTraverse(SqStack S, Status(*visit)(SElemType))
    {
        
    	SElemType *p = S.base;
    	while (p < S.top)
    	{
        
    		if( visit(*p) == ERROR) return ERROR;
    		++p;
    	}
    	return OK;
    }

1.  链栈的定义与实现  
    若栈中元素的数目变化范围较大或不清楚栈元素的数目,  
    可以考虑使用链式存储结构,用链式存储结构表示的栈称为"链栈"

链栈常用一个无头结点的单链表表示,栈名指向栈顶元素(尾元素)  
不同于顺序栈的栈顶,顺序栈栈顶指向第一个空位置

栈的链式存储结构定义:

typedef struct StackNode
    {
        
    	SElemType data;
    	struct SNode *next;
    }StackNode, *LinkStack;
    
    Status InitStack(LinkStack &S)
    {
        
    	S = NULL;
    }
    
    Status Push(LinkStack &S, SElemType e)
    {
        
    	SNode *p = new  StackNode();
    	p->data = e;
    	p->next = S;
    	S = p;
    }
    Status Pop(LinkStack &S, SElemType &e)
    {
        
    	if (S == NULL) return ERROR;
    	e = S->data;
    	p = S;
    	S = S->next;
    	free(p);
    	p = NULL;
    }

3.2 栈的应用–栈与递归  
十进制整数转换为 八进制

void conversion(int num, int carry)
    {
        
    	InitStack(S);
    	while (num)
    	{
        
    		Push(S, num % carry);
    		num /= carry;
    	}
    	while (!StackEmpty(S))
    	{
        
    		Pop(S, e);
    		printf("%d ", e);
    	}
    }

表达式求值-算符优先法  
例如: 2 + 4 - 3 \* 6 \#  
注: 那当前扫描的运算符与上一个比较优先级,  
当前扫描符号低或相等则进行上一个运算(需取最近的两个数)  
否则入栈,扫描下一个  
注:设操作符栈和操作数栈,运算符栈最初压入起始符\#  
逐个扫描符号(直到栈顶运算符与当前符号均为’\#’):  
\{  
遇操作数直接入栈,读下一字符,  
遇运算符则与栈顶运算符比较优先级  
\{  
当前运算符优先级高(前面的运算还不应执行,当前的运算符也不确定是否该执行)  
\{  
则当前运算符入栈,读入下一符号  
\}  
否则  
\{  
栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈  
开始下次循环  
\}  
\}  
\}

补充:后缀表达式  
中缀表达式: 4 + 2 \* 3 - 10 / 5 2 + 4 - 3 \* 6  
后缀表达式: 对于扫描到的数字除了压入数栈以外,同时  
压入到另一个用于求后缀表达式的PEXP,  
当执行一次运算时,将执行的运算符同时压入PEXP.  
所有运算结束后,从栈底到栈顶输出所得序列即为表达式的后缀表达式