线性表
public class SqList<T> {
static int LIST_INIT_SIZE;
static int LIST_INCREMENT_SIZE;
private Object[] elements;
private int length; //当前有多少数据
private int listSize; //数组当前的大小
static //静态代码块初始化
{
LIST_INIT_SIZE = 100;
LIST_INCREMENT_SIZE = 10;
}
private void init() {
elements = null;
length = 0;
elements = new Object[LIST_INIT_SIZE];
listSize = 0;
}
public SqList() {
init();
}
public boolean add(T t) {
if (length >= listSize) {
/**
* 空间不足 扩大数组的容量
*/
listSize += LIST_INCREMENT_SIZE;//更新容量信息
Object[] newBase = new Object[listSize];
for (int i = 0; i < length; i++) {
newBase[i] = elements[i];
}
/**
* 更新信息
*/
newBase[length] = t;
length++;
elements = newBase;
} else {
elements[length++] = t;
}
System.out.println("添加一个数据");
return true;
}
public T get(int index) {
T wantToGet = null;
try {
wantToGet = (T) elements[index];
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("输入的位置不合法!");
}
return wantToGet;
}
public int size() {
return length;
}
public boolean set(int index, T t) {
T wantToGet = null;
try {
wantToGet = (T) elements[index];
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("输入的位置不合法!");
return false;
}
this.elements[index] = t;
return true;
}
public boolean insert(int index, T t) {
try {
T wantToGet = (T) elements[index];
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("输入的位置不合法!");
return false;
}
Object[] tem = new Object[length + 1];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < length + 1; i++) {
if (i < index) {
tem[i] = this.elements[i];
} else if (i == index) {
tem[i] = t;
} else if (i > index) {
tem[i] = this.elements[i - 1];
}
}
this.elements = tem;
length++;
return true;
}
public boolean remove(int index) {
try
{
T wantToGet = (T) elements[index];
} catch (ArrayIndexOutOfBoundsException e)
{
System.out.println("输入的位置不合法!");
return false;
}
Object[] tem = new Object[length - 1];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < length - 1; i++)
{
if (i < index)
{
tem[i] = this.elements[i];
}
else
{
tem[i] = this.elements[i + 1];
}
}
this.elements=tem;
length--;
return true;
}
}
有序线性表的归并
public class ListMethods
{
public static void mergeList(SequenceList<Integer> listA,SequenceList<Integer> listB,SequenceList<Integer>listC)
{
//线性表的归并 ,假设lista listb都是有序的 归并得到listC也是有序排列
int laLength=listA.size();
int lbLength=listB.size();
int lcLength=listC.size();
int i=0,j=0;
while (i<laLength&&j<lbLength)
{
if(listA.get(i)<listB.get(j))
{
listC.add(listA.get(i));
i++;
}
else
{
listC.add(listB.get(j));
j++;
}
}
while (i<laLength)listC.add(listA.get(i++));
while (j<lbLength)listC.add(listB.get(j++));
}
}
链表
public class LinkListPractice<E>
{
private class Node
{
E data;
Node next;
public Node(E data, Node next)
{
this.data = data;
this.next = next;
}
@Override
public String toString()
{
return data.toString();
}
}
private Node head;
private int size;
public LinkListPractice()
{
head= new Node(null,null);
size=0;
}
public int length(){return size;}
public boolean isEmpty(){return size==0;}
/**
* 向指定位置添加元素
* @param index
* @param data
*/
public void add(int index,E data)
{
if (index<0||index>size)throw new IllegalArgumentException("illegal index!");
Node pre=head;
for (int i=0;i<size;i++)
{
pre=pre.next;
}
pre.next=new Node(data,pre.next);
size++;
}
public void addFirst(E data)
{
add(0,data);
}
public void addLast(E data)
{
add(size,data);
}
@Override
public String toString()
{
StringBuilder builder=new StringBuilder();
builder.append("length:"+length()+"\n");
builder.append("head");
Node cur=head.next;
while (cur!=null)
{
builder.append("->"+cur.data);
cur=cur.next;
}
builder.append("->null");
return builder.toString();
}
/**
* 获取指定位置的元素
* @param index
* @return
*/
public E get(int index)
{
if (index<0||index>=size)throw new IllegalArgumentException("illegal index!");
Node cur =head.next;
for (int i=0;i<size;i++)
{
cur=cur.next;
}
return cur.data;
}
public E getFirst()
{
return get(0);
}
public E getLast()
{
return get(size-1);
}
/**
* 删除指定位置的元素
* @param index
* @return
*/
public E remove(int index)
{
if (index<0||index>=size)throw new IllegalArgumentException("illegal index!");
Node pre =head;
for (int i=0;i<index;i++)
{
pre=pre.next;
}
Node toDeleteNode=pre.next;
pre.next=toDeleteNode.next;
toDeleteNode.next=null;
size--;
return toDeleteNode.data;
}
/**
* 删除第一个出现的data元素
* @param data
*/
public void removeData(E data)
{
Node pre =head;
while (pre.next!=null)
{
if (pre.next.data.equals(data))
{
Node toDeleteNode = pre.next;
pre.next = toDeleteNode.next;
size--;
toDeleteNode.next = null;
break;
}
else
{
pre=pre.next;
}
}
}
public E removeFirst(){return remove(0);}
public E removeLast(){return remove(size-1);}
/**
* 删除所有出现的data
* @param data
*/
public void removeAll(E data)
{
Node pre =head;
while (pre.next!=null)
{
if (pre.next.data.equals(data))
{
Node toDeleteNode = pre.next;
pre.next = toDeleteNode.next;
size--;
toDeleteNode.next = null;
}
else
{
pre=pre.next;
}
}
}
public boolean contains(E data)
{
Node cur =head.next;
while (cur.next!=null)
{
if (cur.next.data.equals(data))
return true;
cur=cur.next;
}
return false;
}
}