数据结构之栈的顺序存储结构及其应用

文章目录

一、栈的顺序存储
- 结构体的定义：
- 相关操作实现
- - 1.初始化
  - 2.依次对栈中的每个数据元素输出
  - 3.进栈（push）
  - 4.出栈（pop）
  - 5.栈中元素个数
- 6.具体代码实现
- 7.样例输出
二、栈的应用之括号匹配
- 1.匹配函数
- 2.输出样例
三、表达式求值
- 1.C++闵版复刻
- 2.C版
- - 实现思路：
  - 结构体的定义
  - 初始化
  - 进栈
  - 出栈
  - 获取字符栈栈顶元素
  - 优先级判断
  - 得到后缀表达式
  - 核心计算得到最终结果
  - 完整代码实现
  - 样例输出
四、写在最后

栈的顺序存储及其应用

这里是数据结构个人学习的笔记记录，如有问题欢迎指正说明

一、栈的顺序存储

栈是仅能在表尾进行插入和删除操作的线性表，遵循先进后出。

先来定义结构体变量，它类似于顺序表，不过结构体中记录长度的变量改为top来记录栈顶，具体定义如下

结构体的定义：

typedef struct CharStack{
    int top;
    int data[MAXSIZE];
}*CharStackPtr;

相关操作实现 1.初始化

定义一个栈，且将此时的top值定义为-1

CharStackPtr charStackInit(){
    CharStackPtr resultPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
    resultPtr->top=-1;

    return resultPtr;
}

2.依次对栈中的每个数据元素输出

void outputStack(CharStackPtr paraStack){
    for(int i=0;i<=paraStack->top;i++)
    {
        printf("%c ",paraStack->data[i]);
    }
    printf("rn");
}

3.进栈（push）

改变top值

void push(CharStackPtr paraStackPtr,int paraValue){
    if(paraStackPtr->top>=MAXSIZE-1){
        printf("Cannot push element:stack full.rn");
        return ;
    }
    paraStackPtr->top++;

    paraStackPtr->data[paraStackPtr->top]=paraValue;
}

4.出栈（pop）

char pop(CharStackPtr paraStackPtr){
    if(paraStackPtr->top<0)
    {
        printf("Cannot pop element:stack empty.rn");
        return '';
    }
    paraStackPtr->top--;

    return paraStackPtr->data[paraStackPtr->top+1];
}

5.栈中元素个数

因为pop记录栈顶元素下标，所以求栈中元素的个数就十分容易了

int stackLength(CharStackPtr paraStackPtr)
{
    return paraStackPtr->top+1;
}

6.具体代码实现

#include
#include

#define MAXSIZE 10

typedef struct CharStack{
    int top;
    int data[MAXSIZE];
}*CharStackPtr;

void outputStack(CharStackPtr paraStack){
    for(int i=0;i<=paraStack->top;i++)
    {
        printf("%c ",paraStack->data[i]);
    }
    printf("rn");
}

CharStackPtr charStackInit(){
    CharStackPtr resultPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
    resultPtr->top=-1;

    return resultPtr;
}

void push(CharStackPtr paraStackPtr,int paraValue){
    if(paraStackPtr->top>=MAXSIZE-1){
        printf("Cannot push element:stack full.rn");
        return ;
    }
    paraStackPtr->top++;

    paraStackPtr->data[paraStackPtr->top]=paraValue;
}

char pop(CharStackPtr paraStackPtr){
    if(paraStackPtr->top<0)
    {
        printf("Cannot pop element:stack empty.rn");
        return '';
    }
    paraStackPtr->top--;

    return paraStackPtr->data[paraStackPtr->top+1];
}

int stackLength(CharStackPtr paraStackPtr)
{
    return paraStackPtr->top+1;
}

void pushPopTest(){
    char ch;
    printf("---Begin---rn");

    CharStackPtr tempStack=charStackInit();
    printf("After initialization,the stack is: ");
    outputStack(tempStack);

    for(ch='a';ch<'m';ch++){
        printf("Pushing %c.rn",ch);
        push(tempStack,ch);
        outputStack(tempStack);
    }
    printf("The length of the stack is %dn",stackLength(tempStack));

    for(int i=0;i<3;i++){
        ch=pop(tempStack);
        printf("Pop %c.rn",ch);
        outputStack(tempStack);
    }
    printf("---End---");
}
int main(){
    pushPopTest();
    return 0;
}

7.样例输出

—Begin—
After initialization,the stack is:
Pushing a.
a
Pushing b.
a b
Pushing c.
a b c
Pushing d.
a b c d
Pushing e.
a b c d e
Pushing f.
a b c d e f
Pushing g.
a b c d e f g
Pushing h.
a b c d e f g h
Pushing i.
a b c d e f g h i
Pushing j.
a b c d e f g h i j
Pushing k.
Cannot push element:stack full.
a b c d e f g h i j
Pushing l.
Cannot push element:stack full.
a b c d e f g h i j
The length of the stack is 10
Pop j.
a b c d e f g h i
Pop i.
a b c d e f g h
Pop h.
a b c d e f g
—End—
Finish.

二、栈的应用之括号匹配 1.匹配函数

实现原理：另外生成一个栈，遇到括号的的前半部分则压栈，遇到后半部分就与与新生成的栈的栈顶来匹配，如果不匹配则说明该式子的等号不匹配，直接返回false；否则匹配，继续执行。

bool bracketMatching(char* paraString, int paraLength) {

    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;

	for (int i = 0; i < paraLength; i++) {
		tempChar = paraString[i];

		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);
			break;
		case ')':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '(') {
				return false;
			} // Of if
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			} // Of if
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			} // Of if
			break;
		default:
			// Do nothing.
			break;
		}// Of switch
	} // Of for i

	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return true;
	} // Of if

	return true;
}

2.输出样例

Is the expression ‘[2 + (1 - 3)] * 4’ bracket matching? 1
Is the expression ‘( ) )’ bracket matching? 0
Is the expression ‘()()(())’ bracket matching? 1
Is the expression ‘({}[])’ bracket matching? 1
Is the expression ‘)(’ bracket matching? 0

三、表达式求值 1.C++闵版复刻

#include
#include
#include
#include
#include

using namespace std;

stack num;
stack op;

void eval()
{
    auto b=num.top();
    num.pop();
    auto a=num.top();
    num.pop();
    auto c=op.top();
    op.pop();
    int x;
    if(c=='+')
    x=a+b;
    else if(c=='-')
    x=a-b;
    else if(c=='*')
    x=a*b;
    else 
    x=a/b;
    num.push(x);
}

int main()
{
    unordered_map pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    string str;
    cin >> str;
    for(int i=0;i
        auto c=str[i];
        if(isdigit(c))
        {
            int x=0,j=i;
            while(j
            while(op.top()!='(')
            eval();
        }else{
            while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])
            eval();
            op.push(c);
        }
    }
    while(op.size())
    eval();
    cout << num.top()< 
2.C版 
实现思路： 
 
 (一)中缀表达式 －> 后缀表达式
 从左到右遍历中缀表达式中的每个数字和符号，若是数字则输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。 
 
 
 （二）后缀表达式 -> 求值
 从左到右遍历后缀表达式的每个数字和符号，遇到是数字就进栈，遇到是符号就将处于栈顶两个数字出栈，进行计算，运算结果进栈，一直到得到最终结果。 
 
结构体的定义 
一个存数字，一个存运算符 
typedef struct 
{
    char *ch;
    int top;
}CharStack;

typedef struct
{
    int *num;
    int top;
}NumStack;
 
初始化 
void InitCharStack(CharStack &S)
{
    S.ch = (char *)malloc(MAXSIZE * sizeof(char));
    
    if (S.ch == NULL) 
    {
    	printf("内存分配失败rn");
    	return;
	}
    S.top = -1;
    
    return;
}

void InitNumStack(NumStack &St)
{
	St.num = (int *)malloc(MAXSIZE * sizeof(int));

	St.top = -1;
	
	return;
}
 
进栈 
//字符进栈
void PushCharStack(CharStack &S, char c)
{    
    if (S.top >= MAXSIZE-1) 
    {    
        printf("栈已满rn");
        return;
    }
    S.top ++;
    * ++S.ch = c;
    
    return;
}
//数字进栈
void PushNumStack(NumStack &St, int n)
{
	if (St.top == MAXSIZE) 
    {    
        printf("栈已满rn");
    }
    
	St.top ++;
	
	* ++St.num = n;
	
	return;
}
 
出栈 
char PopCharStack(CharStack &S)
{   
    if (S.top == -1)
    {
        printf("栈为空rn");
        exit(1);
    }
    S.top --;
    char c = *S.ch --;
    
    return c;
}

int PopNumStack(NumStack &St)
{
	if (St.top == -1)
    {
        printf("栈为空rn");
    }
    St.top --;
    int num = *St.num --;
    
    return num;
}
 
获取字符栈栈顶元素 
char GetStackTop(CharStack &S)
{
    char c = *S.ch;
    
    return c;
}
 
优先级判断 
bool PriorJudge(char c1, char c2)
{
	if (c1 == '*' || c1 == '/') 
	   if (c2 == '+' || c2 == '-' || c2 == '(')
	      return true;
	if (c1 == '+' || c1 == '-')
	   if (c2 == '(') return true;
	   
	return false;
}
 
得到后缀表达式 
char *InfixToSuffex(char *a, char *b)//infix中缀 suffex后缀 
{
    fgets(a, MAXSIZE-1, stdin);//从输入流中读取字符串
    
    printf("中缀表达式为:%srn",a);
    
    int t = strlen(a);
    
    int k = 0;
    
    for (int i = 0; i < t; ++ i)
    {
    	
        if (a[i] >= '0' && a[i] <= '9')
        {
        	b[k ++] = a[i];
            if (a[i+1] < '0' || a[i+1] > '9')
                b[k ++] = '#';
        }
        
        else if (a[i] == ' ' || a[i] == '=') continue;
            
        else
        {
            if(S.top == -1 || a[i] == '(') 
			    PushCharStack(S, a[i]);
            
            else if (a[i] == ')')
            {
                while (S.top != -1 && GetStackTop(S) != '(')
				    b[k ++] = PopCharStack(S);
				    
				if (S.top != -1) PopCharStack(S);
                    
            }
            
            else
            {
                while (S.top != -1 && !PriorJudge(a[i], GetStackTop(S)))
                    b[k ++] = PopCharStack(S);
                    
                PushCharStack(S, a[i]);
            }
        }
        
    } 
    return b;
}
 
核心计算得到最终结果 
int CaculatValue(char *b, NumStack &St)
{
	InitNumStack(St);
	int t = strlen(b);
	int num = 0;
	
	for (int i = 0; i < t; ++ i)
	{
		if (b[i] >= '0' && b[i] <= '9')
		{
		    num = 10 * num + b[i] - '0';
		    if (b[i+1] == '#') PushNumStack(St, num), num = 0;
	    }
		
		else
		{
			if (b[i] == '#') continue;
			
			int n = PopNumStack(St);
			int m = PopNumStack(St);
			
			if (b[i] == '+') PushNumStack(St, m + n);
			
			else if (b[i] == '-') PushNumStack(St, m - n);
			
			else if (b[i] == '*') PushNumStack(St, m * n);
			
			else PushNumStack(St, m / n);
		}
		
	}
	
	return PopNumStack(St);
}
 
完整代码实现 
#include
#include
#include

#define MAXSIZE 100

typedef struct 
{
    char *ch;
    int top;
}CharStack;

typedef struct
{
    int *num;
    int top;
}NumStack;

CharStack S;
NumStack St;

void InitCharStack(CharStack &S)
{
    S.ch = (char *)malloc(MAXSIZE * sizeof(char));
    
    if (S.ch == NULL) 
    {
    	printf("memory allocation failedrn");
    	return;
	}
    S.top = -1;
    
    return;
}

void PushCharStack(CharStack &S, char c)
{    
    if (S.top >= MAXSIZE-1) 
    {    
        printf("Stack is full!rn");
        return;
    }
    S.top ++;
    * ++S.ch = c;
    
    return;
}

char PopCharStack(CharStack &S)
{   
    if (S.top == -1)
    {
        printf("Stack is empty!rn");
        exit(1);
    }
    S.top --;
    char c = *S.ch --;
    
    return c;
}

char GetStackTop(CharStack &S)
{
    char c = *S.ch;
    
    return c;
}

bool PriorJudge(char c1, char c2)
{
	if (c1 == '*' || c1 == '/') 
	   if (c2 == '+' || c2 == '-' || c2 == '(')
	      return true;
	if (c1 == '+' || c1 == '-')
	   if (c2 == '(') return true;
	   
	return false;
}

char *InfixToSuffex(char *a, char *b)
{
    fgets(a, MAXSIZE-1, stdin);//从输入流中读取字符串
    
    printf("Infix expression is:%srn",a);
    
    int t = strlen(a);
    
    int k = 0;
    
    for (int i = 0; i < t; ++ i)
    {
    	
        if (a[i] >= '0' && a[i] <= '9')
        {
        	b[k ++] = a[i];
            if (a[i+1] < '0' || a[i+1] > '9')
                b[k ++] = '#';
        }
        
        else if (a[i] == ' ' || a[i] == '=') continue;
            
        else
        {
            if(S.top == -1 || a[i] == '(') 
			    PushCharStack(S, a[i]);
            
            else if (a[i] == ')')
            {
                while (S.top != -1 && GetStackTop(S) != '(')
				    b[k ++] = PopCharStack(S);
				    
				if (S.top != -1) PopCharStack(S);
                    
            }
            
            else
            {
                while (S.top != -1 && !PriorJudge(a[i], GetStackTop(S)))
                    b[k ++] = PopCharStack(S);
                    
                PushCharStack(S, a[i]);
            }
        }
        
    } 
    return b;
}

void InitNumStack(NumStack &St)
{
	St.num = (int *)malloc(MAXSIZE * sizeof(int));

	St.top = -1;
	
	return;
}

void PushNumStack(NumStack &St, int n)
{
	if (St.top == MAXSIZE) 
    {    
        printf("Stack is full!rn");
    }
    
	St.top ++;
	
	* ++St.num = n;
	
	return;
}

int PopNumStack(NumStack &St)
{
	if (St.top == -1)
    {
        printf("Stack is empty!rn");
    }
    St.top --;
    int num = *St.num --;
    
    return num;
}

int CaculatValue(char *b, NumStack &St)
{
	InitNumStack(St);
	int t = strlen(b);
	int num = 0;
	
	for (int i = 0; i < t; ++ i)
	{
		if (b[i] >= '0' && b[i] <= '9')
		{
		    num = 10 * num + b[i] - '0';
		    if (b[i+1] == '#') PushNumStack(St, num), num = 0;
	    }
		
		else
		{
			if (b[i] == '#') continue;
			
			int n = PopNumStack(St);
			int m = PopNumStack(St);
			
			if (b[i] == '+') PushNumStack(St, m + n);
			
			else if (b[i] == '-') PushNumStack(St, m - n);
			
			else if (b[i] == '*') PushNumStack(St, m * n);
			
			else PushNumStack(St, m / n);
		}
		
	}
	
	return PopNumStack(St);
}

int main()
{
    InitCharStack(S);

    char a[MAXSIZE]={0};
    char b[MAXSIZE]={0};

    InfixToSuffex(a,b);

    printf("The suffix expression is:%srn",b);
    int ans=CaculatValue(b,St);

    printf("The value of the expression is:%drn",ans);
    return 0;
}
 
样例输出 
 
 9+(3-1)*3+10/2
 Infix expression is:9+(3-1)*3+10/2 
 The suffix expression is:9#3#1#-3#*+10#2#/+
 The value of the expression is:20 
 
四、写在最后 
希望我们都能学好数据结构。

数据结构之栈的顺序存储结构及其应用

C/C++/C#相关栏目本月热门文章