java数据结构_ 栈与队列武汉大学ppt课件.ppt

《java数据结构_ 栈与队列武汉大学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈与队列线性表的定义也可描述如下：线性表是第一个元素无前驱，最后一个元素无后继，而其他元素都有唯一直接前驱和直接后继的表结构。例如，A=（1，4，7，…，49）是一个线性表，每个数值就是一个元素。B=（（2001，计算机应用基础，10，22），（2003，大学英语，30，14），（2005，机械制图，70，30），（2007，数据结构，35，24））也是一个线性表，每个元素是由4个数据项（图书编号、书名、数量、价格）构成的。知识回顾线性表的操作线性表的常见操作有：建表（初始化）、求表长、查找、插入、删除等。线性表的操作是在其逻辑结构和存储结

2、构的共同支持下完成的。线性表的分类线性表的存储结构可分为顺序存储结构和链式存储结构两种，因此可将线性表分为顺序表和链表两大类。知识回顾知识回顾⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作与位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。⑵当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。总之，根据实际问题的具体需要,加以综合平衡，才能终选定比较适宜的实现方法。顺序表的连接有两个顺序表A和B，其元素均按从小到大的升序排列

3、，编写一个算法将它们合并成一个顺序表C，要求C的元素也是按从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，直到一个线性表扫描完毕，然后将未完的那个顺序表中余下的部分赋给C。C的容量要能够大于A、B两个线性表相加的长度即可。具体程序如下：知识回顾publicclassCombinate{voidmerge(int[]a,int[]b){inti,j,k;i=0;j=0;k=0;intalength=a.length;intblength=b.length;intclength=alength+ble

4、ngth;int[]c=newint[clength];while(i

5、icvoidmain(String[]args){Combinatea1=newCombinate();int[]a={2,5,7};int[]b={3,4,8,9};System.out.print("a数组：");for(inti=0;i

6、序运行的结果为a数组：257b数组：3489排序好的是：2345789知识回顾栈和队列的相关概念；栈的“后进先出”、队列的“先进先出”的结构特点；栈在顺序存储结构、链式存储结构下的特点及相应算法实现；队列在顺序存储结构、链式存储结构下的特点及相应算法实现；栈的定义栈是一种特殊的线性表，其全部操作都被限制在表的固定一端进行，而且构成栈的元素必须是同一数据类型。栈的相关概念栈的特点是在线性表的固定端进行操作，将进行操作的一端称为栈顶，用top表示；另一端称为栈底，用bottom表示。栈的常用操作包括建立栈、元素进入栈（入栈）、元素退出栈（出栈）、取栈

7、顶元素等。栈是一个后进先出（LastInFirstOut，LIFO）的线性表，即最后进栈的元素最先出栈，最先入栈的元素最后出栈。图4.2栈示意图栈的存储结构栈是特殊的线性表，因此其存储结构和线性表非常类似，也可以分为顺序存储结构和链式存储结构。1．顺序栈将栈在顺序存储结构下所得到的结构，称为顺序栈。顺序栈类似于高级语言中的数组，因此可以使用数组实现顺序栈的相关运算。利用Java语言实现数组表示栈类的定义如下：publicclassStackX{//定义栈privatefinalintSIZE=20;privateint[]st;privatein

8、ttop;publicStackX(){//构造方法st=newint[SIZE];top=-1;}publicvoidpush(int