数据结构与算法（快速基础C++版）

1. 基本概念

“ 程序 = 数据结构 + 算法 ”
数据结构通过算法实现操作，算法根据数据结构设计程序
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科

第1章 绪论

1.1 数据结构的研究内容

通常用计算机解决一个问题的步骤，就是：
1.将具体问题抽象为数学模型；2.设计算法；3.最后进行编程、调试与运行。
那抽象数学模型的实质就是：分析问题、提取操作对象、找出操作对象之间的关系并用数学语言描述出来。
操作对象与操作对象之间的关系就是我们说的：数据结构
随着计算机应用领域的扩展，计算机被越来越多地用于非数值计算。描述非数值计算问题的数学模型不是数值计算的数学方程，而是诸如表、树和图之类的具有逻辑关系的数据。
比如：我们常见的学生教务管理系统。操作对象：每位学生的信息(学号、姓名、性别、籍贯、专业.….)。操作算法：查询、插入、修改、删除等。操作对象之间的关系：线性关系，数据结构：线性数据结构、线性表。

换句话说：
是指相互之间存在一种或多种特定关系的数据元素的集合；
或者说，数据结构是带结构的数据元素的集合。

1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象

1.数据
是能输入计算机且能被计算机处理的各种符号的集合。是信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工。
包括：
数值型的数据：整数、实数等
非数值型的数据：文字、图像、图形、声音等
2.数据元素
是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也简称为元素，或称为记录、结点或顶点。

3.数据项
构成数据元素的不可分割的最小单位。

关系：
数据 > 数据元素 > 数据项
例：学生表 > 个人记录 > 学号、姓名…

4.数据对象
是性质相同的数据元素的集合，是数据的一个子集。
例如：
整数数据对象是集合N={0，±1，±2，……}
字母字符数据对象是集合C={‘A’，‘B’，…,‘Z’}
学籍表也可看作一个数据对象
区别：
数据元素：组成数据的基本单位。与数据的关系:是集合的个体
数据对象：性质相同的数据元素的集合。与数据的关系是：集合的子集

1.2.2 数据结构

数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构（Structure）。是指相互之间存在一种或多种特定关系的数据元素集合或者说，数据结构是带结构的数据元素的集合
数据结构包括以下三个方面的内容：
1.数据元素之间的逻辑关系，也称为逻辑结构。
2.数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或数据的存储结构
3.数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。
逻辑结构
1.描述数据元素之间的逻辑关系。
2.与数据的存储无关，独立于计算机。
3.是从具体问题抽象出来的数学模型。
划分方法一：
(1）线性结构
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
例如:线性表、栈、队列、串
(2）非线性结构
一个结点可能有多个直接前趋和直接后继
例如:树、图
划分方式二：四类基本逻辑结构
(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。
(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。
(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
物理结构(存储结构)
1.数据元素及其关系在计算机存储器中的结构（存储方式)。
2.是数据结构在许算机中的表示。
四种基本的存储结构：
1.顺序存储结构
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
C语言中用数组来实现顺序存储结构。

2.链式存储结构
用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
C语言中用指针来实现顺序存储结构。

3.索引存储结构
在存储结点信息的同时，还建立附加的索引表。
4.散列存储结构
根据结点的关键字直接计算出该结点的存储地址。

逻辑结构与存储结构的关系：
1.存储结构是逻辑关系的映象与元素本身的映象。
2.逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
3.两者综合起来建立数据元素之间的结构关系。

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

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。
例如，C语言中:
·提供int,char, float, double等基本数据类型
·数组、结构、共用体、枚举等构造数据类型，还有指针、空(void)类型
·用户也可用typedef自己定义数据类型
一些最基本数据结构可以用数据类型来实现，如数组、字符串等;
而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。
例如，C语言中定义变量i为int类型，就表示i是[-min,max]范围的整数，在这个整数集上可以进行+、-、*、%等操作
数据类型的作用：
1.约束变量或常量的取值范围。
2.约束变量或常量的操作。
定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型 = 值的集合 + 值集合上的一组操作

抽象数据类型(Abstract Data Type，ADT)
是指一个数学模型以及定义在此数学模型上的一组操作。

1.由用户定义,从问题抽象出数据模型（逻辑结构)
2.还包括定义在数据模型上的一组抽象运算(相关操作)
3.不考虑计算机内的具体存储结构与运算的具体实现算法

1.2.4 概念小结

1.3 算法和算法分析

算法的定义：
对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

算法的描述 ：
自然语言：英语、中文

流程图：传统流程图、NS流程图

伪代码：类语言：类C语言
程序代码：C语言程序、JAVA语言程序…
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以多种算法。
程序是用某种程序设计语言对算法的具体实现。
算法的特性 ：
一个算法必须具备以下五个重要特性：
1.有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
2.确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
3.可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
4.输入：一个算法有零个或多个输入。
5.输出：一个算法有一个或多个输出。
算法设计的要求：
1.正确性(Correctness)
2.可读性(Readability)
3.健壮性(Robustness)
4.高效性(Efficiency)
一个好的算法首先要具备正确性，然后是健壮性，可读性；
主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。
算法效率以下两个方面来考虑:
1.时间效率：指的是算法所耗费的时间;
算法运行时间 = 一个简单操作所需的时间 × 简单操作次数
所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。

2.空间效率：指的是算法执行过程中所耗费的存储空间。
时间效率和空间效率有时候是矛盾的。

1.4 总结

设计一个好的算法的过程：

2. 基本的数据结构

第2章 线性表

2.1 线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列。



同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。
从以上例子可看出线性表的逻辑特征是：
1.在非空的线性表，有且仅有1个开始结点a1，它没有直接前趋，而仅有一个直接后继az；
2.有且仅有一个终端结点an，它没有直接后继，而仅有1个直接前趋an-1;
3.其余的内部结点ai(2≤i≤n-1)都有且仅有1个直接前趋ai-1和1个直接后继ai+1。

2.2 案例引入

案例2.1 一元多项式的运算

案例2.2 稀疏多项式的运算

顺序存储结构存在问题：
1.存储空间分配不灵活，比如两个多项式相加，最少的情况下相加为0，C数组不分配空间；最多的清空下相加为7项，C数组分配7个内存空间。
2.运算的空间复杂度高
采用链式存储结构，可以灵活解决上述问题。

案例2.3 图书信息管理系统

总结

1.线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
2.许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单
独编写一个程序。
3.从具体应用中抽象出共性的逻辑结构+基本操作(就是抽象数据类型)，然后实现其存储结构和基本操作。

2.3 线性的类型定义

这里的类型就是抽象数据类型：数据对象、数据对象之间的关系集合、作用在这个数据对象上的基本操作。

2.3.1 基本操作（一）：初始化空表、销毁表、清空表

2.3.2 基本操作（二）：判断表为空、返回表长

2.3.3 基本操作（三）：查找某个元素、查找某个符合条件的元素

2.3.4 基本操作（四）：查找前驱、查找后继

2.3.5 基本操作（五）：插入

2.3.6 基本操作（六）：删除、遍历

总结

以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节、只有待确定了存储结构之后才考虑。

2.4 线性表的顺序表示和实现

2.4.1 多项式的顺序存储结构类型定义

2.4.2 图书表的顺序存储结构类型定义

2.4.3 数组定义的补充

2.4.4 代码实例

2.4.4.1 线性表的初始化

// 线性表的定义
// 其实就是构造结构体：数组+长度
struct SqList
{
	ElemType* elem;  //顺序线性表的表头
	// 也可以这样定义，但是是数组静态分配，上述是动态的，因为可以使用指针指向数组首地址
	//ElemType elem[MAX_SIZE];  
	int length;      //顺序线性表的长度
};
// 线性表的初始化
bool InitList(SqList& L)
{
	L.elem = new ElemType[MAXSIZE];  // //在堆区开辟内存
	if (!L.elem)
	{
		return false;
	}
	L.length = 0;  //设定空表长度为0
	return 1;
}

2.4.4.2 线性表的销毁

// 线性表的销毁
void DestroyList(SqList& L)
{
	if (L.elem)
	{
		delete L.elem;
	}
}

2.4.4.3 线性表的清空

// 线性表的清空
void CLearList(SqList& L)
{
	L.length = 0;
}

2.4.4.4 线性表的长度

// 线性表的长度
int GetLength(SqList& L)
{
	return L.length;
}

2.4.4.5 判断线性表为空

// 判断线性表是否为空
bool IsEmpty(const SqList& L)
{
	// static_cast<bool>(L.length) 的作用是将 L.length 的值转换为布尔值 (bool)。
	return static_cast<bool>(L.length);
}

2.4.4.6 线性表取值

// 线性表取值
// 随机存取的时间复杂度是：O(1)
bool GetELem(const SqList &L, const size_t i, ElemType &e)
{
    if (i < 1 || i > MAXSIZE)
    {
        cerr<<"out of range"<<endl;
        return false;
    }
    e = L.elem[i-1];
    return true;
}

2.4.4.7 线性表的顺序查找

// 线性表的查找
// 顺序查找的时间复杂度是：O(n)
int LocateList(const SqList& L, const ElemType& e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e)
		{
			return i + 1;  //查找成功，返回下标值
		}
	}

	return 0;  // 查找失败，返回0
}

2.4.4.8 线性表的插入

// 线性表的插入
// 顺序存储的插入的时间复杂度是：O(n)
bool InsertList(SqList& L, const ElemType& e, const int& i)
{
	if (i < 1 || i > L.length)
	{
		return false;  // i值不合法
	}
	if (L.length == MAXSIZE)
	{
		return false;  // 当前存储空间已满
	}
	// 将位于插入位置之后的元素依次向后挪动一位
	for (int j = L.length - 1; j >= i - 1; j--)
	{
		L.elem[j + 1] = L.elem[j];
	}

	// 插入元素
	L.elem[i - 1] = e;
	// 线性表长度+1
	L.length++;

	return true;
}

2.4.4.9 线性表的删除

// 线性表的删除
// 顺序存储的删除的时间复杂度是：O(n)
bool EraseList(SqList& L, const int& i)
{
	if (i < 1 || i > L.length)
	{
		return false;  // i值不合法
	}

	// 从要删除的i位置开始遍历
	// 也就是将位于删除位置之后的元素依次向前移一位
	for (int j = i; j < L.length; j++)
	{
		L.elem[j - 1] = L.elem[j];
	}

	// 线性表长度-1
	L.length--;

	return true;
}

2.4.4.10 总结

(1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
(2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
这种存取元素的方法被称为随机存取法
时间复杂度
1.查找、插入、删除算法的平均时间复杂度为O(n)
就是求次数，比如查找，就是在第几个位置需要的查找次数的累加和 / 元素个数。
比如插入，就是在第几个位置插入需要移动元素个数的累加和 / n种可能。
比如删除，就是在第几个位置删除需要移动元素个数的累加和 / n种可能。
空间复杂度
2.显然，顺序表操作算法的空间复杂度S(n)=O(1) (没有占用辅助空间)
优点：
1.存储密度大(结点本身所占存储量 / 结点结构所占存储量，是1：1)
2.可以随机存取表中任一元素
缺点：
1.在插入、删除某一元素时，需要移动大量元素
2.浪费存储空间
3.属于静态存储形式，数据元素的个数能自由扩充

2.5 线性表的链式表示和实现

简化操作：

首元结点处理：如果链表没有头结点，处理链表的第一个节点（比如插入或删除操作）需要特殊处理，因为没有前驱节点。使用头结点后，第一个节点也有前驱节点（即头结点），这样所有节点的处理方式一致，无需对第一个节点做特殊处理。
统一空表和非空表的处理：

空表处理：没有头结点时，链表为空时，头指针为 nullptr，这需要单独检查。使用头结点时，链表的头指针始终指向头结点，无论链表是否为空，操作上都可以统一处理。这避免了对空表和非空表进行不同处理的复杂性。

链表（链式存储结构)的特点：
(1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
(2）访问时只能通过头指针进入链表并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第1个结点和最后1个结点所花费的时间不等

2.5.1 单链表的代码实例

2.5.1.1 单链表的初始化（带头结点的单链表）

// 单向链表的定义
struct Lnode
{
	ElemType data;  //结点的数据域 
	Lnode* next;    //结点的指针域, 因为指针还是指向下一结点，结点类型就是Lnode
};
// typedef 都是常用来创建类型别名的工具。
// 将 Lnode * 这个指针类型定义为 LinkList，使得代码更简洁易读。
typedef Lnode* LinkList;  

// 链表的初始化
bool InitList(LinkList& L)
{
	// LinkList& L = Lnode* L，L其实是Lnode类型的指针
	// 表示头指针
	L = new Lnode;  // 在堆区开辟一个头结点，结点的数据类型为Lnode
	//L->next = NULL;  // 空表，也就是说头结点的指针指向为空
	L->next = nullptr;  // // 使用 C++11 的 nullptr，类型安全
	return 1;
}

2.5.1.2 判断单链表为空

// 判断链表是否为空
bool IsEmpty(const LinkList& L)
{
	if (L->next)
	{
		// 非空
		return false;
	}
	else
	{
		// 为空
		return true;
	}
}

2.5.1.3 单链表的销毁

// 单链表的销毁
void DestroyList(LinkList& L)
{
	LinkList p;
	while (L)
	{
		// 就是定义1个指针p指向头结点，然后将头指针指向下一个结点，并删除当前p指向的结点
		p = L;
		L = L->next;
		delete p;
	}
}

2.5.1.4 单链表的清空

// 单链表的清空
void CLearList(LinkList& L)
{
	LinkList p, q;
	p = L->next;
	while (p)  // p非空，表示还没到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = nullptr;  // 头结点指针域为空
}

2.5.1.5 单链表的表长

// 单链表的长度
int GetLength(LinkList& L)
{
	LinkList p;
	p = L->next;  // 将p指向首元结点 
	int i = 0;  // 计数
	while (p)
	{
		// 遍历单链表,统计结点数
		i++;
		p = p->next;
	}
	return i;
}

知识回顾

2.5.1.6 单链表的取值

// 单链表的取值
bool GetElem(const LinkList& L, const int& i, const ElemType& e)
{
	LinkList p = L->next; 
	int j = 1; // 计数器
	while (p && i > j)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i) return false; // 第i个元素不存在
	e = p->data;
	return true;
}

2.5.1.7 单链表的查找

// 单链表的按值查找，返回L中值为e的数据元素的地址
// 时间复杂度：0(n)
LinkList LocateElem(LinkList& L, ElemType& e)
{
	// 在线性表L中查找值为e的数据元素
	// 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
	LinkList p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}

// 单链表的按值查找，返回L中值为e的位置序号
int LocateElem(LinkList& L, ElemType& e)
{
	// 返回L中值为e的数据元素的位置序号，查找失败返回
	LinkList p = L->next;
	int j = 1;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
	{
		return j;
	}
	else
	{
		return 0;
	}
}

2.5.1.8 单链表的插入

// 单链表的插入
// 时间复杂度：0(1)
bool InsertList(LinkList& L, const int& i, const ElemType& e)
{
	LinkList p = L;
	int j = 0;
	while (p && j < i -1)  // 寻找第i - 1个结点, p指向i - 1结点
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return 0;  // i大于表长+1或者小于1，插入位置非法
	}

	// 生成新结点s，将结点s的数据域置为e
	LinkList s = new Lnode;
	s->data = e;

	// 将结点s插入L中
	s->next = p->next;
	p->next = s;
}

2.5.1.9 单链表的删除第i个结点

// 单链表的删除
// 将单链表L中第i个数据元素删除
// 时间复杂度：0(1)
bool EraseList(LinkList& L, const int& i, const ElemType& e)
{
	LinkList p = L, q;
	int j = 0;
	while (p && j < i - 1)  // 寻找第 i 个结点的前驱

	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		return 0;  // 删除位置不合理
	}
	q = p->next;  // 临时保存被删结点的地址以备释放
	p->next = q->next; // 改变删除结点前驱结点的指针域
	e = q->data;
	delete q;
	return true;
}

2.5.1.10 单链表头插法

头插法是倒序插入，先插入An，再是An-1，直到A1；而尾插法是正序，先插A1，再一直到An。

// 单链表的头插
// n表示结点个数
// 算法时间复杂度：O(n)
void CreatListHead(LinkList& L, int n)
{
	L = new Lnode;
	L->next = nullptr;  // 先建立一个带头结点的单链表

	for (int i = 0; i < n; i++)
	{
		LinkList p = new Lnode;
		cin >> p->data; // 输入元素值
		p->next = L->next;  // 插入到表头
		L->next = p;
	}
}

2.5.1.11 单链表尾插法

// 单链表的尾插
// 算法时间复杂度：O(n)
void CreatListTail(LinkList& L, int n)
{
	L = new Lnode;
	L->next = nullptr;
	LinkList r = L;  // 尾指针r指向头结点

	for (int i = 0; i < n; i++)
	{
		LinkList p = new Lnode;
		cin >> p->data;  // 生成新结点，输入元素值
		p->next = nullptr;
		r->next = p; // 插入到表尾
		r = p; // r指向新的尾结点
	}
}

总结

2.5.2 循环链表的代码实例

2.5.2.1 循环链表的合并

 // 两个链表的合并
 // 算法时间复杂度：O(1)
LinkList ConnectList(LinkList& Ta, LinkList& Tb)
{
	// 假设Ta、Tb都是非空的单循环链表

	LinkList p = Ta->next;  // ①p存表头结点
	Ta->next = Tb->next->next;  // ②Tb表头连结Ta表尾
	delete Tb->next;  // ③释放Tb表头结点
	Tb->next = p;  // ④修改指针
	return Tb;
}

总结

1.单链表使用头指针，比较方便；而单循环链表中，使用尾指针，比较方便。
2.单链表必须通过头指针逐个遍历访问每个结点，而单循环链表可以通过任意一个结点出发。

2.5.3 双向链表的代码实例

如果是双向链表，头结点的prior域和尾结点的next域为空；而如果是双向循环链表，头结点的prior域指向尾结点和尾结点的next域指向头结点。空表，则都是指向空。

2.5.3.1 双向链表的插入

// 双向链表的定义
// 首先定义了一个结构体 DuLnode，然后通过 typedef 定义了一个指向该结构体的指针类型 DuLinkList。
// 这里 typedef 的部分只定义了 DuLnode* 的别名 DuLinkList，而 DuLnode 是单独的结构体定义。
typedef struct DuLnode
{
	ElemType data;  //结点的数据域 
	DuLnode* prior, * next;    
}*DuLinkList;


// 双向链表的初始化
void InitList(DuLinkList& L)
{
	L = new DuLnode;  
	L->prior = nullptr;  
	L->next = nullptr;  
}

// 双向链表的第i个位置插入元素
bool InsertList(DuLinkList& L, const int& i, const ElemType& e)
{
	// 在带头结点的双向循环链表L中第i个位置之前插入元素e
	DuLinkList p = L->next;
	int j = 1;
	while (p->next && j < i)  // 移动指针到i处
	{
		p = p->next;
		j++;
	}
	if (j < i || j < 1)
	{
		return 0;  // i大于表长插入位置非法
	}

	//在堆区创建要插入的结点
	DuLinkList s = new DuLnode;
	s->data = e;

	// 重新建立链接关系, 将结点s插入链表中
	s->prior = p->prior;  //第一步：s的前趋等于p的前趋
	p->prior->next = s;  //第二步，用p的前趋结点的next指向插入元素s，更改了第一条链
	s->next = p;        //第三步：s的后继指向p
	p->prior = s;       //第四步：p的前趋改为指向s，更改了第二条链
	return true;

}

2.5.3.2 双向链表的删除

// 双向链表的删除某个元素
bool ListErase_DuL(DuLinkList& L, const int& i, const ElemType& e)
{
	DuLinkList p = L->next;
	int j = 1;
	while (p && j < i)  // 寻找第i个结点，并令p指向其前驱
	{
		p = p->next;
		j++;
	}
	if (j < i || j < 1)
	{
		return 0;  // i大于表长插入位置非法
	}
	p->prior->next = p->next;
	p->next->prior = p->prior;
	delete p;
	return true;
}

2.6 顺序表和链表的比较

2.7 线性表的应用

2.8 案例分析与实现

第3章 栈和队列

第4章 串

第5章 树

第6章 图

3. 基本的数据处理技术

第7章 查找技术

第8章 排序技术