数据结构基础讲义共47页

《数据结构》讲义间存在的关系———产生背景。

1.1 什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。

其中建立数学模型的实质：找出操作对象之间的关系。

例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。

（地位）1.2 数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声音、图象等。

2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。

一个数据元素可由若干个数据项组成（Data Item）。

3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。

由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。

综上1~3所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。

(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。

…}，字母字符数据对象是集合象。

由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

为数据结构的有限集，S是D上关系的有限集。

表示复数的虚部。

存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。

例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

数据结构基础讲义在计算机科学领域中，数据结构是一门极其重要的基础课程。

它就像是一座桥梁，连接着程序设计和算法分析，为我们解决各种实际问题提供了有力的工具。

接下来，让我们一起走进数据结构的世界，探索其中的奥秘。

一、什么是数据结构简单来说，数据结构就是数据的组织方式和存储结构。

我们在编程中处理的数据，比如整数、字符串、数组等，都需要以某种特定的方式进行组织和存储，以便能够高效地进行操作和处理。

打个比方，我们要整理一个书架上的书籍。

如果随意摆放，找书的时候就会很麻烦。

但如果按照一定的规则，比如按照作者的姓氏字母顺序或者书籍的类别进行排列，那么找书就会变得容易很多。

同样的道理，在计算机中，合理的数据结构可以让我们更快地访问、修改和处理数据。

二、常见的数据结构类型1、数组数组是一种最简单、最常见的数据结构。

它是一组具有相同数据类型的元素的有序集合。

在内存中，数组的元素是连续存储的，这使得我们可以通过索引快速访问到特定位置的元素。

例如，如果我们有一个整数数组｀int arr5 ＝｛10, 20, 30, 40, 50}｀，要访问第三个元素，只需要使用｀arr2` 就可以得到 30。

然而，数组也有它的局限性。

一旦数组的大小被定义，就很难动态地改变。

而且，插入和删除元素的操作可能会比较复杂，因为需要移动大量的元素。

2、链表链表则是一种动态的数据结构。

它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表的优点是插入和删除操作相对简单，只需要修改指针即可。

但访问特定位置的元素就没有数组那么高效了，因为需要从头节点开始逐个遍历。

3、栈栈是一种特殊的线性表，它遵循“后进先出”（Last In First Out，LIFO）的原则。

想象一下叠盘子，最后放上去的盘子总是最先被拿走，这就是栈的工作方式。

在程序中，栈常用于函数调用、表达式求值等场景。

4、队列与栈相反，队列遵循“先进先出”（First In First Out，FIFO）的原则。