10

 每一个节点由两部分组成，左边部分存放具体数值，右边部分存储下一个节点的地址（称为后继指针），这里我们定义一个结构体类型来存储这个节点

struct node //节点node
{int data; //数据域struct node *next; //指针域，存放下一节点首地址
};

 上面代码中，我们定义了一个叫node的结构体类型，它有俩成员，第一个成员叫data，用来存储具体的数值；第二个成员是一个指针，用来存储下一节点的地址。因为下一节点的类型也是struct node，所以这个指针的类型也必须是struct node *类型的指针。

如何建立链表呢？首先需要一个头指针head指向链表的最开始，链表未建立时头指针为空（可理解为指向空节点） 

struct node *head;
head = NULL; //头指针初始为空

 现在创建第一个节点，并用临时指针p指向这个节点

struct node *p;
p = (struct node *)malloc(sizeof(struct node));
//使指针p变成了结构体变量

 设置第一个节点的左半部分和右半部分

int a;
cin>>a;
p->data = a; //将a的值存储到节点的数据域中
p->next = NULL; //后继指针为空，即下一节点为空

 可以这样念“p的data等于a，p的next为空”，->是结构体指针运算符，用来访问内部成员

设置头指针：（方便从头遍历整个链表） 

1，如果这是第一个创建的节点，头指针指向这个节点

2，如果不是，上一节点的后继指针指向这个节点

if(head == NULL)head = p; //第一个节点被头指针指向
elseq->next = p; //否则上一节点后继指针指向这里

最后将指针p也指向当前节点，因为下一步临时指针p会指向新节点 

q = p; //指针q指向当前节点

 完整代码1

#include
#include //malloc()
using namespace std;
struct node
{int data;struct node *next;
};
int main()
{struct node *head, *p, *q, *t;int i, n, a;cin>>n;head = NULL; //头指针初始为空for(i = 1; i <= n; ++i) {cin>>a;//动态申请一个空间存放节点，临时指针p指向这个节点p = (struct node *)malloc(sizeof(struct node));p->data = a; //数据存储到数据域p->next = NULL; //后继指针指向空if(head == NULL)head = p; //第一个节点让头指针指向elseq->next = p; //否则上一节点后继指针指向当前节点q = p; //上一节点指针指向当前节点}//输出链表中所有数t = head;while(t != NULL) {cout<data<<" ";t = t->next; //继续下一节点}return 0;
}

9
2 3 5 8 9 10 18 26 32
2 3 5 8 9 10 18 26 32

注意，上述代码没有free（释放动态申请的空间），很不安全 

插入数据

接下来，往链表插入6

关于插入，这里有个关键： 

下方完整代码第38，39行，初始指针t指向5，p指向6，t的next指向8

1. p->next = t->next;

2. t->next = p;

这两步相当于链表断开，接上了一个新的元素

p的next指向原来的t的next（指向了8的地址）

t的next再指向p的地址，顺序不能调换

插入后，t的next指向p的地址，p的next指向8的地址

 首先用临时指针t从链表头部开始遍历

t = head; //从链表头部开始遍历

 等指针t下一节点的值比6大，将6插到两节点中间，即t->next->data大于6时插入

t->next->data跟我念“t的next的data”

cin>>a; //读入待插入的数
while(t != NULL) {//未到达链表尾部if(t->next == NULL || t->next->data > a) {//动态申请空间，存放新节点p = (struct node *)malloc(sizeof(struct node));p->data = a;//新增节点后继指针指向当前节点后继指针所指向的节点p->next = t->next;t->next = p; //当前节点后继指针指向新增节点break;}t = t->next; //继续下一节点
}

 完整代码2

#include
#include //malloc()
using namespace std;//创建一个结构体表示节点
struct node
{int data;struct node *next;
};int main()
{struct node *head, *p, *q, *t; //p,q,t都是临时指针int i, n, a;cin>>n; //n个数head = NULL; //头指针初始为空for(i = 1; i <= n; ++i) {cin>>a;//动态申请空间存放一个节点，临时指针p指向该节点p = (struct node *)malloc(sizeof(struct node));p->data = a;p->next = NULL; //当前节点下一节点为空if(head == NULL)head = p; //若为第一个创建的，头指针指向该节点elseq->next = p; //上一节点后继指针指向当前节点q = p; //指针q指向当前节点}cin>>a; //待插入的数t = head; //从链表头部开始遍历while(t != NULL) {if(t->next == NULL || t->next->data > a) {p = (struct node *)malloc(sizeof(struct node));p->data = a;//新增节点后继指针指向当前节点后继指针所指向的节点p->next = t->next;t->next = p; //当前节点后继指针指向新增节点break; //插入完退出循环}t = t->next; //继续下一节点}//输出链表所有数t= head;while(t != NULL) {cout<data<<" ";t = t->next; //继续下一节点}return 0;
}

9
2 3 5 8 9 10 18 26 32
6
2 3 5 6 8 9 10 18 26 32

耗时3.5小时终于完成了第四节的学习

第五节 模拟链表

模拟链表不需要指针，却能起到链表的作用，模拟链表还能实现双向链表和循环链表

学习模拟链表可以加深我们对链表的理解，因为它们的思想是一样的，只是工具不同

它使用一个数组存放序列中的数字，使用另一个数组存放下一数字的下标

 比如上面两个数组，

right[1] == 2表示数组data第1个元素右边元素的下标为2，

right[9] == 0表示数组data第9个元素右边元素不存在

 现在需要将6插入5和8中间，怎么做呢？只需要

data[10] = 6; //加在最后

right[3] = 10; //3号右边的元素存放在data[10]

right[10] = 4; //10号元素右边的元素存放在data[4]

完整代码 

#include
using namespace std;
int main()
{int data[110], right[110];int n;cin>>n;for(int i = 1; i <= n; ++i)cin>>data[i]; //读入数据for(int i = 1; i <= n; ++i) { //初始化数组rightif(i != n) right[i] = i + 1;else right[i] = 0;}cin>>data[n + 1]; //待插入数//从链表头部开始遍历int t = 1;while(t != 0) {if(data[right[t]] > data[n + 1]) {right[n + 1] = right[t]; //right[10] = right[3]right[t] = n + 1; //right[3] = 10break; //插入完跳出循环}t = right[t]; //t自增至满足条件或遍历完}//输出链表所有数t = 1; //类似链表中 指针t = head;//t = 1少了会从中间开始输出while(t != 0) {cout<

9
2 3 5 8 9 10 18 26 32
6
2 3 5 6 8 9 10 18 26 32