概述
线性表主要有两种存储方式,分别是顺序存储以及链式存储.顺序存储一般使用数组来实现,链式存储用引用,相当于C语言中的指针.在Java的集合类中,ArrayList可以用来代表顺序表,LinkedList可以代表链表.
本来简单描述自定义的顺序表以及连接,并且引入Java泛型
IList接口
首先,我们定义一个IList接口:
package com.james.list; public interface IList<T> { public void clear(); public boolean isEmpty(); public int length(); public T get(int i) throws Exception; public void insert(int index, T x) throws Exception; public void remove(int index) throws Exception; public int indexOf(T x); public void display(); }
自定义ArrayList实现以及测试
package com.james.list; import java.util.Arrays; public class MyArrayList<T> implements IList<T> { private T[] elem; private int currLen; public MyArrayList(int maxSize) { currLen=0; elem = (T[])new Object[maxSize]; } public void clear() { currLen=0; } public boolean isEmpty() { return (currLen == 0); } public int length() { return currLen; } public T get(int i) throws Exception { if (i<0 || i> currLen -1) throw new Exception("The element is not existed for index: " + i); return elem[i]; } public void insert(int index, T x) throws Exception { if (currLen == elem.length) throw new Exception("The list is full"); if(index<0 ||index>currLen) throw new Exception("Wrong insert location"); for (int j= currLen; j>index; j--) elem[j] = elem[j-1]; elem[index] = x; currLen++; } public void remove(int index) throws Exception { if (index<0 || index>currLen -1) throw new Exception("Wrong deletion order"); for (int j=index; j<currLen ;j++) elem[j] = elem[j+1]; currLen--; } public int indexOf(T x) { int index = 0; while (index<currLen && !elem[index].equals(x)){ index++; } if (index<currLen) return index; else return -1; } public void display() { for (int index =0; index<currLen; index++) System.out.print(elem[index] + " "); System.out.println(); } public static void main(String[] arg) throws Exception{ IList arrList = new MyArrayList<String>(10); arrList.insert(0, "hellow"); arrList.insert(1, "world"); arrList.insert(2, "james"); arrList.insert(3, "hank"); arrList.display(); System.out.println("The index of james is: " + arrList.indexOf("james")); arrList.remove(0); arrList.display(); arrList.insert(2, "second"); arrList.display(); } }
自定义的Node类
package com.james.list; public class Node<T> { private T data; private Node next; public Node(){ this(null, null); } public Node(T data){ this(data, null); } public Node(T data, Node next) { this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }
简单的LinkedList实现:
package com.james.list; public class MyLinkedList<T> implements IList<T> { private Node head; public MyLinkedList() { head = new Node(); } public void clear() { head.setData(null); head.setNext(null); } public boolean isEmpty() { return head.getNext() == null; } public int length() { Node first = head.getNext();; int length = 0; while (first != null) { ++length; } return length; } public T get(int index) throws Exception { Node curr = head.getNext(); int i =0; while(curr.getNext()!=null && i<index){ curr = curr.getNext(); ++i; } if(i>index || curr==null){ throw new Exception("Get Wrong location from List"); } return (T)curr.getData(); } public void insert(int index, T x) throws Exception { Node curr = head; int j = -1; while(curr!=null && j<index-1){ curr=curr.getNext(); ++j; } if(j>index-1 || curr == null){ throw new Exception(" Wrong insert location"); } Node s = new Node(x); s.setNext(curr.getNext()); curr.setNext(s); } public void remove(int index) throws Exception { Node currNode = head; int i = -1; while(currNode.getNext()!=null && i < index-1){ currNode=currNode.getNext(); ++i; } if(i> index-1 || currNode.getNext() == null){ throw new Exception("Illegal deletion location"); } currNode.setNext(currNode.getNext().getNext()); } public int indexOf(T x) { Node currNode = head.getNext(); int index = 0; while(currNode != null && !currNode.getData().equals(x)) { currNode = currNode.getNext(); ++index; } if (currNode!=null) return index; else return -1; } public void display() { Node currNode = head.getNext(); while(currNode!=null){ System.out.println(currNode.getData()+ " "); currNode = currNode.getNext(); } } public static void main(String[] arg) throws Exception{ MyLinkedList ml = new MyLinkedList<String>(); ml.insert(0, "jingshou1"); ml.insert(1, "jingshou2"); ml.insert(2, "jingshou3"); ml.insert(3, "jingshou4"); ml.display(); ml.remove(1); ml.display(); System.out.println(ml.indexOf("jingshou4")); } }
两种线性表的比较:
- 顺序表查找快,但是插入效率低,需要移动元素
- 链接插入效率高,但是查找较慢
- 链表没有空间限制,顺序表有限制.可以实现自动扩容的顺序表,但是扩容后需要重新移动数据
相关推荐
对之前实现的JWList和JWArray加入泛型支持,最基本的都加入了对float、double、char、int类型的支持,支持自定义类型
目的:通过实现线性表的算法设计,掌握数据结构研究方法,算法设计和分析方法。 要求:①掌握线性表的顺序存储结构和链式存储结构实现,体会两者特点,分析算法效率;②掌握在MyEclipse等集成开发环境中程序的运行和...
定义接口,在泛型类中实现了线性表中的各种操作,包含增、删、改、查等。通过本实例,可以学习C#线性表相关内容,也可以学习到接口、类、泛型、索引器等相关知识,为下一步数据结构的学习打下坚实的基础。
使用C++类模板实现了线性表的顺序存储结构,类中包含了线性表的常用方法:向线性表中插入一个元素、删除一个元素、清空线性表、获取一个元素、获取线性表长度、...相关的文章可以在我的主页算法与数据结构专栏查看。
1 1 数据结构 1 1 1 1 学习数据结构的必要性 1 1 1 2 基本概念和术语 1 1 2 算法 4 1 2 1算法的特性 4 1 2 2算法的评价标准 5 1 2 3算法的时间复杂度 6 1 3 数学预备知识 7 1 3 1 集合 7 1 3 2 常用的数学术语 8 1 3...
1 1 数据结构 1 1 1 1 学习数据结构的必要性 1 1 1 2 基本概念和术语 1 1 2 算法 4 1 2 1算法的特性 4 1 2 2算法的评价标准 5 1 2 3算法的时间复杂度 6 1 3 数学预备知识 7 1 3 1 集合 7 1 3 2 常用的数学术语 8 1 3...
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...
其中包括了线性表、栈和队列、串和数组、树和图等数据结构的操作、排序等,非常适合进阶级的朋友学习.其中需要的预备知识数学中的集合、对数、递归等的回顾,还有C#语法中的接口和泛型的温习,从而更快的接受数据...
1.1.1 学习数据结构的必要性...1 1.1.2 基本概念和术语...............1 1.2 算法...4 1.2.1算法的特性............................4 1.2.2算法的评价标准....................5 1.2.3算法的时间复杂度...............
1、实现链式堆栈相关API函数 2、泛型编程思想 3、实体数据可以是基本类型或者复合类型 4、遍历时,使用回调函数。实现“策略”与“机制”分离 5、使用动态内存,保存链表节点及用户数据
泛型编程 异常类 线性表 数组 单链表 智能指针 循环链表 双向链表 内核链表 栈和队列 字符串 递归 排序 树 二叉树 图 BFS DFS Prim kruskal Dijkstra Floyd
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...
本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下: 基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是...
1.1 数据结构...................................................................................................................1 1.1.1 学习数据结构的必要性................................................
1.1 数据结构...................................................................................................................1 1.1.1 学习数据结构的必要性................................................
数据结构...................................................................................................................1 1.1.1 学习数据结构的必要性...................................................
1.1 数据结构...................................................................................................................1 1.1.1 学习数据结构的必要性................................................
1.1 数据结构...................................................................................................................1 1.1.1 学习数据结构的必要性..............................................