链表基本概念

这个就是链表储存结构。

这只是一种链表，即单向链表。还有双向链表，单项循环链表，双向循环链表。

一个链表由无数个结点组成，每一个结点由数据域（用来储存数据）和指针域（用来储存下一个节点的位置），可以把链表想成一个锁链，那么指针域就是连接两个结点之间的链子

所以为了表示这种结构，这么写

1 struct node
2 {
3     int data;
4     node *next;　　//因为指向下一个结点，所以类型还是node
5 }*head, *r, *p;

其中head是头结点，整个链表操作都要从这开始，这也就反映出了链表的一个弊端：必须从头找，不能直接调用中间的某个结点。

p类似于开一个新的结点，r用来连接两个结点。具体看如下代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int data;
 9     node *next;
10 }*head, *r, *p;
11 int x;
12 int main()
13 {
14     scanf("%d", &x);
15     head = new node;    //建立一个新节点 
16     r = head;
17     while(x != -1)    //直到输入-1 
18     {
19         p = new node;
20         p -> data = x;    //将输入的x存入数据域 
21         p -> next = NULL;    //最后的一个结点的next没有，就指向NULL（空指针） 
22         r -> next = p;    //用来连接新的结点 
23         r = p;        //r到p，为下一次做准备 
24         scanf("%d", &x); 
25     }
26     //此时链表成功建立，一下将链表中的数据输出 
27     p = head -> next;     //这里的p的作用和前面的p完全无关，相当于控制循环的变量 
28     while(p -> next != NULL)
29     {
30         printf("%d ", p -> data);
31         p = p -> next;    //相当于for(int i = 0; i < n; ++i)中的i++ 
32     }
33     printf("%d\n", p -> data);//因为是p -> next != NULL，p的下一个没有了就停，所以要在单独输出最后一个p 
34     return 0;
35 }

有必要解释一下这个： -> 。这个东西相当于 p.node 中的 " . " ，用来表示结构体 p 里面的东西。

如 p -> data = 4; 就是将 p 中的 data 赋值成 4 。

需要注意的是，当输入 x = -1 时，并没有将 -1 存到链表中。

单向循环链表只用将最后一个结点的指针指向第一个结点即可。

 1     scanf("%d", &x);
 2     head = new node;
 3     r = head;
 4     while(x != -1)    
 5     {
 6         p = new node;
 7         p -> data = x;
 8         p -> next = NULL;
 9         r -> next = p;
10         r = p;        
11         scanf("%d", &x); 
12     }
13     p -> next = head;    //嗯

双向链表

先上个图

这就是个双向链表。

可见每一个结点的指针域分别指向前一个结点（前趋）和下一个结点（后缀），那么定义时除了一个 *next 还有一个 *pre

1 struct node
2 {
3     int data;
4     node *pre, *next;
5 }*head, *tail, *p;

所以构建双向链表时除了前面的结点和新的结点连上，新的结点还要和上一个结点连上。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 struct node
 8 {
 9     int data;
10     node *pre, *next;
11 }*head, *tail, *p;
12 int main()
13 {
14     int a; scanf("%d", &a);
15     head = new node;
16     head -> next = NULL; head -> pre = NULL;
17     tail = head;
18     while(a != -1)
19     {
20         p = new node;
21         p -> data = a;
22         p -> next = NULL;
23         p -> pre = tail;
24         tail -> next = p;
25         tail = p;
26         scanf("%d", &a);
27     }
28     p = head -> next;
29     while(p -> next != NULL) //正向输出 
30     {
31         printf("%d ", p -> data);
32         p = p -> next;
33     }
34     printf("%d\n", p -> data);
35     p = tail;
36     while(p -> pre != NULL)    //反向输出 
37     {
38         printf("%d ", p -> data);
39         p = p -> pre;
40     }
41     printf("\n");
42     return 0;
43 }

输入：1 2 3 4 5 -1

输出：1 2 3 4 5

5 4 3 2 1