Chapter01 Introduction to Data Structure

本章介绍了数据结构的基本概念，主要的学习内容如下

1.数据结构的基本概念

1.1数据机构的定义

• 数据元素 是数据的基本单位（例如,A班中的每一个学生记录都是一个数据元素）
• 数据对象 是性质相同的有限个数据元素的集合。默认情况下数据结构下指的数据都是数据对象。
• 数据结构 是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。

1.2数据的逻辑结构

数据的逻辑结构是用户根据需要建立的数据组织形式，反映了数据元素之间的逻辑关系，而不是物理关系，独立于计算机。

• 线性结构 只有一个开始记录(王华同学的记录)和一个终端记录（李丽同学的记录），其余每个记录只有一个前趋记录和后继记录。也就是说具有一对一的关系。

• 树型结构 只有一个开始结点，却有多个终端结点，也就是说结点间存在多对多关系

• 图形结构 一个结点与一个或多个结点相连。也就是说结点间存在多对多关系

  

• 集合 集合中的数据元素没有任何相邻关系

1.3数据的存储结构

数据的存储结构应正确的反映数据元素之间的逻辑关系。也就是说，不仅要存储所有的数据元素，还有存储数据元素之间的关系。

• 顺序存储结构

  把逻辑上相邻的结点存储在物理位置上也相邻的存储单位里，结点之间的逻辑关系有存储单位的邻接关系来体现。有个形象的比喻：顺序存储就像是一个皮表带，结点就是一个个表孔，无法拓展。

  • 优点：节省存储空间，因为逻辑关系和物理关系是一致的，所以不用占用额外的存储空间。
  • 缺点：不便于修改。
    

• 链式存储结构

  链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑是由附加的指针字段表示的。有个形象的比喻：链式存储有点像链条表带，插入、删除运算时只需要修改相应结点的指针域。

  • 优点：便于修改
  • 缺点：占用更多空间
    

• 索引存储结构

  除了存储结点信息之外，还建立附加的索引表，索引表中的每一项称为索引项，索引项：（关键字：地址）。

  • 优点：随机访问
  • 缺点：要多存储一个索引表，降低空间利用率

• 哈希（散列）存储结构

  根据结点的关键字，通过Hash函数直接计算一个值（具体内容查找相关Hash函数），并将这个值作为该结点的存储地址。

  • 适用：一般用于对数据能够进行快速查找和插入的场合。
  • 优点：查找速度快
  • 缺点：不储存结点的逻辑关系

1.4数据结构和数据类型

这两个概念经常混淆，但实际上很容易区分，因为我比较熟悉C#和Java,所以会用Java中的数据类型来举例。

• 数据类型 是一组性质相同的值的集合和定义在此集合上的一组操作的总称

  说白了，在高级语言中、或者非高级语言直接支持的数据结构即为数据类型

  比方说，C#和Java的数据类型都可以分为

  • 简单类型(值类型)：整数类型、浮点数、字符、布尔
  • 引用类型：数组、类、接口等

  这里要注意String是引用类型。

  具体的分类看下面两张图：
  

  

1.5算法分析

这里只简单介绍算法分析中的时间复杂度和空间复杂度，起到提示的作用。后面复习到算法在具体分析。

• 算法时间复杂度：主要的表示方法是大O表示法，是一个关于问题规模n的函数
  $T(n)=3n^2-5n+100=O(n^2)$T(n)=3n2−5n+100=O(n2)
  那么这个问题的时间复杂度就为$O(n^2)$O(n2)，因为它的最高阶是$n^2$n2，主要随着$n^2$n2增长而增长。

• 算法空间复杂度

  是指对一个算法在运行过程中临时占用的存储空间的大小的度量