23年青岛大学910数据结构强化班第一课时，学长带你走进算...

青大考研校

欢迎大家来听910数据结构专业强化班第一课时，第一节课是讲算法的时间复杂度。

一定要牢记一句话，将算法章基本操作的执行次数作为算法时间复杂度的度量。

常用的时间复杂度比较关系：O(1)< O(logn) < O(n) < O(nlogn) < O(n2)。

计算时间复杂度，具体步骤：

第一步、确定基本操作基本题规模。

第二步、根据基本操作计算出规模的函数F（n），并确定要实行复杂度O（F（N））中最快的一项。

第一步找基本操作，又是以求时间复杂度的为目的前提下重复直销次数和算法的执行时间成正比的操作。一般来说，这种操作组成的算法，当他们都执行完的时候，算法已经结束了，多数情况下取最深从循环内的语句做所描述的操作作为基本操作。

多数情况下最深层循环内的语句所描述的操作作为基本操作：

第一步、确诊问题的规模。这要具体问题具体分析具体问题，如何度量一个算法的时间复杂度，首先应该与运行该算法的机器编译器无关，不能在一台电脑上套算法时间发动和另一台电脑上套算法时间发动不同。

第二步、与解决的问题规模n有关。

在此它应该与算法的“1步”所执行的工作量无关。所以，在描述算法的时间性能时，只考虑宏观间接形式，即当输入问题规模n充分大的时候，观察算法复杂度随着n的增长趋势：当n变量不断能加时，解决问题所需要的时间的增长关系。比如线性增长T（n）=cn，即问题的规模n增长到2倍、3倍......时，解决问题需要时间n也增长到两倍三倍谁无关？五平方增长这个c的n次方C乘n的屏幕包，那么问题微博n增长到2倍3倍......（与c无关）平方增长T（n）=cn2即问题规模增长到2倍、3倍....时，解决问题所需要的时间T（n）增长到4倍9倍....（与c无关）。如果我们最后求出来的复杂度基本操作f（n）=an2+n，则O（n）=n2

++x处于最基本内层，那么就是取++x作为基本操作。显然n为规模，++x的执行次数为f（n）=n（n-1）/2，变化最快的项为n2/2，则时间复杂度为O(n2)k。

第二个函数同样的，n为规模，++i和s=s+i为基本操作，重点：假设执行次数m此结束，则有s1=1，s2=1+2=3，s3=1+2+3=6.....Sm=m（m+1）/2，则有m（m+1）/2+K=n，（K为修正常数），再倒推m=（-1+根号（8n+1-8k））/2，则时间复杂度为O（根号n）。

算法用五个特性：

1、有穷性：算法必须保证执行有限步骤之后结束；

2、确定性：每一步都必须有确定的含义；

3、输入：有零个或者多个输入；

4、输出：多输出或多或少输出。

5、可行性。

线性表示具有相同特性数据原则的一个有限序列。线性表中所按元素的个数叫做线性表的长度，用n来表示。一般来说，n可以等于0，表示一个空表。线性结构是最常用，最简单的一种数据结构。线性表是一种典型的线性结构，

基本特点是线性表中的数据元素是有序且是有限的，这种结构中：

1、存在一个唯一的，被称为“第一个”的数据元素；

2、存在一个被称为“最后一个”的数据元素；

3、除第一个元素之外，每一个元素均有唯一一个直接前驱；

4、除最后一个元素外，每个元素均有唯一一个直接后期画图表示的话。

比如在一对学生啊。学生人数对应了线性表的长度，那么学生人数是有限的，表示一个有限序列，那么队伍中所有人的身份都是学生体现了现象表中的数据源头，具有相同的特性。线性表示可以是有序的，也可以是无序的。如果按照学生的身高量排队，s在前沿高的在后就体现了有序性，那么在这一对学生中，只有一个学生在对头，同样也只有一个学生在对尾对头的学生前面，没有其他学对尾。学生后面没有其他学生。除了对头和对尾的学生以外，对于其他的每一个学生，紧挨着站在前面的和后面的学生都只有一个了。

NO.1

线性表

线性表也是这样，只有一个比较多元素和一个标本元素，表头元素没有前驱表为元素，没有后继除表头和表对元素之外，其他元素只有一个，直接前驱也只有一个，直接后继。

线性表的逻辑结构，还有一个对象的存储结构。先看线性表的定义，逻辑结构，线性表（Linear List）是由n（n≥0）个数据元素（结点）a1 ，a2 ，…，an 组成的有限序列。

① 数据元素的个数n定义为表的长度（n=0时称为空表）。
② 将非空的线性表（n＞0）记作：（a1 ，a2 ，…，an ）
③ 数据元素ai （1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。

特性：

1、有限性：线性表中数据元素是无穷的。

2、相同性：线性表中数据元素类型是同一的。

3、顺序性：线性表中相邻元素的数据元素存在序偶关系。

顺序表：Loc（ai）=Loc(a1)+(i-1)c。c就是储存，一个元素的空间。随机储存在O1的时间内储存数据元素。

顺序储存，把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称顺序表。

顺序储存的线性表的特点：线性表的逻辑顺序与物理顺序一致，数据元素之间的关系是以元素在计算机内物理位置相邻来体现。即逻辑上相邻的在物理上也相邻转的特点，顺序表要求占有连续的存储空间，那么存储空间只能预先进行，一旦分配好在对其操作的过程中始终不变。在内存中用地址连续的一块储存空间顺序存放线性表的各元素。一维数组在内存中占用的存储空间就是一组连续的存储区域。

顺序表上实现的基本运算

插入：

1、找出可以让顺序表保持有序的插入位置，

2、将找出的位置上以及气候的元素往后移动一个位置，然后将X放置腾出的位置上。

具体算法描述：

顺序表删除操作过程：

在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。其删除过程

具体算法描述：

拆除操作中的躲移是从对左边的元素开始移动。比如说要删除第二位，主要将只要移动覆盖掉，不可以后面的一个移，也就是删除办法主线，延长合法性，然后往前移动移动元素后面的约束往前移动。顺序表示线性表的顺序特殊结果，那同样的还有练表练表就是它的练，也是它的结果。数据结构也是实现复杂数据结构的重要手段。不按照线性的顺序，它就是数据，而是由若干个同一结构类型的节点一直串记而成及每一个节点。

NO.2

链表

链表是一种重要的基础数据结构，也是实现复杂数据结构的重要手段，它不按照信息的顺序存储数据，而是由若干个同一结构类型的节点依次串接而成的集美一个节点里保存着下一个节点的地址。

列表又分为单向链表，双向链表以及循环链表。

存储思想：用一组任意的储存单元存放线性表的元素，有连续、不连续、零散分布之分。

单链表：在每个节点中除包含有数据以外，只设置一个指针与用于指向其后继节点，这样构成的链接表称为线性单向链接表简称单链表。单链表是由若干节点构成的，单链表的节点只有一个指针域。（date next）

1、如何引用数据元素？*s.date；或者s->date；

2、如何引用指针域？s->next

储存特点：

1、逻辑次序和物理次序不一定相同

2、元素之间的逻辑关系用指针表示

带头结点和不带头结点

带头结点：头指针head指向头结点，那么头接点的指针域不含任何信息，从头接点的后续接点开始携带信息。head->next=NULL

不带头结点：所有结点都不含有信息。head==NULL

（1）单链表数据类型定义：

（2）单链表常见操作：

（3）单链表的遍历

（4）链表的建立

有两种常见的插入节点方式，一在链表的头上不断插入性节点，二在列表的尾部不断插入性节点，

如果是后者，一般需要有一个临时的节点指针，一直指向当前链表的最后一个节点，以方便性节点的插入。

尾插法建立单链表

头插法建立单链表

头节点在单链表的第1个元素节点之前复设一个类型相同的节点，以便空表和非空表处理统一，以指向头节点的指针为链表的头指针。

（5）头指针头节点与首元节点的关系：

头节点是为了操作的统一与方便而设立的方便，第1个元素节点之前，其数据域一般无意义当然，有些情况下也可以存放链表的长度，用作监视哨等等，有了头节点后，对在第1个元素节点前插入节点和删除第1个节点，其操作与其它节点的操作统一首元节点，也就是第1个元素的节点，它的头节点后面的第1个节点，在线性表的链式储存结构中，头指针是指链表指向第1个节点的指针，如果链表有头节点，则头指针就是指向链表头节点的指针。

（6）线性表的链式储存实现:

不要求逻辑上相邻的两个数据元素，物理上也是通过链建立起与数据元素之间的逻辑关系，因此对线性表的插入删除不需要移动数据元素，只需要修改链。

（7）求表长

（8）核心操作（关键操作）：工作指针，后移从头节点，开始或开始，节点通过工作指针的反复后移，而将整个单链表审视一遍的方法，称为扫描（或编历）。

1、按序号查找

2、按值查找

（9）线性表的插入操作的实现

（9）插入新节点步骤，在链表的第i个结点后插入一个值为x的新结点，

①先构造一个新结点，用temp指向

➁再找到链表的第i-1个点，用pre指向

③然后修改指针，插入结点（pre之后插入新结点是temp）

（10）删除（删除链表的第i个位置上的结点）

①先找到链表的第i-1个节点，用pre指向

➁再用指针tmp指向要被删除的结点（pre的下一个结点)

③然后修改指针,删除tmp所指结点

④最后释放tmp所直结点的空间

（11）查找列表c带头节点中是否存在一个值为x的节点，若存在则删除点并返回1，否则返回0。