资源描述：
《数据结构 栈和队列b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、井冈山大学电子与信息工程学院计算机科学系孙凌宇sunlingyu@jgsu.edu.cn3.3实现递归当一个函数运行期间调用另一个函数时，运行被调用函数之前需先完成三件事：l将所有的实在参数、返回地址等信息传递给被调用函数保存；l为被调用函数的局部变量分配存储区；l将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成三件事：l保存被调函数的计算结果；l释放被调函数的数据区；l依照被调函数保存的返回地址将控制转移到调用函数。过程的嵌套调用子子过子过t过程s程主rr2s程1r程3序rstsrr•递归过程及其实现–递归：函数直接或间接的调用自身叫
2、递归–实现：建立递归工作栈例递归的执行情况分析voidprint(intw){inti;if(w!=0)运行结果：{print(w-1);1，for(i=1;i<=w;++i)2，2，printf(“%3d,”,w);3，3，3，printf(“/n”);}}多个函数嵌套调用的规则是：后调用先返回,此时的内存管理实行“栈式管理”。l递归过程指向过程中占用的数据区，称之为递归工作栈；l每一层的递归参数合成一个记录，称之为递归工作记录；l栈顶记录指示当前层的执行情况，称之为当前活动记录；l栈顶指针，称之为当前环境指针。典型递归问题：数学函数、Hanoi塔问题参
3、见教材P55-583.4队列(queue)3.4.1抽象数据类型队列的定义•定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的特殊的线性表。–队尾(rear)——允许插入的一端–队头(front)——允许删除的一端例如：队列Q=(a1,a2,a3,……….,an-1,an)队尾队头在队尾插入元素称为入队；在队首删除元素称为出队。队列特点：只能在队头和队尾运算，且访问结点时依照先进先出（FIFO）的原则。出队a1a2a3…………………….an入队frontrear队列Q=(a,a,……,a)12n当队列中没有元素时称为空队列。在空队列中依次加入元
4、素a,a,…a之后，a是队头元素，a是队尾元素。12n1n显然退出队列的次序也只能是a,a,…a，也就是说队12n列的修改是依照先进先出原则进行的。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。队列的独特用途：1.离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）；2.操作系统中的作业调度（一个CPU执行多个作业）；队列的抽象数据定义见教材P59（与栈类似，也有9个基本操作，不同的是它的删除是在表的头部即队头进行）队列的存储结构：1.链队列2.顺序队列，并以循环顺序队列更常见3.4.2链队列——用链表表示的队列
5、结点定义：typedefstructnode{ElemTypedata;structnode*next;}LNode;头结点队头队尾front…...^rear空队^设指针front和rear分别指向头结点和队尾frontrear结点，分别称为头指针、尾指针。显然，一个链队列需要这两个指针才能唯一确定。空的链队列的判决条件：头指针和尾指针均指向头结点。入队算法：向链队列的队尾插入一个元素1）申请一个链结点2）插入动作x入队x^frontreary入队xy^frontrearLNode*ldcr(LNode*rear,ElemTypee){LNode*p;p
6、=(LNode*)malloc(sizeof(LNode));p->data=e;p->next=NULL;rear->next=p;rear=p;return(rear);}出队算法：删除链队列的队头元素1）在删除前应判断链队列是否空2）删除动作x出队xy^frontreary出队^frontrearvoidldsc(LNode*front,LNode*rear,ElemType&e){LNode*s;if(front==rear)returnERROR；s=front->next;front->next=s->next;if(s->next==NULL
7、)rear=front;e=s->data;free(s);}链队列的实现：由于队列必须有队首和队尾指针，因此可以增加定义一个结构类型LinkQueue，将这两个指针封装在一起，即两个域分别为队首指针front和队尾指针rear，其定义见教材P61。其队列运算指针变化状况如P61图33..11其典型操作的算法描述如教材P62。3.4.3顺序队列——循环队列v用一维数组实现sq[M]v由于队列的队头和队尾的位置是变化的，所以要再设立一个队头指示器和一个队尾指示器。v在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。rear555J65
8、444J54rearrear3frontJ4333front2J3
