数据结构（java版）

Question

2、在SinglyLinkedList类中增加下列成员方法。
public SinglyLinkedList(E[] element)//由指定数组中的多个对象构造单链表
public SinglyLinkedList(SinglyLinkedList list)//以单链表list构造新的单链表，复制单链表
public void concat(SinglyLinkedList list)//将指定单链表list链接在当前单链表之后
public Node<E> search(E element)//若查找到指定，则返回结点，否则返回null
public boolean contain (E element)//以查找结果判断单链表是否包含指定对象
public boolean remove (E element)//移去首次出现的指定对象
public boolean replace (Object obj, E element)//将单链表中的obj对象替换为对象element
public boolean equals(Object obj)//比较两条单链表是否相等

实现代码：

Answer 1

package game24.datastructure.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 SinglyLinkedList<E>{
Node head; //头结点
int size; //链表的大小
public SinglyLinkedList() {
head = new Node();
size = 0;
}
public SinglyLinkedList(E[] datas) {
int n = datas.length;
head = new Node();
Node p = head;
for(int i=0; i<n; i++) {
p.next = new Node(datas[i]);
p = p.next;
}
size = n;
}
public SinglyLinkedList(SinglyLinkedList list) {
head = list.head;
size = list.size();
}
public void add(Object e) {
Node p;
if(0 == size) {
p = head;
} else {
p = index(size-1);
}
p.next = new Node(e);
size ++;
}

public void concat(SinglyLinkedList list) {
Node lastNode = this.index(size - 1);
lastNode.next = list.index(0);
size += list.size();
}

public void clear() {
head.next = null;
size = 0;
}

public Object get(int i) {
Node p = index(i);
return p.data;
}

private Node index(int i) {
Node p = null;
if(i>=0 && i<size){
p = head;
for(int j=0; j<=i; j++) {
p = p.next;
}
} 
return p;
}

public int indexOf(Object e) {
Node p = head.next;
int i = 0;
while(!p.data.equals(e)) {
p = p.next;
i++;
}
if(i<size)
return i;
else 
return -1;
}

public void insert(int i, Object e) {
Node p = index(i);
Node p2 = new Node(e);
p2.next = p.next;
p.next = p2;
size ++;
}

public boolean isEmpty() {
if(size ==0)
return true;
else
return false;
}

public int lastIndexOf(Object e) {
int i = size-1;
while(!get(i).equals(e)) {
i--;
}
if(i>=0)
return i;
else 
return -1;
}

public void remove(int i) {
if(i>=0 && i<size) {
Node p = null;
if(i == 0)
p = head;
else {
p = index(i-1);
}
p.next = index(i).next;
}
size --;
}

public void set(int i, Object e) {
Node p = index(i);
p.data = e;
}

public int size() {
return size; 
}
@Override
public boolean equals(Object obj) {
SinglyLinkedList list = (SinglyLinkedList)obj;
if(this == obj && size == list.size) {
return true;
}
return false;
}
/**
 * 测试线性表
 * @param args
 */
public static void main(String args[]) {
//List list = new LinkList();
//List list = new DoubleLinkList();
SinglyLinkedList list1 = new SinglyLinkedList();
for(int i=0; i<10; i++) {
list1.add(new Integer(i));
}
Integer [] a = {101, 102, 103, 104, 105, 106, 107, 108, 109, 110};
SinglyLinkedList list = new SinglyLinkedList(a);
list.remove(9);
System.out.print("size:" + list.size() + "\n");
System.out.println("isEmpty:" + list.isEmpty());
System.out.print("第7个位置的元素：" + list.get(7) + "\n");
list.concat(list1);
for(int i=0; i<list.size(); i++) {
System.out.print(list.get(i) + "    ");
}

list.add(21);
list.add(22);
list.insert(3, new Integer(5));
System.out.print("size:" + list.size() + "\n");
System.out.print("第一次出现5的索引：" + list.indexOf(5) + "\n");
System.out.print("最后一次出现5的索引：" + list.lastIndexOf(5) + "\n");
list.set(0, new Integer(30));
for(int i=0; i<list.size(); i++) {
System.out.print(list.get(i) + "    ");
}

SinglyLinkedList list2 = list;
System.out.println("\n is equels?  " + list2.equals(list));
}
}

Answer 2

没那么简单的。你这个写完全部代码要一天时间。

Answer 3

这需要点时间啊