顺序表

程序

什么是顺序表？

线性表是逻辑关系为1对1的数据结构。数据结构分为顺序存储结构和链式存储结构。
顺序表就是顺序存储结构的线性表。
顺序表又分为静态顺序表和动态顺序表：

  • 静态顺序表：列表最大长度固定，不会在运行时改变。
  • 动态顺序表：运行时可以根据数据的多少，动态改变列表的最大长度。

静态顺序表的实现

通过数组实现。具体数据结构为:
数组和表的长度

1
2
3
4
5
public StaticSeqList
{
    private int[] list;
    private int count;
}

可以定义一些方便使用的属性和方法

1
2
3
4
5
6
7
8
9
public int Count { get { return count; } }
public bool IsEmpty { get { return count <= 0; } }
public bool IsFull { get { return count >= list.Length; } }

//索引号是否超出范围
private bool IsOutOfRange(int index)
{
    return (index < 0 || index >= count);
}

初始化

初始化就是给数组分配一个固定长度的空间。

1
2
3
4
5
public StaticSeqList(int capacity)
{
    count = 0;
    list = new int[capacity];
}

实现的操作

顺序表的操作主要就是增、删、改、查。

添加

添加分为：

  • 添加到末尾
  • 插入到某个位置
添加到末尾
1
2
3
4
5
6
7
8
public void Add(int elem)
{
    if (IsFull)
    {
        throw new OutOfMemoryException();
    }
    list[count++] = elem;
}
插入到某个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void Insert(int index, int elem)
{
    if (index < 0 || index > count)
    {
        //可在末尾插入
        throw new IndexOutOfRangeException();
    }
    if (IsFull)
    {
        throw new OutOfMemoryException();
    }
    for (int i = count - 1; i >= index; i--)
    {
        list[i + 1] = list[i];
    }
    list[index] = elem;
    count++;
}

移除

移除分为：

  • 根据索引号移除
  • 根据元素移除
根据索引号移除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int RemoveAt(int index)
{
    if (IsOutOfRange(index))
    {
        throw new IndexOutOfRangeException();
    }
    if (IsEmpty)
    {
        throw new Exception("List is empty.");
    }
    int elem = list[index];
    for (int i = index; i < count - 1; i++)
    {
        list[i] = list[i + 1];
    }
    count--;
    return elem;
}
根据元素移除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int Remove(int elem)
{
    if (IsEmpty)
    {
        throw new Exception("List is empty.");
    }

    int removeIndex = -1;
    for (int i = 0; i < count; i++)
    {
        if (list[i] == elem)
        {
            removeIndex = i;
            break;
        }
    }

    if (removeIndex != -1)
    { 
        RemoveAt(removeIndex);
    }

    return removeIndex;
}

赋值

1
2
3
4
5
6
7
8
private void Set(int index, int elem)
{
    if (IsOutOfRange(index))
    {
        throw new IndexOutOfRangeException();
    }
    list[index] = elem;
}

查找

查找分为：

  • 根据索引号查找元素
  • 根据元素查找索引号
根据索引号查找元素

使用this

1
2
3
4
5
6
7
8
private int Get(int index)
{
    if (IsOutOfRange(index))
    {
        throw new IndexOutOfRangeException();
    }
    return list[index];
}
根据元素查找索引号
1
2
3
4
5
6
7
8
9
10
11
public int IndexOf(int elem)
{
    for (int i = 0; i < count; i++)
    {
        if (list[i] == elem)
        {
            return i;
        }
    }
    return -1;
}
使用索引器

给元素赋值和根据索引号查找元素可以使用索引器。

1
2
3
4
5
6
7
8
9
10
11
public int this[int index]
{
    get
    {
        return Get(index);
    }
    set
    {
        Set(index, value);
    }
}

动态顺序表的实现

动态顺序表和静态顺序表的基本一致，差别是动态顺序表的增操作做了扩展数组的操作，删操作做了缩减数组的操作，并且初始化有一些细微的变化。

初始化

为了方便扩展和缩减数组，初始化时，可以指定一个扩展和缩减的长度，叫做segment。

1
2
3
4
5
6
public DynamicSeqList(int segment = 4)
{
    segmentLength = segment;
    count = 0;
    list = new int[segmentLength];
}

动态扩展

当表的长度已经达到数组最大长度时，此事再添加元素，自动将数组增加segment长度。
C#中更改数组大小的方式是将数组重新分配一个空间，并将原数组的数据赋给新的数组。

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
private void ExpandList()
{
    int newLength = list.Length + segmentLength;
    int[] tmp = list;
    list = new int[newLength];
    for (int i = 0; i < tmp.Length; i++)
    {
        list[i] = tmp[i];
    }
}

public void Add(int elem)
{
    if (IsFull)
    {
        ExpandList();
    }
    list[count++] = elem;
}

public void Insert(int index, int elem)
{
    if (index < 0 || index > count)
    {
        //可在末尾插入
        throw new IndexOutOfRangeException();
    }
    if (IsFull)
    {
        ExpandList();
    }
    for (int i = count - 1; i >= index; i--)
    {
        list[i + 1] = list[i];
    }
    list[index] = elem;
    count++;
}

动态缩减

当表的长度很小时，空闲的空间不小于1个segment长度时，空间就比较浪费了，此时就需要缩减数组空间。
但是如果当空闲长度刚好不小于1个segment时就缩减数组空间，之后再增加空间，就会重新分配空间。在这个临界值附近频繁发生增删数据的话，就会频繁申请内存，效率低下。所以，我们会在刚好达到这个临界值时再移除一次才会缩减数组空间，来减少上述情况的发生。

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
private void CutDownList()
{
    int newLength = list.Length - segmentLength;
    int[] tmp = list;
    list = new int[newLength];
    for (int i = 0; i < count; i++)
    {
        list[i] = tmp[i];
    }
}

public int RemoveAt(int index)
{
    if (IsOutOfRange(index))
    {
        throw new IndexOutOfRangeException();
    }
    if (IsEmpty)
    {
        throw new Exception("List is empty.");
    }

    int elem = list[index];
    for (int i = index; i < count - 1; i++)
    {
        list[i] = list[i + 1];
    }
    count--;

    if (count < list.Length - segmentLength)
    {
        //为什么不是count <= list.Length - segmentLength?
        //让元素数量比list.Length - segmentLength再小一位，当下次增加元素时，不会立即扩展而申请内存
        //可以防止在此临界值的时候频繁申请内存
        CutDownList();
    }
    return elem;
}