2.线性表——数据结构学习

零个或多个数据元素的有限序列。

• 有序 （每个元素有且只有一个前驱与后继） -> 一对一的关系
  • 前驱 （第一个元素无前驱）
  • 后继（最后一个元素无后继）
• 有限

线性表元素个数：n (n $\ge$ 0)，当n=0时，称为空表。
非空表中的每个数据元素都有一个确定的位置：位序。

在比较复杂的线性表中，一个数据元素可以由若干个数据项组成。

---

线性表的ADT

当传递参数给函数时，它在函数内是否会被改动决定了使用什么参数形式。

• 需要被改动，则需要传递指向这个参数的指针
• 不用被改动，可以直接传递这个参数

---

顺序存储结构

线性表的每个元素类型都相同！

数组长度与线性表长度区别：

• 数组的长度是存放线性表的存储空间的长度
• 线性表的长度指数据元素的个数
  任意时刻，线性表的长度都是小于等于数组的长度！

一般高级语言可以实现动态分配数组。

数组的下标是从0至n-1，用数组存储顺序表意味着要分配固定长度的数组空间。

获取元素

// 获取线性表中第i个位置的元素，并用e返回  
int GetElem(SqList L, int i, ElemType *e){  
    bool ret = true;  
    // 若线性表长度为0 或 位置值小于1 或 线性表长度小于位置i则返回错误  
    if (L.length == 0 || i < 1 || L.length < i){  
        ret = false;  
    } else{  
        *e = L.data[i - 1];  
    }  
  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12

插入操作

1. 如果插入位置不合理，抛出异常
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
4. 将要插入元素填入位置i，表长加 1

// 在位置i处插入元素e  
int ListInsert(SqList *L, int i, ElemType e){  
    bool ret = true;  
    // 线性表满时  
    // 当i插入位置低于第一位 或 当前插入位置超出线性表长度
    if ((L->length == MAXSIZE) || (i < 1 || L->length + 1 < i)){  
        ret = false;  
    } else{  
        // 将要插入位置的所有元素向后移1位  
        for (int j = L->length - 1; i - 1 <= j; j--) {  
            L->data[j + 1] = L->data[j];  
        }  
  
        L->data[i - 1] = e;  
        L->length++;  
    }  
  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除操作

// 删除位置i上的元素，并用e返回  
int ListDelete(SqList *L, int i, ElemType *e){  
    bool ret = true;  
    // 若删除位置不合理  
    if ((L->length == 0) || (i < 1 || L->length < i)){  
        ret = false;  
    } else{  
        *e = L->data[i - 1];  
        // length: 5 0,1,2,3,4  
        for (int j = i; j < L->length; j++) {  
            // 删除i位置的元素，将其余后面的元素向前移   
L->data[j] = L->data[j + 1];  
        }  
        L->length--;  
    }  
  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

链式存储结构

单链表

线性表的链式存储结构：n个节点链结成一个链表 -> 单链表
特点：是用一组任意的存储单元存储线性表的数据元素，可以连续或不连续。

顺序存储结构中，每个数据元素只需要存储数据元素信息
链式存储结构中，除了存储数据元素信息，还需要存储后继元素的存储地址

• 数据域：存储数据元素信息的域
• 指针域：把存储直接后继位置的域
  指针域中存储的信息称作指针或链，这两部分信息组成数据元素$a_i$的存储映像，称结点

头指针：链表中第一个节点存储位置

头节点：单链表的第一个节点前附设一个节点
请添加图片描述

头指针与头节点的异同：

• 头指针
  • 指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标志作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
• 头节点
  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
  • 头结点不一定是链表必需要素

代码描述

若线性表为空，则头节点的指针域为"NULL"

typedef int ElemType;  
  
typedef struct Node{  
    ElemType data;  
    struct Node *next;  
}Node;  
  
typedef Node *LinkList;
1
2
3
4
5
6
7
8

节点由存放数据元素的数据域和存放后继节点的指针域组成

读取

在单链表中，由于第 i 个元素到底在哪没办法一开始就知道，必须得从头开始找。

思路：

• 声明一个指针p只想链表第一个节点，初始化j从1开始
• 当 j < i 时，就遍历链表，让p的指针向后移动，不断指向下一个节点，j累加1
• 若链表末尾为空，则说明第i个节点不存在
• 否则查找成功，返回节点p的数据

// 查找第i个元素，e返回数据值  
int GetElem(LinkList L, int i, ElemType *e){  
    int j = 1;  
    bool ret = true;  
    // 声明p节点  
    LinkList p;  
    p = L->next;  
      
    // 指针p不为空，或j不等于i时  
    while (p && j < i){  
        p = p->next;  
        ++j;  
    }  
      
    if (!p || i < j){  
        ret = false;  
    } else{  
        *e = p->data;  
    }  
      
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

插入

只需要让s->next和p->next的指针做一点改变即可。

s-next = p->next;
p->next = s;
1
2

表头与表尾的特殊情况是相同的。

思路：

1. 声明另一指针(如p)指向链表头节点，初始化j从1开始
2. 当j
3. 若到链表末尾p为空，则说明第i个节点不存在
4. 否则查找成功，在系统中生成一个空节点(如s)
5. 将数据元素e赋值给s->data
6. 单链表的插入标准语句：s->next = p->next; p->next = s;

// 插入  
int Insert(LinkList *L, int i, ElemType e){  
    LinkList p, s;  
    p = *L;  
    int ret = true, j = 1;  
  
    // 当jnext;  
        ++j;  
    }  
  
    if (!p || i < j) {  
        ret = false;  
    } else{  
        s = (LinkList) malloc(sizeof(Node));  
        s->data = e;  
        s->next = p->next;  
        p->next = s;  
    }  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

删除

其实就是将前继节点的指针绕过，指向它的后继节点即可。

思路：

1. 声明一指针 p 指向链表头结点，初始化从 1 开始
2. 当j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j累加 1
3. 若到链表末尾 p 为空，则说明第结点不存在
4. 否则查找成功，将欲删除的结点 p 一> next 赋值给 q
5. 单链表的删除标准语句 p->next=q->next
6. 将 q 结点中的数据赋值给，作为返回
7. 释放q节点

// 删除  
int Delete(LinkList *L, int i, ElemType *e){  
    LinkList p, q;  
    p = *L;  
  
    int ret = true, j = 1;  
    while (p->next && j < i){  
        p = p->next;  
        ++j;  
    }  
    // 末尾为空的情况，表示当前删除元素为  
    if (!(p->next) || i < j){  
        ret = false;  
    } else{  
        q = (LinkList) malloc(sizeof(Node));  
        q = p->next;  
        p->next = q->next;  
        *e = q->data;  
    }  
  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

整表创建

数组的初始化，声明一个类型和大小的数组并赋值的过程。
创建一个单链表的过程就是一个动态生成链表的过程，从“空表”的初始状态起，依次建立元素节点，并逐个插入链表。

思路

• 声明一指针和计数器
• 初始化空链表L
• 让L的头节点的指针指向NULL，建立一个带头节点的单链表
• 循环

头插法

// 整表创建(头插法)  随机生成n个元素的值  
void CreateListHead(LinkList *L, int n){  
    LinkList p;  
    // 初始化随机种子  
    srand(time(0));  
    *L = (LinkList) malloc(sizeof(Node));  
    (*L)->next = NULL;  
  
    for (int i = 0; i < n; i++) {  
        p = (LinkList) malloc(sizeof(Node));  
        p->data = rand() % 100 + 1; // 随机生成100以内的数字  
        p->next = (*L)->next;  
        // 插入到表头  
        (*L)->next = p;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尾插法

// 整表创建(尾插法)  
void CreateLinkTail(LinkList *L, int n){  
    LinkList p, r;  
    srand(time(0));  
    *L = (LinkList) malloc(sizeof(Node));   // 单链表  
    r = *L;    // 指向尾部节点 r: 指向尾节点的变量, 不断变化 L则随着循环增长为一个多节点的链表  
  
    for (int i = 0; i < n; i++) {  
        p = (Node *) malloc(sizeof(Node));  
        p->data = rand() % 100 + 1;  
        r->next = p;    // 将表尾终端节点的指针指向新节点  
        r = p;  // 将当前的新节点定义为表尾终端节点  
    }  
  r->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

整表删除

思路

• 声明指针p和q
• 将第一个节点赋给p
• 循环

// 整表删除  
int ClearList(LinkList *L){  
    bool ret = true;  
    LinkList p, q;  
    p = (*L)->next;  
      
    while (p){  
        q = p->next;  
        free(p);  
        p = q;  
    }  
  
    (*L)->next = NULL;  
  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
• 当线性表中的元素个数变化较大或根本不知道多大时，最好用单链表结构

静态链表

用数组表述的链表

数据域data存放数据元素; cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。
第一个与最后一个元素不存数据。
备用链表：未被使用的数据元素

// 初始化   
void InitList(StaticLinkList space){  
    // 从下标 0 至 MAXSIZE - 1 的游标设置为 i + 1    for (int i = 0; i < MAXSIZE; i++) {  
        space[i].cur = i + 1;  
    }  
      
    // 最后一个下标的游标设置为0，表示数组为空  
    space[MAXSIZE].cur = 0;  
}
1
2
3
4
5
6
7
8
9

插入

如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

辨明数组中哪些分量未被使用，解决办法是将所有未被使用过的及已被删除的分量用游标链成一个备用链表，每当插入时，可以从备用链表上取得第一个结点作为待插入的新结点。

// 插入  
int ListInsert(StaticLinkList L, int i, ElemType e){  
    int j, k;  
    bool ret = true;  
    // 获得空闲分量的下标  
    j = Malloc_SSL(L);  
    // 获得最后一个元素的下标  
    k = MAXSIZE - 1;  
  
    if ((i < 1 || ListLength(L) + 1 < i) || !(j)){  
        ret = false;  
    }  
  
    switch (ret) {  
        case false:  
            break;  
        case true:  
            L[j].data = e;  
            // 找到第i个元素之前的位置  
            for (int l = 1; l < i; l++) {  
                k = L[k].cur;  
            }  
            // 将第i个元素之间的cur赋值给新元素的cur  
            L[j].cur = L[k].cur;  
            // 将新元素的下标赋值给之前元素的cur  
            L[k].cur = j;  
            break;  
    }  
  
    return ret;  
}
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

删除

同插入类似

// 删除  
int ListDelete(StaticLinkList L, int i) {  
    bool ret = true;  
    int j, k;  
    // 获得最后一个元素的下标  
    k = MAXSIZE - 1;  
  
    // 下标不在范围  
    if (i < 1 || ListLength(L) < i) {  
        ret = false;  
    }  
  
    switch (ret) {  
        case false:  
            break;  
        case true:  
            for (j = 1; j < i; j++) {  
                k = L[k].cur;  
            }  
              
            j = L[k].cur;  
            L[k].cur = L[j].cur;  
            Free_SSL(L, j);  
            break;  
    }  
  
    return ret;  
}
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

静态链表优点：

• 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
  缺点：
• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了链式存储结构随机存取的特性

静态链表只是为了给没有指针的高级语言设计的一种实现单链表能力的方法！ 尽管不一定用上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

循环链表

单向

将单链表中终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表——简称循环链表。

为了使空链表与非空链表处理一致，通常设置一个头节点（并非一定要头节点）！

循环链表与单链表的主要差异就在循环的判断条件上。

• 单链表

p -> next
1

• 循环链表

p -> next不等于头节点
1

双向

双向链表是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。

• 一个指向直接后继
• 一个指向直接前驱

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

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

双向链表是单链表中扩展出来的结构，很多操作和单链表都是相同的。

• 在插入与删除时需要更改两个指针变量

s ->  prior = p;
s -> next = p -> next;
p -> next -> prior = s;
p -> next = s;
1
2
3
4

关键在于它们更改的顺序！如何插入理解了，删除也就比较简单了

---

总结

线性表的两种结构式后面其它数据结构的基础，把它们学明白了对后面的学习有着至关重要的作用！