前言

本实验的所有代码都经过Dev c++测试，若有错误或表达不当之处，望指出。

一、单链表的相关知识

单链表是链式存储的，其每个结点除了存放数据元素之外，还存储指向下一个结点的指针；而顺序表是顺序存储的，其每个结点只存放数据元素。【顺序存储结构可以随机存取、顺序存取，而链式存储结构只能顺序存取】

顺序存储结构不仅可用于存储线性结构，还能用于树、图；顺序表的存储密度=1，而链表的存储密度<1，是由于结点中含有指针域。

若需对表进行频繁的插入、删除操作，此时适合选链式存储，因为顺序表平均需要移动近一半的元素且耗费时间（其插入和删除算法的平均时间复杂度为O(n)），而链表在插入和删除操作时不需要移动元素，只需修改指针；当若表的总数基本稳定，且很少进行插入和删除操作，则顺序表相较于链表可以充分发挥其存取速度块、存储利用率高的优点。

单链表无论是否带有头结点，其头指针都指向单链表中第一个结点，在带头结点的单链表中，头结点只作为单链表存在的标志且不存储数据，一个带头结点的单链表，若L->next==NULL时，则该单链表为空；一个不带头节点的单链表，若L==NULL时，则该单链表为空。

在单链表中，访问后继结点的时间复杂度为O(1)，而访问前驱结点的时间复杂度为O(n)。（这里可以将单链表与双链表联合记忆，双链表由于每个结点都包含其前驱结点和后继结点，所以访问它们的时间复杂度都为O(1)。）

单链表的插入和删除结点操作，都是要先找到其前驱结点，即i-1个结点，然后再将其插入或删除，这里的主要时间开销是在寻找第i-1个元素的时间上，时间复杂度为O(n)，从而使插入和删除结点操作的最好时间复杂度为O(1)【要插入或删除的元素位于第一位】，其最坏、平均时间复杂度为O(n)。

单链表的插入和删除操作中常用的是后插操作，可以通过交换两个指针的数据域，从而使时间复杂度为O(1)，这对删除操作也是一样，交换两个指针的数据域，即此时后继结点的值赋予自身，通过free()函数删除后继结点，从而使时间复杂度为O(1)。

1、带头结点的单链表

2、不带头结点的单链表

分配

（一）单链表的定义

带头结点和不带头结点的单链表定义，都为下列代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;

（二）单链表的初始化和空表判断

1、带头结点的单链表

由于带有头结点，所以要通过malloc()函数分配一个头结点L（注：malloc()函数和free()在头文件#include<stdlib.h>中），如下代码分配一个头结点：

L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点

在一个带头结点的单链表，当L->next==NULL时，表示该单链表为空，带头结点的单链表初始化的完整代码如下：

/*初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
  L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点
  if(L==NULL)  //内存不足，分配失败
  return false;
  L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
  return true;
}

带头结点的单链表判断是否为空的代码如下：

/*判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
  if(L->next==NULL) //若单链表的头结点的指针域为空，则表示单链表为空
  return true;
  else
  return false;
}

2、不带头结点的单链表

因为当L==NULL时，则该单链表为空，所以直接将单链表置为空，如下不带头结点的单链表的初始化代码：

//初始化一个不带头结点的空单链表
bool InitList(LinkList &L) {
  L=NULL;  //表示这是一个空表，暂时还没有任何结点
  return true;
}

判断不带头结点的单链表是否为空，return返回L==NULL是否为true或false，如下代码：

//判断单链表（不带头结点）是否为空
bool Empty(LinkList L) {
  return (L==NULL);
}

（三）单链表的输出

1、带头结点的单链表的输出

通过设置一个指针p，使其指向头结点的next域，即指向第一个数据元素，经过while()循环输出每次p指针的数据域（p最终不为空时输出每个结点的数据域），然后依次先后移动p指针，从而输出单链表的所有数据元素。

//单链表（带头结点）的输出
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}

2、不带头结点的单链表的输出

由于不带头结点的单链表的头指针L直接指向第一个结点，当L！=NULL，不等于空时，每次输出其数据域，然后每次移动头指针，从而输出单链表的所有数据元素。

/*单链表（不带头结点）的输出*/
void DispList(LinkList L) {
  while(L!=NULL) {
    printf("%d ",L->data);
    L=L->next;
  }
}

（四）单链表的建立

1、带头结点的单链表的建立

有两种方式建立带头结点的单链表，分别是头插法和尾插法，头插法即将新结点插入到当前单链表的表头（头结点之后），由于是头插，所以最后生成的元素顺序与原输入的元素顺序刚好相反，这就是头插法和尾插法的区别。

头插法中每次通过malloc()函数生成一个新的结点，通过&s->data读取该新结点的数据域，然后将新结点的next域指向头结点的next域，再将其赋值给L->next即放在头结点其后。

如下代码：

//（1）头插法建立单链表（带头结点）
void H_CreateHead(LinkList L,int n) {
  for(int i=0; i<n; i++) {
  int number=i+1; 
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
  scanf("%d",&s->data);   //读入新结点的数据域
  s->next=L->next;  //将新结点的指针域存放在头结点的指针域
  L->next=s;    //将新结点连到头结点之后
  }
}

可以加上以下代码，从而使其逆序，从而使头插法建立的单链表与建立的元素顺序是一样的：

void H_CreateHead(LinkList L,int n) {
  /*LNode *p,*q;*/
  for(int i=0; i<n; i++) {
  int number=i+1; 
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
  scanf("%d",&s->data);   //读入新结点的数据域
  s->next=L->next;  //将新结点的指针域存放在头结点的指针域
  L->next=s;    //将新结点连到头结点之后
  }
  /*将其逆序
  p=L->next;    //从第一个结点开始（而不是头结点）
  L->next=NULL;  //将头结点的指针域置NULL
  while(p!=NULL) {
  q=p;  //使p和q的指针结点位置相同
  p=p->next;  //p指针指向q指针的下一个结点，即q指针存储p指针的指针域
  q->next=L->next; //使q结点指向空，将头结点的指针域存放在q结点的指针域中
  L->next=q;  //将q结点连在头结点后，即q结点赋给头结点的指针域
  }*/
}

例如，通过头插法建立一个单链表并输出单链表，通过头插法建立的单链表刚好与正常输入顺序相反：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
  L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点
  if(L==NULL)  //内存不足，分配失败
  return false;
  L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
  return true;
}
/*2、头插法建立单链表（带头结点）*/
void H_CreateHead(LinkList L,int n) {
  for(int i=0; i<n; i++) {
  int number=i+1; 
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
  scanf("%d",&s->data);   //读入新结点的数据域
  s->next=L->next;  //将新结点的指针域存放在头结点的指针域
  L->next=s;    //将新结点连到头结点之后
  }
}
/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateHead(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
}

运行结果如下：

尾插法建立单链表，通过添加一个尾指针last，指向单链表的最后一个结点，每次申请一个新结点s，将其读取的数据存放到s的数据域中，然后将s的尾指针指向空，将新结点插入到单链表的尾部，从而完成建立单链表。

如下代码，通过尾插法建立的单链表是正常的输入顺序：

//尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
  LNode *last=L;  //last指针始终指向当前单链表的末尾结点
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  scanf("%d",&s->data);   //将数据读入至新结点s的数据域中
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s;  //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s;  //然后将last指针指向单链表的末尾结点，即指向新结点的后面
  }
}

例如，通过尾插法建立一个单链表，并输出单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
  L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点
  if(L==NULL)  //内存不足，分配失败
  return false;
  L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
  return true;
}
/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
  LNode *last=L;  //last指针始终指向当前单链表的末尾结点
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  scanf("%d",&s->data);   //将数据读入至新结点s的数据域中
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s;  //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s;  //然后将last指针指向单链表的末尾结点，即指向新结点的后面
  }
}
/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
}

运行结果如下：

2、不带头结点的单链表的建立

不带头结点的单链表的建立也是采用头插法和尾插法，与带头结点差不多，注意这里是LinkList &L，要不然无结果输出，代码如下：

//头插法建立单链表（不带头结点）
void Creatlist(LinkList &L,int n){
  for(int i=0;i<n;i++){
  int x;
  int number=i+1;
  printf("请输入第%d个整数：\n",number);  
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  scanf("%d",&x); 
  s->data=x;  //将输入的数据至赋予新结点s的数据域 
  s->next=L;  //将新结点的指针域存放在头指针 
  L=s;//将头指针指向新结点s，即指向新结点的前面
  }
}

例如，通过头插法建立一个不带头结点的单链表，并输出单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
  L=NULL;  //表示这是一个空表，暂时还没有任何结点
  return true;
}
/*2、头插法建立单链表（不带头结点）*/
void Creatlist(LinkList &L,int n){
  for(int i=0;i<n;i++){
  int x;
  int number=i+1;
  printf("请输入第%d个整数：\n",number);  
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  scanf("%d",&x); 
  s->data=x;  //将输入的数据至赋予新结点s的数据域 
  s->next=L;  //将新结点的指针域存放在头指针 
  L=s;//将头指针指向新结点s，即指向新结点的前面
  }
}
/*3、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
  while(L!=NULL) {
  printf("%d ",L->data);
  L=L->next;
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  InitList(L);
  printf("请输入要建立单链表的长度：\n");
  scanf("%d",&n); 
  Creatlist(L,n);
  printf("建立的单链表如下：\n");
  DispList(L);
}

运行结果如下：

不带头结点的尾插法中，设置了一个尾指针last，首先对单链表的第一个结点进行特殊处理，使头指针L和尾指针last都指向该结点，然后再从该结点，每次通过尾指针last，将新结点s插入到单链表的表尾，从而使顺序与输入的顺序是一样的，代码如下：

//尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
  int x;
  bool head_node=true;
  LNode *last=L;
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  if(head_node) {  //对第一个结点特殊处理
    head_node=false;
    s->data=x;
    s->next=NULL;
    L=s;  //将头指针指向新结点s
    last=s; //将尾指针指向新结点s
  }
  scanf("%d",&x);
  s->data=x;  //将输入的数据至赋予新结点s的数据域
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s; //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s; //last指针指向尾部
  }
}

例如，通过尾插法创建一个不带头结点的单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
  L=NULL;  //表示这是一个空表，暂时还没有任何结点
  return true;
}
/*2、尾插法建立单链表（不带头结点）*/
void Creatlist_Tail(LinkList &L,int n) {
  int x;
  bool head_node=true;
  LNode *last=L;
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  if(head_node) {  //对第一个结点特殊处理
    head_node=false;
    s->data=x;
    s->next=NULL;
    L=s;  //将头指针指向新结点s
    last=s; //将尾指针指向新结点s
  }
  scanf("%d",&x);
  s->data=x;  //将输入的数据至赋予新结点s的数据域
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s; //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s; //last指针指向尾部
  }
}
/*3、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
  while(L!=NULL) {
  printf("%d ",L->data);
  L=L->next;
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  InitList(L);
  printf("请输入要建立单链表的长度：\n");
  scanf("%d",&n); 
  Creatlist_Tail(L,n);
  printf("建立的单链表如下：\n");
  DispList(L);
}

运行结果如下：

注：不带头结点的尾插法代码参考文章：https://blog.csdn.net/qq_43619271/article/details/120694642

（五）单链表的逆序输出

1、带头结点的单链表

定义两个指针p和q，p为工作指针，q为p的后继为防止断链，其中指针p一开始指向单链表的第一个结点，即从单链表的第一个元素开始，此时并将头结点L的next域置为NULL，然后通过一个while()循环，条件是p指针不为空:

while(p!=NULL)

每次依次将元素结点摘下，q指针用于暂存p的后继，然后依次将p结点插入到头结点后，逆序处理的代码如下，其时间复杂度为O(n)，空间复杂度为O(1)：

//单链表的逆序处理
void ReverseList(LinkList L) {
  LNode *p,*q;  //p为工作指针，q为其后继防止断链 
  p=L->next;  //指向第一个结点 
  L->next=NULL; //将头结点L的next域置为NULL 
  while(p!=NULL) {
  q=p->next;  //q指针用于暂存p的后继 
  p->next=L->next;  //将p结点插入到头结点后 
  L->next=p;
  p=q;
  }
}

当想对一个单链表进行逆序处理，其实可以直接在创建单链表时，通过头插法建立单链表，从而使得到的结果是逆序的。

例如对一个通过头插法创建单链表的单链表逆序处理后输出，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
  L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点
  if(L==NULL)  //内存不足，分配失败
  return false;
  L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
  return true;
}
/*2、头插法建立单链表（带头结点））*/
void H_CreateHead(LinkList L,int n) {
  for(int i=0; i<n; i++) {
  int number=i+1; 
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
  scanf("%d",&s->data);   //读入新结点的数据域
  s->next=L->next;  //将新结点的指针域存放在头结点的指针域
  L->next=s;    //将新结点连到头结点之后
  }
/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*4、单链表（带头结点）的逆序*/
void ReverseList(LinkList L) {
  LNode *p,*q;  //p为工作指针，q为其后继防止断链 
  p=L->next;  //指向第一个结点 
  L->next=NULL; //将头结点L的next域置为NULL 
  while(p!=NULL) {
  q=p->next;  //q指针用于暂存p的后继 
  p->next=L->next;  //将p结点插入到头结点后 
  L->next=p;
  p=q;
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateHead(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  printf("\n");
  printf("逆序后的单链表如下：\n");
  ReverseList(L);
  H_DispList(L);
}

运行结果如下：

2、不带头结点的单链表

不带头结点的单链表代码如下：

void ReverseList(LinkList &L) {
  LNode *p,*q;  //定义两个指针p、q 
  p=NULL; //p指针指向NULL 
  q=L;  //q指针指向第一个数据元素 
  while(q!=NULL){
  L=L->next;  //L指向下一个指针域 
  q->next=p;  //p指针指向第二个数据元素 
  p=q;  //p指针指向q 
  q=L;  //q指针指向头指针L 
  }
  L=p;  //将头指针指向新结点s
}

例如对一个通过尾插法创建不带头结点的单链表，经逆序处理后输出，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
  L=NULL;  //表示这是一个空表，暂时还没有任何结点
  return true;
}
/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
  return (L==NULL);
}
/*3、建立单链表（不带头结点）*/
//尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
  int x;
  bool head_node=true;
  LNode *last=L;
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  if(head_node) {  //对第一个结点特殊处理
    head_node=false;
    s->data=x;
    s->next=NULL;
    L=s;  //将头指针指向新结点s
    last=s; //将尾指针指向新结点s
  }
  scanf("%d",&x);
  s->data=x;  //将输入的数据至赋予新结点s的数据域
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s; //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s; //last指针指向尾部
  }
}
/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
  while(L!=NULL) {
  printf("%d ",L->data);
  L=L->next;
  }
}
/*5、单链表（不带头结点）的逆序输出*/
void ReverseList(LinkList &L) {
  LNode *p,*q;  //定义两个指针p、q 
  p=NULL; //p指针指向NULL 
  q=L;  //q指针指向第一个数据元素 
  while(q!=NULL){
  L=L->next;  //L指向下一个指针域 
  q->next=p;  //p指针指向第二个数据元素 
  p=q;  //p指针指向q 
  q=L;  //q指针指向头指针L 
  }
  L=p;  //将头指针指向新结点s
}
//主函数
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n,i,e;
  InitList(L);
  printf("请输入要建立单链表的长度：\n");
  scanf("%d",&n);
  Creatlist_Tail(L,n);
  printf("建立的单链表如下：\n");
  DispList(L);
  printf("\n");
  printf("逆序输出单链表：\n");
  ReverseList(L); 
  DispList(L);
}

运行结果如下：

（六）单链表的插入操作

1、带头结点的单链表

将要插入的结点插到单链表的第i个位置上，也就是要找到其前驱结点，即i-1结点的位置，然后在其后插入新的结点。

代码如下【时间复杂度为O(n)】：

/*按位序插入元素至单链表中（找到i-1个结点【p】，然后将新结点【s】插入其后）*/
bool H_ListInsert(LinkList &L,int i,int e) {
  if(i<1)
  return false;
  LNode *p=L;//指针p为当前扫描的结点，且L指向头结点（第0个结点，不存储结点） 
  int j=0;  //j的值代表p指向的是第几个结点
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL) //i值不合法
  return false;
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  s->data=e;  //将要插入的结点的值赋给该新结点的数据域
  s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
  p->next=s;  //s结点指到p结点的指针域，即将s连到p之后
  return true;
}

另一种后插操作如下，参数为将指针s插入到指针p的后面【这种方法的时间复杂度为O(1)】：

/*后插法直接插入新结点*/
bool InserprioNode(LNode *p,LNode *s) {
  if(p==NULL||s==NULL)
  return false;
  s->next=p->next;  //修改指针域
  p->next=s;
  int temp=p->data;  //交换数据域
  p->data=s->data;
  s->data=temp;
  return true;
}

例如创建一个带头结点的单链表，在单链表的第2个位置插入元素“0”，最后输出插入后的单链表，通过第一种方法实现如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
  L=(LNode *)malloc(sizeof(LNode));  //分配一个头结点
  if(L==NULL)  //内存不足，分配失败
  return false;
  L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
  return true;
}
/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
  LNode *last;
  int i;
  last=L;  //last指针始终指向当前单链表的末尾结点
  for(i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  scanf("%d",&s->data);   //将数据读入至新结点s的数据域中
  s->next=NULL; //将新结点s的指针域置为空，即空指针NULL
  last->next=s;  //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s;  //然后将last指针指向单链表的末尾结点，即指向新结点的后面
  }
}
/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*4、按位序插入元素至单链表中（找到i-1个结点【p】，然后将新结点【s】插入其后）*/
bool H_ListInsert(LinkList &L,int i,int e) {
  if(i<1)
  return false;
  LNode *p; //指针p为当前扫描的结点，且L指向头结点（第0个结点，不存储结点） 
  int j=0;  //j的值代表p指向的是第几个结点
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL) //i值不合法
  return false;
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  s->data=e;  //将要插入的结点的值赋给该新结点的数据域
  s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
  p->next=s;  //s结点指到p结点的指针域，即将s连到p之后
  return true;
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  H_ListInsert(L,2,0);
  printf("\n");
  printf("插入后的单链表如下：\n");
  H_DispList(L);
}

运行结果如下：

2、不带头结点的单链表

不带头结点的单链表的插入和删除操作中，由于不含有头结点，若对表头元素进行操作，则需要另外的附加代码，修改头指针L。

若要将元素插入至单链表中第i个位置，首先要找到其前驱结点，即i-1结点的位置，然后在其后插入新的结点。但由于是不带头结点的单链表，所以就有两种情况，也就是插入至表头或其他位置，对于第1个位置需特别处理，即此时要修改头指针L。

//按位序插入元素至（不带头结点）的单链表
bool ListInsert(LinkList &L,int i,int e) {
  if(i<1)  //若插入位序小于1，则报错 
  return false;
  if(i==1) {  //插入至单链表的表头，插入第1个结点的操作如下 
  LNode *s=(LNode *)malloc(sizeof(LNode));  //创建一个新结点s 
  s->data=e;  //将e的值赋给新结点s的数据域中 
  s->next=L;  //将新结点s的next域指向原本头指针L指向的结点，从而连接起来 
  L=s;  //修改头指针L，头指针L指向新结点s
  return true;
  }
  LNode *p=L; //指针p为当前扫描到的结点，p指向第一个结点
  int j=1;  //j表示当前指针p扫描的是第几个结点
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL) //i值不合法
  return false;
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  s->data=e;  //将要插入的结点的值赋给该新结点的数据域
  s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
  p->next=s;  //s结点指到p结点的指针域，即将s连到p之后
  return true;
}

例如创建一个不带头结点的单链表，在单链表的第3个位置插入元素“9”，最后输出插入后的单链表，实现如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode *next;
} LNode,*LinkList;
/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
  L=NULL;  //表示这是一个空表，暂时还没有任何结点
  return true;
}
/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
  return (L==NULL);
}
/*3、建立单链表（不带头结点）*/
//（2）尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
  int x;
  bool head_node=true;
  LNode *last=L;
  for(int i=0; i<n; i++) {
  int number=i+1;
  printf("请输入第%d个整数：\n",number);
  LNode *s=(LNode *)malloc(sizeof(LNode));  //生成新结点s
  if(head_node) {  //对第一个结点特殊处理
    head_node=false;
    s->data=x;
    s->next=NULL;
    L=s;  //将头指针指向新结点s
    last=s; //将尾指针指向新结点s
  }
  scanf("%d",&x);
  s->data=x;  //将输入的数据至赋予新结点s的数据域
  s->next=NULL; //将新结点s的指针域置为空
  last->next=s; //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s; //last指针指向尾部
  }
}
/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
  while(L!=NULL) {
  printf("%d ",L->data);
  L=L->next;
  }
}
/*5、单链表（不带头结点）的插入操作*/
//按位序插入元素至（不带头结点）的单链表
bool ListInsert(LinkList &L,int i,int e) {
  if(i<1)  //若插入位序小于1，则报错 
  return false;
  if(i==1) {  //插入至单链表的表头，插入第1个结点的操作如下 
  LNode *s=(LNode *)malloc(sizeof(LNode));  //创建一个新结点s 
  s->data=e;  //将e的值赋给新结点s的数据域中 
  s->next=L;  //将新结点s的next域指向原本头指针L指向的结点，从而连接起来 
  L=s;  //修改头指针L，头指针L指向新结点s
  return true;
  }
  LNode *p=L; //指针p为当前扫描到的结点，p指向第一个结点
  int j=1;  //j表示当前指针p扫描的是第几个结点
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL) //i值不合法
  return false;
  LNode *s=(LNode *)malloc(sizeof(LNode));  //申请一个新结点s
  s->data=e;  //将要插入的结点的值赋给该新结点的数据域
  s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
  p->next=s;  //s结点指到p结点的指针域，即将s连到p之后
  return true;
}
//主函数
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n,i,e;
  InitList(L);
  printf("请输入要建立单链表的长度：\n");
  scanf("%d",&n);
  Creatlist_Tail(L,n);
  printf("建立的单链表如下：\n");
  DispList(L);
  printf("\n");
  printf("请输入要插入的元素位置和元素数据：\n");
  scanf("%d %d",&i,&e);
  printf("插入后的单链表如下：\n");
  ListInsert(L,i,e);
  DispList(L);
}

运行结果如下：

以下是带头结点的单链表插入操作和不带头结点的单链表的代码比较，其中查找前驱结点和将新结点插入等操作代码是相同的，但不带头结点的单链表的代码较麻烦，所以一般不带头结点的使用的较少，如下图：

数据结构学习笔记——链表的相关知识（单链表带头结点和不带头结点的基本操作）（上）

前言

一、单链表的相关知识

（一）单链表的定义

（二）单链表的初始化和空表判断

（三）单链表的输出

（四）单链表的建立

（五）单链表的逆序输出

（六）单链表的插入操作

热门文章

最新文章

相关课程

相关电子书