常见数据结构

 一、线性结构

 

1.最简单的结构:线性表

     线性表具有以下特征:

   - 有且只有一个"首元素";

   - 有且只有一个"末元素";

   - 除末元素之外,其余元素均有唯一的后继元素;

   - 除首元素之外,其余元素均有唯一的前去元素;

   对于线性表主要可进行以下操作:

   - 添加节点 - 插入节点 - 删除节点  - 查找节点  - 遍历节点  - 统计节点数

 

2.先进先出的结构:队列

      队列是一种特殊的线性表,队列是按照"先进先出"(First In First Out,FIFO)原则处理数据,只允许在表的前端进行删除操作,而在表的后端进行插入操作.进行插入操作的端称为队尾,进行删除的一段称为队头.当队列中没有元素时,称为空队列.

      对队列这种数据结构操作很简单,主要有以下几种:

     -初始化队列: 创建一个队列.

     - 进队列:将一个元素添加到队尾.

     - 出队列:将队头的元素取出,同时删除该元素,使后一个元素成为队头.

     - 获取队列第一个元素:将队头的元素取出,不删除该元素(队头仍然是该元素)

     - 获取队列长度:根据队头,队尾计算出队列中元素的数量.

 

循环队列(一种特殊的队列):

 

 3.先进后出的结构:栈

       栈是一种线性表的特殊表现形式,与队列的"先进先出"不同,栈是按照"后进先出"(Last In First Out,LIFO)的原则处理数据.

       栈的基本操作只有两个:

       - 入栈(Push):即将数据保存到栈顶.进行该操作前,先修改栈顶指针.使其向上移一个元素位置,然后将数据保存到栈顶指针所指向的位置.

      - 出栈(Pop):即将栈顶的数据弹出,然后修改栈顶指针,是其指向栈中的下一个元素.

 

二、树结构

 

树的概念：

 

    二叉树的概念:

      - 在二叉树中,第i层的节点总数最多有2i-1个节点.

      - 深度为k的二叉树最多有2k-1个节点(k>=1),最少有k个节点.

      - 对于一棵二叉树,如果其叶节点数为n0,而度为2的节点总数为n2,则n0=n2+1.

      - 具有n个节点的完全二叉树的深度k为:k=[log2n]+1.

 

      - 有n个节点的完全二叉树各节点如果用顺序方式存储,对任意节点i,有如下关系.

 

如果i!=1,则其父节点的编号为i/2;

如果2*i<=n,则其左子树根节点的编号为2*i;若2*i>n,则无左子树.

如果2*i+1<n,则其右子树根节点编号为2*i+1;若2*i+1>n,则无右子树.

 

    遍历二叉树:

      先序遍历(DLR):称为先根次序遍历,即先访问根节点,再先序遍历左子树,最后先序遍历右子树.

      先序遍历(LDR):称为中根次序遍历,先中序遍历左子树,即访问根节点,最后再中序遍历右子树.

      先序遍历(LRD):称为先根次序遍历,即先后续遍历左子树,再后序遍历右子树,最后访问根节点.

      按层遍历:按二叉树的层进行遍历,可更直观的从图中得出遍历的结果.

 

二叉树的概念:

 

 

线索二叉树:

 

线索二叉树的表示:

 

 

最优二叉树(赫夫曼树):

 

赫夫曼编码:

 

 

 

三、网状关系:图

 

1.图的定义:

无向图and有向图:

 

无向图:

 

有向图:

 

 

2.图的存储:

 

邻接矩阵and邻接表:

邻接矩阵:

邻接表:

 

3.图的遍历

 

       广度优先遍历:

         广度优先遍历类似于树的按层次遍历,具体过程如下:

      ---(1)从isTrav数组中选择一个未被访问的顶点Vi,将其标记为已访问.

      ---(2)接着依次访问Vi的所有未被访问的邻接点,并标记为已被访问过.

      ---(3)从这些邻接点出发进行广度优先遍历,直至图中所有和Vi有路径相通的顶点都被访问过. 

 

      ---(4)重复步骤1至步骤3,直至所有顶点都被访问过.

 

       深度优先遍历:

         深度优先遍历方法类似于树的先序遍历.

      ---(1)从isTrav数组中选择一个未被访问的顶点Vi,将其标记为已访问.

      ---(2)接着从Vi的一个未被访问过的邻接点出发进行深度优先遍历.

      ---(3)重复步骤2,直至图中所有和Vi有路径相同的顶点都被访问过.

      ---(4)重复步骤1-步骤3,直至所有的顶点都被访问过.