|
致敬卷风—一位伟大的战士
? ? ? ? 首先用粗俗的语言描述一下链表是什么以及他的作用：
? ? ? ? 链表在某些作用上大致等同于一个动态的数组，尽管链表的编码和管理比数组更复杂，但它们有一些明显的优势。首先，链表可以容易地扩大或缩小。实际上，程序员并不需要知道链表中有多少个结点。它们只是根据需要在内存中创建。这样一来使得内存的利用率大大提高了。当然，使用动态的数组模板还有很多，这里只是对比一下链表与数组的不同。
数组的特点
- 在内存中，数组是一块连续的区域。
- 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
- 插入数据和删除数据效率低。
- 随机读取的效率很高。
?链表的特点
- 内存不要求连续
- 拓展方便，随意增加大小
- 随机访问效率低，但是目前而言不需要考虑这一点
? ??
稍微介绍一下几个链表的创建方法：
1.最基本的定义
#include<bits/stdc++.h>
using namespace std;
// 定义一个结构体 就是单个节点 这里是储存包含数据的一个结构 value
//同时还要有一个指向另一个相同类型节点的指针
struct List
{
double value;
List* next;
};
int main()
{
List* head = nullptr;//初始化
//不能用list 小写list是容器
//nullptr是用来代替NULL的宏定义的 一般两者等价
head = new List;//分配一个新的节点
head->value = 1;//储存值进入value
head->next = nullptr;//表示链表的结尾
List * two = new List;
two->value = 2;
two->next = nullptr;
//这里吧nullptr变成了two指向nest的结果，所以第二个节点现在变成了链表的结尾
head->next = two;//现在第一个节点的next指向的是two
cout << head->value<<endl;
cout << two->value;
//也可以写成
//head->next-value;
return 0;
}
2.特别一点的结构内定义函数
（这个方法使得在创建链表的时候变得更加简洁）
#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
double value;
ListNode* next;
//构造函数
ListNode(double value1, ListNode* next1 = nullptr)
{
value = value1;
next = next1;
}
};
int main()
{
ListNode* three = new ListNode(5);
//通过仅指定其 value 部分，而后继指针则默认为 nullptr
ListNode* secondPtr = new ListNode(13.5,three);
//通过指定 value 部分和一个指向链表下一个结点的指针。
ListNode* head = new ListNode(12.5, secondPtr);
//领悟这个创建列表的方法 注意是倒着写
cout << head->value<<endl;
cout<<secondPtr->value<<endl;
cout << three->value;
}
其次是一个经典的头插法链表
可以用来大炮打小鸡解决倒序问题
#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
double value;
ListNode* next;
//构造函数
ListNode(double value1, ListNode* next1 = nullptr)
{
value = value1;
next = next1;
}
};
int main()
{
ListNode *one = nullptr;
double a[5];
for (int i = 0; i < 5; i++)
{
cin >> a[i];
one = new ListNode(a[i],one);
}
ListNode* ntr = one;
while (ntr != nullptr)
{
cout << ntr->value;
ntr=ntr->next;
}
}
尾插法
#include<bits/stdc++.h>
using namespace std;
struct List
{
int data;
List* next;
};
int main()
{
List* head = new List;//新节点
int a[5];
List* rear = head;//开一个尾指针 一直指向尾巴
for (int i = 0; i < 5; i++)
{
cin >> a[i];
List* one = new List;
one->data = a[i];
rear->next = one;//让尾指针指向one
rear = one;
/*rear 本来在 one前面，但现在rear在one上，
因为是赋地址值，原来rear并没有消失，下个循环one = new List，
就又重新创建一个节点，反复执行*/
}
rear->next = nullptr;
List* h = head->next;
//头节点没数据 所以h直接指向头节点的next
while (h != nullptr)
{
cout << h->data;
h = h->next;
}
}
END
|