济南大学数据结构 第三章.doc

第三章 栈和队列羊肉串排队买票 栈和队列是两种重要的线性结构 栈和队列是操作受限的线性表3.1 栈3.1.1 栈的定义通常，表头端称为栈底，表尾端称为栈顶。栈是限定仅在表尾(栈顶)进行插入或删除操作的线性表。a1为栈底元素an为栈顶元素按a1、a2、an顺序进栈按an、 a2、a1顺序出栈进栈、出栈均在表尾(栈顶)进行栈称为后进先出线性表(LIFO)栈的抽象数据类型的定义ADT Stack 数据对象: D = ai | ai ElemSet，i = 1, 2, , n 数据关系: R1 = ；约定a1为栈底，an为栈顶。基本操作: InitStack( &S )结果: 构造一个空栈 S。DestroyStack( &S )条件: 栈 S 已存在。结果: 销毁栈 S。 ADT Stack 主要基本操作包括:ClearStack( &S ) StackIsEmpty ( S )StackLength ( S )GetTop ( S，&e )Push ( &S，e )Pop ( &S，&e )StackTraverse ( S，visit() )3.1.2 栈的表示和实现-取决于数据在计算机中存储方式!顺序栈 ；链式栈 。1. 顺序栈# define STACK_INIT_SIZE 100# define STACKINCREMENT 10typedef struct SElemType * base ； SElemType * top ； int stacksize ； SqStack ；SqStack S ；栈中有三个元素空栈 S.top = S.base 满栈 S.top - S.base = S.stacksize 栈的初始化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 ；初始化为一个空栈取栈顶元素Status GetTop ( SqStack S ，SElemType &e ) if ( S.top = S.base ) return ERROR ； /空栈e = * ( S.top 1 ) ；return OK ；插入元素(Push)例，在栈中插入元素 A、B 、C 、D 、E 、F每插入一个元素，S.top增加1栈满时，作溢出处理插入元素 e 为新的栈顶元素Status Push ( SqStack &S ，SElemType e ) if ( S.top S.base = S.stacksize ) 溢出处理 ；* S.top = e ；S.top + ；return OK ；溢出处理S.base = ( SElemType * ) realloc ( S.base ， ( S.stacksize + STACKINCREMENT ) * sizeof(SElemType) )；if ( ! S.base ) exit(OVERFLOW) ；S.stacksize += STACKINCREMENT ；删除元素(Pop)例，删除栈顶元素 B 、A 和 C栈空时ERROR删除栈顶元素Status Pop ( SqStack &S ，SElemType &e ) if ( S.top = S.base ) return ERROR ； /空栈-S.top ；e = * S.top ；return OK ；思考：1、2、3、4 四个数字按顺序入栈，问存在多少种出栈顺序。2. 链式栈typedef struct SNode SElemType data ；struct SNode * next ； SNode ，* LinkStack ； 空栈: S-next =NULL插入 PushStatus Push ( LinkStack &S ，SElemType e ) r = ( LinkStack ) malloc ( sizeof (SNode) ) ；r-data = e ；/生成新结点 r-next = S-next；S-next = r ； /插入至栈顶 return OK ；删除 Pope = p - data = zhou free ( p ) Status Pop ( LinkStack &S，SElemType &e ) if (S-next =NULL) return ERROR；p = S-next ； /指向栈顶S-next = p-next ； /删除栈顶 e = p-data ； free(p) ； return OK ；3.2 栈的应用3.2.1 数制转换十进制数向 d 进制数的转换。反向考虑: d 进制数向十进制数的转换例， (02504)8 = (1348)10( ( ( 08+2 ) 8+5 ) 8+0) 8+4= 1348(1348)10 = (2504)8算法3.1void conversion ( ) InitStack( S ) ；scanf( “% d”，N ) ；while ( N ) Push ( S，N % 8 ) ；N = N / 8 ；while ( ! StackIsEmpty ( S ) ) Pop ( S，e ) ；Printf ( “% d”，e ) ；3.2.2 括号匹配的检验设符号串中允许出现两种括号: 圆括号、方括号。要求必须成对匹配出现。( ( ) ) 正确 ( ) 正确 ( ) ( ( ) ) ( ( ) 错误出错原因: ( 和 ) 配对出现。思想:设计栈来依次存放输入的左括号当遇到右括号时，判断是否匹配匹配则退栈，否则出错。例， ( ( ) ) 读入左圆括号 ( 进栈读入左方括号 进栈读入左圆括号 ( 进栈读入右圆括号 ) ，与栈顶( 匹配，出栈读入右圆括号 ) ，与栈顶 不匹配，出错算法描述初始化栈。读入一个符号串。循环处理当前符号 若为左括号，进栈；若为右括号，则于栈顶括号作比较；若匹配，将栈顶括号出栈，否则，出错处理。若栈空，则成功。作业: 算法实现任意输入的符号串的括号匹配算法。3.2.5 表达式求值算术表达式 4 2 * 3 10 / 5 求值4 2 * 3 10 / 5= 4 6 10 / 5= 10 10 / 5= 10 2= 8思想:使用栈存放符号栈顶操作符与当前输入操作符比较优先级低，新操作符进栈优先级高，栈顶操作符出栈，计算结果3.4 队列3.4.1 队列的定义队列只允许在一端进行插入，而在另一端进行删除。队列是一种先进先出(FIFO)的线性表。队列的抽象数据类型的定义ADT Queue 数据对象: D = ai | ai ElemSet，i = 1, 2, , n 数据关系: R1 = ；约定a1为队头元素，an为队尾元素。基本操作: InitQueue( &Q )结果: 构造一个空队列 Q。DestroyQueue( &Q )条件: 队列 Q 已存在。结果: 销毁队列 Q。 ADT Queue 主要基本操作包括:ClearQueue( &Q )QueueIsEmpty ( Q )QueueLength ( Q )GetHead ( Q，&e )EnQueue ( &Q，e )DeQueue ( &Q，&e )QueueTraverse ( Q，visit() )3.4.2 队列的表示和实现链队列；顺序队列；循环队列1. 链队列链式存储结构空队列 Q.front = Q.rear 链队列存储结构typedef struct Qnode QElemType data ； struct QNode * next ； QNode ，* QueuePtr ；typedef struct QueuePtr front ； QueuePtr rear ； LinkQueue ；初始化Status InitQueue ( LinkQueue &Q ) Q.front = Q.rear = ( QueuePtr ) malloc ( sizeof(QNode) ) ； /申请头结点if ( ! Q.front ) exit (OVERFLOW) ；Q.front - next = NULL ；return OK ；插入队列在队尾插入新元素 eStatus 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 ；离开队列删除队头元素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 ；作业: 假设以带头结点的循环链表表示队列，并且只设一个尾指针，试编写入队和出队算法。2. 顺序队列顺序存储结构用一组地址连续的存储单元依次存放队头到队尾的元素。指针 Q.front 、Q.rear 分别指示队头和队尾下一个元素。队列容量Q.queuesize。# define QUEUE_INIT_SIZE 100# define QUEUEINCREMENT 10typedef struct SElemType * front ； SElemType * rear ； int queuesize ； SqQueue ；SqQueue Q ；插入、删除操作插入元素 J1；插入元素 J2 、J3 ；删除元素 J1 、J2 、J3 ；删除元素 J4 ；插入元素 J4 、J5 、J6 ；插入元素 J7 ； 每插入一新元素，Q.rear + 1，每删除一元素，Q.front + 1。顺序队列一般形式空队 Q.front = Q.rear 满队 Q.rear Q.front = queuesize 3. 循环队列顺序存储结构将顺序队列改造为一个环状的空间。 用一组地址连续的循环存储单元依次存放队列中的元素。指针 Q.front 、Q.rear 分别指示队头元素和队尾的下一个元素。队列容量Q.queuesize。插入、删除操作queuesize = 6初始，Q.front = Q.rear = 0，初始空队列。每插入一新元素，Q.rear + 1，每删除一元素，Q.front + 1。插入元素 J0 、J1 、J2 、J3 、J4 ； 删除元素 J0 、J1 ； 插入元素 J5 、J6 ； 问题1:插入元素 J1 、J2 、J3 、J4 ； 每插入一元素，Q.rear = (Q.rear + 1) % queuesize ；问题2:空队列 Q.front = Q.rear 满队列 Q.front = Q.rear 插入元素 J0 、J1 、J2 、J3 、J4 、J5 ； 特殊空间，规定 front 与rear 之间总保留一个空间。空队: Q.front = Q.rear 满队: Q.front = (Q.rear + 1) % queuesize 循环队列存储结构# define QUEUESIZE 100typedef struct QElemType *base ； int front ； int rear ； SqQueue ；初始化Status InitQueue ( SqQueue &Q ) Q.base = ( QElemType * ) malloc ( QUEUESIZE * sizeof( QElemType ) ) ；if ( ! Q.base ) exit ( OVERFLOW ) ；Q.front = Q.rear = 0 ； / 空队return OK ；插入操作插入 eQ.baseQ.rear = e ；Q.rear = (Q.rear+1) % QUEUESIZE插入 xif ( (Q.rear+1) % QUEUESIZE = Q.front )return ERROR在队尾插入新元素 eStatus EnQueue ( SqQueue &Q ，QElemType e ) if ( (Q.rear+1)%QUEUESIZE=Q.front ) return ERROR； / 判断是否队满Q.baseQ.rear = e ；Q.rear = ( Q.rear + 1 ) % QUEUESIZE ； / 插入return OK ；删除操作删除队头e = Q.baseQ.front = xQ.front = ( Q.front + 1 ) % QUEUESIZEif ( Q.f