本文實(shí)例講述了C#實(shí)現(xiàn)順序表(線性表)的方法。分享給大家供大家參考，具體如下：
基本思想是使用數(shù)組作為盛放元素的容器，數(shù)組一開始的大小要實(shí)現(xiàn)確定，并使用一個(gè)Pointer指向順序表中最后的元素。順序表中的元素是數(shù)組中元素的子集。順序表在內(nèi)存中是連續(xù)的，優(yōu)勢是查找，弱勢是插入元素和刪除元素。
為避免裝箱拆箱，這里使用泛型，代替object。使用object的例子可以參照本站這篇文章：http://www.zmynmublwnt.cn/article/208157.html，這個(gè)鏈接中的例子實(shí)現(xiàn)的是隊(duì)列，并沒 有使用Pointer來標(biāo)識 順序表中最后一個(gè)元素，而是動(dòng)態(tài)的調(diào)整數(shù)組的大小，這與本例明顯不同，動(dòng)態(tài)調(diào)整數(shù)組大小開銷較大。使用object同樣可以完成順序表數(shù)據(jù)結(jié)構(gòu)，但是頻繁裝箱拆箱造成較大的開銷，應(yīng)使用泛型代替。
|
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;//最大容量事先確定，使用數(shù)組必須先確定容量 private T[] tItems;//使用數(shù)組盛放元素 private int intPointerLast;//始終指向最后一個(gè)元素的位置 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;//初始值設(shè)為-1，此時(shí)數(shù)組中元素個(gè)數(shù)為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)//設(shè)i為第i個(gè)元素，從1開始。該函數(shù)表示在第i個(gè)元素后面插入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)//設(shè)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)//設(shè)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函數(shù)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;//結(jié)果為下界整數(shù)，正好用于循環(huán) 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#程序設(shè)計(jì)有所幫助。
