本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考，具体如下：
基本思想是使用数组作为盛放元素的容器，数组一开始的大小要实现确定，并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的，优势是查找，弱势是插入元素和删除元素。
为避免装箱拆箱，这里使用泛型，代替object。使用object的例子可以参照本站这篇文章：http://www.tuohang.net/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#程序设计有所帮助。
