数据结构和算法---第一章（综述）

青旅半醒 2023-03-14 08:18 225阅读 0赞

**一、什么是数据结构？什么是算法？**

数据结构是指**数据在计算机的内存或者磁盘上的存储情况**，也是对数据的逻辑结构和物理结构研究。**算法则是指对数据的各种处理方法。**例如：增加数据、删除数据、修改数据、查找数据（即CRUD）、和对数据进行排序等。总之，学好数据结构对一个程序员来说非常重要，学好这个课程有利于我们对现实世界中数据的存储，起到建模的作用，是程序员的重要工具。

**二、数据结构的概述**

常见的数据结构有：数组、有序数组、栈、队列、链表、二叉树、红-黑树、2-3-4树、哈希表、堆、图等。下面我们用表格列出它们的优缺点。

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th>优点</th> 
   <th>缺点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数组</td> 
   <td>插入快，如果知道下标可快速存取</td> 
   <td>查找慢，删除慢，大小固定</td> 
  </tr> 
  <tr> 
   <td>有序数组</td> 
   <td>比无序数组查找快</td> 
   <td>插入、删除慢，大小固定</td> 
  </tr> 
  <tr> 
   <td>栈</td> 
   <td>提供后入先出的存取方式</td> 
   <td>存取其他项很慢</td> 
  </tr> 
  <tr> 
   <td>队列</td> 
   <td>提供先进先出的存取方式</td> 
   <td>存取其他项很慢</td> 
  </tr> 
  <tr> 
   <td>链表</td> 
   <td>查找、删除快</td> 
   <td>查找慢</td> 
  </tr> 
  <tr> 
   <td>二叉树</td> 
   <td>查找、插入、删除都很快（如果树保持平衡）</td> 
   <td>删除算法复杂</td> 
  </tr> 
  <tr> 
   <td>红黑树</td> 
   <td>查找、插入、删除都快，树也总是平衡的</td> 
   <td>算法复杂</td> 
  </tr> 
  <tr> 
   <td>2-3-4树</td> 
   <td>查找、插入、删除都快，树也总是平衡的，类似的树对磁盘存储有用</td> 
   <td>算法复杂</td> 
  </tr> 
  <tr> 
   <td>哈希表</td> 
   <td>如果知道关键字则存取很快，插入快</td> 
   <td>删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分</td> 
  </tr> 
  <tr> 
   <td>堆</td> 
   <td>插入、删除快，对最大数据项存取很快</td> 
   <td>对普通数据项存取慢</td> 
  </tr> 
  <tr> 
   <td>图</td> 
   <td>对现实世界建模</td> 
   <td>部分算法慢且复杂</td> 
  </tr> 
 </tbody> 
</table>

**三、算法的概述**

程序=数据结构+算法，算法的文本意思是对模型分析的一组可行的，确定的，有穷的规则，它有五个特征：**有穷性**、**确定性**、**可行性**、**输入**、**输出**。

**四、名词定义**

**数据库（database）**

数据库是按照数据结构来组织、存储和管理数据的仓库。例如一个存放着所有学生的各项信息数据的数据集就可以称为一个数据库。

**记录（record）**

记录是指数据库中划分成的单元，例如某一个学生在数据库中所有的信息就可以称为一条记录，在java中一个记录被称为一个相应类的对象，例如一个学生就可以称为一个对象。

**字段（field）**

一条记录可由多个字段组成，例如一个学生的数学成绩可以称为一个字段，在java中字段又被称为变量或者成员。

**关键字（keyword）**

在数据库中查找一条记录，需要指定某一个字段作为唯一的标识来区别每条记录，这个被指定被用来做唯一标识的字段就是关键字。例如学生的学号。

**五、基本数据类型**

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>大小（按位计）</th> 
   <th>取值范围</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>1</td> 
   <td>true或false</td> 
  </tr> 
  <tr> 
   <td>byte</td> 
   <td>8</td> 
   <td>-128 ~ +127</td> 
  </tr> 
  <tr> 
   <td>char</td> 
   <td>16</td> 
   <td>‘\u0000’ ~ ‘uFFFF’</td> 
  </tr> 
  <tr> 
   <td>short</td> 
   <td>16</td> 
   <td>-32768 ~ +32767</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td>32</td> 
   <td>-2147483648 ~ +2147483647</td> 
  </tr> 
  <tr> 
   <td>long</td> 
   <td>64</td> 
   <td>-9223372036854775808 ~ +9223372036854775807</td> 
  </tr> 
  <tr> 
   <td>float</td> 
   <td>32</td> 
   <td>约10<sup>-38</sup> ~ 10<sup>+38</sup>；7位有效数字</td> 
  </tr> 
  <tr> 
   <td>double</td> 
   <td>64</td> 
   <td>约10<sup>-308</sup> ~ 10<sup>+308</sup>；15位有效数字</td> 
  </tr> 
 </tbody> 
</table>