導(dǎo)言

GitHub項(xiàng)目地址：https://github.com/HarmoniaLeo/CSharp-DS

線性表家族除了我們上次分享的順序表外,另一位重要成員就是鏈表。鏈表是一串結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)維護(hù)著自己的數(shù)值，以及指向其他結(jié)點(diǎn)的指針。指針將結(jié)點(diǎn)像鎖鏈的一環(huán)一環(huán)一樣扣在一起，在從一個(gè)結(jié)點(diǎn)訪問(wèn)另一個(gè)結(jié)點(diǎn)時(shí)，就通過(guò)指針來(lái)“穿梭”。

鏈表根據(jù)擁有指針的不同，分為只有指向下一個(gè)結(jié)點(diǎn)指針的單向鏈表，和同時(shí)擁有指向下一個(gè)與上一個(gè)結(jié)點(diǎn)的指針的雙向鏈表。如果最后一個(gè)結(jié)點(diǎn)的指針指向了第一個(gè)結(jié)點(diǎn)，還可以實(shí)現(xiàn)環(huán)狀鏈表。

順序表的插入與刪除涉及到大量元素的位移，其運(yùn)算次數(shù)是和數(shù)據(jù)規(guī)模有關(guān)的。但是對(duì)于鏈表來(lái)說(shuō)，只需要改動(dòng)部分結(jié)點(diǎn)指針的指向，把新增的環(huán)“扣進(jìn)”或者“移出”原來(lái)的鏈條就行。然而鏈表也有自己的缺點(diǎn)，這些都將會(huì)在本文中一一討論。

C#的類對(duì)象全部采用引用變量，也就是說(shuō)所有值面上的“類實(shí)例”其實(shí)都只是指向類的引用而已，相當(dāng)于C++的指針。對(duì)于初學(xué)者以及沒(méi)有接觸過(guò)JAVA和Python的人來(lái)說(shuō)可能會(huì)有點(diǎn)摸不著頭腦，但個(gè)人認(rèn)為這也是C#作為純面向?qū)ο笳Z(yǔ)言在設(shè)計(jì)模式上做出的一個(gè)大膽而合理的簡(jiǎn)化——畢竟就算是在C++當(dāng)中，類按指針實(shí)例化、按引用傳遞也是我們的共識(shí)。

本次將制作一個(gè)名為DoubleLinkedList的容器，這是一個(gè)雙向環(huán)狀鏈表，且具有以下功能：

• 使用數(shù)組或其他該鏈表實(shí)例初始化
• 使用迭代器訪問(wèn)元素
• 使用迭代器加入任意個(gè)數(shù)元素
• 使用迭代器刪除任意個(gè)數(shù)元素
• 取子鏈
• 連接兩條鏈
• 從左到右或從右到左查找元素并返回迭代器
• 排序

1.1迭代器的概念

我們知道數(shù)組其實(shí)就是連成一片的地址，數(shù)組的尋址使用的是指針的方式，在訪問(wèn)指針?biāo)傅脑氐南乱粋€(gè)元素時(shí)，只需要將指針?biāo)傅牡刂?1就行。但是，鏈表的數(shù)據(jù)組織方式是散列的，這意味著要訪問(wèn)鏈表中的下一個(gè)元素，需要先獲取指針目前所指元素中的next指針，也就是：指針=指針->next。

但假如我們把指向鏈表的指針?lè)庋b為一個(gè)類，為指針=指針->next這個(gè)操作重載++運(yùn)算符，就可以讓鏈表的指針像數(shù)組的指針一樣方便操作了。再比如，我們?cè)贋檫@個(gè)類重載+號(hào)，讓類對(duì)象+6這個(gè)操作返回其內(nèi)部指針循環(huán)了6次指針=指針->next操作后形成的新類對(duì)象，就可以將原本需要循環(huán)六次才能完成的操作縮減為一行代碼。這個(gè)類就是我們所說(shuō)的迭代器。

本文中所實(shí)現(xiàn)的鏈表，其內(nèi)部結(jié)構(gòu)是封閉的。外界對(duì)鏈表的一切初始化、增刪改找等操作，都通過(guò)迭代器來(lái)實(shí)現(xiàn)。在DSAGL命名空間里定義iterator泛型類。

namespace DSAGL
{
    public class iterator<T> where T : IComparable
    {
        private DoubleLinkedNode pos;
    }
}

迭代器的成員就是一個(gè)DoubleLinkedNode類對(duì)象，由于C#中對(duì)象是引用，它實(shí)際上起到了指針的作用。

1.2鏈表結(jié)構(gòu)的概念

鏈表中的結(jié)點(diǎn)，是一個(gè)由數(shù)據(jù)、指向前一個(gè)結(jié)點(diǎn)的指針、指向后一個(gè)結(jié)點(diǎn)的指針組成的結(jié)構(gòu)。為了使得我們的鏈表更加符合oop的精神，我們將數(shù)據(jù)設(shè)為只讀，同時(shí)增加一個(gè)bool型的avaluable屬性，用來(lái)指示這個(gè)結(jié)構(gòu)是否可用。假如一個(gè)結(jié)構(gòu)中的數(shù)據(jù)未被初始化或者已經(jīng)被從鏈表中刪除，則avaluable屬性為false，否則為true。

結(jié)點(diǎn)支持默認(rèn)初始化、僅數(shù)據(jù)初始化、利用其他結(jié)點(diǎn)中的數(shù)據(jù)的初始化、數(shù)據(jù)和前后指針初始化和自身在被刪除時(shí)的析構(gòu)。它被聲明為迭代器的嵌套類。

public class DoubleLinkedNode
{
    private T data;
    public bool avaluable;
    private DoubleLinkedNode next;
    private DoubleLinkedNode last;

    public DoubleLinkedNode Next { get { return next; } set { next = value; } }
    public DoubleLinkedNode Last { get { return last; } set { last = value; } }
    public T Data { get { return data; } }

    public DoubleLinkedNode()
    {
        next = this;
        last = this;
        avaluable = false;
    }

    public DoubleLinkedNode(T value)
    {
        data = value;
        next = this;
        last = this;
        avaluable = true;
    }

    public DoubleLinkedNode(DoubleLinkedNode value)
    {
        data = value.data;
        next = this;
        last = this;
        avaluable = true;
    }


    public DoubleLinkedNode(T value, DoubleLinkedNode m_last, DoubleLinkedNode m_next)
    {
        if (!m_last.avaluable || !m_next.avaluable)
        {
            data = value;
            next = this;
            last = this;
            avaluable = true;
        }
        data = value;
        next = m_next;
        m_next.last = this;
        last = m_last;
        m_last.next = this;
        avaluable = true;
    }

    public void delete()
    {
        next.last = last;
        last.next = next;
        next = this;
        last = this;
        avaluable = false;
    }
}

1.3迭代器的尋址

迭代器的尋址方式也是迭代器名稱的由來(lái)：迭代器的每次向后尋址都是將自身所指向的結(jié)點(diǎn)設(shè)為該結(jié)點(diǎn)包含的下一結(jié)點(diǎn)引用。由于地址上的不連續(xù)性，鏈表不能像順序表一樣通過(guò)常數(shù)級(jí)別的地址加減來(lái)找到別的元素，而是要用時(shí)間復(fù)雜度為的迭代尋址法，這也是鏈表和順序表相比最顯著的缺點(diǎn)。

迭代器內(nèi)封裝了私有的findPotion方法。通過(guò)傳入DoubleLinkedNode對(duì)象和尋址的次數(shù)，返回一個(gè)新的對(duì)象，指向參數(shù)尋址后指向的DoubleLinkedNode。

private static DoubleLinkedNode findPotion(DoubleLinkedNode start,int id)
{
    if (id >= 0)
    {
        for (int i = 0; i < id; i++)
            start = start.Next;
    }
    else
    {
        for (int i = 0; i > id; i--)
            start = start.Last;
    }
    return start;
}

注意，假如我們把pos對(duì)象傳給了start參數(shù)，我們更改start對(duì)象的成員的值，是會(huì)更改函數(shù)外面pos對(duì)象的值的，因?yàn)?strong>我們通過(guò)引用更改了對(duì)象本身。但是把start賦值給start.Next這個(gè)操作不會(huì)更改pos引用指向的對(duì)象，因?yàn)?strong>引用本身是按值傳遞的。這更加說(shuō)明了C#的引用傳遞其實(shí)就是缺省的C++中的指針傳遞。

1.4迭代器的初始化

迭代器的初始化支持利用數(shù)值的初始化、利用迭代器的初始化和利用數(shù)組的初始化。利用數(shù)值的初始化就是為迭代器指向的鏈表提供一個(gè)初始結(jié)點(diǎn)，利用數(shù)組的初始化則是從數(shù)組中復(fù)制數(shù)值，讓迭代器指向的鏈表?yè)碛幸粋€(gè)初始序列。

值得一提的是，利用迭代器的初始化和“迭代器1=迭代器2”的區(qū)別。由于對(duì)象的引用特性，后者實(shí)際上是一個(gè)淺拷貝，迭代器1和迭代器2這兩個(gè)字面值都指向同一個(gè)迭代器，那么對(duì)于迭代器2的任何操作，比如指向的結(jié)點(diǎn)的改變，都會(huì)對(duì)迭代器1產(chǎn)生影響。因此，利用迭代器的初始化僅僅是將迭代器2中的pos對(duì)象拷貝給迭代器1，這樣兩個(gè)迭代器雖然指向同一個(gè)結(jié)點(diǎn)，本質(zhì)上卻還是不同的迭代器，因此互不干涉。

public iterator()
{
    pos = new DoubleLinkedNode();
}

public iterator(T obj)
{
    pos = new DoubleLinkedNode(obj);
}

public iterator(iterator<T> it, int id = 0)
{
    pos = pos = findPotion(pos,id);
}

public iterator(T[] tar)//使用數(shù)組初始化
{
    if (tar.Length == 0)
    {
        pos = new DoubleLinkedNode();
        return;
    }
    DoubleLinkedNode first;
    DoubleLinkedNode next;
    first = new DoubleLinkedNode(tar[0]);
    pos=first;
    for (int i = 1; i < tar.Length; i++)
    {
        next = new DoubleLinkedNode(tar[i], first, pos);
        first = next;
    }
}

2.1迭代器的自增自減

對(duì)于自身pos位置的重設(shè)。

public static iterator<T> operator ++(iterator<T> a)
{
    a.pos = a.pos.Next;
    return a;
}

public static iterator<T> operator --(iterator<T> a)
{
    a.pos = a.pos.Last;
    return a;
}

2.2迭代器的加減

和自增自減不同的是，迭代器自身的pos并沒(méi)有改變，而是返回了一個(gè)pos為自身pos經(jīng)過(guò)和加減的數(shù)字有關(guān)的尋址后獲得的新pos的迭代器。這個(gè)新的迭代器和原來(lái)的迭代器無(wú)關(guān)，因此可以被放心地賦值給其他空迭代器。

public static iterator<T> operator +(iterator<T> a, int id)
{
    iterator<T> b = new iterator<T>();
    b.pos = findPotion(a.pos, id);
    return b;
}

public static iterator<T> operator -(iterator<T> a, int id)
{
    iterator<T> b = new iterator<T>();
    b.pos = findPotion(a.pos, -id);
    return b;
}

2.3迭代器的下標(biāo)

迭代器的下標(biāo)和數(shù)組的下標(biāo)用法相同。

在用作右值時(shí)，假如下標(biāo)中的數(shù)字為6，那下標(biāo)運(yùn)算就返回迭代器向后尋址6次后指向的結(jié)點(diǎn)中的數(shù)據(jù)。

在用作左值時(shí)，由于結(jié)點(diǎn)數(shù)據(jù)是密封只讀的，要對(duì)數(shù)據(jù)進(jìn)行更改，就要在尋址后，在當(dāng)前指向的結(jié)點(diǎn)前插入用新值初始化的新結(jié)點(diǎn)，再把原來(lái)的結(jié)點(diǎn)刪除。若刪除的就是pos結(jié)點(diǎn)，還要把pos重設(shè)為新結(jié)點(diǎn)。

由于鏈表中的插入和刪除操作都只涉及常數(shù)個(gè)引用對(duì)象的變更，其時(shí)間復(fù)雜度是很低的。

public T this[int id]
{
    get
    {
        return findPotion(pos, id).Data;
    }
    set
    {
        DoubleLinkedNode next = findPotion(pos, id);
        DoubleLinkedNode newPos = new DoubleLinkedNode(value, next.Last, next);
        if (id == 0)
            pos = newPos;
        next.delete();
    }
}

2.4迭代器的對(duì)比

重載函數(shù)Equal實(shí)現(xiàn)迭代器對(duì)比。“迭代器1==迭代器2”和“迭代器1.Equal(迭代器2)”的概念是不同的，前者表示兩個(gè)迭代器引用的必須是同一個(gè)迭代器對(duì)象，后者只許兩個(gè)迭代器引用的迭代器對(duì)象指向的是同一個(gè)結(jié)點(diǎn)即可。舉例來(lái)說(shuō)，對(duì)于通過(guò)public iterator(iterator<T> it)方法初始化的新迭代器，它和原迭代器用==進(jìn)行對(duì)比時(shí)返回的結(jié)果是false，因?yàn)樾碌骱团f迭代器并非同一個(gè)迭代器，而Equal方法對(duì)比返回的是true，因?yàn)樗麄兊膒os相同。

public bool Equal(iterator<T> it)
{
    if (pos==it.pos)
        return true;
    return false;
}

3.1用迭代器插入單個(gè)元素

插入單個(gè)元素僅僅就是將結(jié)點(diǎn)自己的前后結(jié)點(diǎn)引用修改為要插入的位置的前后結(jié)點(diǎn)，在把上一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)引用修改為插入的元素所在的結(jié)點(diǎn)，把下一個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)引用修改為插入的元素所在的結(jié)點(diǎn)。

public void add(T tar)
{
    if (!pos.avaluable)
    {
        pos = new DoubleLinkedNode(tar);
        return;
    }
    DoubleLinkedNode first = new DoubleLinkedNode(tar, pos.Last, pos);
}

public void add(T tar, int id)
{
    if (!pos.avaluable)
    {
        pos = new DoubleLinkedNode(tar);
        return;
    }
    DoubleLinkedNode first = findPotion(pos,id);
    DoubleLinkedNode now = new DoubleLinkedNode(tar, first, first.Next);
}

3.2用迭代器插入多個(gè)元素

從數(shù)組插入多個(gè)元素的步驟也很簡(jiǎn)單：尋址到起點(diǎn)，以起點(diǎn)為last指針、以終點(diǎn)為next指針創(chuàng)建新結(jié)點(diǎn)，將新結(jié)點(diǎn)設(shè)為起點(diǎn)，循環(huán)往復(fù)。

public void add(T[] tar)
{
    if (tar.Length == 0)
        return;
    int i;
    if (!pos.avaluable)
    {
        i = 1;
        pos = new DoubleLinkedNode(tar[0]);
    }
    else
        i = 0;
    int num = tar.Length, startOfTar = 0;
    DoubleLinkedNode first = pos.Last;
    for (; i < num; i++)
    {
        DoubleLinkedNode now = new DoubleLinkedNode(tar[startOfTar + i], first, first.Next);
        first = now;
    }
}

public void add(T[] tar, int startOfMe, int startOfTar = 0)
{
    if (tar.Length == 0)
        return;
    if (startOfTar < 0)
        return;
    int i;
    if (!pos.avaluable)
    {
        i = 1;
        pos = new DoubleLinkedNode(tar[startOfTar]);
    }
    else
        i = 0;
    int num = tar.Length;
    DoubleLinkedNode first = findPotion(pos,startOfMe);
    for (; i < num; i++)
    {
        DoubleLinkedNode now = new DoubleLinkedNode(tar[startOfTar + i], first, first.Next);
        first = now;
    }
}

public void add(T[] tar, int startOfMe, int startOfTar, int num)
{
    if (tar.Length == 0)
        return;
    if (startOfTar < 0)
        return;
    if (num > tar.Length - startOfTar)
        num = tar.Length - startOfTar;
    int i;
    if (!pos.avaluable)
    {
        i = 1;
        pos = new DoubleLinkedNode(tar[startOfTar]);
    }
    else
        i = 0;
    DoubleLinkedNode first = findPotion(pos, startOfMe);
    for (; i < num; i++)
    {
        DoubleLinkedNode now = new DoubleLinkedNode(tar[startOfTar + i], first, first.Next);
        first = now;
    }
}

3.3鏈的連接

從迭代器插入元素實(shí)際上就是連接兩條鏈。在這個(gè)功能的實(shí)現(xiàn)中將用到迭代器對(duì)鏈表的遍歷，這也是我們使用迭代器操作鏈表的初衷。

public void add(iterator<T> tar)
{
    if (!tar.pos.avaluable)
        return;
    iterator<T> tar2=new iterator<T>(tar);
    if (!pos.avaluable)
    {
        pos = new DoubleLinkedNode(tar2[0]);
        tar2++;
    }
    DoubleLinkedNode first = pos.Last;
    do
    {
        DoubleLinkedNode now = new DoubleLinkedNode(tar2[0], first, first.Next);
        tar2++;
        first = now;
    } while (!tar2.Equal(tar));
}

public void add(iterator<T> tar, int startOfMe, int startOfTar = 0)
{
    if (!tar.pos.avaluable)
        return;
    iterator<T> tar2 = new iterator<T>(tar+startOfTar);
    if (!pos.avaluable)
    {
        pos = new DoubleLinkedNode(tar2[0]);
        tar2++;
    }
    DoubleLinkedNode first = findPotion(pos,startOfMe);
    do
    {
        DoubleLinkedNode now = new DoubleLinkedNode(tar2[0], first, first.Next);
        tar2++;
        first = now;
    } while (!tar2.Equal(tar +startOfTar));
}

public void add(iterator<T> tar, int startOfMe, int startOfTar,int num)
{
    if (!tar.pos.avaluable)
        return;
    int count=0;
    iterator<T> tar2 = new iterator<T>(tar + startOfTar);
    if (!pos.avaluable)
    {
        pos = new DoubleLinkedNode(tar2[0]);
        tar2++;
        count++;
    }
    DoubleLinkedNode first = findPotion(pos, startOfMe);
    do
    {
        if (count >= num)
            break;
        DoubleLinkedNode now = new DoubleLinkedNode(tar2[0], first, first.Next);
        tar2++;
        count++;
        first = now;
    } while (!tar2.Equal(tar + startOfTar));
}

迭代器對(duì)鏈表的遍歷需要先通過(guò)迭代器對(duì)迭代器的初始化創(chuàng)建一個(gè)和起點(diǎn)指向的鏈表結(jié)點(diǎn)相同的迭代器2，之后利用dowhile循環(huán)，在每次循環(huán)當(dāng)中讓迭代器1自增指向下一個(gè)結(jié)點(diǎn)，直到用Equal函數(shù)判斷兩個(gè)迭代器指向的結(jié)點(diǎn)相同。由于鏈表是環(huán)狀的，也就是回到了起點(diǎn)，完成了對(duì)整個(gè)鏈表的遍歷。

使用迭代器對(duì)作為數(shù)據(jù)源的鏈表進(jìn)行遍歷獲取數(shù)據(jù)的同時(shí)，作為目標(biāo)的鏈表也使用普通的添加元素的方式儲(chǔ)存數(shù)據(jù)，就完成了從一個(gè)鏈表中將數(shù)據(jù)插入另一個(gè)鏈表的工作。

4.1刪除元素

刪除元素的步驟就是先尋址獲取需要?jiǎng)h除的第一個(gè)元素，然后利用指向下一個(gè)元素的引用，將自身指向下一個(gè)元素，再調(diào)用上一個(gè)元素的delete方法完成析構(gòu)，再繼續(xù)迭代。若上一個(gè)結(jié)點(diǎn)是pos結(jié)點(diǎn)，則要重設(shè)pos結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)。

public void delete(int start = 0)
{
    DoubleLinkedNode now = findPotion(pos, start);
    do
    {
        now = now.Next;
        now.Last.delete();
    } while (now != pos) ;
}

public void delete(int start, int num)
{
    DoubleLinkedNode now = findPotion(pos, start);
    int count = 0;
    while (count<num)
    {
        now = now.Next;
        if (now.Last == pos)
            pos = now;
        now.Last.delete();
        count++;
    }
}

4.2獲取子鏈

獲取子鏈操作和刪除操作的不同的在于：

• 被刪除的結(jié)點(diǎn)變?yōu)椴豢捎茫渔溨械慕Y(jié)點(diǎn)可用
• 沒(méi)有迭代器指向被刪除的結(jié)點(diǎn)，但有迭代器指向子鏈
• 原鏈的結(jié)構(gòu)不受影響

public iterator<T> sub(int start = 0)
{
    DoubleLinkedNode now = findPotion(pos, start);
    iterator<T> it = new iterator<T>();
    it.pos=new DoubleLinkedNode(now);
    DoubleLinkedNode next = it.pos;
    do
    {
        now = now.Next;
        new DoubleLinkedNode(now,next,it.pos);
        next = next.Next;
    } while (now != pos.Last);
    return it;
}

public iterator<T> sub(int start, int num)
{
    DoubleLinkedNode now = findPotion(pos, start);
    DoubleLinkedNode end = findPotion(now, num);
    iterator<T> it = new iterator<T>();
    it.pos = new DoubleLinkedNode(now);
    DoubleLinkedNode next = it.pos;
    do
    {
        now = now.Next;
        new DoubleLinkedNode(now, next, it.pos);
        next = next.Next;
    } while (now != end);
    return it;
}

4.3棧與隊(duì)列

鏈?zhǔn)綏Ｅc鏈?zhǔn)疥?duì)列的操作，實(shí)際上就是返回隊(duì)頭或棧尾結(jié)點(diǎn)中的值，再將隊(duì)頭或棧尾結(jié)點(diǎn)刪除。注意刪除隊(duì)頭結(jié)點(diǎn)時(shí)要重設(shè)迭代器的pos成員。

public T pop()
{
    if (!pos.avaluable)
        return default(T);
    T obj = pos.Last.Data;
    pos.Last.delete();
    return obj;
}

public T start()
{
    if (!pos.avaluable)
        return default(T);
    T obj = pos.Data;
    pos = pos.Next;
    pos.Last.delete();
    return obj;
}

5.1查找

由于查找并不能更改原迭代器指向的結(jié)點(diǎn)，而是要返回一個(gè)指向與查找目標(biāo)數(shù)值相同的結(jié)點(diǎn)的新迭代器，在函數(shù)當(dāng)中要利用原迭代器初始化新的迭代器。利用dowhile循環(huán)遍歷鏈表，每次將目標(biāo)數(shù)值與目前迭代器指向結(jié)點(diǎn)的數(shù)值進(jìn)行對(duì)比。

public iterator<T> find(T tar, int start = 0)//從左到右查找元素
{
    iterator<T> target = this + start;
    do
    {
        if (target[0].CompareTo(tar)==0)
            break;
        target++;
    } while (target!=this+start);
    return target;
}

public iterator<T> find(T tar, int start,int end)//從左到右查找元素
{
    iterator<T> target = this + start;
    iterator<T> ending = this+end;
    do
    {
        if (target[0].CompareTo(tar) == 0)
            break;
        target++;
    } while (target != ending);
    return target;
}

public iterator<T> reverseFind(T tar, int start = 0)
{
    iterator<T> target = this + start;
    do
    {
        if (target[0].CompareTo(tar) == 0)
            break;
        target--;
    } while (target != this + start);
    return target;
}

public iterator<T> reverseFind(T tar, int start, int end)
{
    iterator<T> target = this + start;
    iterator<T> ending = this + end;
    do
    {
        if (target[0].CompareTo(tar) == 0)
            break;
        target--;
    } while (target != ending);
    return target;
}

5.2快速排序

雙向鏈表具有雙向可迭代性，這與快速排序的需求是一致的。進(jìn)行快速排序的指針在這里從int型的下標(biāo)被替換為了兩個(gè)新建的迭代器，通過(guò)迭代器下標(biāo)取值和下標(biāo)賦值來(lái)實(shí)現(xiàn)數(shù)據(jù)位置的變換。

private void quickSort(iterator<T> s, iterator<T> e)
{
    if (s - 1 != e && s != e)
    {
        iterator<T> i, j;
        T x1, x2;
        i = s;
        j = e;
        x1 = i[0];
        x2 = i[0];
        while (i != j)
        {
            while (i != j && j[0].CompareTo(x1) > 0)
                j--;
            if (i != j)
            {
                i[0] = j[0];
                i++;
            }
            while (i != j && i[0].CompareTo(x1) < 0)
                i++;
            if (i != j)
            {
                j[0] = i[0];
                j--;
            }
        }
        i[0] = x2;
        reQuickSort(s, i - 1);
        reQuickSort(i + 1, e);
    }
}

public void sort()//快速排序
{
    quickSort(this, this-1);
}

private void reQuickSort(iterator<T> s,iterator<T>  e)
{
    if (s-1 != e&&s!=e)
    {
        iterator<T> i, j;
        T x1, x2;
        i = s;
        j = e;
        x1 = i[0];
        x2 = i[0];
        while (i != j)
        {
            while (i != j && j[0].CompareTo(x1) < 0)
                j--;
            if (i != j)
            {
                i[0] =j[0];
                i++;
            }
            while (i!=j && i[0].CompareTo(x1) > 0)
                i++;
            if (i != j)
            {
                j[0] = i[0];
                j--;
            }
        }
        i[0] = x2;
        reQuickSort(s, i - 1);
        reQuickSort(i + 1, e);
    }
}

public void reSort()//快速排序
{
    reQuickSort(this,this-1);
}

結(jié)語(yǔ)

寫(xiě)C#鏈表最大的坑還是引用與對(duì)象本身的區(qū)別，寫(xiě)的時(shí)候必須牢記以下四點(diǎn)：

• 賦值符號(hào)創(chuàng)建同一個(gè)對(duì)象的不同引用
• 構(gòu)造函數(shù)可創(chuàng)建部分成員相同的不同對(duì)象的不同引用
• 引用傳參傳入的引用在函數(shù)當(dāng)中的更改不會(huì)影響函數(shù)外的該引用
• 引用傳參傳入的引用指向的對(duì)象在函數(shù)當(dāng)中的更改會(huì)影響函數(shù)外的該引用指向的對(duì)象