跳到主要内容

第 l 章 绪论

1.1 数据结构的研究内容​

image-20220414230225399

【例1.1】 学生学籍管理系统。

诸如此类的线性表结构还有图书馆的书目管理系统、库存管理系统等。在这类问题中，计算机处理的对象是各种表，元素之间存在简单一对一的线性关系，因此这类问题的数学模型就是各 种线性表，施加千对象上的操作有查找、插入和删除等。这类数学模型称为 ＂线性” 的数据结构。

【例1.2】 人机对弈问题。

人机对弈问题的数学模型就是如何用树结构表示棋盘和棋子等，算法是博弈的规则和策略。 诸如此类的树结构还有计算机的文件系统、 一个单位的组织机构等。在这类问题中， 计算机处理的对象是树结构， 元素之间是一对多的层次关系，施加千对象上的操作有查找、插入和删除等。 这类数学模型称为 “树 ” 的数据结构。

［例1.3】 最短路径问题。

最短路径问题的数学模型就是图结构，算法是求解两点之间的最短路径。诸如此类的图结构 还有网络工程图和网络通信图等， 在这类问题中，元素之间是多对多的网状关系，施加于对象上 的操作依然有查找、插入和删除等。这类数学模型称为 “图 ” 的数据结构。

1.2 基本概念和术语​

image-20220414232213807

image-20220414232334420

image-20220414232434595

image-20220414232547265

image-20220414232748726

image-20220414232901187

image-20220414232931688

image-20220414233126979

image-20220414233359301

image-20220414233454608

image-20220414233510559

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

image-20220415094056565

image-20220415094622823

image-20220415094911799

image-20220415095307392

image-20220415095555780

1.1-1.2小结​

image-20220415095935583

image-20220415100023408

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

image-20220416150933479

1.4 算法和算法分析​

image-20220416151608688

image-20220416152310047

1.4.3 算法的时问复杂度​

image-20220416152953282

image-20220416153143860

image-20220416154843050

image-20220416155042723

image-20220416155350385

image-20220416160041713

image-20220416160255692

image-20220416160400399

image-20220416160621358

image-20220416160631942

image-20220416161653806

image-20220416162426586

image-20220417080336229

image-20220417080609226

image-20220417080849642

image-20220417080931024

image-20220417081053727

image-20220417081238941

1.4.4 算法的空问复杂度​

image-20220417081716633

image-20220417082028985

image-20220417082240718