"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“
引言
开始并行学习一下数据结构，基础太重要了，非科班，本科期间也没有学过这些，现在回过来学习。参考青岛大学的王卓老师的资料学习，简单记录一下笔记，方便以后查阅，后续全部学完了，会对笔记进行查缺补漏。
第一章绪论
数据结构的重要性：
程序 = 数据结构 +算法
定义：
数据结构是研究非数值计算的程序设计中计算机的操作对象及它们之间关系和操作的学科。
基本概念术语
-
数据
是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称（集合），数据不仅仅包含整型、实型等数值类型，还包含图形、图像、声音、视频及动画等非数值类型。 -
数据元素
数据的基本单位，在计算机中通常作为一个整体进行考虑和处理 ，也称为元素、记录、节点、顶点。 -
数据项
组成数据元素的、有独立含义的、不可分割的最小单位 。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。 -
数据对象
是性质相同的数据元素的集合，是数据的一个子集。只要集合内元素的性质均相同，都可称之为一个数据对象 。 -
数据结构
数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带”结构＂的数据元素的集合，“结构”就是指数据元素之间存在的关系。
举例
数据、数据元素、数据项三者之间的关系：数据>数据元素>数据项。
例：学生表>个人记录>学号、姓名……
数据两种层次结构
一、逻辑结构
- 定义
从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。 - 种类
（1）线性结构
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。例如：线性表、栈、队列、串。
（2）非线性结构
一个结点可能有多个直接前驱和直接后继。例如：树、图。
一对多，多对多的关系。
另外一种分类标准：
- 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
- 线性结构：结构中的数据元素之间存在着一对一的线性关系。
- 树形结构：结构中的数据元素之间存在着一对多的层次关系。
- 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
二、物理结构（存储结构）
- 定义
数据的逻辑结构在计算机中(内存)的存储形式。 - 种类
（1）顺序存储结构
把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置。(在前面的数据元素就存在前面；在后面的数据元素就存在后面)C语言用数组来实现顺序存储结构。
（2）链式存储结构
用一组任意的存储单元存储数据元素(可能连续也可能不连续)，数据元素之间的逻辑关系用指针来表示(用指针存放后继元素的存储地址)，C语言中用指针来实现链式存储结构。就是存储一个元素本身同时，还存储了下一个元素的地址。
举例：现在如银行、医院等地方，设置了排队系统，也就是每个人去了，先领一个号，等着叫号，叫到时去办理业务或看病。在等待的时候，你爱在哪在哪，可以坐着、站着或者走动，甚至出去逛一圈，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了，下一个就轮到了。
（3）索引存储结构
在存储节点信息的同时，还建立附加索引索引表中的每一项称为一个索引项，索引项的一般形式是：(关键字，地址）关键字是能唯一标识一个结点的那些数据项。
举例：手机通讯录中名字字母排序，点击对应人名即可呼叫对应的号码。
（4）散列存储结构
三、二者的关系
- 存储结构是逻辑关系的映象与元素本身的映象；
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现；
- 两者综合起来建立了数据元素之间的结构关系。
数据类型
- 定义：
数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型=值的集合+值集合上的一组操作
抽象数据类型
-
啥叫抽象
看到了啥？大多数人会说看到的圆，然而这就是抽象。我们看到了他的本质，而去掉了一些非本质的东西，比如大小颜色，线条的粗细，空心还是实心。
那什么是圆呢？
圆是到某个点距离相等的点的集合这个定点就是圆心，距离就是半径，我们就可以描述这个圆的一些相关信息了 。 -
定义
指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。由用户定义，从问题抽象出数据模型（逻辑结构），还包括定义在数据模型上的一组抽象运算（相关操作）不考虑计算机内的具体存储结构与运算的具体实现算法。 -
形式定义
三要素：
1、数据对象 D
2、数据关系 S
3、基本操作 P
具体形式：
ADT 抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT 抽象数据类型名
其中：数据对象、数据关系的定义用伪代码描述；
基本操作的定义格式为：
基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>
①参数表：赋值参数，只为操作提供输入值；引用参数，以&打头，除可提供输入值外，还将返回值操作结果。
②初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。
③操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。
举例：
ADT Circle{
数据对象：D={r,x,y|r,x,y均为实数}
数据关系：R={<r,x,y>|r是半径,<x,y>是圆心坐标}
基本操作：
Circle(&C,r,x,y)
操作结果：构造一个圆。
double Area(C)
初始条件：圆已存在。
操作结果：计算面积。
double Circumference(C)
初始条件：圆已存在。
操作结果：计算周长。
……
}ADT Circle
小结：
借用课程中老师的PPT截图：
抽象数据类型的表示与实现
前面说的一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要实现这个目标，就要把抽象的变成具体的，即抽象数据类型在计算机上实现，变为一个能用的具体的数据类型。
用C语言真正实现抽象数据类型的定义
例如：抽象数据类型“复数”的实现。
下面以计算复数加法、除法为例，我并没有把+-*/都搞出来，太多了，知道两个就可以，王老师课件对应的代码有问题，指针取地址。
#include "stdio.h"
/*结构体定义，对应数据对象、关系*/
typedef struct
{
float real_part; //实部系数
float imaginary_part; //虚部系数
}Complex; //定义复数抽象类
//下面函数就对应数据的基本操作
/* 构造复数*/
void assign (Complex *A,float real,float imaginary)
{
A->real_part = real;
A->imaginary_part = imaginary;
}
/* 复数加法*/
void add(Complex *C,Complex A,Complex B)
{
C->real_part = A.real_part + B.real_part;
C->imaginary_part = A.imaginary_part + B.imaginary_part;
}
/*复数除法*/
void divide(Complex *C,Complex A,Complex B)
{
C->real_part = (A.real_part * B.real_part + A.imaginary_part * B.imaginary_part) / (B.real_part * B.real_part + B.imaginary_part * B.imaginary_part);//实部
C->imaginary_part = (A.imaginary_part * B.real_part - A.real_part * B.imaginary_part) / (B.real_part * B.real_part + B.imaginary_part * B.imaginary_part);//虚部
}
/* 返回复数的虚部*/
float GetReal(Complex A)
{
return A.real_part;
}
/* 返回复数的虚部*/
float GetImag(Complex A)
{
return A.imaginary_part;
}
/*主函数*/
void main()
{
Complex Z1,Z2,C1,C2; //定义局部变量
assign(&Z1,8.0,6.0);//构造复数Z1
assign(&Z2,4.0,3.0);//构造复数Z2
add(&C1,Z1,Z2); //Z1+Z2
divide(&C2,Z1,Z2);//Z1/Z2
printf("+ Result:\n%f\n%f\n",GetImag(C1),GetReal(C1));
printf("÷Result:\n%f\n%f\n",GetImag(C2),GetReal(C2));
}
运行结果：
小结：
虽然说是绪论，但是基本概念比较多，主要还是为我们建立一种思维模式以及铺垫一下这些概念的认识。本节主要记录对应资料前4节的内容，主要强调的是数据结构基本概念的东西，绪论还有后半部分，介绍算法的，下次记录了。
参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
网友评论