C#数据结构【数组】

前言

【此文章所有代码可在文章末尾下载查看源码】

数据结构是计算机存储，组织数据的方式,同样也是相互之间存在一种或者多种特定关系的数据元素的集合

算法是一系列规定的计算步骤，为了实现特定的计算目的

基本数据结构一般有4类:
(1)集合 (2)线性结构 (3)树形结构 (4)图形结构

集合：数据结构中的集合与数学中的集合类似，在集合中的数据只是存在同一集合中，但其数据之间没有关系。

线性结构：数据元素之间是一对一的关系

主要包括：线性表，栈，队列（三者的数据元素以及数据间的逻辑关系完全相同，差别就在于线性表的操作不受限制，而栈和队列的操作受到限制，栈的操作只能在表的一端进行，队列的插入操作在表的一端进行而其它操作在表的另一端进行，所以，把栈和队列称为操作受限的线性表）

树形结构：数据元素之间的层次关系是一对多

图形结构：数据元素之间呈多对多的关系

数组

静态数组：

int[],float[],string[]等

特点：数组一旦创建，其容量的大小是无法进行改变的

动态数组：

ArrayList List

特点：可以根据元素的多少动态的调整数组容量的大小

泛型数组（List）：

优势：对于存储值类型数据，性能更优；使代买更清晰和保证类型安全

动态数组代码实现

这里主要考虑的便是数组中所要实现的功能（插入数据，获取数据，删除数据，修改数据，数组的扩容）

(1).定义一个数组来存储数据T[] data,通过num来统计数组的数组的大小

1 2	private T[] data;//数组数据 private int num;//数组的大小

(2).所需要的参数定义完毕后便是对构造方法，这里主要考虑的便是数组需要在创建之初要设置好数组的大小

/// <summary>
/// 有参构造
/// </summary>
/// <param name="capacity">容量</param>
public ArrayOne(int capacity) {
           data = new T[capacity];
           num = 0;
}
/// <summary>
/// 无参构造==》建议动态数组定义长度
/// </summary>
public ArrayOne(): this(10) { }

(3).考虑使用过程中所需要的功能【添加数据，修改数据，删除数据，获取数据，扩容数组】

插入/添加数据

①.首先需要判定index是否在数组范围内

1	if(index < 0 \|\| index >num )throw new ArgumentException("index不合法，请检查");

②.由于我们使用的是动态数组，当数组的长度和num相同时，则需要对数组进行扩容【相关代码请看ResetCapacity()方法】

1 2	//当数组容量不足时则需要进行数组的扩容 if (num == data.Length) ResetCapacity(2*data.Length);

③下面我们要考虑的便是添加数据，这里主要考虑的便是插入的目标索引和数据信息，需要将目标位置索引数据往后挪动，然后将目标索引的数据写入即可

public void Add(int index,T e) {
       if(index < 0 || index >num )throw new ArgumentException("index不合法，请检查");
       //当数组容量不足时则需要进行数组的扩容
       if (num == data.Length) 
           ResetCapacity(2*data.Length);
       for (int i = num - 1; i >= index; i--) 
           data[i+1]=data[i];
       data[index] = e;
       //数组个数加1
       num++;
 }

④这里为了方便添加了向数据末尾和数据头部添加数据的方法，只需将num和数据添加写入即可

/// <summary>
/// 添加到数组末尾
/// </summary>
/// <param name="e"></param>
public void AddLast(T value){
    Add(num,value);
}
/// <summary>
/// 添加到数组开始
/// </summary>
/// <param name="e"></param>
public void AddFist(T value) {
    Add(0,value);
}

获取数据

这里考虑的比较少一些，只需判断所要获取的索引是否越界，然后返回相应索引的数据

/// <summary>
/// 获取数组元素
/// </summary>
/// <param name="index">数组索引</param>
public T Get(int index) {
    if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
    return data[index];
}
/// <summary>
/// 获取数组的头元素
/// </summary>
public T GetFirst() { return Get(0); }
/// <summary>
/// 获取数组的末尾元素
/// </summary>
public T GetLast() { return Get(num-1); }

修改数据

这里考虑的比较少一些，只需判断所要获取的索引是否越界，将相应索引的数据重新赋值即可

/// <summary>
/// 修改数组的元素数据信息
/// </summary>
public void SetValue(int index,T newValue)
{
    if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
    data[index] = newValue;
}

删除数据

/// <summary>
/// 删除相关头部索引的数据
/// </summary>
public T RemoveFirst() { return RemoveAt(0); }
/// <summary>
/// 删除相关末尾索引的数据
/// </summary>
public T RemoveLast() { return RemoveAt(num-1); }
/// <summary>
/// 删除指定数据==>如果存在将删除，没有不删除
/// </summary>
/// <param name="value"></param>
public string Remove(int value){
    int index=IndexOf(value);
    if (index != -1) {
        RemoveAt(index);
        return "删除成功";
    }
    else
        return "所要删除的数据不存在，故删除失败";
}  
/// <summary>
/// 删除相关索引的数据
/// </summary>
/// <param name="index"></param>
public T RemoveAt(int index) {
    if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
    T delValue=data[index];
    for (int i = index+1; i <=num-1; i++)
        data[i-1] = data[i];
    num--;
    data[num] = default(T);
    //缩容
    if (num == data.Length / 4)
        ResetCapacity(data.Length / 2);
    return delValue;
}

判断数据是否存在

/// <summary>
/// 判断数据是否存在
/// </summary>
/// <param name="value">所要判断的数组数据</param>
public bool Contains(T value)
{
    for (int i = 0; i < num; i++) {
        if (data[i].Equals(value)) return true;
    }
    return false;
}

下面是完整代码

    private T[] data;//数组数据
    private int num;//数组的大小
    /// <summary>
    /// 有参构造
    /// </summary>
    /// <param name="capacity">容量</param>
    public ArrayOne(int capacity) {
        data = new T[capacity];
        num = 0;
    }
    /// <summary>
    /// 无参构造==》建议动态数组定义长度
    /// </summary>
    public ArrayOne(): this(10) { }
    /// <summary>
    /// 返回数组的长度
    /// </summary>
    public int Capacity {
        get { return data.Length; }
    }
    /// <summary>
    /// 返回数组的元素个数
    /// </summary>
    public int Count{
        get { return num; }
    }
    /// <summary>
    /// 判断动态数组是否为空==>只需知道数组的个数是否为0即可
    /// </summary>
    public bool IsEmpty{
        get { return num == 0; }
    }
    
    /// <summary>
    /// 获取数组元素
    /// </summary>
    /// <param name="index">数组索引</param>
    public T Get(int index) {
        if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
        return data[index];
    }
    /// <summary>
    /// 获取数组的头元素
    /// </summary>
    public T GetFirst() { return Get(0); }
    /// <summary>
    /// 获取数组的末尾元素
    /// </summary>
    public T GetLast() { return Get(num-1); }
    /// <summary>
    /// 修改数组的元素数据信息
    /// </summary>
    public void SetValue(int index,T newValue)
    {
        if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
        data[index] = newValue;
    }
    public override string ToString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.Append(string.Format("ArrayOne:  count={0} capacity={1}\n",num,data.Length));
        stringBuilder.Append("[");
        for (int i = 0; i < num; i++) {
            stringBuilder.Append(data[i]);
            if (i != num - 1)
                stringBuilder.Append(", ");
        }
        stringBuilder.Append("]");
        return stringBuilder.ToString();
    }
    /// <summary>
    /// 判断数据是否存在
    /// </summary>
    /// <param name="value">所要判断的数组数据</param>
    public bool Contains(T value)
    {
        for (int i = 0; i < num; i++) {
            if (data[i].Equals(value)) return true;
        }
        return false;
    }
    /// <summary>
    /// 返回数据的相关索引
    /// </summary>
    /// <param name="value"></param>
    public int IndexOf(int value) {
        for (int i = 0; i < num; i++) {
            if (data[i].Equals(value)) return i;
        }
        return -1;
    }
    /// <summary>
    /// 删除相关索引的数据
    /// </summary>
    /// <param name="index"></param>
    public T RemoveAt(int index) {
        if (index < 0 || index >= num) throw new ArgumentException("数组索引越界");
        T delValue=data[index];
        for (int i = index+1; i <=num-1; i++)
            data[i-1] = data[i];
        num--;
        data[num] = default(T);
        //缩容
        if (num == data.Length / 4)
            ResetCapacity(data.Length / 2);
        return delValue;
    }
    /// <summary>
    /// 删除相关头部索引的数据
    /// </summary>
    public T RemoveFirst() { return RemoveAt(0); }
    /// <summary>
    /// 删除相关末尾索引的数据
    /// </summary>
    public T RemoveLast() { return RemoveAt(num-1); }
    /// <summary>
    /// 删除指定数据==>如果存在将删除，没有不删除
    /// </summary>
    /// <param name="value"></param>
    public string Remove(int value){
        int index=IndexOf(value);
        if (index != -1) {
            RemoveAt(index);
            return "删除成功";
        }
        else
            return "所要删除的数据不存在，故删除失败";
    }
    private void ResetCapacity(int newCapacity)
    {
        T[] newData=new T[newCapacity];
        for (int i = 0; i < num; i++)
            newData[i]=data[i];
        data=newData;
    }
}

具体测试代码详见

ArrayOne<int> arrayOne = new ArrayOne<int>(20);
for (int i = 0; i < 10; i++) {
    arrayOne.AddLast(i);
}
Console.WriteLine("数组信息:{0}", arrayOne);
arrayOne.AddLast(1234);
Console.WriteLine("**********末尾添加完数据后的数组信息:**********\n{0}", arrayOne);
arrayOne.AddFist(88);
Console.WriteLine("**********头部添加完数据后的数组信息:**********\ns{0}", arrayOne);
Console.WriteLine("获取数组头部元素:{0}", arrayOne.GetFirst());
Console.WriteLine("获取数组尾部元素:{0}", arrayOne.GetLast());
Console.WriteLine("获取数组第6个元素:{0}", arrayOne.Get(6));
arrayOne.SetValue(2, 755);
Console.WriteLine("**********修改第2个数组元素后:**********\n{0}", arrayOne);
bool isHave= arrayOne.Contains(78);
Console.WriteLine("arrayOne中{0}存在78",isHave?"":"不");
Console.WriteLine("返回数据3的相关索引:{0}", arrayOne.IndexOf(3));
arrayOne.RemoveAt(3);
Console.WriteLine("**********删除索引为3的数据后:**********\n{0}", arrayOne);
arrayOne.RemoveFirst();
Console.WriteLine("**********删除头索引的数据后:**********\n{0}", arrayOne);
arrayOne.RemoveLast();
Console.WriteLine("**********删除末尾索引的数据后:**********\n{0}", arrayOne);
string s=arrayOne.Remove(7777);
Console.WriteLine(s);
Console.WriteLine("**********尝试删除7777的数据后数组:**********\n{0}", arrayOne);
Console.ReadLine();

控制台输出效果

数组信息:ArrayOne:  count=10 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
**********末尾添加完数据后的数组信息:**********
ArrayOne:  count=11 capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1234]
**********头部添加完数据后的数组信息:**********
sArrayOne:  count=12 capacity=20
[88, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1234]
获取数组头部元素:88
获取数组尾部元素:1234
获取数组第6个元素:5
**********修改第2个数组元素后:**********
ArrayOne:  count=12 capacity=20
[88, 0, 755, 2, 3, 4, 5, 6, 7, 8, 9, 1234]
arrayOne中不存在78
返回数据3的相关索引:4
**********删除索引为3的数据后:**********
ArrayOne:  count=11 capacity=20
[88, 0, 755, 3, 4, 5, 6, 7, 8, 9, 1234]
**********删除头索引的数据后:**********
ArrayOne:  count=10 capacity=20
[0, 755, 3, 4, 5, 6, 7, 8, 9, 1234]
**********删除末尾索引的数据后:**********
ArrayOne:  count=9 capacity=20
[0, 755, 3, 4, 5, 6, 7, 8, 9]
所要删除的数据不存在，故删除失败
**********尝试删除7777的数据后数组:**********
ArrayOne:  count=9 capacity=20
[0, 755, 3, 4, 5, 6, 7, 8, 9]