数据结构c语言PPT4

《数据结构c语言PPT4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章限定性线性表—栈和队列3.1栈3.1.1栈的定义及基本运算3.1.2栈的存储结构和实现3.1.3栈的应用3.2队列3.2.1队列的定义及基本运算3.2.2队列的存储结构和实现3.2.3队列的应用3.1栈1.栈的定义限定仅在表尾进行插入或删除操作的线性表。S=(a1,a2,…,an)栈底(Bottom)：表头端称为栈底。栈顶(Top)：表尾端称为栈顶。进栈(入栈)：栈的插入操作。出栈(退栈)：删除操作。空栈：不含元素的空表。栈底元素：a1；栈顶元素：an2.栈的特点“很窄的死胡同”后进先出(LastInFirstOut)，简称LIFO结构。栈又称后进先

2、出线性表。3.栈的基本运算初始化InitStack(&S)。构造一个空栈入栈Push(&S,e)。栈S已经存在，插入e为新的栈顶元素出栈Pop(&S,&e)。栈S存在且非空，删除栈顶元素，e返回读栈顶元素GetTop(S,&e)。栈S存在且非空，用e返回栈顶元素判栈空StackEmpty(S)。栈S存在，若为空栈，返回真，否则假4.栈的表示和实现线性表顺序表链表单链表双链表循环链表双向单向栈顺序栈链栈3.1.2栈的存储结构和实现顺序栈－－栈的顺序存储结构…a1a2an-1an线性表anan-1...a2a1栈栈底栈顶6F28an6F26an-1......6

3、F02a26F00a1栈的顺序存储映象basetop顺序栈的类型定义typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈已分配的空间大小}SqStack;//动态分配typedefstruct{{SElemTypedata[MAXSIZE];inttop;}SqStack;//静态分配顺序栈SqStackS;①栈结构不存在S.base=NULL;②空栈S.base=S.top;③栈满S.top–S.base>=S.stacksize;①空栈top=0;②栈满top=

4、MAXSIZE;顺序栈－－栈的顺序存储结构6F28an6F26an-1......6F02a26F00a1栈的顺序存储映象basetop顺序栈基本操作的实现StackEmpty():top==basePush(e):*top++=ePop(e):e=*--topGettop():e=*(top-1)思考：为何不用top指向栈顶元素？top指针始终指向栈顶元素的下一位置初始化InitStack(SqStack&S){S.base=S.top=(SElemType*)malloc(…);if(!S.base)exit(OVERFLOW);S.stacksize=

5、STACK_INIT_SIZE;returnOK;}读栈顶元素GetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}入栈Push(SqStack&S,SElemTypee){if(S.top–S.base>=S.stacksize){S.base=(SElemType*)realloc(…);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*

6、S.top++=e;//*S.top=e;S.top++;returnOK;}a3出栈Pop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;//--S.top;e=*S.top;returnOK;}链栈typedefstructSTNode{SElemTypedata;structSTNode*next;}STNode,*LinkStack;栈顶结点栈底结点栈顶指针：链栈由栈顶指针S唯一确定链栈本身无容量限制，在用户内存空间的范围内不会出现栈满情况初始化InitStack(Lin

7、kStack&S){S=NULL;returnOK;}读栈顶元素GetTop(LinkStackS,SElemType&e){if(S==NULL)returnERROR;e=S->data;returnOK;}入栈Push(LinkStack&S,SElemTypee){p=(LinkStack)malloc(sizeof(STNode));if(!p)exit(OVERFLOW);p->data=e;①p->next=S;②S=p;returnOK;}出栈Pop(LinkStack&S,SElemType&e){if(S==NULL)returnERRO

8、R;e=S->data;①p=S;②S=S->nex