基本数据类型:
布尔型bool
字符型char
整型int
浮点型float
---------------------------------------------------------------------
修饰符:
signed
unsigned
short
long
---------------------------------------------------------------------
自定义数据类型:
指针类型:
int *p;
枚举类型:
enum Color{red,blue,yellow};默认第一个red值为0,其他依次加1
数组类型:
int a[5],b[2][3];
结构类型:变量成为成员或者域 声明结构时不分配内存
struct Node
{
int data;
NOde *next
};
Node t,*s;
访问结构中的成员t.data,s->data;t是结构变量,s是指针结构变量。
联合类型 :
//所有成员共享相同的内存单元,联合变量所占内存长度为最长的成员所占内存长度
union Uarea
{
int data;
int *link;
};
类类型:是一组变量及其相关函数的封装体。
class Node
{
public:
int getData();
private:
protected:
};
int Node::getData()//::域运算符
{return *;}
关键字typedef
typedef int DataType;
数据结构:data structure相互之间存在一定关系的数据元素的集合。分为以下两种结构:
逻辑结构:(用户视图)集合,线性结构,树结构,图结构(后两个也叫非线性结构)。常将数据的逻辑结构称为数据结构。
存储结构:(物理结构,实现的视图)顺序存储和链接存储结构。
线性表(顺序表,单链表,双链表,栈,队列,串)
广义线性表(多维数组 矩阵 广义表)
树和二叉树(树)二叉树和树都是树型结构。二叉树不是树。
最小生成树(Prim最近的点,Kuskal最短的边)
最短路径(Dijkstra,Floyd)
-------------------------------------------
数组
优点:插入块如果知道坐标可以快速去地存取
缺点:查找慢,删除慢,大小固定
有序数组
优点:比无序数组查找快
缺点:删除和插入慢,大小固定
栈
优点:提供后进先出的存取方式
缺点:存取其他项很慢
队列
优点:提供先进先出的存取方式
缺点:存取其他项都很慢
链表
优点:插入快,删除快
缺点:查找慢
二叉树
优点:查找,插入,删除都快(如果数保持平衡)
缺点:删除算法复杂
红-黑树
优点:查找,插入,删除都快,树总是平衡的
缺点:算法复杂
2-3-4树
优点:查找,插入,删除都快,树总是平衡的。类似的树对磁盘存储有用
缺点:算法复杂
哈希表
优点:如果关键字已知则存取速度极快,插入块
缺点:删除慢,如果不知道关键则存取很慢,对存储空间使用不充分
堆
优点:插入,删除块,对最大数据的项存取很快
缺点:对其他数据项存取很慢
图
优点:对现实世界建模
缺点:有些算法慢且复杂
容器:特性,优缺点
vector
典型的序列容器,C++标准严格要求次容器的实现内存必须是连续的,唯一可以和标准C兼容的stl容器,任意元素的读取、修改具有常数时间复杂度,在序列尾部进行插入、删除是常数时间复杂度,但在序列的头部插入、删除的时间复杂度是O(n),可以在任何位置插入新元素,有随机访问功能,插入删除操作需要考虑。
Vector的数据模型就是数组。
优点:内存和C完全兼容、高效随机访问、节省空间
缺点:内部插入删除元素代价巨大、动态大小查过自身容量需要申请大量内存做大量拷贝。
deque
序列容器,内存也是连续的,和vector相似,区别在于在序列的头部插入和删除操作也是常数时间复杂度,可以在任何位置插入新元素,有随机访问功能。
Deque的数据模型是数组和链表的折衷:
优点:高效随机访问、内部插入删除元素效率方便、两端push pop
缺点:内存占用比较高
list
序列容器,内存是不连续的,任意元素的访问、修改时间复杂度是O(n),插入、删除操作是常数时间复杂度,可以在任何位置插入新元素。
List的数据结构模型是链表
优点:任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度
缺点:不支持随机访问、比vector占用更多的存储空间
set
关联容器,元素不允许有重复,数据被组织成一棵红黑树,查找的速度非常快,时间复杂度是O(logN)
Map、set、multimap、multiset的数据结构模型是二叉树(红黑树)
优点:元素会按照键值排序、查找是对数时间复杂度、通过键值查元素、map提供了下标访问
multiset
关联容器,和set一样,却别是允许有重复的元素,具备时间复杂度O(logN)查找功能。
map
关联容器,按照{键,值}方式组成集合,按照键组织成一棵红黑树,查找的时间复杂度O(logN),其中键不允许重复。
multimap
和map一样,区别是键可以重复
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。