数据结构--数组、单链表和双链表介绍以及双向链表
数组：
数组有上界和下界，数组的元素在上下界内是连续的。
数组的特点是：数据是连续的；随机访问速度快。
数组中稍微复杂⼀点的是多维数组和动态数组。对于C语⾔⽽⾔，多维数组本质上也是通过⼀维数组实现的。⾄于动态数组，是指数组的容量能动态增长的数组；对于C语⾔⽽⾔，若要提供动态数组，需要⼿动实现；⽽对于C++⽽⾔，STL提供了Vector。
单向链表：
单向链表(单链表)是链表的⼀种，它由节点组成，每个节点都包含下⼀个节点的指针。
表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的后继节点是"节点30"(数据为20的节点)，"节点30"的后继节点是"节点40"(数据为10的节点)，......
删除"节点30"
删除之前："节点20" 的后继节点为"节点30"，⽽"节点30" 的后继节点为"节点40"。
删除之后："节点20" 的后继节点为"节点40"。
在"节点10"与"节点20"之间添加"节点15"
添加之前："节点10" 的后继节点为"节点20"。
添加之后："节点10" 的后继节点为"节点15"，⽽"节点15" 的后继节点为"节点20"。
单链表的特点是：节点的链接⽅向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很⾼。
双向链表：
双向链表(双链表)是链表的⼀种。和单链表⼀样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意⼀个结点开始，都可以很⽅便地访问它的前驱结点和后继结点。⼀般我们都构造双向循环链表。
表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的
节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；末尾节点的后继节点是表头。
删除"节点30"
删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。
删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。
在"节点10"与"节点20"之间添加"节点15"
添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。
添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。
C++ STL之list双向链表容器
list的前向链，由头节点→第1个节点→第2个节点→…第n个节点→头节点构成循环。
list的反向链，则由第n个节点→第n-1个节点→…→头节点→第n个节点构成循环。n为list的节点个数，整个链表的存储位置由头指针指出，它指向头节点。
/*
1. list初始化：
（1）list<int>  t;  //没有任何元素
（2）list<int>  t(10);  //创建有10个元素的链表
（3）list<int>  t(10, 3); //创建有10个元素的链表，并且每个元素为3
2. 对链表进⾏插⼊操作：
（1）前插法：在链表头部插⼊新元素，链表⾃动扩张，形式：
t.push_front(8);
（2）尾插法：在链表尾部插⼊新元素，链表⾃动扩张，形式：
t.push_back(9);
（3）中间插⼊：⽤insert()函数，参数是要插⼊位置的迭代器，例如:
it = t.begin();
It++;    //注意链表的迭代器只能进⾏++或--操作，⽽不能进⾏+n
t.insert(it, 20);    //操作
3. 链表的遍历：
(1) 反向遍历：形式：
list<int>::reverse_iterator  rit;
for (rit = t.rbegin(); rit != t.rend(); rit++)
(2) 正向遍历：形似：
list<int>:iterator  it;
for (it = t.begin(); it != t.end(); it++)
4.删除元素的⽅法
(1)remove()⽅法删除⼀个元素，值相同的元素都会被删除，参数为元素的值，⽽不是迭代器的位置, 例如：t.remove(8);
(2)使⽤pop_front()⽅法删除链表⾸元素，例如: t.pop_front();
(3)使⽤pop_back()⽅法删除链表尾元素，例如：t.pop_back();
(4)使⽤erase()⽅法删除迭代器位置上的元素，例如：
数组和链表
it = t.begin();
it++;    //注意链表的迭代器只能进⾏++或--操作，⽽不能进⾏+n
it++;    //操作，但是for(it=t.begin();it!=t.end();it++)这个不影响
(5) clear()，清空链表，例如：t.clear();
(6) size(), 求元素的个数，例如：cout << t.size() << endl;
(7) find(), 在链表中查元素，头⽂件为#include<algorithm>若到，则返回该元素，迭代器的位置，若不到，则返回end()迭代器的位置。查的形式为：list<int>::iterator it;
it = find(t.begin(), t.end(), 8); //这点和其他的不同,list的要有查区间的
(8) sort()⽅法对链表进⾏排序，默认的是升序排列，形式：t.sort();
(9) unique()⽅法可以删除连续重复的元素，注意是连续重复的元素，
例如是1 2 3 4 1 则不可删除1。
*/
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
int main()
{
list<int> l;
l.push_back(2);
l.push_back(5);
l.push_back(4);
l.push_back(4);
l.push_back(6);
l.push_back(4);
list<int>::iterator it;
cout << "剔除前：" << endl;
for (it = l.begin(); it != l.end(); it++)
cout << *it << " ";
cout << endl;
l.unique(); //剔除连续重复元素，只保留⼀个
cout << "剔除后：" << endl;
for (it = l.begin(); it != l.end(); it++)
cout << *it << " ";
cout << endl;
system("pause");
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。