《算法与数据结构》教学课件-第4章栈和队列--C语言描述（第2版）张乃孝编著.ppt

算法算法 创建空栈创建空栈 pseqstack createemptystack_seq( int m ) pseqstack pastack; pastack = new struct seqstack; if (pastack!=null) pastack-s = new datatypem; if (pastack-s!=null) pastack-maxnum = m; pastack-t=-1; return (pastack); else delete pastack; return null: 算法算法 判断栈是否为空栈判断栈是否为空栈 int isemptystack_seq( pseqstack pastack ) return ( pastack-t = -1 ); 算法算法 4.1 进栈进栈 void push_seq( pseqstack pastack, datatype x ) /* 在栈中压入一元素在栈中压入一元素x */ if( pastack-t = pastack-maxnum - 1 ) printf( “overflow! n“ ); else pastack-t = pastack-t + 1; pastack-spastack-t = x; 算法算法 4.2 出栈出栈 void pop_seq( pseqstack pastack ) /* 删除栈顶元素删除栈顶元素 */ if (pastack-t = -1 ) printf( “underflow!n“ ); else pastack-t = pastack-t - 1; 算法算法 4.3 取栈顶元素取栈顶元素 datatype top_seq( pseqstack pastack ) /当当pastack所指的栈不为空栈时，求栈顶元素的值所指的栈不为空栈时，求栈顶元素的值 return (pastack-spastack-t); 算法算法 4.4 创建一个空链栈创建一个空链栈 plinkstack createemptystack_link(void) plinkstack plstack; plstack = new struct linkstack; if (plstack != null) plstack-top = null; else printf(“out of space! n“); return (plstack); 算法算法 4.5 判断栈是否为空栈判断栈是否为空栈 int isemptystack_link( plinkstack plstack ) return (plstack-top = null); 算法算法 4.6 进栈进栈 void push_link( plinkstack plstack, datatype x ) /* 在栈中压入一元素在栈中压入一元素x */ pnode p; p = (pnode)malloc( sizeof( struct node ) ); if ( p = null ) printf(“out of space!n“); else p-info = x; p-link = plstack-top; plstack-top = p; 算法算法 4.7 出栈出栈 void pop_link( plinkstack plstack ) pnode p; if( isemptystack_link( plstack ) ) printf( “empty stack pop.n“ ); else p = plstack-top; plstack-top = plstack-top-link; free(p); 算法算法 4.8 取栈顶元素取栈顶元素 datatype top_link( plinkstack plstack ) /* 对非空栈求栈顶元素对非空栈求栈顶元素 */ if (pastack-top=null) couttop-info); int main() int m,n; . int i; int x,y; 3: 2: 1: op1 op2 struct seqqueue int maxnum; int f,r; datatype *q; ; typedef struct seqqueue *pseqqueue; pseqqueue paqu; 算法算法 4.14 出队出队 void dequeue_seq( pseqqueue paqu ) /* 删除队列头部元素删除队列头部元素 */ if( paqu-f = paqu-r ) printf( “empty queue.n“ ); else paqu-f = (paqu-f + 1) % paqu-maxnum; 算法算法 4.15 取队列的头元素取队列的头元素 datatype frontqueue_seq( pseqqueue paqu ) /* 对非空队列对非空队列 ,求队列头部元素求队列头部元素 */ if( paqu-f = paqu-r ) printf( “empty queue.n“ ); else return (paqu-qpaqu-f); 算法算法 4.17 判断链接表示队列是否为空队列判断链接表示队列是否为空队列 int isemptyqueue_link( plinkqueue plqu ) return (plqu-f = null); 算法算法 4.18 入队入队 void enqueue_link( plinkqueue plqu, datatype x ) pnode p; p = (pnode )malloc( sizeof( struct node ) ); if ( p = null ) printf(“out of space!“); else p-info = x; p-link = null; if (plqu-f = null) plqu-f = p; else plqu-r-link = p; plqu-r = p; 算法算法 4.19 出队出队 void dequeue_link( plinkqueue plqu ) pnode p; if( plqu-f = null ) printf( “empty queue.n “ ); else p = plqu-f; plqu-f = plqu-f-link; free(p); 算法算法 4.20 取队列头部结点的值取队列头部结点的值 datat