學(xué)習(xí)內(nèi)容來自數(shù)據(jù)結(jié)構(gòu)詳解——線性表（C++實(shí)現(xiàn)）

線性表（List）:零個或多個數(shù)據(jù)元素的有限序列。
順序表（數(shù)組）：元素地址單元連續(xù)。
鏈表：結(jié)點(diǎn)地址不連續(xù)，由指針指向下個元素地址。

一、線性表的抽象數(shù)據(jù)類型

ADT 線性表(List)
Data
    線性表的數(shù)據(jù)對象集合為{a1,a2,....,an},每個元素的類型均為DataType。其中，除了第一個元素a1外，每一個元素有且只有一個直接前驅(qū)元素，除最后一個元素an外，每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。

Operation
    InitList(*L):初始化操作，建立一個空的線性表。
    ListEmpty(L):若線性表為空，返回true，否則返回false。
    ClearList(*L):線性表清空。
    GetElem(L,i,*e):將線性表L中第i個位置元素返回給e。
    LocateElem(L,e):在線性表L中查找與給定值e相等的元素，如果查找成功,返回該元素在表中的序列號；否則，返回0表示失敗。
    ListInsert(*L,i,e):在線性表的第i個位置插入元素e。
    ListDelete(*L,i,*e):刪除線性表L中的第i個元素，并用e返回其值
    ListLength(L):返回線性表L的元素個數(shù)。
    PrintList(L):打印線性表

對于不同的應(yīng)用，線性表的基本操作是不同的，上述操作是最基本的。
對于實(shí)際問題中涉及的關(guān)于線性表的更復(fù)雜操作，完全可以用這些基本操作的組合來實(shí)現(xiàn)。

二、順序儲存結(jié)構(gòu)

定義：用一段連續(xù)地址單元依次儲存
結(jié)構(gòu)：
順序表模板類代碼：

//順序存儲
const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
    SeqList() { length = 0; } //無參數(shù)構(gòu)造
    SeqList(DataType[], int n); //有參數(shù)構(gòu)造
    ~SeqList() {}
    int Length() { return length; }//返回線性表長度
    DataType Get(int i);//按位查找
    int Locate(DataType x);//按值查找
    void Insert(int i, DataType x);//插入
    DataType Delete(int i);//刪除
    void PrintList();//遍歷
private:
    DataType data[MaxSize];  //順序列表采用數(shù)組實(shí)現(xiàn)
    int length;
};

順序表描述需要三個屬性：

• 儲存空間的起始位置：數(shù)組data
• 線性表最大儲存容量：數(shù)組長度MaxSize
• 線性表當(dāng)前長度：length

有參數(shù)構(gòu)造：

創(chuàng)建一個長度為n的順序表，需要將給定的數(shù)組元素作為線性表的數(shù)據(jù)元素傳入順序表中，并將傳入的元素個數(shù)作為順序表的長度。

template <class DataType>
SeqList<DataType>::SeqList(DataType a[],int n) 
{
    if (n > MaxSize) throw"wrong parameter";
    for (int i = 0; i < MaxSize; i++)
        data[i] = a[i];
    length = n;
}

按位查找

時(shí)間復(fù)雜度O(1).

template <class DataType>
DataType SeqList<DataType>::Get(int i)
{
    if (i<1 && i>length) throw "wrong locate";
    else
        return data[i - 1];
}

按值查找

對順序表元素依次比較，返回下標(biāo)+1。

template<class DataType>
int SeqList<DataType>::Locate(DataType x)
{
    for (int i = 0; i < length; i++)
        if (data[i] == x) return i + 1;
    return 0;
}

插入

• 注意移動方向，必須從最后一個元素開始移動。

• 表滿，引發(fā)上溢異常；插入位置不合理，引發(fā)位置異常。

  
  

template<class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
    if (length == MaxSize) throw  "overSize";
    if (i<1 || i>length + 1) throw "eror Location";
    
    for (int j=length; j > i-1; j--)
    {
        data[j] = data[j-1];
    }
    data[i - 1] = x;
    length++;
}

刪除

• 注意元素移動方向，移動元素前需取出被刪元素。

• 表為空，則發(fā)生下溢；位置不合理異常，引發(fā)位置

  
  

template<class DataType>
DataType SeqList<DataType>::Delete(int i)
{
    if (i<1 || i>length + 1) throw "eror Location";
    DataType x = data[i - 1];
    for (int j = i; j < length; j++)
    {
        data[j-1] = data[j];
    }
    length--;
    return x;
}

遍歷

template<class DataType>
void SeqList<DataType>::PrintList()
{
    for (int i = 0; i < length; i++)
        std::cout << data[i] << std::endl;
}

順序儲存的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 隨機(jī)訪問特性，查找時(shí)間O(1),存儲密度高
• 無須為邏輯關(guān)系增加額外儲存空間
  缺點(diǎn)：
• 插入、刪除需移動大量數(shù)據(jù)元素
• 線性表長度變化大，難以確定儲存空間
• 造成儲存空間“碎片化”

三、鏈?zhǔn)絻Υ?/h4>

1.鏈?zhǔn)絻Υ娑x

鏈表的定義是遞歸的，它或者為空null，或者指向另一個節(jié)點(diǎn)node的引用，這個節(jié)點(diǎn)含有下一個節(jié)點(diǎn)或鏈表的引用，線性鏈表的最后一個結(jié)點(diǎn)指針為“空”（通常用NULL或“^”符號表示）。

2.鏈?zhǔn)絻Υ鎸?shí)現(xiàn)方式

儲存方法

//鏈表
template<class DataType>
struct Node  //結(jié)構(gòu)體模板
{
    DataType data; //儲存數(shù)據(jù)
    Node<DataType> *next; //儲存下一節(jié)點(diǎn)地址（傳遞自定義類型參數(shù)DataType）
};

結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成。

template<class DataType>
class LinkList 
{
public:
    LinkList();
    LinkList(DataType [],int n);
    ~LinkList();
    int Length();//返回線性表長度
    DataType Get(int i);//按位查找
    int Locate(DataType x);//按值查找
    void Insert(int i, DataType x);//插入
    DataType Delete(int i);//刪除
    void PrintList();//遍歷
private:
    Node<DataType> *first;
};

特點(diǎn)

• 一組任意儲存單元儲存線性表數(shù)據(jù)元素——未被占用的任意位置
• 鏈?zhǔn)絻Υ嫘璐娣艛?shù)據(jù)、后繼元素存儲地址

無參數(shù)構(gòu)造
生成只有頭結(jié)點(diǎn)的空鏈表

template<class DataType>
LinkList<DataType>::LinkList()
{
    first = new Node<DataType>; //new頭指針指向的頭地址
    first->next = NULL; //初始化頭指針
}

有參數(shù)構(gòu)造單鏈表

• 頭插法構(gòu)造

  
  

//頭插法：將新申請的結(jié)點(diǎn)插在頭結(jié)點(diǎn)后面 
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;
    first->next = NULL;
    for (int i = 0; i < n; i++)
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = a[i];
        s->next = first->next;
        first->next = s;
    }
}

• 尾插法構(gòu)造

  
  

//尾插法:將新申請的結(jié)點(diǎn)插在終端節(jié)點(diǎn)的后面 
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;
    Node<DataType> *r = first;
    for (int i = 0; i < n; i++)
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = a[i];
        r->next = s;
        r = s; 
    }
    r->next = NULL; //終端結(jié)點(diǎn)指針域置空
}

析構(gòu)函數(shù)

單鏈表中結(jié)點(diǎn)通過new申請，需通過析構(gòu)中的delete進(jìn)行釋放。

template<class DataType>
LinkList<DataType>::~LinkList()
{
    while (first != NULL) //頭地址不為空，鏈表有值
    {
        Node<DataType> *q = first;
        first = first->next;
        delete q;
    }
}

計(jì)算長度

將單鏈表掃描一遍,，時(shí)間復(fù)雜度為O(n)

//時(shí)間復(fù)雜度O(n)
template<class DataType>
int LinkList<DataType>::Length()
{
    Node<DataType> *p = first->next;
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

按位查找

單鏈表中即使知道節(jié)點(diǎn)位置也不能直接訪問，需要從頭指針開始逐個節(jié)點(diǎn)向下搜索，平均時(shí)間性能為O(n)，單鏈表是順序存取結(jié)構(gòu)

DataType LinkList<DataType>::Get(int i)
{
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL && count < i)
    {   
        p = p->next;
        count++;
    }
    if (p == NULL) throw "no data"; //未找到
    else return p->data; 
}

按值查找

單鏈表中按值查找與順序表中的實(shí)現(xiàn)方法類似，對鏈表中的元素依次進(jìn)行比較，平均時(shí)間性能為O(n).

template<class DataType>
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL)
    {
        if (p->data == x)
            return count;
        p = p->next;//移動查詢指針
        count++;
    }
    return 0;//no found
}

插入

單鏈表在插入過程中需要注意分析在表頭、表中間、表尾的三種情況，由于單鏈表帶頭結(jié)點(diǎn)，這三種情況的操作語句一致，不用特殊處理，時(shí)間復(fù)雜度為O(n).

template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1){
        p = p->next;
        count++;
    }
    if (p == NULL) throw"Location";
    else {
        Node<DataType> *s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

刪除

刪除操作時(shí)需要注意表尾的特殊情況，此時(shí)雖然被刪結(jié)點(diǎn)不存在，但其前驅(qū)結(jié)點(diǎn)卻存在。因此僅當(dāng)被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)存在且不是終端節(jié)點(diǎn)時(shí)，才能確定被刪節(jié)點(diǎn)存在，時(shí)間復(fù)雜度為O(n)

template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i -1 )
    {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL) throw "Location"; //注意不能是終端結(jié)點(diǎn)
    else
    {
        Node<DataType> *q = p->next;
        p->next = q->next;
        return q->data;
    }
}

遍歷

template<class DataType>
void LinkList<DataType>::PrintList()
{
    Node<DataType> *p = first->next;
    while (p != NULL )
    {
        std::cout << p->data << std::endl; 
        p = p->next;    
    }
}

鏈?zhǔn)絻Υ鎯?yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 插入、刪除無需移動其他元素，只用改變指針
• 鏈表各結(jié)點(diǎn)內(nèi)存空間無需連續(xù)，利用率高

缺點(diǎn)：

• 查找需遍歷

四、其他類型鏈表

循環(huán)鏈表

• 特點(diǎn)是表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。（通常為了使空表和非空表的處理一致，通常也附加一個頭結(jié)點(diǎn)）

• 通常以判斷指針是否等于某一指定指針來判定是否掃描了整個循環(huán)鏈表。

  
  

雙鏈表

循環(huán)鏈表雖然可以從任意結(jié)點(diǎn)出發(fā)掃描其他結(jié)點(diǎn)，但是如果要查找其前驅(qū)結(jié)點(diǎn)，則需遍歷整個循環(huán)鏈表。為了快速確定任意結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，可以再每個節(jié)點(diǎn)中再設(shè)置一個指向前驅(qū)結(jié)點(diǎn)的指針域，這樣就形成了雙鏈表。

template<class DataType>
struct Node
{
    DataType data;
    Node<DataType> *prior,*next;
};

結(jié)點(diǎn)p的地址既存儲在其前驅(qū)結(jié)點(diǎn)的后繼指針域內(nèi)，又存儲在它后繼結(jié)點(diǎn)的前驅(qū)指針域中
需要注意：

• 循環(huán)雙鏈表中求表長、按位查找、按值查找、遍歷等操作的實(shí)現(xiàn)與單鏈表基本相同。
• 插入操作需要修改4個指針，并且要注意修改的相對順序。

靜態(tài)鏈表

靜態(tài)鏈表是用數(shù)組來表示單鏈表，用數(shù)組元素的下標(biāo)來模擬單鏈表的指針.
靜態(tài)鏈表儲存儲存：

const int MaxSize = 100;
template<class DataType>
struct Node{
    DataType data;
    int next;
}SList[MaxSize];

靜態(tài)鏈表雖然是用數(shù)組來存儲線性表的元素，但在插入和刪除操作時(shí)，只需要修改游標(biāo)，不需要移動表中的元素，從而改進(jìn)了在順序表中插入和刪除操作需要移動大量元素的缺點(diǎn)，但是它并沒有解決連續(xù)存儲分配帶來的表長難以確定的問題