作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
严蔚敏《数据结构》（C语言版）【教材精讲＋考研真题解析】讲义与视频课程【36小时高清视频】试读：
视频讲解教师简介
耿佳，讲师，北京交通大学中国产业安全研究中心博士后，信息管理方向。硕士毕业于首都师范大学信息工程学院，在高校及职业培训机构讲授计算机课程，主讲课程多为计算机考研考博课程，如数据结构，计算机网络，人工智能，C语言程序设计等。深受学生喜爱，了解学生学习心理，具备教育学专业知识，所教学生成绩优异。
授课特点：教学思路清晰，内容条理性强，重点难点突出，语言清晰流畅。
第一部分 教材精讲[视频讲解]
第1章 绪 论[视频讲解]
1.1 什么是数据结构
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
1.2 基本概念和术语
一、基本概念和术语
数据（Data）：是对客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（Data Element）：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项（Data Item）组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C＝{‘A’，‘B’，…，‘Z’}。
数据结构（Data Structure）：是指相互之间存在一种或多种特定关系的数据元素的集合。
结构：元素之间的相互联系（关系）。四种基本类型：
①集合：结构中的数据元素除了“同属于一个集合”的关系外，没有其他关系；
②线性结构：结构中的数据元素之间存在一对一的关系；
③树形结构：结构中的数据元素之间存在一对多的关系；
④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
二、数据结构的形式定义
数据结构的形式定义是一个二元组：Data_Structure＝（D，S），其中，D是数据元素的有限集，S是D上关系的有限集。
数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
三、数据结构的存储方式
存储结构：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系的表示。
元素的关系的表示方法：
①顺序映像的特点，用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）。
②非顺序映像的特点，借助指示元素存储地址的的指针（pointer）来表示数据元素之间的逻辑结构（关系）。
对应两种存储结构：
①顺序存储结构，数据元素存放的地址是连续的；
②链式存储结构，数据元素存放的地址是否连续没有要求。
数据结构的三个组成部分：
①逻辑结构，数据元素之间逻辑关系的描述D_S＝（D，S）。
②存储结构，数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
③数据操作，对数据要进行的运算。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
四、数据类型
数据类型（Data Type）：指的是一个值的集合和定义在该值集上的一组操作的总称。
数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型、指针类型、空类型和构造类型。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
五、数据结构的运算
数据结构的主要运算包括：（1）建立（Create）一个数据结构；（2）消除（Destroy）一个数据结构；（3）从一个数据结构中删除（Delete）一个数据元素；（4）把一个数据元素插入（Insert）到一个数据结构中；（5）对一个数据结构进行访问（Access）；（6）对一个数据结构（中的数据元素）进行修改（Modify）；（7）对一个数据结构进行排序（Sort）；（8）对一个数据结构进行查找（Search）。
1.3 抽象数据类型的表示与实现
抽象数据类型（Abstract Data Type，简称ADT）：是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：ADT＝（D，S，P），其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT的一般定义形式是：
其中数据对象和数据关系的定义用伪码描述。
基本操作的定义格式是：
其中，初始条件描述的是操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息；操作结果描述的是操作正常完成之后，数据结构的变化状况和应返回的结果；若初始条件为空，则省略之。
1.4 算法与算法分析
一、算法
算法（Algorithm）：是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下五个特性：
①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
②确定性：算法中每一条指令必须有确切的含义，不能存在二义性。且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法具有有穷性，程序可以在无限循环中执行，这意味着不是所有的计算机程序都是算法。
二、算法设计的要求
评价一个好的算法有以下几个标准：
①正确性（Correctness）：算法应满足具体问题的需求。
②可读性（Readability）：算法应容易供人阅读和交流。可读性好的算法有助于人对算法的理解和修改。
③健壮性（Robustness）：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
④通用性（Generality）：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。
⑤效率与低存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。
三、算法效率的度量
算法执行时间通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：（1）事后统计
计算机内部进行执行时间和实际占用空间的统计。
缺陷：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。（2）事前分析
求出该算法的一个时间界限函数。时间取决于下列因素：
①依据算法选用何种策略；
②问题的规模；
③程序设计的语言；
④编译程序所产生的机器代码的质量；
⑤机器执行指令的速度；
撇开软硬件等有关部分因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
算法中基本操作重复执行的次数是问题规模n的某个函数f（n），其时间量度记作T（n）＝O（f（n）），称作算法的渐近时间复杂度（Asymptotic Time complexity），简称时间复杂度。
一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。“O”的定义：若f（n）是正整数n的一个函数，则O（f（n））表示∃M≥0，使得当n≥n时，|f（n）|≤M|f（n）|。00
表示时间复杂度的阶有：
①O（1），常量时间阶
②O（n），线性时间阶
③O（logn），对数时间阶
④O（nlogn），线性对数时间阶k
⑤O（n），k≥2，k次方时间阶【例1】两个n阶方阵的乘法。
由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n＝33n，时间复杂度为T（n）＝O（n）。【例2】{++x;s=0;}
将x自增看成是基本操作，则语句频度为1，即时间复杂度为O（1）。如果将s＝0也看成是基本操作，则语句频度为2，其时间复杂度仍为O（1），即常量阶。【例3】for(i=1;i<=n;++i){++x;s+=x;}
语句频度为：2n，其时间复杂度为：O（n），即为线性阶。【例4】22
语句频度为：2n，其时间复杂度为：O（n），即为平方阶。mm－1【定理】若A（n）＝an＋an＋…＋an＋a是一个m次mm－110m多项式，则A（n）的时间复杂度为O（n）。【例5】
语句频度为：1＋2＋3＋…＋n－2＝（1＋n－2）×（n－2）/2＝2（n－1）（n－2）/2＝n－3n＋2。2
时间复杂度为O（n），即此算法的时间复杂度为平方阶。
一个算法时间为O（1）的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个2时间为O（n）的算法则由一个二次多项式来限界。
以下六种计算算法时间的多项式是最常用的。其关系为：2
O（1）＜O（logn）＜O（n）＜O（nlogn）＜O（n）＜3O（n）nn
指数时间的关系为：O（2）＜O（n!）＜O（n）
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。【例6】素数的判断算法。
嵌套的最深层语句是i＋＋；其频度由条件（（n%i）!＝0&&i*1.01/2＜sqrt（n））决定，显然i*1.0＜sqrt（n），时间复杂度O（n）。【例7】起泡排序法。
最好情况：0次。
最坏情况：1＋2＋3＋⋯＋n－1＝n（n－1）/2。2
平均时间复杂度为：O（n）。
四、算法的空间分析
空间复杂度（Space complexity）：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S（n）＝O（f（n）），其中：n为问题的规模（或大小）。
该存储空间一般包括三个方面：
①指令常数变量所占用的存储空间；
②输入数据所占用的存储空间；
③辅助（存储）空间。
算法的空间复杂度指的是辅助空间。
一维数组a[n]：空间复杂度O（n）。
二维数组a[n][m]：空间复杂度O（n*m）。
第2章 线性表[视频讲解]
2.1 线性表的类型定义
一、线性表的定义
线性表（Linear List）：是由n（n≥0）个数据元素（结点）a，a，12…，a组成的有限序列。该序列中的所有结点具有相同的数据类型。n其中数据元素的个数n称为线性表的长度。
当n＝0时，称为空表。当n＞0时，将非空的线性表记作：（a，1a，…，a）。2n
a称为线性表的第一个（首）结点，a称为线性表的最后一个1n（尾）结点。a，a，…，a都是a（2≤i≤n）的前驱，其中a是a12i－1ii－1i的直接前驱；a，a，…，a都是a（1≤i≤n－1）的后继，其中ai＋1i＋2nii是a的直接后继。＋1i
二、线性表的逻辑结构
线性表中的数据元素a所代表的具体含义随具体应用的不同而不i同，在线性表的定义中，a只不过是一个抽象的表示符号。i
①线性表中的结点可以是单值元素（每个元素只有一个数据项）。【例1】26个英文字母组成的字母表：（A，B，C、…、Z）【例2】某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6，17，28，50，92，188）【例3】一副扑克的点数：（2，3，4，…，J，Q，K，A）
②线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。【例4】某校2001级同学的基本情况：{（‘2001414101’，‘张里户’，‘男’，06/24/1983），（‘2001414102’，‘张化司’，‘男’，08/12/1984），…，（‘2001414102’，‘李利辣’，‘女’，08/12/1984）}。
③若线性表中的结点是按值（或按关键字值）由小到大（或由大到小）排列的，称线性表是有序的。
④线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。
⑤对线性表的数据元素可进行访问、插入和删除操作。
三、线性表的抽象数据类型定义【例5】假设：有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。要求对线性表作如下操作：扩大线性表LA，将存在于LB中而不存在于LA中的数据元素插入到LA中去。
操作步骤：
1．从线性表LB中依次查看每个数据元素；
2．依值在线性表LA中进行查访；
3．若不存在，则插入之。
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即a≥a或a≤a（i＝2，3，ii－1ii－1…，n），则称该线性表为有序表（Ordered List）。【例6】假设：LA＝（3，5，8，11），LB＝（2，6，8，9，11，15，20）。对集合LA和LB而言，值相同的数据元素必定相邻。
要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。
2.2 线性表的顺序表示与实现
一、线性表的顺序存储结构
顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：
①线性表的逻辑顺序与物理顺序一致；
②数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
设有非空的线性表：（a，a，…，a）。顺序存储如图2-1所12n示。
图2-1 线性表的顺序存储表示
在具体的机器环境下：设线性表的每个元素需占用1个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i＋1个数据元素的存储位置Loc（a）和第i个数据元素的存储i＋1位置Loc（a）之间满足下列关系：Loc（a）＝Loc（a）＋1。ii＋1i
线性表的第i个数据元素a的存储位置为：Loc（a）＝Loc（a）ii1＋（i－1）*l
在高级语言（如C语言）环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度的属性，所以用结构类型来定义顺序表类型。
二、顺序表的基本操作
顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。
1顺序线性表初始化
2顺序线性表的插入
在线性表L＝（a，…，a，a，a，…，a）中的第i（1≤i≤n）1i－1ii＋1n个位置上插入一个新结点e，使其成为线性表：L＝（a，…，a，1i－1e，a，a，…，a）ii＋1n（1）实现步骤
①将线性表L中的第i个至第n个结点后移一个位置。
②将结点e插入到结点a之后。i－1
③线性表长度加1。（2）算法描述（假定下标从1开始，与上述L一致）（3）时间复杂度分析
在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个元素之前插入结点的概率为P，不失一般i性，设各个位置插入是等概率，则P＝1/（n＋1），而插入时移动结i点的次数为n－i＋1。总的平均移动次数：E＝∑P*（n－i＋1）（1inserti≤i≤n），因此E＝n/2。insert
即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。
3顺序线性表的删除
在线性表L＝（a，…，a，a，a，…，a）中删除结点1i－1ii＋1na（1≤i≤n），使其成为线性表：i
L＝（a，…，a，a，…，a）1i－1i＋1n（1）实现步骤
①将线性表L中的第i＋1个至第n个结点依此向前移动一个位置。
②线性表长度减1。（2）算法描述（3）时间复杂度分析
删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中删除第i个元素的概率为P，不失一般性，设删除i各个位置是等概率，则P＝1/n，而删除时移动结点的次数为n－i。则i总的平均移动次数：E＝∑P*（n－i）（1≤i≤n），因此E＝（ndeleteidelete－1）/2。
即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。
4顺序线性表的查找定位删除
在线性表L＝（a，a，…，a）中删除值为x的第一个结点。12n（1）实现步骤
①在线性表L查找值为x的第一个数据元素；
②将从找到的位置至最后一个结点依次向前移动一个位置；
③线性表长度减1。（2）算法描述（3）时间复杂度分析
时间主要耗费在数据元素的比较和移动操作上。首先，在线性表L中查找值为x的结点是否存在；其次，若值为x的结点存在，且在线性表L中的位置为i，则在线性表L中删除第i个元素。
设在线性表L删除数据元素概率为P，不失一般性，设各个位置i是等概率，则P＝1/n。i
比较的平均次数为
因此E＝（n＋1）/2。compare
删除时平均移动次数为
因此E＝（n－1）/2。delete
平均时间复杂度：E＋E＝n，即为O（n）。comparedelete
2.3 线性表的链式表示与实现
一、线性表的链式存储结构
链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
存储链表中结点的一组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
链表中结点的逻辑顺序和物理顺序不一定相同。
为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址（或位置），称为指针（pointer）或链（link），这两部分组成了链表中的结点结构，如图2-2所示。
图2-2 链表结点结构
链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结点只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一个头结点（头指针）head指向第一个结点。头结点的数据域可以不存储任何信息（或存储链表长度等信息）。
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。【例1】线性表L＝（bat，cat，eat，fat，hat），其带头结点的单链表的逻辑状态和物理存储方式，如图2-3所示。
图2-3 带头结点的单链表的逻辑状态、物理存储方式
1结点的描述与实现
C语言中用带指针的结构体类型来描述
2结点的实现
结点是通过动态分配和释放来实现的，即在需要时分配内存，不需要时释放内存。实现时分别使用C语言提供的标准函数：malloc（），realloc（），sizeof（），free（）。
动态分配：p＝（LNode*）malloc（sizeof（LNode））；
函数malloc申请了一大小为LNode的内存空间作为结点空间，并将其首地址放入指针变量p中。
动态释放：free（p）；
系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc函数时的返回值。
3最常用的基本操作及其示意图（1）结点的赋值（2）常见的指针操作
①q＝p；
②q＝p->next；
③p＝p->next；
④q->next＝p；
⑤q->next＝p->next；
二、单线性链式的基本操作
1建立单链表
假设线性表中结点的数据类型是整型，以32767作为结束标志。动态地建立单链表的常用方法有如下两种：头插入法，尾插入法。（1）头插入法建表
从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。
算法描述
试读结束[说明：试读内容隐藏了图片]