要了解线性表，首先要了解线性结构

线性结构的特点

  • 只有一个首节点和尾结点
  • 除首尾节点外，其他节点只有一个直接前驱和直接后继

简而言之，线性结构反映结构的逻辑关系是一对一的

线性结构包含线性表，堆栈，队列，字符串，数组。其中最常用的是线性表。

线性表的定义

用数据元素的有限序列表示

image-20251111103800214

二十六个英文字母组成的英文表，元素间关系是线性

同一线性表中的元素必定有相同特性

线性表中的数据类型可以是简单类型也可以是复杂类型

线性表的顺序表示

线性表的顺序表示可以称为顺序存储结构或顺序映像

顺序存储：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

顺序存储方法：用一组地址连续的存储单元存储。可通过数组实现

线性表的重要基本操作

[!NOTE]

若函数括号内为（SqList &L）表示引用传递，可能会修改参数。若是（SqList L，则表示值传递，不能修改原数据）

定义

结构体中定义地址和长度

1
2
3
4
5
#define MAXSIZE 100
typedef struct{
    ElemType *elem; //地址
    int length;//线性表长度
}sqList;

初始化（两种方法，引用与指针）

用new分配空间，再设置长度为0（空表长度为0）

引用

1
2
3
4
5
6
status InitList_Sq(SqList &L){//构造一个空的顺序表
    L.elem=new ElemType[MAXSIZE];//分配空间
    if(!L.elem) exit(OVERFLOW);//OVERFLOW前文定义为-1，此句表示分配失败
    L.length=0;//空表长度为0
    return OK;//前文define OK 1
}

指针

1
2
3
4
5
6
status InitList_Sq(SqList &L){
    L->elem=new ElemType[MAXSIZE];
    if(!L->elem) exit(OVERFLOW);
    L->length=0;
    return OK;//前文define OK 1
}

销毁线性表

用delete删除线性表

1
2
3
void DestroyList(SqList &L){
    if(L.elem) delete[]L.elem;//释放存储空间
}

清空线性表

清空线性表只需把长度置0即可

1
2
3
void ClearList(SqList &L){
    L.length=0;//线性表长度置为0
}

求线性表长度

L.length

1
2
3
int GetLength(SqList L){
    return (L.length);
}

判断是否为空

长度为0则返回1 表示空了

1
2
3
4
int IsEmpty(SqList L){
    if(L.length==0)return 1;
    else return 0;
}

取值（获取第i个数据）

线性表通过下标直接定位元素

1
2
3
4
5
6
7
int GetElem(SqList L,int i,ElemType &e){
    if(i<1 || i>L.length) return 0;
    //判断i值是否合理
    e=L.elem[i-1];
    //第i-1的单元里存着第i个数控
    return 1;
}

查找（找值为e的数据元素）

1
2
3
4
5
6
7
8
int LocateELem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++){
        if(L.elem[i]==e){
            return i+1;//数组通常从0开始计数，但是用户习惯凑从1开始，这是告诉你，你要找的元素是第i+1个，下标是i
        }
    }
    return 0;
}

插入（第i个前插入e）

步骤

  • 判断插入位置是否合法
  • 判断存储空间是否已满
  • 将n至i的元素依次向后移动一位空出i位置
  • 将要插入的e放入第i个位置
  • 表长加一，插入成功返回ok

注意，第i个前插入e，则e下标为i-1

1
2
3
4
5
6
7
8
9
10
status ListInsert_Sq(SqList &L,int i,ElemType e){
    if(i<1 || i>L.length+1)return 0;
    if(L.length==MAXSIZE)return 0;
    for(int j=L.length-1;j>=i-1;j--){//从最后一个元素开始遍历到i-1，依次后移则下标都增加1
        L.elem[j+1]=L.elem[j];
    }
        L.elem[i-1]=e;//插入e
    ++L.length;
    return 1;
}

[!NOTE]

各种位置插入（n+1个可能）的平均移动次数为n/2

删除（第i个）

步骤

  • 判断i是否合法
  • 将欲删除的元素保留在e中
  • 将第i+1至n位元素向前移动一个位置
  • 表长减一，删除成功返回ok

[!CAUTION]

这里判断合法,i不能超过length，但是插入时是不能超过i+1

1
2
3
4
5
6
7
8
status ListDelete_Sq(SqList &L.int i){
    if((i<1) || (i>L.length)) return 0;
    for(int j=i;i<L.length;j++){
        L.elem[j-1]=L.elem[j];
    }
    --L.length;
    return 1;
}

若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？

image-20251111144834143

顺序存储结构特点

查找插入删除的平均时间为 O(n)

空间复杂度为O（1）

image-20251111145051818 image-20251111145112605

什么是链表？

链表是一种用于存储数据的数据结构，通过像链条一般的指针连接元素（得名原因）。它是线性表的链式存储映像，称为线性表的链式存储结构

它的显著优势是删除和插入数据十分方便（数组要O(n)，链表只需O(1)），但寻找和读取数据表现欠佳（数组只需O(1)，链表需要O(n)）。

链表的组成分类

链表由一系列节点（node）组成，每个节点（同结点）有两个部分：

  • 数据域：存储实际数据，(如int value）
  • 指针域： 存储下一个节点的地址（如 node *next）

链表分为，单链表，双链表，循环链表。

单链表

结点只有一个指针域，称为单链表或者线性链表。由表头唯一确定，所以可以用头指针的名字来命名。若头指针是L,则链表命名为L

image-20260106151754807

注意：后文列举代码默认已定义Node结构体

1
2
3
4
5
6
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList
    //*LinkList 为 LNode类型的指针
    //LNode *p=LinkList p  两种写法都可以

双向链表(应该不考，学有余力可看)

有两个指针域(有左右之分)的链表，称为双链表

image-20260106151806982

1
2
3
4
5
typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode,*DuLinkList

循环链表（也应该不考）

首尾相接的链表是循环列表。（尾节点的 next 指向头节点）由于这个特性，在插入数据时需要判断链表是否为空，为空则自身循环，不空则正常插入数据。（从循环链表中的任何一个节点都可以找到其他任何节点，而单链表不行）

image-20260106151826150

1
2
3
4
5
6
7
8
9
10
11
12
void insertNode(int i, Node *p) {
  Node *node = new Node;//创建新节点
  node->value = i;//设置节点值
  node->next = NULL;//初始化next指针
  if (p == NULL) {//链表为空
    p = node;//p指向新节点
    node->next = node;//自己指向自己
  } else {
    node->next = p->next;//新节点指向p的后继
    p->next = node;//p指向新节点
  }
}

链表常见运算符和关键字

初见代码你也许疑惑，new是什么？

它是c++中的关键字，用于动态分配内存。

例如

1
2
int *p=new int //分配一个int 大小的内存
int *p=new int (100)//初始值为100

->则是c/c++中的箭头运算符，等价于，先解引用指针，然后访问成员。

1
2
3
4
5
int main(){
	Node* node=new Node;
    node->value=5;//设置节点的value为5，等价于（*node）.value=5
    node->next=NULL;//设置Next指针为NULL，等价于 (*node).next=NULL
}

链表的一些概念

我们还提到了头结点的概念，其实与之对应的还有尾结点，头指针，首元结点。

  • 头指针：指向链表中第一个元素的指针
  • 头结点：是在链表的首元结点之前附设的一个结点，**数据域内可以为空，**只存放表长和空表标志等信息。但此结点不能计入链表长度值
  • 首元结点：链表中存储第一个数据元素a1的结点

按有无头结点划分

image-20260106151840434

有头结点时，当当头结点的指针域为空时表示空表。

为什么要设置头结点？

  • 便于首元结点的处理。

    **首元结点的地址保存在头结点的指针域中，**所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。

  • 便于空表和非空表的统一

    无论链表是否为空，头指针都是指向头结点的非空指针。

链表的特点

  • 结点在存储器中的位置是任意的，逻辑相邻的数据元素在物理上不一定相邻

  • 访问时只能通过头指针进入链表，所以寻找第一个结点和最后一个结点的所需时间不等。

这种存取元素的方法称为顺序存取法

单向链表的操作（重点，老师说了要考，可能要写代码当大题）

  1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除

链表运算时间

查找：因线性链表只能顺序存取，所有查找时要从头指针找起，O(n)

插入删除：不需要移动元素，只需要修改指针，只需O(1). 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。

初始化

  • new分配一个内存
  • 头结点的指针域置空

注意，后文列举代码默认有此环境

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef DULINKEDLIST_H
#define DULINKEDLIST_H

// 状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

// 状态类型定义
typedef int Status;
typedef int ElemType; // 可根据需要修改元素类型
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList//*LinkList为Lnode类型的指针
    //指针变量p表示结点地址
    //结点变量*p表示一个结点
    //注意：struct LNode结构体类型有了一个别名 LNode。
    //struct LNode *指针类型有了一个别名 LinkList。
    
    //初始化构造一个空表
    //生成新结点作头结点，用头指针L指向头结点，头结点的指针域置空
    Status InitList_L(LinkList &L){
    L=new LNode;
    L->next=NULL;
}

取值（第i个元素赋值为e）

  • 创建指针变量p用来访问节点内容
  • 创建计数器j=1用来记录遍历到第几个元素了
  • 遍历直到第i个节点，p要非空
  • 判断位置合不合法（p是不是空的,i的值是否合理）
  • e->data赋值为e
  • 返回1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//获取链表中第i个元素的值
int GetElem(LinkList L,int i,ElemType &e){
    LNode *p=L->next; //p指向第一个结点（跳过头结点） 等价于LinkList p=L->next
    int j=1;//计数器
    
    //遍历链表直到第i个节点或链表结束，p不为NULL时继续循环
    while(p && j<i){
        p=p->next;
        j++;
    }
    //循环跑完之后j=i
    
    //p空或j>i说明没有找到，i位置不合法，返回0
    if(!p || j>i){
        return 0;
    } 
    
    e=p->data;//通过指针参数返回元素值
    return 1;
}

使用示例
LinkList list;//初始化的链表
int value;
if(GetElem(list,3,&value)==1){
    printf("第三个元素是：%d\n",value);
}
else{
    printf("第三个元素不存在\n");
}

销毁

  • 创造一个指针变量p临时保存要删除的节点

  • 遍历链表所有节点（while(L)），p指向当前节点，L移向下一个节点

  • 删除p指向的节点

    直接 delete L后，L->next无法再访问（因为 L指向的内存已释放），导致后续节点丢失。

1
2
3
4
5
6
7
8
9
int Destroy(LinkList &L){
    LinkList p;//用于临时保存要删除的节点
    while(L){//当链表还有节点时继续循环
        p=L;//P指向当前要删除的节点
        L=L->next;//L移向下一个节点
        delete p;//删除p指向的节点
    }
    return OK;
}

清空

  • 同销毁，但是地址要保留，所以需要再开一个遍历q保存下一个节点的地址
  • 创建两个指针变量pq
  • p指向第一个节点，while(p)开始遍历，把下一个节点的地址保存在q里面
  • 删除p，让q=p，继续删除
  • 删除完后，头结点指针域为空
1
2
3
4
5
6
7
8
9
10
11
int Clear(LinkList &L){
    LinkList p,q;
    p=L->next;//p指向第一个节点
    while(p){//没到末尾
        q=p->next;//先保存下一个节点的地址，防止删除后丢失链表
        delete p;
        p=q;
    }
    L->next=NULL;//头结点指针域为空
    return OK;
}

查找

查找在线性表L中查找值为e的数据元素

LNode *LocataElem_L

1
2
3
4
5
6
7
8
//在链表中查询值为e的节点
LNode *LocateElem(LinkList L,Elemtype e){
    p=L->next;//p指向第一个节点
    while(p && p->data!=e){
        p=p->next;
        return p; // 找到返回节点指针，未找到返回 NULL
    }
}

查找L中值为e的位置序号，失败返回0

1
2
3
4
5
6
7
8
9
int LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的位置序号，查找失败返回0 
  p=L->next; j=1;
  while(p &&p->data!=e)  
        {p=p->next;  j++;}          		
  if(p) return j; //p不为空说明找到了
  else return 0;
}

插入（第i个节点前）

image-20260106155743941
  • 创建p指向头结点
  • 创建j=0表示头结点是第0个节点
  • while循环寻找第i-1个节点并将p指向它
  • 判断i的合法性，是否小于1或大于表长
  • 生成新节点s，s的数据域置为e
  • 新节点的next指向p的后继节点a1**（此时s还未接入链表）**
  • p的后继节点指向S
1
2
3
4
5
6
7
8
9
10
11
12
13
int ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;//注意，p=L->next是指向第一个节点，p=L是指向头结点
    j=0;//头结点是第0个节点
      while(p&&j<i−1){
          p=p->next;++j;
      }	//寻找第i−1个结点 ，并将p指向它
      if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
      s=new LNode;			//生成新结点s 
      s->data=e;      	    //将结点s的数据域置为e 
      s->next=p->next;      //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

删除

删除第i个节点

  • 找到ai-1存储位置p

  • 临时保存结点ai的地址在q中，以备释放

  • 令p->next指向ai的后继节点ai+1(绕过ai)

  • 将ai的值保存在e中

  • 释放ai空间

  • image-20260106160800014
1
2
3
4
5
6
7
8
9
10
11
12
13
int ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){//寻找第i个结点，并令p指向其前驱 
        p=p->next; ++j; 
    } 
    if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 
    q=p->next; //临时保存被删结点的地址以备释放 
    p->next=q->next; 	//本来q后面才是ai+1,改成p后面
    e=q->data; 	//保存删除结点的数据域 
    delete q; 	//释放删除结点的空间 
 return OK; 
}//ListDelete_L

关于p->next = q->next的绕过原理

假设一个链表 头节点-> A->B->C->NULL

p指向节点A,则p->next指向节点B，即q。

q->next指向c。

p->next=q->next就是直接让A指向C

求表长

1
2
3
4
5
6
7
8
9
10
int ListLength_L(LinkList L){
    LinkList p;
    p=L->next;//p指向第一个结点
    i=0;
    while(p){
        i++;
        p=p->next;
    }
    return i;
}

判断是否为空

1
2
3
4
5
6
7
8
9
int ListEmpty(LinkList L){
    //若L为空表，则返回1，否则返回0
    if(L->next){//非空
        return 0;
    }
    else{
        return 1;
    }
}

有序链表合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 函数功能：将两个非递减有序的带头结点的单链表La和Lb合并为一个新的非递减有序链表Lc
// 核心思想：通过指针操作，重用La和Lb的现有节点，不分配新的节点内存
// 参数说明：La, Lb-待合并的有序链表；Lc-合并后的新链表（引用传递）
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
   // 步骤1：初始化工作指针，跳过头结点，指向第一个数据节点
   pa = La->next;  // pa指向链表La的第一个数据节点（首元结点）
   pb = Lb->next;  // pb指向链表Lb的第一个数据节点
   
   // 步骤2：设置合并后链表Lc的头结点，并初始化尾指针pc
   pc = Lc = La;   // 重用La的头结点作为Lc的头结点，pc作为Lc的当前尾指针
   
   // 步骤3：核心循环 - 比较并合并两个链表的节点
   // 循环条件：两个链表都还有未处理的节点（pa和pb都不为NULL）
   while(pa && pb) {
      // 比较当前两个节点的大小，选择较小的节点链接到Lc
      if(pa->data <= pb->data) { 
         // La的当前节点值较小或相等，将其链接到Lc末尾
         pc->next = pa;  // 将pa节点挂接到pc之后
         pc = pa;        // pc指针移动到新的尾节点pa
         pa = pa->next;  // pa指针后移，准备处理La的下一个节点
      }
      else {
         // Lb的当前节点值较小，将其链接到Lc末尾
         pc->next = pb;  // 将pb节点挂接到pc之后
         pc = pb;        // pc指针移动到新的尾节点pb
         pb = pb->next;  // pb指针后移，准备处理Lb的下一个节点
      }
   } // 结束循环时，pa和pb中至少有一个为NULL
   
   // 步骤4：处理剩余节点 - 将未处理完的链表直接连接到Lc末尾
   pc->next = pa ? pa : pb;  // 如果pa不为空则连接La剩余部分，否则连接Lb剩余部分
   
   // 步骤5：资源清理 - 释放Lb的头结点（数据节点已全部并入Lc）
   delete Lb;  // Lb的头结点已不再需要，释放其内存空间
}

//后面的大概率不考，难度比较高，只说了考单链表。有序链表合并

前插法建单链表

从一个空表开始重复读入数据

  • 生成新结点
  • 将读入数据放到新节点
  • 将该新节点插入到链表
1
2
3
4
5
6
7
8
9
10
void CreateList_F(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;//先建立一个带头结点的空链表
    for(int i=n;i>0;i--){
        p=new LNode;//生成新节点
        cin >>p->data;//输入元素值
        p->next=L->next;
        L->next=p;//插入到表头
    }
}

image-20260106151916295

尾插法建单链表

1
2
3
4
5
6
7
8
9
10
11
12
void CreateList_L(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    r=L;//尾指针r指向头结点
    for(int i=0;i<n;i++){
        p=new LNode;
        cin >>p->data;
        p->next=NULL;//将新创建节点p的指针域设置为NULL，表示它是链表的最后一个节点。
        r->next=p;//将新节点链接到链表尾部
        r=p;//r指向新的尾结点
}
}

插入（指定位置插入新节点）

算法步骤

找到插入位置的前驱节点，生成一个新结点，新结点的数据域置为x，新结点* s的指针域指向结点ai，结点*p的指针域指向新节点 *s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//在第i个位置插入新元素e，所有要在i-1个节点后面插入
Status ListInsert(LinkList &L,int i,ElemType e){
    LNode *p=L; //p指向头结点
    int j=0;
    
    //寻找第i-1个节点p
    while(p && j<i-1){
        p=p->next;
        j++;
    }
    //i小于0或大于表长加一
    if(!p || j>i-1){
        return ERROR;
    }
    
    //创建新节点
    s=new LNode;
    s->data=e;
    //插入操作,在第i-1个节点也就是p节点后插入新节点
    //先让新节点指向p原来的下一个节点
    s->next=p->next;//如果s=p->next，指针s会直接指向p->next指向的节点，新节点会丢失
    p->next =s;//在让p指向新节点
    
    return OK;
}

单向循环链表的操作及约瑟夫环

初始化

1
2
3
4
5
6
7
8
9
10
11
// 通常在头文件中这样定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;  // 将Status定义为int类型
Status InitList_CL(LinkList &L){
    L=new LNode;//生成头结点
    if(!L) exit(OVERLOW);//内存分配失败
    L->next=L;//头结点的next指向自己，形成空环
    return OK;
}

判断是否为空

1
2
3
4
int ListEmpty_CL(LinkList L){
    //判断头结点的next是否指向自己
    return (L->next==L);
}

结点p之前插入新结点s

1
2
3
4
5
6
7
8
9
10
11
Status ListInsert_CL(LinkList &L,LNode *p,EleType e){
    LNode *s=new LNode;
    if(!s)return ERROR;
    s->data=e;
    
    s->next=p->next;//新结点s指向p的后继
    p->next=s;//结点p指向新结点s
    
    //如果p是尾结点，那么s就成为新的尾结点，其next头指向头结点L
    return OK;
}

删除点p的后继节点

1
2
3
4
5
6
7
8
9
10
Status ListDelete_CL(LinkList &L,LNode *p,EleType &e){
    if(p->next==L)return ERRER;
    //p是尾结点，无后续可删
    
    LNode *q=p->next;//q指向要删除的结点
    e=q->data;//保存被删除的结点位置
    p->next=q->next;//绕过要删除的结点
    delete q;//释放内存
    return OK;
}

合并链表

Ta是链表a的尾指针，Ta->next指向链表a的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList Connect(LinkList Ta,Linklist Tb){
    //假设ta,tb都是非空单循环链表
    p=Ta->next//p存表头结点
    Ta->next = Tb ->next->next;//tb表头连接Ta表尾
    delete Tb->next;//释放tb表头结点,现在链表a的尾直接指向了链表b的首元结点，链表b原来的头结点（Tb->next）已经不再被需要。
    Tb->next=p;//修改指针
    return Tb;
    /*现在，整个链表的尾部是链表b原来的尾节点（即 Tb指向的节点）。
要让新链表成为循环链表，需要让尾节点的 next指针指向头结点。
p保存的正是链表a原来的头结点，现在它将成为合并后新链表的头结点。
这行代码让链表b的尾节点（Tb）的 next指针指向这个头结点，从而闭合整个链表，形成一个新的循环链表。
合并完成后，Tb指向的是新链表的尾节点。
函数返回 Tb，即返回新循环链表的尾指针。
*/
}

约瑟夫环

image-20260106151944605

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void Josephus(int n, int m) {
    // 创建包含n个结点的循环链表
    LinkList L, current, prev;
    InitList_CL(L);  // 初始化循环链表
    
    // 构建约瑟夫环
    for(int i = 1; i <= n; i++) {
        ListInsert_CL(L, i, i);  // 第i个人的编号为i
    }
    
    current = L->next;  // 从第一个人开始
    prev = L;
    
    while(n > 1) {
        // 数到第m个人
        for(int count = 1; count < m; count++) {
            prev = current;
            current = current->next;
            // 如果遇到头结点，跳过
            if(current == L) {
                prev = current;
                current = current->next;
            }
        }
        
        // 删除当前结点（淘汰这个人）
        printf("出列的人是：%d\n", current->data);
        prev->next = current->next;
        delete current;
        current = prev->next;
        n--;
        
        // 如果遇到头结点，跳过
        if(current == L) {
            current = current->next;
        }
    }
    
    printf("最后剩下的人是：%d\n", current->data);
}

双向链表

定义初始化

1
2
3
4
5
6
typedef struct DuLNode{
    EleType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode,*DuLLinkList

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 函数功能：在带头结点的双向链表L中，第i个位置之前插入新元素e
// 参数说明：L-双向链表头指针（引用传递），i-插入位置，e-待插入元素
// 返回值：操作状态（OK-成功，ERROR-失败）
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
    
    // 步骤1：定位插入位置，获取第i个结点的指针p
    // 注意：这里是在第i个结点"之前"插入，所以p指向的是目标位置的后继结点
    DuLNode *p;
    if(!(p = GetElemP_DuL(L, i)))  // 调用查找函数获取第i个结点的地址
        return ERROR;               // 如果第i个结点不存在，返回错误
    
    // 步骤2：创建新结点并赋值
    DuLNode *s = new DuLNode;  // 动态分配新结点内存
    s->data = e;               // 将数据e存入新结点的数据域
    
    // 步骤3：核心操作 - 四步指针修改，将新结点s插入到p结点之前
    // 这四步操作必须按顺序执行，确保链表不断链
    
    s->prior = p->prior;      // 操作①：新结点s的前驱指向p原来的前驱结点
    p->prior->next = s;       // 操作②：p原前驱结点的后继指向新结点s
    s->next = p;              // 操作③：新结点s的后继指向p结点
    p->prior = s;             // 操作④：p结点的前驱指向新结点s
    
    return OK;  // 插入成功，返回OK状态
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 函数功能：删除带头结点的双向链表L中第i个位置的元素，并通过e返回被删除的值
// 参数说明：L-双向链表头指针（引用传递），i-删除位置，e-用于返回被删除元素值的引用
// 返回值：操作状态（OK-成功，ERROR-失败）
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
    
    // 步骤1：定位要删除的结点，获取第i个结点的指针p
    DuLNode *p;
    if(!(p = GetElemP_DuL(L, i)))     // 调用查找函数获取第i个结点的地址
        return ERROR;                 // 如果第i个结点不存在，返回错误
    
    // 步骤2：保存被删除结点的数据值
    e = p->data;    // 将待删除结点p的数据域值保存到参数e中，以便返回给调用者
    
    // 步骤3：核心操作 - 两步指针修改，将结点p从链表中"摘除"
    // 关键思想：让p的前驱结点直接指向p的后继结点，绕过p本身
    
    p->prior->next = p->next;    // 操作①：p前驱结点的后继指针指向p的后继结点
    p->next->prior = p->prior;  // 操作②：p后继结点的前驱指针指向p的前驱结点
    
    // 步骤4：释放被删除结点的内存空间
    delete p;        // 释放结点p占用的内存，防止内存泄漏
    
    return OK;       // 删除成功，返回OK状态
}

题目

对于循环队列，front=(初始＋删除的位置)%size

rear=(初始＋加入的位置)%size

image-20260103234414184

顺序表中元素地址计算公式：第i个元素地址 = 首地址 + (i-1) × 元素长度。

image-20260103234551135