CosmosNing的个人博客

探索·好奇

0%

数据结构复习笔记1-绪论及线性表

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟
整理一下数据结构基本概念和线性表的知识

1. 数据结构基本概念及简单的算法分析

数据结构的基本概念

  1. 数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
  2. 数据元素：数据元素是数据的基本单位，通常作为一个整体进行思考和处理。一个数据元素可由若干 数据项 组成，数据项是构成数据元素的不可分割的最小单位。
  3. 数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
  4. 数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。
    1. 原子类型。其值不可再分的数据类型。
    2. 结构类型：其值可以再分解为若干成分（分量）的数据类型
    3. 抽象数据类型：抽象数据组织及与之相关的操作。
  5. 抽象数据类型：抽象数据类型（ ADT ）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。通常用 （数据对象，数据关系，基本操作集） 这样的三元组来表示抽象数据类型。
  6. 数据结构：在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为 结构 。数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括以下三方面的内容：
    1. 逻辑结构
      • 是指数据元素之间的逻辑关系，即从逻辑关系描述数据。
      • 与数据的存储无关，是独立于计算机的。
      • 分为线性结构和非线性结构
      • 4 种基本结构
        1. 集合
        2. 线性结构
        3. 树形结构
        4. 图状结构或网状结构
    2. 存储结构
      • 是指数据结构在计算机中的表示（又称映像），也称物理结构。
      • 包括数据的表示和关系的表示。
      • 依赖于计算机语言
      • 4 种存储结构
        1. 顺序存储
        2. 链式存储
        3. 索引存储
        4. 散列存储
    3. 数据运算
      • 包括定义和实现
      • 定义：针对逻辑结构，指出运算的功能
      • 实现：针对存储结构，指出运算的具体操作步骤。

算法的定义、特性

  1. 算法的定义
    • 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。
  2. 算法的特性
    1. 有穷性
    2. 确定性
    3. 可行性
    4. 输入
    5. 输出

简单的算法分析：时间复杂度、空间复杂度

  1. 时间复杂度分析技巧
    • 非递归：分析循环次数和问题规模 n 的关系，根据循环条件列出两者的不等式，取解中增长最快的一项作为时间复杂度。
    • 递归：根据代码中的递推公式，求出通项公式，取增长最快的一项作为时间复杂度。
  2. 空间复杂度
    • 算法原地工作是指所需的辅助空间为常量（而非不需要），即 O(1) 。

2. 线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 算法 2.1
// 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中

/*
算法流程：
1. 分别求线性表的长度
2. 遍历 Lb ，取出元素，在 La 中寻找匹配。如果没找到，先将La长度加一,然后插入到 La 末尾
*/

void Union(List &La, List Lb)
{
    La_Len = ListLength(La);
    Lb_Len = ListLength(Lb);
    for(i = 0; i < Lb_Len; i++)
    {
        GetElem(Lb, i, e);
        if(! LocateElem(La, e equal) )
            ListInsert(La,++La_Len, e);
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 算法 2.2
// 已知线性表 La 和 Lb 中的数据元素按值非递减排列
// 归并 La 和 Lb 得到新的线性表 Lc ，Lc 的数据元素也按值非递减排列

/*
算法流程：
1. 初始化 Lc
2. 获取 La 和 Lb 的长度
3. 设置循环变量 i（La）、j（Lb）、k（Lc）
4. 循环（while）比较 La 和 Lb 数据元素的大小，选择小的插入Lc，循环变量对应增加
5. 遍历 La 的剩余元素，插入到 Lc 中
6. 遍历 Lb 的剩余元素，插入到 Lc 中
P.S. 5、6 只可能执行其中一个。
*/

void MergeList(List La, List Lb, List & Lc)
{
    InitList(Lc);
    La_Len = ListLength(La);
    Lb_Len = ListLength(Lb);
    
    i = 1;
    j = 1;
    k = 0;
    
    while(i <= La_Len && j <= Lb_Len)
    {
        GetElem(La, i, a);
        GetElem(Lb, j, b);
        
        if(a < b)
        {
            ListInsert(Lc, ++k, a);
            i++;
        }
        else
        {
            ListInsert(Lc, ++k, b);
            j++;
        }
    }
    
    while(i <= La_Len)
    {
        GetElem(La, i, a);
        ListInsert(Lc, ++k, a);
        i++;
    }
    
    while(i <= Lb_Len)
    {
        GetElem(Lb, i, b);
        ListInsert(Lc, ++k, b);
        j++;
    }
}

顺序表和链表的存储与基本操作；

顺序表

1
2
3
4
5
6
7
8
9
// 线性表的 动态分配 存储结构定义

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
typedef struct{
    ElemType * elem;
    int length;     // 若没有，则为静态
    int listsize;
}SqList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 算法 2.3
// 构造一个空的线性表 L

/*
算法流程：
1. 申请初始大小的空间
2. 判断是否申请成功。如果不成功，报错退出；否则，length和listsize分别赋予合理的初值。
*/

Status InitList_Sq(SqList & L)
{
    L.elem = (ElemType *) malloc(sizeof(ElemType) * LIST_INIT_SIZE);
    
    if(! L.elem )
        exit(OVERFLOW);
    
    L.listsize = LIST_INIT_SIZE;
    L.length = 0;
    
    return 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
25
26
27
28
29
30
31
32
33
34
35
36
// 算法 2.4
// 在顺序表线性表 L 中第 i 个 位置之前插入新的元素 e
// i 的合法值为 1 <= i <= ListLength(L) + 1

/*
算法流程：
1. i 的非法性检查
2. 存储空间已满检查
3. 循环移动元素，在目标位置插入元素
4. 表长加一
*/

Status ListInsert_Sq(SqList & L, int i, ElemType e)
{
    if(i < 1 || i > L.length + 1) // i 的非法检查
        return ERROR;
    if(L.length + 1 > L.listsize)// 存储空间已满检查
    {
        newbase = (ElemType *)realloc(L.elem, sizeof(ElemType) * (L.listsize + LIST_INCREMENT));
        
        if(! newbase )
            exit(OVERFLOW);
        
        L.elem = newbase;
        L.listsize = L.listsize + LIST_INCREMENT;
    }
    
    q = L.elem + i - 1;// 第i个位置前插入
    
    for(p = L.elem + L.length - 1; p >= q; p--)
        *(p+1) = *p;
    
    *q = e;
    ++ L.length;//勿忘！
    return 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
25
26
// 算法 2.5
// 在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值
// i 的合法值为 1 <= i <= ListLength(L)

/*
算法流程：
1. i 的合法性检查
2. 取出第 i 个位置的元素
3. 移动元素
4. 表长减一
*/
Status ListDelete_Sq(SqList & L, int i, ElemType & e)
{
    if(i < 1 || i > L.length)
        return ERROR;
    
    q = L.elem + i - 1;
    e = *q;
    
    for(p = q; p < p + L.length - 1; p++)
        *p = *(p+1);
    
    L.length--;
    
    return 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
// 算法 2.6
// 在顺序线性表 L 中查找第 1 个值与 e 满足 compare() 的元素的位序
// 若找到，则返回其在 L 中的位序，否则返回 0

/*
算法流程：
遍历L 比较每个元素与e的大小关系，如果满足，则记录下位置，终止循环，返回答案。
*/

int LocateElem_Sq(SqList L, ElemType e, Status(* compare)(ElemType, ElemType))
{
    place = 0;
    
    for(i = 0; i < L.length; i++)
    {
        if(compare(e,L.elem[i]))
        {
            place = i + 1;
            break;
        }
    }
    
    return place;
}
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
// 算法 2.7
// 已知顺序线性表 La 和 Lb 的元素按值非递减排列
// 归并 La 和 Lb 得到新的顺序线性表 Lc ，Lc的元素也按值非递减排列

/*
算法流程：
1. 初始化 Lc， 包括申请空间，初始化 listsize 和 length 的值
2. 设置循环变量（指针） pa，pb，pc
3. while 循环比较，插入 Lc
4. 将 La 或者 Lb 的剩余部分插入 Lc
*/
void MergeList_Sq(SqList La, SqList Lb, SqList & Lc)
{
    Lc.length = La.length + Lb.length;
    Lc.listsize = Lc.length;
    Lc.elem = (ElemType *)malloc(sizeof(ElemType) * Lc.listsize);
    if(! Lc.elem )
        exit(OVERFLOW);
    
    pa = La.elem;
    pb = Lb.elem;
    pc = Lc.elem;
    pa_last = La.elem + La.length - 1;
    pb_last = Lb.elem + Lb.length - 1;
    
    while(pa <= pa_last && pb <= pb_last)
    {
        if(*pa < *pb)
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }
    
    while(pa <= pa_last)
        *pc++ = *pa++;
    
    while(pb <= pb_last)
        *pc++ = *pb++;
}

链表

1
2
3
4
5
6
// 线性表的单链表存储结构

typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode, *LinkList;
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
41
42
43
44
45
46
47
48
// 算法 2.8
// L 为带头节点的单链表的头指针。
// 当第 i 个元素存在时，其值赋给 e 并返回 OK， 否则返回 ERROR

/*
算法流程：
1. 设置用于记录循环状态的变量 j 和 指针 p
2. 循环，找第 i 个元素的位置
3. 出错检查 
4. 取出值，返回成功
*/

Status GetElem_L(LinkList L, int i, ElemType & e)
{
    p = L->next;
    j = 1;
    while(p && j < i)
    {
        p = p->next;
        ++j;
    }
    
    if(!p || j > i)//注意错误条件
        return ERROR;
    
    e = p->data;
    return OK;
    
    /*
    if(i <= 0)
        return ERROR;
    
    p = L;
    count = 0;
    while(p->next != NuLL)
    {
        if(count == i)
        {
            e = p->data;
            return OK;
        }
        count++;
        p = p->next;
    }
    
    return ERROR;
    */
}
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
// 算法 2.9
// 在头节点的单链线性表 L 中第 i 个位置之前插入元素 e

/*
算法流程：
1. 设置 j（循环变量）、p（指针）
2. 循环，找第 i-1 个元素的位置
3. 出错检查 
4. 插入操作，返回成功
*/

Status ListInsert_L(LinkList & L, int i, ElemType e)
{
    j = 0;
    p = L;
    
    while(p && j < i - 1)
    {
        j++;
        p = p->next;
    }
    
    if(!p || j > i - 1)//注意错误条件
        return ERROR;
    
    s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return 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
25
26
27
28
29
30
31
// 算法 2.10
// 在带头结点的单链线性表 L 中， 删除第 i 个元素，并由 e 返回其值

/*
算法流程：
1. 设置 j（循环变量）、p（指针）
2. 循环，找第 i-1 个元素的位置
3. 出错检查 
4. 删除操作，返回成功
*/

Status ListDelete_L(LinkList & L, int i, ElemType & e)
{
    p = L;
    j = 0;
    
    while(p && j < i-1)
    {
        ++j;
        p = p->next;
    }
    
    if(!p && j > i-1)
        return ERROR;
    
    s = p->next;
    e = s->data;
    p->next = s->next;
    free(s);
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 算法 2.11
// 逆位序输入 n 个元素的值，建立带表头结点的单链线性表 L

/*
算法流程：
1. 申请头节点 L，并初始化 L->next 为 NULL
2. 循环：申请新节点，赋值，插入到 L 的头部
*/

void CreateList_L(LinkeList & L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    
    while(n--)
    {
        s = (LinkList)malloc(sizeof(LNode));
        scanf(& s->data);
        
        s->next = L->next;
        L->next = 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 算法 2.12
// 已知单链线性表 La 和 Lb 的元素按值非递减排列
// 归并 La 和 Lb 得到新的单链线性表 Lc ，Lc 的元素也按值非递减排列

/*
算法流程：
（类似 算法 2.7）
*/

void MergeList_L(LinkeList & La, LinkList & Lb, LinkList & Lc)
{
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La;// 用 La 做 Lc 的头节点
    
    while(pa && pb)
    {
        if(pa->data < pb->data)
        {
            // 不需要申请额外空间
            pc->next = pa;// 之间将结点连接到 Lc 对应的位置
            
            //改变位置指针
            pc = pa
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            
            pc = pb;
            pb = pb->next;
        }
    }
    
    if(pa)
        pc->next = pa;
    else
        pc->next = pb;
    
    free(Lb);
}
1
2
3
4
5
6
7
8
// 线性表的静态单链表存储结构

#define MAXSIZE 1000
typedef struct{
    ElemType data;
    int cur;
    
}component, SLinkList[MAXSIZE];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 算法 2.13
// 在静态单链线性表 L 中查找到第 1 个值为 e 的元素
// 若找到，则返回它在 L 中的位序，否则返回 0 。

/*
算法流程：
1. i 初始化为 S[0].cur // 第 1 个 元素的位置
2. 循环比较，若 i 不为 0 并且 i 位置的元素不等于 e，那么 i 指向下一个元素位置（ 即 i = S[i].cur ）；否则跳出循环。
3. 返回结果

*/

int LocateElem_SL(SLinkList S, ElemType e)
{
    i = S[0].cur;
    
    while(i && S[i].data != e)// 注意：当 i 为 0 时，为链表末尾
        i = S[i].cur;
    
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
// 算法 2.14
// 将一维数组 space 中各分量链成一个备用链表，space[0].cur为头指针
// “0” 表示空指针

void InitSpace_SL(SLinkList &space)
{
    for(i = 0; i < MAXSIZE - 1; ++i)
        space[i].cur = i + 1; // 初始化时，默认指向存储空间上的下一个位置
    
    space[MAXSIZE - 1].cur = 0; // 最后一个元素指向空指针
}
1
2
3
4
5
6
7
8
9
10
11
12
// 算法 2.15
// 若备用空间链表为非空，则返回分配的结点下标，否则返回 0

int Malloc_SL(SLinkList & space)
{
    i = space[0].cur; // 取备用链表的第一个元素的下标
    
    if(space[0].cur) // 备用链表非空
        space[0].cur = space[i].cur;// 删除第一个节点，并使头指针指向下一个元素
    
    return i;
}
1
2
3
4
5
6
7
8
9
// 算法 2.16
// 将下标为 k 的空闲结点回收到备用链表

void Free_SL(SLinkList &space, int k)
{
    space[k].cur = space[0].cur; // k 结点的 下一个位置指向 0 结点指向的下一个位置
    
    space[0].cur = k; // 0 结点的下一个位置指向 k
}
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
41
42
43
44
45
46
47
// 算法 2.17
// 依此输入集合 A 和集合 B 的元素， 在一维数组 space 中建立表示集合 
// (A-B)∪(B-A) 的静态链表， S 为其头指针。假设备用空间足够大，
// space[0].cur 为其头指针

void difference(SLinkList &space, int &S)
{
    InitSpace_SL(space);         // 初始化备用空间
    S = Malloc_SL(space);        // 生成 S 的头节点
    r = S;                       // r 指向 S 的当前最后节点
    scanf(m, n);                 // 输入 A 和 B 的元素个数
    
    for(j = 1; j <= m; ++j)      // 建立集合 A 的链表
    {
        i = Malloc_SL(space);    // 分配节点
        scanf(space[i].data);    // 输入 A 的元素值
        space[r].cur = i; r = i; // 插入到表尾
    }
    space[r].cur = 0;            // 尾节点的指针为空
    
    for(j = 1; j <= n; j++)      // 依次输入 B 的元素，若不在
    {                            // 当前表中，则插入，否则删除
        scanf(b); p = S; k = space[S].cur; // k 指向集合 A 中的第一个结点
        while(k != space[r].cur && space[k].data != b)
        {// 在当前表中查找
            p = k; // p 指向当前 
            k = space[k].cur; // k 指向下一个
        }
        
        if(k == space[r].cur)    // 当前表中不存在该元素，
        {                        // 插入在 r 所指结点之后，
                                 // 且 r 的位置不变
            i = Malloc_SL(space);
            space[i].data = b;
            space[i].cur = space[r].cur;
            space[r].cur = i;
        }
        else                     // 该元素已在表中， 删除之
        {
            space[p].cur = space[k].cur;
            Free_SL(space, k);
            if(r == k) r = p;    // 若删除的是 r 所指结点，则需修改尾指针。
        }
    }
}

// 时间复杂度 O(m × n)，第二个循环，外层最多 n 次，内层最多 m 次。

顺序表和链表的应用；

一元多项式的表示及相加

1
2
3
4
5
6
7
8
// 项的结构

typedef struct{  // 项的表示，多项式的项作为 LinkList 的数据元素
    float coef;  // 系数 
    float expn;  // 指数
}term, ElemType; // term 用于本 ADT ，ElemType 为 LinkList 的数据对象名

typedef LinkList polynomial; //用带表头结点的有序链表表示多项式
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
// 算法 2.22
// 输入 m 项的系数和指数，建立表示一元多项式的有序链表 P

/*
算法流程：
1. 初始化线性表
2. 设置头节点数据
3. 读入数据， 判断插入
*/

void CreatPolyn(polynomail &P, int m)
{
    InitList(P);	h = GetHead(P);
    // 设置头节点的数据元素
    e.coef = 0.0;	e.expn = -1;	SetCurElem(h, e);
    
    for(i = 1; i <= m; ++i)
    {
        scanf(e.coef, e.expn);
        if(! LocateElem(P, e, q, (*cmp)()))
        {
            if(MakeNode(s,e))
                InsFirst(q, 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 算法 2.23
// 多项式加法

void AddPolyn(polynomial &Pa. polynomial &Pb)
{
    ha = GetHead(Pa);	hb = GetHead(Pb);
    qa = NextPos(Pa, ha);	qb = NextPos(Pb, hb);
    
    while(qa && qb)
    {
        a = GetCurElem(qa);	b = GetCurElem(qb);
        
        // 三种情况
        // 1. qa->elem < qb->elem: 取 qa 结点插入到结果中
        // 2. qa->elem > qb->elem: 取 qb 结点插入到结果中
        // 3. qa->elem = qb->elem: sum = qa->elem + b->elem
        // 若 sum == 0，则删除该节点；
        // 若 sum != 0，则更新结果中该位置的 elem 域的值。
        switch((*cmp(a, b)))
        {
            case -1:
                ha = qa;	qa = NextPos(Pa, qa);	break;
            case 0:
                sum = a.coef + b.coef;
                
                if(sum != 0.0)
                {
                    SetCurElem(qa, sum);
                    ha = qa;
                }
                else
                {
                    DelFirst(ha, qa);
                    FreeNode(qa);
                }
                
                DelFirst(hb, qb);
                FreeNode(qb);
                qb = NextPos(Pb, hb);
                
                break;
            case 1:
                DelFirst(hb, qb);
                InsFirst(ha, qb);
                qb = NextPos(Pb, hb);
                ha = NextPos(Pa, ha);
                break;
        }
        
        if(!ListEmpty(Pb))	Append(Pa, qb); // A 遍历完了， 
                                            // B 还有，应把剩
                                            // 下的元素一起加
                                            // 入结果中
        FreeNode(hb);
    }
}

循环链表；双向链表；

循环链表

  • 最后一个结点的指针域指向头节点。
  • 遍历循环结束条件是p == 头指针或者p->next == 头指针
  • 基本操作与线性链表类似

双向链表

1
2
3
4
5
6
7
// 线性表的双向链表存储结构

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode *DuLinkList;
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
// 算法 2.18
// 在带头结点的双链循环线性表 L 中第 i 个位置之前插入元素 e
// i 的合法值为 1 ≤ i ≤ 表长 + 1

/*
算法流程：
1. 从头结点开始遍历，找到插入位置
（如果为空，则插入位置不合理，返回错误）
2. 申请新的结点空间（如果申请失败，返回错误）
3. 把新结点的 elem 域设置成指定值，插入到双链循环线性表中
（4处指针修改！！！）
*/

Status ListInsert_DuL(DuLinkList &L, ElemType e)
{
    if(!(p = GetElemP_DuL(L, i)))
        return ERROR;
    if(!(s = (DuLinkList)malloc(sizeof(DuLNode))))
        return ERROR;
    
    s->data = e;
    // 4 处指针修改
    s->prior = p->prior;    // s 的 prior
    p->prior->next = s;     // p 的 prior 的 next
    s->next = p;            // s 的 next
    p->prior = s;           // p 的 prior
    
    return 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
25
26
27
// 算法 2.19
// 删除带头结点的双链循环线性表 L 的 第 i 个元素
// i 的合法值为 1 ≤ i ≤ 表长

/*
算法流程：
1. 从头结点开始遍历，找到删除位置
（如果为空，则插入位置不合理，返回错误）
2. 将删除结点的 elem 域的值赋给制定输出参数，再从链表中删除该结点
并释放相应存储空间。
（2 处指针修改）
*/

Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)
{
    if(!(p = GetElemP_DuL(L, i)))
        return ERROR;
    
    e = p->data;
    
    p->prior->next = p->next;
    p->next->prior = p->prior;
    
    free(p);
    
    return OK；
}

参考资料

  1. 数据结构（C语言版）.严蔚敏
  2. 2020年数据结构考研复习指导.王道论坛