数据结构——C语言描述第3章-栈和队列.pptxVIP

数据结构——C语言描述（慕课版）;;栈;栈的基本概念：;栈的抽象数据类型ADT：;栈的抽象数据类型：;;顺序栈;顺序栈;顺序栈;顺序栈结构定义及基本操作的实现;顺序栈结构定义及基本操作的实现;顺序栈结构定义及基本操作的实现;顺序栈结构定义及基本操作的实现;顺序栈结构定义及基本操作的实现;好处：当其中的某个栈满时，可能其它栈尚余许多空间，这时可以让其它的堆栈进行左右移动，然后让该栈继续获得一些新的空间，从而可以继续进行进栈活动。;;;链式栈;链式栈;链式栈实现;voidinitialize(linkStack*s){s-Top=NULL;};//初始化栈，使其为空栈

intisEmpty(linkStack*s){return(s-Top==NULL);};//栈为空返回1,否则返回0。

intisFull(linkStack*s){return0;};//栈满1，否则0。结点空间不连续，故总能满足

elemTypetop(linkStack*s);

voidpush(linkStack*s,elemTypee);

voidpop(linkStack*s);

voidclear(linkStack*s);

voiddestroy(linkStack*s){clear(s);};

?

elemTypetop(linkStack*s)

{

if(!s-Top)exit(1);//栈空

returns-Top-data;

};voidpush(linkStack*s,elemTypee)

{Node*tmp=(Node*)malloc(sizeof(Node));//创建空间

?tmp-data=e;tmp-next=s-Top;//先武装自己

?s-Top=tmp;//链入栈

}

voidpop(linkStack*s)

{Node*tmp;

if(!s-Top)exit(1);//栈空

?

tmp=s-Top;//用tmp记住原栈顶结点空间，用于弹栈后的空间释放

s-Top=s-Top-next;//实际将栈顶结点弹出栈

?free(tmp);//释放原栈顶结点空间

};voidclear(linkStack*s)

{Node*tmp;

tmp=s-Top;

?

while(tmp)

{s-Top=s-Top-next;

free(tmp);

tmp=s-Top;

}

};;;符号配对;;initialize(s);//栈初始化

printf(Inputthestring:);

scanf(%s,str);

?

i=0;

ch=str[i++];

while(ch!=\0){

switch(ch){

case(:

push(s,ch);

break;

case):

if(isEmpty(s)){

//读入一个闭括号，栈却空，找不到匹配的开括号

printf(“Anopeningbracket‘(’isexpected!\n”);return1;

}; elsepop(s);

break;

}

ch=str[i++];

}

if(!isEmpty(s))//式子读入结束，发现栈中还有多

余的开括号

printf(Aclosingbracket)isexpected!\n);

?

return0;

};;表达式计算;表达式计算;表达式计算;;;表达式转换为后缀式：;表达式转换为后缀式：;;;;;;;;队列可以看作是插入删除位置操作受限的线性表，它的插入和删除分别在表的两端进行。;?;Operations:;队列的抽象数据类型：;;队列的顺序存储及实现;;队列操作中的Rear和Front;队列及操作的实现;队列及操作的实现;队列及操作的实现;队列及操