首先定义一个接口，无论线性存储的表还是链接存储的表都实现这个接口。
package list;
public interface List {
Object value(int pos);//返回第几个位置值
boolean add(Object obj,int pos);//在第几个位置添加
Object remove(int pos);//删除第几个位置的值
int find(Object obj);//查询第一个和obj相等的元素
boolean modify(Object obj,int pos);//修改某个值
boolean isEmpty();
int size();//长度
void forward();//前向输出
void backward();//后向输出
void clear();
List sort();//生成新的有序表，返回新的表
}
//有序表的接口（顺序存储和链接存储）
package list;
public interface SortedList extends List {
void insert(Object obj);
Object delete(Object obj);
int check(Object obj);
}
链接表需要定义节点
（有个疑问？head = new Node(head);这样做不是循环链表。）
实现线性表的链接存储
package list;
public class LinkList implements List {
private Node head;//头结点
private int lenth;//长度
public LinkList() {
// TODO Auto-generated constructor stub
//有个疑问？head = new Node(head);这样做不是循环链表。
lenth = 0;
head = new Node(null);
head.next =head;
}
//Node作为一个内置类
public class Node {
Node next;
Object ele;
public Node(Node n){
next = n;
}
public Node(Object e,Node n) {
// TODO Auto-generated constructor stub
next = n;
ele = e;
}
}
public Object value(int pos) {
// TODO Auto-generated method stub 判断给的位置是否超过范围
if(pos<1||pos>lenth){
return null;
}
int num = 1;
Node p = head.next;
while(num<pos){
num++;
p = p.next;
}
return p.ele;
}
public boolean add(Object obj, int pos) {
// TODO Auto-generated method stub
if(pos<1||pos>lenth+1){
return false;
}
int num = 1;
Node p = head,q = head.next;
while(num<pos){
p=q;q=q.next;
num++;
}//找到插入位置
p.next = new Node(obj,q);
lenth++;
return true;
}
public Object remove(int pos) {
// TODO Auto-generated method stub
if(pos<1||pos>lenth){
return false;
}
int num = 1;
Node p = head,q = head.next;
while(num<pos){
p=q;q=q.next;
num++;
}
p.next = q.next;
lenth--;
return q.ele;
}
public int find(Object obj) {
// TODO Auto-generated method stub
int num =1;
Node p = head.next;
while(p!=head&&p.ele.equals(obj)==false){
num++;
p = p.next;
}
if(p==head)return -1;
else
return num;
}
public boolean modify(Object obj, int pos) {
// TODO Auto-generated method stub
if(pos<1||pos>lenth){
return false;
}
int num = 1;
Node p = head.next;
while(num<pos){
p=p.next;
num++;
}
p.ele = obj;
return true;
}
public boolean isEmpty() {
// TODO Auto-generated method stub
return lenth==0;
}
public int size() {
// TODO Auto-generated method stub
return lenth;
}
public void forward() {
// TODO Auto-generated method stub
Node p = head.next;
while(p!=head){
System.out.println(p.ele.toString());
p = p.next;
}
}
public void backward() {
//新建一个数组，将链表中的拷贝进去，倒叙输出
// TODO Auto-generated method stub
Object []a = new Object[lenth];
int i =0;
Node p = head.next;
while(p!=head){
a[i++]=p.ele;
p = p.next;
}
for(i=lenth-1;i>=0;i--){
System.out.println(a[i].toString());
}
}
public void clear() {
// TODO Auto-generated method stub
lenth = 0;
head.next = head;
}
public List sort() {
// TODO Auto-generated method stub
//首先建立空表
//此次取出当前列表的值，
//寻找插入节点，
//插入
//时间复杂度为n*n
LinkList linklist = new LinkList();
Node r = head.next;
while(r!=head){
Object a = r.ele;
Node p = linklist.head,q = p.next;
while(q!=linklist.head){
Object y = q.ele;
if(((Comparable)a).compareTo(y)<0)break;
p=q;
q=q.next;
}
p.next = new Node(a,q);
lenth++;
r = r.next
}
return linklist;
}
}
总结：
在 获取第几个位置、删除某个位置的值得时候，使用一个 指针 就可以了，p 指向当前节点
在 第几个位置插入、删除时，需要两个指针，需要和前后联系起来。 p指向前一个节点，q指向当前节点。注意 if 的条件，在第一个位置插入元素时，我参考的这本书(pos>len)，根本无法插入，有错。修改了一下，可以在len+1的位置插入元素。
然后新建一个测试类，看看我们的链接存储的表。
package list;
public class LinkListTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList list = new LinkList();
int []a = {20,16,38,42,29};
for(int i =0;i<a.length;i++){
list.add(a[i], i+1);
}
list.forward();
int n = (Integer)list.remove(2);
System.out.println("删除的元素"+n);
System.out.println("删除后的链表");
list.forward();
System.out.println("修改第二个元素");
list.modify(100, 2);
list.forward();
System.out.print(list.size());
LinkList a1 = new LinkList();
a1 = (LinkList)list.sort();
a1.forward();
}
}
20
16
38
42
29
删除的元素16
删除后的链表
20
38
42
29
修改第二个元素
20
100
42
29
4
20
29
42
100
有序线性列表表的链接存储
LinkSortedList 继承 LinkList，实现接口 SortedList
在构造方法中，可以传一个list进来，调用insert方法自动排序添加。
package list;
public class LinkSortedList extends LinkList implements SortedList {
public LinkSortedList(){
super();
}
public LinkSortedList(LinkList list){
super();
for(int i=1;i<=list.size();i++){
this.insert(list.value(i));
}
}
public void insert(Object obj) {
//找到插入位置，下标从1开始，
// TODO Auto-generated method stub
int i ;
for(i=1;i<=size();i++){
if(((Comparable)obj).compareTo(this.value(i))<0)break;
}
add(obj, i);
}
public Object delete(Object obj) {
// TODO Auto-generated method stub
for(int i =1;i<=this.size();i++){
if(((Comparable)obj).compareTo(this.value(i))<0)return null;
if(((Comparable)obj).compareTo(this.value(i))==0)return remove(i);
}
return null;
}
public int check(Object obj) {
// TODO Auto-generated method stub
for(int i =1;i<=this.size();i++){
if(((Comparable)obj).compareTo(this.value(i))<0)return -1;
if(((Comparable)obj).compareTo(this.value(i))==0)return i;
}
return -1;
}
}
结果自己跑就可以了。
下部分，记录多项式求值。
网友评论