C語言描述=====》棧的設(shè)計(jì)與實(shí)現(xiàn)??人生財(cái)富庫積累

#ifndef?_MY_STACK_H_

#define?_MY_STACK_H_

?

typedef?void?Stack;

?

Stack*?Stack_Create();

?

void?Stack_Destroy(Stack*?stack);

?

void?Stack_Clear(Stack*?stack);

?

int?Stack_Push(Stack*?stack,?void*?item);

?

void*?Stack_Pop(Stack*?stack);

?

void*?Stack_Top(Stack*?stack);

?

int?Stack_Size(Stack*?stack);

?

#endif?//_MY_STACK_H_

?

頭文件

#ifndef??__MY_SEQLIST_H__?

#define?__MY_SEQLIST_H__

?

typedef?void?SeqList;

typedef?void?SeqListNode;

?

SeqList*?SeqStack_Create(int?capacity);

?

void?SeqStack?_Destroy(SeqStack?*?list);

?

void?SeqStack?_Clear(SeqStack?*?list);

?

int?SeqStack?_Length(SeqStack?*?list);

?

int?SeqStack?_Capacity(SeqStack?*?list);

?

int?SeqStack?_Insert(SeqStack?*?list,?SeqListNode*?node,?int?pos);

?

SeqListNode*?SeqList_Get(SeqList*?list,?int?pos);

?

SeqListNode*?SeqList_Delete(SeqList*?list,?int?pos);

?

#endif??//__MY_SEQLIST_H__

?

頭文件

#ifndef?_MY_LINKSTACK_H_

#define?_MY_LINKSTACK_H_

?

typedef?void?LinkStack;

?

LinkStack*?LinkStack_Create();

?

void?LinkStack_Destroy(LinkStack*?stack);

?

void?LinkStack_Clear(LinkStack*?stack);

?

int?LinkStack_Push(LinkStack*?stack,?void*?item);

?

void*?LinkStack_Pop(LinkStack*?stack);

?

void*?LinkStack_Top(LinkStack*?stack);

?

int?LinkStack_Size(LinkStack*?stack);

?

#endif?//_MY_LINKSTACK_H_

應(yīng)用1：就近匹配?

幾乎所有的編譯器都具有檢測括號(hào)是否匹配的能力

如何實(shí)現(xiàn)編譯器中的符號(hào)成對(duì)檢測？

#include?<stdio.h>?int?main()?{?int?a[4][4];?int?(*p)[4];?p?=?a[0];?return?0;?

?

算法思路

從第一個(gè)字符開始掃描

當(dāng)遇見普通字符時(shí)忽略，

當(dāng)遇見左符號(hào)時(shí)壓入棧中

當(dāng)遇見右符號(hào)時(shí)從棧中彈出棧頂符號(hào)，并進(jìn)行匹配

匹配成功：繼續(xù)讀入下一個(gè)字符

匹配失敗：立即停止，并報(bào)錯(cuò)

結(jié)束：

成功:?所有字符掃描完畢，且棧為空

失敗：匹配失敗或所有字符掃描完畢但棧非空

當(dāng)需要檢測成對(duì)出現(xiàn)但又互不相鄰的事物時(shí)

可以使用棧“后進(jìn)先出”的特性

棧非常適合于需要“就近匹配”的場合

?

計(jì)算機(jī)的本質(zhì)工作就是做數(shù)學(xué)運(yùn)算，那計(jì)算機(jī)可以讀入字符串

“9?+?(3?-?1)?*?5?+?8?/?2”并計(jì)算值嗎？

應(yīng)用2：中綴?后綴

計(jì)算機(jī)的本質(zhì)工作就是做數(shù)學(xué)運(yùn)算，那計(jì)算機(jī)可以讀入字符串

“9?+?(3?-?1)?*?5?+?8?/?2”并計(jì)算值嗎？

后綴表達(dá)式??==？符合計(jì)算機(jī)運(yùn)算

波蘭科學(xué)家在20世紀(jì)50年代提出了一種將運(yùn)算符放在數(shù)字后面的后綴表達(dá)式對(duì)應(yīng)的，

我們習(xí)慣的數(shù)學(xué)表達(dá)式叫做中綴表達(dá)式===》符合人類思考習(xí)慣

?

實(shí)例：

5?+?4=>?5?4?+??

1?+?2?*?3?=>?1?2?3?*?+??

8?+?(?3?–?1?)?*?5?=>?8?3?1?–?5?*?+??

中綴表達(dá)式符合人類的閱讀和思維習(xí)慣

后綴表達(dá)式符合計(jì)算機(jī)的“運(yùn)算習(xí)慣”

如何將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式？

中綴轉(zhuǎn)后綴算法：

遍歷中綴表達(dá)式中的數(shù)字和符號(hào)

對(duì)于數(shù)字：直接輸出

對(duì)于符號(hào)：

左括號(hào)：進(jìn)棧??

運(yùn)算符號(hào)：與棧頂符號(hào)進(jìn)行優(yōu)先級(jí)比較

若棧頂符號(hào)優(yōu)先級(jí)低：此符合進(jìn)棧??（默認(rèn)棧頂若是左括號(hào)，左括號(hào)優(yōu)先級(jí)最低）

若棧頂符號(hào)優(yōu)先級(jí)不低：將棧頂符號(hào)彈出并輸出，之后進(jìn)棧

右括號(hào)：將棧頂符號(hào)彈出并輸出，直到匹配左括號(hào)

遍歷結(jié)束：將棧中的所有符號(hào)彈出并輸出

中綴轉(zhuǎn)后綴