数据结构课程讲稿第3章.doc

数据结构课程讲稿第3章 第1章绪论第3章栈和队列?栈和队列是两种重要的线性结构。 ?在计算机领域有广泛的应用例如栈是实现函数嵌套调用重要方式?从数据组织关系上栈和队列都属于线性表?它们的特殊性在于操作不同于之前的线性表?同时操作受限于线性结构本身。 ?因此，把栈和队列作为单独的内容从线性表中独立出来。 因此，把栈和队列作为单独的内容从线性表中独立出来。 第1章绪论3.1栈?3.1.1抽象数据类型-栈的定义?栈（stack）限定仅在表尾进行插入或删除操作的线性表。 ）限定仅在表尾进行插入或删除操作的线性表。 ?定义本身说明表尾端有其特殊含义！?表尾端称为栈顶（top）?表头端称为栈底（bottom）?不含元素的空表称为空栈第1章绪论3.1.1抽象数据类型-栈的定义?栈S=(a1,a2,a n)a1是栈底，a n是栈顶?从操作上a1是最先进入栈中，其次是a2，最后是a n。 对于某一时刻，栈中最先退出的元素是栈顶栈的状态变化是按照后进先出(LIFO)的原则进行。 栈又称为后进先出(Last infirst out)的线性表第1章绪论a na2a1进栈出栈栈顶栈底进栈出栈(a)栈栈栈栈栈(b)铁铁铁铁栈栈铁栈图3.1栈第1章绪论3.1.1抽象数据类型-栈的定义?ADT LinearList?数据对象D=a i|a iElemSet,i=1,2,，n,n0?关系RL|a i,a i+1D，i=1,2,n-1?约定a n为栈顶，a1为栈底?基本操作?除了入栈、出栈操作，围绕栈数据结构本身特点，定义如下操作除了入栈、出栈操作，围绕栈数据结构本身特点，定义如下操作第1章绪论?1.InitStack(&S)构造一个空栈S。 ?2.DestroyStack(&S)销毁栈S?3.ClearStack(&S)清空已存在的栈S?4.StackEmpty(S)若栈S为空栈，则返回TRUE，否则FALSE第1章绪论?5.StackLength(S)返回S的元素个数，即栈的长度。 ?6.GetTop(S,&e)用e返回栈顶元素?7.Push(&S,e)插入元素e为新的栈顶元素入栈。 ?8.Pop(&S,&e)删除栈S的栈顶元素出栈，并用e返回该值?ADT Stack第1章绪论3.1.2栈的表示和实现?和线性表相似，栈的数据表示有两种方式和线性表相似，栈的数据表示有两种方式顺序栈链式栈?顺序栈栈的顺序存储结构?在具体实现时，应该充分考虑栈的存储空间动态变化的需求在具体实现时，应该充分考虑栈的存储空间动态变化的需求第1章绪论3.1.2栈的表示和实现?#define STACK_INIT_SIZE100;?#define STACKINCREMENT10;?typedef structSElemType*base;/base=NULL?栈不存在SElemType*top;/top=base?空栈int stacksize;/当前为栈分配的实际空间?SqStack第1章绪论3.1.2顺序栈?关于base和top指针的约定和操作当栈初始化时，base指向存储的空间的第一个位置，也可指向存储空间的最后一个位置如果base=NULL，栈不存在top初始状态是指向base指向的位置，此时为空栈入栈一个元素，top增1出栈一个元素，top减1非空栈的栈顶指针始终在栈顶元素的下一个位置上。 第1章绪论ADT Stack的表示与实现?#define STACK_INIT_SIZE100;?#define STACKINCREMENT10;?typedef structSElemType*base;/base=NULL?栈不存在SElemType*top;/top=base?空栈int stacksize;/当前为栈分配的实际空间?SqStack第1章绪论基本操作的算法描述?Status InitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;Return OK;?/InitStack第1章绪论基本操作的算法描述?Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);Return OK;?/GetTop第1章绪论基本操作的算法描述?Status Push(SqStack&S,SElemType e)if(S.topS.base)=S.stacksize)?S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);?if(!S.base)exit(OVERFLOW);?S.top=S.base+S.stacksize;/为什么？?S.stacksize+=STACKINCREMENT;*S.top+=e;Return OK;?/Push第1章绪论基本操作的算法描述?Status Pop(SqStack&S,SElemType&e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;?/Pop?如果采用链式存储结构，该如何表示和实现栈呢？如果采用链式存储结构，该如何表示和实现栈呢？第1章绪论3.2栈的应用举例?3.2.5表达式求值在程序设计语言中，在对表达式进行计算时，通常采用运算符优先算法。 例如4+2*310/5运算规则?1.先乘除，后加减；?2.从左算到右；?3.现括号内，后括号外。 此例子的运算顺序如下?4+2*310/5?4+610/5?1010/5?102=8如何实现运算符优先呢？第1章绪论3.2.5表达式求值?任何一个表达式都是由:操作数(operand)、运算符(operator)、界限符(delimiter)。 ?操作数既可以是常数，也可以是被说明为变量或常量的标识符；操作数既可以是常数，也可以是被说明为变量或常量的标识符；?运算符可以分为算术运算符、关系运算符和逻辑运算符三类；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；?基本界限符有左右括号和表达式结束符等。 第1章绪论3.2.5表达式求值?为了处理方便，把运算符和界限符统称为算符，以为了处理方便，把运算符和界限符统称为算符，以OP命名该集合?在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一1 1=2，1的优先权等于2。 12，1的优先权高于2。 第1章绪论表表3-1算符之间的优先关系第1章绪论?实现算符优先算法时需要使用两个工作栈一个称作operator，用以存放运算符；另一个称作，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。 ?算法的基本过程如下首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“”压入运算符栈；依次读入表达式中的每个字符若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理? (1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；? (2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈；? (3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。 直到整个表达式求值完毕operator的栈顶元素和当前读入的字符均为“#”第1章绪论?OperandType EvaluateExpression()InitStack(operator);Push(operator,#);InitStack(operand);c=getchar();while(c!=#|GetTop(operator)!=#)?if(!In(c,OP)Push(operand,c);c=getchar();?elseswitch(Precede(GetTop(operator),c)case:?Pop(operator,theta);?Pop(operand,b);Pop(operand,a);?Push(operator,Operate(a,theta,b);?break;/Switch?/else/WhileReturn GetTop(operand);?/EvaluateExpression第1章绪论?例如#3*(72)#求值过程如下Operator栈Operand栈#3*(7-27-2=553*5=1515第1章绪论3.4队列?队列(Queue)是另一种限定性的线性表；它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist InFist Out，缩写为FIFO)的特性。 在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 假设队列为q=(a1，a2，a n)，那么a1就是队头元素，a n则是队尾元素。 队列中的元素是按照a1，a2，a n的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，a n-1都离开队列之后，a n才能退出队列。 第1章绪论3.4队列?关于队列的例子现实生活中的排队?典型的队列的应用操作系统中的处理机调度中各种队列模型第1章绪论3.4.1抽象数据类型队列的定义?队列与栈不同的地方在于队列删除操作删除现有线性结构中最早进入的数据元素！删除在表头进行栈的删除操作删除现有线性结构中最近进入的数据元素！删除在表尾进行第1章绪论3.4.1抽象数据类型队列的定义?ADT Queue数据对象D=a i|a iElemSet,i=1,2,，n,n0关系RL|a i,a i+1D，i=1,2,n-1约定a1为队列头，a n为队列尾。 基本操作?根据队列结构的特点，定义如下操作第1章绪论队列操作的ADT定义?1.InitQueue(&Q)操作结果构造一个空队列Q。 ?2.DestroyQueue(&Q)销毁一个已经存在的队列?3.ClearQueue(&Q)将一个已经存在的队列清空为空队列。 第1章绪论队列操作的ADT定义?4.QueueEmpty(Q)判断队列是否为空队列，并返回状态?5.QueueLength(Q)返回队列Q的元素个数，即队列的长度。 ?6.GetHead(Q，&e)用e返回队列Q的队头元素。 第1章绪论队列操作的ADT定义?7.EnQueue(&Q,e)插入元素e为队列Q的队尾元素。 ?8.DeQueue(&Q,&e)删除Q的队头元素，并用e返回其值。 第1章绪论3.4.2链队列队列的链式表示和实现?队列的数据表示和一般线性表的情况一致队列的数据表示和一般线性表的情况一致顺序表示链式表示?与栈的数据表示相反，在这里我们重点描述链式表示与栈的数据表示相反，在这里我们重点描述链式表示即链队列第1章绪论(b)非非栈非非非a1a nrearfront(a)非栈非非非非队队队rear非队队队front图链队列第1章绪论3.4.2链队列队列的链式表示和实现?队列的增减操作主要限定在队列的头尾两端；队列的增减操作主要限定在队列的头尾两端；?因此，在链式表示中，需要两个指针分别指向头和尾。 因此，在链式表示中，需要两个指针分别指向头和尾。 ?增加队列头结点?处理上的方便。 ?空链队列的条件头指针和尾指针均指向头结点空链队列的条件头指针和尾指针均指向头结点第1章绪论3.4.2链队列队列的链式表示和实现?typedef structQNodeQElemType data;Struct QNode*next;?Qnode,*QueuePtr;?typedef structLinkQueueQueuePtr front;QueuePtr rear;?LinkQueue;第1章绪论基本操作的算法描述?1.构造一个空的队列?Status InitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front?next=NULL;return OK;?第1章绪论基本操作的算法描述?2.销毁队列?Status DestroyQueue(LinkQueue&Q)While(Q.front)?Q.rear=Q.front-next;?free(Q.front);?Q.front=Q.rear;Return OK;?第1章绪论基本操作的算法描述?Status EnQueue(LinkQueue&Q,QElemType e)p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;Return OK;?第1章绪论基本操作的算法描述?Status DeQueue(LinkQueue&Q,QElemType&e)if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;/防止队尾指针丢失free(p);return OK;?第1章绪论3.4.3循环队列队列的顺序表示和实现?队列的特点删除和插入元素分别在对头和队尾两段进行。 队列的特点删除和插入元素分别在对头和队尾两段进行。 ?如果采用顺序表示，频繁的删除和增加将会出现什么问题？，频繁的删除和增加将会出现什么问题？第1章绪论图队列的基本操作Queue6543210rearfront (1)空队列543210rearfrontcbad (2)a、b、c、d依依入队543210rearfrontd (3)a、b、c出队543210rearfrontdef (4)e、f入队第1章绪论?如何充分有效地利用存储空间呢？?将顺序队列臆造为一个环状的空间循环队列循环队列图循环队列012354re