初始化

先了解头结点

头结点是一个特殊的结点，它的数据域不存储信息，通常情况下，头指针指向的结点为头结点，由于头结点不存储信息，所以不是数据结构中的实际结点，第一个实际结点其实是head->next指示的结点，也就是头节点的下一个结点

那么，头节点的作用是什么

不带头结点链表的插入

带头结点链表的插入

可以看到，有了头结点之后，无论是在链表的任何位置进行插入操作都是一样的，所以，头结点的作用就是为了“统一操作”，值得注意的是，链表不删除，头结点就会一直存在。

插入操作也是同理

不带头结点链表的删除操作

带头结点链表的删除操作

了解完头结点后，来看一下如何设置头结点，也就是初始化

不带头结点链表的初始化

代码

//初始化，创建头结点
note *initList(note *L)
{return NULL;
}

带头结点链表的初始化

代码

//初始化，创建头结点
note *initList(note *L)
{L = (note*) malloc(sizeof(note));//为头结点分配空间L->next = NULL;//头结点指针域置空return L;
}

创建链表

头插法创建链表代码

//尾插法创建不指定个数，带头结点单链表
note *createList()
{int i;datatype data ;note *L = initList(L), *n;//分别定义头指针、新指针data = getchar();while (data != '#')//以“#”作为结束符{   n = (note*) malloc(sizeof(note));//为新结点申请空间n->data = data ;n->next = L->next;//新指针指针域是头指针下一个结点地址，L->next = n;//将新指针链入头结点之后getchar();scanf("%c",&data);}return L;
}

尾插法创建链表代码

//尾插法创建不指定个数，带头结点单链表
note *createList()
{int i;datatype data ;note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针r = L;//尾指针初始化为头指针data = getchar();while (data != '#')//以“#”作为结束符{   n = (note*) malloc(sizeof(note));//为新结点申请空间n->data = data ;n->next = NULL;//新指针指针域置空r->next = n;//将新指针链入单链表末尾r = r->next;//尾指针往后移getchar();scanf("%c",&data);}return L;
}

头插法和尾插法的区别

当然，有时要求指定结点个数创建链表，下面给出相应代码，读者可以自行比较

尾插法插法创建链表（指定结点个数）代码

//尾插法创建指定个数，带头结点单链表
note *createList()
{   int len;printf("元素个数");scanf("%d",&len);printf("请输入，用空格间隔");datatype data;note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针r = L;//尾指针初始化为头指针for(int i = 0;i < len;i ++){scanf("%d", &data);n = (note*) malloc(sizeof(note));//为新节点申请空间n->data = data;n->next = NULL;//新指针指针域置空r->next = n;//将新指针链入单链表末尾r = r->next;//尾指针往后移}return L;
}

查找

//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int i )
{int j = 0;note *p = L;if (i < 0){printf("该结点不存在");}else if( i == 0){return p ;//此时，p指向头结点}while ( p && i!=j){p = p->next;j++;}return p ;
}

插入

//插入
note *insert(note *L)
{   int pos ;datatype x;printf("请输入插入的位置和元素(用空格间隔):");scanf("%d %c",&pos,&x);note *p;note *q;p = find(L,pos);if(p){q = (note*)malloc(sizeof(note));//为要插入的结点申请空间q->data = x;q->next = p->next;p->next = q;return L;}else{printf("该结点不存在");return L;}
}

删除

//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int i )
{int j = 0;note *p = L;if (i < 0){printf("该结点不存在");}else if( i == 0){return p ;//此时，p指向头结点}while ( p && i!=j){p = p->next;j++;}return p ;
}

输出链表

void printLinkList(note *L)
{note *p;p = L->next;while(p){printf("%d ",p->data);p = p->next;}
}

这里需要注意

输出链表肯定是要输出实际结点

对于无头节点的链表，从head指向的结点开始输出（p = L）

对于有头结点的链表，需要从head->next指向的结点开始输出(p=L->next)

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>typedef char datatype;
//定义单链表结构
typedef struct note_list
{datatype data;//数据域struct note_list *next;//指针域，指向下一节点
}note;//函数声明
note *initList();
note *createList();
note *find();
note *insert();
note *delete();
void printLinkList();int main()
{note *L;printf("请输入元素，用空格间隔，用“ # ”结尾:");L = createList();insert(L);delete(L);printf("\nL链表所有元素:");printLinkList(L);return 0;
}//初始化，创建头结点
note *initList(note *L)
{L = (note*) malloc(sizeof(note));//为头结点分配空间L->next = NULL;//头结点指针域置空return L;
}//尾插法创建不指定个数，带头结点单链表
//尾插法创建不指定个数，带头结点单链表
note *createList()
{int i;datatype data ;note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针r = L;//尾指针初始化为头指针data = getchar();while (data != '#')//以“#”作为结束符{   n = (note*) malloc(sizeof(note));//为新结点申请空间n->data = data ;n->next = NULL;//新指针指针域置空r->next = n;//将新指针链入单链表末尾r = r->next;//尾指针往后移getchar();//吃掉空格scanf("%c",&data);}return L;
}//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int pos )
{int j = 0;note *p = L;if (pos < 0){printf("该结点不存在");}else if( pos == 0){return p ;//此时，p指向头结点}while ( p && pos!=j){p = p->next;j++;}return p ;
}//插入
note *insert(note *L)
{   int pos ;datatype x;printf("请输入插入的位置和元素(用空格间隔):");scanf("%d %c",&pos,&x);note *p;note *q;p = find(L,pos);if(p){q = (note*)malloc(sizeof(note));//为要插入的结点申请空间q->data = x;q->next = p->next;p->next = q;return L;}else{printf("该结点不存在");return L;}
}//删除操作
note *delete(note *L)
{   int pos;printf("请输入要删除元素的位置");scanf("%d",&pos);note *q;note *pre;//记录要删除结点的前一个结点datatype data;q = find(L,pos);if(!q){printf("此链表不存在该结点，故不能删除");return L;}data = q->data;//记录要删除链结点的数据域pre = find(L,pos-1);//返回要删除结点的前一个结点的地址pre->next = q->next;free(q);//释放空间printf("%c已删除",data);return L;
}//输出链表
void printLinkList(note *L)
{note *p;p = L->next;while(p){printf("%c ",p->data);p = p->next;}
}

结果