《数据结构》学习笔记 - 内容综述

一些基础的概念：

1，什么是数据结构？

数据结构是指带有某种结构或者关联的数据的集合。包含两点：

• 含有数据元素的信息；
• 含有各数据元素的前后件关系；
  • 前后件关系，是指数据元素的逻辑关系，与在计算机中的存储位置无关。

数据元素的逻辑结构：反应数据元素间逻辑关系的结构。

数据元素的存储结构：数据元素间存放位置的结构。深入理解如下：

• 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同。
  • 　　例如：Vector，数据的逻辑关系与存储位置关系是一致的；而List，则不一致。
• 在数据的存储结构中，不仅存放各数据的元素信息，还需存放各数据元素间的前后件关系
  • 　　例如List中，存放指针，以指向元素的前驱与后继。

2，如何理解“某个空的数据结构”这句话？什么是数据结构中的根节点/内部结点/终端结点？

简单讲，就是元素的前后件关系建立了，但是却没有存放元素；如一个空的Vector，存储空间分配了，元素的逻辑关系也定了，但是还没有元素。

没有前件的结点，称为根结点；没有后件的结点称为终端结点（又称叶结点）；有前后件的结点称为内部结点：

3，线性数据结构与非线性数据结构

如果一个非空的数据结构满足以下两个条件，则可以成为线性数据结构；否则为非线性。

• 有且仅有一个根结点；
• 每一个结点最多有一个前件，也最多有一个后件；

线性结构的一个性质：在其中插入或者删除一个结点后还应是线性结构。

4，数据结构支持的操作：静态操作和动态操作

• 静态操作：仅从中获取信息，如向量的size(), get()操作。
• 动态操作：修改数据结构中的信息，如向量的insert()，remove()操作。

5, 数据结构的存储策略：静态存储和动态存储

• 静态存储：各元素物理地址连续，各数据项的物理存放位置与逻辑次序完全对应。
• 动态存储：如list，各元素逻辑上具有线性次序，但物理存放位置上却没有任何限制。
• 例如：Vector为静态存储，对静态操作的效率很高；List为动态存储，对动态操作的效率很高。

《数据结构》学习笔记 - 内容综述

原文：https://www.cnblogs.com/sanlangHit/p/11968076.html