- 浏览: 15080 次
最新评论
-
lazyee:
yfzsj 写道byte bytes[] = new byte ...
存储超过内存大小的数据 -
yfzsj:
byte bytes[] = new byte[(int)Ma ...
存储超过内存大小的数据 -
ifox:
看不懂。。。。我要多来几遍了,唉
哈弗曼树及哈弗曼编码简述
在之前的重绘中,用到了数组来传递数据,但是这个数组只能用于某种特定情形中,如果要存入别的数据,就又要定义新的数组了,这样既麻烦又耗时。为了使用方便,我们可以定义一个通用的存储数据的结构,使用时只需更改传入对象的类型就好。这样一个用来存储数据的通用结构就是队列,队列中一般有几种基本的方法:数据对象的添加、插入、删除、获取、队列长度的获取。
有两种基本的实现队列的方法: 用数组实现的队列和用链表实现的队列。
一、用数组实现的队列
1、如何用数组实现队列
用数组实现的队列实质上就是用队列包装了的数组。在队列中还是用一个数组来存储信息,并定义了几个队数组进行基本操作(添加、获取数组元素、数组长度)的方法。
现在假设要定义一个用来存储在画布上画直线信息的队列。那么首先要定义一个直线信息类MyLine,类中有四个属性,即直线的起点终点坐标,以及设置和获取四个属性的方法。
然后要定义一个队列类MyQueue。在队列类中应该有一个存储信息的数组str,由于用户需求的不确定性,一个确定长度的数组肯定是不能满足要求的,所以我们应该使这个数组的长度“可变”。在“添加”方法中,可以这样来实现数组长度的可变性:将数组的初始长度设为0,在方法中新建一个长度比原数组长度大1的数组;将要添加的数据放在新数组的最后一位;遍历原数组,将原数组中数据复制到新数组中;使str指向新数组。这样,每新增一个数组元素,数组长度就加1。能够满足用户的存储要求,同时有不浪费空间。
最后,可以建立一个测试类,对队列功能进行测试。
队列类的具体代码如下:
2、数组队列的优化
现在,我们已经建立一个数组队列。那么,这个队列是否就是最优队列了呢?
显然不是的,这个队列就有两个明显的缺点:
(1) 数组只能接收MyLine类型的对象。
(2) 每次添加数组元素都要新建一个数组,并把原数组中的数据复制到新数组中,这样不仅浪费内存空间,还延长了执行时间。
(3) 队列中缺少插入和删除的方法。
要解决第一个问题,需要先要理解一个概念:泛型。
所谓泛型,其实就是使一个类中的方法可以接收各种类型的对象,只需在实例化该类是进行指定就行。实现方式为:在类名后加上“<E>”。
定义:public class 类名<E>{}
实例化:类名<要接收的对象类型> 对象名 = new类名<要接收的对象类型>();
要解决第二个问题,可以为数组设置一个初始长度(比如说100),当数组中存满100个数组元素后,新建一个比原数组长10的数组取代原数组。这样,添加前100个数组元素就不用新建数组了。
这样改之后又有一个问题了,用户的需求不同,偏好的数组初始长度和每次增加的长度也不同。为使用户根据自己的需求更改设置,我们可以重载构造方法来设置这两个值。
优化后的数组队列类代码如下:
二、用链表实现的队列
在C语言中,链表是一种数据结构。以单链表为例,单链表即由若干物理上不相连的结点链接而成的表,每个结点有一个数据域和一个指针域,数据域中存储要放置的数据,指针域中的指针指向下个结点的存储地址。
在这里我们还是沿用C语言中的定义。要用链表实现队列,首先要定义一个结点类ListNode,其中包括它的数据域和指针域。具体代码如下:
这之后,我们就可以建立链表队列类了。链表队列中的基本方法与数字队列一样,只是因结构不同,各个方法内部的实现不同。具体代码如下(以下代码中的方法还有别的实现方法有待探索):
有两种基本的实现队列的方法: 用数组实现的队列和用链表实现的队列。
一、用数组实现的队列
1、如何用数组实现队列
用数组实现的队列实质上就是用队列包装了的数组。在队列中还是用一个数组来存储信息,并定义了几个队数组进行基本操作(添加、获取数组元素、数组长度)的方法。
现在假设要定义一个用来存储在画布上画直线信息的队列。那么首先要定义一个直线信息类MyLine,类中有四个属性,即直线的起点终点坐标,以及设置和获取四个属性的方法。
然后要定义一个队列类MyQueue。在队列类中应该有一个存储信息的数组str,由于用户需求的不确定性,一个确定长度的数组肯定是不能满足要求的,所以我们应该使这个数组的长度“可变”。在“添加”方法中,可以这样来实现数组长度的可变性:将数组的初始长度设为0,在方法中新建一个长度比原数组长度大1的数组;将要添加的数据放在新数组的最后一位;遍历原数组,将原数组中数据复制到新数组中;使str指向新数组。这样,每新增一个数组元素,数组长度就加1。能够满足用户的存储要求,同时有不浪费空间。
最后,可以建立一个测试类,对队列功能进行测试。
队列类的具体代码如下:
/** * 用数组实现的队列类 */ public class MyQueue { MyLine myl; private MyLine[] str = new MyLine[0]; /** * 添加直线信息的方法 * @param myl 接收的MyLine类对象 */ public void add(MyLine myl){ //1、创建一个临时数组,它的长度是str的长度加1 MyLine[] str2 = new MyLine[str.length +1]; //2、将接收的ml对象添加到新数组的最后一位 str2[str.length] = myl; //3、将原数组中的信息复制到新数组中 for(int i=0;i<str.length;i++){ str2[i]=str[i]; } //4、使原数组指向新数组 str=str2; } /** * 获得第index位的数组元素的方法 * @param index 指定的位数 * @return 第index位的数组元素信息 */ public MyLine get(int index){ MyLine myl =str[index]; return myl; } /** * 获得队列的长度的方法 * @return 队列长度数值 */ public int size(){ return str.length; } }
2、数组队列的优化
现在,我们已经建立一个数组队列。那么,这个队列是否就是最优队列了呢?
显然不是的,这个队列就有两个明显的缺点:
(1) 数组只能接收MyLine类型的对象。
(2) 每次添加数组元素都要新建一个数组,并把原数组中的数据复制到新数组中,这样不仅浪费内存空间,还延长了执行时间。
(3) 队列中缺少插入和删除的方法。
要解决第一个问题,需要先要理解一个概念:泛型。
所谓泛型,其实就是使一个类中的方法可以接收各种类型的对象,只需在实例化该类是进行指定就行。实现方式为:在类名后加上“<E>”。
定义:public class 类名<E>{}
实例化:类名<要接收的对象类型> 对象名 = new类名<要接收的对象类型>();
要解决第二个问题,可以为数组设置一个初始长度(比如说100),当数组中存满100个数组元素后,新建一个比原数组长10的数组取代原数组。这样,添加前100个数组元素就不用新建数组了。
这样改之后又有一个问题了,用户的需求不同,偏好的数组初始长度和每次增加的长度也不同。为使用户根据自己的需求更改设置,我们可以重载构造方法来设置这两个值。
优化后的数组队列类代码如下:
/** * 队列类,存放数组元素信息(优化后的数组队列) */ public class MyQueue<E> { private int sLength; //数组初始长度 private short inLength; //数组每次增加长度 private int count = 0; //计数器,数值为数组当前长度 private Object[] str; /** * 重载的构造方法,由使用者决定sLength和inLength; * @param sLength 数组初始长度 * @param inLength 数组每次增加的长度 */ public MyQueue(int sLength, short inLength) { this.sLength = sLength; this.inLength = inLength; str = new Object[sLength]; } /** * 重载的构造方法,有使用者决定sLength值,inLength值默认 * @param sLength 数组初始长度 */ public MyQueue(int sLength) { this(sLength, (short) 10); } /** * 重载的构造方法,由使用者决定inLength值,sLength值默认 * @param inLength 数组每次增加的长度 */ public MyQueue(short inLength) { this(100, inLength); } /** * 无参构造器,使用默认的inLength和sLength值 */ public MyQueue() { this(100, (short) 10); } /** * 添加数组元素的方法 * @param e 接受的数组元素对象 */ public void add(E e){ if(count<sLength){ str[count]=e; count++; }else if(count>=sLength){ //1、创建一个临时数组,它的长度是str的长度加inLength Object[] str2 = new Object[str.length +inLength]; //2、将接收的ml对象添加到新数组的最后一位 str2[count] = e; //3、将原数组中的信息复制到新数组中 for(int i=0;i<count;i++) str2[i]=str[i]; //4、使原数组指向新数组 str=str2; count++; } } /** * 获得第index位的数组元素 * @param index 指定的位数 * @return 第index位的数组元素信息 */ public E get(int index) { E e = (E)str[index]; return e; } /** * 将新元素插入到给定的index位置上,原index位置及之后的元素向后移一位 * @param e 要插入的元素 * @param index 插入的位置 */ public void insert(E e,int index){ if(index<0||index>=str.length){ System.out.println("超出数组范围"); }else if(index>=count){ System.out.println("插入的为空区"); }else if(count<str.length){ for(int i=count-1;i>=index;i--) str[i+1]=str[i]; str[index]=e; count++; }else if(count==str.length){ Object[] str3=new Object[str.length +inLength]; for(int i=0;i<index;i++) str3[i]=str[i]; str3[index]=e; for(int i=index;i<count;i++) str3[i+1]=str[i]; str=str3; count++; } } /** * 删除指定位置的数组元素 * @param index 要删除的数组元素位置 * @return 被删除的数组元素 */ public E remove(int index){ if(index<0||index>=str.length){ System.out.println("超出数组范围"); }else if(index>=count){ System.out.println("删除的为空区"); }else if(index<count){ E e =(E)str[index]; for(int i=index;i<count-1;i++) str[i]=str[i+1]; count--; return e; } return null; } /** * 获得队列的长度 * * @return 队列长度数值 */ public int size() { return count; } }
二、用链表实现的队列
在C语言中,链表是一种数据结构。以单链表为例,单链表即由若干物理上不相连的结点链接而成的表,每个结点有一个数据域和一个指针域,数据域中存储要放置的数据,指针域中的指针指向下个结点的存储地址。
在这里我们还是沿用C语言中的定义。要用链表实现队列,首先要定义一个结点类ListNode,其中包括它的数据域和指针域。具体代码如下:
/** * 结点类,定义结点数据域和指针域 */ public class ListNode { private Object obj; private ListNode next; //重载构造方法,初始化数据域的值 public ListNode(Object obj){ this.obj=obj; } /** * 设置数据域的值 * @param obj */ public void setObj(Object obj){ this.obj=obj; } /** * 获取数据域的值 * @return 数据域值 */ public Object getObj(){ return obj; } /** * 设置指针域指向 * @param next */ public void setNext(ListNode next){ this.next=next; } /** * 获得指针域指向 * @return 指针域指向的结点 */ public ListNode getNext(){ return next; } }
这之后,我们就可以建立链表队列类了。链表队列中的基本方法与数字队列一样,只是因结构不同,各个方法内部的实现不同。具体代码如下(以下代码中的方法还有别的实现方法有待探索):
/** * 用链表实现的队列类 */ public class SingleList { //定义头结点 ListNode head;; /** * 向链表中添加新的结点 * @param obj 新结点数据域值 */ public void add(Object obj) { //实例化一个要加入的新结点 ListNode node = new ListNode(obj); //判断头结点是否为空,若为空,则将新结点设为头结点 if (head == null) { head = node; } else { //若头结点非空,将新结点添加到链表最后 ListNode temp = head; //遍历链表,找到目前的最后一个结点 while (temp.getNext() != null) temp = temp.getNext(); //将新结点设为目前最后一个结点的下一个结点 temp.setNext(node); } } /** * 向链表中某位置插入新结点,插入后原位置及之后的结点向后移 * @param obj 新结点数据域值 * @param index 插入位置 */ public void insert(Object obj, int index) { int len = size(); ListNode node = new ListNode(obj); ListNode temp = head; //判断给出的位置是否超出队列范围 if (index < 0 || index >= len) { System.out.println("超出队列范围"); return; } //判断要插入的位置是否为第一个位置 if (index == 0) { //将头结点接到新结点后,并将新结点设为头结点 node.setNext(temp); head = node; } else { //遍历链表,寻找要插入结点的前一个结点 for (int i = 0; i < index-1; i++){ temp = temp.getNext(); } //在index位置插入新结点 node.setNext(temp.getNext()); temp.setNext(node); } } /** * 从链表中移除某位置的结点,移除后该位置之后的结点前移 * @param index 要移除结点的位置 * @return 移除的结点数据域的值 */ public Object remove(int index) { int len = size(); ListNode temp = head; ListNode curNode = head.getNext(); //判断给出的位置是否超出队列范围 if (index < 0 || index >= len) { System.out.println("超出队列范围"); return null; } //判断要移除的结点是否在第一个位置 if(index==0){ //若是,则将头结点的下一个结点设为新的头结点 head=head.getNext(); return temp.getObj(); } //遍历链表,最后curNode为要移除的结点,temp为要移除结点的前一个结点 for(int i=0;i<index-1;i++){ temp=curNode; curNode=curNode.getNext(); } //将temp直接与curNode的下一个结点相连 temp.setNext(curNode.getNext()); return curNode.getObj(); } /** * 获得某位置的结点的数据域值 * @param index 需获得结点的位置 * @return 结点的数据域值 */ public Object get(int index) { int len = size(); ListNode temp = head; //判断给出的位置是否超出队列范围 if (index < 0 || index >= len) { System.out.println("超出队列范围"); return null; } //遍历链表,获得index位置的结点 for (int i = 0; i < index; i++) temp = temp.getNext(); return temp.getObj(); } /** * 求链表长度 * @return 链表长度 */ public int size() { int length = 0; ListNode temp = head; while (temp != null) { temp = temp.getNext(); length++; } //System.out.println("length="+length); return length; } }当然,链表队列中也可以用泛型。但是,要注意将结点类也用泛型表示。
发表评论
-
存储超过内存大小的数据
2013-10-13 10:34 1829问题是这样的:如何存储5亿个正整数,并对这些数据进行排重。 ... -
哈弗曼树及哈弗曼编码简述
2013-08-18 17:13 1549哈弗曼树是一种特 ... -
滑杆组件的应用实例
2013-08-15 14:16 1497滑杆JSlider类是让用户能够通过滑块的滑动来改变选择值的组 ... -
简单分形(谢尔宾斯基三角形和地毯)
2013-06-25 11:05 4327对于分形,我的理解就是:由小元件组成整体,然后再用另一或相 ... -
事件机制与简单画板
2013-04-09 16:18 825一、事件机制 1、事件参与者 事件机制的参与者有三个:事件源 ... -
QQ界面和计算器界面
2013-04-06 22:48 884在前面简单登录界面实 ... -
简单登陆界面的实现
2013-04-06 19:00 1457要用java实现一个简单登陆界面,首先应该来了解下java中有 ... -
类与对象
2013-03-22 00:02 6841、类与对象: ... -
类的继承,接口及抽象类
2013-03-21 23:08 794一、类的继承 1、什么 ...
相关推荐
利用数组和链表实现队列的基本操作,如入队,出队,读出队首元素
python利用数组和链表实现栈和队列 数组和链表.pdf
数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
数组、链表、队列、栈的区别和联系 数组和链表.pdf
队列关于数组与链表的实现, linux c语言
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,下面介绍一下java使用数组和链表实现队列的示例
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
arithmetic java算法冒泡排序、二叉树、数组、链表、队列学习简单示例 private static void mpSoft(String [] data) { for (int i = 0; i ; i++) { System.out.println(Arrays.toString(data)); for (int j = 0; ...
经过一上午的学习,对数据结构有了新的认识和理解 数组 数组是由有限个相同类型的变量所组成的有序集合,...栈是一种线性逻辑结构,可以使用数组实现,也可以使用链表实现。包含入栈还有出栈操作,遵循先入后出的原则(F
常见的数据结构(栈、队列、数组、链表和红黑树) 数组和链表.pdf
超级数组和链表及栈队列
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。这篇文章主要介绍了使用python实现数组、链表、队列、栈的相关知识,需要的朋友可以参考下
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等
两个文件 一个是数组实现循环队列 一个是链表实现 功能是常用的基本功能 希望对大家有所帮助
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
循环链表队列的代码实现 循环数组队列的代码实现
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf