数据结构线性表

.第2章定线表格，2.1定线表格的基本概念，2.2定线表格的顺序储存，2.3定线表格的链储存，2.4定线表格的应用，本章摘要，2.5排序表格，2.1定线表格的基本概念，2.1.1定线表格的定义，2.1.2定线表格中的运算，2.1.1定线表格中的定义定线表格是具有相同性质的资料元素的有限序列。此序列中包含的元素数称为线性表的长度，表示为n0。如果N=0，则线型表格为空表格。也就是说，表格中没有元素。将序列的i(i表示位顺序)元素设置为ai(1In)。通常，定线表格为： (a1、a2、ai、ai1、an)，其中a1是第一个元素(页眉元素，a2是第二个元素，an是最后一个元素，也称为页脚元素)。例如，在线性表格(1，4，3，2，8，10)中，1是表头元素，10是页尾元素。2.1.2线性表格的运算线性表格的预设运算为：(1)初始化线性表格InitList(ilength=0)。此算法的时间复杂性为O(1)。(4)查找路线表的长度ListLength(L)操作返回连续表L的长度。实际上，只需返回length成员的值。intlist length(sqlist * l) return(l-length)；此算法的时间复杂性为O(1)。(5)输出行表DispList(L)此操作在行表L不为空时按顺序显示L中每个元素的值。void displist(SqList * L) inti；if(ListEmpty(L)return；for(I=0)；IlengthI)printf(“% c”，L-dataI)；printf(“ n”)；，在此算法中，默认运算是for循环中的printf语句，因此时间复杂性为：O(L-length)或O(n)，(6)查找数据元素值GetElem(L，I，e)。此运算将i(1iListLength(L)元素的值存储在L中。Intgetelem (sqlist * l、inti、elemtype)此算法的时间复杂性为O(1)。(7)按元素值查找LocateElem(L，e)。此运算顺序会寻找元素的位元序列，其中第一个值等于e。如果没有这些元素，则返回值为0。Intrateelem (sqlist * l，elem type e) inti=0；While(ilength，在此算法中，默认运算是while循环中的I语句，因此时间复杂性为：O(L-length)或O(n)，(8)插入数据元素ListInsert(L，I，e)操作在序列表L的第一个位置(1Ilist length(L)1)插入新元素e。想法：如果I值不正确，将显示相应的错误消息。否则，顺序表会将原始I元素和后续元素都向后移动一个位置，将空位置插入新元素，顺序表长度会增加1。intrist insert (sqlist *)，逻辑位顺序1ii 1nMaxSize，对于此算法，元素不仅具有表长度L.length=n，而且相对于插入位置I的： i=n 1的移动次数也为零。如果I=1，则移动次数为n，达到最大值。定线表格sq具有n个位置，您可以在其中插入零件。假设Pi(=)是在第I个位置插入元素的概率，将元素插入到长度为n的直线表中时，元素必须移动的平均次数为：因此插入算法的平均时间复杂性为O(n)。(9)数据元素ListDelete(L，I，e)删除顺序表L中的I(1Ilist length(L)个元素。想法：如果I值不正确，将显示相应的错误消息。否则，线性表中第I个元素之后的元素将向前移动一个位置，复盖原始第I个元素，达到删除该元素的目的，并从最后一个序列表的长度中减去1。intListDelete(SqList*)，逻辑位序列1ii 1nMaxSize，对于此算法，当元素相对于表长度n和元素删除的位置I为： i=n时，移动数为0。如果I=1，则行程数为n-1。定线表格sq包含n个可以删除的元素。假设Pi(pi=)是从第I个位置删除元素的概率，则从长度为n的直线表中删除元素时，移动元素的平均次数为：=，因此删除算法的平均时间复杂性为O(n)。示例2.2设计了将x插入到有序线性表(顺序存储结构为顺序表)的适当位置并保持线性表顺序的算法。首先在顺序表l中找到存储x的位置I，然后将x插入L.datai，然后将顺序表的长度增加1。，voidInsert(SqList*)，查找插入位置，将元素向后移动一个位置，逻辑位顺序1ii 1nMaxSize，示例2.3设计了将两个元素排序(从小到大)的顺序表合并为一个顺序表的算法。解决思路：将两个顺序表合并成两个方向。返回到顺序表rk记录r中的元素数1 (I=0) 2 (j=0) r中的1(i=1)插入r (k=1) 3 (I=1) 2 (j=)，sqlist * merge (sqlist * p，sqlist * q) sqlist * r；Inti=0，j=0，k=0；r=(sqlist *)malloc(sizeof(sqlist)；While (ilength，while(I length) r-datak=p-dataI；I；k； while(j length) r-datak=q-dataj；j；k； r-length=k；/*或p-length q-length */return(r)；，范例2.4 n，线性表格a建立时间复杂度为O(n)、空间复杂性为O(1)的演算法，以从线性表格中删除值为item的所有资料元素。解决方案：使用k记录顺序表a中的item等元素数扫描a边缘统计k，将非item元素移动到k位置前，然后修改a的长度。相应的算法为：voiddel node 1(SqList/* ordered table a的长度为k*/，算法1:类似于构建顺序表，voiddel node 2(SqList/* ordered table a的长度减少*/，算法2，在上述算法中，只有一个while循环，时间复杂性为O(n)。算法仅使用了两个名为I，k的临时变量，空间复杂性为O(1)。2.3行表的链存储，2.3.1行表的链存储-链接表，2.3.2单链接表的基本操作的实现，2.3.3双链接表，2.3.4环链接表，2.3.5静态链接表，2.3.1行表的链存储-每个存储节点不仅包含有关存储元素本身的信息(称为数据域)，而且包含有关元素之间逻辑关系的信息的链存储(即，前体节点包含具有后缀节点的地址信息)。这称为指针域，可以方便地查找后续节点的位置，从而加快数据检索速度。通常，每个节点都有一个或多个这样的指针字段。如果一个节点的“指针”字段不需要节点，则仅该值为空，并显示为常量NULL。顺序表中的每个元素最多有一个前导元素和一个后续元素，即数据元素之间存在一对一的逻辑关系，因此存储链最简单、最常用的方法是仅设置指向该后续节点的指针域，除非每个节点都有数据域。此配置的链接表称为线性单向链接表。前导节点单链表示意图，为了便于线性表的链存储中插入和删除算法的实现，每个链表都有一个标题节点，并且相应的链接列表由标题节点的指针唯一标识。在单个链接列表中，每个节点仅包含指向后续节点的一个指针，因此，访问一个节点后，您只能访问后续节点，而不能访问其前一个节点。另一种可用的方法是，通过设置两个指针字段(:在每个节点上具有数字字段时除外)，使其分别指向相应的前后节点，而配置的链接表称为线性双向链接表(简单地说是双链接表)。前面节点的2链接列表图，在2链接列表中，每个节点都包含一个指向后继节点的指针和指向前置节点的指针，因此，访问一个节点后，可以依次反向访问每个节点，也可以依次正向访问每个节点。双链路列表的特征，假定在单个链接列表中，每个节点类型都显示为LinkList，并且必须包含存储元素的数据域。其中data将类型表示为常规类型标识符ElemType，下一个(next)包含用于存储后继元素位置的指针域。LinkList类型定义为：typedefstructLNode/*，单一连结表格节点类型*/ ElemTypedata；StructLNode * next/*指向后续节点*/LinkList。2.3.2单链路列表基本运算的实现，1 .创建单个链接列表首先考虑如何创建单个链接列表。假设通过包含n个数据的数组创建单个连接的列表。设置单个链接表的常用方法是使用两种：(1)标题插入方法构建表：此方法从空表开始读取字符数组a中的字符，创建新节点，将读取的数据保存到新节点的数据字段中，然后将新节点插入到当前链接表的标题中，直到结束。使用Headline创建表的算法为：voidcreatelistf (link list *)，I=0，I=1，I=2，I=3，head，head，head，head，head，head，(2)插入最终节点后，使用“插入标题”方法创建连接的列表。但是，生成的链接表中节点的顺序与原始数组元素的顺序相反。如果希望两者的顺序一致，可以使用尾部插值方法创建。此方法是在当前连接的列表的页脚上方插入新节点。为此，必须始终添加结束指针r以指向当前连接的列表的结束节点。使用尾部插值方法生成表的算法如下：voidcreatelistr (linklist */*终端节点next域为空*/，b，c，d，a，I=0，I=1，I=2，I=3，2 .插入节点插入操作是在单个链接表中第I个节点的位置插入值为x的新节点。首先在单个链接列表中查找i-1节点，然后在其后插入新节点。单个链接列表插入节点的过程如下图所示。插入节点外形图，3 .删除节点操作删除单个链接表中的第I个节点。首先在单个链接列表中查找i-1节点，然后删除其后的节点。删除单个链接列表节点的过程如下图所示。删除节点图，4 .线性表基本运算实现(1)线性表初始化InitList(L)此运算创建空的单链接表，即头节点。VoidInitList(LinkList*，(2)删除线性表DestroyList(L)释放单个链接表L占用的内存空间。确保每个节点都有一个空间。Voiddestroylist (link list * ，(3)线性表是否为空ListEmpty(L)如果单个链接表L中没有数据节点，则返回true，否则返回false。intlist empty(link list * l) return(l-next=null)；，(4)查找路线表的长度ListLength(L)返回单个链接表L中的数据节点数。intlist length(link list * l) link list * p=l；inti=0；While(p-next)！=NULL) I；p=p-next； return(I)；，(5)输出线路表DispList(L)扫描单个链路表L中的每个数据节点，并显示每个节点的数据域值。void displist(link list * l) link list * p=l-next；While(p)！=NULL)printf(%c ，p-data)；p=p-next； printf(“ n”)；，(6)定线表格L中指定位置的资料元素GetElem(L，I，intn=1；While(p)！=NULL，(8)插入数据点list insert (，if(p=null)return 0；/*找不到具有i-1位顺序的节点*/else/*找到具有i-1位顺序的节点* p */ s=(link list *)malloc(sizeof(link)/*创建新节点* s */s-data=e；s-next=p-next；/* *s在*p后插入*/p-next=s；Return1，(9)删除数据点list delete (，if(p=null)return 0；/* i-1位顺序的节点无*/else/* i-1位顺序的节点查找* p */ q=p-next；/*q指向要删除的节点。*/if(q=NULL)return 0；/*如果I节点不存在，则返回0*/p-next=q-next。/*从单个链接列表中删除*q节点*/free(q)。/*释放*q节点*/return 1；，范例2.5表示c=a1，B1，a2，B2，an，bn设置为行表，使用read节点的HC单个链接表存档，a=a1，a2，an，b=B1，B2，bn，解决方案：创建算法，以将两个拆分的行表存档为进退刀节点的单个链接表。首先，设置两个头节点*ha和*hb。这两个节点分别指向所拆分的线性表a和B、ra和Rb的两个单个链接表的表末尾，用p指针扫描单个链接表HC，扫描当前节点*p链，沿next域向下移动一个节点，如果p不为空，则从当前节点*