堆疊的實作：括號的決議

一、問題引入

在學習堆疊的程序中，教材有一個案例：利用堆疊結果決議括號的匹配問題，括號問題：[({}{})]，說明 [] 、() 、{} 稱為一對，

號碼位置對應的括號之間進行匹配，結果：0-7、 1-6、 2-3、 4-5

二、程序記錄

?? 基于順序堆疊實作

利用堆疊的特性：先進后出 ，對括號進行匹配輸出

對堆疊的基本操作進行抽象定義函式：

• 堆疊初始化

• 入堆疊

• 出堆疊

• 堆疊銷毀

2-1 資料結構定義

#define MAXSIZE 100 // 順序堆疊存盤空間的初始分配量

#define ERROR -1
#define OK 0
#define OVERFLOW 1

typedef struct
{
	char bracket;  // 存盤括號字符
	int  idx;      // 存盤括號字符索引
}BracketInfo;

typedef struct
{
	BracketInfo *base;      // 堆疊底指標
	BracketInfo *top;       // 堆疊頂指標
	int  stack_size;        // 堆疊可用的最大容量
}SqStack_T;

2-2 堆疊操作定義

• 堆疊初始化

static int stack_init(SqStack_T *sq_stack_pt)
{
	/* base為堆疊底指標，初始化完成后，堆疊底指標base始終指向堆疊底位置.
	 * 若base的值為NULL，則表明堆疊結構不存在， 
	*/
	sq_stack_pt->base = (BracketInfo *)malloc(MAXSIZE * sizeof(BracketInfo));
	if (NULL == sq_stack_pt->base)
	{
		printf("malloc memory fail\n");
		exit(OVERFLOW); // 退出程式
	}
	sq_stack_pt->top = sq_stack_pt->base;
	sq_stack_pt->stack_size = MAXSIZE;
	return OK;
}

• 入堆疊

static int stack_push(SqStack_T *sq_stack_pt, BracketInfo elem)
{
	// 入堆疊前，先判斷是否堆疊滿
	if (sq_stack_pt->base - sq_stack_pt->top == sq_stack_pt->stack_size)
		return ERROR;
	// 元素入堆疊，堆疊頂指標top+1
	*(sq_stack_pt->top) = elem;
	(sq_stack_pt->top)++;
	return OK;
}

• 出堆疊

static int stack_pop(SqStack_T *sq_stack_pt, BracketInfo *elem)
{
	// 出堆疊前，先判斷是否堆疊空
	if (sq_stack_pt->top == sq_stack_pt->base)
	{
		
		return ERROR;
	}
	// 元素出堆疊，堆疊頂指標top-1
	sq_stack_pt->top--;
	*elem = *(sq_stack_pt->top);
	return OK;
}

• 取堆疊頂元素

static BracketInfo stack_top_element_get(SqStack_T sq_stack_t)
{
	BracketInfo elem = { 0 };
	if (sq_stack_t.top != sq_stack_t.base)
		elem = *(sq_stack_t.top - 1);
	return elem;
}

• 堆疊銷毀

static int stack_destory(SqStack_T *sq_stack_pt)
{
	if (sq_stack_pt->base != NULL)
		free(sq_stack_pt->base);
	return OK;
}

2-3 main函式

?? 資料結構的定義和堆疊操作的定義都放在檔案 sq_stack.h 和 sq_stack.c 中

#include "sq_stack.h"
#include <stdio.h>

int main(void)
{
	SqStack_T sq_stack_t;
	stack_init(&sq_stack_t);
	char buffer[50] = { "[({}{})]" };
	int buffer_len = strlen(buffer);
	for (int i = 0; i < buffer_len; i++)
	{
		if (buffer[i] == '[' || buffer[i] == '(' || buffer[i] == '{')
		{
			BracketInfo elem = { 0 };
			elem.idx = i;
			elem.bracket = buffer[i];
			if (ERROR == stack_push(&sq_stack_t, elem)) // 入堆疊
				printf("stack full\n");
		}
		else if (buffer[i] == ']' || buffer[i] == ')' || buffer[i] == '}') 
		{
			BracketInfo elem_top, elem;
			elem_top = stack_top_element_get(sq_stack_t);
			if (buffer[i] == ']')
			{
				if (elem_top.bracket == '[')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出堆疊
						printf("stack empty\n");
				}
			}
			else if (buffer[i] == ')')
			{
				if (elem_top.bracket == '(')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出堆疊
						printf("stack empty\n");
				}
			}
			else if (buffer[i] == '}')
			{
				if (elem_top.bracket == '{')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出堆疊
						printf("stack empty\n");
				}
			}
			printf("%c %c (%d,%d)\n", elem.bracket, buffer[i], elem.idx, i);
		}
	}
	stack_destory(&sq_stack_t);
	return 0;
}

三、反思總結

堆疊(stack) 是限定僅在表尾進行插入或洗掉操作的線性表，
因此，對堆疊來說，表尾端有其特殊含義，稱為堆疊頂(top), 相應地，表頭端稱為堆疊底(bottom)，不含元素的空表稱為空堆疊

四、參考參考

資料結構第二版：C語言版 【嚴蔚敏】

標籤：其他

上一篇：Activiti 7 啟動流程實體

下一篇：C++記憶體重疊