节点类
package com.opensource.nodes;
/**
* 一个IntNode为链表提供一个节点,每个节点包含整形数据。链表可以具有任何长度,
* 仅受堆中空闲内存空间的限制。但是当超出Integer.MAX_VALUE时,listLengh将
* 因为算术溢出而不正确
*/
public class IntNode
{
private int data; //储存在这个节点中的元素
private IntNode link; //指向链表中的下一个节点
public IntNode(int initialData,IntNode initialLink)
{
data = initialData;
link = initialLink;
}
/**
* 在当前节点之后添加新节点
* @param element
*/
public void addNodeAfter(int element)
{
link =new IntNode(element,link);
}
/**
* 获取节点中储存的数值
* @return
*/
public int getData()
{
return data;
}
/**
* 获取指向当前节点的下一个节点的指针
*/
public IntNode getLink()
{
return link;
}
/**
* 复制链表
* @param source 将要复制的链表的头指针
* @return
*/
public static IntNode listCopy(IntNode source)
{
IntNode copyHead;
IntNode copyTail;
if(source == null)
return null;
copyHead = new IntNode(source.data,null);
copyTail = copyHead;
while(source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
return copyHead;
}
/**
* 复制链表,同时返回副本的头指针和为指针
* @param source 将要复制的链表的头指针
* @return
*/
public static IntNode[] listCopyWithTail(IntNode source)
{
IntNode copyHead;
IntNode copyTail;
IntNode[] answer = new IntNode[2];
if(source == null)
return null;
copyHead = new IntNode(source.data , null);
copyTail = copyHead;
while(source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* 获取链表的长度
* @param head
* @return
*/
public static int listLength(IntNode head)
{
IntNode cursor;
int answer = 0;
for(cursor = head;cursor !=null;cursor = head.link)
{
answer++;
}
return answer;
}
/**
* 复制链表的一部分,同时提供副本的头指针和尾指针
* @param start
* @param end
* @return
*/
public static IntNode[] listPart(IntNode start, IntNode end)
{
IntNode copyHead;
IntNode copyTail;
IntNode[] answer = new IntNode[2];
if(start == null)
throw new IllegalArgumentException("start is null");
if(end == null)
throw new IllegalArgumentException("end is null");
copyHead = new IntNode(start.data,null);
copyTail = copyHead;
while(start != end)
{
start = start.link;
if(start ==null)
throw new IllegalArgumentException
("end node was not found on the list");
copyTail.addNodeAfter(start.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* 查找位于链表中特定位置的节点
* @param head
* @param position
* @return
*/
public static IntNode listPosition(IntNode head,int position)
{
IntNode cursor;
int i;
if(position <= 0)
throw new IllegalArgumentException("position is not positive.");
cursor = head;
for(i = 1;(i < position)&&(cursor != null);i++)
cursor = cursor.link;
return cursor;
}
/**
* 查找链表中的特定数据
* @param head
* @param target
* @return
*/
public static IntNode listSearch(IntNode head,int target)
{
IntNode cursor;
for(cursor = head;cursor != null;cursor = cursor.link)
{
if(target == cursor.data)
return cursor;
}
return null;
}
/**
* 删除当前节点的下一个节点
*/
public void removeAfter()
{
link = link.link;
}
/**
* 设置当前节点中的数据
* @param newData
*/
public void setData(int newData)
{
data = newData;
}
/**
* 设置指向当前节点的下一个节点的指针
* @param newLink
*/
public void setLink(IntNode newLink)
{
link = newLink;
}
}
包操作类
package com.opensource.collections;
import com.opensource.nodes.IntNode;
/**
* 整形集合元素操作
* 单向链表实现
*/
public class IntLinkedBag implements Cloneable
{
//包ADT的不变式:
//1.包中的元素存储在链表中.
//2.链表的头指针位于实例变量head中.
//3.链表中的元素总数位于实例变量manyNodes;
private IntNode head; //链表的头指针
private int manyNodes; //链表的节点数
public IntLinkedBag()
{
head = null;
manyNodes = 0;
}
/**
* 添加一个新元素到包中
* @param element
*/
public void add(int element)
{
head = new IntNode(element,head);
manyNodes++;
}
/**
* 将另一个包中的内容添加到当前包中
* @param addend
*/
public void addAll(IntLinkedBag addend)
{
IntNode[] copyInfo;
if(addend == null)
throw new IllegalArgumentException("addend is null.");
if(addend.manyNodes > 0)
{
copyInfo = IntNode.listCopyWithTail(addend.head);
copyInfo[1].setLink(head);
head = copyInfo[0];
manyNodes += addend.manyNodes;
}
}
/**
* 生成当前包的副本
*/
public Object clone()
{
IntLinkedBag answer;
try
{
answer = (IntLinkedBag)super.clone();
}catch(CloneNotSupportedException e)
{
throw new RuntimeException
("This class does not implement Cloneable.");
}
answer.head = IntNode.listCopy(head);
return answer;
}
/**
* 统计特定元素在当前包中出现的次数
* @param target
* @return
*/
public int countOccurrences(int target)
{
int answer = 0;
IntNode cursor = IntNode.listSearch(head, target);
while(cursor != null)
{
answer++;
cursor = cursor.getLink();
cursor = IntNode.listSearch(cursor, target);
}
return answer;
}
/**
* 从当前包中检索一个随机元素
* @return
*/
public int grab()
{
int i;
IntNode cursor;
if(manyNodes == 0)
throw new IllegalArgumentException("Bag size is zero.");
i = (int)(Math.random()*manyNodes+1);
cursor = IntNode.listSearch(head, i);
return cursor.getData();
}
/**
* 从包中指定元素
* @param target
* @return
*/
public boolean remove(int target)
{
IntNode targetNode;
targetNode = IntNode.listSearch(head, target);
if(targetNode == null)
return false;
else
{
targetNode.setData(head.getData());
head = head.getLink();
manyNodes--;
return true;
}
}
/**
* 获取当前包中元素的个数
* @return
*/
public int size()
{
return manyNodes;
}
/**
* 创建一个新包,它包含来自其他两个包中的所有元素
* @param b1
* @param b2
* @return
*/
public static IntLinkedBag union(IntLinkedBag b1,IntLinkedBag b2)
{
if(b1 == null)
throw new IllegalArgumentException("b1 is null.");
if(b2 == null)
throw new IllegalArgumentException("b2 is null.");
IntLinkedBag answer = new IntLinkedBag();
answer.addAll(b1);
answer.addAll(b2);
return answer;
}
}
分享到:
相关推荐
4.2 用C语言表示单向链表 4.3 链式栈与链式队列 4.4 多项式 4.5 其它链表操作 4.6 等价类 4.7 稀疏矩阵 4.8 双向链表 第5章 树 5.1 引论 5.2 二叉树 5.3 遍历二叉树 5.4 其它二叉树操作 5.5 线索二叉树 ...
循环链表和单向链表基本一致,差别仅在于算法中循环的条件不是结点的指针是否为空,而是他们的指针是否等于头指针, 循环链表最后一个结点的 link 指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表...
9. 数据结构的抽象操作的定义与具体实现有关。( )【华南理工大学 2002 一、1(1分)】 10. 在顺序存储结构中,有时也存储数据结构中元素之间的关系。( )【华南理工大学 2002 一、2 (1分)】 11. 顺序存储方式的...
底层由单向链表组成,每个节点结 构如下所示:在⼤多数的应⽤场景中,读操作的⽐例远远⼤于写操作。那么,当执⾏读操作的时候,对数据是没 有修改的,所以,⽆须对数据进⾏加锁操作。⽽针对于写操作的场景中,则需要...
LinkedList是基于串联实现的线性表(双向链表),没有最大容量限制。 LinkedList还实现了Deque接口,可以作为单向和双向实例。 堆栈继承自向量,提供基础的堆栈操作。其保障线程安全的手段是使用同步的包装所有函数...
031106_【第11章:Java常用类库】_日期操作类(DateFormat、SimpleDateFormat)笔记.pdf 031107_〖第11章:Java常用类库〗_实例操作:取得当前日期笔记.pdf 031108_【第11章:Java常用类库】_Math与Random类笔记.pdf...
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...
八、 线性链表(单向链表、双向链表、循环链表) 九、 堆栈(先进后出):口袋装大米 十、 队列(先进先出):排对买大米 第三部分:非线性结构 十一、 树(根、叶、分支结点。其它:深度、度、父子兄弟) : 特点见...
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
• 数组(静态数组、动态数组)、线性表、链表(单向链表、双向链表、循环链表)、队列、栈、树(二叉树、查找树、平衡树、线索树、线索树、堆)、图等的定义、存储和操作 • Hash(存储地址计算,冲突处理) ...
第9章 slist单向链表容器 132 9.1 slist技术原理 132 9.2 slist应用基础 140 9.3 本章小结 148 第10章 bit_vector位向量容器 149 10.1 bit_vector技术原理 149 10.2 bit_vector应用基础 156 10.3 本...
在ANSI C中除了允许具有相同类型的结构变量相互赋值以外, 一般对结构变量的使用,包括赋值、输入、输出、 运算等都是通过结构变量的成员来实现的。 表示结构变量成员的一般形式是: 结构变量名.成员名 例如:...
第9章 slist单向链表容器 132 9.1 slist技术原理 132 9.2 slist应用基础 140 9.3 本章小结 148 第10章 bit_vector位向量容器 149 10.1 bit_vector技术原理 149 10.2 bit_vector应用基础 156 10.3 本...
第9章 slist单向链表容器 132 9.1 slist技术原理 132 9.2 slist应用基础 140 9.3 本章小结 148 第10章 bit_vector位向量容器 149 10.1 bit_vector技术原理 149 10.2 bit_vector应用基础 156 10.3 本...
1.3.2. 输入一个单向链表,输出该链表中倒数第 k 个结点............................. 44 1.3.3. 输入一个已经按升序排序过的数组和一个数字.................................... 46 1.3.4. 输入一颗二元查找树,...
27 <br>0056 强行改变运算符的运算顺序 27 <br>第3章 程序算法 29 <br>3.1 数据结构 30 <br>0057 如何实现单向链表 30 <br>0058 如何实现双向链表 35 <br>0059 如何实现堆栈 41 ...