最近在公司On Bench比较蛋疼,正好手头有本《C#数据结构》,拿来复习一下数据结构。以前大学里都是用C语言写的,C#从来没试过,毕竟C#本身就带有很多数据结构的Class可以直接拿来用。出于实验性目的,我还是看着书用C#写了几个demo。书上有些错误我也一并修正了。接下来发的代码都是经过测试可以正常运行的~

DAY1.顺序表

最近博客系统有点BUG,代码中如果有三条杠注释就会排版混乱,所以抱歉这次不能带注释了。

IListDs接口:

public interface IListDs
{
    void Clear();
    void Append(T item);
    void Insert(T item, int i);
    T Delete(int i);
    T GetElement(int i);
    int Locate(T value);
}

SqList顺序表类:

public class SqList : IListDs
{
    private int _MaxSize;
    private T[] _Data;
    private int _Last;

    public int MaxSize { get; set; }

    public T[] Data { get; set; }

    public int Last { get; set; }

    public T this[int index]
    {
        get
        {
            return _Data[index];
        }
        set
        {
            _Data[index] = value;
        }
    }

    public int Length
    {
        get { return this._Last + 1; }
    }

    public bool IsEmpty
    {
        get
        {
            if (this._Last == -1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public bool IsFull
    {
        get
        {
            if (this._Last == this._MaxSize - 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public SqList(int size)
    {
        this._Data = new T[size];
        this._MaxSize = size;
        this._Last = -1;
    }

    public void Clear()
    {
        this._Last = -1;
    }

    public void Append(T item)
    {
        if (IsFull)
        {
            // need error message?
            return;
        }
        this._Data[++this._Last] = item;
    }

    public void Insert(T item, int index)
    {
        if (IsFull)
        {
            // need error message?
            return;
        }
        if (index < 1 || index > this._Last + 2)
        {
            // position error
            return;
        }
        if (index == this._Last + 2)
        {
            this._Data[this._Last + 1] = item;
        }
        else
        {
            // 将插入位置后面的元素逐个向后移1位
            for (int j = index; j <= this._Last + 1; j++)
            {
                this._Data[j] = this._Data[j - 1];
            }
            this._Data[index - 1] = item;
        }
        ++this._Last;
    }

    public T Delete(int index)
    {
        T temp = default(T);
        if (IsEmpty)
        {
            // need error message?
            return temp;
        }
        if (index < 1 || index > this._Last + 1)
        {
            // position error
            return temp;
        }
        if (index == this._Last + 1)
        {
            temp = this._Data[this._Last--];
        }
        else
        {
            // 将删除位后的元素逐个往前移1位
            temp = this._Data[index - 1];
            for (int j = index; j <= this._Last; j++)
            {
                this._Data[j - 1] = this._Data[j];
            }
        }
        --this._Last;
        return temp;
    }

    public T GetElement(int index)
    {
        if (IsEmpty || index < 1 || index > this._Last + 1)
        {
            // empty or wrong position
            return default(T);
        }
        return this._Data[index - 1];
    }

    public int Locate(T value)
    {
        if (IsEmpty)
        {
            return -1;
        }

        int i = 0;
        for (i = 0; i < this._Last; i++)
        {
            if (value.Equals(this._Data[i]))
            {
                break;
            }
        }

        if (i > this._Last)
        {
            return -1;
        }

        // 返回逻辑序位(物理序位+1)
        return i + 1;
    }
}

测试代码:

private static void SqListTest()
{
    // 因为要插入元素,所以先得开辟够多的存储单元
    SqList sq = new SqList(10);
    sq.Append("Hello");
    sq.Append("World");
    sq.Append("ABC");
    Console.WriteLine("SeqList Created:\n---------------------------------");
    PrintSqList(sq);
    Console.WriteLine();

    Console.WriteLine("Insert \"123\" into index 3\n---------------------------------");
    // 在逻辑序位3处插入"123","!"后移。
    sq.Insert("123", 3);
    PrintSqList(sq);
    Console.WriteLine();

    Console.WriteLine("Delete Element on index 3\n---------------------------------");
    sq.Delete(3);
    PrintSqList(sq);
    Console.WriteLine();

    Console.WriteLine("Locate Element \"World\"\n---------------------------------");
    int index = sq.Locate("World");
    Console.WriteLine("Position: {0}", index);
    Console.WriteLine();

    Console.WriteLine("Get Element on index 1\n---------------------------------");
    Console.WriteLine("#1: {0}", sq.GetElement(1));
    Console.WriteLine();
    Console.ReadKey();
}

private static void PrintSqList(SqList sq)
{
    for (int i = 0; i < sq.Length; i++)
    {
        Console.Write("[{0}]", sq[i]);
        System.Threading.Thread.Sleep(300);
    }
    Console.WriteLine();
}

有图有真相: