数据结构 - 链表

线性表的链式存储结构

概念

将线性表 L = (a₀, a₁, … , a_n-1)中各元素分布在存储器的不同存储块，成为结点，通过地址或指针建立元素之间的联系。

结点的 data 域存放数据元素 a_i ，而 next 域是一个指针，指向 a_i 的直接后继 a_i+1 所在的结点。

• 下图中的首元结点（头结点） A 的 data 不重要，next 域指向链表的真正的第一个结点，头结点的作用也是为了指明哪个结点是链表的第一个结点。

• 最后一个结点的 next 域，也就是下图中最后一个结点的那个 ^ 代表的是 NULL。

结点类型描述

typedef struct node
{
	data_t data; //结点的数据域
	struct node *next; //结点的后继指针域
}listnode, *linklist;
1
2
3
4
5

则有：

listnode A;
linklist p = &A;
1
2

结点声明

设 P 指向链表中结点 a_i

获取 a_i，写作：p->data
获取 a_i+1，写作：p->next->data

若指针 p 的值为 NULL，则它不指向任何结点，此时 p->data 或 p->next 是非法操作。

可调用 C 语言中 malloc() 函数向系统申请结点的存储空间：

linklist p;
p = (linklist)malloc(sizeof(listnode));
1
2

则创建一个类型为 linklist 的结点，且该结点的地址已存入指针变量 p 中。

建立单链表

• 目标：建立单链表
• 思路：
  1、给头结点分配空间然后判空
  2、初始化头结点（H->data，H->next）
  3、返回头结点
• 代码：

linklist list_create()
{
	linklist H; //头结点

	//分配空间并判空
	if ((H = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc H failed!\n");
		return NULL;
	}
	
	//初始化头结点
	H->data = 0;
	H->next = NULL;
	
	//返回头结点
	return H;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链表尾部插入节点

• 目标：向单链表的尾部插入新的节点
• 思路：
  1、建立新节点，给新节点分配空间并初始化
  2、定义指针指示插入节点的位置，这个位置的 next 为空，这样才能在 next 插入新节点，才能保证在链表的结尾插入节点 （从 H 开始，通过 q=q->next 遍历链表直到链表尾部）
  3、在指针的 next 插入新节点
• 代码：

int list_insert_tail(linklist H, data_t value)
{
	linklist p; //要插入的新节点 
	linklist q; //确定插入位置的指针

	//如果头结点为空那么以后的操作也没办法进行
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return -1;
	}

	//给新节点分配空间并判空
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc p failed!\n");
		return -1;
	}
	
	//初始化新节点
	p->data = 0;
	p->next = value;

	q = H;
	//确定插入节点的位置
	while (q->next)
    {
    	q = q->next;
    }

    //在链表尾部插入节点
    q->next = p;

	return 0;
}
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

根据下标查找节点

• 目标：根据位置获取链表中的节点
• 思路：
  1、判头结点是否为空，判下标是否合法；
  2、定义遍历链表的指针和 i 遍历链表直到找到指定位置（注意遍历完链表也没有找到指定节点的情况）；
  3、返回要查找的节点或空节点（未找到的情况）
• 代码：

linklist list_get(linklist H, int pos)
{
	linklist p; //遍历用指针
	int i; //遍历用标记
	
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return NULL;
	}

	if (pos < 0)
	{
		printf("pos is invalid\n");
		return NULL;
	}

	p = H;
	i = -1;
	while (i < pos)
	{
		p = p->next; //指针p向下移动
		//已经遍历完链表但没找到这个位置则break
		if (p == NULL)
		{
			break;
		}
		i++; //i迭代
	}

	return p;
}
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

在链表指定位置插入新节点

• 目标：给定链表、位置和新节点的值将这个新节点插入到链表的指定位置
• 思路：
  1、判头节点是否为空，位置是否合法（初步）
  2、通过指针和 i 遍历链表找到这个要插入节点的前一个节点的位置，让指针指向这个节点
  3、通过改变指针指向插入这个新节点
• 代码：

int list_insert_between(linklist H, data_t value, int pos)
{
	linklist p; //遍历用指针
	linklist q; //新节点
	int i;
	
	//如果头结点为空那么以后的操作也没办法进行
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return -1;
	}

	//这种位置无效
	if (pos < -1)
	{
		printf("H is invalid!\n");
		return -1;
	}

	//给新节点分配空间并判空
	if ((q = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc p failed!\n");
		return -1;
	}
 	
 	//初始化新节点
 	q->next = NULL;
 	q->data = value;

	//p从头结点开始遍历
	p = H;
	while (i < pos - 1) //注意这里是 pos - 1,一定要在循环结束时让指针指向指定位置的前一个节点
	{
		p = p->next;
		//i还没到pos指针指向节点就空了，证明给定的位置无效
		if (p == NULL)
	    {
	    	printf("the pos not found!\n");
	    	return -1;
	    }
	    i++;
	 }
		
	//此时指针指向指定位置的前一个节点,通过改变指针指向插入新节点
	q->next = p->next;
	p->next = q;

	return 0;
}	
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

打印链表

• 目标：打印链表节点
• 思路：通过指针遍历链表并打印
• 代码：

int list_show(linklist H) {
    linklist p;
 
    if (H == NULL) {
        printf("H is NULL\n");
        return -1;
    }
 
    p = H;
 
    while (p->next != NULL) {
        printf("%d ", p->next->data);
        p = p->next;
    }
    puts("");
 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18