資料結構（二）——線性表

一：線性表的概述

線性表是最簡單最基本的一種資料結構，線性表中的資料元素都存在一對一的關系，屬于線性結構，是有順序有先後關系的，除了第一個元素外，其他資料元素前隻有一個資料元素（前驅），除了最後一個元素外，其他資料元素後隻有一個資料元素（後驅）

二：線性表的順序存儲結構

用一段位址連續的存儲單元依次存儲線性表中的資料元素

線性表的順序存儲結構在讀、存資料時，時間複雜度都是O(1)，我們把讀、存資料時時間複雜度為O(1)的存儲結構稱為随機存儲結構

在插入、删除資料時，時間複雜度是O(n)，數組就是線性表的順序存儲結構的展現，這也是為什麼數組比較适合元素個數不太變化，更多的是存取資料的應用

三：線性表的鍊式存儲結構

引言：對于線性表的順序存儲結構，當元素個數不太變化時很适用，但是當我們插入、删除資料時，有可能會移動大量的資料，進而耗費時間，根本原因在于順序存儲結構中資料與資料之間的存儲位置是連續的，當我們插入、删除資料時，也要讓線性表中的資料仍然保持記憶體的連續，既然這樣，我們可以不考慮記憶體的連續，隻是讓每個元素知道它下一個元素的位址就可以，這就是線性表的鍊式存儲結構(連結清單)

為了表示ai與ai+1之間的關系，對于ai來說，除了存儲本身的資訊外，還需要存儲一個指向它直接後繼的資訊(直接後繼的位址)，我們把存儲本身資料資訊的域稱為資料域，把存儲直接後繼位置的域稱為指針域，資料域與指針域組成了ai的存儲映像，稱為結點，n個結點組成為一個連結清單，也就是線性表的鍊式存儲結構(連結清單)。又因為此連結清單中的每個結點隻包含一個指針域(隻能指向直接後驅)，是以稱為單連結清單

我們把線性表的鍊式存儲結構中指向第一個結點的指針稱為頭指針，連結清單的存儲從頭指針開始進行，之後的每一個結點都是上一個的指針指向的位址，規定最後一個的結點的指針域為NULL，有時候為了友善操作，會在第一個結點前附設一個結點，稱為頭結點，頭結點的資料域可以不存儲任何資訊(也可以存儲線性表的公共資料)，頭結點的指針域（也就是頭指針）指向第一個結點的位址，就算線性單連結清單為空，頭指針也不能為空，但是頭結點是附設的可以沒有

線性表的鍊式存儲結構對于插入、删除資料越頻繁的操作優勢越是明顯

四：線性表的順序存儲與鍊式存儲的比較

五：其他連結清單

——靜态連結清單

引言：對于C、C++來說，它具有指針，可以友善地操作記憶體中的位址和資料，而對于C#、Java等面向對象的語言，雖然沒有指針但是可以利用引用間接地實作指針的作用，但是對于早期的一些程式設計語言，例如Basic、Fortran等，由于沒有指針也不是面向對象語言，是以前人就想出了用數組代替指針，我們把這種描述方式稱為遊标實作法，把這種用數組描述的連結清單稱為靜态連結清單

首先讓數組中的每個元素都是由兩個資料域組成，data和cur，data存儲資料元素，cur存儲下一個元素在數組中的下标(與單連結清單中的next指針作用相同)，把未被使用的數組元素稱為備用連結清單，另外對數組中的第一個和最後一個元素進行特殊處理，都不存儲資料，第一個元素的cur存儲第一個備用連結清單的下标，最後一個元素的cur存儲第一個有數值的元素的下标(與頭結點作用相同)，當某一個元素的cur為0時，則此元素是靜态連結清單中最後一個有數值的元素

——循環連結清單

引言：對于單連結清單，我們無法從中間某個結點開始周遊到整個連結清單的結點，是以引出了循環連結清單

将單連結清單中的最後一個結點由空指針改為指向頭結點的指針，使整個單連結清單形成了一個環，這樣頭尾相連的單連結清單稱為循環連結清單

循環連結清單與單連結清單最主要的差别就在于循環的判斷條件上，單連結清單是判斷結點的指針指向是否為空，而循環連結清單是判斷結點的指針指向是否為頭結點

——雙向連結清單

六：實作線性表的順序存儲結構（順序表）

using System;

//順序表類
public class LinearList<T>
{
    //存儲順序表中元素的數組
    private T[] array;

    //順序表中元素的個數
    private int count;
    public int Count
    {
        get
        {
            return count;
        }
    }

    //構造器初始化
    public LinearList()
    {
        array = new T[0];
    }
    public LinearList(int size)
    {
        array = new T[size];
    }

    //判斷順序表是否已滿
    private bool IsFull()
    {
        return count >= array.Length;
    }

    //判斷索引是否正确
    private bool IndexIsVaild(int index)
    {
        return index >= 0 && index <= array.Length - 1;
    }

    //得到順序表長度
    public int GetLength()
    {
        return count;
    }

    //清空順序表
    public void Clear()
    {
        for (int i = 0; i < count; i++)
        {
            array[i] = default(T);
        }
        count = 0;
    }

    //添加元素
    public void AddItem(T item)
    {
        if (!IsFull())
        {
            array[count] = item;
            count++;
        }
        else
        {
            throw new Exception("表已滿");
        }
    }

    //得到元素（不通過索引器）
    public T GetItem(int index)
    {
        if (IndexIsVaild(index))
        {
            return array[index];
        }
        else
        {
            throw new Exception("索引超出範圍");
        }
    }
    //得到元素（通過索引器）
    public T this[int index]
    {
        get
        {
            if (IndexIsVaild(index))
            {
                return array[index];
            }
            else
            {
                throw new Exception("索引超出範圍");
            }
        }
        set
        {
            if (!IsFull())
            {
                array[index] = value;
            }
            else
            {
                throw new Exception("順序表目前已滿");
            }
        }
    }

    //判斷順序表是否為空
    public bool IsEmpty()
    {
        return count == 0;
    }

    //插入元素
    public void Insert(int index, T item)
    {
        if (!IsFull() == false)
        {
            if (IndexIsVaild(index))
            {
                for (int i = count - 1; i >= index; i--)
                {
                    array[i + 1] = array[i];
                }
                array[index] = item;
                count++;
            }
            else
            {
                throw new Exception("索引超出範圍");
            }
        }
        else
        {
            throw new Exception("順序表目前已滿");
        }
    }

    //移除元素（通過指定位置）
    public void RemoveAt(int index)
    {
        if (IndexIsVaild(index))
        {
            for (int i = index + 1; i < count; i++)
            {
                array[index - 1] = array[index];
            }
            count--;
        }
        else
        {
            throw new Exception("索引超出範圍");
        }
    }
    //移除元素（通過指定元素）
    public void Remove(T item)
    {
        int index = 0;
        for (int i = 0; i < count; i++)
        {
            if (array[i].Equals(item))
            {
                index = i;
            }
        }
        RemoveAt(index);
    }

    //擷取元素位置
    public int IndexOf(T item)
    {
        for (int i = 0; i < count; i++)
        {
            if (array[i].Equals(item))
            {
                return i;
            }
        }
        return -1;
    }
}

class Program
{
    //*****進行測試*****
    static void Main(string[] args)
    {
        LinearList<int> myList = new LinearList<int>(5);
        myList.AddItem(1);
        myList[1] = 2;
        myList.Insert(1, 3);
        myList.Remove(1);
        myList.RemoveAt(1);
    }
}           

七：實作線性表的鍊式存儲結構（單連結清單）

using System;

//結點類
public class Node<T>
{
    //存儲資料（資料域）
    public T Data { get; set; }

    //存儲下一個結點的位址（指針域）——引用
    public Node<T> Next { get; set; }

    //構造器初始化
    public Node()
    {
        this.Data = default(T);
        Next = null;
    }
    public Node(T value)
    {
        this.Data = value;
        Next = null;
    }
    public Node(T value, Node<T> next)
    {
        this.Data = value;
        this.Next = next;
    }
    public Node(Node<T> next)
    {
        this.Next = next;
    }
}

//連結清單類
public class LinearList<T>
{
    //頭結點
    private Node<T> head;

    //連結清單長度
    private int length;
    public int Length
    {
        get
        {
            return length;
        }
    }

    //構造器初始化
    public LinearList()
    {
        head = null;
    }

    //得到連結清單長度
    public int GetLength()
    {
        return length;
    }

    //判斷索引是否正确
    private bool IndexIsVaild(int index)
    {
        return index >= 0 && index <= length - 1;
    }

    //添加元素
    public void AddItem(T item)
    {
        Node<T> newNode = new Node<T>(item);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            Node<T> temp = head;
            while (true)
            {
                if (temp.Next != null)
                {
                    temp = temp.Next;
                }
                else
                {
                    break;
                }
            }
            temp.Next = newNode;
        }
        length++;
    }

    //插入元素
    public void Insert(int index, T item)
    {
        Node<T> newNode = new Node<T>(item);
        if (index == 0)
        {
            newNode.Next = head;
            head = newNode;
            length++;
        }
        else
        {
            if (IndexIsVaild(index))
            {
                Node<T> temp = head;
                for (int i = 1; i <= index - 1; i++)
                {
                    temp = temp.Next;
                }
                Node<T> preNode = temp;
                Node<T> nextNode = temp.Next;
                preNode.Next = newNode;
                newNode.Next = nextNode;
                length++;
            }
            else
            {
                throw new Exception("索引超出範圍");
            }
        }
    }

    //删除元素
    public void Remove(int index)
    {
        if (IndexIsVaild(index))
        {
            if (index == 0)
            {
                head = head.Next;
            }
            else
            {
                Node<T> temp = head;
                for (int i = 1; i <= index - 1; i++)
                {
                    temp = temp.Next;
                }
                Node<T> preNode = temp;
                Node<T> nextNode = temp.Next.Next;
                preNode.Next = nextNode;
            }
            length--;
        }
        else
        {
            throw new Exception("索引超出範圍");
        }
    }

    //清空連結清單
    public void CLear()
    {
        head = null;
    }

    //擷取元素（通過索引器）
    public T this[int index]
    {
        get
        {
            if (IndexIsVaild(index))
            {
                Node<T> temp = head;
                for (int i = 1; i <= index; i++)
                {
                    temp = temp.Next;
                }
                return temp.Data;
            }
            else
            {
                throw new Exception("索引超出範圍");
            }
        }
        set
        {
            if (IndexIsVaild(index))
            {
                Node<T> newNode = new Node<T>(value);
                Node<T> temp = head;
                for (int i = 1; i <= index - 1; i++)
                {
                    temp = temp.Next;
                }
                Node<T> preNode = temp;
                Node<T> nextNode = temp.Next.Next;
                preNode.Next = newNode;
                newNode.Next = nextNode;
            }
            else
            {
                throw new Exception("索引超出範圍");
            }
        }
    }
    //擷取元素（不通過索引器）
    public T GetItem(int index)
    {
        if (IndexIsVaild(index))
        {
            Node<T> temp = head;
            for (int i = 1; i < index; i++)
            {
                temp = temp.Next;
            }
            return temp.Data;
        }
        else
        {
            throw new Exception("索引超出範圍");
        }
    }

    //擷取元素位置
    public int IndexOf(T item)
    {
        int index = 0;
        Node<T> temp = head;
        while (true)
        {
            if (temp.Data.Equals(item))
            {
                return index;
            }
            else
            {
                if (temp.Next != null)
                {
                    temp = temp.Next;
                    index++;
                }
                else
                {
                    break;
                }
            }
        }
        return -1;
    }

    //判斷連結清單是否為空
    public bool IsEmpty()
    {
        return length == 0 || head == null;
    }
}

class Program
{
    //*****進行測試*****
    public static void Main(string[] args)
    {
        LinearList<int> myList = new LinearList<int>();
        myList.AddItem(1);
        myList.AddItem(2);
        myList[1] = 3;
        myList.Insert(1, 4);
        myList.Remove(2);
    }
}