数据结构-刘波-3

《数据结构-刘波-3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

数据结构第三章栈和队列主讲人:刘波

1本章要点掌握栈的相关概念掌握栈的存储结构(顺序栈和链栈)及其基本运算的实现掌握队列的相关概念掌握队列的存储结构(循环顺序队列和链队列)及其基本运算的实现灵活运用栈和队列的特点解决应用问题

2栈的基本含义是一种只能在表尾进行插入或删除操作的线性表.其中:表尾称为栈顶;表头称为栈底.主要特点:先进后出(lastinfirstout,LIFO),即后进栈的元素先出栈.示意图利用栈进行车辆调度,求得出站车厢序列(P44图3.11b)

3出栈进栈栈顶栈底anan-1...a3a2a1

4举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。

5栈的抽象数据类型的定义ADTStack{数据对象:D={ai|aiElemSet,i=1,2,…n;n>0}数据关系:R1={|ai-1,aiD,i=2,…n}

6基本操作:InitStack(&S)//构造一个空栈DestroyStack(&S)//销毁栈ClearStack(&S)//将S清为空栈StackEmpty(S)//判断S是否为空栈StackLength(S)//返回栈S的长度GetTop(S,&e)//用e返回S的栈顶元素push(&S,e)//插入e为新的栈顶元素pop(&S,&e)//删除S的栈顶元素,并且用e返回StackTraverse(S,visit())//从栈底到栈顶依此对S的每个元素调用visit函数}ADTStack

7栈的顺序存储表示顺序栈,利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素顺序栈的定义(类型说明)#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;//栈底指针ElemType*Top;//栈顶指针intstacksize;}SqStack;

8栈的操作在操作过程中,非空栈的栈底base不变,栈顶top始终指向栈顶元素的下一个位置.注意:有些教材及复习资料将top指向栈顶元素.初始化操作:base=top;插入一个新元素:top=top+1;删除栈顶元素:top=top-1

9顺序栈的基本运算初始化栈,构造一个空栈SStatusInitStack(Sqstack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFOW);S.top=S.base;S.Stacksize=STACK_INIT_SIZE;returnOK;}

10顺序栈的基本运算(2)读取栈顶元素StatusGetTop(SqStackS,ElemType&e){if(S.top==S.base)returnERROR;//空栈e=*(S.top-1);returnOK;}

11顺序栈的基本运算(3)进栈(插入新元素e)StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.Stacksize)//栈满{S.base=(ElemType*)realloc(S.base,(S.Stacksize+STACKINCREME)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.Stacksize;S.Stacksize=S.Stacksize+STACKINCREMENT;}*S.top=e;top++;returnOK;}

12顺序栈的基本运算(4)出栈(删除栈顶元素e)StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;//空栈S.top--;e=*S.top;returnOK;}

13顺序栈的基本运算(5)判断是否为空栈StatusStackEmpty(SqStackS){if(S.top==S.base)returnERROR;elsereturnOK;}

14栈的链式表示链栈:是栈的链接存储表示,即只允许在表头进行插入和删除运算的单链表,其表头指针叫做栈顶指针.链栈的结点类型与单链表结点类型Lnode相同.P28链栈的类型与单链表LinkList相同.P28

15链栈的基本操作初始化voidInitStack(Linklist&S){S=(LinkList)malloc(sizeof(Lnode));S->next=Null;}

16链栈的基本操作(2)进栈Statuspush(LinkList&S,ElemTypee){P=(LinkList)malloc(sizeof(Lnode))if(!P)exit(OVERFLOW);P->data=e;P->next=S->next;S->next=P;returnOK;}

17链栈的基本操作(3)出栈Statuspop(LinkList&S,ElemType&e){if(S.next==NULL)returnERROR;P=S->next;e=P->data;S->next=P->next;Free(P);returnOK;}

18链栈的基本操作(4)读取栈顶元素StatusGetTop(LinkListS,ElemType&e){if(S==NULL)returnERROR;else{e=(S->next)->data;returnOK;}}

19栈的应用数制转换

20十进制数转换为八进制数示例

21voidconversion()//将十进制转换为8进制{InitStack(S);Scanf(“%d”,N);while(N){push(S,N%8);N=N/8;}while(!StackEmpty(S)){pop(S,e);printf(“%d”,e);}}

22栈的应用(2)行编辑程序#:表示退格符@：表示退行符voidLineEdit(){InitStack(S);//构造空栈ch=getchar();//从键盘接收第1个字符while(ch!=EOF)//EOF为全文结束符{while(ch!=EOF&&ch!=‘

23’){

24swich(ch){case“#”:pop(S,C);break;case“@”:ClearStack(S);break;default:push(S,ch);break;}ch=getchar();//从键盘接收下一个字符}//一行输入结束将栈内字符传送到用户数据区;ClearStack(S);//重置栈为空if(ch!=EOF)ch=getchar();//从键盘接收下一行第一个字符}DestroyStack(S);//销毁栈}

25栈的应用(3)表达式求值OperandTypeEvaluateExpression(){InitStack(OPTR);push(OPTR,‘#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,op)//c不是运算符{push(OPND,c);c=getchar();}

26else//c是运算符swich(precede(GetTop(OPTR),c))//Precede函数比较运算符栈顶元素和c的优先级case‘<‘:push(OPTR,c);c=getchar();break;case‘=‘:pop(OPTR,c);c=getchar();break;

27case‘>”:pop(OPTR,theta);pop(OPND,b);pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}}ReturnGetTop(OPND);}

28队列的基本含义队列(queue)也是一种线性表,只允许在表的一端(队头)进行插入,在另一端(队尾)进行删除.主要特点:先进先出(firstinfirstout,FIFO)一般队列的示意图出队a0a1a2……an入队frontrear队列有何应用?

29队列抽象数据类型的定义ADTQueue{数据对象:D={ai|aiElemSet,i=1,2,…n;n>0}数据关系:R1={|ai-1,aiD,i=2,…n}其中:a1为队头,an为队尾基本操作:InitQueue(&Q);//构造一个空队列QDestroyQueue(&Q);//销毁队列QClearQueue(&Q);//将Q清为空队列(空间还在)QueueEmpty(Q);//判断Q是否为空QueueLength(Q);//求队列Q的长度GetHead(&Q,e);//用e返回队列Q的队头元素EnQueue(&Q,&e);//插入元素e为Q的新队尾元素DeQueue(&Q,&e);//删除Q的队头元素,并用e返回……

30链队列链队列是只允许在表尾进行插入,在表头进行删除运算的单链表.链队列的类型定义typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;

31^frontrear

32链队列的基本操作算法构造一个空队列StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));if(!Q.front)exit(OVERFOW));Q.front->next=NULL;returnOK;}

33链队列的基本操作算法(2)插入元素e为Q的队尾元素(入队)statusEnQueue(LinkQueue&Q,QElemTypee){P=(QueuePtr)malloc(sizeof(Qnode));if(!P)exit(OVERFLOW);P->data=e;P->next=NULL;Q.rear->next=P;Q.rear=P;ReturnOK;}

34链队列的基本操作算法(3)删除Q的队头元素(出队)StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;P=Q.front->next;e=P->data;Q.front->next=P->next;if(Q.rear==P)Q.rear=Q.front;free(P);returnOK;}

35链队列的基本操作算法(4)销毁队列QStatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}

36队列的顺序表示和实现用一组连续存储单元依次存放队列元素两种形式一般顺序队列(非循环顺序队列)循环队列

37一般顺序队列类型定义#defineMAXQSIZE100typedefstruct{ElemTypeq[Maxsize];或ElemType*q;intfront,rear;}Queue;初始化空队:front=rear=0;插入新元素:rear++;删除队头元素:front++;

38循环队列类型定义#defineMAXQSIZE100typedefstruct{QElemType*base;或QElemTypebase[MAXQSIZE];intfront,rear;}SqQueue;队空的条件:front=rear队满的条件:(rear+1)%MAXQSIZE=front

39a7a6a576543210rearfront76543210rearfronta4

40循环队列基本操作算法构造一个空队列StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}

41循环队列基本操作算法(2)求队列的长度intQueueLength(SqQueueQ){L=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;return(L);}

42循环队列基本操作算法(3)插入元素(入队)statusEnQue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}

43循环队列基本操作算法(4)删除元素(出队)StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}

44队列的应用举例简化的生产者与消费者问题（1）生产者进程与消费者进程共用一个缓冲存储器，它具有N个缓冲区，每个缓冲区可容纳一个记录；（2）生产者进程P不断生产地（或产生）数据并将数据依次放在缓冲区Buffer中；（3）消费者进程C不断地消费数据，即不断地从缓冲区中依次取走数据并处理。（4）当缓冲区Buffer中装满数据后，生产者进程P不能再生产，它要等待消费者进程取走一个数据并通知生产者，生产者进程收到通知后方可再生产；当缓冲区Buffer中无数据（空）时，消费者进程不能再消费，它要等待生产者进程生产一个数据并通知消费者，消费者进程收到通知后方可再消费。

45问题分析由上述的（1）、（2）及（3）可以知道，这是一个循环队列问题生产者的工作相当于不断地执行入队操作消费者的工作相当于不断地执行出队操作由上述的（4）可以知道，两个进程要协调处理该队列用循环队列来处理此问题，则其模型如下图所示阴影区表示生产者所生产的数据base所指位置表示缓冲区的起始位置

46生产者与消费者问题算法初始化缓冲区BuffervoidInitBuffer(void){InitQueue(Q)//构造具有N个缓冲区的空队列Q}voidProducer(void)//生产者进程do{生产一个数据e；if(QueueFull（Q）)//队列满时，等待消费者取走数据的通知；wait(message_from_Consumer);EnQueue(Q,e);//收到通知后，将数据e插入到队列Q的队尾；signal(message_to_Consumer);//向消费者发出生产数据通知；}whileTRUE;}

47voidConsumer(void){//消费者进程do{if(QueueEmpty（Q）)//队列空时，等待生产者生产数据wait(message_from_Producer);//等待已生产通知DeQueue(Q,e)//收到通知后，将数据e从队列中取走Consume(e);//消费者进程加工数据signal(message_to_Producer)//向生产者发出已取走数据的通知；}whileTRUE;}

48小结栈与队列都是一种操作受限的线性表前者要求在线性表一端进行后进先出（LIFO）操作后者则要求在表的两端进行先进先出的操作具体问题的应用当计算结果中所产生数据的次序与要求相反时，可以通过入栈与出栈两个操作改变原数据顺序；如果希望保持原有计算结果中数据的次序，则应选择队列这一数据结构。

49作业3.3,3.4,3.12,3.13,3.19*,3.28