前言

链表就是指动态分配结构的序列链

说明

我们知道，数组是被分配的连续的内存块，可以轻易调用其中的项，但是要增加和删除其中的项却很困难。
而链表呢，因为它是靠结构中的指针将散乱的内存块，串起来。就变得增加，删除其中的项很容易，要访问其中的某一项却很困难。

构造链表的一般步骤

(prev是一个结构指针，表示前一个结构的中介)
(current是一个结构指针，表示当前结构的中介)

  1. while循环（人为结束）
  2. malloc分配结构空间，并返回指针给current(结构将在循环中创建)
  3. if-else 给prev的next赋值
  4. 将本结构的next = NULL
  5. 对本结构的内容赋值
  6. 让prev = current的指针

关于结构指针

  1. struct Node *ps定义一个Node类型的结构指针。
    注意，此时并没有指向Node的某个结构

  2. 必须malloc分配结构空间，并返回结构地址，给ps

  3. 这样ps才能有类似的ps->next操作

查找

随机访问

使用数组的时候，用下标访问数组中的元素。就是随机访问。

顺序访问

从链表的首节点开始，逐个节点移动到要访问的节点。就是顺序访问。

二分查找

二分查找需要直接跳到中点，使用这种方法适合用于数组，因为能随机访问。
不适用于链表，因为链表只能顺序访问。

示例

打印单链表的所有元素
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
#include<stdio.h>
#include<stdlib.h>
typedef struct Node* PtrToNode;//Node结构指针

struct Node
{
    int e;
    PtrToNode next;
};
int main()
{
    int n = 0;
    //定义3个Node结构指针
    PtrToNode head = NULL;
    PtrToNode prev, current;

    while (n < 3)
    {
        //动态分配内存，每次循环分配一个结构大小的内存，返回结构指针。
        //虽然current一次只能存储一个地址，但是都记录到结构中的next结构指针中
        current = (PtrToNode)malloc(sizeof(struct Node));

        if(head == NULL)
            head = current;//头指针指向第一项
        else
            prev->next = current;//存储结构地址

        current->next = NULL;//让最后一项的next指针为空
        scanf("%d", &current->e);
        prev = current;//最后，让中介指向current结构，开启下一次循环
        n++;
    }
    //打印单链表的所有元素
    current = head;
    while(current != NULL)
    {
        printf("%d ", current->e);
        current = current->next;
    }
    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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<stdio.h>
#include<stdlib.h> //提供malloc()
#include<string.h> //提供strcpy()
#define TSIZE 45
struct film
{
    char title[TSIZE];//电影题目
    int rating;//评分
    struct film * next;//存储下一个结构地址的指针
};
char * s_gets(char * st, int n);

int main()
{
    struct film * head = NULL;//头指针
    struct film * prev, *current;//前一个结构的指针，和当前结构的指针
    char input[TSIZE];
    
    puts("Enter first movie title: ");
    while (s_gets(input, TSIZE) != NULL && input[0] != '\0')
    {
        current = (struct film *)malloc(sizeof(struct film));//为当前结构的指针分配空间，开辟一块内存
        if(head == NULL)
            head = current;//让头指针指向第一个结构
        else
            prev->next = current;//让前一个结构指针指向当前的结构
        current->next = NULL;     //让当前结构的指针为空
        strcpy(current->title, input);
        puts("Enter you rating<0-10>: ");
        scanf("%d", &current->rating);
        while(getchar() != '\n')
            continue;
        puts("Enter next movie title (empty line to stop): ");
        prev = current;//经过上面的输入操作之后，让指向前一个结构的指针指向当前结构，（更新）为下一次循环做准备
    }

    if(head == NULL)
        printf("No data entered. ");
    else 
        printf("Here is the movie list:\n");
    current = head;
    while (current != NULL)
    {
        printf("Movie: %s Rating: %d\n", 
            current->title, current->rating);
        current = current->next;//（更新），让当前指针指向下个结构
    }
    current = head;
    while (current != NULL)
    {
        free(current);
        head = current->next;//（更新），让当前指针指向下个结构
    }
    printf("Bye!\n");

    return 0;
}

char * s_gets(char * st, int n)
{
    char * ret_val;
    char * find;

    ret_val = fgets(st, n, stdin);
    if(ret_val)
    {
        find = strchr(st, '\n');
        if(find)
            *find = '\0';
        else 
            while (getchar() != '\n')
                continue;
    }
    return ret_val;
}
两个链表，根据P链表的i索引作为L链表的第i个元素，输出该元素
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
#include<stdio.h>
#include<stdlib.h>
typedef struct Node * PtrToNode;
typedef PtrToNode List; //某个结构指针
typedef PtrToNode Position;
void PrintLots(List P, List L);

struct Node 
{
    int i;
    PtrToNode next;
};

int main()
{
    PtrToNode head1 = NULL, head2 = NULL;
    PtrToNode prev1, current1, prev2, current2;
    int n1 = 0, n2 = 0;
    while(n1 < 7)
    {
        //分配空间，并给指针赋值
        current1 = (PtrToNode)malloc(sizeof(struct Node));
        //让head = 第一个结构指针。else，让prev1的next = 当前的结构指针
        if(head1 == NULL)
            head1 = current1;
        else
            prev1->next = current1;
        //不要忘记，将当前的结构中的next = NULL
        current1->next = NULL;
        //给结构中的元素赋值
        current1->i = (n1 += 2);
        //最后让prev指向current，由此开始下一次循环
        prev1 = current1;
    }
    while(n2 < 70)
    {
        //分配空间，并给指针赋值
        current2 = (PtrToNode)malloc(sizeof(struct Node));
        if(head2 == NULL)
            head2 = current2;
        else
            prev2->next = current2;
        current2->next = NULL;
        current2->i = (n2 += 10);
        prev2 = current2;
    }

    PrintLots(head1, head2);

    return 0;
}
void PrintLots(List head1, List head2)
{
    int Counter = 1;
    Position Ppos = head1, Lpos = head2;

    while (Ppos->next != NULL && Lpos->next != NULL)
    {
        if(Ppos->i == Counter++)
        {
            printf("%d ", Lpos->i);
            Ppos = Ppos->next;
        }
        Lpos = Lpos->next;
    }
    
}