顺序表的缺点及解决办法：
缺点：
- 插入和删除时需要移动大量元素，算法时间复杂度为O(n)。
- 顺序线性表长度变化较大时难以确定存储空间的容量。
- 造成存储空间的“碎片”。
解决思路：
- 所有元素不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道它下一个元素的位置在哪里，这样就可以依次查找了。同时也解决了“难以确定存储空间容量”的问题了。
- 思考：这么做是不是也有缺点？
答：有缺点。如c++标准容器类forward_list用链表连接，我要查找里面第n个元素，那么就要从第一个元素开始遍历，时间复杂度为O(n)。
链表方案：
- 为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
把存储数据元素信息的域成为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。 - n个结点链结成一个链表。即为线性表的链式存储结构。如果每个结点中只包含一个指针域，就称为单链表。
- 链表中第一个结点的存储位置称为头指针。存取从头指针开始进行。
- 最后一个指针为尾指针，next指针指向NULL。
项目代码实现思路：
- 现在设计一个具体的单链表实现。假设项目中，链表的数据域存储一个姓名，指针域存储下一个姓名。将数据域和指针域用一个struct封装起来。
- 要实现的功能为：
1）获取单链表第i个元素的数据
2）对单链表实现任意位置插入与删除操作
3）实现整表创建与整表删除（C++更好实现，使用构造函数和析构函数即可）
4）打印链表最终内容
1）获取单链表中第i个元素的数据
强调：这种做法需要让指针遍历，因此不是一个效率很高的做法。
具体算法思路：
- 声明一个指针p指向链表第一个结点，初始化j从1开始。
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
- 若到链表末尾p为空，则说明第i个结点不存在。
- 否则查找成功，返回结点p的数据。
说明：第三条很重要，因为在面试中，一个程序的鲁棒性非常重要。它意味着你的程序是否健壮以及是否有抵御bug的能力。
2）在任意位置插入元素
强调：单链表的尾插非常方便，但是如果在任意位置插入，则需要遍历之前的所有元素直至找到当前位置。因此时间复杂度也较高，消耗资源大。
具体算法思路：
- 声明一个指针p指向链表头结点，初始化j从1开始。
- 当j<pos时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
- 若到链表末尾p为空，则说明第pos个结点不存在。（鲁棒性）
- 否则查找成功，在系统中生成一个空结点s。
- 将string对象st赋值给node->name。
- 插入标准语句node->next = p->next;,p->next=node。
- 长度length加一。
- 返回。
（p是一个查找用的指针）
3）在任意位置删除元素
具体算法思路：
- 核心就是删除第pos个元素，将第pos-1个指针的next指针绕过第i个元素，指向第pos+1个结点。
- 首先声明指针p指向链表头指针，初始化j从1开始。
- 当j<i时遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1。
- 若到链表末尾p为空，则说明第i个结点不存在。
- 否则查找成功，将欲删除的结点p->next赋值给q。
- 单链表的删除标准语句p->next=q->next，p为q之前的结点。
- 长度length减一。
- 释放q结点，返回成功。
具体代码
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后面的结点和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）输出结果
Paste_Image.png
