順序表的缺點(diǎn)及解決辦法：

缺點(diǎn)：

• 插入和刪除時(shí)需要移動(dòng)大量元素，算法時(shí)間復(fù)雜度為O(n)。
• 順序線性表長(zhǎng)度變化較大時(shí)難以確定存儲(chǔ)空間的容量。
• 造成存儲(chǔ)空間的“碎片”。

解決思路：

• 所有元素不要考慮相鄰位置了，哪有空位就到哪里，而只是讓每個(gè)元素知道它下一個(gè)元素的位置在哪里，這樣就可以依次查找了。同時(shí)也解決了“難以確定存儲(chǔ)空間容量”的問(wèn)題了。
• 思考：這么做是不是也有缺點(diǎn)？
  答：有缺點(diǎn)。如c++標(biāo)準(zhǔn)容器類forward_list用鏈表連接，我要查找里面第n個(gè)元素，那么就要從第一個(gè)元素開(kāi)始遍歷，時(shí)間復(fù)雜度為O(n)。

鏈表方案：

• 為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。
  把存儲(chǔ)數(shù)據(jù)元素信息的域成為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱為指針域。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)（Node）。
• n個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表。即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。如果每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，就稱為單鏈表。
• 鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置稱為頭指針。存取從頭指針開(kāi)始進(jìn)行。
• 最后一個(gè)指針為尾指針，next指針指向NULL。

項(xiàng)目代碼實(shí)現(xiàn)思路：

• 現(xiàn)在設(shè)計(jì)一個(gè)具體的單鏈表實(shí)現(xiàn)。假設(shè)項(xiàng)目中，鏈表的數(shù)據(jù)域存儲(chǔ)一個(gè)姓名，指針域存儲(chǔ)下一個(gè)姓名。將數(shù)據(jù)域和指針域用一個(gè)struct封裝起來(lái)。
• 要實(shí)現(xiàn)的功能為：
  1）獲取單鏈表第i個(gè)元素的數(shù)據(jù)
  2）對(duì)單鏈表實(shí)現(xiàn)任意位置插入與刪除操作
  3）實(shí)現(xiàn)整表創(chuàng)建與整表刪除（C++更好實(shí)現(xiàn)，使用構(gòu)造函數(shù)和析構(gòu)函數(shù)即可）
  4）打印鏈表最終內(nèi)容

1）獲取單鏈表中第i個(gè)元素的數(shù)據(jù)

強(qiáng)調(diào)：這種做法需要讓指針遍歷，因此不是一個(gè)效率很高的做法。
具體算法思路：

• 聲明一個(gè)指針p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開(kāi)始。
• 當(dāng)j<i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j累加1。
• 若到鏈表末尾p為空，則說(shuō)明第i個(gè)結(jié)點(diǎn)不存在。
• 否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)。
  說(shuō)明：第三條很重要，因?yàn)樵诿嬖囍?，一個(gè)程序的魯棒性非常重要。它意味著你的程序是否健壯以及是否有抵御bug的能力。

2）在任意位置插入元素

強(qiáng)調(diào)：?jiǎn)捂湵淼奈膊宸浅７奖?，但是如果在任意位置插入，則需要遍歷之前的所有元素直至找到當(dāng)前位置。因此時(shí)間復(fù)雜度也較高，消耗資源大。
具體算法思路：

• 聲明一個(gè)指針p指向鏈表頭結(jié)點(diǎn)，初始化j從1開(kāi)始。
• 當(dāng)j<pos時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j累加1。
• 若到鏈表末尾p為空，則說(shuō)明第pos個(gè)結(jié)點(diǎn)不存在。（魯棒性）
• 否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s。
• 將string對(duì)象st賦值給node->name。
• 插入標(biāo)準(zhǔn)語(yǔ)句node->next = p->next;,p->next=node。
• 長(zhǎng)度length加一。
• 返回。
  （p是一個(gè)查找用的指針）

3）在任意位置刪除元素

具體算法思路：

• 核心就是刪除第pos個(gè)元素，將第pos-1個(gè)指針的next指針繞過(guò)第i個(gè)元素，指向第pos+1個(gè)結(jié)點(diǎn)。
• 首先聲明指針p指向鏈表頭指針，初始化j從1開(kāi)始。
• 當(dāng)j<i時(shí)遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j累加1。
• 若到鏈表末尾p為空，則說(shuō)明第i個(gè)結(jié)點(diǎn)不存在。
• 否則查找成功，將欲刪除的結(jié)點(diǎn)p->next賦值給q。
• 單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句p->next=q->next，p為q之前的結(jié)點(diǎn)。
• 長(zhǎng)度length減一。
• 釋放q結(jié)點(diǎn)，返回成功。

具體代碼

1）Linklist.h

#include<string>
using std::string;
struct Node
{
    string name;
    Node * next;
};
class Linklist
{
private:
    Node * head;
    int length;
public:
    Linklist():head(NULL),length(0){};
    ~Linklist();
    Node * GetHead();
    Node * ReverseList(Node * head);
    void Insert(int pos,string st);
    void Delete(int pos);
    void GetLinkListElem(int i,string st);
    void Print();
};

2）Linklist.cpp

#include<iostream>
#include"Linklist.h"
using std::cout;
using std::endl;
Linklist::~Linklist()
{
    Node * temp = new Node;  
    for(int i=0;i<length;i++)  
    {  
        temp = head;  
        head = head->next;  
        delete temp; 
    }
}
Node * Linklist::GetHead()
{
    return this->head;
}
Node * Linklist::ReverseList(Node * head)
{
    Node * node = head;
    Node * prev = NULL;
    while(node != NULL)
    {
        Node * next1 = node->next;
        node->next = prev;
        prev = node;
        node = next1;
    }
    this->head = prev;
    return prev;
}
void Linklist::Insert(int pos,string st)
{
    int j = 1;
    Node * node = new Node;
    Node * p = head;
    if (pos == 1)
    {
        node->name = st;
        node->next = p;
        head = node;
        length++;
        return;
    }
    while(p && j < pos-1)//尋找p==pos-1的位置,在其后插入即為在pos處插入。
    {
        p=p->next;
        j++;
    }
    if(!p || j > pos)//考慮p超出鏈表范圍（變成NULL），pos為0或小于0的情況
    {
        cout << "Cannot insert!" << endl;
        return;
    }
    node->name = st;
    node->next = p->next;
    p->next = node;
    length++;
}
void Linklist::Delete(int pos)
{
    int j = 1;
    Node * p = head;
    if (pos == 1)
    {
        head = head->next;
        length--;
        return;
    }
    while(p && j < pos-1)//尋找p==pos-1的位置，在p->next刪除即為在pos刪除。
    {
        p=p->next;
        j++;
    }
    if(!p || j > pos)//如果p超出范圍或pos太小
    {
        cout << "Cannot delete!" << endl;
        return;
    }
    Node * temp = new Node;
    temp = p->next;
    p->next = temp->next;//把temp后面的結(jié)點(diǎn)和p->next鏈起來(lái)。
    delete temp;//釋放temp，即p->next。
    length--;
}
void Linklist::Print()
{
    if(head == NULL)
    {
        cout << "Linklist has no elements." << endl;
        return;
    }
    Node * temp = head;
    while(temp != NULL)
    {
        cout << temp->name << "," << endl;
        temp = temp->next;
    }
    cout << endl;
}

3）具體測(cè)試main.cpp

#include"Linklist.h"
#include<iostream>
using std::cout;
using std::endl;
int main()
{
    Linklist L;
    L.Insert(1,"sword");
    L.Print();
    L.Insert(2,"edward");
    L.Print();
    L.Insert(3,"ed");
    L.Print();
    Node * head = L.GetHead();
    head = L.ReverseList(head);
    head = L.GetHead();
    L.Print();
    return 0;
}

4）輸出結(jié)果

Paste_Image.png