数据结构和算法——绪论

一、绪论

1.1 数据结构的研究内容

        1、数据的各种逻辑结构和物理结构（存储结构），以及它们之间的相应关系

        2、对每种结构定义相适应的各种运算

        3、设计出相应的算法

        4、分析算法的效率

1.2 基本概念和术语

1.2.1 数据、数据结构、数据项和数据对象

 举个例子说明：假设有两张表，上表为人员表，下表为课程表，表的格式如下：

这两张表就是数据

而单独的一张表就是数据对象， 即人员表和课程表都是一个数据对象，而每张表的每一行就是数据元素。而姓名、身高、课程代号、性别就是数据项，是最小的不可分割的最小单位。

1.2.2 数据结构

数据结构包括逻辑结构和物理结构（存储结构）两个层次。

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。

a、逻辑结构

逻辑结构是分为四种类型：集合结构、线性结构、树形结构、图结构

集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。

 线性结构：类似于线性关系，线性结构中的数据元素之间是一对一的关系。

 树形结构：树形结构中数据元素之间存在一对多的关系。（各元素及元素关系所组成图形类似于树状图）。

 图形结构：数据元素之间是多对多的关系。如下图所示。

 总结：逻辑结构是独立于计算机的，总体可以划分为线性结构和非线性结构，其中线性结构是指每个元素都有且仅有一个前驱和后继，而非线性结构是一个结点可能有多个直接前驱和多个直接后继。

b 存储结构（物理结构）

物理结构又叫存储结构，分为四种:顺序存储结构、链式存储结构、索引存储结构、散列存储结构，主要关注于前面两种存储结构。

（1）顺序存储结构

顺序存储结构就是把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。之前学习的数组就是一种顺序存储结构，（如下图所示）

（2）链式存储结构

链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。根据指针找出相邻元素的位置。

 

 1.2.3 数据类型和抽象数据类型

a、数据类型

一般包括整型，实型、字符型等基本类型外、还有数组、结构体和指针等构造数据类型。

b、抽象数据类型（Abstract Data Type,ADT）

类似于C语言中的结构体和C++、Java中的类。

通俗的讲，抽象数据类型，泛指除基本数据类型以外的数据类型。

1.3 抽象数据类型的表示与实现

抽象数据类型的概念与面向对象的思想是一致的。

1.4 算法和算法分析

程序 = 数据结构 + 算法

1.4.1 算法的定义及特性、

算法是为了解决某类问题而规定的一个有限长的操作序列。

一个算法必须满足以下5个重要特性：有穷性、确定性、可行性、输入、输出、

1.4.2 评价算法优劣的基本标准

正确性、可读性、健壮性（鲁棒性）、高效性

1.4.3 算法的时间复杂度

详细可看这个：(5条消息) 一套图 搞懂“时间复杂度”_12 26 25的博客-CSDN博客_时间复杂度

看以下代码的时间复杂度：

 最好、最坏和平均时间复杂度

1.最好时间复杂度：指的是算法计算量可能达到的最小值

2.最坏时间复杂度：指的是算法计算量可能达到的最大值。

3.平均时间复杂度：是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值

1.4.4 算法的空间复杂度

空间复杂度只需要分析辅助变量所占的额外空间。一个算法的空间包括算法本身占用的空间以及辅助空间。

空间复杂度：S（n）= O(f(n))

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O（1）

举个例子

int i = 1;
int j = 1;
++i;
++j;
int m = i+j;

代码中的i，j，m所分配的空间不能随着处理数据量的变化，因此它的空间复杂度S（n） = O（1）

我们再看一个代码：

int []m = new int[n];
    for (i = 1; i <= n; ++i) {
        j = i;
        j++;
    }

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-5行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

第一章 总结

数据、数据对象和数据元素、数据项的关系如下

 

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，同样是结构，从不同角度来讨论，会有不同的分类，如下图所示

 

算法是为了解决某类问题而规定的一个有限长的操作序列。

算法具有五个特性：有穷性、确定性、可行性、输入和输出

算法分析的重点方面是分析算法的时间复杂度和空间复杂度。