- 老师版
- 创建
- 压栈
- 出栈
- 测试代码
- 运行结果
- 自己版
- 创建
- 压栈
- 出栈
- 运行结果
- 总结
- 栈的应用--括号匹配
- 运行结果
今天敲得是栈。栈是一种特殊的存储方式，这种方式就像往箱子里面放东西，先放进去的后拿出来，后放进去的先拿出来。老师是用数组的形式实现，我用链表的形式实现。来看代码吧。
老师版 创建#include#include #define STACK_MAX_SIZE 10 typedef struct CharStack{ int top; int data[STACK_MAX_SIZE]; }*CharStackPtr; CharStackPtr CharStackInit() { CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack)); resultPtr->top=-1; return resultPtr; }
我们在结构体里设置了一个名为top的变量，它的作用就是始终指向最顶部，也就是最后放进去的元素。
压栈
这副动态图很形象的解释了压榨，每放入一个元素，都使top往后移一位，使之始终指向栈顶的元素。
void push(CharStackPtr paraStackPtr,int paraValue)
{
if((paraStackPtr->top)>=STACK_MAX_SIZE -1)
{
printf("Can not push element:stack is full.");
return;
}
paraStackPtr->top ++;
paraStackPtr->data[paraStackPtr->top] = paraValue;
}
出栈
出栈操作也十分简单，元素移出，让top前移。
char pop(CharStackPtr paraStackPtr)
{
if(paraStackPtr->top<0)
{
printf("Can not pop element:stack empty.rn");
return ' ';
}
paraStackPtr->top --;
return paraStackPtr->data[paraStackPtr->data +1];
}
测试代码
void pushPopTest() {
char ch;
int i;
printf("---- pushPopTest begins. ----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);
}
for ( i = 0; i < 3; i ++) {
ch = pop(tempStack);
printf("Pop %c.rn", ch);
outputStack(tempStack);
}
printf("---- pushPopTest ends. ----rn");
}
int main() {
pushPopTest();
}
运行结果
---- pushPopTest begins. ---- 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. Can not push element:stack is full.a b c d e f g h i j Pushing l. Can not push element:stack is full.a b c d e f g h i j 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 ---- pushPopTest ends. ----自己版
我自己写了链式栈的基本算法的代码，附在下方
创建链式栈需要两个结构体，一个定义节点，另外一个定义栈顶和栈底。
typedef struct Node
{
int data;
struct Node *next;
}NODE,*PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
}STACK,*PSTACK;
void initStack(PSTACK pS)
{
printf("initrn");
pS->pTop = (PNODE)malloc(sizeof(NODE));
pS->pBottom = pS->pTop ;
pS->pTop ->next=NULL;
return;
}
在写创建这代码的时候，我遇到了一个令我百思不得其解的问题。因为创建其实理解起来很简单，让栈顶和栈底相等，然后栈顶指向为空即可。
一开始，我让栈顶和栈底相等是这样写的：
pS->pTop = pS->pBottom ;
但是却怎么也无法压栈和出栈，我甚至为此把所有代码重新敲了一遍。后来，再一次对我的代码的修改时我将这两者互换了位置，突然就全部都运行了。
然后我看了这一小段代码的网课，原来在我已经给pTop动态分配了内存，但是pBottom却仍然是一堆垃圾值，而我们应该给pBottom赋值并且使他们指向同一处。而把pTop赋值给pBottom才能使他们指向同一处。
void pushStack(PSTACK pS,int val)
{
printf("pushrn");
PNODE p;
p=(PNODE)malloc(sizeof(NODE));
p->data =val;
p->next =pS->pTop ;
pS->pTop =p;
}
出栈
void popStack(PSTACK pS)
{
printf("poprn");
PNODE p;
p=(PNODE)malloc(sizeof(NODE));
p=pS->pTop ;
pS->pTop =p->next ;
free(p);
p=NULL;
}
运行结果
init 11 push push push push 22 print 4 3 2 1 33 pop print 3 2 1总结
实际上栈的算法很好理解，无非是先进后出，后进先出八字。
但是栈虽然简单，却能解决生活中很多问题，比如下面的括号匹配问题。
栈的应用–括号匹配由于栈的实现和之前的完全一样，所以这里我只列出最主要的括号匹配部分的代码。
bool bracketMatching(char* String, int Length)
{
CharStackPtr stack = initStack();
int i;
char tempch,popch;
pushStack(stack,'#');
for(i=0;i
tempch=String[i];
switch(tempch)
{
case '(':
case '[':
case '{':
pushStack(stack,tempch);
break;
case')':
popch=popStack(stack);
if(popch!='(')
{
return false;
}
break;
case']':
popch=popStack(stack);
if(popch!='[')
{
return false;
}
break;
case'}':
popch=popStack(stack);
if(popch!='}')
{
return false;
}
break;
default:
break;
}
}
popch=popStack(stack);
if(popch!='#')
{
return false;
}
return true;
}
这一段代码的逻辑思想也很简单，理解之后敲起来就十分顺手。当我们在表达式中遇到了‘（，【，}’这几个括号时，我们进行压栈操作，将这几个括号存入栈中，接着，如果我们遇到了‘），】，}’这几个括号中的一个时，我们进行出栈操作，如果此时弹出的元素和此时遇到的括号对应，就接着循环找到下一个括号，否则就返回‘0’，也就是不匹配。
在代码中，我们还设置了“#”标识符，当我们匹配结束却仍然没有弹出“#”，证明我们多了一个括号没有匹配到，也会返回“0”。
另外，代码中的变量和老师的略有差异，因为我是自己敲得，所以改变了部分变量名。
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? 0
Is the expression ')(' bracket matching? 0
