数据结构

一、线性数据结构

1）数组： int array[5]; 末尾添加元素：.push_back();

2）链表：

struct listnode{

int val; listnode *next;

listnode(int x): val(x) , next(NULL) {}

}

listnode *n1= new listnode(4);

n1->next = n2 ;// 构建引用指向

3）栈：先入后出，可用链表和数组实现。 stack stk; 入栈： .push() ； 出栈： .pop();

4）队列： 先入先出，可用链表实现。 queue que; 入队： .push() ； 出队： .pop();

二、非线性数据结构

1）树，分为 二叉树和多叉树。最顶层的节点称为根节点 root

//二叉树定义

strcut treenode{

int val;//节点值

treenode *left;//左子节点

treenode *right;//右子节点

treenode(int x): val(x), left(NULL), right(NULL) {}

}

2）图，由节点（顶点vertex）和边（edge）组成，每条边连接一对顶点。根据边的方向有无，分为有向图和无向图

顶点集合： vertices = {1, 2, 3, 4, 5} 边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

图的表示方法：邻接矩阵和邻接表

（1）邻接矩阵： 使用数组 verticesvertices 存储顶点，邻接矩阵 edgesedges 存储边； edgesiedgesi 代表节点 i + 1i+1 和 节点 j + 1j+1 之间是否有边。

int vertices[5] = {1, 2, 3, 4, 5}; int edges[5] [5]= {{0, 1, 1, 1, 1}, {1, 0, 0, 1, 0}, {1, 0, 0, 0, 1}, {1, 1, 0, 0, 1}, {1, 0, 1, 1, 0}};

(2)邻接表： 使用数组 verticesvertices 存储顶点，邻接表 edgesedges 存储边。 edgesedges 为一个二维容器，第一维 ii 代表顶点索引，第二维 edges[i]edges[i] 存储此顶点对应的边集和；例如 edges[0] = [1, 2, 3,4]

edges[0]=[1,2,3,4] 代表 vertices[0] 的边集合为 1, 2, 3, 4 。

int vertices[5] = {1, 2, 3, 4, 5}; vector> edges;

vector edge_1 = {1, 2, 3, 4}; vector edge_2 = {0, 3}; vector edge_3 = {0, 4}; vector edge_4 = {0, 1, 4}; vector edge_5 = {0, 2, 3}; edges.push_back(edge_1); edges.push_back(edge_2); edges.push_back(edge_3); edges.push_back(edge_4); edges.push_back(edge_5);

3)散列表，通过Hash函数将指定的键key映射至对应的值value

unodered_map dic;

4）堆，是一种基于完全二叉树的数据结构，可用数组实现。

以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。

堆分为「大顶堆」和「小顶堆」，大顶堆：任意节点的值不大于其父节点的值，小顶堆反之。

priority_queue, greater> heap; 压入 .push() , 弹出 .pop() 从小到大弹出

TRANSLATE with

Bing Webmaster Portal