第4章 栈和队列-3.ppt

1、第1页,4.3 栈和队列算法实现的C语言源程序,4.3.1 栈的顺序存储结构及实现 #include stdio.h #include stdlib.h #define MAXSIZE 100 typedef int ElemType; typedef struct ElemType elemMAXSIZE; int top; SqStack; /*顺序栈的类型标识符 */,第2页,void OutStack(SqStack p); /*此处参数必须与下边函数说明一致*/ void InitStack(SqStack *p); void Push(SqStack *p,ElemType x);

2、 ElemType Pop(SqStack *p); ElemType GetTop(SqStack p);,第3页,main() SqStack q; int i,y,cord; ElemType a; do printf(n); printf(n 主菜单n); printf(n 1 初始化顺序栈 n); printf(n 2 插入一个元素 n); printf(n 3 删除栈顶元素 n); printf(n 4 取栈顶元素 n); printf(n 5 结束程序运行 n); printf(n-n); printf(请输入您的选择(1, 2, 3, 4, 5); scanf(%d, swit

3、ch (cord),第4页,case 1: InitStack(,第5页,case 5:exit(0); while (cordtop=0; void Push( SqStack *p, ElemType x) if (p-toptop=p-top+1; p-elemp-top=x; else printf(n Overflow!); ,第6页,ElemType Pop(SqStack *p) ElemType x; if (p-top!=0) x=p-elemp-top; p-top= p-top-1; return(x); else printf(n Underflow!); return

4、(-1); ,第7页,ElemType GetTop( SqStack p) ElemType x; if (p.top!=0) x= p.elemp.top; return(x); else printf(n Underflow!); return(-1); ,第8页,void OutStack(SqStack p) int i,j; if (p.top=0) printf(n The Stack is NULL. ); for (i=p.top; i0; i-) printf(n%2d%6d,i, p.elemi); ,第9页,在上述程序中既包括了每个算法对应的函数代码，也包括在主函数之中

5、对函数的调用。应该注意的是输出函数和取栈顶数据(但是不出栈)函数中形参SqStack p不使用指针，再看主函数的调用语句的实参q不用求地址。而进栈、出栈和初始化栈的函数形参SqStack *p使用指针，在主函数中调用语句的实参 struct NodeType *next; NodeType; typedef struct /*队列头、尾指针被封装在一起*/ NodeType *front,*rear; LinkQueue; /*队列头尾指针结构体*/,第11页,NodeType *p, *s, *h; void outlin(LinkQueue qq); /*参数要与下面的函数说明一致*/ v

6、oid creat(LinkQueue *qe); void insert(LinkQueue *qe,ElemType x); ElemType delete(LinkQueue *qe); main() LinkQueue que; ElemType y,x; int i,x,y,cord; doprintf(n 主菜单 n ) ; printf( 1 建立链表队列 n ); printf( 2 入队一个元素X n); printf( 3 出队一个元素 n); printf( 4 结束程序运行 n);,第12页,printf(-n); printf( 请输入您的选择(1， 2， 3， 4)

7、 ); scanf(%d, /*main end*/,第13页,void outlin(LinkQueue qq) p=qq.front-next; /*指向第一个数据元素结点*/ while(p!=NULL) printf( data=%4dn,p-data); p=p-next; printf(n outend nn); void insert(LinkQueue *qe,int x) /* 值为x 的结点入队 */ s=( NodeType *)malloc(sizeof(NodeType); s-data=x; s-next=NULL; qe-rear-next=s; qe-rear=

8、s; ,第14页,ElemType delete(LinkQueue *qe) ElemType x; if (qe-front= qe-rear) printf(队列为空。n); x=0; else p= qe-front-next; qe-front-next=p-next; if(p-next=NULL) qe-rear=qe-front; /*防止尾指针丢失*/ x=p-data; free(p); return(x); ,第15页,void creat(LinkQueue *qe) int i,n,x; h=( NodeType *)malloc(sizeof(NodeType);

9、h-next=NULL; /建立一个空队列 printf(n= ); scanf(%d, ,第16页,在上述程序中既包括了每个算法对应的函数代码，也包括在主函数之中对函数的调用。虽然队列是链表结构，但是头、尾指针被封装在一个结构体之中，因此在主函数中代表队列的是LinkQueue que，而不是一个指针。应该注意的是输出函数中形参LinkQueue qq不使用指针，所以主函数的调用语句的实参que不用求地址，这是传值调用。,第17页,在进队、出队和建立一个队列的函数中形参LinkQueue *qe采用指针，所以在主函数中调用语句的实参&que 需要将地址代入，这是传址调用。 链表队列的实现与单

10、链表有着明显的区别，关键在于头、尾指针组成的结构体。,第18页,习 题 四,1. 假定有编号为A、B、C、D的四辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序有几种？(注：列车由站台开出的方向假设是自左向右。每一列车均可自左进栈、出栈向右开出站台，但不允许出栈后回退。列车也可以不进栈直接开出站台。)写出每一种可能的序列。 2. 已知堆栈采用链式存储结构，初始时为空，试画出a、b、c、d四个元素依次进栈以后堆栈的状态。在此基础上出栈一个数据元素，再画出此时的栈状态。,第19页,3.写出链栈的取栈顶元素和置栈空的算法。 4.写出多个链表栈中取第j个链表栈顶元素值的算法。 5.写出

11、计算表达式3+4/25*8-6时操作数栈和运算符栈的变化情况。 6.对于给定的M进制的正整数(例如十进制)，转换为相应的N进制正整数(如二进制、八进制和十六进制)，并且输出。 (1) 写出递归算法。 (2) 写出非递归算法(需要使用栈)。,第20页,7. 已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归算法。,f(n)=,第21页,8. 阿克曼函数(Ackermanns function)定义如下：,akm(m,n)=,之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。设计运用 (1) 递归算法的源程序，上机运行。 (2) 非递归算法的源程序，上机运行，并进行比较。,第22页,9二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。 10. 课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。试画出有2个元素A、B的不同存储结构的图示，及将这2个元素出队后循环队列和链表队列的状态示意图。 11. 对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。,第23页,12. 对于一个具有n