线性表（知识梳理）

🕗 发布于 2024-11-07 13:54 数据结构

线性表是最基本且最常用的一种线性结构

线性结构的基本特点是除第一个元素无直接前驱、最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和一个后继。

线性表：由n（n≥0）个数据特性相同的元素构成的有限序列
线性表的长度：线性表中元素的个数n（n≥0）（当n = 0时称之为空表）
数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系

非空的线性表或线性结构的特点：

存在唯一的一个被称作“第一个”的数据元素；
存在唯一的一个被称作“最后一个”的数据元素；
除第一个元素之外，结构中的每个数据元素均只有一个前驱；
除最后一个元素之外，结构中的每个数据元素均只有一个后继。

线性表的抽象数据类型定义：

ADT List{
数据对象 ：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系 ：R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
基本操作 ：

InitList(&L) 　　　
操作结果：构造一个空的线性表L。　　
DestroyList(&L) 　　　
初始条件：线性表L已存在。　　　
操作结果：销毁线性表L。　　
ClearList(&L) 　　　
初始条件：线性表L已存在。　　
操作结果：将L重置为空表。　　
ListEmpty(L) 　　　
初始条件：线性表L已存在。　　　
操作结果：若L为空表，则返回true，否则返回false。　　
ListLength(L) 　　　
初始条件：线性表L已存在。
操作结果：返回L中数据元素的个数。　　
GetElem(L,i,&e) 　　　
初始条件：线性表L已存在，且1≤i≤ListLength(L)。　　　
操作结果：用e返回L中第i个数据元素的值。
LocateElem(L,e) 　　
初始条件：线性表L已存在。　　　
操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。
PriorElem(L,cur_e,&pre_e) 　　
初始条件：线性表L已存在。　　　
操作结果：若cur_e 是 L的数据元素，且不是第一个，则用pre_e 返回其前驱，否则操作失败，pre_e无定义。 (查找给定节点cur_e的前驱节点。cur_e是当前节点，pre_e是一个指针，用于存储找到的前驱节点的地址。)
NextElem(L,cur_e,&next_e) 　
初始条件：线性表L已存在。　　　
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。
ListInsert(&L,i,e) 　　
初始条件：线性表L已存在，且1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。　　
ListDelete(&L,i) 　　　
初始条件：线性表L已存在且非空，且1≤i≤ListLength(L)。　　　
操作结果：删除L的第i个数据元素，L的长度减1。
TraverseList(L) 　　　
初始条件：线性表L已存在。　　　
操作结果：对线性表L进行遍历，在遍历过程中对L的每个节点访问一次。

}ADT List

抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。

线性表的顺序表示和实现是计算机科学中的基础概念，以下是对这一概念的整理和输出：

顺序表

线性表的顺序表示

定义

线性表的顺序表示使用一组地址连续的存储单元来依次存储线性表的数据元素。这种表示方法也被称为顺序存储结构或顺序映像。采用这种存储结构的线性表被称为顺序表（Sequential List）。

特点

逻辑上相邻的数据元素在物理位置上也是相邻的。
每个元素占用固定大小的存储空间，通常用l表示。
第i+1个数据元素的存储位置LOC(ai+1)与第i个数据元素的存储位置LOC(ai)之间的关系为：
LOC(ai+1) = LOC(ai) + l 。

存储位置计算

第i个数据元素ai的存储位置LOC(ai)可以通过公式计算：LOC(ai) = LOC(a1) + (i−1) × l。
LOC(a1)是线性表的第一个数据元素a1的存储位置，也称为线性表的起始位置或基地址。

随机存取

确定了存储线性表的起始位置后，线性表中任一数据元素都可随机存取。
顺序存储结构是一种随机存取的存储结构。

线性表的顺序实现

数组表示

高级程序设计语言中的数组类型具有随机存取的特性，因此通常用数组来描述顺序存储结构。

动态数组实现（C语言）

在C语言中，可以使用动态分配的一维数组来表示线性表，以适应长度可变的需求。

顺序表操作概述

顺序表的基本操作包括初始化、取值、查找、插入和删除。

1. 初始化

顺序表的初始化操作就是构造一个空的顺序表。

【算法步骤】
① 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
② 将表的当前长度设为0。

【算法描述】

Status InitList(SqList &L)
{//构造一个空的顺序表L
 L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
 if(!L.elem) exit(OVERFLOW);　　　 //存储分配失败退出
 L.length=0; //空表长度为0 
 return OK; 
}

动态分配线性表的存储区域可以更有效地利用系统的资源，当不需要该线性表时，可以使用销毁操作及时释放占用的存储空间。

2. 取值

取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。
由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到，elem[i-1]单元存储第i个数据元素。

【算法步骤】
① 判断指定的位置序号i值是否合理（1≤i≤L.length），若不合理，则返回ERROR。
② 若i值合理，则将第i个数据元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的传值。

【算法描述】

Status GetElem(SqList L,int i,ElemType &e)
{
 if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR
 e=L.elem[i-1]; //elem[i-1]单元存储第i个数据元素　　　　　　　　　　　　　　　　　　　
 return OK;
}

顺序表取值算法的时间复杂度为O(1)。

3. 查找

查找操作是根据指定的元素值e，查找顺序表中第1个值与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

【算法步骤】
① 从第一个元素起，依次将其值和e相比较，若找到值与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1。
② 若查遍整个顺序表都没有找到，则查找失败，返回0。

【算法描述】

int LocateElem(SqList L,ElemType e)
{//在顺序表L中查找值为e的数据元素，返回其序号
 for(i=0;i< L.length;i++) 
　　　if(L.elem[i]==e) return i+1; //查找成功，返回序号i+1
 return 0; //查找失败，返回0
}

在这里插入图片描述

4. 插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，
使长度为n的线行表：(a1,…,ai−1,ai,…,an) 变成长度为n + 1的线性表： (a1,…,ai−1,e,ai,…,an)

【算法步骤】
① 判断插入位置i是否合法（i值的合法范围是1≤i≤n + 1），若不合法则返回ERROR。
② 判断顺序表的存储空间是否已满，若满则返回ERROR。
③ 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i = n + 1时无须移动）。
④ 将要插入的新元素e放入第i个位置。
⑤ 表长加1。

Status ListInsert(SqList &L,int i ,ElemType e)
{//在顺序表L中第i个位置插入新的元素e，i值的合法范围是1≤i≤L.length+1
 if((i<1)||(i>L.length+1)) return ERROR; //i值不合法
 if(L.length==MAXSIZE) return ERROR; //当前存储空间已满
 for(j=L.length-1;j>=i-1;j--)
　　　L.elem[j+1]=L.elem[j];　　　　　　　　　　　 //插入位置及之后的元素后移
 L.elem[i-1]=e;　　　　　　　　　　　　　　　　　 //将新元素e放入第i个位置
 ++L.length; //表长加1 
 return OK; 
}

上述算法没有处理表的动态扩充，因此当表长已经达到预设的最大空间时，则不能再插入元素。

在这里插入图片描述
由此可见，顺序表插入算法的平均时间复杂度为O(n)。

5. 删除

线性表的删除操作是指将表的第i个元素删去，
将长度为n的线性表： (a1,…,ai−1,ai,ai+1,…,an) 变成长度为n−1的线性表：(a1,…,ai−1,ai+1,…,an)
一般情况下，删除第i（1≤i≤n）个元素时需将第i + 1个至第n个元素（共n−i个元素）依次向前移动一个位置（i = n 时无须移动）。

【算法步骤】
① 判断删除位置i是否合法（合法值为1≤i≤n），若不合法则返回ERROR。
② 将第i+1个至第n个元素依次向前移动一个位置（i=n时无须移动）。
③ 表长减1。

【算法描述】

Status ListDelete(SqList &L,int i)
{//在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.length 
 if((i<1)||(i>L.length)) return ERROR; //i值不合法
 for(j=i;j<=L.length-1;j++)　　　　　　　　　　
　　　L.elem[j-1]=L.elem[j];　　　　　　 //被删除元素之后的元素前移
 --L.length;　　　　　　　 //表长减1 
 return OK; 
}

在这里插入图片描述

链表

线性表的链式表示和实现

1. 单链表的定义和表示

线性表的链式存储结构使用一组任意的存储单元来存储数据元素，这些存储单元可以是不连续的。每个数据元素（节点）包含两个部分：

数据域：存储数据元素的信息。
指针域：存储直接后继的存储位置，也称为链。

2. 节点和链表

节点（Node）：包含数据域和指针域的存储映像。
链表：由多个节点链接而成的线性表的链式存储结构。

3. 单链表的特点

每个节点只包含一个指向直接后继的指针域，因此称为单链表。
单链表的存取必须从头指针开始，头指针指向链表中的第一个节点（首元节点）。
单链表中最后一个节点的指针域为空（NULL），表示没有直接后继。

4. 单链表的C语言描述

单链表可由头指针唯一确定。在C语言中可用“结构指针”来描述：

//- - - - - 单链表的存储结构- - - - - 
typedef struct LNode
{
 ElemType data;　　　　　　　　 //节点的数据域
 struct LNode *next;　　　　　　 //节点的指针域
}LNode,*LinkList;　　　　　　　　　 //LinkList为指向结构体LNode的指针类型

LNode：定义了一个单链表节点的结构体，包含数据域和指针域。
LinkList：定义了一个指向LNode结构体的指针类型，用于操作单链表。

在这里插入图片描述

头节点

为了处理方便，在单链表的第一个节点之前附设一个节点。
在这里插入图片描述
链表增加头节点的作用如下：

便于首元节点的处理
增加了头节点后，首元节点的地址保存在头节点（其“前驱”节点）的指针域中，则对链
表的第一个数据元素的操作与对其他数据元素的操作相同，无须进行特殊处理。
便于空表和非空表的统一处理
当链表不设头节点时，假设L为单链表的头指针，它应该指向首元节点，则当单链表为长度n为0的空表时， L指针为空（判定空表的条件可记为：L = = NULL）。
增加头节点后，无论链表是否为空，头指针都是指向头节点的非空指针。若为空表，则头节点的指针域为空（判定空表的条件可记为：L −>next = = NULL）。

单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存储结构。因此，其基本操作的实现不同于顺序表。

单链表基本操作的实现

1. 初始化

单链表的初始化操作就是构造一个如图2.10（b）所示的空表。

【算法步骤】
① 生成新节点作为头节点，用头指针L指向头节点。
② 头节点的指针域置空。

【算法描述】

Status InitList(LinkList &L)
{//构造一个空的单链表L 
 L=new LNode;　　　　//生成新节点作为头节点，用头指针L指向头节点
 L->next=NULL;　　　//头节点的指针域置空
 return OK; 
}

2. 取值

和顺序表不同，链表中逻辑相邻的节点并没有存储在物理相邻的单元中，这样，根据给定的节点位置序号i，在链表中获取该节点的值不能像顺序表那样随机访问，而只能从链表的首元节点出发，顺着链域next逐个节点向下访问。

【算法步骤】
① 用指针p指向首元节点，用j做计数器初值赋为1。
② 从首元节点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为（NULL），并且没有到达序号为i的节点，则循环执行以下操作：
p指向下一个节点；计数器j相应加1。
③ 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j = i时，p所指的节点就是要找的第i个节点，用参数e保存当前节点的数据域，返回OK。

【算法描述】

Status GetElem(LinkList L,int i,ElemType &e)
{//在带头节点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
 p=L->next;j=1; //初始化，p指向首元节点，计数器j初值赋为1
 while(p&&j<i) //顺链域向后查找，直到p为空或p指向第i个元素
 { 
　　　p=p->next; //p指向下一个节点
　　　++j; //计数器j相应加1
 }
 if(!p||j>i)return ERROR; //i值不合法i>n或i<=0 
 e=p->data; //取第i个节点的数据域
 return OK; 
}

在这里插入图片描述

3. 查找

链表中按值查找的过程和顺序表类似，从链表的首元节点出发，依次将节点值和给定值e进行比较，返回查找结果。

【算法步骤】
① 用指针p指向首元节点。
② 从首元节点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p
所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一个节点。
③ 返回p。若查找成功，p此时指向节点的地址值，若查找失败，则p的值为NULL。

【算法描述】

LNode *LocateElem(LinkList L，ElemType e)
{//在带头节点的单链表L中查找值为e的元素
 p=L->next; //初始化，p指向首元节点
 while(p && p->data!=e) //顺链域向后查找，直到p为空或p所指节点的数据域等于e
　　　p=p->next; //p指向下一个节点
 return p; //查找成功返回值为e的节点地址p，查找失败p为NULL 
}

该算法的执行时间与待查找的值e相关，其平均时间复杂度分析类似于算法单链表的取值，也为O(n)。

4. 插入

【算法步骤】
将值为e的新节点插入表的第i个节点的位置，即插入节点ai−1与ai之间，具体插入过程如图2.12所示，图中对应的5个步骤说明如下。
① 查找节点ai−1并由指针p指向该节点。
② 生成一个新节点s。
③ 将新节点s的数据域置为e。
④ 将新节点s的指针域指向节点ai。
⑤ 将节点p的指针域指向新节点*s。

【算法描述】

Status ListInsert(LinkList &L,int i,ElemType e)
{//在带头节点的单链表L中第i个位置插入值为e的新节点
 p=L;j=0; 
 while(p && (j<i −1))
　　　{p=p->next;++j;} //查找第i−1个节点，p指向该节点
 if(!p||j>i −1) return ERROR; //i＞n+1或者i＜1
 s=new LNode; //生成新节点*s 
 s->data=e;　　　　　　　　　　 //将节点*s的数据域置为e
 s->next=p->next; //将节点*s的指针域指向节点ai
 p->next=s; //将节点*p的指针域指向节点*s
 return OK; 
}

和顺序表一样，如果表中有 n 个节点，则插入操作中合法的插入位置有 n+1 个，即1 ≤ i ≤ n+1。当 i=n+1 时，新节点则插在链表尾部。

在这里插入图片描述

5. 删除

在这里插入图片描述

【算法步骤】
① 查找节点ai−1并由指针p指向该节点。
② 临时保存待删除节点ai的地址在q中，以备释放。
③ 将节点*p的指针域指向ai的直接后继节点。
④ 释放节点ai的空间。

【算法描述】

Status ListDelete(LinkList &L,int i)
{//在带头节点的单链表L中，删除第i个元素
 p=L;j=0; 
 while((p->next) && (j<i-1)) //查找第i −1个节点，p指向该节点
　　　{p=p->next; ++j;}
 if(!(p->next)||(j>i-1)) return ERROR; //当i>n或i<1时，删除位置不合理
 q=p->next;　　　　　　　　　　　　 //临时保存被删节点的地址以备释放
 p->next=q->next; //改变删除节点前驱节点的指针域
 delete q;　　　　　　　　　　　　　 //释放删除节点的空间
 return OK; 
}

类似于插入算法，删除算法时间复杂度亦为O(n)。

6.创建单链表

链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素节点，并逐个插入链表。根据节点插入位置的不同，链表的创建方法可分为前插法和后插法。

前插法

前插法是通过将新节点逐个插入链表的头部（头节点之后）来创建链表，每次申请一个新
节点，读入相应的数据元素值，然后将新节点插入到头节点之后

【算法步骤】
① 创建一个只有头节点的空链表。
② 根据待创建链表包括的元素个数n，循环n次执行以下操作：
 生成一个新节点p；
 输入元素值赋给新节点p的数据域；
 将新节点*p插入到头节点之后。

【算法描述】

void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头节点的单链表L 
 L=new LNode; 
 L->next=NULL; 　　//先建立一个带头节点的空链表
 for(i=0;i<n;++i)
 {
　　 p=new LNode; //生成新节点*p
　　 cin>>p->data; //输入元素值赋给新节点*p的数据域
　　 p->next=L->next;L->next=p; //将新节点*p插入到头节点之后
 }
}

时间复杂度分析为O(n)。

后插法

后插法是通过将新节点逐个插入链表的尾部来创建链表。同前插法一样，每次申请一个新节点，读入相应的数据元素值。不同的是，为了使新节点能够插入表尾，需要增加一个尾指针r指向链表的尾节点。

【算法步骤】
① 创建一个只有头节点的空链表。
② 尾指针r初始化，指向头节点。
③ 根据创建链表包括的元素个数n，循环n次执行以下操作：
 生成一个新节点p；
 输入元素值赋给新节点p的数据域；
 将新节点p插入尾节点r之后；
 尾指针r指向新的尾节点*p。

【算法描述】

void CreateList_R(LinkList &L,int n)
{//正位序输入n个元素的值，建立带表头节点的单链表L 
 L=new LNode; 
 L->next=NULL; 　　//先建立一个带头节点的空链表
 r=L; 　　//尾指针r指向头节点
 for(i=0;i<n;++i)
  { 
　　　p=new LNode; 　　//生成新节点
　　　cin>>p->data; 　　//输入元素值赋给新节点*p的数据域
　　　p->next=NULL; r->next=p; 　　//将新节点*p插入尾节点*r之后
　　　r=p; 　　//r指向新的尾节点*p
 } 
}

时间复杂度分析为O(n)。

循环链表

在这里插入图片描述

双向链表

双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

//- - - - - 双向链表的存储结构- - - - -
typedef struct DuLNode
{ 
 ElemType data; //数据域
 struct DuLNode *prior; //指向直接前驱
 struct DuLNode *next; //指向直接后继
}DuLNode,*DuLinkList;

在这里插入图片描述

双向链表的插入

【算法描述】

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{//在带头节点的双向链表L中第i个位置之前插入元素e
 if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
　　　return ERROR; //p为NULL时，第i个元素不存在
 s=new DuLNode; //生成新节点*s
 s->data=e; //将节点*s数据域置为e
 s->prior=p->prior; //将节点*s插入L中，此步对应图2.20①
 p->prior->next=s; //对应图2.20②
 s->next=p; //对应图2.20③
 p->prior=s; //对应图2.20④
 return OK; 
}

双向链表的删除

【算法描述】

Status ListDelete_DuL(DuLinkList &L,int i)
{//删除带头节点的双向链表L中的第i个元素
 if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p 
　　　return ERROR; //p为NULL时，第i个元素不存在
 p->prior->next=p->next; //修改被删节点的前驱节点的后继指针，对
　　　　　　　　　　　　　　　　　　　 应图2.21①
 p->next->prior=p->prior; //修改被删节点的后继节点的前驱指针，对
　　　　　　　　　　　　　　　　　　 应图2.21②
 delete p; //释放被删节点的空间
 return OK; 
}

顺序表与链表的比较

1. 空间性能比较

存储空间分配：
- 顺序表：需要预先分配固定大小的存储空间，可能导致空间浪费或溢出。
- 链表：不需要预先分配空间，元素个数无限制，更灵活。
存储密度：
- 顺序表：存储密度为1，存储空间利用率为100%。
- 链表：需要额外的指针域，存储密度小于1，存储空间利用率较低。

2. 时间性能比较

存取元素效率：
- 顺序表：随机存取结构，可以直接在O(1)时间内存取任意位置的元素。
- 链表：顺序存取结构，访问第i个元素需要O(n)时间。
插入和删除操作效率：
- 链表：在确定位置后，插入或删除只需修改指针，时间复杂度为O(1)。
- 顺序表：插入或删除可能需要移动大量元素，平均时间复杂度为O(n)。

顺序表：适合元素个数固定或变化不大，且需要频繁进行元素存取的场景。它的存储密度高，空间利用率高，但存储空间需要预先分配，且插入和删除操作效率较低。

链表：适合元素个数变化较大，且需要频繁进行插入和删除操作的场景。它不需要预先分配存储空间，存储灵活，但存储密度低，空间利用率低，且存取元素效率较低。

在这里插入图片描述

原文地址：https://blog.csdn.net/Xiao_die888/article/details/143581180

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Flutter&鸿蒙next 中的 Drawer 导航栏
下一篇：梧桐数据库中处理连续日期序列的解决方案

macOS｜前端工程部署到Nginx服务器
前端工程部署到Nginx服务器
阅读更多2024-11-07
自己开发得期货资管模拟软件演示1.0.15版仅供学习
期货资管模拟软件是投资者学习和实践期货交易的重要工具。基于C++技术栈的期货资管模拟软件，以其高效性、稳定性和可扩展性，为投资者提供了卓越的交易体验。通过不断优化和完善软件框架设计，我们可以进一步提高
阅读更多2024-11-07
【WebRTC】视频采集模块中各个类的简单分析
WebRTC主体是基于C++实现的框架，有必要分析其中各个类之间的继承关系。视频采集模块的代码在modules/video_capture中，其中有很多个文件，逐一分析。需要说明的是，采集模块与使用的
阅读更多2024-11-07
深度学习引言
神经网络的强大之处在于，只需要提供输入和输出的数据，网络通过训练可以自动学习输入与输出之间的复杂非线性关系，而无需人为地设计特征提取的规则。当训练集规模较小的时候，模型能从数据中学习到的信息有限，这时
阅读更多2024-11-07
Linux 文件基本属性
轻松学习Linux 文件基本属性
阅读更多2024-11-07
道品科技智慧农业中的自动气象检测站
这些传感器通过实时监测环境参数，收集气象数据。1. **农作物种植**：为农民提供种植决策支持，如适时播种、施肥和灌溉等，提高农作物的产量和质量。5. **多样化应用**：可以根据不同的农业需求，定制
阅读更多2024-11-07
中小企业如何利用CRM系统提升竞争力
中小企业需要有效的工具来管理客户关系、优化业务流程并提升客户满意度。客户关系管理（CRM）系统正是这样一种工具，它能够帮助企业更好地理解和满足客户需求，从而提升竞争力。本文将探讨中小企业如何利用CRM
阅读更多2024-11-07
c++基础20数学知识阶乘和区间
c++基础20数学知识阶乘和区间
阅读更多2024-11-07
C# 都有哪些集合？
C# 提供了多种集合类型来满足不同场景的需求。泛型集合通常是首选，它们提供类型安全和高效操作。对于需要线程安全的场景，可以使用并发集合。而对于简单的场景，非泛型集合依然有其适用的地方。
阅读更多2024-11-07
视频自动播放被浏览器阻止及其解决方案
视频自动播放被浏览器阻止及其解决方案
阅读更多2024-11-07

线性表（知识梳理）

线性表是最基本且最常用的一种线性结构

非空的线性表或线性结构的特点：

线性表的抽象数据类型定义：

顺序表

线性表的顺序表示

定义

特点

存储位置计算

随机存取

线性表的顺序实现

数组表示

动态数组实现（C语言）

顺序表操作概述

1. 初始化

2. 取值

3. 查找

4. 插入

5. 删除

链表

线性表的链式表示和实现

1. 单链表的定义和表示

2. 节点和链表

3. 单链表的特点

4. 单链表的C语言描述

头节点

单链表基本操作的实现

1. 初始化

2. 取值

3. 查找

4. 插入

5. 删除

6.创建单链表

前插法

后插法

循环链表

双向链表

双向链表的插入

双向链表的删除

顺序表与链表的比较

1. 空间性能比较

2. 时间性能比较

相关文章