绪论
数据结构相关的概念
基本概念和术语
集合：是无法精准定义的基本概念，通常认为集合就是若干具有共同可辨特征的事务的聚合，其中每个事物称为集合的元素或成员。
数据：是对客观信息的一种描述，它是由能被计算机识别与处理的数值、字符等符号构成的集合。
数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素可以是不可分割的原子，也可由若干个款项组成，其中每个款项被称为一个数据项，又称为组合项，否则被称为原子项。
关键码：是数据元素中能起识别作用的数据项，其中能起唯一标识作用的关键码称为主关键码，反之称为次关键码。
关系：指的是集合中元素之间的某种相关性。{<老师，学生>}表示老师和学生之间的关系，{<王二，李四>，<李四，张三>}表示王二、李四、张三他们之间的关系
数据结构
若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为数据结构，换句话说数据结构是带结构的数据元素的集合。
数据结构包括逻辑结构和物理结构两个层次。
逻辑结构
线性结构：指的是数据元素之间存在着一对一的线性关系的数据结构
树形结构：指的是数据元素之间存在着一对多的树形关系的数据结构
图状或网状结构：指的是数据元素之间存在着多对多的网络关系的数据结构
纯集合结构：指的是在数据元素之间除了同属一个集合之外，别无其他关系
存储结构
顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定关系来表示数据元素之间的逻辑关系。
链式存储结构：用附加的“指针”表示数据元素之间的逻辑关系，称为链式存储结构。
数据类型和抽象数据类型
抽象数据类型：是一个数据结构加上定义在这个数据结构上的一组操作。
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
算法及其描述和分析
算法
算法是对问题求解过程中的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。
算法的特征：有穷性、确定性、可行性、有输入、有输出
算法的目标：正确性、可读性、健壮性、高效率和低存储需求
算法的描述
预定义常量和类型
常量说明采用C++语言规范
//函数结果主要状态代码
const TRUE=1;
const FALSE=0;
const OK=1;
const ERROR=0;
const INFEASIBLE=-1;
const OVERFLOW=-2;
//status是函数返回值类型，其值是函数结果状态代码
tyedef int status;
//布尔类型
enum bool{TRUE,FALSE};数据结构的表示
数据结构的表示都用类型定义(typedef)的方式描述。基本元素类型约定为ElemType，由用户在使用该数据类型时再自行具体定义
基本操作的算法都用以下形式的函数描述
函数类型 函数名(函数参数表){
//算法说明
//语句序列
}//函数名除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言abcde等用作数据元素名；ijklmn等用作整形变量名；pqr等用作指针变量名。当函数返回值为函数状态代码时，函数定义为status类型
为了便于算法描述，在形参表中，以&开头的参数即为引用参数。引用参数能被函数本身更新参数值，可以作为输出数据的管道。
//参数表中的某个参数允许预先用表达式的形式赋值，作为默认值使用，以简化参数表
函数类型 函数名(类型1 参数1,类型2 参数2=算术表达式);
//在调用时可以是
函数名(实参数1); //实参数2使用默认值
或
函数名(实参数1,实参数2); //实参数2不使用默认值，另外定义 内存的动态分配
//使用new和delete动态分配和释放内存空间
指针变量= new 数据类型;//分配空间
delete指针变量;//释放空间 赋值语句
变量名=表达式; //简单赋值
变量名1=变量名2=……=变量名k=表达式; //串联赋值
//成组赋值
(变量名1,变量名2,……,变量名k)=(表达式1,表达式2,……,表达式k);
结构名=结构名;
结构名={值1,值2,……,值k};
变量名[]=表达式;
变量名[起始下标……终止下标]=变量名[起始下标……终止下标];
变量名=条件表达式?表达式T:表达式F;//条件赋值选择语句
//条件语句1
if(条件表达式)语句;
//条件语句2
if(条件表达式)语句;
else语句;
//开关语句
switch(表达式){
case值1:语句1;break;
...
default:语句;
}循环语句
//for语句
for(初始化;条件判断;迭代更新)语句;
//for循环初始化只执行一次
//while语句
while(条件表达式)语句;
//do-while语句
do{
语句序列;
}while(条件表达式);结束语句有
//函数结束语句
return 表达式;
return;
//case结束语句
break;注释
//单行注释
//文字序列基本函数
//求最大值
max(表达式1,...,表达式n);
//求最小值
min(表达式1,...,表达式n);
//求绝对值
abs(表达式);
//推出程序
exit(表达式);逻辑运算约定
与运算&&：对于A&&B，当A的值为0时，不再对B求值
或运算||：对于A||B，当A的值为非0时，不再对B求值
算法效率的衡量方法和准则
算法的效率指的是算法的执行时间随问题规模的增长而增长的趋势，假如随问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同可以记做$T(n)=O(f(n))$，称$T(n)$为算法的时间复杂度。
算法的执行时间=$\sum_{i}^{}$原操作$(i)$的执行次数$\times$原操作$(i)$的执行时间
常数项可以忽略视为$O(0)$
算法的存储空间需求
算法执行期间所需要的存储量应该包括三个部分：输入数据所占空间、程序本身所占空间、辅助变量所占空间
空间复杂度为$S(n)=O(g(n))$
线性表
线性表有两种存储表示方法：顺序表和链表，他的主要基本操作是插入、删除和查找。
线性表的类型定义
线性表的定义
线性表是$n(n\ge0)$个元素的有限序列，表中各个数据元素具有相同特性，即属同一数据对象，表中相邻的数据元素之间存在序偶关系。通常将线性表记做$(a_1,a_2,\dots,a_{i-1},a_i,a_{i+1},\dots,a_{n-1},a_n)$则表中的$a_{i-1}$领先于$a_i$，$a_i$领先于$a_{i+1}$则称$a_{i-1}$是$a_i$的直接前驱元素，$a_{i+1}$是$a_{i}$的直接后继元素，当$i=1,2,\dots,n-1$时$a_i$有且只有一个直接后继。当$i=2,3,\dots,n$时$a_i$有且只有一个直接前驱。
线性表中元素的个数$n(n\ge0)$定义为线性表的长度，$n=0$的线性表称为空表。在非线性表中的每个数据元素都有一个确定的位置，$a_i$时第$i$个元素，称$i$为数据元素$a_i$在线性表中的位序。
线性表的基本操作
InitList(&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已经存在。
操作结果：销毁线性表L。
ClearList(&L)
初始条件：线性表L已经存在。
操作结果：将L重置为空表。
ListEmpty(L)
初始条件：线性表L已经存在。
操作结果：若L为空表，则返回TRUE；否则FALSE。
ListLength(L)
初始条件：线性表L已经存在。
操作结果：返回L中元素个数，即线性表L的长度。
GetElem(L,i,&e)
初始条件：线性表L已经存在,且$1\le i\le ListLength(L)$
操作结果：用e返回L中第i个元素的值。
LocateElem(L,e)
初始条件：线性表L已经存在。
操作结果：返回L中第1个其值与e相等的位序。这样的元素不存在则返回值为0.
PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已经存在。
操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回他的前驱；否则操作失败，pre_e无定义。
NextElem(L,cur_e,&next_e)
初始条件：线性表L已经存在。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回他的后继；否则操作失败，pre_e无定义。
ListInsert(&L,i,e)
初始条件：线性表L已经存在,$1\le i \le LengthList(L)+1$
操作结果：在L的第i个元素之前插入新的元素e,L的长度增1
ListDelete(&L,i,&e)
初始条件：线性表L已经存在且非空，$1\le i \le LengthList(L)$
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1
ListTraverse(L)
初始条件：线性表L已经存在。
操作结果：一次输出L中的每个数据元素。
线性表的顺序表示和实现
顺序表——线性表的顺序存储表示
顺序线性表简称为顺序表，是在计算机中以一组地址连续的存储单元依次存储线性的数据元素。
//线性表的顺序存储表示
const LIST_INIT_SIZE=100;//线性表（默认的）初始分配最大空间量
const LISTINCREMENT=10;//（默认的）增补空间量
typedef struct{
ElemType*elem;//存储数据元素的一维数组
int length;//线性表的当前长度
int listsize;//当前分配的数组容量(以ElemType为单位)
int incrementsize;//约定的增补空间量(以ElemType为单位)
}SqList;若设SqList L；则L为如上定义的顺序表，表中含有L.length个数据元素，依次存储在L.elem[0]至L.elem[L.length-1]；该顺序表最多容纳L.listsize个数据元素；ElemType为线性表中的数据元素所属类型。
顺序表中基本操作的实现
初始化操作
void InitList_Sq(SqList &L, int maxsize = LIST_INIT_SIZE, int incresize = LISTINCREMENT)
{
L.elem = new ElemType[maxsize]; // 为顺序表分配一个最大容量为 maxsize 的数组空间
L.listsize = maxsize; // 该顺序表可以容纳 maxsize 个数据元素
L.listsize = maxsize; // 该顺序表可以容纳 maxsize 个数据元素
L.incrementsize = incresize; // 需要时可扩容 incresize 个元素空间
}//InitList_Sq初始化函数 InitList_Sq 的实现顺序表。这是一个初始化顺序表 SqList 的函数；L 是传入的顺序表（引用类型，代表一个结构体或类对象）；maxsize 是顺序表的初始最大容量，默认值是 LIST_INIT_SIZE；incresize 是顺序表每次需要扩容时增加的元素个数，默认值是 LISTINCREMENT。
查找元素操作
int LocateElem_Sq(SqList L, ElemType e)
{
//在顺序表L中查找第1个值与e相等的数据元素，
//若找到，则返回其在L中的位序，否则返回0
i = 1; // i 的初值为第 1 个元素的位置
p = L.elem; // 将顺序表（线性表）L 的第一个元素的地址赋给指针 p
while (i <= L.length && *p++ != e) ++i; // 依次进行判断，其中
// *p++ != e，这个的步骤是指针p先自增然后（*p++就是）自增后的指针取到对应的值与e进行比较
if (i <= L.length) return i; // 找到满足判定的元素，返回其位置
else return 0; // 若没找到，返回 0
}//LocateElem_Sq
注：c++中指针是从0开始的，最大是表长度-1
插入元素操作
void ListInsert_Sq(SqList &L, int i, ElemType e)
{
if (i < 1 || i > L.length + 1) ErrorMessage("i 值不合法");
if (L.length == L.listsize) increment(L);
q = &(L.elem[i - 1]); // q 为插入位置
for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p;
//p = &(L.elem[L.length - 1]);是指针p的赋值
//L.elem[L.length - 1是最后一个元素的地址
//&:取地址符,根据地址获取相应的值
//p >= q;是循环条件
//--p修改表达式序列
//*(p + 1) = *p;是循环体是将每个数向后移动一位
*q = e; // 插入元素 e
++L.length; // 表长加 1
}//ListInsert_Sq为顺序表追加空间的函数
void increment(SqList &L)
{
ElemType a[];
a = new ElemType[L.listsize + L.incrementsize]; // a 为临时过渡的辅助数组
for (i = 0; i < L.length; i++) a[i] = L.elem[i]; // 腾挪原空间数据
delete[] L.elem; // 释放数据元素所占原空间 L.elem
L.elem = a; // 移交空间首地址
L.listsize += L.incrementsize; // 扩容后的顺序表最大空间
}
删除元素操作
void ListDelete_Sq(SqList &L, int i, ElemType &e)
{
// 在顺序线性表L中删除第i个元素，并用e返回其值
// i 的合法值为 1 <= i <= L.length
if ((i < 1) || (i > L.length)) ERROR("i值不合法");
p = &(L.elem[i - 1]); // p为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem + L.length - 1; // 表尾元素的位置
for (++p; p <= q; ++p)
*(p - 1) = *p; // 被删除元素之后的元素左移
//第一个++p是初始化，为了在*(p - 1) = *p;实现后一个元素覆盖前一个元素只执行一次
//第二个++p是循环迭代为了下一次能够实现后一个元素覆盖前一个元素
--L.length; // 表长减 1
}//ListDelete_Sq
注：++p和p++的区别
p++（后置自增）：
特点：先返回原值，再自增。
过程：在使用变量之前，先将当前变量的值用于表达式的计算，然后再将变量的值增加1。
销毁结构操作
void DestroyList_Sq(SqList &L){
delete[] L.elem;
L.listsize = 0;
L.length = 0;
} // DestroyList_Sq- 函数签名
void DestroyList_Sq(SqList &L)void: 这个函数没有返回值。DestroyList_Sq: 这是函数的名字，用于销毁顺序表（SqList）。SqList &L: 这是函数的参数，类型是SqList的引用。通过引用传递L，意味着这个函数会直接操作传入的L对象，而不需要复制该对象。引用避免了额外的开销，并且函数内对L的修改在函数外也能体现出来。
- 释放内存
delete[] L.elem;L.elem:L是一个SqList对象，其中elem是一个指针，指向存储顺序表元素的动态数组。delete[]: 这是C++中释放动态分配的数组内存的操作符。动态数组是使用new[]分配的，必须用delete[]来释放，以避免内存泄漏。例如，假设之前的
SqList顺序表是通过类似以下方式创建的：L.elem = new int[10];这表示
L.elem指向了一个大小为10的整数数组。使用delete[] L.elem;将释放这段内存。- 这一步的操作非常重要，因为如果一个顺序表使用动态分配的内存来存储元素而没有释放，程序的内存使用量会不断增加，可能导致内存泄漏。
- 重置顺序表属性
L.listsize = 0;
L.length = 0;L.listsize = 0;:listsize表示顺序表的容量（表中最多可以存储的元素数量）。在释放内存后，这个容量已经无效，所以将其重置为0。L.length = 0;:length表示当前顺序表中实际存储的元素个数。在销毁顺序表时，所有元素都已经被释放，因此长度重置为0。
这两个操作的目的是将顺序表状态重置为“空”的状态，表示没有任何存储空间，也没有任何数据。
- 函数结束
} // DestroyList_Sq这是函数的结束标记，表示函数定义到此结束。
插入和删除操作的时间分析
$E_{in}(n)$表示在长度为n的顺序表中进行一次插入操作时所需进行"移动"个数的期望值，则
$$ E_{in}=\sum_{i=1}^{n+1}p_i(n-i+1) $$
其中$p_i$是在第i个元素之前插入一个元素的概率，$n-i+1$是在第$i$个元素之前插入一个元素时所需移动的元素个数。$p_i=\frac{1}{n+1}$由此得出
$$ E_{in}=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)\\ \qquad=\frac{1}{n+1}\times\frac{n(n+1)}{2}=\frac{n}{2} $$
类似地令$E_{dl}(n)$表示在长度为n的顺序表中进行一个次删除操作所需进行移动个数的期望值
$$ E_{dl}=\sum_{i=1}^{n}q_i(n-1) $$
其中$q_i$是删除第$i$个元素的概率$q_i=\frac{1}{n}$由此可以得出
$$ E_{dl}=\frac{1}{n}\sum_{i=1}^{n}(n-i)\\ =\frac{1}{n}\times\frac{n(n-1)}{2}=\frac{n-1}{2} $$
线性表的链式表示和实现
单链表和指针
对于链表中的数据元素来说除了存储其本身的信息之外，还需存储一个指示其直接后继的信息，这两部分信息组成一个节点表示线性表中一个数据元素。节点中存储数据元素信息的域称为数据域（data），存储直接后继存储位置的域称为指针域（next）。n个节点依次相链构成一个链表，称为线性表的链式存储表示。每个节点只包含一个指针域故又称为单链表或线性链表。
若p、q、H均为指针型变量。若p的值非空，则表明p指向某个结点；p->data表示p所指结点中的数据域；p->next表示p所指结点中的指针域，若非空则指向其后继结点。
单链表的基本操作
求线性表的长度
int ListLength_L(LinkList L){
p = L; k = 0;
while (p) {
k++;
p = p->next;
}
return k;
}
- 函数签名
int ListLength_L(LinkList L)int: 这个函数的返回值类型是int，即返回一个整数，表示链表的长度。ListLength_L: 这是函数的名字，表示计算链表长度的功能。LinkList L: 这是函数的参数，表示传入的链表L。在这个上下文中，LinkList可能是一个链表的结构体类型，L是链表的头指针。
- 局部变量初始化
p = L; k = 0;p = L;:p是一个指针，初始化为链表L的头指针。即p开始指向链表的第一个节点。k = 0;:k是一个整数变量，用来计数链表的节点个数，初始值设为0。
while循环
while (p) {
k++;
p = p->next;
}while (p): 当指针p不为空时（即p指向一个有效的节点），循环执行。k++: 每进入一次循环，k增加1，这意味着发现了一个新的非空节点。k会累加链表中的节点数。p = p->next;: 将p更新为当前节点的下一个节点，即通过p->next，指针指向链表的下一个节点。如果链表的下一个节点为空（NULL），则p变为NULL，循环结束。
- 返回链表长度
return k;- 当链表遍历完毕后，
p为NULL，k保存了链表中非空节点的个数。最后返回k，即链表的长度。
查找元素操作
INode* LocateElem_L(LinkList L, ElemType e){
p = L;
while (p && p->data != e){p = p->next;}
return p;
}- 函数签名
INode* LocateElem_L(LinkList L, ElemType e)INode*: 表示函数返回一个INode类型的指针（即链表节点的指针）。LocateElem_L: 函数名，表示在链表中查找指定元素的功能。LinkList L: 链表的头指针，L是指向链表第一个节点的指针。ElemType e: 查找的元素值e，该类型为ElemType，可能是链表中节点数据的类型，如int、float等。
- 局部变量初始化
p = L;p = L;:p是一个链表节点指针，用来遍历链表。初始化为链表头指针L，即开始遍历链表的第一个节点。
while循环
while (p && p->data != e)
p = p->next;p: 判断当前节点是否为NULL，即是否到达链表的末尾。p->data != e: 判断当前节点的数据域data是否与查找的元素e相等。如果不相等，则继续向下遍历链表。p = p->next;: 如果当前节点的数据与e不匹配，则更新p为下一个节点的指针p->next，即继续查找下一个节点。
这个循环会一直遍历链表，直到找到值等于 e 的节点，或是到达链表末尾（p == NULL）。
- 返回结果
return p;返回
p：当循环结束时，p可能指向一个包含值e的节点，也可能为NULL（即没有找到符合条件的节点）。- 如果找到了值为
e的节点，p指向该节点的指针就会被返回。 - 如果遍历完整个链表都没有找到值为
e的节点，则p会等于NULL，函数返回NULL，表示没有找到目标元素。
- 如果找到了值为
插入结点操作
void ListInsert_L(LinkList &L, INode *p, INode *s){
if (p == L) {
s->next = L;
L = s;
}
else {
INode *q = L;
while (q->next != p) q = q->next;
q->next = s;
s->next = p;
}
}- 函数签名
void ListInsert_L(LinkList &L, INode *p, INode *s)void: 该函数没有返回值。ListInsert_L: 函数名，表示在链表L中插入节点的功能。LinkList &L: 通过引用传递链表L，表示对链表进行修改，传入的是链表的头指针。INode *p: 这是链表中的一个节点指针，表示要在p节点之前插入s节点。INode *s: 这是新插入的节点，s要插入到p之前。
- 插入节点到链表的第一个位置
if (p == L) {
s->next = L;
L = s;
}if (p == L): 这判断p是否是链表的第一个节点（即头节点）。如果p就是头节点，表示需要把s插入到链表的最前面。s->next = L;: 将s的next指针指向链表的头节点L，这一步是为了将s插入到链表的最前面。L = s;: 更新链表的头指针L，使其指向新插入的节点s，这样s就成为了新的头节点。
- 插入节点到链表中间位置
else {
INode *q = L;
while (q->next != p) q = q->next;
q->next = s;
s->next = p;
}else: 如果p不是头节点，则进入else块，将s插入到链表的中间（p的前面）。INode *q = L;: 定义一个临时指针q，初始化为链表的头指针，用于遍历链表找到p节点的前驱节点。while (q->next != p): 通过这个循环，q会依次指向链表中的节点，直到q->next等于p，也就是说找到了p的前驱节点q。q->next = s;: 将q的next指针指向s，即将s插入到q的后面。s->next = p;: 将s的next指针指向p，完成s插入到p前面的操作。
- 函数结束
} // ListInsert_L这是函数的结束标志。