数据结构（第2章）.docx

《数据结构（第2章）.docx》由会员分享，可在线阅读，更多相关《数据结构（第2章）.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第2章线性表从本章开始到第4章将讨论线性结构。线性结构是最简单且最常用的数据结 构，线性表是一种典型的线性结构。2. 1线性表的逻辑结构在现实世界中，线性表的例子不胜枚举。例如，英文字母表(A, B,，Z) 是一个线性表，表中的每个字母是一个数据元素(结点)；又如，一副扑克牌的 点数(2, 3,10, J, Q, K, A)也是一个线性表，这里的数据元素是每张牌的点数。在较为复杂的线性表中，数据元素可由若干数据项组成，如学生成绩 表中，每个学生及其成绩是一个数据元素，它由学号、姓名、各科成绩及平均成 绩等数据项组成。综合上述例子，可将线性表描述为：3. 1. 1线性表的定义线性表(Linear

2、 List)是由n(n20)个数据元素(结点)ai,a2,an组成的有限 序列。其中，数据元素的个数n定义为表的长度。当n=0时称为空表，常常将 非空的线性表(n0)记作：(ai, az,，田，an)这里的数据元素小只是一个抽象的符号，其具体含义在不同情况下可以不同。4. 1. 2线性表的逻辑特征从线性表的定义可以看出它的逻辑特征是：_对于非空的线性表，有且仅有一个开始结点画，它没有直接的前驱，而仅有 一个直接的后继a2；有且仅有一个终端结点an,它没有直接的后继，而仅有一 个直接前驱an-i;其余的内部结点ai(2Win1)都有且仅有一个直接前驱团和 一个直接后继线性表中结点之间的逻辑关系就

3、是上述的邻接关系，由于该 关系是线性的，因此线性表是一种线性结构。5. 1. 3线性表的基本运算数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进 行的。因此，在逻辑结构上定义的运算，只要给出这些运算的功能是“做什么”, 至于“如何做”等实现细节，只有待确定了存储结构之后才考虑。常见的线性表的基本运算有如下六种：(1) InitList(L)构造一个空的线性表L,即表的初始化。(2) ListLength(L)求线性表L中的结点个数，即求表长。(3) GetNode(L,i)取线性表中的第i个结点，这里要求iWiWListLength(L)。(4) LocateNode(L,x

4、)在L中查找值为x的结点，并返回该结点在L中的位置。若L中有多个结点的值和x相同，则返回首次找到的结点位置；若L中没有结点的值 为x,则返回一个特殊值表示查找失败。(5) InsertList(L,x, i)在线性表L的第i个位置上插入一个值为x的新结点，使得原编号为 i, i+1,n的结点变为编号为i+1, i+2,n+l的结点。这里linex匚=NULL) /ivl 或 in 时删除位置有错 Eiror(position error); /退出程序运行r=p-next; 令r指向被删结点 刃p-next=r-next; 将 aifree(r); 释放结点 也1设单链表的长度为n,则删去第i

5、个结点仅当iWiWn时是合法的。注意， 当i=n+l时，虽然被删结点不存在，但其前驱结点却存在，它是终端结点。因此 被删结点的直接前驱*p存在并不意味着被删结点就一定存在，仅当*p存在(即 p!=NULL)且*p不是终端结点(即p-next!=NULL)口寸，才能确定被删结点存在。此算法的时间复杂度也是0(n)。从上面的讨论可以看出，链表上实现的插入和删除运算，无须移动结点，仅 需修改指针。循环链表循环链表(Circular Linked List)是一种首尾相接的链表。其特点是无须增加存 储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。在用头指针表示的单循环链表中，找开始结点ai

6、的时间是0(1),然而要找 到终端结点ani和终端结点an都很方便，它们的存储位置分别是rear-next-next 和rear,显然，查找时间都是0(1)。因此，实用中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再是像 非循环链表那样判别p或p-next是否为空，而是判别它们是否等于某一指定指 针，如头指针或尾指针等。例 2. 1 在链表上实现将两个线性表(ai，a2, ，an) 和(bi，b2, ，bm) 链接成一个线性表(理_, ，刖，bi, ，bm_) 的运算。倘若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一 个链表，找

7、到结点an,然后将结点bl链接到an相应的算法如下：LinkList Connect(LinkList A, LinkList B)假设A, B为非空循环链表的尾指针，保存A表的头结点位置，B表的开始结点链接到A表尾 Return B; 返回新循环链表的尾指针在单链表中，从一已知结点出发，只能访问到该结点及其后继结点，无法找 到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中 所有结点，这一优点使得某些运算在单循环链表上易于实现。1 . 3.3双链表单循环链表中，虽然从任一已知结点出发能找到其直接前驱结点，但时间耗 费是0(n)。若希望从表中快速确定一个结点的直接前驱，可以

8、在单链表的每个 结点里再增加一个指向其直接前驱的指针域prioro这样形成的链表中有两条方 向不同的链，故称为双(向)链表(Double Linked List)。形式描述为：DataType data;Struct dlistnode *prior, *next;DlistNode;typedef DlistNode * DLinkList;DLinkList head;在单链表上，若已知某结点的存储位置p,则将一新结点*s插入*p之前(称 为前插)不及插入*p之后(称为后插)方便，因为前插操作必须知道*p的直接 前驱的位置，而单链表中链方向的单向性使我们必须从头指针开始向后遍历链表 才能找

9、到*p的直接前驱；同理，删除*p本身不如删除*p的直接后继方便。而双 链表是一种对称结构，它既有前向链又有后向链，这就使得上述两种插入及两种 删除操作同样方便。设指针p指向某一结点，则双链表结构的对称性可用下式描 述：p-prior-next=p=p-next-prior 假设*p的直接前驱和直接后继均存在 亦即结点*p的存储位置既存放在其前驱结点*(p-prior)的直接后继指针域中，也 存放在它的后继结点*(p-next)的直接前驱指针域中。void DInsertBefore(DlistNode *p, DataType x)在带头结点的双链表中，将值为x的新结点插入*p之前，设pWNU

10、LLs-data=x; 加链表上删除结点*p自身的操作如图2.17所示，其算法如下: void DDeleteNode(DListNode *p)在带头结点的双链表中，删除结点*p,设*为非终端结点至p-prior-next二p-next;p-next-prior=p-prior;free”1注意，与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须 同时修改两个方向上的指针。上述两个算法的时间复杂度均为0(1)。2.4顺序表和链表的比较上面两节介绍了线性表的两种存储结构：顺序表和链表，它们各有短长。在 实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决 定。通常有以

11、下几方面的考虑：1 .基于空间的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规 模。若线性表的长度n变化较大，则存储规模难于预先确定。估计过大将造成空 间的浪费，估计太小又将使空间溢出机会增多。链表的存储空间是动态分配的， 只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难 以估计其存储规模时，以采用动态链表作为存储结构为好。在链表中的每个结点，除了数据域外，还要额外设置指针域，从存储密度来 讲，这是不经济的。所谓存储密度(Storage Density)是指结点数据本身所占的 存储量和整个结点所占的存储量之比，即存储密度=(结点数据本身所占的存储量

12、)/ (结点结构所占的存储总量)一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密 度为1,而链表的存储密度小于1。例如，若单链表的结点数据均为整数，指针 所占的空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中 的空闲区，则顺序表的存储空间利用率为100%,而单链表的存储空间利用率为 50%o由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约 存储空间，易采用顺序表作为存储结构。2 .基于时间的考虑顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可在 0(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链扫描才能取得。 因此，若

13、线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表 做存储结构为宜。在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中 进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较 大时，移动结点的时间开销就相当可观。因此，对于频繁进行插入和删除的线性 表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采 用尾指针表示的单循环链表为宜。n是原表L的长度。插入后表L的长度加1。(6) DeleteList(L, i)删除线性表L的第i个结点，使得原编号为i+1, i+2,n的结点变为编 号为ij+l9声1的结点。这里而n是原表L的长度。删除

14、后 表L的长度减1。上述运算并不是线性表的全部运算。因为对于不同应用问题中所使用的线 性表，所需执行的运算可能不同，所以我们不可能也没有必要事先定义一 组适合各种需要的运算。因此，通常的做法是只给出一组最基本的运算， 对于实际问题中涉及的其它更为复杂的运算，可以用基本运算的组合来实 现。2. 2线性表的顺序存储结构2. 2. 1顺序表(1)定义：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单 元里，用这种方法存储的线性表简称为顺序表(Sequential List)o将线性表存储到计算机中可以有许多不同的方法，其中既简单又自然的就 是这种顺序表的方法。(2)顺序表中结点的寻址公式为不失

15、一般性，不妨设线性表中所有结点的类型是相同的，因此每个结点所 占用的存储空间的大小亦是相同的。假设表中每个结点占用c个存储单元，其 中的第一个单元的存储地址则是该结点的存储地址，并设表中开始结点at的 存储地址(简称为基地址)是LOC (aD,那么结点印的存储地址可通过下式 计算：LOC(a0=LOC(ai)+(i-l)*c1W i dataO和 L-dataL-length-l中。从该示意图可看出，顺序表是用向量实现的线性表， 向量的下标可以看作结点的相对地址。它的特点是逻辑上相邻的结点其物理位 置亦相邻。2. 2. 2顺序表上实现的基本运算在顺序表中，线性表的有些运算很容易实现。例如，设L

16、是指向某一顺序表的指针，则表的初始化操作是将表的长度置0,即L-length=0；求表长和 取表中第i个结点的操作只需分别返回L-length和L-datai-l即可。以下主 要讨论插入和删除两种运算。(1)插入顺序表插入定义线性表的插入运算是指在表的第i(lWiWn+l)个位置上，插入一个新结点x,使长度为n的线性表:(ai, a2,，a” ，an) 变成长度为n+1的线性表：(ai,，aw x, ，an)用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑 顺序保持一致，因此我们必须将表中位置n, n-1,，i上的结点，依次后移到 位置n+1, n,，i+1上，空出第i个位置

17、，然后在该位置上插入新结点X。仅 当插入位置i=n+l时，才无需移动结点，直接将x插入表的末尾。(注意：表中 位置，即结点的序号，它与下标相差1,第1号元素存放于下标为0的单元，, 第i号元素存放于下标为i-1单元，。)顺序表的插入过程顺序表的插入算法具体算法描述如下：void InsertList(SeqList *L,DataType x,int i)将新结点x插入到L所指的顺序表的第i个结点at的位置上intj;if (ilength+l)Error(uposition error)；非法位置，退出运行if(L-length=ListSize)Eiror(overflow);表空间溢出，

18、退出运行for (j=L- length-1;j =i-1;j -)1(叫+1=1-(1沆2。；结点后移L-datail=x;插入 xL-length+; 表长力口 1)注意算法中结点后移的方向，必须从表中最后一个结点开始后移，直至将第 i个结点后移为止。此外，由于表中结点位置比相应的向量下标大1,故算法中 处理显得不自然。若将线性表的结点序列定义为(ao, ai, an-i),使表中结 点和相应的向量下标一致，则处理将更简单自然。顺序表插入算法的时间复杂度现在分析算法的时间复杂度。这里问题的规模是表的长度L-length,设它的 值为n。显然该算法的时间主要花费在for循环中的结点后移语句上

19、，该语句的 执行次数(即移动结点的次数)是n-i+l。由此可看出，所需移动结点的次数不 仅依赖于表的长度n,而且还与插入位置i有关。当1=11+1时，由于循环变量的 终值大于初值，结点后移语句将不执行，无须移动结点；若i=l,则结点后移语 句将循环执行n次，需移动表中所有结点。也就是说该算法在最好情况下时间复 杂度是0(1);最坏时间复杂度是O(n)。由于插入可能在表中任何位置上进行， 因此需分析算法的平均性能。在长度为n的线性表中插入一个结点，令Eis表示移动结点次数的期望值(即 移动结点的平均次数)，在表中的第i个位置上插入一个结点的移动次数为n-i+1。 故Eis(n)= pi式中，p表

20、示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表 中任何合法位置(lWiWn+1)上插入结点的机会是均等的，则P1 =P2二-Pn+1 = 1 /(n+1)因此，在等概率插入的情况下，Eis(n)=(n-+1 )/(n+1 )=n/2也就是说，在扁序表上做插入运算，平均要移动表中的一半结点。当表长n较大 时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然 是线性阶的，因此算法的平均时间复杂度是0(n)。(2)删除顺序表删除的定义线性表的删除运算是指将表的第i(lWiWn)个结点删去，使长度为n的线性 表(a. aii， ai， ai+” ,一 a*)变成长

21、度为nJ的线性表(ai，, ai-i, 组+i, , a1)和插入运算类似，在顺序表上实现删除运算也必须移动结点，才能反映出结点问 逻辑关系的变化。若亡n,则只要简单地删除终端结点，无须移动结点；若iWi Wn-1,则必须将表中位置i+1, i+2,，n上的结点，依次前移到位置i, i+1,，n-1上，以填补删除操作造成的空缺。顺序表的删除过程顺序表的删除算法具体算法如下：void DeleteList(SeqList *L,int i)从L所指的顺序表中删除第i个结点砥int i;if(iL-length)Error(“position error);非法位置for(j二i;j v二L-lc

22、ngth- 1 ;j+)L-dataj-1 l=Ldatail;/结点前移LTength-; 表长减小1顺序表删除算法的时间复杂度该算法的时间分析与插入算法类似，结点的移动次数也是由表长n和位置i 决定的。若1=必则由于循环变量的初值大于终值，前移语句将不执行，无须移 动结点；若i=l则前移语句将循环执行n-1次，需移动表中除开始结点外的所有 结点。这两种情况下算法的时间复杂度分别是0(1)和O(n)o删除算法的平均性能分析与插入算法类似。在长度为n的线性表中删除一个 结点，令Ede表示所需移动结点的平均次数，删除表中第i个结点的移动次数 为n-i,故EDE(n)=pi式中，p表示删除表中第个

23、结点的概率。在等概率的假设下，P1=P2二=pn=l/n由此可得：Ede即在顺序表上做删除运算，平均要移动表约一半的结点，平均时间复杂度也是 O(n)o数据结构(第4讲)2.3线性表的链式存储结构由上节的讨论可知，线性表的顺序表表示的特点是用物理位置上的邻接关系 来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它 也使得插入和删除操作会移动大量的结点。为避免大量结点的移动，本节将介绍 线性表的另一种存储方法一一链式存储结构，并将这种用链式方式存储的线性表 简称为链表(LinkedList)。值得指出的是，链式存储是最常用的存储方法之一, 它不仅可用来表示线性表，而且可用来表

24、示各种非线性的数据结构，在以后的章 节中将反复使用这种存储方式。2.3.1单链表在顺序表中，我们用一组地址连续的存储单元来依次存放线性表的结点，因 此结点的逻辑次序和物理次序一致。而链表则不同，链表是用一组任意的存储单 元来存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚 至是零散分布在内存中的任何位置上。因此，链表中结点的逻辑次序和物理次序 不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还 必须存储指示其后继结点的地址(或位置)信息、，这个信息称为指针(pointer) 或链(link)o这两部分信息组成了链表中的结点结构，其中：data域是数据域，

25、用来存放结点的值；next域是指针域(亦称链域)，用来存放结点的直接后继的 地址(或位置)。链表正是通过每个结点的链域将线性表的n个结点按其逻辑顺 序链接在一起的。由于上述链表的每个结点只有一个链域，故将这种链表称为单 链表(Single Linked List)。显然，单链表中的每个结点的存储地址是存放在其前驱结点next域中，而开 始结点无前驱，故应设头指针head指向开始结点。同时，由于终端结点无后继, 故终端结点的指针域为空，即NULL (图示中也可用A(bat, cat, cat, fat, hat, lat, mat)的单链表示意图，这里假设指针占两个字节的存储空间。(2)单链表的

26、类型定义单链表由头指针惟一确定，因此单链表可以用头指针的名字来命名。例如， 若头指针名是head,则把链表称为head。用C语言描述的单链表如下：typedef char DataType；假设结点的数据类型是字符typedef struct node 结 点类 型定义DataType data；结点的数据域 Struct node *next；结点的指针域ListNode；typedef ListNode *LinkList；ListNode *p；LinkList head；这里，LinkList和ListNode *是不同名字的同一个指针类型，命名的不同是 为了概念上更明确。例如，Lin

27、kList类型的指针变量head表示它是单链表的头指 针，而ListNode *类型的指针变量p则表示它是指向某一结点的指针。值得一提的是，我们一定要严格区分指针变量和结点变量这两个概念。例如, 以上定义的变量p是类型为ListNode *的指针变量，若p的值非空(p!=NULL), 则它的值是类型为ListNode的某一个结点的地址。通常p所指的结点变量并非 在变量说明部分明显的定义，而是在程序执行过程中，当需要时才产生，故称为 动态变量。实际上它是通过标准函数生成的，即p=( ListNode *)malloc(sizeof(ListNode)；函数malloc分配一个类型为ListNod

28、e的结点变量的空间，并将其首地址放入指 针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放p所指的结点变量空间。因此，我们无法通过预先定义的标识符去访问这种 动态的结点变量，而只能通过指针p来访问它，即用*p作为该结点变量的名字 来访问。由于结点类型ListNode是结构类型，因而*p是结构名，故可用C语言 的成员选择符”来访问该结构的两个分量(*p).data和).!，这种表示形式 较为繁琐，可用C语言的另一种成员选择符来访问指针所指结构的成员更 为方便，即 p-data 和 p-nexto 又因为(*p).next(即 p-next)也是 ListNode *类

29、型 的指针变量，故加上符号请注意，若指针变量p的值为空(NULL),则它不指向任何结点，此时，若 通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。下面我们将讨论用单链表做存储结构时，如何实现线性表的几种基本运算。 为此，首先讨论如何建立单链表。1 .建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并 以换行符(nD为输入结束标志符。动态地建立单链表的常用方法有如下两种: (1)头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新 结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为 止。具体算法如下：Lin

30、kList CreateListF(void)返回单链表的头指针char ch;LinkList head; 头指针ListNode *s; 工作指针head=NULL; 链表开始为空ch-getchar(); /读第 1 个字符while(ch!=n)ch二getchar() /读入下一字符1return head; 返回 头指针1(2)尾插法建表尾插法建表算法如下：LinkList CreateListR(void)1char ch;LinkList head;ListNode *s, *r;head-NULLq=NULL;链表初值为空，尾指针初值为空while(ch=getcharQ)!

31、=n)if(head-NULL)head=s; 新结点插入空表else一)end of while if(r!=NULL)r-nex匚NULL; 对于非空表，将尾结点指针域置空return head ；1在上述算法中，第一个生成的结点是开始结点，将开始结点插入到空表中， 是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的 插入操作处理是不一样的(实际上对其它操作亦可能如此)，原因是开始结点的 位置是存放在头指针(指针变量)中，而其余结点的位置是在其前驱结点的指针 域中。因此我们必须对第一个位置上的插入操作做特殊处理，为此上述算法使用 了第一个if语句。算法中第二个if语句的

32、作用是为了分别处理空表和非空表这 两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表， 尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终 端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并 称它为头结点，那么会带来以下两个优点：由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位 置上的操作就和在表的其它位置上操作一致，无须进行特殊处理；无论链表是否为空，其头指针是指向头结点的非空指针(空表中头结点的 指针域空)，因此空表和非空表的处理也就统一了。引入头结点后，尾插法建立单链表的算法可简化为：LinkList Cr

33、eateListRl(void)用尾插法建立带头结点的单链表char ch;LinkList head=(LinkList)maoc(sizeof(ListNode); 生成头结点ListNodehead;/尾指针初值亦指向 头结点while(ch=getchar()!=n)s二(ListNode*)malloc(sizeof(ListNode);s-data=ch;r-next=s;r=s;1r-nex匚NULL; 终端结点的指针域置空，或空表的头结点指针域置空 return head ；1显然CreateListRl比CreateListR简洁。因此链表中一般都附加一个头结点来 简化边界条

34、件的处理。上述算法里动态申请新结点空间时未加错误处理，这对申 请空间较少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的 程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。 例如，上述算法中申请新结点的处理应为：s=(ListNode *)malloc(sizeof(ListNode)if(s=NULL)/动态分配空间失败ErrorCNo space for node can be obtained)；退出运行以下按正常情况处理为节省篇幅，这里不介绍处理这种错误。以上三个算法的时间复杂度均为0(n)。2 .查找运算(1)按序号查找在链表中，即使知道被访问结点的序

35、号i,也不能像顺序表中那样直接按序 号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直 至搜索到第i个结点为止。因此，链表不是随机存储结构。设单链表的长度为n,要查找表中第i个结点，仅当iWiWn时，i值是合法 的。但有时需要找头结点的位置，故我们把头结点看作是第。号结点，因而下面 给出的算法中，我们从头结点开始顺着链扫描，用指针p指向当前扫描到的结点, 用j作计数器，累计当前扫描的结点数。p的初值指向头结点，j的初值为当 p扫描下一个结点时，计数器j相应地加1。因此当j=i时，指针p所指的结点就 是要找的第i个结点。ListNodc * GctNodc(LinkLis

36、t hcad,int i)在带头结点的单链表head中查找第i个结点，若找到(1 WiWn),则返回 该结点的存储位置,否则返回NULL。int j;ListNode * p;p=head;j=O; 从头结点开始扫描while(p-next & jvi) 顺指针向后扫描，直至U p-next 为 NULL 或 j=i为止p=p-next;J；1if(i二二j)return p; /找至lj第i个结点elsereturn NULL; 当inext; 从开始结点比较，表非空时，p 初始值指向开 始结点。while(p & p-data!二key)直至U p 为 NULL 或 p-data 为 ke

37、y 止p=p-next; /扫描下结点return p; 若 p二NULL 则查找失败否则 p 指向找至U的值为 key 的结点1该算法的执行时间亦与输入实例中key的值有关，其平均时间复杂度分析类 似于按序号查找，也是0(n)。3 .插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到之 间。因此，我们必须首先找到超1的存储位置p,然后生成一个数据域为x的新结点 *s,并令结点*p的指针域指向新结点，新结点的指针域指向结点笺。从而实现三 个结点小小x和5之间逻辑关系的变化，具体算法如下：void InsertList(LinkList head, DataType x, int i)将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上ListNode *p; if (p二二NULL) ivl或in+l时插入位置i有错 Error(position error);