线性表的链式表示和实现

1.4 线性表的链式表示和实现

1.4.1 线性链表

1. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）

2. 不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作都不需要移动元素，只需要移动指针。

3. 为建立起数据元素之间的线性关系，对于每个数据元素来说，除了存放数据元素本身的信息外，还必须有包含指示该元素直接后继元素存储位置的信息，这两部分信息组成了一个结点。即链表中的每一个结点都至少包括两个域。一个域存储数据元素的信息称为“数据域”（data）;另一个域存储直接后继元素的地址，称为“指针域”（next）（指针指向的是地址）。

4. 结点的逻辑结构如图2-4（a）所示。

5. 一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。

   ---

6. 首元结点，头结点，头指针的区别

   首元结点是指链表中存储第一个数据元素a₁的结点。如图2-4所示的结点a₁。

   头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。

   头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针指向结点为线性表的头结点；若链表不设头结点，则头指针所指向的结点为该线性表的首元结点。

   ---

7. 单链表查找某个特定的结点时，需要从头开始遍历，依次查找。

8. 单链表可由头指针（Header）唯一确定。

9. typedef struct LNode {
       Elemtype data; // 数据域,存放节点数据信息。
       struct LNode *next;  // 结点的指针域
   }LNode, *LinkList;      // LinkList为指向结构体LNode的指针类型
   1
   2
   3
   4

   为了提高程序可读性，LinkList与LNode* ，两者本质上是等价的。通常用LinkList定义单链表，强调的是某个单链表的头指针；用LNode*定义指向单链表中任意结点的指针变量。

10. 若定义LinkList L，则L为单链表的头指针，即表示单链表L。若定义LNode *p， 则p为指向单链表中某个结点的指针，用 *p代表该结点。

11. 单链表是由表头指针唯一确定的，因此单链表可以用头指针的名字命名。若头指针名是L，则简称该链表为表L。

12. 指针变量和结点变量的区别：若定义LinkList p 或 LNode *p， 则p为指向某结点的指针变量，表示该结点的地址；而 *p 为对应的结点变量，表示该结点的名称。

13. LinkList 强调这是链表，LNode * 强调这是结点。

14. 增加头结点的优点：

    ① 首元结点的地址保存在头结点（即其“前驱”结点）的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同。

    ② 不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空。（判定空表的条件可记为：L==NULL）。

    增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。若为空表，则头结点的指针域为空（判定空表的条件可以记为：L->next == NULL）。

15. 在单链表中，各个元素的存储位置都是随意的。每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向单链表中第i个数据元素（结点为a_i，即数据域为a_i的结点）的指针，则p->next是指向第i+1个数据元素（结点a_i+1）的指针。

16. 若p->data=a_i，则p->next->data=a_i+1。

17. 单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。

1.4.2 单链表基本操作的实现

利用头插法建立单链表

在链表的头部插入结点建立单链表的方法又简称为“头插法”。其建立思想为：

​ 申请一个头结点，并将头结点的指针域置空（NULL）；依次读入数据元素，如果不是结束标志-1，则申请结点，将新结点插在链表的头结点之后。

LinkList CreateList_H(LinkList &L){
    // 逆位序建立带表头结点的单链表L
	LNode *s;  // 新插入的数据结点，指向该结点的指针为s
    int x;     // 输入的新元素x
    L = (LinkList)malloc (sizeof(LNode)); // 生成头结点
    L->next = NULL;  // 置空，空表
    scanf("%d",&x);  // 输入新元素
    while(x!=-1) {
        s = (LNode *) malloc (sizeof(LNode)); // 创建新结点
    	s->data = x;  // 将输入的新元素的值赋给新结点s的数据域
        s->next = L->next;  // 将s的指针域指向L的指针域
    	L->next = s;  // 将新结点插入到链表中
    	scanf("%d",&x);
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

注：采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个点插入的时间为O(1)。设单链表长为n，则总时间复杂度为O(n)。

利用尾插法建立单链表

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

① 创建一个只有头结点的空链表。

② 尾指针r初始化，指向头结点。

③循环：生成新结点，输入元素赋值给新结点的数据域，将新结点插入到尾结点之后，尾指针指向新的尾结点。

LinkList CreateList_R(LinkList &L){  // 正位序创建带头结点的单链表L
    int x;
    L= (LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;    // r为表尾指针
    scanf("%d",&x);   // 输入结点的值
    while(x!=-1) {
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;       // r指向新的表尾结点
        scanf("%d", &x);
    }
 	r->next = NULL;  // 尾结点指针置空
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注：时间复杂度与头插法相同 为O(n)

查找操作

按序号查找

算法思路：从链表的第一个元素结点起判断当前结点是否为第i个，若是则返回该结点的指针，否则继续查找下一个，直到表结束为止。没有第k个结点时返回空。

LinkList Get_Linklist(LinkList L, int i){
    int j = 1;   // 初始为1
    LNode *p = L->next;  // 第1个结点指针赋给p
    if(i == 0){
        return L;   // 若i等于0，则返回头结点
    }
    if(i<1){
        return NULL:  // 若i无效，则返回NULL
    }
    while (p&&j<i){  // 从第1个结点开始找，查找第i个结点
        p = p->next;
        j++
    }
    return p;  // 返回第i个结点的指针，若i大于表长，则返回NULL
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

按序号查找操作的时间复杂度为O(n)。

按值x查找（即查找x结点所在位置）

算法思路：从链表的第一个元素结点起，判断当前结点的值是否等于x，若是则返回该结点的指针，否则继续向后查找，直到表结束为止。若查找不到则返回空。

LNode *LocateElem(LinkList L, Elemtype e) {
	LNode *p = L->next;
    while(p!=NULL && p->data!=e)  // 从第1个结点开始查找data域为e的结点
    {
        p=p->next;
    }
    return p;       // 找到后返回该结点指针，否则返回NULL
}
1
2
3
4
5
6
7
8

按值查找操作的时间复杂度为O(n)

插入操作

设p指向单链表中的某结点，s指向待插入的新结点，将*s 插入到 *p 的后面，其过程如图2-9所示，操作顺序如下。

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

如果将新结点*s 插入到 *p 前面，其过程如图2-10所示，在插入操作前首先要找到 *p 的前驱结点 *q，然后再将 *s 插入 *q之后。设单链表头指针为H，操作如下。

① q = H;
while(q->next != p)   // 找*p的直接前驱
    q = q->next;
② s->next = p;
③ q->next = s;  // 插入
1
2
3
4
5