No.2.4 链表
一、链表简介
数组/列表：作为一个整体出现，只能在头、尾进行更新操作
链表：指针+动态分配内存函数malloc实现，每个元素都有一个后向指针，指明下一个元素的位置，尾元素有个空指针。
1.关于指针：
int a=10, *p; // * 间接运算符，作用是取得指针 p 指向的内存地址保存的变量值
p = &a; // &为取地址符，这样 p 就获得了 a 的内存地址
*p = 100; // a == 100
2.关于动态分配内存函数 malloc
int *p;
p = (int *)malloc(sizeof(int)); //指针 p 获取动态分配的内存空间地址
注意：指针指向的是内存空间的首地址（第一个字节的地址），而指针类型决定了作为一个整体的内存长度；
3.链表结构体
struct node
{ int data; //存储具体数据
struct node *next; //指针，存储下一个节点的地址，因为下一个节点类型也是struct node，所以该指针也必须是struct node类型的指针
struct node *head; //链表首先要有一个头指针
head = NULL; //初始化时，头指针为空
4.代码练习
EG1. 向链表中写入数据
int main(){
struct node *head,*q,*p,*t;
int i,b,nn;
scanf("%d",&nn);
head = NULL; //头指针为空
for (i=1;i<=nn;i++){ //循环读取n个数
scanf("%d", &b);
//动态申请一个空间以存放node，并用临时指针p指向这个节点
p = (struct node *)malloc(sizeof(struct node)); //释放空间 free
p->data = b;
p->next=NULL; //尾指针为空
if(head==NULL)
head=p; //如果这是创建的第一个节点，则将头指针指向该节点
else
q->next = p; //若不是第一个创建的节点，则将上一个节点的后续指针指向该节点
q=p; //递归，q 重置为尾节点
}
t = head;
while (t!=NULL){
printf("%d ",t->data);
t=t->next; //递归，t 重置为下一个节点
}
return 0;
}
EG2.向链表中插入数据
int main(){
struct node *head,*q,*p,*t,*y;
int i,b,nn;
printf("请输入链表长度:\n");
scanf("%d",&nn);
head = NULL; //头指针为NULL
printf("请输入各节点整数值:\n");
for (i=1;i<=nn;i++){ //循环读取n个数
scanf("%d", &b);
//动态申请一个空间以存放node，并用临时指针p指向这个节点
p = (struct node *)malloc(sizeof(struct node));
p->data = b;
p->next=NULL; //尾指针为空
if(head==NULL)
head=p; //如果这是创建的第一个节点，则将头指针指向该节点
else
q->next = p; //若不是第一个创建的节点，则将上一个节点的后续指针指向该节点
q=p; //递归，q 重置为尾节点
}
printf("当前链表为：\n");
t=head;
while (t!=NULL){
printf("%d ",t->data);
t=t->next; //递归，t 重置为下一个节点
}
printf("请输入要插入链表的值：\n");
scanf("%d",&b);
t = head;
while (t->data <=b){
t=t->next;
}
y=t->next;
t->data=b;
t->next=y;
printf("新链表值为：\n");
t=head;
while (t!=NULL){
printf("%d ",t->data);
t=t->next; //递归，t 重置为下一个节点
}
getchar();
return 0;
}
EG2.测试会发现，插入的值把后面一个节点替代了，而不是要求的那样“新增一个节点，后面的节点全部后移“。正确的做法应该是这样：
scanf("%d",&a);//读入待插入的数
t=head;//从链表头部开始遍历
while(t!=NULL)//当没有到达链表尾部的时候循环
{
if(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;//继续下一个结点
}
5.讨论：还是老问题，弄清楚head到底是节点自身，还是指向节点的指针！
上述代码是有点问题的：
a.head直接指向了头节点，而判断语句if(t->next->data > a)，直接跳过了头结点进行判断，导致头查有问题：
要么head 作为一个空节点独立存在，
要么以 head->data作为判断起点
b.这时又出现另外一个问题，比如向(1,3,5)中插入2，指针已经指到了3，那么就要交换节点的值，然后进行指针操作；
c.尾节点的插入相似。