数据结构之链表与数组(一)—数组实现队列
一、数组与链表简介
对于一组数据,在计算机的内存中的存储形式可以分为连续存储和离散存储两种,它们对应了我们通常所说的数组和链表。当内存空间中有足够大的连续空间时,可以把数据连续的存放在内存中,各种编程语言中的数组一般都是按这种方式存储的;当内存中只有一些离散的可用空间时,为了能把这些空间中存储的数据联系起来,需要在前一块数据的存储空间中记录下一块数据的地址,这样只要知道第一块内存空间的地址就能环环相扣地把数据集整体联系在一起了, 这便是链表存储数据的方式。
由于数组是连续存储的,在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据,但是如果要在数据组中任意位置上插入一个元素,就需要先把后面的元素集体向后移一位为其空出存储空间。与之相反,链表是离散存储的,所以在插入一个数据时只要申请一片新空间,然后将其中的连接关系做一个修改就可以,但是显然在链表上查找一个数据时就要逐个遍历了。考虑以上的总结可见,数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组;当对数据集中的数据进行添加或删除比较多时最好选择链表。
二、数组实现队列
下面通过数组对数据进行操作,主要功能有:
1、在队列末尾添加数据;
public void add(Object obj) { // 实例化一个新数组对象,其长度比原数组大一 Object[] arr2 = new Object[arr.length+1]; //将原来的数组复制到新的数组 for(int i=0;i<arr.length;i++){ arr2[i] = arr[i]; } //在arr2数组的最后添加obj arr2[arr.length-1] = obj; //覆盖原数组 arr = arr2; }
2、从队列中取指定位置的数据;
public Object get(int index) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ //提示错误 System.out.println("index= "+index+" 超出队列范围"); } //返回该数据 else{ return arr[index-1]; } }
3、删除队列中指定位置的数据,并且返回被指定删除的数据;
public Object remove(int index) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ //提示错误 System.out.println("index= "+index+" 超出队列范围"); } else{ //新建一个数组 Object[] arr2 = new Object[arr.length-1]; //将该数据保存 Object a = arr[index-1]; //把要删除的数据之前的数据复制到新数组 for(int i = 0 ; i < index; i++){ arr2[i] = arr[i]; } //将之后的数据复制到新数组 for(int i = index-1;i < arr2.length;i++){ arr2[i] = arr[i+1]; } //覆盖原数组 arr = arr2; //返回被删除的数据 return a; } }
4、插入数据到队列中的某个位置;
//将数据obj插入到队列的index位置 public void inser(int index, Object obj) { // TODO Auto-generated method stub //判断index是否超出队列 if( index < 0 || index >arr.length-1){ System.out.println("index= "+index+" 超出队列范围"); } else{ Object[] arr2 = new Object[arr.length+1]; //复制index位置前的数据 for(int i = 0 ; i < index-2;i++){ arr2[i] = arr[i]; } //复制index位置后的数据 for(int i = index; i < arr.length;i++){ arr2[i] = arr[i]; } //插入新数据 arr2[index-1] = obj; //覆盖原数组 arr = arr2; } }
5、返回原队列中数据的长度;
public int size() { // TODO Auto-generated method stub return arr.length; }
以上为自己定义的数组实现队列,此外,我们仍可以使用Java中已定义好的ArrayList类来对队列数据进行操作,此处不详细介绍。
相关推荐
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
数据结构的定义 数据结构是计算机存储、组织数据的方式,用于高效地访问和修改数据。...Java提供了丰富的数据结构库,包括数组、链表、栈、队列等,这些数据结构为程序员提供了处理各种问题的工具和方法。
数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
在队列的代码中,引用了链表的代码
常见的数据结构(栈、队列、数组、链表和红黑树) 数组和链表.pdf
目录: 数据结构中的一些概念 栈(stack) 队列 链表 python中字典对象实现原理 数组 一. 数据结构中的一些概念 1、数据结构是什么 简单来说,数据结果就是设计数据以何种...数据结构:数组、栈、队列、链表、树、图、
这份资料里面讲解的很清楚详细,易懂,对正在学习编程的同学特别是对正在找工作的同学非常有帮助。
链表是一种链式数据结构,由若干节点组成,每个节点包含指向下一个节点的指针。链表的物理存储方式是随机存储,访问方式是顺序访问。查找链表节点的时间复杂度是O[n],中间插入、删除节点的时间复杂度是O(1)。 栈 栈...
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
包含数据结构中线性表、链表、队列、栈、串等几种结构的常见操作,以及顺序和链式存储过程
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的,遵循先进先出原则的线性表。 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。 分解代码没有包含在内的代码如下: #include #...
数据结构实验报告+代码(链表 二叉树 图 字符串 数组 排序 队列 栈)
进行多项式运算,运用链表,队列,数组等数据结构。
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等
包括数据结构课程的各种程序:队列、二叉树、数组、图、稀疏矩阵、线性表和链表、栈