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

第三章 栈与队列 线性表的定义也可描述如下：线性表是第一个元素无前驱，最后一个元素无后继，而其他元素都有唯一直接前驱和直接后继的表结构。 例如，A=（1，4，7，…，49）是一个线性表，每个数值就是一个元素。 B=（（2001，计算机应用基础，10，22），（2003，大学英语，30，14），（2005，机械制图，70，30），（2007，数据结构，35，24））也是一个线性表，每个元素是由4个数据项（图书编号、书名、数量、价格）构成的。 知识回顾 线性表的操作 线性表的常见操作有：建表（初始化）、求表长、查找、插入、删除等。线性表的操作是在其逻辑结构和存储结构的共同支持下完成的。 线性表的分类 线性表的存储结构可分为顺序存储结构和链式存储结构两种，因此可将线性表分为顺序表和链表两大类。 顺序表的连接 有两个顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是按从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，直到一个线性表扫描完毕，然后将未完的那个顺序表中余下的部分赋给C。C的容量要能够大于A、B两个线性表相加的长度即可。具体程序如下： 知识回顾 public class Combinate{ void merge(int[] a,int[] b) { int i,j,k; i=0;j=0;k=0; int alength=a.length; int blength=b.length; int clength=alength+blength; int[] c=new int[clength]; while(ialength jblength){ if(a[i]b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } while(ialength) c[k++]=a[i++]; while(jblength) c[k++]=b[j++]; System.out.println(); System.out.print(排序好的是：); for(int l=0;lclength;l++) System.out.print( +c[l]); } 知识回顾 public static void main(String[] args) { Combinate a1=new Combinate(); int[] a={2,5,7}; int[] b={3,4,8,9}; System.out.print(a数组：); for(int i=0;ia.length;i++) System.out.print( +a[i]); System.out.println(); System.out.print(b数组：); for(int j=0;jb.length;j++) System.out.print( +b[j]); a1.merge(a,b); } } 程序运行的结果为 a数组：2 5 7 b数组：3 4 8 9 排序好的是：2 3 4 5 7 8 9 栈和队列的相关概念； 栈的“后进先出”、队列的“先进先出”的结构特点； 栈在顺序存储结构、链式存储结构下的特点及相应算法实现； 队列在顺序存储结构、链式存储结构下的特点及相应算法实现； 栈的定义 栈是一种特殊的线性表，其全部操作都被限制在表的固定一端进行，而且构成栈的元素必须是同一数据类型。 栈的相关概念 栈的特点是在线性表的固定端进行操作，将进行操作的一端称为栈顶，用top表示；另一端称为栈底，用bottom表示。 栈的常用操作包括建立栈、元素进入栈（入栈）、元素退出栈（出栈）、取栈顶元素等。 栈是一个后进先出（Last In First Out，LIFO）的线性表，即最后进栈的元素最先出栈，最先入栈的元素最后出栈。 栈的存储结构 栈是特殊的线性表，因此其存储结构和线性表非常类似，也可以分为顺序存储结构和链式存储结构。 1．顺序栈 将栈在顺序存储结构下