《數(shù)據(jù)結(jié)構(gòu)（C語言版）》棧的實(shí)現(xiàn)與應(yīng)用
清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第三章棧中順序棧的代碼實(shí)現(xiàn)，并且完成了數(shù)制轉(zhuǎn)換、括號(hào)匹配的檢驗(yàn)、行編輯程序等功能，代碼（含詳細(xì)注釋）在450行左右
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯）?
//順序棧的表示和實(shí)現(xiàn)
//用順序棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換、括號(hào)匹配檢查、行編輯程序
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100//存儲(chǔ)空間初始分配量
#define STACKINCREMENT 10//存儲(chǔ)空間分配增量
typedef int SElemType;
typedef int Status;
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;//當(dāng)前已分配的存儲(chǔ)空間，以元素為單位
}Sqstack;
/*
通常top指示真正的棧頂元素之上的下標(biāo)地址，初始值指向棧底
base始終指向棧底的位置，若base的值為NULL則表明棧結(jié)構(gòu)不存在
棧空：top==base
棧滿：top-base==stacksize
*/
Status InitStack(Sqstack& S);//初始化一個(gè)空棧
Status DestoryStack(Sqstack& S);//銷毀棧
Status ClearStack(Sqstack& S);//把S置為空棧
Status StackEmpty(Sqstack S);//判斷棧是否為空
int StackLength(Sqstack S);//求棧的長度
Status GetTop(Sqstack& S, SElemType& e);//返回棧頂元素，若為空則返回ERROR
Status Push(Sqstack& S, SElemType e);//順序棧的入棧
Status Pop(Sqstack& S, SElemType& e);//順序棧的出棧
Status StackTraverse(Sqstack S, Status(*visit)(SElemType*));//從棧底到棧頂一次對棧中每個(gè)元素調(diào)用函數(shù)visit()，一旦visit()失敗則操作失敗
Status ShowStack(SElemType* p);//打印順序棧中的元素(從棧底到棧頂）
Status ShowStack2(SElemType* p);//該打印函數(shù)是為行編輯函數(shù)服務(wù)的，因?yàn)橐蛴∽址?/p>
void conversion();//對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其值等值得八進(jìn)制數(shù)
Status CheckParenMatching(char* str);//括號(hào)匹配檢驗(yàn)
void LineEdit();//利用字符棧S，從終端接受一行并傳送至調(diào)用過程的數(shù)據(jù)區(qū)
void Menu1()
{
printf("******************************\n");
printf("********0.退出本次使用********\n");
printf("********1.棧的基本功能********\n");
printf("********2.不同數(shù)制轉(zhuǎn)換********\n");
printf("********3.括號(hào)匹配檢驗(yàn)********\n");
printf("********4.行編輯程序**********\n");
printf("******************************\n");
}
void Menu2()
{
printf("**************************\n");
printf("********0.返回上步********\n");
printf("********1.入? ? 棧********\n");
printf("********2.出? ? 棧********\n");
printf("********3.求 棧 長********\n");
printf("********4.求 棧 頂********\n");
printf("********5.打 印 棧********\n");
printf("********6.置 空 棧********\n");
printf("********7.銷 毀 棧********\n");
printf("********8.判斷空棧********\n");
printf("**************************\n");
}
int main()
{
int option1 = -1;
int option2 = -1;
int value = 0;
char str[100] = { 0 };
Sqstack Mystack;
InitStack(Mystack);
Menu1();
while (scanf("%d", &option1) != EOF)
{
while (getchar() != '\n');
switch(option1)
{
case 1:
Menu2();
while (scanf("%d", &option2) != EOF)
{
while (getchar() != '\n');
switch (option2)
{
case 1:
printf("請輸入你要入棧的元素：");
while (scanf("%d", &value) != 1)
{
printf("你輸入了非法字符，請重新輸入:");
while (getchar() != '\n');
}
if (Push(Mystack, value))
{
printf("入棧成功！\n");
}
break;
case 2:
if (Pop(Mystack, value))
{
printf("出棧成功！\t您出棧的元素為%d\n", value);
}
else
{
printf("該順序棧已空！不能出棧！\n");
}
break;
case 3:
printf("該順序棧的棧長為：%d\n", StackLength(Mystack));
break;
case 4:
if (GetTop(Mystack, value))
{
printf("該順序棧棧頂元素為：%d\n", value);
}
else
{
printf("該順序棧為空棧！\n");
}
break;
case 5:
if (StackEmpty(Mystack))
{
printf("該順序棧為空棧！\n");
}
else
{
printf("從棧底到棧頂依次為：");
if (StackTraverse(Mystack, ShowStack))
{
printf("\n");
}
}
break;
case 6:
if (ClearStack(Mystack))
{
printf("棧已置空！\n");
}
break;
case 7:
if (DestoryStack(Mystack))
{
printf("棧已銷毀！\n");
}
break;
case 8:
if (StackEmpty(Mystack))
{
printf("該順序棧為空棧！\n");
}
else
{
printf("該順序棧非空！\n");
}
case 0:
break;
default:
printf("你輸入了非法字符，請重新輸入\n");
break;
}
if (option2 == 0)
{
break;
}
Menu2();
}
break;
case 2:
conversion();
break;
case 3:
printf("您可以用此功能檢查形如5-{3-[5*(9/3)-4]}的算術(shù)表達(dá)式括號(hào)是否匹配\n");
printf("請輸入表達(dá)式：");
fgets(str, 100, stdin);
if (CheckParenMatching(str))
{
printf("括號(hào)成功匹配!\n");
}
else
{
printf("括號(hào)不匹配!\n");
}
break;
case 4:
printf("您可以用此功能在不小心輸入錯(cuò)誤時(shí)用#代替退格符Backspace，用@代替退行符\n");
printf("例如你輸入了如下兩段字符：\n");
printf("whli##ilr#e(s#*s)\n");
printf("? outcha@putchar(*s=#++);\n");
printf("則實(shí)際有效的是下列兩行\(zhòng)n");
printf("while(*s)\n");
printf("putchar(*s++);\n");
printf("當(dāng)你按住Ctrl+z可停止輸入\n");
printf("請輸入一串字符：\n");
LineEdit();
break;
case 0:
printf("感謝使用！\n");
exit(0);
default:
printf("你輸入了非法字符，請重新輸入\n");
}
Menu1();
}
return 0;
}
Status InitStack(Sqstack& S)//初始化一個(gè)空棧
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(Sqstack& S)//銷毀棧
{
if (S.base)
{
free(S.base);
S.stacksize = 0;
S.top = NULL;
S.base = NULL;
}
return OK;
}
Status ClearStack(Sqstack& S)//把S置為空棧
{
if (S.base)
{
S.top = S.base;
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)//返回棧頂元素，若為空則返回ERROR
{
if (S.top == S.base)
{
return ERROR;
}
e = *(S.top - 1);
return OK;
}
Status Push(Sqstack& S, SElemType e)//順序棧的入棧
{
if (S.top - S.base >= S.stacksize)
{
/*
這里和課本有一點(diǎn)點(diǎn)不同，我是先realloc一個(gè)指針為New_ptr的空間，再把這個(gè)指針分配給S.base
原因是visual studio太高級了，它覺得realloc不安全，可能會(huì)引出一個(gè)內(nèi)存泄露的問題
當(dāng)realloc分配失敗的時(shí)候，會(huì)返回NULL。如果直接賦值給S.base的話，S.base的內(nèi)存是沒有被釋放的
如果直接將realloc的返回值賦給S.base，那么當(dāng)申請內(nèi)存失敗時(shí)，就會(huì)造成S.base原來指向的內(nèi)存丟失，造成泄露。
*/
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = 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 StackTraverse(Sqstack S, Status(*visit)(SElemType*))//從棧底到棧頂一次對棧中每個(gè)元素調(diào)用函數(shù)visit()，一旦visit()失敗則操作失敗
{
while (S.top != S.base)
{
if (!visit(S.base++))
{
return ERROR;
}
}
return OK;
}
Status ShowStack(SElemType* p)//打印順序棧中的元素(從棧底到棧頂）
{
printf("%d ", *p);
return OK;
}
Status ShowStack2(SElemType* p)//該打印函數(shù)是為行編輯函數(shù)服務(wù)的，因?yàn)橐蛴∽址?/p>
{
printf("%c", *p);
return OK;
}
void conversion()//對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其值等值得八進(jìn)制數(shù)
{
Sqstack S;
int N = 0;
SElemType e = 0;
InitStack(S);
printf("請輸入你想轉(zhuǎn)換的數(shù)：");
while (scanf("%d", &N) != 1)
{
printf("你輸入了非法字符，請重新輸入:");
while (getchar() != '\n');
}
while (N)
{
Push(S, N % 8);
N = N / 8;
}
printf("轉(zhuǎn)換成八進(jìn)制后的數(shù)為：");
while (!StackEmpty(S))
{
Pop(S, e);
printf("%d", e);
}
printf("\n");
}
Status CheckParenMatching(char* str)//括號(hào)匹配檢驗(yàn)
/*
算法具體描述如下
依次讀取代碼字符串中的字符
? ?若是非括號(hào)字符，則忽略并繼續(xù)讀取下一個(gè)字符；
? ?若是左括號(hào)字符，則壓棧；
? ?否則為右括號(hào)，與棧頂元素進(jìn)行匹配：
? 若棧空，則是多余的右括號(hào)，報(bào)錯(cuò)返回；
? 否則
若匹配成功，則棧頂元素彈棧，繼續(xù)讀取下一個(gè)字符；
否則匹配錯(cuò)誤，報(bào)錯(cuò)返回；
代碼字符串遍歷結(jié)束時(shí)：
? ?若?？眨瑒t匹配成功，正確返回；
? ?否則有左括號(hào)還沒匹配，報(bào)錯(cuò)返回。
*/
{
Sqstack S;
InitStack(S);
int Length = strlen(str);
SElemType e = 0;
for (int i = 0; i < Length; i++)
{
switch (str[i])
{
case '{':
case '[':
case '(':
Push(S, str[i]);
break;
case '}':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '{')
{
return ERROR;
}
break;
case ']':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '[')
{
return ERROR;
}
break;
case ')':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '(')
{
return ERROR;
}
break;
default:
break;
}
}
if (!StackEmpty(S))
{
return ERROR;
}
return OK;
}
void LineEdit()//利用字符棧S，從終端接受一行并傳送至調(diào)用過程的數(shù)據(jù)區(qū)
{
Sqstack S;
InitStack(S);
SElemType c = 0;
char ch = getchar();
while (ch != EOF)
{
while (ch != EOF && ch != '\n')
{
switch (ch)
{
case '#':
Pop(S, c);
break;
case '@':
ClearStack(S);
break;
default:
Push(S, ch);
}
ch = getchar();
}
printf("你最終輸入的字符為：");
if (StackTraverse(S, ShowStack2))
{
printf("\n");
}
printf("已將你所編輯的字符傳入到數(shù)據(jù)區(qū)\n");
ClearStack(S);
if (ch != EOF)
{
ch = getchar();
}
}
DestoryStack(S);
}
