概述
在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点的结构为date域(值域),next(指针域)，每个指针域的值为其对应的后继元素或前驱元素所在结点(以后简称为后继结点或前驱结点)的引用(存储位置)。通过结点的指针域可以访问到对应的后继结点或前驱结点，该后继结点或前驱结点称为指针域所指向的结点。若一个结点中的某个指针域不需要指向任何结点，则令它的值为空(null)。
结点类定义
1
2
3
4
5
6
7
8
9
| public class Node {
Object date;
Node next;
public Node(Node nextval){next=nextval;}
public Node(Object obj,Node nextval){
date=obj;
next=nextval;
}
}
|
成员以及操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private Node head;
private int length;
public interface List {
public Object value(int n);
public boolean add(Object obj,int n);
public Object remove(int n);
public int find(Object obj,int n);
public boolean modify(Object obj,int n);
public boolean isEmpty();
public int size();
public void nextOrder();
public void preOrder();
public void clear();
public linkList sort();
}
|
操作实现
这里只演示单链表的实现(JAVA)
1.构造函数
1
2
3
4
5
| public linkList(){
length=0;
head=new Node(null);
head.next=head;
}
|
2.得到表中第n个元素的值
1
2
3
4
5
6
7
8
9
10
11
12
| public Object value(int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return null;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
return p.date;
}
|
3.向表中给定位置上插入一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public boolean add(Object obj, int n) {
if(n<1||n>length+1){
System.out.println("参数n的值不合法！"); return false;
}
int num=1;
Node p=head,q=head.next;
while(num<n){
p=q;
q=q.next;
num++;
}
p.next=new Node(obj,q);
length++;
return true;
}
|
4.从表中删除给定位置上的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public Object remove(int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return null;
}
int num=1;
Node p=head,q=head.next;
while(num<n){
num++;
p=q;
q=q.next;
}
p.next=q.next;
length--;
return q.date;
}
|
5.从表中指定位置开始按值查找对应的第一个元素并返回所在位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int find(Object obj, int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return -1;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
while(p!=head&&p.date.equals(obj)==false){
num++;
p=p.next;
}
if(p==head) return -1;
else return num;
}
|
6.修改表中给定位置的元素值
1
2
3
4
5
6
7
8
9
10
11
12
13
| public boolean modify(Object obj, int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return false;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
p.date=obj;
return true;
}
|
7.判断表是否为空
1
2
3
| public boolean isEmpty() {
return length==0;
}
|
8.求出表长度
1
2
3
| public int size() {
return length;
}
|
9.正序遍历表中所有元素
1
2
3
4
5
6
7
| public void nextOrder() {
Node p=head.next;
while(p!=head){
System.out.print(p.date.toString()+" ");
p=p.next;
}
}
|
10.反序遍历表中的所有元素
1
2
3
4
5
6
7
8
9
10
11
| public void preOrder() {
Object ar[]=new Object[length];
int i=0;
Node p=head.next;
while(p!=head){
ar[i++]=p.date;
p=p.next;
}
for(i=length-1;i>=0;i--)
System.out.print(ar[i].toString()+" ");
}
|
11.清除表中所有元素使之为空表
1
2
3
4
| public void clear() {
length=0;
head.next=head;
}
|
12.根据链表产生一个新的有序表并返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public linkList sort() {
linkList list;
list=new linkList();
Node n=head.next;
Comparable x,y;
while(n!=head){
x=(Comparable)n.date;
Node p=list.head,q=p.next;
while(q!=list.head){
y=(Comparable)q.date;
if(x.compareTo(y)<0) break;
p=q;
q=q.next;
}
p.next=new Node(n.date,q);
list.length++;
n=n.next;
}
return list;
}
|
整体代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| public class linkList implements List{
private Node head;
private int length;
public linkList(){
length=0;
head=new Node(null);
head.next=head;
}
public Object value(int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return null;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
return p.date;
}
public boolean add(Object obj, int n) {
if(n<1||n>length+1){
System.out.println("参数n的值不合法！"); return false;
}
int num=1;
Node p=head,q=head.next;
while(num<n){
p=q;
q=q.next;
num++;
}
p.next=new Node(obj,q);
length++;
return true;
}
public Object remove(int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return null;
}
int num=1;
Node p=head,q=head.next;
while(num<n){
num++;
p=q;
q=q.next;
}
p.next=q.next;
length--;
return q.date;
}
public int find(Object obj, int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return -1;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
while(p!=head&&p.date.equals(obj)==false){
num++;
p=p.next;
}
if(p==head) return -1;
else return num;
}
public boolean modify(Object obj, int n) {
if(n<1||n>length){
System.out.println("参数n的值不合法！"); return false;
}
int num=1;
Node p=head.next;
while(num<n){
num++;
p=p.next;
}
p.date=obj;
return true;
}
public boolean isEmpty() {
return length==0;
}
public int size() {
return length;
}
public void nextOrder() {
Node p=head.next;
while(p!=head){
System.out.print(p.date.toString()+" ");
p=p.next;
}
}
public void preOrder() {
Object ar[]=new Object[length];
int i=0;
Node p=head.next;
while(p!=head){
ar[i++]=p.date;
p=p.next;
}
for(i=length-1;i>=0;i--)
System.out.print(ar[i].toString()+" ");
}
public void clear() {
length=0;
head.next=head;
}
public linkList sort() {
linkList list;
list=new linkList();
Node n=head.next;
Comparable x,y;
while(n!=head){
x=(Comparable)n.date;
Node p=list.head,q=p.next;
while(q!=list.head){
y=(Comparable)q.date;
if(x.compareTo(y)<0) break;
p=q;
q=q.next;
}
p.next=new Node(n.date,q);
list.length++;
n=n.next;
}
return list;
}
}
|
