- 浏览: 3462309 次
- 性别:
- 来自: 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 3888question:农场的母牛寿命是5年,母牛第二年和第四年会繁 ... -
树形显示
2011-07-17 11:26 1676/** 树形结构应用十分广泛。 下面这段代码根据 ... -
求能除尽1至n的最小整数
2011-07-16 02:43 4012为什么1小时有60分钟,而不是100分钟呢?这是历史上的 ... -
java 四则运算 栈的实现
2011-07-15 13:42 13892import java.util.Stack; /* ... -
用1、2、3、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列 要求:"4"不能在第三位,"3"与"5"不能相连。
2011-07-15 12:45 3412用1、2、3、3、4、5这六 ... -
【code】java红黑树
2011-06-28 10:07 3483import java.util.*; publi ... -
【code】java实现排序二叉树
2011-06-27 21:45 2900import java.util.*; publi ... -
【code】java创建哈夫曼树和实现哈夫曼编码
2011-06-27 17:31 12917创建哈夫曼树 主要思想: (1)对List集合中所有节点进 ... -
【code】java实现十种常见内部排序
2011-06-20 19:22 3121常见的内部排序: 下面介绍这十种常见内部排序(都是从 ... -
【code】java二叉树深(先中后)、广遍历
2011-06-19 16:55 1994import java.util.*; publi ... -
【code】java二叉树的实现
2011-06-17 22:50 5900二叉树的顺序存储 public class Array ... -
【code】java树的实现
2011-06-17 22:20 11990树的父节点存储实现 import java.util. ... -
【code】java栈和队列实现
2011-06-16 22:11 4987顺序栈的实现 import java.util.Arrays ...
相关推荐
7. **Java中的数据结构**:Java提供了多种内置数据结构,如线性表(ArrayList)、链表(LinkedList)、栈(Stack)、队列(Queue)、图(Map)和树(Tree)等,这些数据结构在解决问题时扮演着重要角色。 8. **OOP...
java索引QT practice //QT 练习代码LinuxHelloWorldsignalslotc++ primer plus//《C++ primer plus》笔记及练习代码c++ programming style//《C++ 编码风格》笔记及练习代码c++ qt design pattern//《C++ QT设计模式...
ArrayList是基于串联实现的线性表,没有最大容量限制(实际上有,是Integer.MAX_VALUE),可扩容。LinkedList是基于串联实现的线性表(双向链表),没有最大容量限制。 LinkedList还实现了Deque接口,可以作为单向...
在实际应用中,数组和链表是最常见的线性表实现方式。数组提供了随机访问的优势,但插入和删除操作可能涉及大量元素的移动;链表则在插入和删除上更灵活,但访问速度较慢。 2. **栈**:栈是一种后进先出(LIFO)的...
每个顶点用`DataType`结构体表示,包括景点名称(`char name[20]`)、代号(`int code`)和简介(`char introduction[50]`)。此外,`RowColWeight`结构体用于描述两个景点之间的连接,包含行索引(`int row`)、列...
通过上述分析,我们可以看到`ArrayList`是一个基于动态数组实现的线性表,它支持高效的随机访问和插入删除操作。通过合理的扩容策略,`ArrayList`能够在保证空间利用率的同时减少数组复制的开销。此外,`ArrayList`...
24. App-Code文件夹:在ASP.NET中,App-Code文件夹通常用于存放共享的代码文件。 25. MouseListener接口:MouseListener接口处理鼠标按钮的点击、释放、进入和退出事件,但不处理鼠标移动事件,需要...
2. **实验环境**:可能包括使用的编程语言(如C++、Java或Python)、开发工具(IDE如Visual Studio Code、Eclipse)以及任何必要的库或框架。 3. **实验内容**:通常涵盖一系列具体的数据结构实现,如线性表、链表...
leetcode手册JAVA CGADS ChenGuang Algorithm and Data Structure library :sun: Keys 线性表 链表 二叉树 遍历 前序遍历 中序遍历 后序遍历 层序遍历 二叉树的序列化和反序列化 二叉树两结点的最近共同祖先结点...
它结合了多种语言的优点,如C++的强大功能和Java的易用性,同时还引入了一些创新特性,如垃圾回收机制,从而简化了内存管理的工作。C#语言简洁、高效、易于学习,是.NET平台的首选语言之一。 #### 二、本书编写背景...
- 在Java中,实现软件重用的技术包括: - **平台无关性**:Java代码可以在任何支持Java虚拟机(JVM)的操作系统上运行,无需重新编译。 - **Java虚拟机(JVM)**:提供了一个抽象的计算机环境,使得Java程序能够在不同...
22. 对象的hash code与equals:在Java等语言中,两个对象的hash code相同表示它们在哈希表中可能被视为相等,但equals相等的两个对象的hash code通常也应该是相等的,但不是必须的。特殊情况如重写hash code方法可能...
基础数据结构,如线性表、栈等 基础算法,如递推、递归 编程语言 编程语言掌握任意一门即可,推荐C++或Java C++教程: C教程: Java教程: Python3教程: 推荐编程工具 C / C++ Dev-C++(Windows,自动配置编译器) ...
传统的数据结构教材多使用如PASCAL、C、C++和JAVA等语言编写,而C#语言版的数据结构教材在国内较为罕见。这不仅是对现有教学资源的补充,更是顺应了C#语言和.NET平台在软件开发领域日益增长的需求。本书通过C#语言来...
- **第2章至第6章**:分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,并且探讨了在.NET框架中对应的实现方式。 - **第7章和第8章**:深入分析了排序和查找算法,包括各种经典的...