02.第02节课第2章线性表

罗泽兵 · 发表于 2024-4-15 09:13:18

我们刚才讲过，那么我们呢？可以呢，用记息方法呢来。衡量我们算法的这样一个部分。通常呢，有两种衡量算法效率的方法，第一种呢是事后统计法。它的缺点呢？必须执行程序。第二个呢，是其他因素。改掩盖算法本质，第二种呢，是事前估计分析法。

和算法实行时间相关的因素呢？有算法采用的策略问题的规模，编写程序的语言，编译程序产生的机器代码的质量以及呢？计算机执行指令的速度。一个特定算法的运行工作量的大小呢，只依赖于问题的规模，那么通常呢，用整数n来表示，或者说它是问题规模的函数。那么，假如呢？随着问题规模n的增长，算法执行时间的增长率和fn的增长率相同，那么则可以记做了。

tn=of n。称tn呢？称为算法的渐进时间复杂度，那么我们来看一下如何估算算法的时间复杂度呢？算法那么是我们的控制结构和我们的原操作，算法的执行时间呢？是我们原操作I执行的次数。加原操作I的执行时间，然后把它把c干嘛呢？原操作I的执行次数乘以原操作I的执行时间。算法的执行时间与原操作执行次数之和呢？成正比。从算法中呢，选择一种对于所研究问题来说是基本操作的语言操作，以该基本操作呢，

在算法中执行。重复执行的次数作为算法运行时间的衡量准则，比如说我们看一下这个程序，两个矩阵相乘，这个程序啊，是不是word mount？inta数组in TB，数组int取地址int这样一个c数组。以二为数组了。存储数据源组成元素c为a和b的乘积for I=1 g小于n加加if org小于1g小于等于n加加g。cig=0，fork=1，k小于等于n。加上k cig。等于cig加。

等于。aik×bk I。这是我们的两个直径相乘的这样一个部分。那么，我们的基本操作呢？是我们的乘法操作，那么时间复杂度呢？是on的三次方。那么我们看一下我们的算法，实践复杂度呢？首先我们看一下这个部分。第一个for循环I从一到n。第二个for循环j从一到n。另外呢，还有我们的k从一到n，

那么这些for循环的部分，那么基本的操作呢我们？这里呢，从一到n这里呢，也从一到n那么它要进行的次数就是n平方，那么再有一个一到n呢，那么就是n的三次方，所以它的基本操作呢，是我们这样一个运行的，这样一个操作的，这样一个运行运用部分。那么，基本操作呢？就是乘法操作实现复杂度呢？就是on的三次方。

那么我们再看一下选择排序。wade selects or tint数组a in tn。将a中整数序列重新排列成至小有大大有序的整数序列，我们来看一下这个程序。for循环，第一个for循环呢是零到n- 1 I=0。以及呢，我们的I小于n- 1第二个for循环是k=I+1以及呢k小于n。那么，它的操作呢？是比较数据元素的操作，那么就就要执行呢？那么，这样一个。这些到到I这样一个从I呢到ni+1这样一个I+1呢到n这样一个，

还有另外的这样一个I的零到n- 1的这样一些。结合联系的这样一个数数量的这样一些运运行次数，那么进行一些这些数据元素的比较。那么，它的时间复杂度呢？就是on的平方，那么这是它的时间复杂度？第三个起泡排序。我们来看一下它的当中的这样一个操作for I=n- 1。I大于一。并且呢，change。这里呢，还有一个for循环g=0 g小于I。那么，

这里呢？就是从我们的零到I垂直的n- 1了，到我们到我们的一的那么这些。联系的数量的这样一些操作次数，那么它的基本操作呢？是我们的复制操作。它的实现复杂度呢，就是我们on的平方。接下来我们再看一下算法的空间需求。算法的空间复杂度呢？定义为SN=ogn表示，随着问题规模n的扩大，算法运算呢？所需存储量的增长率与gn的存长率相同。算法的存储量呢，

包括输入数据所占空间程序本身所占空间，以及呢，辅助变量所占空间。如果输入数据了，所占空间只取决于问题本身和算法无关，则只需要分析出输入和程序外的辅助变量了，所占的额外空间。那么，若所需额外空间呢？相对于输入数据量来说是常数，那么只称此算法呢？为原地工作。若所需存储量依赖于特定的输入，则通常呢，按最坏的情况来进行考虑的这样一个部分。

好，接下来我们来看一下我们数据结构当中那么这样一些。一种数据的进行，一些结构的这样一些部分。那么。我们线性表。我们。这里讲的线性表以及我们之后要讲的栈队列串数组。也就是说，线性表栈队列串数组了都属于线性结构。线性结构的基本特点呢，是除第一个元素无直接前驱，最后一个元素无直接后驱外。其他每一个元素呢，都有一个前驱和后继，

就是前面的一个元素和后面的一个元素。线就是一个前驱，一个前面的一个元素，后面的一个元素，一个前驱后继线性表了是最基本且最常用的一种线性结构。同时也是其他数据的基础。尤其呢，单链表是贯穿整个数据结构了，那么这样一个。基本的这样一个技术。这里呢，我们先给大家讨论一下线性表的逻辑结构，存储结构，以及呢，相关预算以及线性表的。

应用实例。那么，这些问题呢？都具有一定的普遍性。那么大家呢？来看一下这个部分，那么我们讲一下呢？那么看一下其中的这样一个运用的，那么这样一个部分。好，大家看，就这样一个那么这样一些讲的这样一个内容。啊，这样一些用的部分。线性表呢，

是一种最简单的数据结构，那么也是构造其他各种复杂数据结构的基础，它有顺序和链式两种存储表示方法。数据线性表的类型呢，定义包括它的逻辑定义及其操作，以及不同的存储方式，表示线性表示啊，它也有不同的这样一个操作。那么，通过对线性表的操作及线性表应用算法的评价呢？可以呢，我们可以来了解。算法分析的这样一个部分。那么，我们首先来看一下线性表的类型定义。

线性表呢，是一种最简单的线性结构，比如说我们的从a。从我们的一二三十到90勾框k。它这样一个排列的部分线性结构的基本特征呢？为一个数据元素的有序次序集，比如说我们的a一二三。一二三勾框k。数据集合中呢，必存在唯一的一个第一元素，以及呢，一个唯一的一个最后元素。除最后元素之外呢，均有唯一的后具。除第一元素外呢，

均有唯一的前驱。那么，我们来看一下线性表的定义。线性表中的元素个数n定义为其长度。n=0的线性表呢？称之为空表。那么，我们的线性表呢？那么可以这样呢？这样一个写字，这样一个方式，比如说a1a2到aai- 1 AI AI加一直到an。在非空线性表中的每个元素呢，都有一个确定的位置，比如说a2是第一是第一个元素an是最后一个元素。

AI是第I个元素，称I为数据元素。AI呢在线性表中的这样一个序位。线性表的基本操作呢？那么可以分为四大类，基本操作，比如说。初始化。操作结构销毁，操作引用型操作以及呢，加工型操作。我们来看一下初始化操作。初始化操作initial is t选l的地址操作，结果呢，是构造一个空的线性表l。

销毁结构操作destroy list al的地址，那么它的结果呢？就是我们。线性表了，销毁掉我们的线性表以后。那么，以及我们的引用型操作list empty list length prior element next element get element location locate element。alisttravescy那么，这些引用型操作不涉及表结构的变化。那么，我们来看一下。加工型操作。表的结构呢？有变化，比如说clear list。

put empty element list insert和list delete那么这些呢，就表的结构呢有变化。我们可以了。用上述定义的线性表类型呢，可以实现其他更复杂的操作。我们来看一下线性表的顺序，表示和实现。那么，首先我们来看一下顺序表。顺序表了是什么了？顺序表这里呢，我们讲的是它的存储结构。顺序表。那么所以呢，我们所以呢，

我们就那么我们讲的这样一个顺序表呢，是讲的它的这样一个存储结构。它的这个顺序表呢？指的是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。那么，这种表示呢？也称为线性表的顺序存储结构，或者说顺序印象。称这种存储结构呢的线性表呢？为顺序表那么所以说大家这里要记住我们说顺序表呢？那么我们这里呢？是在。讨论它吃了，说它的这样一个存储结构的这样一个部分，那么接下来我们还可以，

今后以后我们还可以，还会遇到一些其他的表。比如说。这一种表称之为我们的。还有有序表。另外呢，我们还会遇到一种表呢，叫我们的有序表，这里我们遇说到的这样一个顺序表呢，是它的这样一个存储结构的部分。顺序表呢，就是用一组地址连续的存储单元依次存放线性表中的数据元素，比如说a1呢。是它的这样一个线性表的起始地址，称之为线性表的基地是。

那么，在高级语言的层次呢？通常以一组数组呢来存放。依次的存放线性表数据元素的顺序表，并且可以通过数组元素的下标，方便的访问数据元素，那么所以这里给大家知道。我们的顺序表了，可以了直接进行访问，它可以了。要访问某个数据元素了，那么比较方便。那么我们看一下顺序表的C语言描述。首先是define list initial size。define.

list.instrument type define struct empty type.信号element。inter lens inter dis size inter.increment size.那么sq list那么这个呢？就是我们顺序表的C语言描述的部分。那么我们再来看一下。构造一个空线性表woi DIN lists q。s qu list.选要的地址。刚才我们看到了。我们的cq list呢？表示的。是我们的这样一个结构体。

这个结构体当中呢，有我们存储空间的基质。由我们的当前长度。由我们当前分配的存储容量。以及呢，约定的增补空间量，那么这个结构体呢？它是？那么，我们构造一个新的空的线性表。那么cl的地址，那么这个l呢？指向这样一个结构体的，这样一个是一个指向结构体的指针。那么，

接下来我们看一下这样一个。它的这样一个程序部分，这样一个程序部分语句部分l element=6。element type list in the size.if.这样一个l element。那么取反那么exit overflow？哈哈哈。l认识等于零线性表的当前长度。l list size=list inter size，initial size。l increment size，那么等于我们的一。list increment.那么，

增补空间量。那么我们看一下构造空线性表的这样一个部分。那么，首先呢，是我们的。l element.好吧，这样一个结构体当中这样一个。element啊，是我们的六。element type list in the size.那就是这里了，是为顺序表了分配一个大小了。v max size的这样一个数组空间。那么if。

取反l element exit如果呢？存储失败。那么，分存储分配失败，那么就退出。那么，接下来呢？l认识等于零线性表的空表的长度呢？是零。l list size.我要说我们的list initial size。l increment size=list increment那么增补空间，空间量那么这是我们的构造空的线性表的这样一个方式。那么，这是我们构造的新的空线性表，

那么这样一个构造的这样一个方式。查找。元素这样一个方式int locate element csq SQL SQL l。element type e.在顺序表中呢，查询第一个满足判定条件的数据元素，那么若存在了，则返回它的位序，否则呢，返回零。那么I=1。I的初值呢，为第一元素的位序p=l点。element.p的初值呢？

为第一元素的存储位置。yi小于等于l点ls，并且呢？星星号p加加不等不等于e。那么加加I。是吧，依次呢进行判定。那么判断呢？我们的这样一个指针，所指向的那个元素呢？那么是？是指指针的指针的这个元素呢，它的值呢？对吧，判断呢，

我们的这样一个星p。它是否了是我们的这样一个e？然后进行了加加I。依次呢进行判定。if I那么我们这里的I小于等于l点嫩次，那么就说我们I呢，比这个表长要要比这个长度呢要小。并且呢，我们的星p要是否要等于e是否不等于e？那么，如果它不等于一了，那么就p加加，那么指针呢？增加这样一个部分，那么增加，

那么最后呢？那么我们的I加加I，那么不等于一了，那么我们加加I。依次来进行判定if。I小于等于l点认识。return I返回第I个值这样一个它的这样一个值I的这样一个值返回它的位序else return 0，否则了返回零。那么，这是我们的查找。在顺序表中啊，查找第一个满足判定元素的数据元素，满判定元素的数据条件。然后我们再来看一下。插入。

元素插入元素呢，是void list int inserts qc list li nti element。e element type e在顺序表l的第I个元素之前呢？插入新元素。e.I的合法范围呢，是我们的一小于等于I，小于等于l。小l点愣是加一。那么我们看一下这个程序q等于那么取地址。l点。element i- 1。那么q呢？表示要插入的位置。for p等于取地址l点element length- 1。

p大于等于q减减p。新p+1。等于星p在插入位置之后的元素呢？右移。新q=e那么插入e。加加l点嫩死表长加一，那么这是我们插入元素的方法，那么我们看一下这样一个解释的部分。那么我们看一下插入元素时呢，逻线性表的逻辑结构呢？会发生什么变化？那么我们来看一下。插入元素之前，比如说我们呢？要在第I个元素之前插入一个e。

那么，我们把它放在一之前，那么本来我们的存储空间呢？是我们的a1a2一直到ai- 1 AI一直到an。那么，我们到AI之前差一个元素e呢？那么，我们AI呢？一直到an呢？这些元素呢？都要向这些元素呢？就要右移一个一个单位，那么an呢？向右移an- 1呢？向右移个单位。

那么就是说在AI前面插入一个元素e的话，那么我们eae之后，那么我们。从AI呢到an那么这些元素呢，就要向右移动，那么这是我们插入的这样一个运用的方法。那么，我们看这个程序当中for p等于取地址l点element。l点认识减一。那么就是说。p的初值啊，是我们。最开始的时候呢，我们表长减一，它就在最后一个位置，

就在最后一个位置，那么就是在这个位置的部分。那么p呢，大于等于qpp呢，要在我们这样一个插入的元素q之前。然后呢？减减p，然后把p星p呢赋给p星p- 1，也就是说将我们星p所指向的元素呢插入到它下一个元素。插下一个位置，比如说将我们插入，将我们这样一个元素呢，进行一个右移，进行往后面移动一个位置，再插入元素之后，

插入位置之后的元素呢，进行右移，那么这是我们的。这样一个运用的方式，那么最后呢e等于新q，那么在我们这样一个。秀指向的这样一个位置了，原来原来I的这样一个位置，第I个元素的这样一个位置呢，插入e那么最后呢，加加愣死我们的表长呢，加一。那么，这是我们插入元素的这样一个方式。删除元素的方式，

那么比如说。我们要删除第I个元素，原来呢，在我们的存储空间当中呢？我们是存放的a1a2，一直到ai- 1 AI AI加，一直到an。那么，我们删除了第a，第I个元素AI之后呢？我们这个时候呢？AI后面的元素呢？就要向前移动，就要向前移动，向左移动一个移动移动移动位置，

那么向前移动。那么AI+1呢，就变成了原来AI的位置，那么到an呢，那么就变得了，变成了它之前的这样一个位置，那么就是我们插入元素的方，删除元素的方式。那么我们看一下这个语句。void list delete SQ SQ sq list li nti element type e.if I小于一或者I大于认识，return error删除位置不符合不合法，如果在第I在第I第一个元素之前。并或者说I大于表长，那么删除为return返回一个错误，

返回一个error。那么p等于取地址l element i- 1。p为被删除元素的位置一等于星p。把被删除元素的值啊，复制给e。q等于。l element.加l认识减一。这是表尾元素的位置。那么for加加p for小于等于q加加加p。那么，新p+1。星p- 1等于星p那么被删除之元素之后的元素呢？左移。最后呢，

减减认识，那么我们的表长减一。那么也就是说我们p呢？指向的这个元素呢，就把它放在它之前的这个元素的位置，也就说。我们的它所指向的元素呢？权益的这样一个。直接想想到了这样一个运用的。使用的。选取了这样一个位置的。进行联系的，实现实实实现的这样一个。运用运用的联联系的这样一个。直直接的这样一个位置的这样一个。

应用的这样一一一个。方式的这样一个归位范围部分，那么就是这样一个位置改变的，它这个位置的部分，比如说我们这样一个被删除的元素呢，那么之后的元素就是p指向这个元素了。那么，它的这样一个绝绝世的这样一个。规规范的这样一个直线位置的这样一个变化的这样移动位置，那么就将它呢进行一个向前移动。那么，向前移动呢？就移动到它前面的这样一个位置，那么最后呢？我们的表长减一，

那么这就是我们的。删除一个元素的这样一个方式。

		自动登录	找回密码
密码			立即注册