注意：本人也是小白，如果出现错误希望各位读者能够包容
文章目录
前言
这次分享的是数据结构中单链表的创建和基本操作，这一部分是属于比较基础的内容，越是基础的越要投入精力去学习，不能眼高手低。在编写这篇博客的时候也出现了许多错误，这也算是一篇查漏补缺的博客。希望对大家有帮助。
一、单链表的结构定义
常规定义下的单链表，一般会包含数据域和指针域。
typedef struct node {
int data;//数据域
struct node* next;//指针域
}node,*linklist;//struct node可以用node替换 struct node*可以用linklist替换
//例如：struct node p p是结构体node的变量 node q q也是结构体node的变量
//struct node *p p是结构体node的指针变量 linklist q q也是结构体node的指针变量
//想要详细了解，可以去查阅typedef和struct的用法
这个地方会出现两个让人比较迷的东西：结构指针node和linklist。本质上（可以自行去了解指针的深层的机制）而言，这两种类型是等价的。通常用linklist说明指针变量，强调它是某个单链表的头指针变量，定义为linklist L,L表示头指针。node用来定义单链表中结点的指针，例如node *p，p为结点的指针变量，p也可以定义为头结点。但是在方法的编写时，这两种定义会混合使用，非常容易迷惑我们的思维。所以我接下来的所有方法都只使用node来定义(当然你也可以两种都使用)。
二、单链表的基本操作
1.单链表的初始化
代码如下（示例）：
//初始化链表
void startlist(node* l) {
l->next = NULL;
}
/*当然在主函数中是需要创建头结点的，你也可以换一种写法，可以不需要分配头结点内存的写法，请自行查阅
node* l;
l = (node*)malloc(sizeof(node));//分配头结点内存
startlist(l);
*/
2.单链表的创建
1.头插法
//头插法创建单链表
void creatfromhead(node* head) {
node* s;//新建一个结点指针变量
int i = 1;
int j;
while (i != 0) {
scanf("%d", &j);
if (j != EOF) {
s = (node*)malloc(sizeof(node));//新建一个结点，node*可以替换成linklist
s->data = j;//把输入的值赋值给新结点的指针域
s->next = head->next;//把新结点插入到表头
head->next = s;//头结点始终要放在表头
}
else {
i = 0;
}
}
}
头插法图片讲解
//头插法核心代码
head->next = NULL;
s->next = head->next;
head->next = s;
单个结点
原始状态
第一个元素的插入过程（注意：1和2的过程不能颠倒，否则会导致链表缺失）
1表示把新结点插入到表头
2表示头结点始终要放在表头
第一个元素插入后
第二个元素的插入过程（其他元素也类似）
第二个元素插入后
2.尾插法
//尾插法
void creatfromtail(node* head) {
node* s;//新建一个结点指针变量
node* tail;//在建立一个尾结点指针变量
int i = 1;
int j;
tail = head;//很重要的一步，令尾指针tail指向头结点head，便于做尾插入
while (i != 0) {
scanf("%d", &j);
if (j != -1) {
s = (node*)malloc(sizeof(node));//建立一个新结点
s->data = j;
tail->next = s;//尾指针的指针域指向新结点head（换一句话说，就是将新结点放在最后面）
tail = s;//再让尾指针放在s后面，尾指针永远在最后面
}
else {
i = 0;
tail->next = NULL;//尾指针的指针域设置为空，表示链表结束
}
}
}
尾插法图片讲解
//核心代码
tail = head;
s->next = NULL;
tail->next = s;
tail = s;
原始状态
第一个元素的插入过程（注意：2和3的顺序不能颠倒，否则会导致链表生成出错）
1表示尾指针为空，链表结束
2表示将新结点放在链表的最后面
3表示尾指针一直指向链表的最后一个结点
第一个元素插入后
第二个元素插入的过程（其余元素的插入也类似）
第二个元素插入后
3.头插法和尾插法的对比
头插法建立链表的算法简短易懂，但是生成链表的结点顺序与原来输入的顺序相反，而用尾插法建立的链表可使输入和生成的结点顺序相同
原因：
根据上面的头插法和尾插法的算法，我们很容易知道，当用头插法依次插入值分别为1,2,3,4,5的结点（也叫做元素）后，单链表会如下图所示：
但是用尾插法同样插入值分别为1,2,3,4,5的结点后，单链表却会如下图所示：
而在这两个链表中，输出链表中各个元素的值只能从已知的头结点head开始遍历，所以分别用头插法和尾插法创建链表后，依次输出的元素的值刚好是相反的
3.单链表的输出
//输出链表
void printlist(node *l) {
printf("该链表的内容为\n");;
while (l->next != NULL) {
printf("%d\t", l->next->data);
l = l->next;
}
printf("\n");
}
4.单链表的插入
//单链表的插入
void enterlist(node* l, int i, int e) {
node* p, * s;
int k = 0;
if (i <= 0) {
printf("插入的位置不合理\n");
}
p = l;
while (p != NULL && k < i - 1) {//查找第i-1个结点
p = p->next;
k++;
}
if (p == NULL) {//当遍历完整个表也没找到时，说明插入位置不合理（i过大）
printf("插入的位置不合理\n");
}
s = (node*)malloc(sizeof(node));
s->data = e;
s->next = p->next;// 因为p时第i-1个结点 故 s的指针域应该指向第i个结点
p->next = s;
printf("插入成功\n");
}
图片讲解（来自网上，仅供参考）
在结点p之前插入一个新的结点q:对于不带头结点的单链表，结点p的位置有所不同，插入操作有以下两种情况：
1)在链表的表头插入：
(1)创建一个新的结点q。
(2)将此结点的数据域赋值为e，并将它的next指针指向第一个结点，即L。
(3)将L修改为指向新的结点q。
操作示意图如下：
2)在链表的中间插入
(1)创建一个新的结点q。
(2)将此结点的数据域赋值为e，并将它的next指针指向p。
(3)查找到p的前驱结点pre。
(4)将pre的next指针指向新创建的结点q。
操作示意图如下：
//不带头结点的单链表的插入操作
void LinkedListInertQE1(LinkedList L, LinkedList p, ElemType e)
{
q=(LNode *)malloc(sizeof(LNode)); //创建一个新的结点q
if(q==NULL)
{
printf("申请空间失败！");
exit(0);
}
q->data=e;
if(p==L) //在表头插入
{
q->next=L;
L=q;
}
else //在表的中间进行插入
{
pre=L;
while((pre!=NULL)&&(pre->next!=p)) //寻找p的前驱
pre=pre->next;
q->next=pre->next;
pre->next=q;
}
}
//带头结点的单链表的插入操作
void LinkedListInertQE2(LinkedList L, LinkedList p, ElemType e)
{
q=(LNode *)malloc(sizeof(LNode)); //创建一个新的结点q
if(q==NULL)
{
printf("申请空间失败！");
exit(0);
}
q->data=e;
//插入新的结点
pre=L;
while((pre!=NULL)&&(pre->next!=p)) //寻找p的前驱
pre=pre->next;
q->next=pre->next;
pre->next=q;
}
5.单链表的删除
//单链表的删除操作
void dellist(node* l, int i) {
node* p, * r;
int k = 0;
p = l;
while (p->next != NULL && k < i - 1) {
p = p->next;
k++;
}
if (p->next == NULL) {
printf("删除位置不合法\n");
}
r = p->next;
p->next = r->next;
printf("删除的元素是%d\n", r->data);
free(r);
}
图片讲解（来自网上，仅供参考）
删除链表中的某个元素e，如果e在链表中出现不止一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：
1)p是链表中的第一个结点
(1)将L指向p->next。
(2)释放p。
示意图如下：
2)p是链表中的其他结点
(1)找到p的前驱结点pre。
(2)将pre->next指向p->next。
(3)释放p。
示意图如下：
//不带头结点的单链表的删除操作
void LinkedListDeleteQE1(LinkedList L, LinkedList p, ElemType e)
{
pre=L;
while((pre!=NULL)&&(pre->next->data!=e)) //查找元素e的前驱
pre=pre->next;
p=pre->next;
if(p!=NULL) //找到需要删除的结点
{
if(p==L) //删除的是第一个结点
L=p->next;
else //删除的是其他结点
pre->next=p->next;
free(p);
}
}
//带头结点的单链表的删除操作
void LinkedListDeleteQE2(LinkedList L, LinkedList p, ElemType e)
{
pre=L;
while((pre!=NULL)&&(pre->next->data!=e)) //查找元素e的前驱
pre=pre->next;
p=pre->next;
if(p!=NULL) //找到需要删除的结点
{
pre->next=p->next;
free(p);
}
}
三、源码
#include<stdio.h>
#include<stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
//链表结构
typedef struct node {
int data;
struct node* next;
}node,*LinkList;
//初始化链表
void startlist(node* l) {
l->next = NULL;
}
//头插法
void creatfromhead(node* head) {
node* s;
int i = 1;
int j;
while (i != 0) {
scanf("%d", &j);
if (j != EOF) {
s = (node*)malloc(sizeof(node));
s->data = j;
s->next = head->next;
head->next = s;
}
else {
i = 0;
}
}
}
//尾插法
void creatfromtail(node* head) {
node* s;
node* tail;
int i = 1;
int j;
tail = head;
while (i != 0) {
scanf("%d", &j);
if (j != -1) {
s = (node*)malloc(sizeof(node));
s->data = j;
tail->next = s;
tail = s;
}
else {
i = 0;
tail->next = NULL;
}
}
}
//输出链表
void printlist(node *l) {
printf("该链表的内容为\n");;
while (l->next != NULL) {
printf("%d\t", l->next->data);
l = l->next;
}
printf("\n");
}
//按序号查找
node* search1(node* l, int i) {
node* p;
int j = 0;
if (i <= 0) {
return NULL;
}
p = l;
while (p->next != NULL && j < i) {
p = p->next;
j++;
}
if (i == j) {
return p;
}
else {
return NULL;
}
}
//按值查找
node* search2(node* l, int e) {
node* p;
p = l->next;
while (p != NULL) {
if (p->data != e) {
p = p->next;
}
else {
break;
}
}
return p;
}
//求单链表的长度
int length(node* l) {
node* p;
p = l->next;
int j = 0;
while (p != NULL) {
p = p->next;
j++;
}
return j;
}
//单链表的插入
void enterlist(node* l, int i, int e) {
node* p, * s;
int k = 0;
if (i <= 0) {
printf("插入的位置不合理\n");
}
p = l;
while (p != NULL && k < i - 1) {
p = p->next;
k++;
}
if (p == NULL) {
printf("插入的位置不合理\n");
}
s = (node*)malloc(sizeof(node));
s->data = e;
s->next = p->next;
p->next = s;
printf("插入成功\n");
}
//单链表的删除操作
void dellist(node* l, int i) {
node* p, * r;
int k = 0;
p = l;
while (p->next != NULL && k < i - 1) {
p = p->next;
k++;
}
if (p->next == NULL) {
printf("删除位置不合法\n");
}
r = p->next;
p->next = r->next;
printf("删除的元素是%d\n", r->data);
free(r);
}
int main() {
node* l, * m;
l = (node*)malloc(sizeof(node));
startlist(l);
printf("单链表已初始化\n");
printf("用头插法插入链表l\n");
creatfromhead(l);
printlist(l);
m = (LinkList)malloc(sizeof(node));
startlist(m);
printf("用尾插法插入链表m\n");
creatfromtail(m);
printlist(m);
printf("查找链表m的第i个结点\n");
int k;
scanf("%d", &k);
node* s;
s = search1(m, k);
printf("链表中第i个结点的值为：%d\n", s->data);
printf("单链表的长度为：%d\n", length(m));
printf("在链表m的第一个结点插入2\n");
enterlist(m, 1, 2);
printlist(m);
printf("删除链表m中的第二个结点的值\n");
dellist(m, 2);
printlist(m);
}
效果图：
版权声明：本文为qq_60394113原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。