21天学习挑战赛-静态链表以及一个带头结点的 线性链表类型 的定义

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

1. 静态链表

1. 结点结构

有时，也可借用一维数组来描述线性链表，其类型说明如下所示：

//ーーー 线性表的静态单链表存储结构 

#define MAXSIZE 1000            //链表的最大长度

typedef struct{
    ElemType data;
    int cur;
}component, SLinkList[MAXSIZE]; //SLinkList 的类型是 匿名 struct [10]，即长度为 10 的数组类型
1
2
3
4
5
6
7
8

这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。

在如上描述的链表中，数组的一个分量表示一个结点，同时用游标（指示器 cur）代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。

左边是下标，右边是游标，每个链表结点的游标指向下个链表结点的索引，原本左边的数组中 LI 的游标指向索引 5，而右边在插入 SHI 和删除 ZHENG 后，LI 的游标指向结点 SHI 的索引 9，SHI 的游标再指向索引 5，索引 5 的结点 ZHOU 游标指向了结点 WU 的索引 6，而结点 WU 的游标指向了结点 WANG 的索引 8（之前是指向索引 7），索引跳过了 ZHENG （删除了 ZHENG)

例如图 2.10 (a）中所示为和图 2.6 相同的线性表。这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插人和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结枃的主要优点。

例如，图 2.10 (b）展示了图 2.10 (a）所示线性表在插入数据元素“SHI”和删除数据元素“ZHENG“之后的状况。为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名叫 静态链表。

假设 S 为 SLinkList 型变量，由于游标 cur 表示下一个结点的索引，则 S[0].cur 指示第一个结点在数组中的位置，若设 i = S[0].cur，则 S[i].data 存储线性表的第一个数据元素，且 S[i].cur 指示第二个结点在数组中的位置。一般情况，若第 i 个分量表示链表的第 k 个结点，则 S[i].cur 指示第 k + 1 个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似，以整型游标 i 代替动态指针 p，i = S[i].cur 的操作实为指针后移（类似于 p = p -> next），例如，在静态链表中实现的定位函数 LocateElem 如算法 2.13 所示。

2. 定位元素

算法 2.13

int LocateElem_SL (SLinkList S, ElemType e){
    //在静态单链线性表中査找第 1 个值为 e 的元素
    //若找到，则返回它在 L 中的位序，否则返回 0
    int i = S[0].cur;                         //i 指示表中第一个结点
    while (i && S[i].data != e)
        i = S[i].cur;                         //在表中顺链查找
    return i;
}//LocateElem_SL
1
2
3
4
5
6
7
8

3. 插入和删除元素

类似地可写出在静态链表中实现插人和删除操作的算法。

从图 2.10 的例子可见，指针修改的操作和前面描述的单链表中的插入与删除的算法 2.9、2.10 类似，所不同的是，需由用户自己实现 malloc 和 free 这两个函数。为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过以及被删除的分量用游标链成一个备用的链表，每当进行插入时便可从备用链表上取得第一个结点作为待插人的新结点；反之，在删除时将从链表中刪除下来的结点链接到备用链表上。

算法解析

现以集合运算 $(A-B)U(B-A)$ 为例来讨论静态链表的算法

如果 A 和 B 被认为是集合，那么 $(A-B)U(B-A)$ 给出了集合 A 和集合 B 的对称差分
例如，我们将集合 A 和集合 B 作为:

A = { 1 , 2 , 3 , 4 , 5 } \qquad A = \{1,2,3,4,5 \} A={1,2,3,4,5} 和 B = { 3 , 4 , 5 , 6 } B = \{3,4,5,6 \} B={3,4,5,6}
则有
$A-B=1,2$ 和 $B-A=6$
且
$(A-B)U(B-A)=1,2,6$

例 2-3 假设由终端输入集合元素，先建立表示集合 A 的静态链表 S，而后在输入集合 B 的元素的同时査找 S 表，若存在和 B 相同的元素，则从 S 表中删除之，否则将此元素插人 S 表。

为使算法清晰起见，我们先给出 3 个过程：

1. 将整个数组空间初始化成一个链表；
2. 从备用空间取得一个结点；
3. 将空闲结点链结到备用链表上，分别如算法 2.14、2.15 和 2.16 所示。

算法 2.14

void InitSpace_SL(SLinkList & space){
    //将一维数组 space 中各分量链成一个备用链表，Space[0].cur 为头指针，
    //“0”表示空指针
    int i;
    for  (i = 0; i < MAXSIZE - 1; ++ i)
        space [i].cur = i + 1;
    space [MAXSIZE - 1].cur = 0;
} //Initspace. SL
1
2
3
4
5
6
7
8

算法 2.15

int Malloc_SL (SLinkList & space){
    //若备用空间链表非空，则返回分配的结点下标，否则返回 0
    int i = space [0].cur;
    if (space [0].cur)
        space [0].cur = space [i].cur;
    return 1;
}//Mal1oc-SL
1
2
3
4
5
6
7

算法 2.16

void Free_SL(SLinkList &space, int k) {
    //将下标为 k 的空闲结点回收到备用链表 
    space[k].cur = space[0].cur;
    space[0].cur = k;
}//Free_SL
1
2
3
4
5

算法 $2.17$

//依次输入集合 A 和 B 的元素，在一维数组 space 中建立表示集合（A-B) U (B-A)
//的静态链表，S 为其头指针。假设备用空间足够大，space[0].cur 为其头指针。
void difference(SLinkList & space, int & list_s_head_index) {

    InitSpace_SL(space);                                   //初始化备用空间
    list_s_head_index = Malloc_SL(space);                  //生成 S 的头结点，开始时 space[list_s_head_index].data 是空的
    int r_list_s_last_index = list_s_head_index;              // r 指向 S 的当前最后结点
    int list_a_count,list_b_count;
    printf("请输入 A 的元素个数 和 B 的元素个数 (用空格分隔)");
    scanf("%d%d", &list_a_count,&list_b_count);               //输入 A 的元素个数 m 和 B 的元素个数 n

    for (int j = 1; j <= list_a_count; ++j) {                 //建立集合 A 的链表
        int distributed_index = Malloc_SL(space);          //分配结点
        printf("请输入 A 的元素值");
        scanf("%d",& space[distributed_index].data);          //输入 A 的元素值
        space[r_list_s_last_index].cur = distributed_index;
        r_list_s_last_index = distributed_index;              //插人到表尾
    }//for

    space[r_list_s_last_index].cur = 0;                       //尾结点的指针为空

    for (int j = 1; j <= list_b_count; ++j) {                 //依次输入 B 的元素，若不在当前表中，则插入，否则删除

        int b_input_data;
        printf("请输入 B 的元素值");
        scanf("%d",&b_input_data);

        int list_s_head_index_cur_temp = list_s_head_index;
        int list_s_head_index_cur = space[list_s_head_index].cur;                 // k 指向集合 A 中第一个结点

        //遍历 A 集合
        while (list_s_head_index_cur != space[r_list_s_last_index].cur &&
                    space[list_s_head_index_cur].data != b_input_data ) {         //在当前表中查找
            list_s_head_index_cur_temp = list_s_head_index_cur;                   //list_s_head_index_cur_temp 指向 A 中的最后一个节点的前一个结点
            list_s_head_index_cur = space[list_s_head_index_cur].cur;
        }//while

        if (list_s_head_index_cur == space[r_list_s_last_index].cur) {            //遍历集合 A 的头尾 index 重合，说明当前表中不存在该元素，插入在 r_list_s_last_index 所指结点之后
            int i = Malloc_SL(space);                                          //且 r_list_s_last_index 的位置不变
            space[i].data = b_input_data;
            space[i].cur = space[r_list_s_last_index].cur;
            space[r_list_s_last_index].cur = i;
        } else {                                                                  //该元素已在表中，删除之
            space[list_s_head_index_cur_temp].cur = space[list_s_head_index_cur].cur; //list_s_head_index_cur_temp 正好是 list_s_head_index_cur 的前一个结点，所以 list_s_head_index_cur_temp 的值被覆盖
            Free_SL(space, list_s_head_index_cur);
            if (r_list_s_last_index == list_s_head_index_cur)                     //list_s_head_index_cur 已经被 free 掉了，最后一个结点的 index 是 list_s_head_index_cur_temp
                r_list_s_last_index = list_s_head_index_cur_temp;                 //若删除的是 r 所指结点，则需修改尾指针为 list_s_head_index_cur_temp
        }
    }//for
}//difference
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

解析:
space[0] 是备用空间链表的头结点，space[0].cur 为备用链表的头指针，第一个分配的结点为集合 A 的头结点，r（r_list_s_last_index）的值为 7 （因为算上集合 A 的头结点有 8 个数，所以最后一个元素的索引是 7）

在算法 $2.17$ 中，只有一个处于双重循环中的循环体（在集合 A 中查找依次输入的 b），其最大循环次数为：外循环 $n$ 次，内循环 $m$ 次，故算法 $2.17$ 的时间复杂度为 $O(m\times n)$（即 $list\_a\_count\times list\_b\_count$ ）

图 $2.11$ 是算法 $2.17$ 执行的示意图。假设集合 $A=(c,b,e,g,f,d)$, $B=(a,b,n,f)$，则图 $2.11(a)$ 所示为输入集合 A 的元素之后建成的链表 S 和备用空间链表的状况，图 2.11 (b）所示为逐个输入集合 B 的元素并在链表 S 中依次插入 a、删除 b、插人 n、删除 f 后的状况

一个带头结点的 线性链表类型 的定义

typedef struct LNode{       //结点类型
    ElemType data;
    struct LNode * next;
 } *Link, Position;

typedef struct{             //链表类型
    Link head, tail;        //分别指向线性链表中的头结点和最后一个结点
    int len;                //指示线性链表中数据元素的个数
 } LinkList;

Status MakeNode (Link &p, ElemType e);
//分配由 p 指向的值为 e 的结点，并返回 K；若分配失败，则返回 ERROR 

void FreeNode (Link &p);
//释放 p 所指结点

status InitList (LinkList &L);
//构造一个空的线性链表 

Status DestroyList (LinkList &L);
//销毁线性链表工，L 不再存在 

Status ClearList (LinkList &L);
//将线性链表 L 重置为空表，并释放原链表的结点空间

Status InsFirst (Link h, Link s);
//已知 h 指向线性链表的头结点，将 s 所指结点插入在第一个结点之前 

Status Delfirst (Link h, Link &q);
//已知 h 指向线性链表的头结点，删除链表中的第一个结点并以 q 返回 

Status Append(LinkList &L, Link s);
//将指针 s 所指（彼此以指针相链）的一串结点链接在线性链表 L 的最后一个结点之后，并改变链表 L 的尾指针指向新的尾结点

Status Remove (LinkList &L, Link &q);
//删除线性链表 L 中的尾结点并以 q 返回，改变链表 L 的尾指针指向新的尾结点 

Status InsBefore (LinkList &L, Link &p, Link s);
//已知 p 指向线性链表 L 中的一个结点，将 S 所指结点插入在 P 所指结点之前，并修改指针 p 指向新插入的结点

Status InsAfter (LinkList &L, Link &p, Link s);
//已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入在 p 所指结点之后，并修改指针 p 指向新插入的结点 

Status SetCurElem (Link &p, ElemType e);
//已知 p 指向线性链表中的一个结点，用 e 更新 P 所指结点中数据元素的值

ElemType GetCurElem (Link p);
//已知 p 指向线性链表中的一个结点，返回 p 所指结点中数据元素的值

Status ListEmpty (LinkList L);
//若线性链表 L 为空表，则返回 TRUE，否则返回 FALSE

int ListLength (LinkList L);
//返回线性链表 L 中元素个数

Position GetHead (LinkList L);
//返回线性链表 L 中头结点的位置 

Position GetLast (LinkList L);
//返回线性链表 L 中最后一个结点的位置

Position PriorPos (LinkList L, Link p);
//已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点的直接前驱的位置，若无前驱，则返回 NULL

Position NextPos (LinkList L, Link p);
//已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点的直接后继的位置，若无后继，则返回 NULL

Status LocatePos (LinkList L, int i, Link & p);
//返回 p 指示线性链表 L 中第个结点的位置并返回 OK, i 值不合法时返回 EROR 

Position LocateElem  (LinkList L, ElemType e, Status (* compare) (ElemType, ElemType));
//返回线性链表 L 中第 1 个与 e 满足函数 compare() 判定关系的元素的位置，若不存在这样的元素，则返回 NULL

Status ListTraverse (LinkList L, Status (* visit) ());
//依次对 L 的每个元素调用函数 visit()。一且 visit() 失败，则操作失败。
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

在上述定义的线性链表的基本操作中，除了 DestroyList、ClearList、Remove、InsBefore、PriorPos、LocatePos、LocateElem 和 ListTraverse 的时间复杂度和表长成正比之外，其他操作的时间复杂度都和表长无关，Append 操作的时间复杂度则和插入的结点数成正比。

2. 链表操作

利用这些基本操作，容易实现诸如 在第 i 个元素之前插入元素 或 删除第个元素 或 合并两个线性表等操作，如算法 2.20 和 2.21 所示

算法 2.20

Status ListInsert_L (LinkList & L, int i, ElemType e){

    //在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e

    if (! LocatePos (L, i - 1, h)) return ERROR;  //值不合法
    if (! MakeNode (s, e))) return ERROR;         //结点存储分配失败

    InsFirst (h, s);                              //对于从第 i 个结点开始的链表，第 i-1 个结点是它的头结点

    return OK;
}//ListInsert_L
1
2
3
4
5
6
7
8
9
10
11

算法 2.21

//合并 La、Lb 的内容到 Lc 中
Status MergeList_l(LinkList &La, LinkList &Lb, LinkList &Lc, int (*compare)(ElemType, ElemType)) {

    //已知单链线性表 La 和 Lb 的元素按值非递减排列
    //归并 La 和 Lb 得到新的单链线性表 Lc, Lc 的元素也按值非递减排列
    if (!InitList(Lc))
        return ERROR; //存储空间分配失败

    Link ha = GetHead(La);                                          //返回线性链表 La 中头结点的位置赋值给 Link
    Link hb = GetHead(Lb);                                          //ha 和 hb 分别指向 La 和 Lb 的头结点
    Position pa = NextPos(La, ha);                                  //获取 La 中的头结点 ha 的下一个结点 pa
    Position pb = NextPos(Lb, hb);                                   //获取 Lb 中的头结点 hb 的下一个结点 pb

    while (pa && pb) {                                              //La 和 Lb 均非空

        ElemType a = GetCurElem(pa);                                //获取 pa 的 data 值赋值给 a
        ElemType b = GetCurElem(pb);                                //a 和 b 为两表中当前比较元素
        Link q;

        if ((*compare)(a, b) <= 0) {                                //如果 a 小于 b，则删除 a 中第一个元素并添加到 Lc 中
            DelFirst(ha, q);
            Append(Lc, q);
            pa = NextPos(La,
                         ha);                                   //因为 ha 之前的后边的那个结点被 DelFirst 删掉了，所以这里重新把 La 的头结点 ha 的下一个结点赋值给 pa
        } else {       // a > b
            DelFirst(hb, q);
            Append(Lc, q);
            pb = NextPos(Lb, hb);
        }
    }//while

    if (pa)                                                         //说明 pb 是空的，pa 不是空的
        Append(Lc, pa);                                         //链接 a 中剩余结点
    else
        Append(Lc, pb);                                         //链接 Lb 中剩余结点

    FreeNode(ha);
    FreeNode(hb);                                               //释放 La 和 Lb 的头结点

    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
37
38
39
40
41

算法 2.20 和算法 2.21 分别为算法 2.9 和算法 2.12 的改写形式，它们的时间复杂度和前面讨论相同。