C++ 数据结构与容器.md · scgg/每日算法

[toc]

## 一. 链表

### 1.1 单向链表

#### 1.1.1 传统链表

**模型：**

![传统链表](E:\My Word\MarkDown文件\图片\数据结构\传统链表.png)

~~~c++
#include<iostream>
using namespace std;

//链表节点
struct LinkNode{
    int data; //指向任何类型数据
    LinkNode* next;
};

//链表结构体
struct LinkList{
    LinkNode* head;
    int size;
};

//初始化链表
LinkList* init(){
    LinkList* list = new LinkList;
    list -> size = 0;
    list -> head = NULL;
    return list;
}
//末尾插入
template<typename T>
void push_back(LinkList* list, T value){
    LinkNode* node = new LinkNode;
    node -> data = value;
    node -> next = NULL;
    if(list->head == NULL){
        list->head = node;
        list->size = 1;
    }
    else{
        LinkNode* pt = list->head;
        while(pt->next!=NULL)
            pt = pt->next;
        pt->next = node;
        list->size++;
    }
}

//指定位置插入
template<typename T>
void insert(LinkList* list, int pos, T value){
    if(pos == list->size - 1)
        push_back(list, value);
    else if(pos==0){
        LinkNode* node = new LinkNode;
        node -> data = value;
        node -> next = list->head;
        list->head = node;
        list->size++;
    }
    else{
        int num = 0;
        LinkNode* pt = list->head;
        while(num<pos){
            pt = pt -> next;
            num++;
        }
        LinkNode* ps = pt -> next;
        LinkNode* node = new LinkNode;
        node -> data = value;
        node -> next = ps;
        pt->next = node;
        list->size++;
    }
}
//遍历链表的值
void print(LinkList* list){
    if(list->head==NULL)
        cout<<"NULL";
    else{
        LinkNode* pt = list->head;
        while(pt->next!=NULL){
            cout<<pt->data<<" ";
            pt = pt->next;
        }
        cout<<pt->data;
    }
}

int main(){
	LinkList* list = init();
	for(int i=0;i<5;i++)
		push_back(list, i);
	print(list);
	insert(list, 2, 255);
	cout<<endl;
	print(list);
	return 0;
}
~~~

**结果：**

![执行结果](E:\My Word\MarkDown文件\图片\数据结构\链表结果.png)

#### 1.1.2 企业链表

**模型：**

![企业链表](E:\My Word\MarkDown文件\图片\数据结构\企业链表.png)

**对比传统链表的优势：** 数据类型可以任意更改，只需重构一下输出函数即可

```c++
#include <iostream>
#include<string>

using namespace std;

//企业链表
struct LinkNode {
	LinkNode* next;
};

struct LinkList {
	LinkNode head;
	int size;
};

//初始化链表
LinkList* init() {
	LinkList* list = new LinkList;
	list->head.next = NULL;
	list->size = 0;
	return list;
}

//插入
void insert(LinkList* list, int pos, LinkNode* data) {
	LinkNode* pre = &list->head;
	for (int i = 0; i < pos; i++) {
		pre = pre->next;
	}
	data->next = pre->next;
	pre->next = data;
	list->size++;

}

struct student {
	LinkNode node;
	string name;
	int age;
};

void sss(LinkNode* node) {
	student* s = (student*)node;
	cout << s->name << " " << s->age << endl;
}

//打印
void print(LinkList* list) {
	LinkNode* p = list->head.next;
	if (list->size==0)
		return;
	while (p != NULL) {
		student* s = (student*)p;
		cout << s->name << " " << s->age << endl;
		p = p->next;
		
	}
}

int main() {
	student s1, s2, s3, s4;
	s1.age = 18; s2.age = 19; s3.age = 20; s4.age = 21;
	s1.name = "AAA";
	s2.name = "BBB";
	s3.name = "CCC";
	s4.name = "DDD";
	LinkList* list = init();
	insert(list, 0, (LinkNode*)&s1);
	insert(list, 1, (LinkNode*)&s2);
	insert(list, 2, (LinkNode*)&s3);
	insert(list, 3, (LinkNode*)&s4);
	print(list);
	return 0;
}
```

**结果：**

![企业链表结果](E:\My Word\MarkDown文件\图片\数据结构\企业链表结果.png)

### 1.2 list容器

**简介：** list是C++的标准容器之一，是一个双向链表

**头文件：** `#include <list>`

**构造函数：**

- `list<int> c0;` ：创建一个空链表c0
- `list<int> c1(3);` ：创建一个含三个默认值（都为0）的链表c1
- `list<int> c2(5,2);` ：创建一个含五个值的链表c2，其中每个值都为二
- `list<int> c3(c1);` ：创建一个链表c3，并将c1拷贝给c3
- `list<int> c4(c1.begin(), c1.end());` ：使用迭代器将某个链表的一部分拷贝给c4

**函数：**

- `c.begin()` ：返回指向链表第一个元素的迭代器
- `c.end()` ：返回指向链表最后一个元素之后的迭代器
- `c.rbegin()` ：返回逆向链表的第一个元素,即c链表的最后一个元素的迭代器
- `c.rend()` ：返回逆向链表的最后一个元素的下一个位置,即c链表的第一个数据再往前的位置的迭代器

- `c.assign(n, num)` ：将n个num拷贝赋值给链表c

- `c.assign(c1.begin(), c1.end())` ：将c1的部分拷贝给c，这里是将c1完全拷贝给c

- `int a[3] = {1,2,3}; c.assign(a, a+3);` ：将数组a的值赋给链表c

- `c.swap(c1)` ：交换c和c1里的元素，前提是两个链表的元素类型相同

- `c.front()` ：返回链表c的第一个元素

- `c.back()` ：返回链表c的最后一个元素

- `c.empty()` ：判断链表是否为空，若为空返回true

- `c.size()` ：返回链表c中实际元素的个数

- `c.resize(num)` ：重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除

- `c.resize(num, elem)` ：重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除

- `c.max_size()` ：返回链表c可能容纳的最大元素数量

- `c.clear()` ：清除链表c中的所有元素

- >`c.insert(pos,num) ` ： 在pos位置插入元素num。
  >
  >`c.insert(pos,n,num)` ：在pos位置插入n个元素num。
  >
  >`c.insert(pos,c1.beg(),c1.end())` ：在pos位置插入c1链表里区间为[beg,end)的元素。
  >
  >==**pos** 、**beg** 、**end** 都是迭代器类型==

- `c.push_back(num)` ：在末尾增加一个元素num

- `c.pop_back()` ：删除末尾的元素

- `c.push_front(num)` ：在开始位置增加一个元素num

- `c.pop_front()` ： 删除第一个元素

- `c.emplace_front(num)` ：在容器头部插入一个元素num, 该函数和 push_front() 的功能相同，但效率更高

- `c.emplace_back(num)` ：在容器尾部直接插入一个元素num, 该函数和 push_back() 的功能相同，但效率更高

- `emplace()` ：在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高

- `c.erase(pos)` ：删除pos位置的元素（pos为迭代器），返回下一个数据的位置

- `c.erase(beg, end)` ：删除[beg, end)区间内的元素，返回下一个数据的位置

- `c.remove(elem)` ：删除容器中所有与elem值匹配的元素

- `c.reverse()` ：反转链表

- `c.unique()` ：删除容器中相邻的重复元素，只保留一个

- `c.merge(c2)` ：合并2个有序的链表到c中并使之有序,释放c2

- `c.splice(c.begin(), c2)` ：将c2插入到c1的begin位置,释放c2

- `c1.splice(c1.beg,c2,c2.beg,c2.end)` ：c2的[beg,end)位置的元素连接到c1的beg位置并且释放c2的[beg,end)位置的元素

- `c.sort()` ：将链表排序，默认升序

- `c.sort(compare)` ：自定义回调函数实现自定义排序

> 例：
  >
  > ```c++
  > bool compare(int a, int b){
  >     return a > b;
  > }
  > c.sort(compare); //降序排列
  > ```

## 二、栈

**头文件** ：`#include <stack>`

和其它容器相比，stack是一类存储机制简单、提供成员函数较少的容器：

| 成员函数   | 作用                                       |
| ---------- | ------------------------------------------ |
| empty()    | 当栈为空时返回true，否则返回false          |
| size()     | 返回stack中元素个数                        |
| top()      | 返回栈顶元素的引用，如果栈为空，程序会报错 |
| push(val)  | 将val元素压入栈顶                          |
| pop()      | 删除栈顶元素                               |
| top()      | 返回栈顶元素                               |
| c.swap(c1) | 交换两个栈的元素                           |

## 三、map容器

**头文件** ：`#include <map>`

map容器类似python的字典类型，是使用键值对来存储数据。在map中，所有元素都会根据键值自动排序。底层是用二叉树实现，不允许容器中出现重复的键值。

**构造** ：

- map<key, value> v;     (例：map<string， int> v，其中键的类型为string，值的类型为int)

**插入** ：

map里的每个元素都是关联的键值对，在c++里属于pair类型

- pair<string ,int> p("Tom", 20);
- pair<string, int> p = make_pair("Tom", 20);

访问key值：

cout<<p.first;         //结果为Tom

cout<<p.second;     //结果为20

使用p.first和p.second来访问每一项的键和值

所以，map容器在插入时：

- v.insert(pair<string,int>("Tom", 20));
- v.insert(make_pair("Tom", 20));

*注意：使用insert插入时，如果新插入的key值在map中已经存在，则不会执行*

数组插入：

- v["Tom"] = 20;

*和insert不同的是，如果新插入的key值在map中已经存在，则更新value值*

**不建议使用数组形式去插入，建议用于查找和更新** ，这是由于当键不存在时，会自动为该键赋0值并插入。

**删除** ：

- v.erase(v.begin());    删除指定位置元素
- v.erase(v.begin(), v.end());     删除指定区间元素
- v.erase(key);       删除指定key值元素

**清空** ：

- v.clear();

**查找** ：

- v.find(key);       若找到返回key值处的迭代器，否则返回迭代器v.end()

**统计** ：

- v.count(key)    统计键为key的元素个数，在map里要么为0，要么为1

**大小和交换** ：

- v.size();        返回容器中元素数目
- v.empty();        若容器为空返回true
- v.swap(v1);         交换v和v1的元素

**排序** ：

按键值从大到小排序：

```c++
class compare
{
	public:
        bool operator()(int v1,int v2)
		{
			return v1>v2;
		}
}
map<int,int,compare> v;
```

scgg/每日算法

简介

发行版

贡献者

近期动态

scgg/每日算法 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

scgg/每日算法