一. 基本概念

数据结构三要素：逻辑结构、数据的运算、物理结构(存储结构)

1. 提取操作对象，找出操作对象之间的关系并用数学的语言描述就是数据结构。

   操作对象指：每位学生的信息(学号、姓名、性别.....)

   操作的算法指：查询、插入、修改、删除等。

2. 数据结构可分为：线性数据结构（数组，队列，线性表等）、非线性数据结构（集合，树，图等）。

   线性数据结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。如：学生管理系统，是一对一关系

   非线性数据结构：一个结点可能油多个直接前趋和直接后继。如：目录结构(树)、最短路径(图)，是一对多关系或多对多关系。

   最短路径：

   

1. 概念及定义

数据(Data)

数据是能输入计算机且能被计算机处理的各种符号的集合。

数据特点：

1. 信息的载体
2. 是对客观事物符号化的表示
3. 能够被计算机识别存储和加工

数据包括：

1. 数值型的数据：整数、实数等。
2. 非数值型的数据：文字、图像、图形、声音等。

数据元素

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。而一个数据元素可由多个数据项组成，数据项是构成数据元素不可分割最小单位。

也可称为元素，或称为记录、结点或顶点。如上面最短路径图，其中的每个点我们称之为结点。

• 数据项

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

  数据项：

  

  上面每行可称为数据元素，而每列可以称之为数据元素中的数据项。

• 三者关系

  数据$>$$>$数据元素$>$$>$数据项

  例子：学生表$>$$>$个人记录$>$$>$学号、姓名....

数据对象

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

如：学籍表可以看作是一个数据对象，由若干条学生信息构成的子集。

• 数据元素和数据对象关系

  数据元素：组成数据的基本单位。其与数据的关系是：数据元素是集合的个体。

  数据对象：性质相同的数据元素的集合。其与数据的关系是：集合的子集。

数据对象图例：

数据结构

意义：数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构( Structure )

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

• 数据结构包含内容：

  1. 数据元素之间的逻辑关系，也称为逻辑结构。
  2. 数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或数据的存储结构。
  3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

• 数据结构的两个层次

  1. 逻辑结构：

     描述数据元素之间的逻辑关系

     与数据存储无关，独立于计算机

     是从具体问题抽象出来的数学模型

  2. 物理结构(存储结构)：

     数据元素及其关系在计算机存储器中的结构(存储方式)

     是数据结构在计算机中的表示

  3. 逻辑结构和存储结构的关系：

     存储结构是逻辑关系的映像与元素本身的映像。

     逻辑结构是数据结构的抽象，存储结构是数据结构的实现。

     两者综合起来建立了数据元素之间的结构关系。

2. 四种逻辑结构

逻辑结构和数据的运算是定义一种数据结构前提。

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

集合结构例子：

线性结构：结构中的数据元素之间存在着一对一的线性关系，除了除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。

基本运算：①查找第$i$$i$个数据元素。②在第$i$$i$个位置插入新的数据元素。③删除第$i$$i$个位置数据元素.....

线性结构例子：

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

树形结构例子：

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

图结构例子：

逻辑结构分类：

3. 四种基本存储结构

当我们定义完一种数据结构后，需要用计算机来实现这种数据结构，此时用到基本存储结构。

顺序存储结构

含义：

1. 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
2. C语言中用数组来实现顺序存储结构

顺序存储结构示例：

链式存储结构

含义：

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

链式存储结构：

如：上图$bat$$bat$对应指针(地址)是$165$$165$，后面$130$$130$是下一个元素地址，即$cat$$cat$。没有即为$NULL$$NULL$

索引存储结构

含义：

1. 在存储结点信息的同时，还建立附加的索引表。
2. 通俗讲索引就是目录，一般形式是：关键字、地址。
3. 关键字是能唯一标识一个结点的数据项。
4. 若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引。

索引存储结构：

散列存储结构

根据结点的关键字直接计算出该结点的存储地址。如：哈希表。

4. 数据类型、抽象数据类型

4.1 数据类型

数据类型是一个值的取值范围和定义在此范围上的一组操作(加减、取模等)的总称。

1. 原子类型：其值不可再分的数据类型。如$int$$int$类型(可进行加、减、乘、除、取模等运算)，$bool$$bool$类型(可进行与、或、非等操作)
2. 结构类型：其值可以再分解为若干成分(分量)的数据类型。如定义一个可操作横坐标和纵坐标的函数。

4.2 抽象数据类型(ADT)

抽象数据类型是抽象数据组织及与之相关的操作。如：逻辑结构、数据运算、物理结构(存储结构)，这个过程。

二. 算法

1. 算法基本概念

算法就是如何高效地处理这些数据，以解决实际问题。

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

算法特点：

1. 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
3. 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4. 输入。 一个算法有零个或多个输入， 这些输入取自于某个特定的对象的集合。 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

以上特点只要有一个不满足，就不能称之为算法。

一个好的算法所具备特质：

1. 正确性。算法能够正确解决求解问题。
2. 可读性。算法应具有良好的可读性，以帮助人们理解。考试时候要写注释。
3. 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 高效率和低存储。即算法时间复杂度低，空间复杂度低。

算法基本概念总结：

2. 算法效率度量

算法复杂度度量可以从两个方面：①时间复杂度、②空间复杂度

2.1 时间复杂度

用事前预估算法时间开销$T(n)$$T(n)$与问题规模$n$$n$的关系($T$$T$表示"time")。

方法：

• 时间复杂度加法规则：

  我们可以通过对每一行有效代码进行时间记录，从而估计出代码所需的执行时间。如下：

  1
  void loveYou(int n) { //n 为问题规模
  2
      int i=1;//爱你的程度
  3
      while(i<=n){
  4
          i++ ;
  5
          //每次+1
  6
          printf("I Love You %d\n",i);
  7
      }
  8
      printf("I Love You More Than %d\n",n) ;
  9
  }
  10
  int main( ){
  11
      loveYou(3000) ;
  12
  }
  

  以上代码模拟打印3000遍I Love You。运行结果如下：

  xxxxxxxxxx
  9
  1
  ....
  2
  I Love You 2994
  3
  I Love You 2995
  4
  I Love You 2996
  5
  I Love You 2997
  6
  I Love You 2998
  7
  ....
  8
  I Love You 3001
  9
  I Love You More Than 3000
  

  我么可以估计一下语句执行时间：①⑤各执行一次，②执行3001次，③④执行3000次，所以变量$n$$n$为3000时，所需执行时间为：

  $T(3000)=1+1+3001+2\times 3000$$T(3000)=1+1+3001+2\times3000$。所以其时间开销$T$$T$与问题规模$n$$n$关系式子为：$T(n)=3n+3$$T(n)=3n+3$。

  虽然我们通过如此简单方式得出这段程序所需执行时间，但是广义化之后该方法并不适用：如果代码是几万行的这种方法显然不适用。

  根据我们所学数学知识，我们想得到一个估计大小时，一个表达式中更低阶部分我们往往可以省略。所以上面可以写为$T(n)=3n$$T(n)=3n$。假设有以下算法时间复杂度：

  $$\begin{array}{rl}& T_1(n)=3n^2+3n+3000\stackrel{\text{忽}\text{略}\text{低}\text{阶}\text{后}}{\to }=3n^2\\ \\ & T_2(n)=n^3+n^2+9999\stackrel{\text{忽}\text{略}\text{低}\text{阶}\text{后}}{\to }=n^3\end{array}$$

  我们一般用$O$$O$表示"同阶"(同等数量级。即，当$n\to \mathrm{\infty }$$n\to\infty$时，二者极限之比为常数，来代替最高阶前面系数)，来规范时间复杂度的写法。所以上面规范写法如下：

  $$\begin{array}{rl}& 3n^2=O(n^2)\\ \\ & n^3=O(n^3)\end{array}$$

  结论：一个程序的算法复杂度可以只考虑阶数高的部分。以上是时间复杂度计算的加法规则，同样我们可以推出以下的规则：

• 乘法规则

  $T(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$$T(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

  即多项相乘，都保留。如：$T(n)=O(n^3)\times O(n^2)=O(n^5)$$T(n)=O(n^3)\times O(n^2)=O(n^5)$¹

• 混合运算规则

  $T(n)=O(f(n))+O(g(n))=max\{O(f(n))+O(g(n))\}$$T(n)=O(f(n))+O(g(n))=max\{O(f(n))+O(g(n))\}$

  混合运算需要保留最大那个项。为了方便理解我们可以保留其中变化趋势最大函数，函数变化趋势如下：

  复杂度变化趋势：

  

  例子：$T(n)=n^3+n^2{\log }_{2}n=$$T(n)=n^3+n^2\log_2n=$$O(n^3)+O(n^2{\log }_{2}n)=$$O(n^3)+O(n^2\log_2n)=$$O(n^3)$$O(n^3)$。

通过以上规则我们还要注意以下几点：

1. 顺序执行的代码只会影响常数项，所以可以忽略不记。
2. 循环执行代码中，我们只需要挑一个循环体基本操作，分析他的执行次数即可。
3. 如果有多层嵌套循环，我们只需要关注最深层代码循环次数即可。

例1：分析以下代码时间复杂度

xxxxxxxxxx
9
1
//算法3- 指数递增型爱 你
2
void loveYou(int n) { //n 为问题规模
3
    int i=1;//爱你的程度
4
    while(i<=n){
5
        i=i*2; //每次翻倍
6
        printf("I Love You %d\n",i);        
7
    }
8
    printf("I Love You More Than %d\n",n);
9
}

答案：$T(n)=O({\log }_{2}n)$$T(n)=O(\log_2n)$

解析：我们直接看循环体，循环体中，赋值语句$i$$i$每次翻倍，假设循环了$x$$x$次，则循环结束时刚好满足$2^x>n$$2^x>n$，所以$x={\log }_{2}n+1$$x=\log_2n+1$

则，时间复杂度$T(n)=O({\log }_{2}n)$$T(n)=O(\log_2n)$

例2：分析以下代码时间复杂度

xxxxxxxxxx
15
1
void loveYou(int flag[]， int n) { //n 为问题规模
2
    printf("I Am Iron Man\n") ;
3
    for(int i=0; i<n; i++){ //从第一个元素开始查找
4
        if(flag[i]==n){ //找到元素n
5
            printf("I Love You %d\n"，n) ;
6
            break; //找 到后立即跳出循环
7
        }
8
    }
9
}
10
//其中flag数组是1~n个数，输入一个数n找出n在数组中的位置
11
int main(){
12
    int flag[n]={1...n};
13
    loveYou(flag,n); 
14
    return 0;
15
}

答案：最好情况：元素n在第一个位置，即最好时间复杂度$T(n)=O(1)$$T(n)=O(1)$ 最坏情况：元素n在最后一个位置，最坏时间复杂度$T(n)=O(n)$$T(n)=O(n)$ 平均情况：假设元素n在任意一个位置的概率相同为$\frac{1}{n}$$\frac{1}{n}$，平均时间复杂度$T(n)=O(n)$$T(n)=O(n)$

平均情况解析：循环次数$x=(1+2+3+...+n)\frac{1}{n}=(\frac{n(1+n)}{2})\frac{1}{n}=\frac{1+n}{2}$$x=(1+2+3+...+n)\frac{1}{n}=(\frac{n(1+n)}{2})\frac{1}{n}=\frac{1+n}{2}$，即$T(n)=O(x)=O(n)$$T(n)=O(x)=O(n)$

注意：我们在评价一个算法时候一般只看最坏情况和平均情况，而最好情况一般参考意义不大。

时间复杂度总结：

2.2 空间复杂度

空间复杂度需要时间复杂度中运算知识。空间复杂度我们用$S(n)$$S(n)$表示。

例1：计算以下程序空间复杂度

xxxxxxxxxx
6
1
void test(int n) {
2
    int flag[n];
3
    //声明一个长度为n的数组
4
    int i;
5
    //.....此处省略很多代码
6
}

答案：$S(n)=O(n)$$S(n)=O(n)$

解析：函数所需要参数$n\text{为}int\text{类}\text{型}$$n为int类型$占四个字节，下面的$i\text{也}\text{是}int$$i也是int$类型所以也是四字节，数组长度是$n$$n$且为int类型，所以是$4n$$4n$，那么这个程序所需要空间为：$4n+8$$4n+8$。规范写法为$S(n)=O(n)$$S(n)=O(n)$

结论：常数项同样不考虑，注意数组大小等。

例2：计算以下程序空间复杂度

xxxxxxxxxx
7
1
void test(int n) {
2
    int flag[n][n]; //声明 n*n的二维数组
3
    int otheg[n];
4
    //声明一个长度为n的数乡
5
    int i;
6
    //.... .此处省略很多代码
7
}

答案：$S(n)=O(n^2)$$S(n)=O(n^2)$

解析：二维int类型n长度数组占大小为：$4n^2$$4n^2$，下面一维数组是$4n$$4n$，所以$S(n)=O(n^2)+O(n)+O(1)=O(n^2)$$S(n)=O(n^2)+O(n)+O(1)=O(n^2)$

例3：计算以下程序空间复杂度

xxxxxxxxxx
11
1
void loveYou(int n) { //n 为问题规模
2
    int a,b,c; //声明一 系列局部变量
3
    //...省略代码
4
    if(n>1){
5
        loveYou(n-1);
6
    }
7
    printf("I Love You %d\n"， n);
8
}
9
int main(){
10
    loveYou(n)
11
}

答案：$S(n)=O(n)$$S(n)=O(n)$

解析：函数递归$n$$n$次，每次变量大小占$16$$16$，所以应该为$S(n)=16n=O(n)$$S(n)=16n=O(n)$

结论：递归问题空间复杂$=$$=$递归调用深度。

例4：我们对例3进行改进，讲声明变量改为数组

xxxxxxxxxx
11
1
void loveYou(int n) { //n 为问题规模
2
    int flag[n]; //声明一 系列局部变量
3
    //...省略代码
4
    if(n>1){
5
        loveYou(n-1);
6
    }
7
    printf("I Love You %d\n"， n);
8
}
9
int main(){
10
    loveYou(n)
11
}

答案：$S(n)=O(n^2)$$S(n)=O(n^2)$

解析：函数递归调用$n$$n$次，每次数组长度为$n$$n$，所以空间复杂度为：$1+2+3+...n=\frac{n(1+n)}{2}=\frac{1}{2}{n}^2+\frac{1}{2}n$$1+2+3+...n=\frac{n(1+n)}{2}=\frac{1}{2}n^2+\frac{1}{2}n$，即答案。

空间复杂度总结：

三. 线性表

1. 线性表定义

定义：线性表是具有相同数据类型的$n(n\ge 0)$$n (n≥0)$ 个数据元素的有限序列，其中$n$$n$为表长，当$n=0$$n=0$时线性表是一个空表。若用$L$$L$命名线性表，则其一般表示为：

几个概念：

1. $a_i$$a_i$是线性表中的"第$i$$i$个"元素线性表中的位序
2. $a_1$$a_1$是表头元素；$a_n$$a_n$是表尾元素。
3. 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

2. 线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表$L$$L$，分配内存空间。 DestroyList(&L)：销毁操作。销毁线性表，并释放线性表$L$$L$所占用的内存空间。

ListInsert(&L，i，e)：插入操作。在表$L$$L$中的第$i$$i$个位置上插入指定元素$e$$e$。 ListDelete(&L，i，&e)：删除操作。删除表$L$$L$中第$i$$i$个位置的元素，并用$e$$e$返回删除元素的值。

LocateElem(L，e)：按值查找操作。在表$L$$L$中查找具有给定关键字值的元素。 GetElem(L，i)：按位查找操作。获取表$L$$L$中第$i$$i$个位置的元素的值。

其他常用操作: Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。 PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。 Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

以上括号内的是参数。

总结：

1. 对数据的操作：创建，销毁、增删改查

2. $C$$C$语言函数的定义：<返回值类型>函数名(<参数1类型>参数1，<参数2类型>参数2.....)

3. 函数名和参数的形式、命名都可改变。对于命名一般用驼峰命名法：

   方法名、参数名、成员变量、局部变量需要使用小驼峰命名法

   类名需要使用大驼峰命名法

4. 什么时候要传入引用"&"：对参数的修改结果需要"带回来"。解释如下：

   xxxxxxxxxx
   11
   1
   #include<stdio.h>
   2
   void test(int & x) {
   3
       x=1024;
   4
       printf( "test函数内部x=%d\n",x);
   5
   }
   6
   int main() {
   7
       int X=1;
   8
       printf("调用test前x=%d\n",x) ;
   9
       test(X) ;
   10
       printf( "调用test后x=%d\n",x) ;
   11
   }
   

   运行结果：

   调用test前x=1 test函数内部x=1024 调用test后x= 1024

   这里test函数中的$x$$x$是引用类型，所以不用返回值就可以修改主函数中的$x$$x$值。

线性表知识点总结：

3. 顺序表

顺序表是线性表的一种。其定义是：用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置，上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表优缺点：

• 优点:可随机存取，存储密度高
• 缺点:要求大片连续空间，改变容量不方便

我们可以用$C$$C$语言提供的$sizeof$$sizeof$关键字来判断一个类型或者数据的大小。

顺序存储：

3.1 顺序表的静态分配

xxxxxxxxxx
5
1
#define MaxSize 10          //定义最大长度
2
typedef struct{
3
    ElemType data[MaxSize]; //用静态的“数组”存放数据元素
4
    int length;             //顺序表的当前长度
5
}SqList;                    //顺序表的类型定义(静态分配方式)

给各个数据元素分配连续的存储空间，大小为$MaxSize\ast sizeof(ElemType)$$MaxSize* sizeof(ElemType)$。即数组大小$\times$$\times$数据类型。

注意：$C$$C$语言要初始化数据。否则会出现"脏数据"情况。

静态分配存在一定局限性：无法提前预知数组大小。

3.2 顺序表的动态分配

$C$$C$语言中动态申请和释放内存空间函数：

• malloc(动态申请空间)：SeqList.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);

  malloc函数返回一个指针，需要强制转型为你定义的数据元素类型指针。

• free(删除申请空间)：free(SeqList.data)

xxxxxxxxxx
6
1
#define InitSize 10 //顺序表的初始长度
2
typedef struct{
3
    ElemType *data; //指示动态分配数组的指针
4
    int MaxSize;    //顺序表的最大容量
5
    int length;     //顺序表的当前长度
6
} SeqList;          //顺序表的类型定义(动态分配方式)

动态分配案例：

​x
1
#include <bits/stdc++.h>
2
using namespace std;
3
struct stu{
4
    int *arr;
5
    int len;
6
};
7
void initArr(stu &l){                       //初始化arr指针，并未其分配初始空间
8
    int i=0,j=0;
9
    l.arr=(int *)malloc(10*sizeof(int));
10
    l.len=0;
11
    while(cin>>i){                          //输入数组值
12
        l.arr[j]=i;
13
        l.len++;
14
        j++;
15
    }
16
}
17

18
void insertArr(stu &l,int cout){            //扩大arr指针空间
19
    int *p=l.arr;
20
    l.arr=(int *)malloc((cout+l.MaxSize)*sizeof(int));
21
    for(int i=0;i<l.len;i++){
22
        l.arr[i]=p[i];
23
        printf("指针值：%d\n",p[i]);
24
    }
25
    free(p);
26
}
27
int main(){
28
    stu l;
29
    initArr(l);
30
    insertArr(l,3);
31
    for(int i=0;i<l.len;i++){
32
        cout<<l.arr[i]<<endl;               //输出扩大后的数组arr
33
    }
34
} 

顺序表的特点:

1. 随机访问，即可以在$O(1)$$O(1)$时间内找到第$i$$i$个元素。
2. 存储密度高，每个节点存储数据元累
3. 拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)
4. 插入、删除操作不方便，需要移动大量元素

3.3 顺序表的插入

xxxxxxxxxx
23
1
#define MaxSize 10              //定义最大长度
2
typedef struct{
3
    int data[MaxSize];          //用静态的"数组"存放数据
4
    int length;                 //顺序表的当前长度
5
}SqList;                        //顺序表的类型定义
6
bool ListInsert(SqList &L,int i,int e){
7
    if(i<1||i>L.length+1)       //判断i的范围是否有效
8
        return false;
9
    if(L.length>=MaxSize)       //当前存储空间已满，不能插入
10
        return false;
11
    for(int j=L.length;j>=i;j--)//将第1个元素 及之后的元素后移
12
        L.data[j]=L.data[j-1];
13
    L.data[i-1]=e;              //在位置i处放入e 
14
    L.length++;                 //长度加1
15
    return true ;
16
}
17
int main( ) {
18
    SqList L;                   //声明一个顺序表
19
    InitList(L);                //初始化顺序表
20
    //...此处省略一些代码，插入几个元素
21
    ListInsert(L,3,3);
22
    return 0;
23
}

以上就是对顺序表进行元素插入操作。

我们可以对以上ListInsert()方法进行时间复杂度分析：

1. 最好情况：新元素插入到表尾，不需要移动元素。

   $i=n+1$$i=n+1$，循环$0$$0$次，最好时间复杂度$=O(1)$$=O(1)$

2. 最坏情况：新元素插入到表头，需要将原有的$n$$n$个元素全部向后移动

   $i=1$$i=1$，循环$n$$n$次；最坏时间复杂度$=O(n)$$=O(n)$

3. 平均情况：假设新元素插入到任何一个位置的概率相同，即$i=1,2,3...,length+1$$i=1,2,3...,length+1$的概率都是$p=\frac{1}{n+1}$$p=\frac{1}{n+1}$

   当$i=1$$i=1$时，循环$n$$n$次；$i=2$$i=2$时，循环$n-1$$n-1$次；$i=3$$i=3$时，循环$n-2$$n-2$次$...i=n+1$$...i=n+1$时，循环$0$$0$次。

   所以平均循环次数$=np+(n-1)p+(n-2)p+...+p=\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$$=np+(n-1)p+(n-2)p+...+p=\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$

   由此可得时间复杂度为$O(n)$$O(n)$

3.4 顺序表的删除

xxxxxxxxxx
25
1
#define MaxSize 10              //定义最大长度
2
typedef struct{
3
    int data[MaxSize];          //用静态的"数组"存放数据
4
    int length;                 //顺序表的当前长度
5
}SqList;    
6
bool ListDelete(SqList &L,int i,int &e){
7
    if(i<1||i>L.length)         //判断i的范围是否有效
8
        return false;
9
    e=L.data[i-1];              //将被删除的元素赋值给e
10
    for(int j=i;j<L.length;j++) //将第i个位 置后的元素前移
11
        L.data[j-1]=L.data[j];
12
    L.length--;                 //线性表长度减1
13
    return true ;
14
}
15
int main() {
16
    SqList L;                   //声明一个顺序表
17
    InitList(L);                //初始化顺序表
18
    //.. .此处省略一些代码，插入几个元素
19
    int e;                      //用变量e把删除的元素”带回来”
20
    if (ListDelete(L,3,e))
21
        printf("已删除第3个元素,删除元素值为=%d\n",e);
22
    else
23
        printf("位序i不合法，删除失败\n");
24
    return 0;
25
}

运行结果：已删除第3个元素,删除元素值为$=$$=$3；

我们可以对以上ListDelete()方法进行时间复杂度分析：

1. 最好情况：删除表尾元素，不需要移动其他元素

   $i=n$$i=n$，循环$0$$0$次，最好时间复杂度$=O(1)$$=O(1)$

2. 最坏情况：删除表头元素，需要将后续的$n-1$$n-1$个元素全都向前移动

   $i=1$$i=1$，循环$n-1$$n-1$次；最坏时间复杂度$=O(n)$$=O(n)$；

3. 平均情况：假设删除任何一个元素的概率相同，即$i=1,2,3,...length$$i= 1,2,3, ... length$的概率都是$p=\frac{1}{n}$$p=\frac{1}{n}$

   $i=1$$i=1$，循环$n-1$$n-1$次，$i=2$$i=2$，循环$n-2$$n-2$次$...i=n$$...i=n$时，循环$0$$0$次

   平均循环次数为$=(n-1)p+(n-2)p+...+p=\frac{n(n-1)}{2}\frac{1}{n}=\frac{n-1}{2}$$=(n-1)p+(n-2)p+...+p=\frac{n(n-1)}{2}\frac{1}{n}=\frac{n-1}{2}$

   由此可得时间复杂度为$O(n)$$O(n)$

顺序表基本操作总结：

3.5 顺序表的查找

• 按位查找

  获取表L中第i个位置的元素的值。静态分配方式：

  xxxxxxxxxx
  9
  1
  #define MaxSize 10
  2
  //定义最大长度
  3
  typedef struct{
  4
      ElemType data [MaxSize];//用静态的“数组”存放数据元素
  5
      int length;             //顺序表的当前长度
  6
  }SqList;                    //顺序表的类型定义(静态分配方式)
  7
  ElemType GetElem(SqList L,int i){
  8
     return L.data[i-1]; 
  9
  }
  

  动态分配方式：

  xxxxxxxxxx
  9
  1
  #define InitSize 10         //顺序表的初始长度
  2
  typedef struct{
  3
      ElemType *data;         //指示动态分配数组的指针
  4
      int MaxSize;            //顺序表的最大容量
  5
      int length;             //顺序表的当前长度
  6
  } SeqList;                  //顺序表的类型定义(动态分配方式)
  7
  ElemType GetElem(SqList L,int i){
  8
     return L.data[i-1]; 
  9
  }
  

  由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第$i$$i$个元素。具有"随机存取"特性。

• 按值查找

  注意：不能直接判断两个结构体是否相等。如果要判断我们需要对结构体一个一个比较。

  基本数据类型如：int、 char、 double、float等可以直接用运算符"=="比较。但$C++$$C++$可以

  xxxxxxxxxx
  13
  1
  #define InitSize 10                 //顺序表的初始长度
  2
  typedef struct{
  3
      ElemType *data;                 //指示动态分配数组的指针
  4
      int MaxSize;                    //顺序表的最大容量
  5
      int length;                     //顺序表的当前长度
  6
  } SeqList;                          //顺序表的类型定义(动态分配方式)
  7
  //在顺序表L中查找第一一个元素值等于e的元素，并返回其位序
  8
  int LocateElem(SeqList L,ElemType e){
  9
      for(int i=0;i<L. length; i++)
  10
          if(L.data[i]==e)
  11
              return i+1;             // 数组下标为i的元素值等于e，返回其位序i+1
  12
      return 0;                       //退出循环，说明查找失败
  13
  }
  

  该算法的时间复杂度：

  1. 最好情况：目标元素在表头，循环$1$$1$次；最好时间复杂度$=O(1)$$=O(1)$

  2. 最坏情况：目标元素在表尾，循环$n$$n$次，最坏时间复杂度$=O(n)$$=O(n)$

  3. 平均情况：假设目标元素出现在任何一个位置的概率相同， 都是$\frac{1}{n}$$\frac{1}{n}$

     目标元素在第$1$$1$位，循环$1$$1$次；在第$2$$2$位，循环$2$$2$次.....在第$n$$n$位，循环$n$$n$次

     平均循环次数：$=1·\frac{1}{n}+2·\frac{1}{n}+...+n·\frac{1}{n}=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{n}$$=1·\frac{1}{n}+2·\frac{1}{n}+...+n·\frac{1}{n}=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{n}$

     即时间复杂度为$=O(n)$$=O(n)$

顺序表按位查找和按值查找总结：

4. 单链表

链表不同于顺序表的顺序存储方式，用的是链式存储。

单链表的每个结点除了存放数据元素，同时还需要包含指向下一个结点的指针。由于每个结点只包含一个指针所以叫单链表。

单链表优缺点：

• 优点：不要求大片连续空间，改变容量方便
• 缺点：不可随机存取，要耗费一定空间存放指针，无法逆向检索。

单链表定义如下：

xxxxxxxxxx
4
1
struct LNode{
2
    ElemType data;
3
    struct LNode *next;
4
}

上面的"LNode"称之为结点，data称为数据域，*next称为指针域。

带头节点的单链表：

xxxxxxxxxx
19
1
typedef struct LNode{
2
    int data;               //定义单链表结点类型
3
    struct LNode *next;     //每个节点存放一个数据元素
4
}LNode,*LinkList;           //指针指向下一个节点
5

6
//初始化一个空的单链表
7
bool InitList(LinkList &L) {
8
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
9
    if (L==NULL)                        //内存不足，分配失败
10
        return false;
11
    L->next = NULL;                     //头结点之后暂时还没有节点
12
    return true;
13
}
14
void test(){
15
    LinkList L;             //声明一个指向单链表的指针
16
    //初始化一个空表
17
    InitList(L);
18
    //......后续代码......
19
}

上面前四行代码是将"struct LNode"命名为"LNode"，并且用"LinkList"表示一个指向"struct LNode"的指针。

不带头结点单链表

xxxxxxxxxx
16
1
typedef struct LNode{
2
    int data;               //定义单链表结点类型
3
    struct LNode *next;     //每个节点存放一个数据元素
4
}LNode,*LinkList;           //指针指向下一个节点
5

6
//初始化一个空的单链表
7
bool InitList(LinkList &L) {
8
    L = NULL; //空表，暂时还没有任何结点
9
    return true;
10
}
11
void test(){
12
    LinkList L;             //声明一个指向单链表的指针
13
    //初始化一个空表
14
    InitList(L);
15
    //......后续代码......
16
}

4.1 单链表建立

4.1.1 尾插法

先初始化一个带头结点的单列表，之后每次取个数据元素插入表尾部。是比较常用的方法。

• 先初始化链表：

  xxxxxxxxxx
  13
  1
  typedef struct LNode{
  2
      int data;               //定义单链表结点类型
  3
      struct LNode *next;     //每个节点存放一个数据元素
  4
  }lNode,*linkList;           //指针指向下一个节点
  5
  
  6
  //初始化链表 
  7
  bool initList(linkList &l){
  8
      l=(lNode*)malloc(sizeof(lNode));    //链表开辟一个头节点
  9
      if(l==NULL)
  10
          return false;
  11
      l->next=NULL;                       //头结点指针域指向空
  12
      return true;
  13
  }
  

• 创建链表：

  xxxxxxxxxx
  17
  1
  //尾插法创建链表 
  2
  bool insertTail(linkList &l){
  3
      lNode *pHead,*pTial;                //指针pHead和pTial分别表示链表头部和尾部
  4
      pTial=l;                            //将尾指针指向l链表
  5
      int i=0;
  6
      while(i!=999999){       
  7
          cin>>i;
  8
          if(i!=999999){
  9
              pHead=(lNode*)malloc(sizeof(lNode));    
  10
              pHead->data=i;              //创建结点pHead其数据与为输入的i值
  11
              pTial->next=pHead;          //将尾部结点的指针域指向头部结点
  12
              pTial=pHead;                //接着将尾部结点指向创建的头部结点
  13
          }
  14
      }
  15
      pTial->next=NULL;                   //将最后一个指针域设置为空
  16
      return 1;
  17
  }
  

• 主函数：

  xxxxxxxxxx
  5
  1
  int main(){
  2
      linkList link;
  3
      initList(link);                 //链表初始化 
  4
      insertTail(link);               //尾插法创建链表 
  5
  } 
  

运行结果：

输入：1，2，399

尾插法图像示例：

4.1.2 头插法建立链表

头插法将每个数据插入在链表头部。头插法可以用于链表的逆置。

• 同样先初始化链表：

  xxxxxxxxxx
  13
  1
  typedef struct LNode{
  2
      int data;               //定义单链表结点类型
  3
      struct LNode *next;     //每个节点存放一个数据元素
  4
  }lNode,*linkList;           //指针指向下一个节点
  5
  
  6
  //初始化链表 
  7
  bool initList(linkList &l){
  8
      l=(lNode*)malloc(sizeof(lNode));    //链表开辟一个头节点
  9
      if(l==NULL)
  10
          return false;
  11
      l->next=NULL;                       //头结点指针域指向空
  12
      return true;
  13
  }
  

• 创建链表：

  xxxxxxxxxx
  14
  1
  bool insertHead(linkList &l){
  2
      int i=0;
  3
      lNode *p;
  4
      while(i!=999999){       
  5
          cin>>i;
  6
          if(i!=999999){
  7
              p=(lNode*)malloc(sizeof(lNode));
  8
              p->data=i;
  9
              p->next=l->next;
  10
              l->next=p;
  11
          }       
  12
      }
  13
      return 1;
  14
  }
  

• 主函数

  xxxxxxxxxx
  5
  1
  int main(){
  2
      linkList link;
  3
      initList(link);                 //链表初始化 
  4
      insertHead(link);               //尾插法创建链表 
  5
  } 
  

运行效果和尾插法一样。

头插法图像示例：

4.2 单链表的插入

核心思路是将插入位置前一个结点的指针域指向新建立的结点，再将新节点的指针与指向后一个结点(前一个结点指针域中的值为后一个结点)。

代码如下：

xxxxxxxxxx
25
1
//按序号插入
2
bool insertVaule(linkList &l,int local,int e){  //local表示要插入位置，e表示插入的值
3
    lNode *p,*head=l;                           
4
    int i;
5
    p=(lNode*)malloc(sizeof(lNode));
6
    if(p==NULL||local<1) return 0;
7
    p->data=e;                                  //建立新节点p
8
    while(head->next!=NULL&&i<local-1){         //找到要插入位置的上一个结点
9
        head=head->next;
10
        i++;
11
    }
12
    p->next=head->next;                         //将新节点p的指针域指向后一个结点
13
    head->next=p;                               //前一个结点指针域指向新节点p
14
    return 1;
15
} 
16
//前插操作:将s结点插入到p结点之前
17
bool InsertPriorNode (LNode *p,LNode *s){
18
    if (p==NULL||S==NULL) return false;
19
    s->next=p->next;                //s指针与连接到p结点的后继
20
    p->next=s;                      //s连到p之后
21
    ElemType temp=p->data;          //交换数据域部分
22
    p->data=s->data;
23
    S->data=temp;
24
    return true;
25
}

主函数：

xxxxxxxxxx
7
1
int main(){
2
    linkList link;
3
    initList(link);                 //链表初始化 
4
    insertTail(link);               //尾插法创建链表 
5
    insertVaule(link,3,66);         //按号插入 
6
    printlist(link);                //链表遍历  
7
}  

指定结点前插操作：

输入：1，2，3，4，5

运行结果：1，2，3，66，4，5

4.3 单链表的删除

通过按照输入序号删除对应结点，其原理和上面的插入类似。

xxxxxxxxxx
25
1
//按序号删除
2
bool deletaList(linkList &l,int number){
3
    int i=0;
4
    lNode *p=l,*tail;               //tail指针存放的要删除的结点
5
    if(number<=0){
6
        return 0;
7
    }
8
    while(p!=NULL&&i<number-1){     //找到删除结点的前一个结点
9
        p=p->next;
10
        i++;
11
    }
12
    tail=p->next;                   //将tail指向要删除结点地址
13
    p->next=tail->next;             //将前一个结点指针域指向被删除结点后一个结点
14
    free(tail);                     //释放要删除结点
15
    return 1;
16
} 
17
//删除指定结点p
18
bool DeleteNode (LNode *p){
19
    if (p==NULL) return false;
20
    LNode *q=p->next;               //令q指向*p的后继结点
21
    p->data=p->next->data;          //和后继结点交换数据域
22
    p->next=q->next;                //将*q结点从链中“断开”
23
    free(q);                        //释放后继结点的存储空间
24
    return true;
25
}

主函数代码：

xxxxxxxxxx
7
1
int main(){
2
    linkList link;
3
    initList(link);                 //链表初始化 
4
    insertTail(link);               //尾插法创建链表 
5
    deletaList(link,3);             //按序号删除
6
    printlist(link);                //链表遍历  
7
}  

关于删除指定节点p，其本质就是将p的后继结点复制给p结点，再释放后继结点，并将p结点重新指向下一个结点。这种方法有个局限性，就是我们在删除最后一个结点时，由于后一个结点为null所以程序会出错，我们就只能使用传统办法循环一个个找了。

输入：1，2，3，4，5

运行结果：1，2，4，5

4.4 链表的查找

最常用的查找是按值查找和按序号查找

xxxxxxxxxx
33
1
//按值查找
2
bool findVaule(linkList &l,int d){  //d代表要查找的值
3
    lNode *p=l;
4
    while(p!=NULL){
5
        if(p->data==d){             //如果找到要查找的值d返回1
6
            return 1;
7
        }
8
        p=p->next;
9
    }
10
    return 0;
11
    
12
} 
13

14
//按号查找
15
int findNumber(linkList &l,int num){//表示返回第num个结点的值
16
    int i=0;
17
    if(num<=0){
18
        return 0;
19
    }
20
    lNode *p=l;
21
    while(p!=NULL&&i<num){          //找到这个结点，并返回结点值域中的值
22
        p=p->next;
23
        i++;
24
    }
25
    return p->data;
26
} 
27
//对单链表进行打印 
28
void printlist(linkList &l){
29
    while(l->next!=NULL){
30
        cout<<l->next->data<<endl;
31
        l=l->next;
32
    }
33
}