线性表(二)
;
array = new Object[defLen];
}
@Override
public void clear() {
size = 0;
}
@Override
public Object get(int i) {
if(i>=0 && i
return array[i];
else
return null;
}
@Override
public int indexOf(Object e) {
int i =0;
while(i
i++;
}
if(i < size)
return i;
else
return -1;
}
@Override
public void insert(int i, Object e) {
if(i >= size) {
i = size;
if((size) >= maxLen)//如果插入数的位置大于顺序表的最大容量，则扩大容量
expand();
}
for(int j = size; j>i+1; j--) {
array[j] = array[j-1];
}
array[i+1] = e;
size ++;
}
@Override
public boolean isEmpty() {
if(size == 0)
return true;
else
return false;
}
@Override
public int lastIndexOf(Object e) {
int i = size-1;
while(i>=0 && !array[i].equals(e)) {
i--;
}
if(i>=0)
return i;
else
return -1;
}
@Override
public void remove(int i) {
for(int j=i; j
array[j] = array[j+1];
}
size --;
}
@Override
public void set(int i, Object e) {
array[i] = e;
}
@Override
public int size() {
return size;
}
/**
* 当顺序表的大小不够时，扩充顺序表的大小
*/
private void expand() {
maxLen = 2*maxLen;
Object newArray[] = new Object[maxLen];
for(int i=0; i
newArray[i] = array[i];
}
array = newArray;
}
@Override
public void add(Object e) {
if(size >=maxLen)
expand();
array[size] = e;
size ++;
}
}
单向循环链表
结构模型
带头结点的单链结构
(a)空链； (b)非空链
源代码
[java]
package list;
/**
* 链表的结点
* @author luoweifu
*
*/
class Node{
Object data; //数据元素
Node next; //后驱结点
public Node() {
this(null);
}
public Node(Object data) {
this.data = data;
this.next = null;
}
}
/**
* 带头结点的链式链表,下标从0开始;
* @author Administrator
*
*/
public class LinkList implements List {
Node head; //头结点
int size; //链表的大小
public LinkList() {
head = new Node();
size = 0;
}
public LinkList(Object[] datas) {
int n = datas.length;
head = new Node();
Node p = head;
for(int i=0; i
p.next = new Node(datas[i]);
p = p.next;
}
size = n;
}
@Override
public void add(Object e) {
Node p;
if(0 == size) {
p = head;
} else {
p = index(size-1);
}
p.next = new Node(e);
size ++;
}
@Override
public void clear() {
head.next = null;
size = 0;
}
@Override
public Object get(int i) {
Node p = index(i);
return p.data;
}
private Node index(int i) {
Node p = null;
if(i>=0 && i
p = head;
for(int j=0; j<=i; j++) {
p = p.next;
}
}
return p;