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

简介: 数据结构学习笔记——链表的相关知识(单链表带头结点和不带头结点的基本操作)

(七)单链表的删除操作


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

相关文章
|
3天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
23 4
|
4天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
3天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
13 0
|
17天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
17 0
|
23天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
23天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
1天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
28 9
|
23天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
24 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
4天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!