一、单链表的分类
单链表一共有两种，一个是带头结点的单链表，还有一个是不带头结点的单链表
总的来说，带头结点的单链表相对于不带头结点的单链表来说，更加方便对链表基本操作的实现
（带头结点的单链表操作起来更方便，所以很多时候我们都是用带头结点的单链表）
二、单链表的初始化
单链表的初始化，我们分不带头结点和带头结点两种情况
2.1 初始化不带头结点的单链表
不带头结点的单链表，说明头指针指向了第一个有效的结点
PNode Init_1_Node(){ PNode head; head=NULL; //因为不带头结点，所以我们只要让头结点为空 return head; }
2.2 初始化带头结点的单链表
带头结点的单链表，头指针要指向头结点（头结点不存放数值，可将头结点理解为无效结点）
PNode Init_2_Node(){ PNode head; head=(PNode)malloc(sizeof(Node)); //申请一个头结点 head->next=NULL; //头结点指针域指向空 return head; }
三、单链表的创建
单链表的创建，我们分不带头结点和带头结点来介绍，具体再分为头插法和尾插法两种方法
3.1 创建不带头结点的单链表
3.1.1 头插法
头插法嘛，顾名思义，每次都在链表的前面插入，这样最先输入的结点最后输出，最后输入的结点最先输出。例如你输入的是1，2，3。那么打印出来的将是3，2，1。
void Creat_1_Node(PNode *head){ //不带头结点我们用头指针的地址来保存单链表 int i,n; printf("（头插法）请输入不带头结点的链表结点个数："); scanf("%d",&n); //输入不带头结点单链表的结点个数 for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); //创建一个新的结点 Pnew->next=NULL; //指针域指向空 printf("第%d个结点的元素为：",n+1-i); scanf("%d",&Pnew->data); if(*head==NULL){ //判断头指针是否指向空 *head=Pnew; //如果是则让头指针指向第一个有效结点 }else{ //当头指针指向非空时 Pnew->next=*head; //将新的结点插入到头指针所指结点的前面 *head=Pnew; //头指针指向新插入的结点 } } //例如你输入 1 2 3 } //实际上链表是 3 2 1 这是因为你是在前面插入了新的结点
3.1.2 尾插法
尾插法呢就比较好理解了，每次都在链表的最后插入一个新的结点就好了，这个是按顺序的，输入什么最后就输出什么。例如输入1，2，3。输出将是1，2，3。
void Creat_2_Node(PNode *head){ PNode Last; //尾插法的话，我们要有一个时刻指向尾结点的指针 int i,n; printf("（尾插法）请输入不带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",i); scanf("%d",&Pnew->data); if(*head==NULL){ //判断头指针是否指向空，这是必要的 *head=Pnew; //头指针指向第一个有效结点 Last=Pnew; //因为此时只有一个结点，所以Last指向这个结点就好 }else{ //当头指针指向不是空的时候 Last->next=Pnew; //尾结点指针域指向新插入的结点 Last=Pnew; //将新结点赋给尾结点（插入的结点变成新的尾结点） } } }
3.2 创建带头结点的单链表
3.2.1 头插法
带头结点的单链表使用头插法创建时，一定要注意 Pnew->next=p->next 和 p->next=Pnew 两行代码不能颠倒！Pnew->next=p->next 的意思是将p后面的所有结点都接到了要插入的新结点的后面，p->next=Pnew 的意思是将新结点接到p（头结点）的后面。如果将两行代码颠倒了，那么头结点后面的所有结点将丢失，这样无论你创建多大的链表，其实最后都只有两个结点（一个是头结点，没什么用，还有一个就是你输入的最后一个数据），其他的结点都丢失了
void Creat_3_Node(PNode head){ PNode p=head; //将head赋给p，p是头结点，不保存数据，为无效结点 int i,n; printf("（头插法）请输入带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); //创建新的结点 Pnew->next=NULL; //指针域指向空 printf("第%d个结点的元素为：",n+1-i); scanf("%d",&Pnew->data); Pnew->next=p->next; //这里注意一定要先把p后面的所有结点接到Pnew后面 p->next=Pnew; //再执行把Pnew连接到p后面 } }
3.2.2 尾插法
尾插法就不需要担心数据丢失的问题了，因为是在尾结点后面插入（尾结点后面没有其他结点）
void Creat_4_Node(PNode head){ PNode p=head; PNode Last; //需要一个时刻指向尾结点的指针 Last=p; int i,n; printf("（尾插法）请输入带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",i); scanf("%d",&Pnew->data); Last->next=Pnew; //尾结点指针域指向要插入的结点 Last=Pnew; //新插入的结点成为新的尾结点 } }
四、单链表的打印
这里分为不带头结点和带头结点两种情况，需要分别打印
4.1 打印不带头结点的单链表
void Print_1_Node(PNode head){ PNode p=head; //不带头结点，p就是第一个有效元素 printf("新的链表为："); while(p!=NULL){ //采用循环挨个打印 printf("%d ",p->data); p=p->next; } printf("\n"); }
4.2 打印带头结点的单链表
void Print_2_Node(PNode head){ PNode p=head->next; //带头结点，p应该为第一个有效结点 printf("新的链表为："); while(p!=NULL){ printf("%d ",p->data); //打印 p=p->next; } printf("\n"); }
五、代码实现
5.1 完整代码
#include<stdio.h> #include<malloc.h> typedef struct Node{ int data; struct Node * next; }Node,*PNode; PNode Init_1_Node(){ PNode head; head=NULL; return head; } PNode Init_2_Node(){ PNode head; head=(PNode)malloc(sizeof(Node)); head->next=NULL; return head; } void Creat_1_Node(PNode *head){ int i,n; printf("（头插法）请输入不带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",n+1-i); scanf("%d",&Pnew->data); if(*head==NULL){ *head=Pnew; }else{ Pnew->next=*head; *head=Pnew; } } } void Creat_2_Node(PNode *head){ PNode Last; int i,n; printf("（尾插法）请输入不带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",i); scanf("%d",&Pnew->data); if(*head==NULL){ *head=Pnew; Last=Pnew; }else{ Last->next=Pnew; Last=Pnew; } } } void Creat_3_Node(PNode head){ PNode p=head; int i,n; printf("（头插法）请输入带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",n+1-i); scanf("%d",&Pnew->data); Pnew->next=p->next; p->next=Pnew; } } void Creat_4_Node(PNode head){ PNode p=head; PNode Last; Last=p; int i,n; printf("（尾插法）请输入带头节点的链表结点个数："); scanf("%d",&n); for(i=1;i<=n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); Pnew->next=NULL; printf("第%d个结点的元素为：",i); scanf("%d",&Pnew->data); Last->next=Pnew; Last=Pnew; } } void Print_1_Node(PNode head){ PNode p=head; printf("新的链表为："); while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } void Print_2_Node(PNode head){ PNode p=head->next; printf("新的链表为："); while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ PNode H1,H2,H3,H4; H1=Init_1_Node(); Creat_1_Node(&H1); Print_1_Node(H1); H2=Init_1_Node(); Creat_2_Node(&H2); Print_1_Node(H2); H3=Init_2_Node(); Creat_3_Node(H3); Print_2_Node(H3); H4=Init_2_Node(); Creat_4_Node(H4); Print_2_Node(H4); return 0; }
5.2 运行结果
六、总结
综上所述，我们一共有四种创建单链表的方法，其实头插法基本不用，我们用的最多的是尾插法创建带头结点的单链表。
在创建单链表的时候，要注意几个问题：
1.一定要初始化单链表，不管是带头结点还是不带头结点的单链表，不然会出现输入一半程序终结的情况（暂时不知道是什么情况）
2.创建不带头结点的单链表，要用到指针的指针，否则没法保存地址。
3.创建不带头结点的单链表，一定要先判断头指针是否指向空
