首页 > 代码库 > 数据结构C#版笔记--顺序表(SeqList)

数据结构C#版笔记--顺序表(SeqList)

2024-07-06 08:29:56   224人阅读

线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构，其特征用图形表示如下：


即：每个元素前面有且只有一个元素(称为“前驱”)，同样后面有且只有一个元素(称为"后继")--注：起始元素的前驱认为是空，末尾元素的后继认为也是空，这样在概念上就不冲突了。


线性表(List)是线性结构的一种典型实现，它又可以分为：顺序表(SeqList)和链表(LinkList)二大类.


顺序表（SeqList）的基本特征为：元素在内部存储时是一个接一个在存储单元中按顺序存储的，所以只要知道"起始元素的存储地址"--称为顺序表的基地址(Base Address)以及顺序表中任何元素的位置(即它是第几个元素)，就能直接定位到该元素的地址，从而直接访问到该元素的值。也就是说存储/读取每个元素 所用的时间是相同的，即所谓的“随机存取”

 

C#语言中数组(Array)在内存中占用的就是一组连续的存储区域，所以用数组来实现顺序表再适用不过。

 

先来定义线性表的通用接口IListDS.cs(注：DS为DataStructure的缩写)

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
namespace 线性表
{
    public interface IListDS<T>
    {
        //取得线性表的实际元素个数
        int Count();
 
        //清空线性表
        void Clear();
 
        //判断线性表是否为空
        bool IsEmpty();
 
        //（在末端）追加元素
        void Append(T item);
 
        //在位置i“前面”插入元素item
        void InsertBefore(T item, int i);
 
        //在位置i“后面”插入元素item
        void InsertAfter(T item, int i);
 
        //删除索引i处的元素
        T RemoveAt(int i);
 
        //获得索引位置i处的元素
        T GetItemAt(int i);
 
        //返回元素value的索引
        int IndexOf(T value);
 
        //反转线性表的所有元素
        void Reverse();
    }
}

顺序表(SeqList)的实现：

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
using System;
using System.Text;
 
namespace 线性表
{
    /// <summary>
    /// 顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SeqList<T> : IListDS<T>
    {
        private int maxsize;
        private T[] data;
        private int last;
 
        //类索引器
        public T this[int index]
        {
            get
            {
                return this.GetItemAt(index);
            }
            set
            {
                if (index < 0 || index > last + 1)
                {
                    Console.WriteLine("Position is error");
                    return;
                }
                data[index] = value;
            }
        }
 
        //最后一个元素的下标
        public int Last
        {
            get { return last; }
        }
 
        //最大容量
        public int Maxsize
        {
            get { return this.maxsize; }
            set { this.maxsize = value; }
        }
 
        //构造函数
        public SeqList(int size)
        {
            data = http://www.mamicode.com/new T[size];
            maxsize = size;
            last = -1;
        }
 
        //返回链表的实际长度
        public int Count()
        {
            return last + 1;
        }
 
        //清空
        public void Clear()
        {
            last = -1;
        }
 
        //是否空
        public bool IsEmpty()
        {
            return last == -1;
        }
 
        //是否满
        public bool IsFull()
        {
            return last == maxsize - 1;
        }
 
        //(在最后位置)追加元素
        public void Append(T item)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            data[++last] = item;
        }
 
        /// <summary>
        ///前插
        /// </summary>
        /// <param name="item">要插入的元素</param>
        /// <param name="i">要插入的位置索引</param>
        public void InsertBefore(T item, int i)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
 
            if (i < 0 || i > last + 1)
            {
                Console.WriteLine("Position is error");
                return;
            }
 
            if (i == last + 1)
            {
                data[last + 1] = item;
            }
            else
            {
                //位置i及i以后的元素，全部后移
                for (int j = last; j >= i; j--)
                {
                    data[j + 1] = data[j];
                }
                data[i] = item;
            }
            ++last;
        }
 
        /// <summary>
        /// 后插
        /// </summary>
        /// <param name="item"></param>
        /// <param name="i"></param>
        public void InsertAfter(T item, int i)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
 
            if (i < 0 || i > last)
            {
                Console.WriteLine("Position is error");
                return;
            }
 
            if (i == last)
            {
                data[last + 1] = item;
            }
            else
            {
                //位置i以后的元素(不含位置i)，全部后移
                for (int j = last; j > i; j--)
                {
                    data[j + 1] = data[j];
                }
                data[i+1] = item;
            }
            ++last;
        }
 
        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="i">要删除的元素索引</param>
        /// <returns></returns>
        public T RemoveAt(int i)
        {
            T tmp = default(T);
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return tmp;
            }
 
            if (i < 0 || i > last)
            {
                Console.WriteLine("Position is error!");
                return tmp;
            }
 
            if (i == last)
            {
                tmp = data[last];
            }
            else
            {
                tmp = data[i];
                //位置i以及i以后的元素前移
                for (int j = i; j <= last; j++)
                {
                    data[j] = data[j + 1];
                }
            }
            --last;
            return tmp;
        }
 
        /// <summary>
        /// 获取第几个位置的元素
        /// </summary>
        /// <param name="i">第几个位置</param>
        /// <returns></returns>
        public T GetItemAt(int i)
        {
            if (IsEmpty() || (i < 0) || (i > last))
            {
                Console.WriteLine("List is empty or Position is error!");
                return default(T);
            }
            return data[i];
        }
 
        /// <summary>
        /// 定位元素的下标索引
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public int IndexOf(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            int i = 0;
            for (i = 0; i <= last; i++)
            {
                if (value.Equals(data[i]))
                {
                    break;
                }
            }
            if (i > last)
            {
                return -1;
            }
            return i;
        }
 
        /// <summary>
        /// 元素反转
        /// </summary>
        public void Reverse()
        {
            T tmp = default(T);
            for (int i = 0; i <= last / 2; i++)
            {
                tmp = data[i];
                data[i] = data[last-i];
                data[last-i] = tmp;
            }
        }
 
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= last; i++)
            {
                sb.Append(data[i].ToString() + "，");
            }
            return sb.ToString().TrimEnd(‘，‘);
        }
    }
}

测试代码片段：

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
Console.WriteLine("顺序表测试开始...");
SeqList<string> seq = new SeqList<string>(10);
 
seq.Append("x");
seq.InsertBefore("w", 0);
seq.InsertBefore("v", 0);
seq.Append("y");
seq.InsertBefore("z", seq.Count());
Console.WriteLine(seq.Count());//5
Console.WriteLine(seq.ToString());//v,w,x,y,z
Console.WriteLine(seq[1]);//w
Console.WriteLine(seq[0]);//v
Console.WriteLine(seq[4]);//z
Console.WriteLine(seq.IndexOf("z"));//4
Console.WriteLine(seq.RemoveAt(2));//x
Console.WriteLine(seq.ToString());//v,w,y,z
seq.InsertBefore("x", 2);          
Console.WriteLine(seq.ToString());//v,w,x,y,z
Console.WriteLine(seq.GetItemAt(2));//x
seq.Reverse();
Console.WriteLine(seq.ToString());//z,y,x,w,v
 
seq.InsertAfter("z_1", 0);
seq.InsertAfter("y_1", 2);
seq.InsertAfter("v_1", seq.Count()-1);
Console.WriteLine(seq.ToString());//z，z_1，y，y_1，x，w，v，v_1

顺序表的优点：读取元素时可直接定位，所以在某些操作(比如将顺序表元素反转合围)中，不需要完全遍历，循环次数(即时间复杂度)相对完全遍历而言能减少一半。

顺序表的优点：插入/删除元素，因为要保持其顺序性，所以后续元素需要移动，增加了时间开销。

 

最后指出：.Net命名空间System.Collections.Generic中的List<T>就是一个内置的顺序表.


联系
我们