《数据结构》课程教学资源（PPT课件）第3章 栈和队列

(2)销毁栈ClearStack(&s)释放栈s占用的全部存储空间*&s)void ClearStack(LiStackLiStack *p=s->next;while (p!-NULL)free(s);s=p;p=p->next;27

27 (2)销毁栈 ClearStack(&s) 释放栈s占用的全部存储空间。 void ClearStack(LiStack *&s) { LiStack *p=s->next; while (p!=NULL) { free(s); s=p; p=p->next; } }

(3)求栈的长度StackLength(s)从第一个数据结点开始扫描单链表，用记录访问的数据结点个数，最后返回值*Sint StackLength(LiStackint i-0;LiStack *p;p=s->next;while (p-NULL)i++;p=p->next;return(i);28

28 (3)求栈的长度 StackLength(s) 从第一个数据结点开始扫描单链表，用i记录访问 的数据结点个数，最后返回i值。 int StackLength(LiStack *s) { int i=0; LiStack *p; p=s->next; while (p!=NULL) { i++;p=p->next; } return(i); }

(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s->nex-=NULL，即单链表中没有数据结点。int StackEmpty(LiStack*Sreturn(s->next=-NULL);29

29 (4)判断栈是否为空 StackEmpty(s) 栈S为空的条件是s->next==NULL，即单链表中 没有数据结点。 int StackEmpty(LiStack *s) { return(s->next==NULL); }

(5)入栈Push(&s，e)将新数据结点插入到头结点之后void Push(LiStack *&s , ElemType e)LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p->data=e;p->next-s->next;/*插入*p结点作为第一个数据结点*/s->nextp;30

30 (5)入栈 Push(&s，e) 将新数据结点插入到头结点之后。 void Push(LiStack *&s，ElemType e) { LiStack *p; p=(LiStack *)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p结点作为第一个数据结点*/ s->next=p; }

(6)出栈Pop(&s, &e)在栈不为空的条件下，将头结点后继数据结点的数据域赋给e，然后将其删除int Pop(LiStack *&s, ElemType &e)LiStack *p;return0；/*栈空的情况*/if (s->next--NULL)p=s->next；/*p指向第一个数据结点*e=p->data;s->next=p->next;free(p);return 1;31

31 (6)出栈 Pop(&s, &e) 在栈不为空的条件下，将头结点后继数据结点的数 据域赋给e，然后将其删除。 int Pop(LiStack *&s, ElemType &e) { LiStack *p; if (s->next==NULL) return 0; /*栈空的情况*/ p=s->next; /*p指向第一个数据结点*/ e=p->data; s->next=p->next; free(p); return 1; }