数据结构-严蔚敏

引言

教材：清华大学《数据结构C语言版》严蔚敏版

笔记：尘鱼好美著

讲在前面：本笔记所用的代码皆为伪代码。

---

文章目录

• 引言
• • @[toc]
• 第一章、绪论
• • 1.1、什么是数据结构
  • 1.2、基本概念和术语
  • • 数据结构的两个层次
    • 逻辑结构的种类
    • 四种基本的存储结构
    • 数据类型和抽象数据类型
  • 1.3、算法的基本概念
  • • 算法和算法分析
  • 1.4、算法的时间复杂度
  • • 渐进时间复杂度
  • 1.5、算法的空间复杂度
  • • 渐进空间复杂度
  • 1.6、作业
• 第二章、线性表的类型定义
• • 2.1、线性表的类型定义
  • 2.2、类C语言有关操作补充
  • 2.3、线性表的顺序表示和实现
  • 2.4、线性表的基本操作
  • 2.5、顺序表的插入和删除
  • 2.6、顺序表的查找
  • 2.7、线性表的链式表示和实现
  • 2.8、单链表的插入和删除
  • 2.8、单链表的插入和删除

第一章、绪论 1.1、什么是数据结构

---

1.2、基本概念和术语

数据：

• ​ 是能输入计算机且能被计算机处理的各种符号的集合
• ​ 是信息的载体
• ​ 是对客观事物符号化的认识
• ​ 能够被计算机识别、存储和加工

包括：

• ​ 数值型的数据：整数、实数等
• ​ 非数值型的数据集：文字、图像、图形、声音等

数据元素：是数据的基本单位（相当于数据库的元组）

数据元素在计算机程序中通常作为一个整体进行考虑和处理。

也简称为元素，或称为记录、结点或顶点。

一个数据元素由若干个数据项组成

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

相当于数据库中的属性；在数据库中我们也曾叫作数据项。

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

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

数据结构包含以下三个方面的内容

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

---

数据结构的两个层次

逻辑结构

• 描述数据元素之间的逻辑关系
• 和数据的存储无关，独立于计算机
• 是从具体问题抽象出来的数学模型

物理结构（存储结构）

• 数据元素及其关系在计算机存储器中的结构（存储方式）
• 是数据结构在计算机中的

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

• 存储结构是逻辑关系的映像与元素本身的映像
• 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
• 两者综合起来建立了数据元素之间的结构关系

---

逻辑结构的种类

划分方法一：

线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。例如：线性表，栈，队列，图

非线性结构：一个结点可能有多个直接前驱和直接后继。例如：树，图

划分方法二：

集合结构：结构中的数据元素直接除了同属于一个集合的关系外，无任何其他关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

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

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

---

四种基本的存储结构

顺序存储结构：

用一组连续的存储单元一次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

C语言中用数组来实现顺序存储结构

链式存储结构：

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。

C语言中用指针来实现链式存储结构

索引存储结构：

在存储结点信息的同时，还建立附加的索引表。

散列存储结构：

根据结点的关键字直接计算出该结点的存储地址。

---

数据类型和抽象数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。

例如，C语言中：

• 提供int,char,float,double等基本数据类型
• 数组、结构、共用体、枚举等构造数据类型
• 还有指针、空类型
• 用户还可用typedef自己定义数据类型

但是上面说的这些仅仅只能够去表示一些简单的数据类型，对于栈、线性表、队列、树这些，很明显表示不了。

高级语言中的数据类型明显地或隐含的规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。

例如：C语言定义变量i为int类型，就表示i是[-min，max]范围的整数，在这个整数集上做加减乘除操作。

所以，什么是数据类型？

数据类型：是一组性质相同的值的集合以及定义在这个值集上的一组操作的总称。

抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。

• 由用户定义，从问题抽象出数据模型。（逻辑结构）
• 还包括定义在数据模型上的一组抽象运算。（相关操作）
• 不考虑计算机内的具体存储结构和运算的具体实现算法

一个抽象数据类型的定义格式如下：

ADT 抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名

其中：数据对象、数据关系的定义用伪代码描述。

基本操作的定义格式：

基本操作名<参数表>
	初始条件：<初始条件描述>
	操作结果：<操作结果描述>

说明：

参数表：参数表中引用参数以&开头，表示不仅可以作为参数输入值，还能返回操作后的结果。

初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应的，并返回相应出错信息。若初始条件为空，则省略

操作结果：说明操作正常完成之后，数据结构的变化状况和返回的结果。

---

1.3、算法的基本概念 算法和算法分析

算法：是对特定问题求解步骤的一种描述

算法的描述：

自然语言：语言、中文

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

伪代码：类语言：类C语言

程序代码：C语言，java语言

算法和程序：

算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。

程序是用某种设计语言对算法的具体实现。

算法的重要特性：

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一地一条执行路径，即对于相同的输入只能得到相同的输出。

可行性：一个算法是能行的，即算法种描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法可以有零个或多个输入。

输出：一个算法可以有一个或多个输出。

算法设计的要求：

正确性：算法应当满足具体问题的需求。

可读性：算法要方便人对算法的理解。

健壮性（鲁棒性）：算法能应对非法情况

高效性：要求花费尽量少的时间和尽量低的存储需求

算法分析：

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

算法效率从以下两个方面来考虑：

时间效率：指的是算法所耗费的时间；

空间效率：指的是算法执行过程中所耗费的存储空间。

时间效率和空间效率有时候是矛盾的。

算法时间效率的度量：

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。

两种度量方法：

事后统计：将算法实现：测算其时间和空间开销。

缺点：

1. 必须先运行依据算法编制的程序。
2. 所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时任意掩盖算法本身的优劣。
3. 与编程语言的选择有关。
4. 有些算法不能事后统计。

**事前分析：**对算法所消耗资源的一种估算方法

---

1.4、算法的时间复杂度 渐进时间复杂度

若有某个辅助函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度。

一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T（n）表示。

为了便于比较不同算法的时间效率，我们仅比较它们的数量级

如何计算：

1. 找出语句频度最大的那条语句作为基本语句（最复杂的操作，一般是循环）
2. 分析该操作的执行次数X和问题规模n的关系X = f(n)
3. X的数量级O(x)就是算法时间复杂度T(n)

怎么找频度最大的语句？

• 算法中重复执行次数和算法的执行时间成正比的语句
• 对算法运行时间的贡献最大
• 执行次数最多

x = 0;y = 0;
for(int k = 0;k < n;k++)
	x++;
//下面的循环语句有两层n，即n的平方，也就是所谓的语句频度最大的那条语句。
for(int i = 0;i 
由此我们可知：时间复杂度是由嵌套最深层语句的频度决定的。
 
//三层循环，时间复杂度n的三次方
for(i = 1;i<=n;i++)
	for(j=1;j<=1;j++)
		for(k=1;k<=j;k++)
			x=x+1;
 
i = 1;
while(i<=n)
	i = i*2;
 
三种复杂度：
 
**最坏时间复杂度：**考虑输入数据“最坏”的情况。
 
平均时间复杂度：考虑所有输入数据都等概率出现的情况。
 
**最好时间复杂度：**考虑输入数据“最好”的情况。
 
一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
 
对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度。
 
加法规则：
 
T(n) = T1(n)+T2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))
 
乘法规则：
 
T(n) = T1(n)T2(n) = O(f(n))O(g(n)) = O(f(n)g(n))
 
算法时间效率的比较：
 
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
 
 
实际上上面的表不用记，只需要利用高数的函数图形去理解就行。
 
速记口诀：常对幂指阶
 
总结：
 
顺序执行的代码只会影响常数项，可以忽略
只需要挑循环中的一个基本操作与分析他的执行次数与n的关系即可
如果有多层嵌套循环，只需关注最深层循环了几次。
 
 
1.5、算法的空间复杂度 
渐进空间复杂度 
**空间复杂度：**算法所需存储空间的度量，
 
记作：S(n) = O(f(n))
 
其中n为问题的规模（或大小）
 
算法要占据的空间：
 
算法本身要占据的空间，输出/输出，指令，常数，变量等
算法要使用的辅助空间
 
若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
 
 
1.6、作业 
一、简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
 
数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
 
数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行处理和考虑。
 
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
 
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
 
存储结构：数据结构在计算机中的表示
 
数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
 
抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。
 
二、试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
 
三、设有数据结构（D,R）其中D={d1,d2,d3,d4},R ={r}，r={(d1,d2),(d2,d3),(d3,d4)}。试着按图论中图的画法惯例画出其逻辑结构图。
 
四、试着仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义。
 
第二章、线性表的类型定义 
2.1、线性表的类型定义 
线性表是具有相同数据类型的n个数据元素的有限序列。
 
其中n为表长，当n=0的时候线性表是一个空表。若用L命名线性表，即：
 
 
 
L = (a1,a2,a3….,an)
 
 
这里有必要提一下数据元素。
 
数据元素：
 
​ 在数据库中，我们知道一个事物的特征我们叫做数据项，数据项的集合我们叫记录型，记录型的实例我们称为记录，在关系型数据库里叫做元组。实际上，数据元素即为元组。如果一个线性表里含有大量记录（数据元素），我们称其为文件。
 
​ 在C语言里，我们很喜欢用结构体去表示线性表中的一个数据元素。
 
那么定义里具有相同数据类型是什么意思？
 
我们知道，假如现在有一个表：
 
+--------+------------+----------+

| DEPTNO | DNAME   | LOC   |

+--------+------------+----------+

|   10 | ACCOUNTING | NEW YORK |

|   20 | RESEARCH  | DALLAS  |

|   30 | SALES   | CHICAGO |

|   40 | OPERATIONS | BOSTON  |

+--------+------------+----------+
 
那么我们知道，第二条记录和第一条记录应该是有相同特征的，比如说第二个员工不可能有个特征是性别而第一个员工就没有，不可能出现这种事。
 
线性表中的顺序问题
 
线性表里有很多元素，比如a1,a2。a2相对于a1来说排在后面，所以我们叫做直接后继。a1相对于a2来说排在前面，所以我们叫他直接前驱。
 
很显然，倒数第二个元素只有一个直接后继，第二个元素只有一个直接前驱。
 
在非空表里每个数据元素都有自己对应的位置，我们叫做位序。比如在线性表中，a1排在第一位，我们说a1排在线性表中的第一位序。
 
对线性表有啥操作？
 
 
这里面要扯一个问题了，关于&修饰符的问题。
 
在C语言里面我们知道，用&可以找到某个变量或其他量的地址。
 
比如：
 
		#include 
		int main()
		{
		    const int a = 10;
		    //a = 100;
		    int* p = &a;
		    *p = 100;
		    printf("%d",a);
		    return 0;
}
 
说明：在这里面我们可以看到，我们用&调取了常量a的地址，然后把地址赋给了指针，让指针指向这个常量。
 
实际上，这个符号在C++也有个功能。他能够把在函数里参数修改的结果带回主函数。
 
也就是说，要想把主函数的实参带到函数里面修改再带回来，可以在函数引用参数里添加一个&。
 
 
2.2、类C语言有关操作补充 
一、在顺序表的定义中，我们会看到以下的情况：
 
typedf struct{
	ElemType data[];
	int length;
}SqList;//顺序表类型
 
这时候我们会觉得很奇怪，从来没有看过ElemType这种类型，这是怎么回事？
 
这实际上取决于你要用什么数组，如果你的数组打算放int，那么你可以把ElemType的位置换成int，或者通过typedef重新定义int为ElemType。
 
二、在数组的定义中，我们会看到这种情况:
 
typedf struct{
	ElemType data[MaxSize];
	int length;
}SqList;//顺序表类型
 
但是有时候也会遇到这种情况
 
typedf struct{
	ElemType *data;
	int length;
}SqList;//顺序表类型
 
实际上，如果是data[MaxSize]，那么我们会发现一旦MaxSize确定下来了，那么我们的数组长度也就确定下来了。
 
但是如果我们用的是data，那么data是一个指针变量，我们可以通过malloc函数即L.data=(ElemType)malloc(sizeof(ElemType)*MaxSize)，来返回malloc函数申请的一片内存的地址，然后把地址赋给data数组，这样数组的长度由数组元素的字节长度和数组的最大容纳量来确定了。
 
这实际上就是静态数组分配和动态数组分配的区别，后面会讲到。
 
3、关于建链表我们总是会用到几个函数
 
malloc函数，用于开辟m字节长度的地址空间，并且返回这段空间的首地址。
 
sizeof函数，计算变量x的长度
 
free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量。
 
需要注意的是，如果要用到以上的函数，需要加载头文件：
 
4、关于参数传递
 
函数调用时抄送给形参表的实参必须与形参三个一致
 
 
 
类型，个数，顺序
 
 
当指针变量作为参数时，有两种情况，第一种
 
形参变化影响实参
 
 
说明：他之所以能影响是因为他在函数里面定义了两根指针，两根指针把原来主函数指针指的两个元素的值给调换了。
 
形参变化不影响实参
 
 
说明：这个之所以影响不了是因为他在函数里面定义了两根指针，两根指针互换了，函数结束，函数里定义的指针也消失，相当于白干。
 
 
当数组名作参数
 
 
  
传递的是数组的首地址
对形参数组所做的任何改变都将反映到实参数组中
 
 
 
说明：数组传入，则数组的首地址传入，那么a[]传入后实际上动的是b[]地址的值，函数消失，a的值被改变。
 
引用类型做参数
 
什么是引用？
 
引用就是他用来给一个对象提供一个替代的名字。
 
 
引用类型做形参的三点说明
 
1、传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。
 
2、引用类型作形参，在内存中并没有产生实参的副本，他直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。
 
3、指针参数虽然能达到和使用引用类型的效果，但在被调函数中需要重复使用“指针变量名”的形式进行计算，这很任意产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。
 
2.3、线性表的顺序表示和实现 
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
 
这里实际上就是说，假如我们知道了一个数据元素占几个字节（数据元素的大小），那么既然连续，就必定会
 
     
      
       
        
         L
        
        
         O
        
        
         C
        
        
         （
        
        
         
          a
         
         
          (
         
        
        
         i
        
        
         +
        
        
         1
        
        
         )
        
        
         ）
        
        
         =
        
        
         L
        
        
         O
        
        
         C
        
        
         （
        
        
         
          a
         
         
          i
         
        
        
         ）
        
        
         +
        
        
         l
        
       
       
         LOC（a_(i+1)） = LOC（a_i）+l 
       
      
     LOC（a(​i+1)）=LOC（ai​）+l
 这种情况，其中l代表他们一个数据元素的大小。
 
和学数学一样，既然有这种相邻关系，就存在
 
     
      
       
        
         L
        
        
         O
        
        
         C
        
        
         （
        
        
         
          a
         
         
          i
         
        
        
         ）
        
        
         =
        
        
         L
        
        
         O
        
        
         C
        
        
         （
        
        
         
          a
         
         
          1
         
        
        
         ）
        
        
         +
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         )
        
        
         l
        
       
       
         LOC（a_i） = LOC（a_1）+(i-1)l 
       
      
     LOC（ai​）=LOC（a1​）+(i−1)l
 这样的不相邻的关系。
 
其中，我们把a1的地址称为基地址。
 
这种表示一般被我们叫做顺序存储结构或者叫做顺序映像。这种结构的线性表我们叫顺序表。
 
顺序表的特点：
 
地址连续，依次存放，随机存取，类型相同
 
这不禁让我们想起可以用数组表示顺序表。
 
但是这里要注意一点，线性表长可变，而数组长度是不可动态定义。这时候我们用一个变量(length)来表示顺序表的长度属性。
 
那如何用C语言去定义顺序表呢？
 
我们通常利用结果提来创建一个线性表
 
 
其中线性表包含数据元素和长度。所以如果写成代码如下：
 
#define MAXSIZE 100
typedef struct{
	ElemType elem [MAXSIZE];
	int length;
}SqList;
 
静态分配方法如下：
 
 
说明：
 
最开始我们定义了一个线性表，在里面设置了用没有初始化的数组（静态数组）去存放数据元素，比如数组是int data[3] = {a1,a2,a3}。
 
而后我们又定义了顺序表的长度和顺序表的数据类型别名。
 
定义完顺序表后，我们定义了一个函数初始化顺序表（因为没有初始化数组里的数据元素会随机分配），我们把所有数据元素都设置成0，并且把顺序表定义成空表（不可省略）。
 
在主函数中我们声明了一个顺序表，并且初始化了这个顺序表。
 
当然，其实设置默认值的步骤可以省略，因为我们最开始顺序表是空表，空表里面没有元素，所以访问不到东西，设置为0的实际上是数组的各个元素。
 
访问元素最好不要通过for循环，而应该用线性表的基本操作（GetElem）去访问。
 
看完静态分配我们想到一个问题，由于静态数组是不可改变的，那如果里面的数据元素存满了怎么办？
 
这时候就可以放弃治疗了。
 
那有人会说多申请点内存空间不就行了？
 
 
动态分配方法如下：
 
 
说明：
 
左上角是定义线性表，这里由于是动态定义，所以没有赋值，只是把原来的静态数组换成了整型指针，这个指针指向一片malloc申请好的内存空间，我们在这里可以理解这片空间是一个数组，指针指向首地址，也就是数组名。
 
右上角是定义了一个初始化线性表的函数，我们首先用malloc函数申请了一片连续的存储空间，malloc右边的()里面指的是malloc申请的空间长度，具体到例子里面malloc申请了线性表数据元素的长度乘int字节大小，malloc左边()指的是执行完右边括号操作后返回的东西，这里具体到例子是返回了一个指针，这个指针我们赋给了data指针变量，是为了以后方便用这个指针来扩展线性表长度，还有要注意的问题是，由于我们定义的指针是int类型的，所以malloc返回的指针也必须是int类型的。后面我们又定义了线性表目前的长度以及他所能容纳的数据元素的容量数。
 
右上角千言万语说起来很复杂，我们可以理解成我们设置了一个动态的内存空间，但是现在还没去用，现在处于空表状态，如果后面添加了数据元素了，就会占用申请的空间。
 
在左下角的主函数中，我们声明了一个顺序表，然后初始化了顺序表。
 
在右下角我们定义了一个增加顺序表长度的方法，如果长度不够，这时候我们增加顺序表长度，len代表要加的长度，然后利用malloc去申请一片新的内存空间。在这时，我们申请的内存空间相当于原来存满的空间复制了一份加上新增加的空间，然后把申明数组的指针指向新的内存区域，然后再把老的那片满的内存空间通过free释放（删除）掉。
 
顺序表示意图：
 
 
顺序表的特点：
 
1、随机访问，即可以在O(1)时间内找到第i个元素。
 
2、存储密度高，每个节点只存储数据元素。
 
3、拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）。
 
4、插入、删除操作不方便，需要移动大量元素。
 
 
2.4、线性表的基本操作 
线性表有哪些基本操作呢？
 
 
下面我们一一来介绍：
 
在这之前我们需要介绍一下操作算法中用到的预定义常量和类型。
 
 
 
2.5、顺序表的插入和删除 
插入基本操作：
 
ListInsert(&L,I,e):插入操作。在表L中的第i个位置上插入指定元素e。
 
说明：这里用到了&L，说明要把顺序表传入这个函数，然后经过插入操作后再返回这个L
 
插入操作：
 
 
说明：
 
在定义插入函数的里面，L传入函数，首先定义了一个循环，让j等于顺序表的长度，如果j没有到插入的地方，那么j自减。每一次循环里，每个元素都会往后移动，直到给插入元素的地址空出位置，然后在该位置放入插入的元素e，此时要增加顺序表的长度1。
 
注意：在增加元素的时候一定要检查插入之前是否存满了，为此，我们改动了上面的代码。
 
 
说明：检查i的合法性判断。好的算法，应该具有“健壮性”。能处理异常情况，并且给使用者反馈。
 
关于插入操作的时间复杂度
 
我们在关注时间复杂度的时候，通常都是直接看最内层循环。
 
如果考虑最好情况：新元素插入到表尾，不需要移动元素，i = n+1，循环0次；最好时间复杂度为O(1)
 
最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动，i = 1，循环n次，最坏时间复杂度 为O(n)
 
平均情况：假设新元素插入每个位置的概率都相等，即p = 1/(n+1)，i = 1，循环n次，i = 2，循环n-1次，也就是1+2+3+…+n，根据等差数列求和公式，也就是n(n+1)/2
 
平均循环概率 = 平均复杂度 = np = n/2 = O(n)
 
删除基本操作
 
ListDelete(&L,I,e)：删除操作。删除表中第i个位置的元素，并用e返回删除元素的值。
 
删除操作：
 
 
说明：删除方法，有&L，同理，带入L顺序表进去操作后返回，最开始先检查i的合理性，检查成功后，将要删除的值赋给e，然后开始把e这个i位置的元素往前移，把要删除的元素挤掉，然后线性表长度减一，返回成功字样。
 
关于插入操作的时间复杂度就不细说了，实际上和插入的时间复杂度一模一样，计算方法也大同小异。
 
 
2.6、顺序表的查找 
顺序表的按位查找：
 
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
 
实际操作:
 
ElemType GetElem(SepList L,int i){

return L.data[i-1];

}
 
说明：这实际上就是访问数组下标，懂了把。
 
按值查找：
 
例如图书表中查找，按照给定书号进行查找，确定是否存在该图书。
 
 
如果存在：输出第几个元素
 
如果不存在：输出0
 
查找步骤：
 
1、在线性表L中查找与指定值e相同的数据元素的位置
 
2、从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号；未找到，返回0
 
 
提示：
 
数据结构考研初试中，手写代码可以直接用“==”，无论ElemType是基本数据类型还是结构类型。
 
 
2.7、线性表的链式表示和实现 
线性表有两种，第一个是我们前面讲到的顺序表，对应顺序存储。第二个是链表，对应链式存储。
 
这里首先要提出一个单链表的概念。
 
单链表也叫线性链表。
 
线性链表
 
线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素。由图可知，每个数据元素ai由两部分组成，一部分放数据元素信息，我们叫做数据域；另外一部分放下一个数据元素地址的信息，我们叫指针域，两部分加起来合称为结点。指针域里面放的地址我们叫指针或者链。n个结点结成一个链表。因为每个结点只放了一个指针域，所以我们又叫单链表或线性链表。
 
 
顺序表优点：可随机存取，存储密度高
 
缺点：要求大片连续空间，改变容量不方便。
 
单链表优点：不要求大片连续空间，改变容量方便
 
缺点：不可随机存取，要耗费一定空间存放指针。
 
怎么定义一个单链表？
 
这里先定义其中一个结点
 
 
定义单链表如下
 
 
说明：
 
首先是头结点部分，在头结点部分，我们把struct重写定义成LNode，*linkList两个数据类型名，第一个名字主要强调定义的结构体为链表，第二个主要强调其为头结点。
 
其次是定义下一个结点。
 
如何初始化一个单链表？
 
 
说明：
 
首先，这是一个不带头结点的单链表。
 
我们定义了链表的第一个结点。
 
在下方，我们写了一个关于初始化的函数，我们把L的值设置为空表，设置成功了返回true，然后我们又写了一个函数，声明了一个指针来指向这个单链表，又将定义好的链表传入InitList函数中初始化。
 
这里我们还可以利用判断语句来判断单链表是否为空，具体做法是查看头指针是否为空，如果是空，则说明链表没有地址，即链表不存在，即链表为空。
 
带头结点的单链表？
 
 
说明：
 
第一段代码写了个结点。
 
第二段开始，我们用malloc函数分配了一片空间，内存为结点的大小，然后返回一个地址给了L，在主函数我们可以注意L是指针。在这里我们设置一个约束：如果头指针L的地址为空，说明链表不存在，添加头结点失败，如果头指针L指向的头结点的下一个数据元素是空，说明链表存在，只是还没添加数据元素，返回添加成功。
 
然后在主函数中声明链表，然后将链表初始化。
 
头结点的好处？
 
不带头结点写代码会更麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。 带头结点写代码好写。
 
加强理解：
 
空表判断：L==NULL。写代码不方便
 
空表判断：L->next==NULL。写代码更方便
 
不带头结点：
 
 
这里会发现头指针所指向的是链表（链表第一个数据元素地址），而不是头结点。这时候如果L = null，说明链表不存在，该表为空。
 
带头结点：
 
 
这里会发现头结点和链表之间接了一个头结点，头结点的下一个数据元素才属于链表。也就是说，如果是空表，应该是P->next = NULL。
 
 
2.8、单链表的插入和删除 
开局先讲原理：
 
说明：看这张图我们可以发现，如果要想在某个位置插入一个结点，只需要改变这个位置前一个位置的结点的指针和自己的指针即可。
 
即：S->next = p->next; p->next = s
 
也就是，把P中存放的指针域（b结点的地址）给改为s指向b的地址，，这样s的下一个结点就是b了；然后，再把s的地址作为p的指针域（p的下一个结点的地址）。这样，s结点成功的添加到了链表里。
 
这里有个地方要注意：
 
这个过程中顺序不能改变，也就是不能变成
 
p->next = s；S->next = p->next
 
假如变成这样，那么p的下一个是s，s的下一个是p的下一个，两句话合成一下，即：s的下一个是（s），所以就会造成b结点后面的链表全部丢失。
 
存在，即链表为空。
 
带头结点的单链表？
 
[外链图片转存中…(img-PSeGYNyd-1633145947472)]
 
说明：
 
第一段代码写了个结点。
 
第二段开始，我们用malloc函数分配了一片空间，内存为结点的大小，然后返回一个地址给了L，在主函数我们可以注意L是指针。在这里我们设置一个约束：如果头指针L的地址为空，说明链表不存在，添加头结点失败，如果头指针L指向的头结点的下一个数据元素是空，说明链表存在，只是还没添加数据元素，返回添加成功。
 
然后在主函数中声明链表，然后将链表初始化。
 
头结点的好处？
 
不带头结点写代码会更麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。 带头结点写代码好写。
 
加强理解：
 
空表判断：L==NULL。写代码不方便
 
空表判断：L->next==NULL。写代码更方便
 
不带头结点：
 
[外链图片转存中…(img-pyGjRxnU-1633145947473)]
 
这里会发现头指针所指向的是链表（链表第一个数据元素地址），而不是头结点。这时候如果L = null，说明链表不存在，该表为空。
 
带头结点：
 
[外链图片转存中…(img-h3mte9vJ-1633145947474)]
 
这里会发现头结点和链表之间接了一个头结点，头结点的下一个数据元素才属于链表。也就是说，如果是空表，应该是P->next = NULL。
 
 
2.8、单链表的插入和删除 
开局先讲原理：
 
说明：看这张图我们可以发现，如果要想在某个位置插入一个结点，只需要改变这个位置前一个位置的结点的指针和自己的指针即可。
 
即：S->next = p->next; p->next = s
 
也就是，把P中存放的指针域（b结点的地址）给改为s指向b的地址，，这样s的下一个结点就是b了；然后，再把s的地址作为p的指针域（p的下一个结点的地址）。这样，s结点成功的添加到了链表里。
 
这里有个地方要注意：
 
这个过程中顺序不能改变，也就是不能变成
 
p->next = s；S->next = p->next
 
假如变成这样，那么p的下一个是s，s的下一个是p的下一个，两句话合成一下，即：s的下一个是（s），所以就会造成b结点后面的链表全部丢失。