常见的数据结构都有哪些（浅显理解数据结构及各类数据结构的关系）

数据结构 = 数据元素 数据元素的关系，我来为大家讲解一下关于常见的数据结构都有哪些?跟着小编一起来看一看吧!

常见的数据结构都有哪些

数据结构 = 数据元素 数据元素的关系。

数据元素的关系也是数据。

这里的关系是指逻辑意义上的关系，包括：

I 一对一的线性关系：元素之间是前驱后继的关系。

II 一对多的树型关系：元素之间是父子、兄弟关系。

III 多对多的图型关系：元素之间是邻接关系。

元素及其关系都需要存储到存储器才能被处理，存储的方式称为存储关系，存储还有关系？有的。计算机的存储单元是一种线性关系，因为不可能所有的数据都存储到一起，有时需要分散存储。正像我们在一个仓库存储物品一样，当一批物品所需要的空间较大，而仓库没有这样大的一整块空间，但一些零散的空间可以存储下来，就要分散存储（假设分7个位置），分散存储的物品，如何能找到全部的物品呢？

I 每一个位置再放置一张卡片，上面标识下一个位置的地址，只要知道了第一个位置的地址，顺着找便能全部找到；

II 额外建立一张表格，用来存储每一个地址，这样的表格称索引表，你打开索引表一看，就知道物品的位置了，就像一本书的目录一样。

以上都是需要额外增加空间来表示存储关系的，对应到计算机存储器上的数据存储，就是链式存储和索引存储。

顺序存储自然不用说，数据不加处理地按顺序放到一起，通过存储单元的线性关系来体现其数据元素逻辑上的线性关系，如数组。还有一种称为哈希存储的方式，我们知道，对于一个数组，数组名就是这一块内存单元的基地址，通过偏移值便可以得出各元素的偏移地址，在数据中，偏移值称为下标。对于一个数据元素，在一个数组的地址空间中，如果不考虑按顺序放置数据元素，是否可以根据数据元素的关键字来确定一个特定的下标呢？这是可以的，解决的办法就是使用哈希函数，用哈希函数哈希一下这个关键字，得出一个特定的下标，作为其存储地址，这样，当用关键字查询时，只需用哈希函数哈希关键字便可求出地址而找到元素了。当然，有可能会有几个关键字通过相同的哈希函数哈希出相同的下标，解决的方法很多，其中之一就是链地址法，将相同下标的数据元素再串成一张线性链表，这样就形成了数组 链表的方式。

数组 链表的方式是一个万能的方式，数据元素的关系都可以通过链式存储来实现，相比用数组（如图型的邻接矩阵）来存储数据关系，更能节约内存空间，如树型的孩子链表表示法、图型的邻接表等。

不管是数组 数据（或二维数组）还是数组 链表，都是一种线性关系，所以说，非线性关系的树型和图型的逻辑关系和存储关系都是用线性的数据或链表来表示和存储的。

线性关系是一种一维关系，树型和图型可以理解为一种二维关系，二维关系可以用二维数组来描述，也可以用数组 链表的方式来描述和存储。

我们来看一下数组和链表的在增删、查找等基础操作上执行性能（时间复杂度）：

数组：增删是O(n)，查找是O(1)。

链表：增删是O(1)，查找是O(n)。

如何在两者之间获得一个平衡？

在数据结构中，二叉树是一个很特殊的存在。我们知道，现实中的树不可能只有两个叉，在计算机科学中也是一样，二叉树也是特意设置的，我们知道，二分查找可以获得O(logn)的效率，如果用一个图形来描述，就是一个二叉树的形状。

如果将线性关系的数据组织成特定二叉树的形式，其查找效率便可以获得O(logn)的时间复杂度，O(1)<O(logn)<O(n)，所谓的特定就是要求相对平衡和有序，如平衡搜索树，红黑树等。

另外，对于数据结构，很核心的一个东西就是遍历了，遍历离不开循环，循环要理解循环的结束方式及元素或指针的移动方式。

数组和链表的遍历较简单，也不需要什么辅助的数据结构，树和图就要复杂一些，要将一个非线性结构进行线性化的操作。深度优先遍历需要一个显式栈或隐式栈（递归会由编译器实现一个隐式栈），广度优先遍历需要一个队列作为辅助。

无论哪种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。

处理头部优先的时候，也就是先加入的先探索，就是广度优先了，因为，头部的都是兄弟节点；

而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点，后加入的先探索——也就是所谓一条路走到死。

同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。

所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。(不管是广度还是深度，遍历都会形成一条一维的线)

1 数组

for (int i = 0; i < n; i ) { printf(“%d\n”, a[i]); }

下标是相对于数组起始地址a的偏移量，i 表示每次移动一个数据类型的内存单元长度。

for的循环次数确定，因此循环结束条件也是确定的：i < n。

i ……→n。

2 链表

typedef struct lnk { int data; struct lnk* next; }*lnkPtr; lnkPtr p; …… while (p) { p = p->next; }

对于链表，尾部结构会特殊处理，将next指针置为NULL，这样在循环时便可以将此作为结束标志。

链表的指针域指向相邻结点，因此指针的移动用p = p->next;表示。

对于指针的赋值，可以理解为指针指向。如p = p->next;可以理解为p指向p->next。

p = p->next……→p(NULL)

3 栈和队列

while(!stk.empty()) // 栈非空 { stk.pop(); // 出栈； // 操作出栈元素 } while(!q.empty()) // 队非空 { q.dequeue( ); // 出队； // 操作出队中元素 }

栈有顺序栈（一般用数组实现）和链式栈（一般用单链表实现），队列也是如此。其循环操作类似上述的数组与链表。在出栈函数中一般定义了内存地址或指针的移动，也类似于上述的数组与链表。

stk.pop()……stk.empty()==0 q.dequeue……q.empty()==0

-End-