数据结构与算法学习（1）——绪论

Q：为什么要学习数据结构？

A：私认为，研究数据结构的目的是为了设计出更高效的算法。       

目录

引言      

基本概念和术语

定义

抽象数据类型

参考资料

引言      

        通过学习数学建模的经历告诉我们：要解决具体的实际问题首先要建立抽象的数学模型，而建立抽象数学模型的第一步就是数据预处理并建立各个变量之间的关系，例如传染病模型（常微分方程）等可以通过建立相关变量的数学方程得到模型结果。然而，并非所有数学模型都能得到相应的数学方程（一般称为非数值计算问题），这时就需要运用数据结构相关知识来建立数学模型。

        下面来看三个不同的例子：

        例1：书目自动检索系统

        书目文件：

        按书名检索：

        按作者名：

        按分类号：

        书籍的信息记录形成一个线性序列，也称作为线性表结构。

        例2：人机对弈

        人机对弈问题的数学模型就是如何用树结构表示棋盘和棋子等，算法是博弈的规则和策略。

        有兴趣的话可以阅读人工智能方面的书（我忘记我看的是哪本了），里面一定会有关于博弈树的系统解释。

        例3：最短路径问题

        问题：现有一个人要从v1出发，经过这个交通网到达v6，要寻求总路程最短的线路。

        （下图来自于网络）

        每条线段旁边的数字表示距离（权重）。

        现在求从v1到v6的最短路径，解决方法就是把这类问题抽象为图的最短路径问题，使用matlab创建图，见下图。

        再找出有向图中每对节点之间的最短路径，结果如下：

        得到最短路径是10（可以验证过程如下1-2、2-3、3-5、5-6；3+1+1+5=10）

        有兴趣的话可以用matlab输入以下代码

 clc,clear
 w = zeros(6);
 %（起点，终点）=权重值
 w(1,2)=3;w(1,3)=5;w(2,3)=1;w(2,4)=6;w(3,4)=4;
 w(3,5)=1;w(5,4)=2;w(4,6)=3;w(5,6)=6;
 %构建稀疏矩阵
 g = sparse(w);
 %创建并查看有向图
 view(biograph(g,[],'ShowWeights','on'))
 %找出有向图中每对节点之间的所用最短路径
 graphallshortestpaths(g)

        最短路径问题的数学模型就是图结构，算法是求解两点之间的最短路径。

        从上面三个例子可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。

基本概念和术语

定义

• 数据：所有能输入到计算机中去的描述客观事物的符号，包括字符串、图形、图像、声音及动画等通过特殊编码定义后的数据。

• 数据元素：数据的基本单位，也称节点或记录，例如书籍记录，棋盘状态，图中的顶点。

• 数据项：有独立含义的数据最小单位，也称域，例如书籍名字、作者、编号。

• 数据对象：相同特性数据元素的集合，是数据的一个子集，包括多个数据项组成的复合数据元素（书籍表）的集合。

• 数据结构：数据元素和数据元素关系的集合。

根据数据元素间关系的基本特性，有四种基本数据结构

        1.集合：数据元素间除“同属于一个集合”外，无其它关系

        2.线性结构：一个对一个，如线性表、栈、队列

        3.树形结构：一个对多个，如树

        4.图状结构：多个对多个，如图 

存储结构分为：

        1.顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系

        2.链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系

h（节点）

h

h

h

h

1345

元素1

1400

元素2

1536

元素3

1356

元素4

存储地址	存储内容	指针
1345	元素1	1400
1356	元素4
......	......	......
1400	元素2	1536
......	......	......
1536	元素3	1356

数据结构形式定义：

        数据结构是一个二元组：

        D：数据元素的有限集合

        R：是D上关系的有限集合

例：复数是一种数据结构，给复数定义：

                  为实数的集合

                            P是定义在集合C上的一种关系

                有序偶对，为实部，为虚部

抽象数据类型

抽象数据类型可用三元组表示：（D，R，P）
        D：数据对象，是性质相同的数据元素的集合；
        R：D上的关系；
        P：对D的基本操作集。

以复数为例子：

//表示部分
typedef struct         //复数类型
{
    float Realpart;    //实部
    float Imagepart;   //虚部
}Complex

//实现部分
void Create( &Complex C,float x,float y)
{   //构造一个复数
    C.Realpart = x;
    C.Imagepart = y;
}
float GetReal(Complex C)
{   //取复数C=x+yi的实部
    return C.Realpart;
}
float GetImag(Complex C)
{   //取复数C=x+yi的虚部
    return C.Imagepart;
}
Complex Add(Complex C1, Complex C2)
{   //求两个复数C1和C2的和sum
    Complex sum;
    sum.Realpart = C1.Realpart + C2.Realpart;
    sum.Imagepart = C1.Imagepart + C2.Imagepart;
    return sum;
}
Complex Sub(Complex C1, Complex C2)
{   //求两个复数C1和C2的差difference
    Complex difference;
    difference.Realpart = C1.Realpart - C2.Realpart;
    difference.Imagepart = C1.Imagepart - C2.Imagepart;
    return difference;
}

参考资料

1.数据结构（C语言版）（第2版）

2.张合生：数据结构与算法2022  01绪论.pptx