数据结构知识点总结归纳整理.docxVIP

第1章绪论

1.1数据结构的基本概念

数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型是一个值的集合和定义在此集合上一组操作的总称。

原子类型：其值不可再分的数据类型

结构类型：其值可以再分解为若干成分（分量）的数据类型

抽象数据类型：抽象数据组织和与之相关的操作

抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。

#关键词：数据，数据元素，数据对象，数据类型，数据结构

数据结构的三要素：

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。

数据的运算：包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2算法和算法评价

算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。一个算法有零个或多个的输入，有一个或多个的输出。

时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。一般指最坏情况下的时间复杂度。

空间复杂度定义为该算法所耗费的存储空间。算法原地工作是指算法所需辅助空间是常量，即O(1)。

第2章线性表

2.1线性表的定义和基本操作

线性表是具有相同数据类型的n个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构。两者属于不同层面的概念，因此不要混淆。

2.2线性表的顺序表示

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

顺序表最主要的特点是随机访问（随机存取），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。但插入和删除操作需要移动大量元素。

顺序表的存储密度高，每个结点只存储数据元素。

顺序表插入操作：

最好情况：在表尾插入，元素后移语句不执行，时间复杂度为O(1)

最坏情况：在表头插入，元素后移语句将执行n次，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

顺序表删除操作：

最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)

最坏情况：删除表头元素，需要移动除第一个元素外的所有元素，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

顺序表按值查找（顺序查找）：

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)

最坏情况：查找的元素在表尾或不存在时，需要比较n次，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

2.3线性表的链式表示

链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，对线性表的插入和删除不需要移动元素，只需要修改指针。

单链表是非随机存储的存储结构，即不能直接找到表中某个特定的结点。

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。

采用头插法建立单链表：从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

读入数据的顺序与生成的链表中元素的顺序是相反的。

每个结点插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)。

采用尾插法建立单链表：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

时间复杂度和头插法相同。

按序号查找结点值：在单链表中从第一个结点出发，顺指针next域逐个往下有哪些信誉好的足球投注网站，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

时间复杂度为O(n)。

按值查找表结点：从单链表第一个结点出发，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回