本文實例講述了C#實現順序表(線性表)的方法。分享給大家供大家參考，具體如下：
基本思想是使用數組作為盛放元素的容器，數組一開始的大小要實現確定，并使用一個Pointer指向順序表中最后的元素。順序表中的元素是數組中元素的子集。順序表在內存中是連續的，優勢是查找，弱勢是插入元素和刪除元素。
為避免裝箱拆箱，這里使用泛型，代替object。使用object的例子可以參照本站這篇文章：http://www.jfrwli.cn/article/208157.html，這個鏈接中的例子實現的是隊列，并沒 有使用Pointer來標識 順序表中最后一個元素，而是動態的調整數組的大小，這與本例明顯不同，動態調整數組大小開銷較大。使用object同樣可以完成順序表數據結構，但是頻繁裝箱拆箱造成較大的開銷，應使用泛型代替。
|
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
|
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace LinearList{ public interface IListDS<T> { int GetLength(); void Insert(T item, int i); void Add(T item); bool IsEmpty(); T GetElement(int i); void Delete(int i); void Clear(); int LocateElement(T item); void Reverse(); } //順序表類 class SequenceList<T>:IListDS<T> { private int intMaxSize;//最大容量事先確定，使用數組必須先確定容量 private T[] tItems;//使用數組盛放元素 private int intPointerLast;//始終指向最后一個元素的位置 public int MaxSize { get { return this.intMaxSize; } set { this.intMaxSize = value; } } public T this[int i]//索引器方便返回 { get { return this.tItems[i]; } } public int PointerLast { get { return this.intPointerLast; } } public SequenceList(int size) { this.intMaxSize = size; this.tItems = new T[size];//在這里初始化最合理 this.intPointerLast = -1;//初始值設為-1，此時數組中元素個數為0 } public bool IsFull()//判斷是否超出容量 { return this.intPointerLast+1 == this.intMaxSize; } #region IListDS<T> 成員 public int GetLength() { return this.intPointerLast + 1;//不能返回tItems的長度 } public void Insert(T item, int i)//設i為第i個元素，從1開始。該函數表示在第i個元素后面插入item { if (i < 1 || i > this.intPointerLast + 1) { Console.WriteLine("The inserting location is wrong!"); return; } if (this.IsFull()) { Console.WriteLine("This linear list is full! Can't insert any new items!"); return; } //如果可以添加 this.intPointerLast++; for(int j=this.intPointerLast;j>=i+1;j--) { this.tItems[j] = this.tItems[j - 1]; } this.tItems[i] = item; } public void Add(T item) { if (this.IsFull())//如果超出最大容量，則無法添加新元素 { Console.WriteLine("This linear list is full! Can't add any new items!"); } else { this.tItems[++this.intPointerLast] = item;//表長+1 } } public bool IsEmpty() { return this.intPointerLast == -1; } public T GetElement(int i)//設i最小從0開始 { if(this.intPointerLast == -1) { Console.WriteLine("There are no elements in this linear list!"); return default(T); } if (i > this.intPointerLast||i<0) { Console.WriteLine("Exceed the capability!"); return default(T); } return this.tItems[i]; } public void Delete(int i)//設i最小從0開始 { if (this.intPointerLast == -1) { Console.WriteLine("There are no elements in this linear list!"); return; } if (i > this.intPointerLast || i < 0) { Console.WriteLine("Deleting location is wrong!"); return; } for (int j = i; j < this.intPointerLast; j++) { this.tItems[j] = this.tItems[j + 1]; } this.intPointerLast--;//表長-1 } public void Clear() { this.intPointerLast = -1; } public int LocateElement(T item) { if (this.intPointerLast == -1) { Console.WriteLine("There are no items in the list!"); return -1; } for (int i = 0; i <= this.intPointerLast; i++) { if (this.tItems[i].Equals(item))//若是自定義類型，則T類必須把Equals函數override { return i; } } Console.WriteLine("Not found"); return -1; } public void Reverse() { if (this.intPointerLast == -1) { Console.WriteLine("There are no items in the list!"); } else { int i = 0; int j = this.GetLength() / 2;//結果為下界整數，正好用于循環 while (i < j) { T tmp = this.tItems[i]; this.tItems[i] = this.tItems[this.intPointerLast - i]; this.tItems[this.intPointerLast - i] = tmp; i++; } } } #endregion } class Program { static void Main(string[] args) { } }} |
基于順序表的合并排序：
|
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
|
//基于順序表的合并排序static private SequenceList<int> Merge(SequenceList<int> s1,SequenceList<int> s2){ SequenceList<int> sList = new SequenceList<int>(20); int i = 0; int j = 0; while(i<=s1.PointerLast&&j<=s2.PointerLast) { if (s1[i] < s2[j]) { sList.Add(s1[i]); i++; } else { sList.Add(s2[j]); j++; } } if (i > s1.PointerLast) { while (j <= s2.PointerLast) { sList.Add(s2[j]); j++; } return sList; } else//即j>s2.PointerLast { while (i <= s1.PointerLast) { sList.Add(s1[i]); i++; } return sList; }} |
希望本文所述對大家C#程序設計有所幫助。
