C語言實現數據結構-棧
棧是僅在表尾進行插入、刪除操作的線性表。即棧 S= (a1, a2, a3, ………,an-1, an),其中表尾(即 an 端)稱為棧頂 /top,表頭(即 a1 端)稱為棧底/base。
由於只能在表尾進行操作,因此棧的運算規則就是「後進先出」(LIFO)
提起棧,最常見的用途就是調用函數了,例如JS裡面的執行棧,但是棧可以用於遞歸運算、簡化程序等等。
和線性表類似,棧也有兩種存儲結構——順序棧與鏈棧棧的順序存儲結構——順序棧
順序棧的表示與實現
用C語言表示棧的順序結構
#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct{ SElemType *base; // 棧底指針(始終指向棧底) SElemType *top; // 棧頂指針 int stacksize; // 當前棧的最大容量} SqStack;
用下圖表示就是
其中: 1. s.base 始終指向棧底 2. s.top 始終指向棧頂元素的下一個位置 3. s.base = NULL 表示棧結構不存在 4. s.top = s.base 表示棧空 5. top-base = stacksize 表示棧滿
順序棧的基本操作
1. 初始化棧
Status initStack(SqStack *S){ S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}
2. 棧判空
Status stackEmpty(SqStack* S) { return S.top == S.base;}
3. 判棧滿
Status stackFull(SqStack* S){ return ((S.top - S.base) == S.stacksize);}
4. 讀取棧頂元素
Status getTop(SqStack* S, ElemType e){ //返回棧S的棧頂元素,但棧頂指針保持不變 if(S.top == S.base) //棧為空 { printf("Stack is empty!"); return ERROR; } e = *(S.top-1); return OK;}
5. 入棧
Status push(SqStack* S, SElemType e){ if(S.top-S.base >= S.stacksize) //判滿 { //追加存儲空間 S.base = (ElemType*)realloc(S.base(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) exit(OVERFLOW); //上溢 S.top = S.base+S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; //棧頂指針後移,賦值 return OK;}
6. 出棧
Status pop(SqStack* S, SElemType *e){ //將棧S的棧頂元素彈出並返回 if(S.top == S.base) { printf("Stack is empty!"); return ERROR; } e = s->top; s->top--; return OK;}
棧的鏈式存儲結構——鏈棧
棧的鏈式存儲結構,也稱為鏈棧,它是一種限制運算的鏈表,即規定鏈表中的插入和刪除運算只能在鏈表開頭進行。
鏈棧的表示與實現
用C語言表示棧的鏈式結構
typedef struct SNode { SElemType data; struct SNode *next; }SNode, *LinkStack
鏈棧的基本操作
1. 初始化棧
void iniStack(LinkStack* top){ top = (LinkStack*)malloc(sizeof(SNode)); top->next = NULL;}
2. 進棧
Status push(LinkStack* top, SElemType e){ LinkStack* q; q = (LinkStack*)malloc(sizeof(SNode)); if (!q) exit(OVERFLOW); //存儲分配失敗 q->data = e; q->next = top->next; top->next = q; return OK;}
3. 出棧
Status pop(LinkStack* top, SElemType e){ LinkStack* q; if (!top->next) return ERROR; e = top->next->data; //取出棧頂元素的值 q = top->next; //q指向棧頂元素 top->next = q->next; //刪除棧頂元素 free (q); //釋放棧頂元素所佔的空間 return OK;}
4.取棧頂元素
Status getTop(LinkStack* top, SElemType e) { if (!top->next) return ERROR; else { e = top->next->data; return OK; } }
棧的典型應用
棧的典型應用,包括數字轉換問題、括弧匹配問題、表達式求值、遞歸中的漢諾塔等等。
這裡用棧對表達式求值做一個很簡單的解釋。
編寫演算法,用棧實現表達式3 * (7 - 2)求值。一個算術表達式是由操作數(x,y,z…)和算符(*, /, +, -, (, ), #)組成。其中演算法規則是:1. 從左算到右; 2. 先乘除, 後加減; 3. 先括弧內, 後括弧外.其中算符之間的優先順序如下圖在這個問題中,演算法的思想是:
為了實現算符優先演算法,可以設定兩個工作棧,OPND—存放操作數或運算結果,OPTR—存放運算符號。
1) 首先置操作數棧OPND為空棧,表達式的起始符#為運算符棧OPTR的棧底元素;2) 依次讀入表達式中的每個字元,若運算符是 「#」 且棧頂是 「#」,結束計算,返回OPND棧頂值。如果是操作數,則push(OPND,操作數),如果是運算符,則與OPTR棧頂元素進行比較,按優先順序進行操作。演算法的實現,偽代碼形式。
OperandType eval() { initstack(&OPTR); //初始化OPTR棧 push(&OPTR, "#"); initstack(&OPND); c = getchar(); while (c != "#") || getTop(OPTR) != "#") { if (!in(c,op)) //如果c是操作數 { push(&OPND); c = getchar(); } else //c是一個運算符 { r=precede(getTop(OPTR), c); // 比較兩個運算符的優先順序 switch(r) { case "<": //棧頂元素優先順序低 push(&OPTR, c); c=getchar(); break; case "=": //脫括弧並接受下一字元 pop(&OPTR, &x); c=getchar(); break; case ">": //退棧並將運算結果入棧 pop(&OPTR,&op); pop(&OPND,&b); pop(&OPND,&a); value=operate(a, op, b) ; push(&OPND, value); break; } } } return(getTop(OPND)); }
用一張圖來表示這個過程就是
棧的另一個重要的用途就是遞歸,在這裡就不細說了,orz,我先歇會下次再說_(:D)∠)_。。。
歡迎批評指正!推薦閱讀:
TAG:数据结构 |