第3章 栈和队列 3．1 栈 3．2 队列 3．3 应用.

Presentation on theme: "第3章 栈和队列 3．1 栈 3．2 队列 3．3 应用."— Presentation transcript:

1 第3章 栈和队列 3．1 栈 3．2 队列 3．3 应用

2 汉诺塔 进 出 排队买票 进 出 栈和队列是两种重要的线性结构 栈和队列是操作受限的线性表

3 3．1 栈 3.1.1 栈的基本概念 进栈（Push） 出栈（Pop） 栈顶 top en-1 en-2 … e1 栈底bottom e0

4 栈的基本运算 ： InitStack(s)初始化操作 IsEmpty(s)判断栈空函数 IsFull(s)判断栈满函数
Push(s，x)压栈操作 Pop(s)出栈函数 GetTop(s)获取栈顶元素函数 EmptyStack(s)清空栈操作 DestroyStack ()销毁栈

5 3.1.2栈的顺序存储结构 栈的顺序存储结构称为顺序栈 A B C top -1 4 3 2 1
(a)空栈 （b）元素A进栈 （c）元素B、C进栈 （ d）出栈一次 （ e）出栈二次

6 顺序栈类型定义如下： #define StackSize /*顺序栈的初始分配空间*/ typedef struct sqst { DataType data[StackSize]; /*栈中元素*/ int top; /*栈指针*/ }SeqStack;

7 顺序栈的基本运算 ： void InitStack(SeqStack *sq) {
(1)初始化栈运算算法 创建一个空栈，并将栈顶下标top初始化为-1。 void InitStack(SeqStack *sq) { sq=(SeqStack *)malloc(sizeof(SqStack)); sq->top=-1 ; }

8 (2)进栈运算算法 { if(sq->top== StackSize-1)/*栈满*/ return 0; else
int Push(SeqStack *sq,DataType x) { if(sq->top== StackSize-1)/*栈满*/ return 0; else sq->top++; sq->data[sq->top]=x ; return 1; } }

9 (3)出栈运算算法 int Pop(SeqStack *sq,DataType x) { if(sq->top==-1) /*栈空*/ return 0; else { x=sq->data[sq->top]; sq->top--; return 1; } }

10 (4)取栈顶元素运算算法 int GetTop(SeqStack *sq,DataType x) {
if(sq->top==-1) /*栈空*/ return 0; else x=sq->data[sq->top]; return 1; }

11 (5)判断栈空运算算法 int StackEmpty(SeqStack *sq) { if(sq->top==-1)
return 1; else return 0; }

12 struct stnode *next ; /*指针域*/
3．1．3栈的链式存储结构 … ∧ ls data next 栈顶指针 栈顶 栈底 typedef struct stnod { DataType data; /*存储结点数据*/ struct stnode *next ; /*指针域*/ }LinkStack;

13 链栈的基本运算算法： (1)初始化栈运算算法 void InitStack(LinkStack *ls) { ls=NULL; }

14 (2)判断栈空运算算法 int StackEmpty(LinkStack *ls) { if(ls==NULL) return 1;
else return 0;}

15 (3)进栈运算算法 void Push(LinkStack *ls,DataType x) { LinkStack *p;
p=(LinkStack*)malloc(Sizeof(LinkStack)); p->data=x; p->next=ls; ls=p; }

16 (4)出栈运算算法 { LinkStack *p; if(ls==NULL) /*栈空，下溢出*/ return 0; else
int Pop(LinkStack *ls，DataType x) { LinkStack *p; if(ls==NULL) /*栈空，下溢出*/ return 0; else { p=ls; x=p->data; ls=p->next; free(p); return 1; }}

17 (5)取栈顶元素运算算法 int GetTop(LinkStack*ls,DataType x) {
if(ls==NULL) /*栈空，下溢出*/ return 0; else x=ls->data; return 1; } }

18 3．2 队列 3．2．1队列的基本概念 队列限制插入在一端进行，删除在另一端进行的线性表。 出列 入列 队尾（rear） 队首（front）

19 队列的基本操作： 1)InitQueue(Q)：构造一个空队列Q。 2)QueueEmpty(Q)：判断队列是否为空。
3)QueueLength(Q)：求队列的长度。 4)GetHead(Q)：返回Q的队头元素。 5)EnQueue(Q,x)：插入x为Q的新的队尾元素。 6)DeQueue(Q)：删除Q的队头元素。 7)C1earQueue(Q)：清除队列Q中的所有元素。

20 3.2.2队列的链式存储结构 队首 队尾 … front 队首指针 ^ rear 队尾指针

21 链队的类型定义如下： typedef struct QNode { DataType data; struct QNode *next;
}QType; /*链队中结点的类型*/ typedef struct qptr { QType *front,*rear; }LinkQueue; /*链队类型*/

22 void InitQueue(LinkQueue *lq) { lq->rear=lq->front=NULL; }
(1)初始化队列运算算法 /*置队列lq的rear和front均为NULL*/ void InitQueue(LinkQueue *lq) { lq->rear=lq->front=NULL; }

23 (2)入队运算算法 voidEnQueue(LinkQueue*lq,DataType x)
{ QType *s; /*创建新结点，插入到链队的末尾*/ s=(QType *)malloc(sizeof(QType)); /*创建新结点，插入到链队的末尾*/ s->data=x;s->next=NULL; if(lq->front==NULL&&lq->rear==NULL) /*空队*/ lq->rear=lq->front=s; else { lq->rear->next=s; lq->rear=s; } }

24 (3)出队运算算法 int DeQueue(LinkQueue *lq,DataType x) { QType *p;
if(lq->front==NULL&&lq->rear==NULL) return 0; /*空队*/ p=lq->front; x=p->data; lq->front=p->next; if(lq->rear==lq->front) lq->rear=lq->front=NULL; /*若原队列中只有一个结点，删除后队列变空*/ free(p); return x;}

25 (4)取队头元素运算算法 { if(lq->front==NULL&&lq->rear==NULL) /*空队*/
DataType GetHead(LinkQueue*lq,DataType x) { if(lq->front==NULL&&lq->rear==NULL) /*空队*/ return 0; x=lq->front->data; return x; }

26 (5)判断队空运算算法 int QueueEmpty(LinkQueue *lq) { return 1; else return 0; }
if(lq->front==NULL&&lq->rear==NULL) return 1; else return 0; }

27 3.2.3 循环队列 1.队列的顺序存储结构为顺序队列。 MAXSIZE-1 … 2 1 rear front

28 a)空队 b）a、b入队 c）a、b出队，c、d入队 d）假溢出
rear 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 f e rear front d c rear front b a rear front front a)空队 b）a、b入队 c）a、b出队，c、d入队 d）假溢出

29 rear e4 e3 循环队列的类型定义： #define MAXSIZE 100 /*最大队列长度 */ typedef struct {
datatype data[MAXSIZE]; /*存储队列的数据空间*/ int front; /*队头指针，指向队头元素*/ int rear; /*队尾指针，指向队尾元素的下一个位置*/ }SeqQueue; rear 3 e4 1 2 e3 front

30 e5 e6 e4 2．循环队列的特点 rear 1 2 3 3 e4 1 2 e3 将头尾连接成一个环，形成循环队列。 3 1 2 e3
(1)一般情况 rear front 2．循环队列的特点 rear 1 2 3 rear=front 3 e4 1 2 e3 front front (3) 队空 rear 将头尾连接成一个环，形成循环队列。 rear=front e5 e6 e4 3 1 2 e3 (2) 队满

31 若(rear+1)%maxsize=front, 称为队满。
5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 rear f e d c d c front front rear rear g front (a)正常情况 （b） 队满 （c） 队空 若front=rear ,称为队空； 若(rear+1)%maxsize=front, 称为队满。

32 3．循环队列的基本操作 (1)构造空队列 SeqQueue *InitQueue() { SeqQueue *q;
q=(SeqQueue*)malloc(sizeof(SeqQueue));/*开辟一个足够大的存储队列空间*/ q->front=q->rear=0; /*将队列头尾指针置为零*/ return q;}

33 (2)判断队空 int QueueEmpty(SeqQueue *q) { return(q->front==q->rear);
/*如果队列为空，则返回1，否则返回0*/ }

34 int EnQueue(SeqQueue*q，datatype x)
(3)入队 int EnQueue(SeqQueue*q，datatype x) { if((q->rear+1)%MAXSIZE==q->front) /*判断队列是否满*/ { printf("\n循环队列满!”); return FALSE; /* 若队列满，则终止*/ } q->data[q->rear]=x; /*将元素x入队*/ q->rear=(q->rear+1)％MAXSIZE; /*修改队尾指针*/ return TRUE;}

35 (4)出队 datatype DeQueue(SeqQueue *q) { datatype x;
if(q->front==q->rear) {printf("\n循环队列空!不能做删除操作!"); return FALSE; } x=q->data[q->front]; q->front=(q->front+1)％MAXSIZE; /*修改队列头指针*/ return x; /*将被删除元素返回*/ }

36 3．3 应用 3．3．1栈的应用 【例3.1】 设计一个算法，判断一个表达式中符号“(”与“)”、“[”与“]”、“{”与“}”是否匹配。若匹配，返回1；否则返回0。

37 case ')':if(exps[top]=='(')top--;
else nomatch=l ; break; case ']':if(exps[top]==’[’)top--; else nomatch=1 ; case '}':if(exps[top]== ’{‘)top--; else nomatch=l; } i++; if(nomatch==0&&top==-1) /*栈空且符号匹配则返回l*/ return 1; else return 0 ; /*否则返回0*/} #define Max 100 int match(char *exps) {char st[Max]; int top=-1,i=0; int nomatch=0; while(exps[i]!=’\0'&&nomatch==0) {switch(exps[i]) {case '(': top++;st[top]=exps[i] ;break; case '[': top++;st[top]=exps[i] ;break; case '{': top++;st[top]=exps[i] ;break;

38 【例3.2】数制转换问题。把非负十进制整数转换成n（2≤n≤35）进制数，各位系数如果大于9依次用大写英文字母A~Z表示。
(83)10=(123)8

39 while(x) /*除n取余,余数保存栈中*/ { Push(stack,x%n); x/=n;}
main() { int x,n; do { scanf("%d",&x); scanf("%d",&n); }while(n<2 || n>35 || x<0); /*输入有效数据*/ while(x) /*除n取余,余数保存栈中*/ { Push(stack,x%n); x/=n;} while(!ISEmpty(stack)) /*出栈，直到栈空*/ { Pop(stack,x); if(x<10) printf("%c",x+'0'); /*输出’0’~’9’*/ else printf("%c",x+'A'-10); } }

40 【例3.3】利用一个栈逆置一个带头结点的单链表，已知head是带头结点的单链表(a1，a2，…，an) (其中n≥0)。
typedef struct node { datatype data； struct node *next； }linklist； linklist *head;

41

42 解题思路： 1)建立一个带头结点的单链表head。 2)输出该单链表。 3)建立一个空栈s(顺序栈)。 4)依次将单链表的数据入栈。 5)依次将单链表的数据出栈，并逐个存入单链表的数据域 。 6)再输出单链表。

43 main() { linklist *head; head=creatlist(); print(head); head=backlinklist(head); print(head);}

44 void print(linklist *head) /*输出单链表*/ { linklist *p; p=head->next;
struct seqstack /*定义顺序栈*/ { datatype d[maxsize]; int top; }s; linklist *creatlist() /*建立单链表 */ { linklist *p,*q; p=q=(struct node *)malloc(sizeof(linklist)); head=p; p->next=0; p=(struct node *)malloc(sizeof(linklist)); scanf("%d",&p->data); while(p->data!=-1) { q->next=p; q=p; p=(struct node *)malloc(sizeof(linklist)); scanf("%d",&p->data); } q->next=0; return(head);} void print(linklist *head) /*输出单链表*/ { linklist *p; p=head->next; if(p==0) printf("empty 1ist．" ); else {do {printf("%6d",p->data); p=p->next; } while(p!=0);} }

45 datatype pop(seqstack *s) /*出栈*/ { datatype y; if((*s).top==-1)
{printf("栈为空"); return 0;} else {y=(*s).d[(*s).top]; (*s).top--; /*栈顶指针下移*/ return y; } } seqstack initstack() /*构造一个空栈s*/ { s.top=-1; return s; } int push(seqstack *s,datatype x) /*入栈*/ {if((*s).top==maxsize-1) { printf("栈已满"); return 0; } else {(*s).top++; (*s).d[(*s).top]=x; return x; } }

46 linklist *backlinklist(linklist *head)/*利用顺序栈s逆置单链表head*/
{ linklist *p; p=head->next; initstack(); while(p) { push(&s,p->data); /*数据依次入栈s*/ p=p->next; } while(!stackempty(s)) { p->data=pop(&s); /*数据出栈依次存入单链表*/ p=p->next; } return(head);}

47 3．3．2队列的应用 【例3.4】打印杨辉三角形。

48 分析第 i 行元素与第 i+1行元素的关系 目的是从前一行的数据计算下一行的数据

49 从第 i 行数据计算并存放第 i+1 行数据

50 EnQueue(SeqQueue *q,datatype x)
DeQueue(SeqQueue *q) {if(q->front==q->rear) {printf(“空队列!");exit(1);} x=q->data[q->front]; q->front=(q>front+1)% MAXSIZE; return x;} int GetHead(SeqQueue *q) { int e; if(q->front==q->rear) e=0; else e=q->data[q->front]; return e;} EnQueue(SeqQueue *q,datatype x) { if((q>rear+1)%MAXSIZE==q->front) {printf("\n队列是满的!"); exit(1);} q->data[q->rear]=x; q->rear=(q>rear+1)% MAXSIZE; }

51 void YangHui(int n) /*打印*/
{ int j,s,t; EnQueue(q,0); /*添加行分隔符*/ EnQueue(q,1);EnQueue(q,1); /*第一行的值入队*/ for(j=2;j<=n;j++) {EnQueue(q,0); /*行分隔符0入队*/ do /*输出第j行计算第j+1行*/ { s=DeQueue(q); /*删除队头元素*/ t=GetHead(q); /*取队头元素*/ if(t) printf("%5d",t); else printf("\n"); /*否则输出一个换行符*/ EnQueue(q,s+t); /*第j+1行的对应元素s+t入队*/ }while(t!=0);} main() { YangHui(10);}

52 实例扩展 在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。如两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。请编写程序，列出进入舞池的成员。

53 结 束！