数据结构课件 第3章

数 据 结 构 第3章 栈和队列第3章栈和队列•栈和队列是两种特殊的线性表，是限定插入和删除只能在表的“端点”进行的线性表，是操作受限的线性表，称限定性数据结构。

3.1 栈•栈–是一种限定仅在表尾进行插入或删除操作的线性表•表尾即栈顶，表头即栈底•不含元素的空表称空栈–特点•先进后出（FILO）或后进先出（LIFO）3.1 栈•栈的结构a 1a 2a n……进栈出栈栈底栈顶栈 = (a 1, a 2, …, a n )栈 s = (a 1, a 2, …, a n )栈的抽象数据类型ADT Stack { 数据对象：D ＝ {a i | a i ∈ElemType, i = 1, 2, ..., n, n ≥ 0} 数据关系：R = {<a i-1, a i > | a i-1,a i ∈D, i = 1, 2, ..., n} 基本操作：InitStack(&s)DestroyStack(&s)ClearStack(&s)StackEmpty(s)StackLength(s)GetTop(s, &e)Push(&s, e)Pop(&e, &e)StackTraverse(s, visit())}ADT Stack { 数据对象：D ＝ {a i | a i ∈ElemType, i = 1, 2, ..., n, n ≥ 0} 数据关系：R = {<a i-1, a i > | a i-1,a i ∈D, i = 1, 2, ..., n} 基本操作：InitStack(&s)DestroyStack(&s)ClearStack(&s)StackEmpty(s)StackLength(s)GetTop(s, &e)Push(&s, e)Pop(&e, &e)StackTraverse(s, visit())}3.1 栈•顺序栈的存储表示–类似于线性表的顺序存储实现，指向表尾的指针可以作为栈顶指针–当栈底指针和栈顶指针一致时，表示为空栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针#define STACK_INIT_SIZE 100 // 栈的初始大小#define STACK_INCREMENT 10// 栈每次增加的大小typedef struct { SElemType *base; // 栈底指针 SElemType *top; // 栈顶指针 int stackSize;// 栈的大小} SqStack;#define STACK_INIT_SIZE 100 // 栈的初始大小#define STACK_INCREMENT 10// 栈每次增加的大小 typedef struct { SElemType *base; // 栈底指针 SElemType *top; // 栈顶指针 int stackSize; // 栈的大小} SqStack;3.1 栈•构造一个空栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status InitStack(SqStack &s){ s.base = (ElemType*) malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!s.base) exit(OVERFLOW); //存储分配失败 s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK;}Status InitStack(SqStack &s){ s.base = (ElemType*) malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!s.base) exit(OVERFLOW); //存储分配失败 s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK;}3.1 栈•销毁栈•把栈置为空类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status DestroyStack(SqStack &s){ free(s.base); s.base = NULL; s.top = NULL; s.stacksize=0; return OK;}Status DestroyStack(SqStack &s){ free(s.base); s.base = NULL; s.top = NULL; s.stacksize=0; return OK;}Status ClearStack(SqStack &s){ s.top = s.base; return OK;}Status ClearStack(SqStack &s){ s.top = s.base; return OK;}3.1 栈•判断栈是否为空栈•计算栈的长度Status StackEmpty(SqStack s){ return s.top == s.base;}Status StackEmpty(SqStack s){ return s.top == s.base;}int StackLength(SqStack s){ return s.top - s.base;}int StackLength(SqStack s){ return s.top - s.base;}3.1 栈•返回栈顶元素类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status GetTop(SqStack s, SElemType &e){ if (s.top > s.base) { e = *(s.top - 1); return OK; } else return ERROR;}Status GetTop(SqStack s, SElemType &e){ if (s.top > s.base) { e = *(s.top - 1); return OK; } else return ERROR;}3.1 栈•将一个元素压入栈中类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status Push(SqStack &s, SElemType e){if (s.top - s.base >= s.stacksize) { // 栈满，追加存储空间 s.base = (SElemType *) realloc(s.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType)); if (!s.base)exit(OVERFLOW); // 存储分配失败 s.top = s.base + s.stackSize; s.stacksize += STACK_INCREMENT; }*(s.top++) = e; return OK;}Status Push(SqStack &s, SElemType e){ if (s.top - s.base >= s.stacksize) { // 栈满，追加存储空间 s.base = (SElemType *) realloc(s.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType)); if (!s.base) exit(OVERFLOW); // 存储分配失败 s.top = s.base + s.stackSize; s.stacksize += STACK_INCREMENT; } *(s.top++) = e; return OK;}3.1 栈•将一个元素从栈中弹出类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status Pop(SqStack &s, SElemType &e){if (s.top == s.base) return ERROR; e = *(--S.top); return OK;}Status Pop(SqStack &s, SElemType &e){ if (s.top == s.base) return ERROR; e = *(--S.top); return OK;}3.1 栈•链栈是以链表来存储栈的所有数据元素的数据结构typedef struct _Node {int data;struct _Node *next;} *LinkStack;typedef struct _Node { int data; struct _Node *next;} *LinkStack;a na 1a 2…^栈顶栈底3.2 栈的应用举例•数制转换–十进制N 和其它d 进制数的转换原理为N = (N div d )×d + N mod d–例如：(1348)10 = (2504)8 ，其运算过程如下NN div 8N mod 813481684168210212522计算顺序输出顺序数制转换算法void Conversion () {InitStack(s); scanf("%d", n); while (n) {Push(s, n % 8); n /= 8; }while (!StackEmpty(s)) { Pop(s, e);printf ("%d", e); }}void Conversion () { InitStack(s); scanf("%d", n); while (n) { Push(s, n % 8); n /= 8; } while (!StackEmpty(s)) { Pop(s, e); printf ("%d", e); }}3.2 栈的应用举例•后缀表达式求值–后缀表达式是将运算符放在两个运算数之后的表达式–后缀表达式的优点不需要考虑运算符的优先级，也不用括号来改变运算符的优先级中缀表达式后缀表达式a *b +c a b * c +a +b *c a b c * +a * (b + c) a bc + *a + (b *c + d) / e a b c *d +e / +后缀表达式求值算法OperandType EvaluateExpression(){Stack opnd;InitStack opnd; c = getchar();while (c != ‘#’) { if (isdigit(c)) {Push(opnd, atov(c));// atov()是将ascii 转化为数值 // 的函数 c = getchar(); } else {Pop(opnd, b); Pop(opnd, a);Push(opnd, Operate(a, c, b));}}return GetTop(opnd);}OperandType EvaluateExpression(){ Stack opnd; InitStack opnd; c = getchar(); while (c != ‘#’) { if (isdigit(c)) { Push(opnd, atov(c));// atov()是将ascii 转化为数值 // 的函数 c = getchar(); } else { Pop(opnd, b); Pop(opnd, a); Push(opnd, Operate(a, c, b));} } return GetTop(opnd);}3.3 栈与递归的实现•本节不做要求3.4 队列•队列–是限定只能在表的一端进行插入，在表的另一端进行删除的线性表•队尾（rear）—允许插入的一端•队头（front）—允许删除的一端–特点•先进先出(FIFO)3.4 队列•队列的结构a 1 a 2 a 3 … a n入队列出队列队头队尾队列 Q = (a 1, 2, …, a n )队列 Q = (a 1, a 2, …,a n )队列的抽象数据类型ADT Queue { 数据对象：D ＝ {a i | a i ∈ElemType, i = 1, 2, ..., n, n ≥ 0} 数据关系：R = {<a i-1, a i > | a i-1,a i ∈D, i = 1, 2, ..., n} 基本操作：InitQueue(&q)DestroyQueue(&q)ClearQueue(&q)QueueEmpty(q)QueueLength(q)GetHead(q, &e)EnQueue(&q, e)DeQueue(&q, &e)QueueTraverse(s, visit())}ADT Queue { 数据对象：D ＝ {a i | a i ∈ElemType, i = 1, 2, ..., n, n ≥ 0} 数据关系：R = {<a i-1, a i > | a i-1,a i ∈D, i = 1, 2, ..., n} 基本操作：InitQueue(&q)DestroyQueue(&q)ClearQueue(&q)QueueEmpty(q)QueueLength(q)GetHead(q, &e)EnQueue(&q, e)DeQueue(&q, &e)QueueTraverse(s, visit())}3.4 队列•链队列—队列的链式表示和实现–类似于线性表的链式存储实现，队头指针指向链表的头结点，队尾指针指向尾结点–当队头与队尾的指针都指向头结点时，队列为空类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针typedef struct _QNode {// 结点类型 QElemType data;struct _QNode *next; } QNode;typedef struct { // 链队列类型QNode *front; // 队头指针 QNode *rear; // 队尾指针} LinkQueue;typedef struct _QNode {// 结点类型 QElemType data; struct _QNode *next; } QNode;typedef struct { // 链队列类型 QNode *front; // 队头指针 QNode *rear; // 队尾指针} LinkQueue;链队列结构a na 1…^q.front q.rearq.front q.rear^空队列空队列3.4 队列•构造一个空队列类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status InitQueue (LinkQueue &Q) {Q.front = Q.rear = (QNode*) malloc(sizeof(QNode)); if (!Q.front)exit(OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK;}Status InitQueue (LinkQueue &Q) { Q.front = Q.rear = (QNode*) malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK;}3.1 队列•销毁队列类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status DestroyQueue(LinkQueue &Q){while (Q.front) {Q.rear = Q.front->next free(Q.front); Q.front = Q.rear; }return OK;}Status DestroyQueue(LinkQueue &Q){ while (Q.front) { Q.rear = Q.front->next free(Q.front); Q.front = Q.rear; } return OK;}3.4 队列•在队尾后增加一个元素类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status EnQueue (LinkQueue &Q, QElemType e) {// 插入元素e 为新的队尾元素p = (QNode*) malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); //存储分配失败 p->data = e; p->next = NULL;Q.rear->next = p; Q.rear = p; return OK;}Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e 为新的队尾元素 p = (QNode*) malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK;}3.4 队列•将一个元素从列头中出队类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针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;}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;}3.4 队列•队列的顺序表示和实现–用一组地址连续的存储单元依次存放所有元素–附设两个指针front 和rear•初始化建立空队列时，令front=rear=0–front 指向队列头元素–rear 指向队列尾元素的下一个位置•当插入新的队列尾元素时，尾指针加1•当删除队列头元素时，头指针加1#define MAXQSIZE 100 //最大队列长度typedef struct {QElemType *base; // 动态分配存储空间 int front; // 指向队列头元素 int rear; // 指向队列尾元素的下一个位置} SqQueue;#define MAXQSIZE 100 //最大队列长度typedef struct { QElemType *base; // 动态分配存储空间 int front; // 指向队列头元素 int rear; // 指向队列尾元素的下一个位置} SqQueue;队列的顺序存储结构Q.rear Q.frontQ.rearQ.front Q.rear Q.front初始空队列非空队列空队列123401234012343.4 队列•上述结构存在问题–设数组维数为M，当front≠0,rear=M时，再有元素入队发生溢出—假溢出–解决方案有两种•队首固定，每次出队剩余元素向下移动，这种方法效率不高•利循环队列，把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear=M，则令rear=0;循环队列的结构1234567a 1a 2a 3Q.rearQ.front•在左边的结构中–两个操作•入队： Q.rear=(Q.rear+1)%M •出队：Q.front=(Q.front+1)%M–当Q.front 和Q.rear 相同时，无法判断队列是空还是满，故可以采用两种方法•另设一个标志位以区别队列的空或满状态•少用一个元素空间，约定在环状结中，如队列头指针在在队列尾指针的下一个位置上时，队列为满，即(Q.rear+1)%M ==Q.front3.4 队列•构造一个空循环队列类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status InitQueue(SqQueue &Q){Q.base = (ElemType *) malloc(MAXQSIZE * sizeof(ElemType)); if (!Q.base) exit(OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK;}Status InitQueue(SqQueue &Q){ Q.base = (ElemType *) malloc(MAXQSIZE * sizeof(ElemType)); if (!Q.base) exit(OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK;}3.4 队列•销毁循环队列类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status DestroyQueue(SqQueue &Q){free(Q.base);Q.front = Q.rear = 0; return OK;}Status DestroyQueue(SqQueue &Q){ free(Q.base); Q.front = Q.rear = 0; return OK;}3.4 队列•在循环队列的队尾后增加一个元素类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status EnQueue(SqQueue &Q, ElemType e){if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;}Status EnQueue(SqQueue &Q, ElemType e){ if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK;}3.4 队列•将一个元素从循环列队的列头中出队类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针Status DeQueue(SqQueue &Q, ElemType &e){if (Q.front == Q.rear) return ERROR;// 队列为空 e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q, ElemType &e){ if (Q.front == Q.rear) return ERROR;// 队列为空 e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK;}本章小结•掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。