栈和队列也是线性表

1、 栈和队列也是线性表，只不过是操作受限操作受限的线性表。但从数据类型角度看，他们是和线性表大不相同的两类重要的抽象数据类型。广泛应用于各种软件系统中。4.1 栈及其基本运算栈及其基本运算4.1.1. 定义定义栈栈是限定在表尾进行插入或删除操作的线性表。表尾端称表尾端称栈顶栈顶，表头端称栈底栈底。如图。an.a2a1栈底栈顶出栈进栈栈的修改是按后进先出的原则进行的。第四章第四章 栈和队列栈和队列4.1.2栈的基本运算1. 创建一个空栈；2. 判断栈是否为空栈；3. 往栈中插入（或称推入）一个元素；4. 从栈中删除（或称弹出）一个元素； 5. 求栈顶元素的值。 4.2 栈的表示和实现栈的表示和实现

2、4.2.1顺序表示typedef int ElemType; /* 定义栈元素的数据类型，这里定义为整型 */#define MAXNUM 100 /* 栈中能达到的最大容量，这里设为100 */struct SeqStack /* 顺序栈类型定义 */ElemType sMAXNUM;int t; SeqStack, *PSeqStack;PSeqStack createEmptyStack_seq( void ) PSeqStack pastack; pastack = (PSeqStack)malloc(sizeof(SeqStack);if (pastack=NULL)printf(O

3、ut space! n);elsepastack-t=-1; return pastack; 算法4.1 创建空栈算法4.2 判断栈是否为空栈int isEmptyStack_seq( PSeqStack pastack )return ( pastack-t = -1 ); 算法4.3 栈的推入void push_seq( PSeqStack pastack, DataType x )/* 在栈中压入一元素x */ if( pastack-t = MAXNUM - 1 ) printf( overflow! n ); else pastack-t = pastack-t + 1; pasta

4、ck-spastack-t = x; 算法4.4 栈的弹出ElemType pop_seq( PSeqStack pastack )/* 删除栈顶元素 */ ElemTypetemp;if( isEmptyStack_seq( pastack ) )printf( Underflow!n ); elsetemp = pastack.spastack-t;pastack-t = pastack-t - 1;return temp; 算法4.5 读栈顶元素DataType top_seq( PSeqStack pastack )/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ ret

5、urn pastack-spastack-t; 4.2.2链接表示typedef int ElemType;/* 定义栈中元素类型为整型，也可定义为其他类型 */struct Node/* 单链表结点结构 */ElemType info;struct Node *link;struct LinkStack/* 链接栈类型定义 */struct Node *top;/* 指向栈顶结点 */LinkStack, *PLinkStack;PLinkStack createEmptyStack_link( ) PLinkStack plstack;plstack = (struct LinkStack

6、 *)malloc( sizeof(struct LinkStack); if (plstack != NULL)plstack-top = NULL;elseprintf(Out of space! n); return plstack; 算法4.6 创建一个空栈算法4.7 判单链形式栈是否为空栈int isEmptyStack_link( PLinkStack plstack ) return (plstack-top = NULL);算法4.8 单链形式栈的推入void push_link( PLinkStack plstack, DataType x )/* 在栈中压入一元素x */s

7、truct Node * p; p = (struct Node *)malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!n); elsep-info = x;p-link = plstack-top;plstack-top = p;算法4.9 单链形式栈的弹出ElemType pop_link( PLinkStack plstack )/* 在栈中删除栈顶元素 */ struct Node * p;ElemTypeelem; if( isEmptyStack_link( plstack ) )printf(

8、Empty stack pop.n ); elsep = plstack-top;elem = p-info;plstack-top = plstack-top-link;free(p);return elem;算法4.10 读单链形式栈的栈顶元素DataType top_link( PLinkStack plstack )/* 对非空栈求栈顶元素 */return plstack-top-info;4.3.1数制转换void Conversion()PSeqStackps;intn;ps = createEmptyStack_seq();/*InitStack(&s); */scan

9、f(“%d”, &n);while(n)push_seq(ps, n%8);n /= 8;while(!isEmptyStack_seq(ps)n= pop_seq(ps);printf(“%d”, n);free(ps);/* End of Conversion() */4.3 栈的应用举例栈的应用举例4.3.2栈与递归1。递归的概念及递归调用过程 用自身的简单情况来定义自己的方式，称为“递归定义”。int factorial(int n)if(n = 1)return 1;elsereturn(n*factorial(n-1);2。简化的背包问题一个背包可以放入的物品重量为s，现有

10、n件物品，重量分别为w1,w2,wn,问能否从这些物品中选若干件放入背包中，使得放入的重量之和正好是s.1s = 00s 0 , n 0,n=1int knap(int s, int n)if( s=0)return 1;else if(s0 & n0)push_seq(st,n);n = n 1;res = 1;while (! isEmptyStack_seq(st) res = res * top_seq(st);pop_seq(st);return ( res );3。简化的背包问题*设有一个背包可以放入的物品重量为s，现有n件物品，重量分别为w1, w2, ，wn。问能否从这

11、n件物品中选择若干件放入此背包，使得放入的重量之和正好为s。(1)分析问题，得到数学模型1 当 s = 00 当 s 0 且 n 0 且 n 1（2）设计算法：递归算法（3）程序设计：int knap(int s,int n) if ( s = 0 ) return 1; else if (s0)&(nsst-t.k = TRUE; goto exit2; else if (top_seq(st).s0 & top_seq(st).nsst-t.k = FALSE; goto exit2; else x.s = top_seq(st).s - wtop_seq(st).n-1;

12、 x.n = top_seq(st).n - 1; x.r = 2; push_seq(st,x); goto entry1; exit2: /* 返回处理 */x = top_seq(st);pop_seq(st);switch (x.r) case 1: return(x.k); case 2: goto L3; case 3: goto L4; L3: /* 继续处理1 */if (x.k = TRUE) st-sst-t.k = TRUE; printf(result n=%d , w=%d n,top_seq(st).n,wtop_seq(st).n-1); goto exit2;

13、else x.s = top_seq(st).s; x.n = top_seq(st).n - 1; x.r = 3; push_seq(st,x); goto entry1; L4: /* 继续处理2 */st-sst-t.k = x.k;goto exit2;4。迷宫问题(a) 迷宫的图形表示 (b) 迷宫的二维数组表示 求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。 为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号。 为了记录当前位置

14、以及在该位置上所选的方向，算法中设置了一个栈，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即directon数组的下标值） 栈用顺序存储结构实现，栈中元素的说明如下： struct NodeMaze int x,y,d; ;typedef struct NodeMaze DataType;算法4.15 求迷宫中一条路径的算法void mazePath(int *maze,int *direction,int x1,int y1,int x2,int y2)/* 迷宫mazeMN中求从入口mazex1y1到出口mazex2y2的一条路径 */* 其中 1=x1

15、,x2=M-2 , 1=y1,y2=N-2 */ int i,j,k,kk; int g,h; PSeqStack st; DataType element; st = createEmptyStack_seq( ); mazex1y1 = 2; /* 从入口开始进入,作标记 */ element.x = x1; element.y = y1; element.d = -1; push_seq(st,element); /* 入口点进栈 */ while (not isEmptyStack_seq(st) /* 走不通时,一步步回退 */ element = top_seq(st);i = e

16、lement.x;j = element.y;k = element.d + 1;pop_seq(st);while (k=3) /* 依次试探每个方向 */ g = i + directionk0; h = j + directionk1; if (g=x2 & h=y2 & mazegh=0) /* 走到出口点 */ printf(The path is:n); /* 打印路径上的每一点 */ for (kk=1;kkt;kk+) printf(the %d node is: %d %d n,kk, st-skk.x,st-skk.y); printf(the %d nod

17、e is: %d %d n,kk,i,j); printf(the %d node is: %d %d n,kk+1,g,h); return; if (mazegh=0) /* 走到没走过的点 */ mazegh = 2; /* 作标记 */ element.x = i; element.y = j; element.d = k; push_seq(st,element); /* 进栈 */ i = g; /* 下一点转换成当前点 */ j = h; k = -1; k = k + 1; printf(The path has not been found.n); /* 栈退完,未找到路径

18、*/4.4队列的定义及基本运算 “队列”也是一种特殊的线性表，对于它所有的插入都在表的一端进行，所有的删除都在表的另一端进行。进行删除的这一端叫队列的“头”，进行插入的这一 端叫队列的“尾”。当队列中没有任何元素时，称为“空队列”。队列的基本运算有以下五种：1. 创建一个空队列或将队列置成空队列；2. 判队列是否为空队列；3. 往队列中插入一个元素；4. 从队列中删除一个元素；5. 求队列头部元素的值。4.5队列的实现typedef struct _QNodeElemTypeinfo;struct _QNode*link;Node, *PNode;typedef structPNodef;PN

19、oder;LinkQueue, *PLinkQueue;算法4.21 创建一个空队列PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu = (struct LinkQueue *)malloc(sizeof(struct LinkQueue); if (plqu!=NULL)plqu-f = NULL; plqu-r = NULL; elseprintf(Out space! n); return plqu; 1。队列的链式表示和实现。队列的链式表示和实现 算法4.23 链接表示队列的插入void enQueue_link( PL

20、inkQueue plqu, Datatype x ) struct Node *p;p = (struct Node *)malloc( sizeof( struct Node ) );if ( p = NULL )printf(out of space!);elsep-info = x;p-link = NULL;if (plqu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r-link = p; plqu-r = p; 算法4.22 判断链接表示队列是否为空队列 int isEmptyQueue_link( PLinkQueue plqu )

21、return (plqu-f = NULL);算法4.24 链接表示队列的删除void deQueue_link( PLinkQueue plqu )struct Node * p; if( plqu-f = NULL )printf( Empty queue.n ); else p = plqu-f;plqu-f = plqu-f-link;free(p); 算法4.25 读链接表示队列的头部结点值Datatype frontQueue_link( PLinkQueue plqu )/* 在非空队列中求队头元素 */ return plqu-f-info; Q.rearQ.frontJ1J2

22、J3Q.frontQ.rearQ.rearQ.frontJ6J5队列空队列数组越界（）普通情况2。循环队列。循环队列队列的顺序表示和实现队列的顺序表示和实现Q.rearQ.frontQ.frontJ2J1J8J7J6J5J4J3Q.rearJ1J2J7J6J5J4J3Q.frontQ.rear图队列满图队列空图队列满，判断Q.rear-next = Q.front（）循环队列struct SeqQueue/* 顺序队列类型定义 */ ElemTypeqMAXNUM; intf, r;typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */算法4

23、.17 判队列是否为空队列int isEmptyQueue_seq( PSeqQueue paqu ) return (paqu-f = paqu-r);算法4.16 创建一个空队列PSeqQueue createEmptyQueue_seq( void ) PSeqQueue paqu; paqu = (struct SeqQueue *)malloc(sizeof(struct SeqQueue); if (paqu=NULL)printf(Out space! n);else paqu-f = 0; paqu-r = 0;return paqu;算法4.18 队列的插入void enQu

24、eue_seq( PSeqQueue paqu, DataType x )/* 在队列中插入一元素x */ if( (paqu-r + 1) % MAXNUM = paqu-f ) printf( Full queue.n );else paqu-qpaqu-r = x;paqu-r = (paqu-r + 1) % MAXNUM; 算法4.19 队列的删除void deQueue_seq( PSeqQueue paqu )/* 删除队列头部元素 */ if( paqu-f = paqu-r )printf( Empty Queue.n ); elsepaqu-f = (paqu-f + 1)

25、 % MAXNUM; 算法4.20 求队列的头元素DataType frontQueue_seq( PSeqQueue paqu )/* 对非空队列,求队列头部元素 */return paqu-qpaqu-f; 4.6 限制存取点的表限制存取点的表*4.6.1双端队列双端队列是一种特殊的线性表，对它所有的插入和删除都限制在表的两端进行。这两个端点分别记作end1和end2。它好象一个特别的书架，取书和存书限定在两边进行。4.6.2 双栈双栈是一种加限制的双端队列，它规定从end1插入的元素只能从end1端删除，而从end2插入的元素只能从end2端删除。它就好象两个底部相连的栈。4.6.3 超

26、队列 超队列是一种输出受限的双端队列，即删除限制在一端(例如end1)进行，而插入仍允许在两端进行。它好象一种特殊的队列，允许有的最新插入的元素最先删除。4.6.4 超栈 超栈是一种输入受限的双端队列，即插入限制在一端（例如end2）进行，而删除仍允许在两端进行。它可以看成对栈溢出时的一种特殊的处理，即当栈溢出时，可将栈中保存最久（end1端）的元素删除。#define MaxQueueSize100typedef struct _QNodeElemType*base;intfront;int rear;SeqQueue;Status InitQueue(SeqQueue *q);void D

27、estroyQueue(SeqQueue *q);void ClearQueue(SeqQueue *q);BOOL IsQueueEmpty(SeqQueue q);int QueueLength(SeqQueue q);Status GetHead(SeqQueue q, ElemType *elem);Status InQueue(SeqQueue *q, ElemType elem);Status OutQueue(SeqQueue *q, ElemType *elem);3。可变长循环队列的表示和实现。可变长循环队列的表示和实现Status InitQueue(SeqQueue *q

28、) q-base = (ElemType *)malloc(sizeof(ElemType) * MaxQueueSize);assert(q-base);q-rear = q-front = 0;return OK;Status InQueue(SeqQueue *q, ElemType elem)PQNodepNode;if(IsQueueFull(*q)return ERROR;q-baseq-rear = elem;q-rear = (q-rear+1)%MaxQueueSize;return OK;Status OutQueue(SeqQueue *q, ElemType *elem)if(IsQueueEmpty(*q)return ERROR;*elem = q-baseq-front;q-front = (q-front+1) % MaxQueueSize;return OK;Status InitStack(SeqStack *s)s-base = (ElemType *)malloc(sizeof(ElemType) * InitSize);assert(s-base != NULL);s-top = s-base;