备案控制台
探索云世界
开发者社区 人工智能 文章 正文

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

2022-10-31 383
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构学习笔记——链表的相关知识（单链表带头结点和不带头结点的基本操作）

（七）单链表的删除操作


1、带头结点的单链表

删除操作，也就是将单链表的第i个结点删除，这里也就是要找到其前驱结点，即i-1结点的位置（要删除的结点的前驱结点），将其指针指向第i+1个结点，并释放第i个结点。（通过free()函数实现，注意要加#include<stdlib.h>头文件）

代码如下：

/*单链表（带头结点）删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
  if(i<1)
  return false;
  int j=0;    //j的值代表p指向的是第几个结点
  LNode *p=L;   //指针p为当前扫描的结点,L指向头结点（第0个结点，不存储结点）
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL || p->next==NULL)
  return false;
  LNode *q=p->next;  //令q指向被删除的结点
  //e=q->data;    //用e返回元素的值
  p->next=q->next;  //将*q结点从链表中断开
  free(q);
  return true;
}


例如，创建一个带头结点的单链表，删除带头结点的单链表第3位元素，如下：

#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、单链表（带头结点）删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
  if(i<1)
  return false;
  int j=0;    //j的值代表p指向的是第几个结点
  LNode *p=L;   //指针p为当前扫描的结点,L指向头结点（第0个结点，不存储结点）
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL || p->next==NULL)
  return false;
  LNode *q=p->next;  //令q指向被删除的结点
  //e=q->data;    //用e返回元素的值
  p->next=q->next;  //将*q结点从链表中断开
  free(q);
  return true;
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n,i;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  printf("\n");
  printf("请输入要建删除的元素位序：\n");
  scanf("%d",&i);
  ListDelete(L,i);
  printf("删除后的单链表如下：\n");
  H_DispList(L);
}


运行结果如下：

1667220038425.jpg

另一种删除方法是删除该结点的后继结点从而实现删除一个结点，首先将其后继结点的值赋给自身，然后再删除后继结点，这样可以使时间复杂度达到O(1)，代码如下：

bool DeleteNode(LNode *p) {
  if(p==NULL)
  return false;
  LNode *q=p->next; //q指向*p的后继结点
  p->data=p->next->data;  //交换数据域
  p->next=q->next;  //将*q结点从链表中断开
  free(q);
  return true;
}


2、不带头结点的单链表

不带头结点的单链表的删除操作，与带头结点的部分代码相似，不过也是要对表头元素操作时需特殊处理，即当i==1时进行处理。

1667220061013.jpg

1667220104762.jpg


代码如下：

/*按位序删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
  if(i<1) //位序小于1，则报错 
  return false;
  LNode *p,*q;
  p=L;    //指针p为当前扫描的结点,L指向第一个结点 
  int j=1;    //j的值代表p指向的是第几个结点
  if(i==1){ //对删除第一个结点的特殊情况 
  q=L->next;
  free(p);
  L=q;
  return true;
  } 
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL || p->next==NULL)
  return false;
  q=p->next;  //令q指向被删除的结点
  //e=q->data;    //用e返回元素的值
  p->next=q->next;  //将*q结点从链表中断开
  free(q);
  return true;
}


例如，创建一个不带头结点的单链表，删除单链表第3位元素，如下：

#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、按位序删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
  if(i<1) //位序小于1，则报错 
  return false;
  LNode *p,*q;
  p=L;    //指针p为当前扫描的结点,L指向第一个结点 
  int j=1;    //j的值代表p指向的是第几个结点
  if(i==1){ //对删除第一个结点的特殊情况 
  q=L->next;
  free(p);
  L=q;
  return true;
  } 
  while(p!=NULL&&j<i-1) {
  p=p->next;  //循环找到i-1个结点，且该结点为不为空
  j++;
  }
  if(p==NULL || p->next==NULL)
  return false;
  q=p->next;  //令q指向被删除的结点
  //e=q->data;    //用e返回元素的值
  p->next=q->next;  //将*q结点从链表中断开
  free(q);
  return true;
}
//主函数
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n,i;
  InitList(L);
  printf("请输入要建立单链表的长度：\n");
  scanf("%d",&n);
  Creatlist_Tail(L,n);
  printf("建立的单链表如下：\n");
  DispList(L);
  printf("\n");
  printf("请输入要删除的元素位序：\n");
  scanf("%d",&i);
  ListDelete(L,i);
  printf("删除后的单链表如下：\n");
  DispList(L);
}


运行结果如下：

1667220123142.jpg


（八）单链表的查找操作


单链表的查找操作分为按值查找和按位查找（注：位序是从1开始）：

image.png


1、带头结点的单链表


按值查找的操作通过比较data数据域，即从单链表的第一个结点开始（不是头结点，而是p=L->next），依次比较各个结点的data数据域，若某结点的data数据域等于查找值，再通过一个if语句判断该指针是否为空，若为空则表示单链表中有该结点并输出该结点的位序和值，然后返回true；否则返回false。

按值查找的代码如下：

/*按值查找（比较data数据域）*/
bool Locatexdata(LinkList L,int x) {
  int i=1;
  LNode *p=L->next;
  while(p!=NULL&&p->data!=x) {
  p=p->next;
  i++;
  }
  if(p!=NULL) {
  printf("已找到表中第%d位且值为%d的结点",i,x);
  return true;
  } else
  return false;
}


例如创建一个单链表，然后查找值为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、按值查找（比较data数据域）*/
bool Locatexdata(LinkList L,int x) {
  int i=1;
  LNode *p=L->next;
  while(p!=NULL&&p->data!=x) {
  p=p->next;
  i++;
  }
  if(p!=NULL) {
  printf("已找到表中第%d位且值为%d的结点",i,x);
  return true;
  } else
  return false;
}
/*5、单链表（带头结点）的输出*/
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,x,a;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  printf("\n");
  printf("请输入要查找的值！\n");
  scanf("%d",&x);
  a=Locatexdata(L,x);
  printf("\n");
  printf("返回值为：%d",a);
}


运行结果如下：

1667220187708.jpg


按位查找的操作是从头结点开始，通过next指针域依次搜索链表，直到找到第i个结点（要搜索的结点的位序）为止，若找到则输出第i个结点的值和位序并返回true；若没有找到则返回false。

按位查找的代码如下：

/*带头结点的单链表按位查找*/
bool Searchlocate(LinkList L,int i){
  if(i==0 || i<1)
  return false;
  int j=1;
  LNode *p=L->next;
  while(p!=NULL&&j<i){
  p=p->next;
  j++;
  }
  printf("已找到表中第%d位且值为%d的结点",j,p->data);
  return true;
}


例如创建一个单链表，查找单链表中位序为3的元素（第三个元素），如下：

#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指针指向单链表的末尾结点，即指向新结点的后面
  }
}
/*4、按位查找*/
bool Searchlocate(LinkList L,int i){
  if(i==0 || i<1)
  return false;
  int j=1;
  LNode *p=L->next;
  while(p!=NULL&&j<i){
  p=p->next;
  j++;
  }
  printf("已找到表中第%d位且值为%d的结点",j,p->data);
  return true;
}
/*5、单链表（带头结点）的输出*/
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,i,a;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  printf("\n");
  printf("请输入要查找的位序！\n");
  scanf("%d",&i);
  a=Searchlocate(L,i);
  printf("\n");
  printf("返回值为：%d",a);
}


运行结果如下：

1667220229600.jpg

2、不带头结点的单链表

按值查找的代码如下：

/*不带头结点的单链表按值查找*/
bool Locatexdata(LinkList L,int x) {
  int i=1;
  LNode *p=L;
  while(p!=NULL&&p->data!=x) {  //依次查找
  p=p->next;
  i++;
  }
  if(p!=NULL) {
  printf("已找到表中第%d位，值为%d的结点",i,x);
  return true;
  } else
  return false;
}


按位查找的代码如下：

/*不带头结点的单链表按位找*/
bool Searchlocate(LinkList L,int i){
  if(i==0 || i<1)
  return false;
  int j=1;
  LNode *p=L;
  while(p!=NULL&&j<i){
  p=p->next;
  j++;
  }
  printf("已找到表中第%d位且值为%d的结点",j,p->data);
  return true;
}


（九）单链表的求表长操作


1、带头结点的单链表

求表长需定义一个变量来记录链表长度，另外定义一个指针p指向链表的头结点，然后可以通过一个while循环，其循环条件是当p->next!=NULL，即指向第一个数据元素p->next开始，直到指向NULL时结束循环，每次p指针移动至下一个数据元素，然后变量递加，最后返回链表长度，如下代码：

/*带头结点的单链表求表长*/
int LengthList(LinkList L) {
  int length=0; //定义变量length记录链表长度 
  LNode *p=L; //指针p从头结点开始，指向头结点 
  while(p->next!=NULL) {
  p=p->next;  //循环中p指针每次移动 
  length++;
  }
  return length;
}


例如，输出一个单链表的表长：

#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、判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
  if(L->next==NULL) //若单链表的头结点的指针域为空，则表示单链表为空
  return true;
  else
  return false;
}
/*3、建立单链表（带头结点）*/
//（1）头插法建立单链表（带头结点）并逆置单链表
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结点赋给头结点的指针域
  }*/
}
//（2）尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
  LNode *last=L;
  //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的指针域置为空，即空指针NULL
  last->next=s;  //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s;  //然后将last指针指向单链表的末尾结点，即指向新结点的后面
  }
}
/*4、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*5、带头结点的单链表求表长*/
int LengthList(LinkList L) {
  int length=0; //定义变量length记录链表长度 
  LNode *p=L; //指针p从头结点开始，指向头结点 
  while(p->next!=NULL) {
  p=p->next;  //循环中p指针每次移动遍历单链表 
  length++;
  }
  return length;
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);
  printf("建立的单链表如下：\n");
  H_DispList(L);
  printf("\n");
  printf("单链表的长度为：%d\n",LengthList(L));
}


运行结果如下：

1667220332931.jpg

2、不带头结点的单链表

不带头结点的单链表求表长操作，在带头结点的单链表的代码上，将while循环条件改为p!=NULL即可，其他不变，也是定义一个变量来记录链表长度，另外定义一个指针p指向链表的头结点，每次p指针移动至下一个数据元素，然后变量递加，最后返回链表长度，如下代码：

/*单链表（不带头结点）的求表长*/
int LengthList(LinkList L) {
  int length=0; //定义变量length记录链表长度 
  LNode *p=L; //指针p从头结点开始，指向头结点 
  while(p!=NULL) {
  p=p->next;  //循环中p指针每次移动遍历单链表 
  length++;
  }
  return length;
}


例如，输出一个单链表的表长：

#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、建立单链表（不带头结点）*/
//（1）头插法建立单链表（不带头结点）【顺序相反】
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，即指向新结点的后面
  }
}
//（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、单链表（不带头结点）的求表长*/
int LengthList(LinkList L) {
  int length=0; //定义变量length记录链表长度 
  LNode *p=L; //指针p从头结点开始，指向头结点 
  while(p!=NULL) {
  p=p->next;  //循环中p指针每次移动遍历单链表 
  length++;
  }
  return length;
}
//主函数
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("单链表的长度为：%d\n",LengthList(L));
}


运行结果如下：

1667220374254.jpg


（十）单链表的排序


这里采用的是通过直接排序算法，使带头结点的单链表递增有序，并输出。

//使单链表递增排列有序
void SortList(LinkList L) {
  LNode *p=L->next,*pre;
  LNode *r=p->next; //r指针用于保持p后继结点指针，保证不断链
  p->next=NULL; //断链，构造只含有一个数据结点的有序表
  p=r;  //将r指针改为p指针 
  while(p!=NULL) {
  r=p->next;  //保存p的后继结点指针，r指针始终指向p指针的next域 
  pre=L;  //pre指针从头开始 
  while(pre->next!=NULL&&pre->next->data<p->data)
    pre=pre->next;  //在有序表中查找插入p的前驱结点pre 
  p->next=pre->next;  //将p插入到pre之后 
  pre->next=p;
  p=r;  //扫描原单链表中剩下的结点 
  }
}


例如，创建一个带头结点的单链表，然后通过排序算法输出排序后的单链表：

#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、判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
  if(L->next==NULL) //若单链表的头结点的指针域为空，则表示单链表为空
  return true;
  else
  return false;
}
//3、尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
  LNode *last=L;
  //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的指针域置为空，即空指针NULL
  last->next=s;  //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
  last=s;  //然后将last指针指向单链表的末尾结点，即指向新结点的后面
  }
}
/*4、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
  LNode *p;
  p=L->next;
  while(p!=NULL) {
  printf("%d ",p->data);
  p=p->next;
  }
}
/*5、排序：使单链表递增排有序*/
void SortList(LinkList L) {
  LNode *p=L->next,*pre;
  LNode *r=p->next; //r指针用于保持p后继结点指针，保证不断链
  p->next=NULL; //断链，构造只含有一个数据结点的有序表
  p=r;  //将r指针改为p指针 
  while(p!=NULL) {
  r=p->next;  //保存p的后继结点指针，r指针始终指向p指针的next域 
  pre=L;  //pre指针从头开始 
  while(pre->next!=NULL&&pre->next->data<p->data)
    pre=pre->next;  //在有序表中查找插入p的前驱结点pre 
  p->next=pre->next;  //将p插入到pre之后 
  pre->next=p;
  p=r;  //扫描原单链表中剩下的结点 
  }
}
/*主函数*/
int main() {
  LinkList L;  //声明一个指向单链表的指针
  int n;
  H_InitList(L);  //初始化一个空的单链表
  printf("请输入要建立单链表的长度：");
  scanf("%d",&n);
  H_CreateTail(L,n);//创建单链表 
  printf("建立的单链表如下：\n");
  H_DispList(L);//输出单链表 
  printf("\n");
  SortList(L);//排序 
  printf("排序后的单链表如下：\n"); 
  H_DispList(L);
}


运行结果如下：

1667220426896.jpg

若需将排序的结果是递减排序的，将“<”改为“>”，即

while(pre->next!=NULL&&pre->next->data<p->data)


二、双链表的相关知识


双链表是在单链表结点上增添了一个指针域，指向当前结点的前驱结点，从而可以通过后继结点找到前驱结点，由于每个结点都包含其前驱结点和后继结点，所以访问它们的时间复杂度都为O(1)。

一个带头结点的双链表，若L->next==NULL时，则该双链表为空；一个不带头结点的双链表，若L==NULL时，则该双链表为空。

双链表的插入、删除操作的时间复杂度都为O(1)。

1667220449060.jpg


三、循环链表的相关知识


循环单链表可以实现从任一个结点访问链表中的任何结点，在带头结点的循环单链表中，若L==head->next时，循环单链表为空；在不带头结点的循环单链表中，若L==NULL时，循环单链表为空。

1667220468865.jpg

一个带头结点的循环双链表，若L->prior==L&&L->next==L时，则该双链表为空。（即其头结点的prior和next域都指向其本身时为空）

循环单链表中，设置尾指针而不设置头指针的好处是可以使查找链表的开始结点和终端结点很方便，其查找时间都为O(1)，而若使用头指针则查找开始结点的时间为O(1)，查找终端结点时间为O(n)。

1667219976224.jpg

文章标签：
搜索推荐
关键词：
数据结构链表
链表数据结构
链表结点
数据结构单链表
数据结构结点
游客5pa3gelrqbo2g
目录
相关文章
西柚与蓝莓
|
11天前
19 删除链表的倒数第 N 个结点
19 删除链表的倒数第 N 个结点
西柚与蓝莓
14 1
吹吹晚风
|
21天前
|
存储 缓存 算法
数据结构-链表(一)
链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素（节点）在内存中不必连续存储，而是通过指针链接在一起。 链表由多个节点组成，每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点的引用）。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针通常指向空值（null）。
吹吹晚风
31 1
游客yit5ffk3osumc
|
22天前
|
存储 算法 索引
数据结构与算法：单链表
朋友们大家好，本节来到数据结构与算法的新内容：单链表 在上篇文章中，我们知道顺序表通常需要预分配一个固定大小的内存空间， 通常以二倍的大小进行增容，可能会造成空间的浪费，本篇文章我们介绍的链表可以解决这个问题
游客yit5ffk3osumc
19 1
小林熬夜学编程
|
23天前
|
存储 C++
数据结构第六弹---带头双向循环链表
数据结构第六弹---带头双向循环链表
小林熬夜学编程
30 0
起飞的风筝
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
起飞的风筝
32 0
认真学习的小雅兰.
|
1天前
|
存储 算法
单链表——“数据结构与算法”
单链表——“数据结构与算法”
认真学习的小雅兰.
5 0
Mylvzi
|
6天前
数据结构--链表刷题(一)快慢指针（上）
数据结构--链表刷题(一)快慢指针
Mylvzi
13 0
阿森要自信
|
15天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
11 1
阿森要自信
|
15天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
20 0
修修修也
|
19天前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
修修修也
27 0

热门文章

最新文章

  • 1
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
  • 2
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
  • 3
    C++关联容器深度解析：提升数据结构操作的艺术
  • 4
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 5
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 6
    Java数据结构与算法-java数据结构与算法（二）
  • 7
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 8
    【软件设计师备考 专题 】数据结构深度解析：从数组到图
  • 9
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 10
    C/C++ 数据结构设计与应用（二）：自定义数据结构的设计 (Design of Custom Data Structures)
  • 1
    【数据结构算法（二）】链表总结
    15
  • 2
    《剑指offer》——合并两个排序的链表
    18
  • 3
    《剑指offer》——从尾到头打印链表
    20
  • 4
    【移除链表元素】LeetCode第203题讲解
    18
  • 5
    【顺序表和链表的对比】
    15
  • 6
    【双向链表】数据结构双向链表的实现
    20
  • 7
    【单链表】数据结构单链表的实现
    32
  • 8
    实现单链表的基本操作（力扣、牛客刷题的基础&笔试题常客）
    140
  • 9
    快慢指针该如何操作？本文带你认识快慢指针常见的三种用法及在链表中的实战
    19
  • 10
    leetcode82. 删除排序链表中的重复元素 II
    22

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云oss简介和使用流程
    为什么选择阿里云什么是云计算全球基础设施技术领先稳定可靠安全合规分析师报告
    产品和定价全部产品免费试用产品动态产品定价价格计算器云上成本管理
    解决方案技术解决方案
    文档与社区文档开发者社区天池大赛培训与认证
    权益中心免费试用高校计划企业扶持计划推荐返现计划
    支持与服务基础服务企业增值服务迁云服务官网公告健康看板信任中心
    关注阿里云
    关注阿里云公众号或下载阿里云APP，关注云资讯，随时随地运维管控云服务
    阿里云APP阿里云微信
    联系我们：4008013260
    法律声明Cookies政策廉正举报安全举报联系我们加入我们
    阿里巴巴集团淘宝网天猫全球速卖通阿里巴巴国际交易市场1688阿里妈妈飞猪阿里云计算AliOS万网高德UC友盟优酷钉钉支付宝达摩院淘宝海外阿里云盘饿了么
    © 2009-2024 Aliyun.com 版权所有 增值电信业务经营许可证： 浙B2-20080101 域名注册服务机构许可： 浙D3-20210002 京D3-20220015
    浙公网安备 33010602009975号浙B2-20080101-4