结点类
package DataStructures;
class CursorNode
{
// Friently data;accessible by other package routines
Object element;
int next;
// Constructers
CursorNode(Object theElement) {
this(theElement, 0);
}
CursorNode(Object theElement, int n) {
element = theElement;
next = n;
}
}
迭代器
package DataStructures;
public
class CursorListItr
{
int current; // Current position
CursorListItr(int theNode) {
current = theNode;
}
public boolean IsPastEnd() {
return current == 0;
}
public Object Retrieve() {
return IsPastEnd() ? null : CursorList.cursorSpace[current].element;
}
public void Advance() {
if (!IsPastEnd()) {
current = CursorList.cursorSpace[current].next;
}
}
}
主类
package DataStructures;
public
class CursorList
{
private int header;
static CursorNode[] cursorSpace;
private static final int SPACE_SIZE = 100;
static {
cursorSpace = new CursorNode[SPACE_SIZE];
for (int i = 0; i < SPACE_SIZE; i++) {
cursorSpace[i] = new CursorNode(null, i + 1);
}
cursorSpace[SPACE_SIZE - 1].next = 0;
}
private static int alloc() {
int p = cursorSpace[0].next;
cursorSpace[0].next = cursorSpace[p].next;
if (p == 0)
throw new OutOfMemoryError();
return p;
}
private static void free(int p) {
cursorSpace[p].element = null;
cursorSpace[p].next = cursorSpace[0].next;
cursorSpace[0].next = p;
}
public CursorList() {
header = alloc();
cursorSpace[header].next = 0;
}
public boolean IsEmpty() {
return cursorSpace[header].next == 0;
}
/**
* Make the list logically empty.
*/
public void MakeEmpty() {
while (!IsEmpty())
Remove(First().Retrieve());
}
public CursorListItr Zeroth() {
return new CursorListItr(header);
}
public CursorListItr First() {
return new CursorListItr(cursorSpace[header].next);
}
/**
* Return iterator corresponding to the first node containing an tiem.
*
* @param x
* the item to search for
* @return an iterator;iterator IsPastEnd if item is not found.
*/
public CursorListItr Find(Object x) {
int itr = cursorSpace[header].next;
while (itr != 0 && cursorSpace[itr].element.equals(x))
itr = cursorSpace[itr].next;
return new CursorListItr(itr);
}
/**
* Insert after p.
*
* @param x
* the item to insert.
* @param p
* the position prior to the newly inserted item.
*/
public void Insert(Object x, CursorListItr p) {
if (p != null && p.current != 0) {
int pos = p.current;
int tmp = alloc();
cursorSpace[tmp].element = x;
cursorSpace[tmp].next = cursorSpace[pos].next;
cursorSpace[pos].next = tmp;
}
}
/**
* Remove the first occurence of an item.
*
* @param x
* the item to remove.
*/
public void Remove(Object x) {
CursorListItr p = FindPrevious(x);
int pos = p.current;
if (cursorSpace[pos].next != 0) {
int tmp = cursorSpace[pos].next;
cursorSpace[pos].next = cursorSpace[tmp].next;
free(tmp);
}
}
/**
* Return iterator prior to the first node containing an item.
*
* @param x
* the item to search for.
* @return appropriate iterator if the item is found. Otherwise, the
* iterator corresponding to the last element in the list is
* returned.
*/
public CursorListItr FindPrevious(Object x) {
int itr = header;
while (cursorSpace[itr].next != 0
&& !cursorSpace[cursorSpace[itr].next].element.equals(x))
itr = cursorSpace[itr].next;
return new CursorListItr(itr);
}
}
package DataStructures;
class CursorNode
{ // Friently data;accessible by other package routines Object element; int next; // Constructers CursorNode(Object theElement) { this(theElement, 0); } CursorNode(Object theElement, int n) { element = theElement; next = n; }}
迭代器
package DataStructures;
public
class CursorListItr
{ int current; // Current position CursorListItr(int theNode) { current = theNode; } public boolean IsPastEnd() { return current == 0; } public Object Retrieve() { return IsPastEnd() ? null : CursorList.cursorSpace[current].element; } public void Advance() { if (!IsPastEnd()) { current = CursorList.cursorSpace[current].next; } }}
主类
package DataStructures;
public
class CursorList
{ private int header; static CursorNode[] cursorSpace; private static final int SPACE_SIZE = 100; static { cursorSpace = new CursorNode[SPACE_SIZE]; for (int i = 0; i < SPACE_SIZE; i++) { cursorSpace[i] = new CursorNode(null, i + 1); } cursorSpace[SPACE_SIZE - 1].next = 0; } private static int alloc() { int p = cursorSpace[0].next; cursorSpace[0].next = cursorSpace[p].next; if (p == 0) throw new OutOfMemoryError(); return p; } private static void free(int p) { cursorSpace[p].element = null; cursorSpace[p].next = cursorSpace[0].next; cursorSpace[0].next = p; } public CursorList() { header = alloc(); cursorSpace[header].next = 0; } public boolean IsEmpty() { return cursorSpace[header].next == 0; } /** * Make the list logically empty. */ public void MakeEmpty() { while (!IsEmpty()) Remove(First().Retrieve()); } public CursorListItr Zeroth() { return new CursorListItr(header); } public CursorListItr First() { return new CursorListItr(cursorSpace[header].next); } /** * Return iterator corresponding to the first node containing an tiem. * * @param x * the item to search for * @return an iterator;iterator IsPastEnd if item is not found. */ public CursorListItr Find(Object x) { int itr = cursorSpace[header].next; while (itr != 0 && cursorSpace[itr].element.equals(x)) itr = cursorSpace[itr].next; return new CursorListItr(itr); } /** * Insert after p. * * @param x * the item to insert. * @param p * the position prior to the newly inserted item. */ public void Insert(Object x, CursorListItr p) { if (p != null && p.current != 0) { int pos = p.current; int tmp = alloc(); cursorSpace[tmp].element = x; cursorSpace[tmp].next = cursorSpace[pos].next; cursorSpace[pos].next = tmp; } } /** * Remove the first occurence of an item. * * @param x * the item to remove. */ public void Remove(Object x) { CursorListItr p = FindPrevious(x); int pos = p.current; if (cursorSpace[pos].next != 0) { int tmp = cursorSpace[pos].next; cursorSpace[pos].next = cursorSpace[tmp].next; free(tmp); } } /** * Return iterator prior to the first node containing an item. * * @param x * the item to search for. * @return appropriate iterator if the item is found. Otherwise, the * iterator corresponding to the last element in the list is * returned. */ public CursorListItr FindPrevious(Object x) { int itr = header; while (cursorSpace[itr].next != 0 && !cursorSpace[cursorSpace[itr].next].element.equals(x)) itr = cursorSpace[itr].next; return new CursorListItr(itr); }}
本文转自冬冬博客园博客，原文链接：http://www.cnblogs.com/yuandong/archive/2006/08/20/481986.html
，如需转载请自行联系原作者
