什么是链表？
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每 一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数域据，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
优点：可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
缺点：但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表插入快，但是查找节点会消耗时间。
链表：1.单向 2.双向 3.循环
难于理解的：1.是否为头结点 2.与下一个结点怎么连接 3.尾结点的特征
必须掌握的：1.创建链表 2.一系列操作：a.插入 b.删除 c.查找 d.修改
例题：在有序数（升序）列插入几个数，并使作用后还保持升序
分析：这题难道肯定会想到用数组和循环来解决，但是那种方法写过太多次了，所以想换一个解法。
开始思路还是比较清晰的，但是写代码的过程中遇到好多问题，特别在实现插入功能时，开始盲目的写并没有分析好是否已经检索到最后一 个结点，并分析该结点存储的数与要插入的数之间的关系，导致好多情况出错。
只有在思考透彻之后并且一行一行找出bug才能正确运行。
/*链表来解决在有序数（升序）列插入几个数的问题*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
struct an{
float num;
struct an *next;
};
int icount;
struct an *insert(struct an *phead,float a);
int main(void)
{
struct an *pnew,*phead=NULL,*pend,*p;
pnew=pend=(struct an *)malloc(sizeof(struct an));/*开辟存储空间 */
icount=0;
printf("按升序输入几个数（^z）结束:\n");
while(scanf("%f",&pnew->num)!=EOF)/*输入符合则将该结点与上一个结点连接起来*/
{
icount++;
if(icount==1)
{
pnew->next=NULL;
phead=pnew;
pend=pnew;
}
else
{
pnew->next=NULL;
pend->next=pnew;
pend=pnew;
}/*判断刚生成的结点是否为链表的第一个结点*/
pnew=(struct an *)malloc(sizeof(struct an));/*开辟新空间来存储接下来的数据*/
}
free(pnew);/*释放多余空间 */
p=(struct an *)malloc(sizeof(struct an));
int n;
float a;
printf("请输入要插入的数的个数:");
scanf("%d",&n);
printf("请依次输入%d个数:\n",n);
while(n--)
{
scanf("%f",&a);
phead=insert(phead,a);
} /*依次插入n个数 */
p=phead;
printf("插入后的顺序为:\n");
while(icount--)/*输出n个结点所存储的数据 */
{
printf("%g ",p->num);
p=p->next;
}
printf("\n");
return 0;
}
/*定义插入函数*/
/*返回头指针*/
struct an *insert(struct an *phead,float a)
{
struct an *temp=phead,*pnew,*temp1;
pnew=(struct an *)malloc(sizeof(struct an));/*为要插入的数据开辟空间*/
pnew->num=a;
icount++;
/*判断1.第一个结点之前插入2.在中间插入3.在最后一个结点之后插入*/
if(temp->num>a)/*第一个结点之前插入*/
{
pnew->next=phead;
phead=pnew;
return phead;
}
/*找到这个数该有的位置*/
while(temp->next!=NULL&&temp->num<a)
temp=temp->next;
/*在最后一个结点之前插入*/
if(temp->next!=NULL)
{
pnew->num=temp->num;
temp->num=a;
pnew->next=temp->next;
temp->next=pnew;
}
else if(temp->num>a)/*temp已经在最后一个结点，但是要在最后一个结点之前插入*/
{
pnew->next=temp;
temp1=phead;
while((temp1->next)->next!=NULL)/*单链表中关键找到最后一个结点的前一个结点*/
temp1=temp1->next;
temp1->next=pnew;
}
/*最后一个结点之后插入*/
else
{
pnew->next=NULL;
temp->next=pnew;
}
return phead;
}