数据结构基础笔记Day1

基本介绍： 私人向的数据结构与算法的基础内容笔记 每天学习一点点，加油鸭! 路线是王卓老师（基础很细）–> 陈越姥姥(更难一点）

基本概念和术语

1.数据（Data） 定义： 是能输入计算机且被计算机处理的各种符号的集合 分为： 数值型的数据：整数、实数 非数值型的数据：文字、图像、图形、声音

2.数据元素 定义： 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理 也简称为元素，或记录、结点、顶点 （注意！它不是最小的，还可以被分成数据项） 举例： 比如表格里面的一行数据：小明，男，2001 人机对弈的某一种走法 导航里面某个地点

3.数据项 定义：构成数据元素不可分割的最小单位 比如上面的一行数据里的其中项，如小明就是一个数据项

小总结： 4.数据对象 定义:是性质相同的数据元素的集合，是数据的一个子集 以上四个容易混淆，现解析 1.数据基本单位是数据元素，数据元素的最小单位是数据项 2.相同数据的集合是数据对象，即：数据的一个子集

5、数据结构 定义：数据元素相互之间的关系称为结构（是指相互之间存在一种或多种特定关系的数据元素集合，或者说，数据结构是带结构的数据元素的集合） 包括三个方面内容 两个层次 逻辑结构 描述数据元素之间的逻辑关系 与数据的存储无关，独立于计算机 是从具体问题抽象出来的数学模型 物理结构（存储结构） 数据元素及其关系在计算机存储器中的结构（存储方式） 逻辑结构与存储结构的关系： 存储结构是逻辑关系的映像与元素本身的映像

逻辑结构的种类 划分方法一： （1）线性结构（1：1的关系） 有且仅有一个开始和终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继 例如：线性表、栈、队列、串 （2）非线性结构（1：n的关系） 一个结点可能有多个直接前趋和直接后继 例如：树、图 划分方法二： 四类基本逻辑结构： 存储结构的种类 四种基本的存储结构： 顺序存储结构 链式存储结构 索引存储结构 散列存储结构

顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示 C语言中用数组来实现顺序存储结构 链式存储结构： 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 C语言中用指针来实现链式存储结构

如图头指针指向165单元的bat的时候，该位置还存储了130，这个130就是下一个元素的地址，指针就会根据这个130找到130位置的单词cat 索引存储结构： 定义：在存储结点信息 的同时，还建立附加的索引表 方便查找

散列存储结构： 根据结点关键字直接计算出该结点的存储地址