数据结构与算法-基础

一、数据结构

1.数据：程序的操作对象、用于描述客观事物。

    特点 ：①可以输入到计算机；②可以被计算机处理。

    1.1数据对象：性质相同的数据元素的集合（类似于数组)；

    1.2数据元素：组成数据对象的基本单元；

    1.3数据项：组成数据元素的基本的基本单元。

2.结构：数据元素之间不是独立的，存在特定的关系，这些关系便是结构。

3.数据结构：指数据对象中的数据元素之间的关系。

数据结构图 程序图

二、逻辑结构（指在数据对象中数据元素之间的相互关系），分为以下四种：

1.集合结构： 集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是"平等"的.。它们的共同属性是：“同属于一个集合”。

结合结构图

2.线性结构：线性结构中的数据元素之间是一对一的关系。常用的线性结构有：线性表，栈，队列，双队列，数组，串。

线性结构图

3.树形结构：重要的非线性数据结构。树形数据结构可以表示数据表素之间一对多的关系.树型结构中的数据元素之间存在一种一对多的层次关系。常见的树形结构: 二叉树,B树,哈夫曼树,红黑树等。

树形结构

4.图形结构：图形结构的数据元素是多对多的关系. 常见的图形结构: 邻近矩阵,邻接表。

图形结构图

三、物理结构（指的是数据的逻辑结构在计算机的存储形式），分为以下两种：

1.顺序存储结构：是指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

    解读：这样的存储方式，实际非常简单。可以理解为排队占位。 按照顺序，每个一段空间.。我们所学习且使用的数组就是典型顺序存储结构。当你在计算机建立一个有6个整型数据的数组时，计算机便在内存中找到一片空地。按照一个整型所占空间大小乘以6，开辟一段连续的内存空间，然后将数据依顺序放在位置上，依次排放。

顺序存储结构图

2.链式存储结构：是把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的.。数据元素的存储关系并不能反映逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关关联数据元素的位置。

链式存储结构图

总结：逻辑结构是面向问题的，而物理结构就是面向计算机的， 其基本的目标就是将数据以及逻辑关系存储到计算机的内存中。

四、线性表的顺序表示与实现

1.线性表的顺序存储表示

线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素,这种表示也称为线性表的顺序存储结构或顺序映像. 通常,称这种存储结构的线性表为顺序表(Sequential List). 其特点是, 逻辑上相邻的数据元素,其物理次序也是相邻的。

线性表的结构设计图

2.顺序表的基本操作实现

   2.1初始化

顺序表的初始化方法

   2.1.1main函数调用

main函数调用

   2.1.2结果显示

初始打印结果

2.2插入

顺序表的插入

   2.2.1main函数调用

main函数调用

   2.2.2结果显示

插入数据打印结果

2.3取值

顺序表取值

2.4删除

顺序表删除

2.5顺序表清空

顺序表清空

2.6判断顺序表清空

判断顺序表清空

2.7顺序表查找元素并返回

查找元素返回

五、线性表链式存储

1.前插法创建链表

前插法

2.后插法创建链表

后插法

PS：不管是前插法还是后插法：都是先处理要插入的结点（要插入的的结点需要一个指针域next去指向它，防止丢失），再更新新结点的指针域next的指向，最后更新首元结点的指向或者表尾终端结点的指向。