AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

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

（七）单链表的删除操作


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
目录
相关文章
java冯坚持
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四：单链表面试题，新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题，并提供了详细的问题分析、思路分析以及Java代码实现，包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
java冯坚持
37 1
数据结构与算法学习四：单链表面试题，新浪、腾讯【有难度】、百度面试题
杀死一只知更鸟debug
|
3月前
|
存储 JSON NoSQL
redis基本数据结构（String，Hash，Set，List，SortedSet）【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记，包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景，并通过命令示例演示了如何在Redis中操作这些数据结构。此外，还提供了一些练习示例，帮助读者更好地理解和应用这些数据结构。
杀死一只知更鸟debug
55 0
redis基本数据结构（String，Hash，Set，List，SortedSet）【学习笔记】
小徐在进步
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
50 2
是基德吖
|
5月前
【数据结构OJ题】环形链表
力扣题目——环形链表
是基德吖
41 3
【数据结构OJ题】环形链表
是基德吖
|
5月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
是基德吖
55 1
【数据结构OJ题】复制带随机指针的链表
是基德吖
|
5月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
是基德吖
36 1
【数据结构OJ题】环形链表II
是基德吖
|
5月前
【数据结构OJ题】相交链表
力扣题目——相交链表
是基德吖
37 1
【数据结构OJ题】相交链表
是基德吖
|
5月前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
是基德吖
48 2
【数据结构OJ题】移除链表元素
是基德吖
|
5月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
是基德吖
40 1
【数据结构OJ题】链表中倒数第k个结点
东方睿赢
|
4月前
|
存储 Java 程序员
"揭秘HashMap底层实现：从数组到链表，再到红黑树，掌握高效数据结构的秘密武器！"
【8月更文挑战第21天】HashMap是Java中重要的数据结构，采用数组+链表/红黑树实现，确保高效查询与更新。构造方法初始化数组，默认容量16，负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素，利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制，提升性能。理解这些原理能帮助我们更高效地应用HashMap。
东方睿赢
50 0