《计算机科学导论（第二版）》 11章 数据结构

11.1 引言

1、为什么要使用数据结构？

尽管单变量在程序设计语言中被大量使用，但是它们不能有效地解决复杂问题。此时考虑使用数据结构。

2、数据结构是什么？

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

3、三种数据结构

数组；

记录;

链表；

大多的编程语言都隐式实现了前两种，而第三种则通过指针和记录来模拟。

11.2 数组

1、为什么使用数组？

为了处理大量的数据，需要一个数据结构，如数组。当然还有其他的数据结构。

2、数组的定义

数组是元素的顺序集合，通常这些元素具有相同的数据类型。

3、数组的基础知识

1索引

表示元素在数组中的顺序号，顺序号从数组开始计数。

数组元素通过索引被独立给出了地址，使用索引可以访问数组中的元素。

有些现代语言（如C、C++和Java）是从0开始数组索引的。

2数组名与元素名

在一个数组中，有两种标识符：数组的名字（scores）和各个元素的名字（scores[1]、scores[2]）。

3多维数组

许多应用需要数据以多于一维的形式存储。一个常见的例子是表，其是由行和列组成的二维数组。

多维数组（多于二维的数组）也是可以的。

二维数组在内存中可以使用行主序存储或列主序存储，第一种更常见。

4、数组操作

数组操作是值得一些把数组作为数据结构的操作。

常见的数组操作有：查找、插入、删除、检索和遍历

1查找

未排序的数组使用顺序查找。对排序的数组使用折半查找；

2插入（操作冗长和棘手）

语言允许可变长数组的前提（例如，C语言的最新版本）

①尾部的插入

②开始或中间的插入

首先查找数组。找到插入的位置后，插入新的元素。

注意移位需要在数组的尾部进行，以防止元素值的丢失。

3删除（操作冗长和棘手）

需要把需要移动的元素向数组的开始位置移动一个位置。

4检索

检索操作就是随机（注意对随机地理解）地存取一个元素，达到检查或拷贝元素中的数据的目的。

5、数组的应用

当需要进行的插入和删除操作数目较少，而需要大量的查找和检索操作时，数组是合适的数据结构。

11.3 记录

1、为什么要用记录？

记录也是为了处理大量的数据而被需要的一个数据结构。

2、什么是记录？

记录是一组相关元素的集合，它们可能是不同的类型，但整个记录有一个名称。

记录中的数据必须都与一个对象关联。

3、记录的基础知识

1域

记录中的每个元素称为域。域是具有含义的最小命名数据。域不同于变量主要在于它是记录的一部分。

2记录名与域名

就像数组一样，在记录中也有两种标识符：记录的名字student和记录中各个域的名字。

域名（student.id student.name）

11.4 记录与数组

1、记录与数组的比较

数组定义了元素的集合，而记录定义了元素可以确认的部分。

2、记录数组

1什么时候使用记录数组？

如果我们需要定义元素的集合，且同时还需要定义元素的属性，那么可以使用记录数组。

2规则

1、数组的名字定义了整个结构，作为一个整体的学生组。

2、首先定义元素，然后在定义元素的部分（属性），如（student[2]）.id，括号告诉我们索引运算符要先于点运算符。

3、通常使用循环来读记录数组中的数据。

3数组与记录数组

数组可以看成是记录数组的一种特例，其中每个元素是只带一个域的记录。


11.3 链表

1、为什么要用到链表？

记录也是为了处理大量的数据而被需要的一个数据结构。

2、什么是链表？

链表是一个有序数据的集合，其中每个元素（节点）包含下一个元素的地址。链表中的节点是至少包含两个域的记录。

3、链表的基本知识

1元素

习惯上称节点，包含两个部分：数据和链。链包含指明列表中下一个元素的指针（地址）；

2空指针和空链表

3节点间的连线：实心圆和箭头；

4链表名和节点名

①链表名是头指针的名字，该头指针指向表中的第一个节点。

②节点的名字与指向节点的指针有关。不同语言不同。C语言的约定是指向节点的指针称为p，则称节点为*p。这种命名约定隐含一个节点可以有多于一个名字。

4、数组与链表区别

1连接工具：数组是索引，链表是指向下一元素的链（指针或地址）

2在内存中的存储方式：数组是无间隔存储；链表是有间隔存储。

5、链表操作

1搜索链表

链表的搜索算法只能是顺序的。由于链表中的节点没有特定的名字，我们使用两个指针来进行搜索：

pre（先前的）和cur（当前的）。

搜索算法使用一个标记（一个只能取真值或假值的变量），目标找到为真，未找到为假。

2插入节点

在插入链表之前，我们首先要使用搜索算法。如果搜索算法的返回值为假，将允许插入，否则终止算法。因为我们不允许重复值的数据。

①在空表中插入

②在表的开始插入

③在表的末尾插入

④在表中间插入

对list<--new的理解

3删除节点

在插入链表之前，我们首先要使用搜索算法。如果搜索算法的返回值为真（节点找到），我们可以在链表中删除该节点。

①删除首节点

②删除中间或末尾节点

4检索节点

检索就是为了检索或复制节点中的所含数据的目的而随机访问节点。在检索之前也是需要检索的。

检索只使用cur指针。

遍历链表

为了遍历链表我们需要一个步行指针，当指针被处理时，他从一个节点移到另一个节点。

使用循环，步行指针为空的时候，循环终止。

6、链表的应用（与数组应用比较）

如果需要大量的插入和删除，那么链表是合适的数据结构。但是搜索一个链表比搜索一个数组要慢。

11.4 疑问：

为什么没有记录操作？链表为什么是有序的？