順序表的缺點及解決辦法：
缺點：
- 插入和刪除時需要移動大量元素狡刘，算法時間復(fù)雜度為O(n)。
- 順序線性表長度變化較大時難以確定存儲空間的容量。
- 造成存儲空間的“碎片”易核。
解決思路：
- 所有元素不要考慮相鄰位置了，哪有空位就到哪里浪默，而只是讓每個元素知道它下一個元素的位置在哪里牡直，這樣就可以依次查找了缀匕。同時也解決了“難以確定存儲空間容量”的問題了。
- 思考：這么做是不是也有缺點碰逸？
答：有缺點乡小。如c++標(biāo)準(zhǔn)容器類forward_list用鏈表連接，我要查找里面第n個元素饵史，那么就要從第一個元素開始遍歷满钟，時間復(fù)雜度為O(n)。
鏈表方案：
- 為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系胳喷，對數(shù)據(jù)元素ai來說湃番，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）吭露。
把存儲數(shù)據(jù)元素信息的域成為數(shù)據(jù)域吠撮，把存儲直接后繼位置的域稱為指針域。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像讲竿，稱為結(jié)點（Node）泥兰。 - n個結(jié)點鏈結(jié)成一個鏈表。即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)戴卜。如果每個結(jié)點中只包含一個指針域逾条，就稱為單鏈表。
- 鏈表中第一個結(jié)點的存儲位置稱為頭指針投剥。存取從頭指針開始進(jìn)行师脂。
- 最后一個指針為尾指針，next指針指向NULL江锨。
項目代碼實現(xiàn)思路：
- 現(xiàn)在設(shè)計一個具體的單鏈表實現(xiàn)吃警。假設(shè)項目中，鏈表的數(shù)據(jù)域存儲一個姓名啄育，指針域存儲下一個姓名酌心。將數(shù)據(jù)域和指針域用一個struct封裝起來。
- 要實現(xiàn)的功能為：
1）獲取單鏈表第i個元素的數(shù)據(jù)
2）對單鏈表實現(xiàn)任意位置插入與刪除操作
3）實現(xiàn)整表創(chuàng)建與整表刪除（C++更好實現(xiàn)挑豌，使用構(gòu)造函數(shù)和析構(gòu)函數(shù)即可）
4）打印鏈表最終內(nèi)容
1）獲取單鏈表中第i個元素的數(shù)據(jù)
強(qiáng)調(diào)：這種做法需要讓指針遍歷安券，因此不是一個效率很高的做法。
具體算法思路：
- 聲明一個指針p指向鏈表第一個結(jié)點氓英，初始化j從1開始侯勉。
- 當(dāng)j<i時，就遍歷鏈表铝阐，讓p的指針向后移動址貌，不斷指向下一結(jié)點，j累加1。
- 若到鏈表末尾p為空练对，則說明第i個結(jié)點不存在遍蟋。
- 否則查找成功，返回結(jié)點p的數(shù)據(jù)螟凭。
說明：第三條很重要虚青，因為在面試中，一個程序的魯棒性非常重要赂摆。它意味著你的程序是否健壯以及是否有抵御bug的能力挟憔。
2）在任意位置插入元素
強(qiáng)調(diào)：單鏈表的尾插非常方便，但是如果在任意位置插入烟号，則需要遍歷之前的所有元素直至找到當(dāng)前位置。因此時間復(fù)雜度也較高政恍，消耗資源大汪拥。
具體算法思路：
- 聲明一個指針p指向鏈表頭結(jié)點，初始化j從1開始篙耗。
- 當(dāng)j<pos時迫筑，就遍歷鏈表，讓p的指針向后移動宗弯，不斷指向下一結(jié)點脯燃，j累加1。
- 若到鏈表末尾p為空蒙保，則說明第pos個結(jié)點不存在辕棚。（魯棒性）
- 否則查找成功，在系統(tǒng)中生成一個空結(jié)點s邓厕。
- 將string對象st賦值給node->name逝嚎。
- 插入標(biāo)準(zhǔn)語句node->next = p->next;,p->next=node。
- 長度length加一详恼。
- 返回补君。
（p是一個查找用的指針）
3）在任意位置刪除元素
具體算法思路：
- 核心就是刪除第pos個元素，將第pos-1個指針的next指針繞過第i個元素昧互，指向第pos+1個結(jié)點挽铁。
- 首先聲明指針p指向鏈表頭指針，初始化j從1開始敞掘。
- 當(dāng)j<i時遍歷鏈表叽掘，讓p的指針向后移動，不斷指向下一個結(jié)點渐逃，j累加1够掠。
- 若到鏈表末尾p為空，則說明第i個結(jié)點不存在茄菊。
- 否則查找成功疯潭，將欲刪除的結(jié)點p->next賦值給q赊堪。
- 單鏈表的刪除標(biāo)準(zhǔn)語句p->next=q->next，p為q之前的結(jié)點竖哩。
- 長度length減一哭廉。
- 釋放q結(jié)點，返回成功相叁。
具體代碼
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é)點和p->next鏈起來。
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）具體測試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
