- 浏览: 3435617 次
- 性别:
- 来自: China
文章分类
- 全部博客 (536)
- ajax (1)
- Algorithm (14)
- Android (40)
- CSS/HTML... (2)
- defy (3)
- DesignPattern (2)
- dorado (0)
- Drools (6)
- English/日本語 (7)
- Flex (2)
- Framework (0)
- Google (3)
- hibernate (13)
- homework (3)
- HTML5 (0)
- IDE (29)
- java (45)
- javaee (7)
- Javascript (14)
- java组件 (5)
- jQuery (4)
- jsp (8)
- jsf (2)
- Linux (2)
- lucene (0)
- mysql (6)
- news (3)
- Oracle (8)
- other (4)
- PHP (5)
- Python (0)
- Software Engineering (3)
- spring (7)
- struts1.x (14)
- struts2.x (14)
- strolling in cloud (1)
- subject:javaEnhance (20)
- Tomcat (7)
- validator (3)
- 学习·方法·心得 (8)
- .NET (2)
- vba (6)
- groovy (5)
- grails (2)
- SWT (0)
- big data (1)
- perl (1)
- objective-c (50)
- product (1)
- mac (7)
- ios (188)
- ios-phone (2)
- ios-system (15)
- ios-network (5)
- ios-file (4)
- ios-db (1)
- ios-media (3)
- ios-ui (27)
- ios-openSource (6)
- ios-animation (5)
- ios-drawing (7)
- c (2)
- ios-app (2)
- ios-course (15)
- ios-runtime (14)
- ios-code (8)
- ios-thread (8)
- ios-LBS (2)
- ios-issue (1)
- ios-design (2)
- Jailbreak (2)
- cocos2d (0)
- swift (16)
- ios-framework (4)
- apple watch (4)
- ios-web (1)
- react native (3)
- TVOS (1)
- OpenGL (1)
最新评论
-
xiaobinggg:
...
Session机制详解 -
菜鸟学生会:
Drools规则工作流引擎开发教程网盘地址:http://pa ...
Drools入门-----------环境搭建,分析Helloworld -
wangyudong:
不是很好用,不支持自动化测试RESTful API,也不支持自 ...
Simple REST Client POST使用方法 -
Paul0523:
很棒的一篇文章,感谢楼主分享
Session机制详解 -
啸笑天:
获取原型对象的三种方法<script>functi ...
复习JavaScript面向对象技术
顺序线性表的实现
import java.util.Arrays; public class SequenceList<T> { private int DEFAULT_SIZE = 16; //保存数组的长度。 private int capacity; //定义一个数组用于保存顺序线性表的元素 private Object[] elementData; //保存顺序表中元素的当前个数 private int size = 0; //以默认数组长度创建空顺序线性表 public SequenceList() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一个初始化元素来创建顺序线性表 public SequenceList(T element) { this(); elementData[0] = element; size++; } /** * 以指定长度的数组来创建顺序线性表 * @param element 指定顺序线性表中第一个元素 * @param initSize 指定顺序线性表底层数组的长度 */ public SequenceList(T element , int initSize) { capacity = 1; //把capacity设为大于initSize的最小的2的n次方 while (capacity < initSize) { capacity <<= 1; } elementData = new Object[capacity]; elementData[0] = element; size++; } //获取顺序线性表的大小 public int length() { return size; } //获取顺序线性表中索引为i处的元素 public T get(int i) { if (i < 0 || i > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } return (T)elementData[i]; } //查找顺序线性表中指定元素的索引 public int locate(T element) { for (int i = 0 ; i < size ; i++) { if (elementData[i].equals(element)) { return i; } } return -1; } //向顺序线性表的指定位置插入一个元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("线性表索引越界"); } ensureCapacity(size + 1); //将index处以后所有元素向后移动一格。 System.arraycopy(elementData , index , elementData , index + 1 , size - index); elementData[index] = element; size++; } //在线性顺序表的开始处添加一个元素。 public void add(T element) { insert(element , size); } //很麻烦,而且性能很差 private void ensureCapacity(int minCapacity) { //如果数组的原有长度小于目前所需的长度 if (minCapacity > capacity) { //不断地将capacity * 2,直到capacity大于minCapacity为止 while (capacity < minCapacity) { capacity <<= 1; } elementData = Arrays.copyOf(elementData , capacity);//此方法jdk1.6开始提供 } } //删除顺序线性表中指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } T oldValue = (T)elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData , index+1 , elementData, index , numMoved); } //清空最后一个元素 elementData[--size] = null; return oldValue; } //删除顺序线性表中最后一个元素 public T remove() { return delete(size - 1); } //判断顺序线性表是否为空表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null Arrays.fill(elementData , null); size = 0; } public String toString() { if (size == 0) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (int i = 0 ; i < size ; i++ ) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } public static void main(String[] args) { SequenceList<String> list = new SequenceList<String>(); list.add("aaaa"); list.add("bbbb"); list.add("cccc"); //在索引为1处插入一个新元素 list.insert("dddd" , 1); //输出顺序线性表的元素 System.out.println(list); //删除索引为2处的元素 list.delete(2); System.out.println(list); //获取cccc字符串在顺序线性表中的位置 System.out.println("cccc在顺序线性表中的位置:" + list.locate("cccc")); } }
链式线性表的实现:单链表
public class LinkList<T> { //定义一个内部类Node,Node实例代表链表的节点。 private class Node { //保存节点的数据 private T data; //指向下个节点的引用 private Node next; //无参数的构造器 public Node() { } //初始化全部属性的构造器 public Node(T data , Node next) { this.data = data; this.next = next; } } //保存该链表的头节点 private Node header; //保存该链表的尾节点 private Node tail; //保存该链表中已包含的节点数 private int size; //创建空链表 public LinkList() { //空链表,header和tail都是null header = null; tail = null; } //以指定数据元素来创建链表,该链表只有一个元素 public LinkList(T element) { header = new Node(element , null); //只有一个节点,header、tail都指向该节点 tail = header; size++; } //返回链表的长度 public int length() { return size; } //获取链式线性表中索引为index处的元素 public T get(int index) { return getNodeByIndex(index).data; } //根据索引index获取指定位置的节点 private Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } //从header节点开始 Node current = header; for (int i = 0 ; i < size && current != null ; i++ , current = current.next) { if (i == index) { return current; } } return null; } //查找链式线性表中指定元素的索引 public int locate(T element) { //从头节点开始搜索 Node current = header; for (int i = 0 ; i < size && current != null ; i++ , current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } //向线性链式表的指定位置插入一个元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("线性表索引越界"); } //如果还是空链表 if (header == null) { add(element); } else { //当index为0时,也就是在链表头处插入 if (index == 0) { addAtHeader(element); } else { //获取插入点的前一个节点 Node prev = getNodeByIndex(index - 1); //让prev的next指向新节点,让新节点的next引用指向原来prev的下一个节点。 prev.next = new Node(element , prev.next); size++; } } } //采用尾插法为链表添加新节点。 public void add(T element) { //如果该链表还是空链表 if (header == null) { header = new Node(element , null); //只有一个节点,header、tail都指向该节点 tail = header; } else { //创建新节点 Node newNode = new Node(element , null); //让尾节点的next指向新增的节点 tail.next = newNode; //以新节点作为新的尾节点 tail = newNode; } size++; } //采用头插法为链表添加新节点。 public void addAtHeader(T element) { //创建新节点,让新节点的next指向原来的header //并以新节点作为新的header header = new Node(element , header); //如果插入之前是空链表 if (tail == null) { tail = header; } size++; } //删除链式线性表中指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } Node del = null; //如果被删除的是header节点 if (index == 0) { del = header; header = header.next; } else { //获取删除点的前一个节点 Node prev = getNodeByIndex(index - 1); //获取将要被删除的节点 del = prev.next; //让被删除节点的next指向被删除节点的下一个节点。 prev.next = del.next; //将被删除节点的next引用赋为null. del.next = null; } size--; return del.data; } //删除链式线性表中最后一个元素 public T remove() { return delete(size - 1); } //判断链式线性表是否为空表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //header、tail赋为null header = null; tail = null; size = 0; } public String toString() { //链表为空链表时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header ; current != null ; current = current.next ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } public static void main(String[] args) { LinkList<String> list = new LinkList<String>(); list.insert("aaaa" , 0); list.add("bbbb"); list.add("cccc"); //在索引为1处插入一个新元素 list.insert("dddd" , 1); //输出顺序线性表的元素 System.out.println(list); //删除索引为2处的元素 list.delete(2); System.out.println(list); //获取cccc字符串在链表中的位置 System.out.println("cccc在链表中的位置:" + list.locate("cccc")); System.out.println("链表中索引2处的元素:" + list.get(2)); } }
链式线性表的实现:双向链表
public class DuLinkList<T> { //定义一个内部类Node,Node实例代表链表的节点。 private class Node { //保存节点的数据 private T data; //指向上个节点的引用 private Node prev; //指向下个节点的引用 private Node next; //无参数的构造器 public Node() { } //初始化全部属性的构造器 public Node(T data , Node prev , Node next) { this.data = data; this.prev = prev; this.next = next; } } //保存该链表的头节点 private Node header; //保存该链表的尾节点 private Node tail; //保存该链表中已包含的节点数 private int size; //创建空链表 public DuLinkList() { //空链表,header和tail都是null header = null; tail = null; } //以指定数据元素来创建链表,该链表只有一个元素 public DuLinkList(T element) { header = new Node(element , null , null); //只有一个节点,header、tail都指向该节点 tail = header; size++; } //返回链表的长度 public int length() { return size; } //获取链式线性表中索引为index处的元素 public T get(int index) { return getNodeByIndex(index).data; } //根据索引index获取指定位置的节点 private Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } if (index <= size / 2) { //从header节点开始 Node current = header; for (int i = 0 ; i <= size / 2 && current != null ; i++ , current = current.next) { if (i == index) { return current; } } } else { //从tail节点开始搜索 Node current = tail; for (int i = size - 1 ; i > size / 2 && current != null ; i++ , current = current.prev) { if (i == index) { return current; } } } return null; } //查找链式线性表中指定元素的索引 public int locate(T element) { //从头节点开始搜索 Node current = header; for (int i = 0 ; i < size && current != null ; i++ , current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } //向线性链式表的指定位置插入一个元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("线性表索引越界"); } //如果还是空链表 if (header == null) { add(element); } else { //当index为0时,也就是在链表头处插入 if (index == 0) { addAtHeader(element); } else { //获取插入点的前一个节点 Node prev = getNodeByIndex(index - 1); //获取插入点的节点 Node next = prev.next; //让新节点的next引用指向next节点,prev引用指向prev节点 Node newNode = new Node(element , prev , next); //让prev的next指向新节点。 prev.next = newNode; //让prev的下一个节点的prev指向新节点 next.prev = newNode; size++; } } } //采用尾插法为链表添加新节点。 public void add(T element) { //如果该链表还是空链表 if (header == null) { header = new Node(element , null , null); //只有一个节点,header、tail都指向该节点 tail = header; } else { //创建新节点,新节点的pre指向原tail节点 Node newNode = new Node(element , tail , null); //让尾节点的next指向新增的节点 tail.next = newNode; //以新节点作为新的尾节点 tail = newNode; } size++; } //采用头插法为链表添加新节点。 public void addAtHeader(T element) { //创建新节点,让新节点的next指向原来的header //并以新节点作为新的header header = new Node(element , null , header); //如果插入之前是空链表 if (tail == null) { tail = header; } size++; } //删除链式线性表中指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("线性表索引越界"); } Node del = null; //如果被删除的是header节点 if (index == 0) { del = header; header = header.next; //释放新的header节点的prev引用 header.prev = null; } else { //获取删除点的前一个节点 Node prev = getNodeByIndex(index - 1); //获取将要被删除的节点 del = prev.next; //让被删除节点的next指向被删除节点的下一个节点。 prev.next = del.next; //让被删除节点的下一个节点的prev指向prev节点。 if (del.next != null) { del.next.prev = prev; } //将被删除节点的prev、next引用赋为null. del.prev = null; del.next = null; } size--; return del.data; } //删除链式线性表中最后一个元素 public T remove() { return delete(size - 1); } //判断链式线性表是否为空链表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null header = null; tail = null; size = 0; } public String toString() { //链表为空链表时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header ; current != null ; current = current.next ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } public String reverseToString() { //链表为空链表时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = tail ; current != null ; current = current.prev ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } public static void main(String[] args) { DuLinkList<String> list = new DuLinkList<String>(); list.insert("aaaa" , 0); list.add("bbbb"); list.insert("cccc" , 0); //在索引为1处插入一个新元素 list.insert("dddd" , 1); //输出顺序线性表的元素 System.out.println(list); //删除索引为2处的元素 list.delete(2); System.out.println(list); System.out.println(list.reverseToString()); //获取cccc字符串在顺序线性表中的位置 System.out.println("cccc在顺序线性表中的位置:" + list.locate("cccc")); System.out.println("链表中索引1处的元素:" + list.get(1)); list.remove(); System.out.println("调用remove方法后的链表:" + list); list.delete(0); System.out.println("调用delete(0)后的链表:" + list); } }
发表评论
-
qweqwe
2012-07-11 16:06 1江蛤蟆 一统江湖 -
123123123
2012-07-11 16:04 0<p>法轮</p> -
母牛繁殖问题
2011-12-30 13:08 3833question:农场的母牛寿命是5年,母牛第二年和第四年会繁 ... -
树形显示
2011-07-17 11:26 1638/** 树形结构应用十分广泛。 下面这段代码根据 ... -
求能除尽1至n的最小整数
2011-07-16 02:43 3957为什么1小时有60分钟,而不是100分钟呢?这是历史上的 ... -
java 四则运算 栈的实现
2011-07-15 13:42 13842import java.util.Stack; /* ... -
用1、2、3、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列 要求:"4"不能在第三位,"3"与"5"不能相连。
2011-07-15 12:45 3370用1、2、3、3、4、5这六 ... -
【code】java红黑树
2011-06-28 10:07 3439import java.util.*; publi ... -
【code】java实现排序二叉树
2011-06-27 21:45 2855import java.util.*; publi ... -
【code】java创建哈夫曼树和实现哈夫曼编码
2011-06-27 17:31 12877创建哈夫曼树 主要思想: (1)对List集合中所有节点进 ... -
【code】java实现十种常见内部排序
2011-06-20 19:22 3074常见的内部排序: 下面介绍这十种常见内部排序(都是从 ... -
【code】java二叉树深(先中后)、广遍历
2011-06-19 16:55 1951import java.util.*; publi ... -
【code】java二叉树的实现
2011-06-17 22:50 5848二叉树的顺序存储 public class Array ... -
【code】java树的实现
2011-06-17 22:20 11948树的父节点存储实现 import java.util. ... -
【code】java栈和队列实现
2011-06-16 22:11 4943顺序栈的实现 import java.util.Arrays ...
相关推荐
JAVA线性表JAVA线性表JAVA线性表JAVA线性表
压缩包中有两个.java文件,一个是接口一个是具体实现,使用java代码实现了线性表
java实现线性表 java实现线性表 java实现线性表 java实现线性表 java实现线性表 java实现线性表
用动态扩充实现线性表用动态扩充实现线性表
线性表实现.pdf线性表实现.pdf线性表实现.pdf线性表实现.pdf
java实现的简单线性表结构,包含顺序存储结构和单向链式存储结构的源码
用Java 实现的线性表的一些操作。线性表实现其实很简单,类似操作数组,只是添加删除时要注意下。
该源程序是数据结构的代码实现:用线性表实现一个一元多项式Polynomial
线性表,单链表,栈的代码实现,java简单实现,内附有代码少许注释
用线性表实现斗地主发牌程序,本人水平低劣,可供数据结构初学者参考,如有错误可留言指出
Java开发线性表;Java开发线性表;Java开发线性表;Java开发线性表;Java开发线性表;Java开发线性表;Java开发线性表;Java开发线性表;
用链表实现线性表java用链表实现线性表
用线性表写的通信录管理系统,资源只是把源代码写出来,并没有设计界面!代码写的也比较粗陋,适合刚学C++和数据结构的同学使用!
链式存储结构线性表的java实现,全代码注释,通俗易懂
数据结构课程中要求用线性表实现一个多项式,这是完整的实验报告.
用线性链表完成信息的存储、删除、遍历、修改,用线性表的直接选择排序完成学生信息按学号排序
java编写的线性表,用于理解数据结构中的线性表有很大帮助,使用Java原生sdk实现,内含源代码,可以运行。
线性表顺序存储的插入操作java.java
主要介绍了java 线性表接口的实现实例详解的相关资料,希望通过本能帮助到大家,需要的朋友可以参考下
线性表