欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

数据结构》学习笔记 - 链表知识（有头节点和无头节点单链表的基本操作）（回顶部）

最编程 2024-06-11 13:18:09
...

前言


本实验的所有代码都经过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);
}


运行结果如下：

1667219487846.jpg


尾插法建立单链表，通过添加一个尾指针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指针指向单链表的末尾结点，即指向新结点的后面
  }
}


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

上一篇： 数据结构：双向链表各种操作的图解（表头插入、表尾插入、任意位置插入、查询节点、删除节点、查找链表长度......）。...)

下一篇： 链表基础知识（即单链表、表头插入、表尾插入、表头删除、表尾删除、查找、删除、插入）

推荐阅读