数据基础及结构 4

第2章线性表1本章目录01.问题导入：购物车背后的数据结构02.基础定义：线性表的定义与抽象数据类型03.顺序存储：线性表的顺序存储结构（顺序表）04.链式存储：线性表的链式存储结构（单链表）05.总结应用：应用案例与本章小结问题导入：购物车是如何管理的？生活场景在淘宝、京东等电商平台挑选商品时，我们通常会将心仪的商品加入“购物车”暂存。核心问题平台如何高效管理海量用户的购物车数据？如何支持快速的添加、删除和修改商品数量操作？底层逻辑购物车的底层实现依赖于“线性表”数据结构。无论是顺序表还是链表，都能很好地支持这些基础操作。线性表的定义基本定义由n(n≥0)个数据元素组成的有限序列，元素之间具有顺序性。逻辑特征(一对一)唯一的开始结点（无前驱）和唯一的终端结点（无后继）。其余内部结点有且仅有一个直接前驱和一个直接后继。通俗理解如同一条直线，元素一个接一个地顺序排列。逻辑特征：对于非空线性表：（1）有且仅有一个开始结点a1，它没有前驱，只有一个直接后继a2；（2）有且仅有一个终端结点an，它没有后继，只有一个直接前驱an－1；（3）其余内部结点，都有且仅有一个直接前驱和一个直接后继；（4）线性表中的数据元素之间是一种一对一的线性关系。抽象数据类型(ADT)线性表ADT核心定义1.数据对象(D)定义线性表中数据元素的集合，通常具有相同性质。2.数据关系(R1)定义数据元素之间的一对一关系，即线性结构的前驱后继关系。3.基本操作(P)InitList(L):初始化线性表ListInsert(L,i,e):插入元素ListDelete(L,i):删除元素ListSearch(L,e):查找元素抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}{称n

为线性表的表长;n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}ADT线性表定义示意线性表的两种存储结构顺序存储结构(Sequential)数据元素存储在连续的内存空间中，物理地址相邻特点：随机存取效率高，但插入删除需移动大量元素类比：教室中按座位号连续就坐的同学链式存储结构(Linked)数据元素分散存储，通过指针链接，物理地址可不相邻特点：插入删除灵活，但查找需从头遍历类比：分布在教室各处但知道下家位置的同学顺序表的结构定义基本概念采用顺序存储结构的线性表，将逻辑上相邻的元素存储在物理位置相邻的存储单元中。核心特点随机存取：通过首地址和索引可直接计算内存地址，访问速度快。存储密度高：仅存储数据元素本身，无需额外指针开销。C++结构定义typedefstruct{ElemType*elem;//数据元素起始地址intlength;//当前长度|intlistsize;//总容量}SeqList;顺序表的结构定义内存存储示意图图示展示了顺序表在内存中的连续存储形式。每个元素占据固定大小的内存单元，地址连续递增，便于快速定位。顺序表的随机存取假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：

LOC(ai+1)=LOC(ai)+L线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L也就是说，在顺序表中，每个数据元素ai

的存储地址是该元素在表中的位置i的线性函数顺序表的基本操作：初始化操作目标创建一个空的顺序表，为后续存储数据做准备。算法步骤分配内存：为数组分配初始容量的连续空间。初始化属性：长度设为listsize，记录存储容量。时间复杂度O(1)-仅需常数时间完成初始化操作。执行流程示意顺序表的基本操作：初始化C++代码实现constintLISTSIZE=100;//初始分配的表空间大小，可根据实际而定,这里假定为100constintINCREMENT=10;//当线性表由于插入导致空间不足而进行扩容时，申请扩容的空间大小usingElemType=int;//ElemType为实际数据元素的类型，这里假定为int型typedefstruct{ElemType*elem;//顺序表存储空间的首地址

intlength;//顺序表中数据元素的个数

intListsize;//当前分配的存储容量，即最多能存放的数据元素的个数}Seqlist;顺序表的基本操作：插入线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素e（1≤i≤n+1），使长度为n的线性表

（a1,a2,…，ai-1,ai,…,an）变成长度为n+1的线性表（a1,a2,…，ai-1,e,ai,…,an）此时数据元素之间的逻辑关系发生了如下改变：<ai-1,ai><ai-1,e>，<e,ai>顺序表的基本操作：插入代码voidListInsert(SeqList*L,ElemTypee,inti){//将新结点e插入到顺序表L的第i个结点之前if(i<1||i>L->length+1){//检查插入位置是否合法returnFALSE;//插入位置非法}if(L->length>=L->listsize){//检查是否需要扩容L->listsize+=INCREMENT;//增加存储容量//使用new重新分配内存ElemType*newElem=new(std::nothrow)ElemType[L->listsize];if(!newElem){exit(OVERFLOW);//扩容失败，退出程序}for(intj=0;j<L->length;++j){//复制旧数据到新内存空间newElem[j]=L->elem[j];}deleteL->elem;//删除旧内存空间L->elem=newElem;//更新指针到新内存空间

顺序表的基本操作：插入代码//元素后移（插入位置之后）for(intj=L->length-1;j>=i-1;--j){L->elem[j+1]=L->elem[j];}//插入新元素L->elem[i-1]=e;L->length++;//表长加1}

注意：算法中结点后移的方向，必须从表中最后一个结点开始后移，直至将第i个结点后移为止。顺序表插入的时间复杂度分析最好情况(O(1))在表尾插入，无需移动任何元素，操作一步到位。最坏情况(O(n))在表头插入，需要移动所有n个元素，效率最低。平均情况(O(n))假设插入概率均等，平均需要移动n/2个元素。性能总结顺序表插入效率较低，不适合频繁在表头插入的场景。顺序表的基本操作：删除线性表的删除运算是指将表的第i(1≤i≤n)个结点删去，使长度为n的线性表（a1,a2,…，ai-1,ai,…,an）变成长度为n-1的线性表（a1,a2,…，ai-1,ai+1,…,an）此时数据元素之间的逻辑关系发生了如下改变：<ai-1,ai>，<ai,ai+1><ai-1,ai+1>顺序表的基本操作：删除核心算法步骤检查合法性：确保i在1到length之间。元素前移：从第i+1个元素开始，依次向前覆盖。更新长度：表长length减1。时间复杂度最好O(1)，平均/最坏O(n)操作目标删除顺序表中第i个位置的元素，并调整后续元素位置。关键问题删除位置之后的所有元素都需要向前移动一位，以填补空缺。顺序表的基本操作：删除C++代码intListDelete(Seqlist*L,inti,ElemType*e){//在顺序表L中删除第i个元素，并用e返回其值，//i的合法值为1≤i≤ListLength(L) intj;if((i<1)||(i>L->length))returnFALSE;*e=L->elem[i-1];//将删除的元素存放到e所指向的变量中

for(j=i;j<L->length;j++)L->elem[j-1]=L->elem[j];//结点前移L->length--;//表长度减1returnTRUE;}

顺序表删除的时间复杂度分析最好情况(O(1))删除表尾元素，不需要移动任何元素，效率最高。最坏情况(O(n))删除表头元素，需要移动n-1个元素，效率最低。平均情况(O(n))假设概率均等，平均需要移动(n-1)/2个元素。核心结论：顺序表的删除操作效率同样较低，不适合频繁进行删除的场景。顺序表的基本操作：按值查找操作目标与方法•目标：在顺序表中查找值为e的元素。•方法：采用顺序查找，从表头开始逐个比较。时间复杂度分析最坏情况下需遍历所有元素，时间复杂度为O(n)。//顺序查找核心代码boolcompare(ElemTypea,ElemTypeb){returna==b;}intListSearch(SeqList*L,ElemTypee){for(inti=0;i<L->length;++i){//逐个比较元素if(compare(L->elem[i],e)){returni;//找到返回索引}}return-1;//未找到}顺序表的优缺点总结核心优势(Pros)随机存取，访问速度快可以直接通过下标访问元素，时间复杂度为O(1)，效率极高。存储密度高，结构简单无需额外空间存储指针，只存储数据元素，空间利用率较好。实现简单，易于理解基于数组实现，逻辑直观，开发和调试成本较低。主要局限(Cons)插入删除效率低需要移动大量元素来保持连续性，平均时间复杂度为O(n)。需要预先分配固定空间初始化需指定容量，易造成空间浪费或溢出，灵活性差。空间扩展不方便扩容通常需要重新分配内存并复制数据，开销较大。线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址或位置信息，这个信息称为指针（pointer）或链(link)。这两部分信息组成了链表中的结点结构。

结点node=元素data+指针next

其中，data域是数据域，用来存放结点的值，next域是指针域，亦称链域，用来存储结点的直接后继的地址或位置。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起的，由于上述链表的每个结点只有一个链域，故将这种链表称为单链表(SingleLinkedList)。单链表的存储结构

单链表中每个结点的存储地址是存储在其前驱结点next域中，而开始结点无前驱，因此应设头指针head指向开始结点。同时由于终端结点无后继，其指针域为空，即NULL。（图示中也可用^表示）。例如，下图是单链表(red，orange，green，yellow，blue，purple，white，black)的单链表示意图。单链表的结构定义由于讨论问题时只注重结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此我们通常是用箭头来表示链域中的指针，于是链表就可以直观地画成用箭头链接起来的结点序列。如图2-5可简单画成下图的形式。由于单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。例如，若头指针是head，则把链表称为表head。usingDataType=int;//假设结点中的数据类型为整型typedefstructnode{//结点类型定义DataTypedata;//结点的数据域structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;ListNode*p;LinkListhead;单链表的头结点

有时我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存放任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域指向第一个结点的地址，如图2-7所示，此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”。单链表的基本操作：初始化操作目标创建一个空的带头结点的单链表，为后续数据插入做准备。算法步骤01.创建头结点：为头结点分配内存空间(malloc)。02.初始化指针：将头结点的指针域置为NULL。初始化C++代码LinkListInitList(){LinkListL=newLinkList();//建立头结点L->next=nullptr;returnL;//建立空的单链表L}单链表的基本操作：按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索直至搜索到第i个结点为止。因此，链表是一种顺序存取结构。在搜索过程中，需要设置一个指针（设为p）依次指向所数到的结点（即*p），显然其初值应为L->next（首元结点），并需要设置一个变量（设为j）以记录所指结点的序号。算法中需要注意控制循环的条件以及p和j的同步问题。另外，需要考虑在所指定结点不存在时返回的值。单链表的基本操作：按序号查找C++代码ListNode*GetElem(LinkListL,inti){//在单链表L中查找第i(1<=i<=n)个数据元素结点，若找到返回该结点的存储//位置，否则返回NULL。ListNode*p=L->next;

intj=1;while(j!=i&&p!=nullptr)//当前结点不是目标结点，并且表不空时继续搜索{p=p->next;

j++;}returnp;}单链表的基本操作：按值查找

按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则，返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key做比较。其算法如下：ListNode*LocateElem(LinkListL,DataTypee){//在带头结点的单链表head中查找其值为key的结点，若找到返回其位置，没找//到返回NULL。ListNode*p=L->next;while(p!=nullptr&&p->data!=e){//当前结点不是目标结点且表不空继续搜索 p=p->next;}returnp;}单链表的基本操作：插入在带头结点的单链表L中第i个位置前插入一个数据元素e的过程如图所示，分为三步：（1）查找：在单链表中找到第i-1个结点并由指针p指示；（2）构造新结点：申请结点空间，并将其数据域赋值为e；（3）插入链表中：通过修改指针域完成插入操作。单链表的基本操作：插入操作目标与核心优势目标：在第i个位置插入新元素e优势：无需移动任何元素，仅需修改指针指向时间复杂度分析主要耗时：查找前驱结点(需遍历链表)复杂度：O(n)，n为链表长度核心算法代码intListInsert(LinkListL,DataTypee,inti){//将值为e的新结点插入到带头结点的单链表L的第i个结点的位置上ListNode*p,*s;p=GetElem(L,i-1);//寻找第i-1个结点if(p==nullptr)returnFALSE;//插入位置i有错s=newListNode();//申请结点空间s->data=e;s->next=p->next;p->next=s;returnTRUE;}单链表的基本操作：删除

在带头结点的单链表L中删除第i个结点的过程如图所示，分为两步：（1）查找：在单链表中找到第i-1个结点并用p指示；（2）修改指针p->next=q->next；（3）释放结点空间q。单链表的基本操作：删除C++代码实现intListDelete(LinkListL,inti){//删除带头结点的单链表L中的第i个结点ListNode*p,*q;p=GetElem(L,i-1);//寻找第i-1个结点if(p==nullptr||p->next==nullptr)returnFALSE;//删除位置有错q=p->next;p->next=q->next;deleteq;//释放第i个结点的内存returnTRUE;}单链表的基本操作：删除时间复杂度分析

设单链表的长度为n，则删去第i个结点仅当1<=i<=n时是合法的。注意，当i=n+1是，虽然被删结点不存在，但其前驱结点却存在，它是终端结点，因此被删结点的直接前驱(p)存在并不意味着被删结点就一定存在(p->next).从上面的讨论可知：链表实现的插入删除运算，无需移动结点，仅需修改指针。在单链表中插入、删除一个结点，必须知道其前驱结点。单链表不支持按元素序号进行随机访问，只能从头指针开始按顺序逐个进行查找。时间复杂度分析主要耗时：查找前驱结点(需遍历链表)复杂度：O(n)，n为链表长度单链表的优缺点总结核心优势(Advantages)插入删除效率高无需移动元素，仅修改指针，时间复杂度O(1)动态分配空间按需分配内存，无需预分配，空间利用率高易于扩展可方便地在任意位置添加新结点，结构灵活存在局限(Disadvantages)顺序存取，查找效率低不支持随机访问，查找需从头遍历，时间复杂度O(n)需要额外空间开销每个结点需存储指针，导致存储密度低于顺序表实现相对复杂指针操作容易出错，代码编写和调试比顺序表复杂循环链表的定义循环链表是一种首尾相接的链表，将单链表最后一个结点的指针域由NULL改为指向表头结点，就得到了单链形式的循环链表，称为循环单链表。在循环单链表中，表中所有结点都被链在一个环上，为使得某些操作实现方便，在循环单链表中也可设置一个头结点。这样，空循环链表仅由一个自成循环的头结点构成。带头结点的循环单链表如图所示。循环链表的定义带头结点的循环单链表的各种操作的实现算法与带头结点的单链表的实现算法相似，差别仅在于算法中判别当前结点p是否为表尾结点的条件不同。单链表中判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件则是p!=L或p->next!=L。在循环单链表中附设尾指针有时比附设头指针会使操作变得更简单。如在用头指针表示的循环单链表中，找开始结点a1的时间复杂度是O(1)，然而要找到终端结点an

，则需要从头指针开始遍历整个链表，其时间复杂度是O(n)，如果用尾指针rear来表示循环链表，则查找开始结点和终端结点都很方便，它们的存储位置分别是rear->next->next和rear，时间复杂度都是O(1)。因此，实际中多采用尾指针表示循环单链表。双向链表的定义单循环链表中，虽然从任一已知结点出发能找到其直接前驱结点，但时间消耗是O(n)。如希望从表中快速确定一个结点的直接前驱，可以在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样形成的链表中有两条方向不同的链，故称之为双（向）链表（DoubleLinkedList）。双链表的结构定义如下：typedefstructDulNode{DataTypedata;structDulNode*prior;structDulNode*next;}DulNode,*DulLinkList;双向链表的定义与单链表类似，双链表也可增加头结点使双链表的某些运算变得更为方便。同时双链表也可以有循环链表，称为双向循环链表，其结构如图所示。双向链表的前插操作双向链表的前插过程如图所示，此处要注意修改指针的前后顺序，不得导致某些结点的丢失。前两个步骤申请结点空间并让指针S指向此空间，剩余步骤的语句序列如下：③s->prior=p->prior;④s->next=p;⑤p->prior->next=s;⑥p->prior=s;双向链表的删除操作双向链表删除操作的语句序列如下：①p->prior->next=p->next;②p->next->prior=p->prior;③free(p);引入案例的实现假设你正在使用在线购物平台的购物车功能。你的购物车使用链表来存储商品信息。每当你添加新商品或修改已有商品的数量时，平台通过操作链表来更新购物车的内容。1.添加商品操作：

-将一个新商品添加到购物车链表中。-代码示例：typedefstructItem{intproductId;intquantity;structItem*next;}Item;voidaddItem(Item*&head,intproductId,intquantity){Item*newItem=newItem();newItem->productId=productId;newItem->quantity=quantity;newItem->next=head;head=newItem;}引入案例的实现2.删除商品操作：

-从购物车中删除一个指定的商品。-代码示例：voidremoveItem(Item*&head,intproductId){Item*current=head;Item*previous=nullptr;while(current!=nullptr){if(current->productId==productId){if(previous==nullptr){head=current->next;}else{previous->next=current->next;}deletecurrent;return;}previous=current;current=current->next;}}引入案例的实现3.更新商品数量操作：

-更新购物车中某个商品的数量。-代码示例：voidupdateItemQuantity(Item*&head,intproductId,intnewQuantity){Item*current=head;while(current!=nullptr){if(current->productId==productId){current->quantity=newQuantity;return;}current=current->next;}}静态链表的定义静态链表：用数组存放线性表中的元素，但并不按照元素顺序在数组中依序存放，而是给每个数组元素增加一个域，用于指示线性表中下一个元素的位置（即它在数组中的下标）。静态链表在物理存储空间上依赖于数组，元素逻辑链接关系却是采用了链表的思想。结构定义为：#defineMAXSIZE1000//链表的最大长度typedefstruct{ElemTypedata;intnext;}component,SLinkList[MAXSIZE];静态链表的基本操作实例静态链表仍需要预先分配一个比较大的数组空间，但在线性表中插入和删除元素时，不需要移动其他元素，仅需要修改相应的链接信息。如图所示，下标0是静态链表的头结点，next的值为1，则链表的第一个元素在下标1的位置，data的值为ZHAO，下一个元素的位置在ZHAO的next域中存储，即2。以此类推，可以得到此静态链表的序列为（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）。最后一个元素WANG的next的值为0。静态链表的查找算法intLocateElem_SL(SLinkList&S,ElemTypee){//在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的位序，否则返回0。inti=S[0].next;//i指示表中第一个结点while(i&&S[i].data!=e)i=S[i].next;//在表中顺链查找

returni;}//LocateElem_SL静态链表的插入和删除