Luckylau's Blog

阅读大话数据结构（2）

发表于 | 分类于 |

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解线性表，代码均为自己实现。

线性表

线性表表示0个或者多个数据元素的有限序列。

线性表的特性有:

除第一个元素外,每一个元素均有一个直接前驱，除最后一个元素外,每一个元素均有一个直接后继。

线性表抽象数据类型

IList接口如下：

1
2
3
4
5
6
7
8
9
public interface IList<E> {
	boolean isEmpty();
	void clear();
	E get(int i);
	boolean contains(Object o);
	E insert(int i , E e);
	E remove(int i);
	int size();
}

线性表的顺序存储结构

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
public class SequenceList<E> implements IList<E> {
	private final static int CAPACITY = 10;
	private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA =new Object[CAPACITY];
 	private Object[] elementData;
	private int size;
	
	@SuppressWarnings("unchecked")
	E elementData(int index){
		return (E) elementData[index];
	}
	
	public SequenceList(){
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}
	public SequenceList(int capacity){
		this.elementData = new Object[capacity];
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for ( int i = 0; i < size ; i++) {
			elementData[i] = null;
		}
		size = 0;	
	}
	@Override
	public E get(int i) {
		// TODO Auto-generated method stub
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
		return elementData(i);
	}
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		for(int i = 0 ; i < size ; i++) {
			if(o.equals(elementData[i])){
				return true;
			}
		}
		return false;
	}
	@Override
	public E insert(int i, E e) {
		// TODO Auto-generated method stub
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
		ensureCapacityInternal(++size);
		int length = size - i;
		System.arraycopy(elementData, i, elementData, i + 1, length);
		elementData[i] = e;
		return e;
	}
	private String outOfBoundsMsg(int i) {
		return "Index: " + i + ", Size: " + size;
	}
	@Override
	public E remove(int i) {
		// TODO Auto-generated method stub
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
		E oldvalue = elementData(i);
		int length = size - i - 1;
		System.arraycopy(elementData, i + 1, elementData, i, length);
		elementData[--size] = null;
		return oldvalue;
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	public boolean add(E e) {
		// TODO Auto-generated method stub
		ensureCapacityInternal(size + 1);
		elementData[size++] = e;
		return true;
	}
	
	private void ensureCapacityInternal(int capacity){
		if(elementData.length - capacity < 0) {
			grow(capacity);
		}
	}
	private void grow(int capacity){
		int oldcapacity = elementData.length;
		int newcapacity = oldcapacity + (oldcapacity >> 1);
		if(newcapacity < capacity){
			newcapacity = capacity;
		}
		elementData =Arrays.copyOf(elementData, newcapacity);
	}
}
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
public class Testdemo {
	public static void main(String[] args) {
		IList<String> list = new SequenceList<String>();
		System.out.println(list.size());
		System.out.println(list.isEmpty());
		list.add("a");
		list.add("b");
		list.add("c");
		list.add("d");
		list.insert(2, "e");
		list.insert(2, "f");
		list.insert(2, "g");
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		list.remove(2);
		list.remove(2);
		list.remove(2);
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		System.out.println(list.contains("c"));
		list.clear();
		System.out.println(list.size());
	}
}

线性表的链式存储结构

单链表

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
public class SinglelinkedList<E> implements IList<E> {
	private int size = 0;
	private Node<E> first;
	private Node<E> last;
	public SinglelinkedList(){	
      
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(Node<E> x = first; x != null;){
			Node<E> next = x.next;
			x.item = null;
			x.next = null;
			x = next;
		}
		first = null;
		last = null;
		size = 0;		
	}
	@Override
	public E get(int index) {
		// TODO Auto-generated method stub
		checkElementIndex(index);
		Node<E> x =first;
		if (index == 0) {
			return x.item;
		}
		for (int i = 0 ; i < index ; i++) {
			x = x.next;
		}
		E elem =x.item;
		return elem;
	}
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		if(first == null){
			return false;
		}
		Node<E> x = first;
		for( int i = 0 ; i < size ; i++){
			if(x.item.equals(o)){
				return true;
			}
			x = x.next;
		}
		return false;
	}
	@Override
	public E insert(int index, E e) {
		// TODO Auto-generated method stub
		checkElementIndex(index - 1);
		if(index == 0){
			final Node<E> newNode = new Node<E>(e, first);
			first = newNode;
		}else if(index == size){
			final Node<E> newNode = new Node<E>(e, null);
			last.next =newNode;
			last = newNode;
		}else{
			Node<E> x =first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			final Node<E> newNode = new Node<E>(e,x.next);
			x.next = newNode;
		}
		size++;
		return e;
	}
	@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		if(first == null){
			return null;
		}
		checkElementIndex(index);
		if(index == 0){
			E elem =first.item;
			first = first.next;
			size--;
			return elem;
		}else{
			Node<E> x =first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			Node<E> tmp = x.next;
			E elem = tmp.item;
			x.next = tmp.next;
			size--;
			return elem;
		}	
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	public boolean add(E e) {
		// TODO Auto-generated method stub
		final Node<E> newNode = new Node<E>(e,null);
		if(first == null && last == null){	
			last = newNode;
			first = newNode;
		}else{
			last.next = newNode;
			last = newNode;
		}
		size++;
		return true;
	}
	private void checkElementIndex(int i){
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
	}
	private String outOfBoundsMsg(int i) {
		return "Index: " + i + ", Size: " + size;
	}
	private static class Node<E>{
		E item;
		Node<E> next;
		public Node(E item ,Node<E> last){
			this.item = item;
			this.next = last;
		}
	}
}

双向循环链表

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
public class DoublylinkedList<E> implements IList<E> {
	private int size = 0;
	private Node<E> first;
	private Node<E> last;
	public DoublylinkedList(){
		
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(Node<E> x = first; x != null;){
			Node<E> next = x.next;
			x.item = null;
			x.next = null;
			x.before = null;
			x = next;
		}
		first = null;
		last = null;
		size = 0;		
	}
	@Override
	public E get(int index) {
		// TODO Auto-generated method stub
		
		if (index == 0) {
			return first.item;
		}else if(index < (size >>1)){
			Node<E> x =first;
			for (int i = 0 ; i < index ; i++) {
				x = x.next;
			}
			E elem =x.item;
			return elem;
		}else{
			Node<E> x =last;
			for ( int i = size - 1; i > index; i--){
				x = x.before;
			}
			E elem =x.item;
			return elem;
		}
			
	}
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		if(first == null){
			return false;
		}
		Node<E> x = first;
		for( int i = 0 ; i < size ; i++){
			if(x.item.equals(o)){
				return true;
			}
			x = x.next;
		}
		return false;
	}
	@Override
	public E insert(int index, E e) {
		// TODO Auto-generated method stub
		checkElementIndex(index - 1);
		if(index == 0){
			final Node<E> newNode = new Node<E>(last,e, first);
			first.before = newNode;
			first = newNode;
			last.next = first;		
		}else if(index == size){
			final Node<E> newNode = new Node<E>(last,e, first);
			first.before = newNode;
			last.next =newNode;
			last = newNode;
		}else if(index < (size >>1)){
			Node<E> x = first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			final Node<E> newNode = new Node<E>(x,e,x.next);
			x.next.before = newNode;
			x.next = newNode;
		}else {
			Node<E> x = last;
			for(int i = size - 1; i > index - 1; i--){
				x =x.before;
			}
			final Node<E> newNode = new Node<E>(x,e,x.next);
			x.next.before = newNode;
			x.next = newNode;
		}
		size++;
		return e;
	}
	@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		if(first == null){
			return null;
		}
		checkElementIndex(index);
		if(index == 0){
			E elem =first.item;
			Node<E> x = first.next;
			x.before = last;
			last.next = x;
			first = x;
			size--;
			return elem;
		}else{
			Node<E> x =first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			Node<E> tmp = x.next;
			E elem = tmp.item;
			x.next = tmp.next;
			tmp.next.before =x;
			size--;
			return elem;
		}	
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	public boolean add(E e) {
		// TODO Auto-generated method stub
		final Node<E> newNode = new Node<E>(null,e,null);
		if(first == null && last == null){	
			last = newNode;
			last.before = last;
			last.next = last;
			first = newNode;
		}else{
			newNode.before = last;
			last.next = newNode;
			last = newNode;
			last.next = first;
            first.before = last;
		}
		size++;
		return true;
	}
	
	private void checkElementIndex(int i){
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
	}
	private String outOfBoundsMsg(int i) {
		return "Index: " + i + ", Size: " + size;
	}
	private static class Node<E>{
		E item;
		Node<E> next;
		Node<E> before;
		public Node(Node<E> before,E item ,Node<E> last){
			this.before = before;
			this.item = item;
			this.next = last;
		}
	}
}
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
public class Testdemo {
	public static void main(String[] args) {
		IList<String> list = new DoublylinkedList<String>();
		System.out.println("list.size()"+list.size());
		System.out.println(list.isEmpty());
		list.add("a");
		list.add("b");
		list.add("c");
		list.add("d");
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		list.insert(4, "e");
		list.insert(5, "f");
		list.insert(6, "g");
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		list.insert(5, "f");
		list.remove(0);
		list.remove(2);
		list.remove(2);
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		System.out.println("index > size "+list.get(4));
		System.out.println("index > size "+list.get(5));
		System.out.println("index > size "+list.get(6));
		System.out.println("index > size "+list.get(7));
		System.out.println("index > size "+list.get(8));
		System.out.println(list.contains("c"));
		list.clear();
		System.out.println(list.size());
	}
}

循环链表

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
public class CircularlinkedList<E> implements IList<E> {
	private int size = 0;
	private Node<E> first;
	private Node<E> last;
	public CircularlinkedList(){
		
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(Node<E> x = first; x != null;){
			Node<E> next = x.next;
			x.item = null;
			x.next = null;
			x = next;
		}
		first = null;
		last = null;
		size = 0;		
	}
	@Override
	public E get(int index) {
		// TODO Auto-generated method stub
			Node<E> x =first;
			if (index == 0) {
				return x.item;
			}
			for (int i = 0 ; i < index ; i++) {
				x = x.next;
			}
			E elem =x.item;
			return elem;	
	}
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		if(first == null){
			return false;
		}
		Node<E> x = first;
		for( int i = 0 ; i < size ; i++){
			if(x.item.equals(o)){
				return true;
			}
			x = x.next;
		}
		return false;
	}
	@Override
	public E insert(int index, E e) {
		// TODO Auto-generated method stub
		checkElementIndex(index - 1);
		if(index == 0){
			final Node<E> newNode = new Node<E>(e, first);
			first =newNode;
			last.next= first;
		}else if(index == size){
			final Node<E> newNode = new Node<E>(e, first);
			last.next =newNode;
			last = newNode;
		}else{
			Node<E> x =first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			final Node<E> newNode = new Node<E>(e,x.next);
			x.next = newNode;
		}
		size++;
		return e;
	}
	@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		if(first == null){
			return null;
		}
		checkElementIndex(index);
		if(index == 0){
			E elem =first.item;
			first = first.next;
			last.next = first;
			size--;
			return elem;
		}else{
			Node<E> x =first;
			for (int i = 0 ; i < index - 1; i++) {
				x = x.next;
				}
			Node<E> tmp = x.next;
			E elem = tmp.item;
			x.next = tmp.next;
			size--;
			return elem;
		}	
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	public boolean add(E e) {
		// TODO Auto-generated method stub
		final Node<E> newNode = new Node<E>(e,null);
		if(first == null && last == null){	
			last = newNode;
			last.next = newNode;
			first = last;
		}else{
			last.next = newNode;
			last = newNode;
			last.next = first;
		}
		size++;
		return true;
	}	
	private void checkElementIndex(int i){
		if( i >= size){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(i));
		}
	}
	private String outOfBoundsMsg(int i) {
		return "Index: " + i + ", Size: " + size;
	}
	private static class Node<E>{
		E item;
		Node<E> next;
		public Node(E item ,Node<E> last){
			this.item = item;
			this.next = last;
		}
	}
}
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
public class Testdemo {
	public static void main(String[] args) {
		IList<String> list = new CircularlinkedList<String>();
		System.out.println("list.size()"+list.size());
		System.out.println(list.isEmpty());
		list.add("a");
		list.add("b");
		list.add("c");
		list.add("d");
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		list.insert(4, "e");
		list.insert(5, "f");
		list.insert(6, "g");
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		list.remove(0);
		list.remove(2);
		list.remove(2);
		System.out.println("list.size() = "+list.size());
		for ( int i = 0; i < list.size();i++){
			System.out.println(list.get(i));
		}
		System.out.println("index > size "+list.get(4));
		System.out.println("index > size "+list.get(5));
		System.out.println("index > size "+list.get(6));
		System.out.println("index > size "+list.get(7));
		System.out.println("index > size "+list.get(8));
		System.out.println(list.contains("c"));
		list.clear();
		System.out.println(list.size());
	}
}
Luckylau wechat
如果对您有价值,看官可以打赏的！