【头歌】单链表的基本操作

article/2025/10/7 7:26:05

单链表的基本操作

第1关：单链表的插入操作

任务描述

本关任务：编写单链表的初始化、插入、遍历三个操作函数。

相关知识

链表是线性表的链式存储结构的别称，特点是以“指针”指示后继元素，因此线性表的元素可以存储在存储器中任意一组存储单元中。

每个结点只有一个指针域的链表称为单链表。

因此单链表的一个存储结点包含两个部分，结点的形式如下：

data：为数据域，用于存储线性表的一个数据元素，也就是说在单链表中一个结点存放一个数据元素。 next：为指针域或链域，用于存放一个指针，该指针指向后继元素对应的结点，也就是说单链表中结点的指针用于表示后继关系。

单链表结点类型定义如下：

typedef  struct  LNode         // 结点类型定义 
{           ElemType  data;           //数据域    struct  LNode  *next;     //指针域
}LNode,*LinkList;             // LinkList为结构指针类型

单链表中数据类型ElemType可以多种多样，但是在编程实现算法时针对不同数据类型，每类数据元素的输入输出是有区别的，单链表的基本操作算法要在计算机上执行，须针对ElemType类型数据编写输入、输出、比较等函数：

void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

一般情况下使用链表只关心链表中结点之间的逻辑关系，并不关心链表的每个结点的实际存储位置，通常用箭头来表示链域中的指针，链表的逻辑结构可以直观的画成用箭头链接起来的结点序列。

单链表的逻辑示意图如下：

用单链表作存储结构时，对于链表的各种操作必须从头指针开始。这里讨论的单链表除特别指出外均指带头结点的单链表。

首先讨论如何进行单链表的初始化操作。

单链表的初始化操作

有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点，头结点的数据域可以什么都不存储，如果线性表为空表，则头结点的指针域为“空”，空的单链表逻辑示意图如下：

带头结点的单链表具有以下两个优点：

  1. 由于起始结点的位置被存放在头结点的指针域中，所以在单链表的第一个位置上的操作与表中的其它位置上操作一致，无须进行特殊处理；

  1. 无论单链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。

构建一个空的单链表

void InitList( LinkList &L)
{   // 操作结果：构造一个空的单链表L    L=(LinkList)malloc(sizeof(LNode)); // 申请分配头结点，并使L指向此头结点    if(!L)                             // 存储分配失败        return ;    L->next=NULL;                      // 头结点的指针域为空
}

查找单链表中第i个数据元素值的操作

在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，所以即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i随机访问一维数组中相应元素，而只能从链表的头指针出发，顺着指针域next逐个结点往下搜索，直至搜索到第i个结点为止。

从单链表的头指针L出发，从头结点开始顺着指针域向后查找。在查找过程中，头指针L保持不变，用指针p来遍历单链表，初始指向头结点，用整型变量j做记数器，j初值为0，当指针p扫描下一个结点时，计数器j相应地加1，如果跳出循环后j=i，指针p所指的结点就是要找的第i个结点；如果跳出循环后指针p的值为NULL或j≠i，则表示此单链表没有第i个结点。

    int j = 0;              // j为计数器    LinkList p = L;         // p指向单链表L的头结点    while ( p && j<i )      // 顺指针向后查找，直到p指向第i个元素或p为空    {        p=p->next;j++;    }    if ( !p || j>i )        // 第i个元素不存在，否则p指向第i个结点        return ;

单链表的插入操作

要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，首先在单链表中找到第i-1个结点并由指针p指示，然后创建一个以e为值的新结点s，将其插入到p指向的结点之后。

    int j=0;    LinkList p=L,s;    while( p && j<i-1 )                  // p指向第i-1个结点    {        p=p->next;j++;    }    if(!p || j>i-1)                      // i小于1或者大于表长        return ;    s=(LinkList)malloc(sizeof(LNode));   // s指向新生成的结点    s->data=e;                           // 将e存入新结点的数据域    s->next=p->next;                     // ①新结点s的指针域指向第i个结点    p->next=s;                           // ②第i-1个结点的指针域指向新生成的结点s

注意：插入操作的①和②执行顺序不能颠倒。

说明：当单链表中有n个结点时，则插入操作的插入位置有n+1个，即1≤i≤n+1。当i=n+1时，则认为是在单链表的尾部插入一个结点。 算法的时间主要耗费在查找操作上，故时间复杂度为O(n)。

可以通过调用基本运算算法来创建单链表，其过程是先初始化一个单链表，然后向其中一个一个地插入元素。

单链表的遍历操作

由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，头指针L指向第一个结点，对于整个单链表的读取必须从头指针开始，同时，由于单链表中最后一个结点的指针域为“空”（NULL），没有直接后继元素，对于整个单链表的读取必须在尾结点结束。函数定义如下：

   LinkList p=L->next;   //p指向单链表第一个结点   while( p )   {     vi( p->data );     p = p->next;   }

在执行遍历函数时，用函数指针vi来实现对output()函数的调用。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表的初始化操作，遍历操作及插入操作三个子函数的定义，具体要求如下：

  • void InitList(LinkList &L);//构造一个空的单链表L

  • int ListInsert(LinkList &L,int i,ElemType e) ;//在单链表L中第i个位置之前插入新的数据元素

  • void ListTraverse(LinkList L,void(*vi)(ElemType));// 依次调用函数vi()输出单链表L的每个数据元素

测试说明

平台会对你编写的代码进行测试：

测试输入： 5 12 47 5 8 69 1 99 预期输出： 插入成功，插入后单链表如下： 99 12 47 5 8 69

测试输入： 5 12 47 5 8 69 7 99 预期输出： 插入位置不合法，插入失败！

输入说明 第一行输入单链表的数据元素的个数M； 第二行输入单链表M个整数； 第三行输入要插入元素的位置； 第四行输入要插入的数据元素的值。
输出说明 第一行输出插入是否成功的提示信息； 如果插入成功，第二行输出插入元素后的单链表所有元素；如果插入失败，则不输出第二行。

开始你的任务吧，祝你成功！

实例代码

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 单链表类型定义 */
typedef struct LNode
{	ElemType data;struct LNode *next;
}LNode,*LinkList;void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));int main()               //main() function 
{	LinkList A;ElemType e;InitList(A);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}//cout<<"请输入插入的位置："<<endl;cin>>i;//cout<<"请输入插入的值："<<endl;input(e);if(  ListInsert(A,i,e) ){cout<<"插入成功，插入后单链表如下："<<endl;ListTraverse(A,output) ;}elsecout<<"插入位置不合法，插入失败！"<<endl;return  0;  }/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s){
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ // 操作结果：构造一个空的单链表L/********** Begin **********/ L=(LinkList)malloc(sizeof(LNode)); // 申请分配头结点，并使L指向此头结点L->next=NULL;          /********** End **********/
}
int ListInsert(LinkList &L,int i,int e) 
{int j=0;LinkList p=L,s;while( p && j<i-1 )                 {p=p->next;j++;}if(!p || j>i-1)                    return 0;s=(LinkList)malloc(sizeof(LNode));   s->data=e;                           s->next=p->next;                    p->next=s;                          }void ListTraverse(LinkList L,void(*vi)(ElemType))
{ LinkList p=L->next;while( p ){vi( p->data );p = p->next;}}

第2关：单链表的删除操作

任务描述

本关任务：编写单链表的删除操作函数。

相关知识

要在带头结点的单链表L中删除第i个结点，则同样要先找到第i-1个结点，使p指向第i-1个结点，使q指向第i个结点，然后令第i-1个结点的指针域指向第i+1个结点，而后删除q指向的第i个结点并释放结点空间。

设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。

注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，即p指向最后一个结点。因此只有在p->next != NULL时，才能进行删除结点的操作。

删除算法的时间复杂度也是O(n)。

链表上实现的插入和删除运算，无须移动结点，仅需修改指针。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表的删除操作函数的定义，具体要求如下：

  • int ListDelete(LinkList L,int i,ElemType &e);// 在单链表L中删除第i个元素，并由e返回其值

测试说明

平台会对你编写的代码进行测试：

测试输入： 5 12 47 5 8 69 1 预期输出： 删除成功，删除后单链表如下： 47 5 8 69 删除元素的值：12

测试输入： 5 12 47 5 8 69 6 预期输出： 删除位置不合法，删除失败！

输入说明 第一行输入单链表的长度M； 第二行输入单链表的M个整数； 第三行输入要删除元素的位置；
输出说明 第一行输出删除是否成功的提示信息； 如果删除成功，第二行输出删除元素后的单链表；第三行输出删除的数据元素；如果删除位置不合法，不输出第二行和第三行。

开始你的任务吧，祝你成功！

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);/* 单链表类型定义 */
typedef struct LNnode
{	ElemType data;struct LNnode *next;
}LNnode,*LinkList;void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
int ListDelete(LinkList L,int i,ElemType &e);
void ListTraverse(LinkList L,void(*vi)(ElemType));int main()               //main() function 
{	LinkList A;ElemType e;InitList(A);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}//cout<<"请输入删除的位置："<<endl;cin>>i;	if(  ListDelete(A,i,e) ){cout<<"删除成功，删除后单链表如下："<<endl;ListTraverse(A,output) ;cout<<"删除元素的值：";output(e);cout<<endl;}elsecout<<"删除位置不合法，删除失败！"<<endl;
}/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{cin>>s;
}
void output(ElemType s)
{cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 构造一个空的单链表L	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点if(!L) // 存储分配失败return ;L->next=NULL; // 指针域为空}int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  LinkList p,s;p = L;   int j = 0;while (p && j < i-1) {  // 寻找第i-1个结点p = p->next;++j;} if (!p || j > i-1) return 0;                   // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点s->data = e;  s->next = p->next;      // 插入L中p->next = s;return 1;
}void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 调用函数vi()依次输出单链表L的每个数据元素LinkList p=L->next;while(p){vi(p->data);p=p->next;}printf("\n");	
}int  ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改变L
{ // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值/********** Begin **********/ int j=0;LinkList p=L,r;while(p->next && j<i-1){p=p->next;j++;}// i > 表长 || i <= 0if(!p->next || j > i - 1) return 0;r=p->next;p->next=r->next;e=r->data;free(r);return 1;/********** End **********/
}

第3关：单链表的按照序号查找值操作

任务描述

本关任务：编写单链表按照序号i查找数据元素值操作函数。

相关知识

在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，所以即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i随机访问一维数组中相应元素。

设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点开始顺着指针域向后查找。

在查找过程中，头指针L保持不变，用指针p来遍历单链表，初值指向头结点，用整型变量j做记数器，j初值为0，当指针p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点；而当指针p的值为NULL或j≠i时，则表示找不到第i个结点。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表按照序号i查找数据元素值操作函数的定义，具体要求如下：

  • int GetElem(LinkList L,int i,ElemType &e);//当单链表L的的第i个元素存在时，其值赋给e并返回1，否则返回0

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 12 47 5 8 6 92 45 63 75 38 8

预期输出： 查找成功！ 第8个元素的值： 63

测试输入： 10 12 47 5 8 6 92 45 63 75 38 11

预期输出： 查找失败！

输入说明 第一行输入单链表的长度M； 第二行输入单链表的M个整数； 第三行输入要查找的序号。
输出说明 第一行输出按照序号查找是否成功的提示信息； 如果查找成功，输出查找的数据元素的值；如果查找失败，则不输出。

开始你的任务吧，祝你成功！

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);/* 单链表类型定义 */
typedef struct LNnode
{	ElemType data;struct LNnode *next;
}LNnode,*LinkList;void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int GetElem(LinkList L,int i,ElemType &e) ;int main()               //main() function 
{	LinkList A;ElemType e;InitList(A);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}//cout<<"请输入查找的序号："<<endl;cin>>i;	if(  GetElem(A,i,e) ){cout<<"查找成功！"<<endl;cout<<"第"<<i<<"个元素的值："<<endl;output(e);cout<<endl;}elsecout<<"查找失败！"<<endl;
}/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{cin>>s;
}
void output(ElemType s)
{cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表LL=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点if(!L) // 存储分配失败return ;L->next=NULL; // 指针域为空}int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  LinkList p,s;p = L;   int j = 0;while (p && j < i-1) {  // 寻找第i-1个结点p = p->next;++j;} if (!p || j > i-1) return 0;                   // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点s->data = e;  s->next = p->next;      // 插入L中p->next = s;return 1;
}void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。//操作结果：依次对L的每个数据元素调用函数vi()LinkList p=L->next;while(p){vi(p->data);p=p->next;}printf("\n");
}int GetElem(LinkList L,int i,ElemType &e) 
{ // L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回1，否则返回0/********** Begin **********/ int j=1;LinkList p=L->next;while(p && j<i){p=p->next;j++;}if(!p || j>i) return 0;e=p->data;return 1;  /********** End **********/
}

第4关：单链表的按照值查找结点位序的操作

任务描述

本关任务：编写单链表的按照值查找结点位序的操作函数。

相关知识

在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的位序，否则返回0，表示单链表中没有值等于e的结点。

查找过程从单链表的头指针指向的头结点出发，顺着指针域逐个将结点的值和给定值e作比较。

在算法实现时，应根据单链表数据元素的类型ElemType编写判断两个数据元素是否相等的比较函数equals()，如果相等equals()返回1，否则返回0。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成在单链表中查找值为e的结点位序函数的定义，具体要求如下：

  • int LocateElem(LinkList L,ElemType e,int (*equal)(ElemType,ElemType) );//在单链表L中查找，返回L中第1个与e满足关系equal()的数据元素的位序否则为0。

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 12 47 5 8 6 92 45 63 75 38 92

预期输出： 查找成功！ 92 是单链表第6个元素

测试输入： 10 12 47 5 8 6 92 45 63 75 38 93

预期输出： 查找失败！

输入说明 第一行输入单链表的长度M； 第二行输入单链表的M个整数； 第三行输入要查找的数据元素的值。
输出说明 第一行输出按照值查找是否成功的提示信息； 如果查找成功，第二行输出查找元素的逻辑序号；如果查找失败，则不输出。

开始你的任务吧，祝你成功！

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);/* 单链表类型定义 */
typedef struct LNnode
{	ElemType data;struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType));
int main()               //main() function 
{	LinkList A;ElemType e;InitList(A);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}//cout<<"请输入查找的元素："<<endl;cin>>e;	i=LocateElem(A,e,equals);if( i ) {cout<<"查找成功！"<<endl;		output(e);cout<<"是单链表第"<<i<<"个元素"<<endl;}elsecout<<"查找失败！"<<endl;
}/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{cin>>s;
}
void output(ElemType s)
{cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表LL=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点if(!L) // 存储分配失败return ;L->next=NULL; // 指针域为空	
}int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  LinkList p,s;p = L;   int j = 0;while (p && j < i-1) {  // 寻找第i-1个结点p = p->next;++j;} if (!p || j > i-1) return 0;                   // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点s->data = e; s->next = p->next;      // 插入L中p->next = s;return 1;	
}void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。//操作结果：依次对L的每个数据元素调用函数vi()LinkList p=L->next;while(p){vi(p->data);p=p->next;}printf("\n");
}int LocateElem(LinkList L,ElemType e,int (*equal)(ElemType,ElemType))
{ // 初始条件: 单链表L已存在，equal()是数据元素判定函数(满足为1，否则为0)// 操作结果: 返回L中第1个与e满足关系equal()的数据元素的位序，若这样的数据元素不存在，则返回值为0/********** Begin **********/ int j=0;LinkList p=L->next;while(p){j++;if(equal(p->data,e))return j;p=p->next;}return 0;/********** End **********/
}

第5关：单链表的逆置操作

任务描述

本关任务：编写单链表的逆置操作函数。

相关知识

单链表的就地逆置，就是要求算法不引入额外的存储空间。

先将单链表L拆分成两部分，一部分是只有头结点L的空表，另一部分是由p指向第一个数据结点的单链表。

然后遍历p，将p所指结点逐一采用头插法插入到L单链表中，由于头插法的特点是建成的单链表结点次序与插入次序正好相反，从而达到结点逆置的目的。

单链表逆置与顺序表逆置的算法思想不同，是因为数据的存储结构不同产生的。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表的逆置化操作函数的定义，具体要求如下：

  • void reverse(LinkList &L); //链表的就地逆置

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 12 47 5 8 6 92 45 63 75 38

预期输出： 逆置单链表： 38 75 63 45 92 6 8 5 47 12

输入说明 第一行输入单链表的长度M； 第二行输入单链表的M个整数；
输出说明 第一行输出提示信息； 第二行输出逆置后的单链表。

开始你的任务吧，祝你成功！

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);/* 单链表类型定义 */
typedef struct LNnode
{	ElemType data;struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void reverse (LinkList  L);
int main()               //main() function 
{	LinkList A;ElemType e;InitList(A);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}cout<<"逆置单链表："<<endl;reverse(A);ListTraverse(A,output) ;	
}/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{cin>>s;
}
void output(ElemType s)
{cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表LL=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点if(!L) // 存储分配失败return ;L->next=NULL; // 指针域为空	
}int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  LinkList p,s;p = L;   int j = 0;while (p && j < i-1) {  // 寻找第i-1个结点p = p->next;++j;} if (!p || j > i-1) return 0;                   // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点s->data = e;  s->next = p->next;      // 插入L中p->next = s;return 1;	
}void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。//操作结果：依次对L的每个数据元素调用函数vi()LinkList p=L->next;while(p){vi(p->data);p=p->next;}printf("\n");	
}void reverse (LinkList  L)
{  //逆置L指针所指向的单链表/********** Begin **********/ LinkList n,m;n=L->next;L->next=NULL;while(n != NULL){m=n;n=n->next;m->next=L->next;L->next=m;}/********** End **********/
}

第6关：两个有序单链表的合并操作

任务描述

本关任务：分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表。要求合并后的单链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。

相关知识

已知单链线性表La和Lb的元素按值非递减排列，编写函数将两个有序单链表La和Lb归并得到新的单链表Lc，Lc的元素也按值非递减排列，归并后La和Lb表不再存在。

算法思想：

  • 用pa遍历La的数据结点，pb遍历Lb的数据结点。

  • 将La头结点用作新单链表Lc的头结点，让pc始终指向Lc的尾结点（初始时指向Lc）。

  • 当pa和pb均不为空时循环：比较pa与pb之data域值，将较小者链到pc之后。

  • 如此重复直到La或Lb为空，再将余下的链表链接到pc之后。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成两个有序单链表的合并操作函数的定义，具体要求如下：

  • void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) ; // 归并有序单链表La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

测试说明

平台会对你编写的代码进行测试：

测试输入： 5 10 15 20 25 30 6 12 22 32 42 52 62

输入说明 第一行输入有序表A的长度M； 第二行依次输入有序表A的M个有序的整数； 第三行输入有序表B的长度N； 第四行依次输入有序表B的N个有序的整数。

预期输出： 合并两个有序单链表： 10 12 15 20 22 25 30 32 42 52 62

输出说明 第一行输出提示信息； 第二行输出合并后的有序单链表所包含的M+N个有序的整数。

开始你的任务吧，祝你成功！

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);/* 单链表类型定义 */
typedef struct LNnode
{	ElemType data;struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);int main()               //main() function 
{	LinkList A,B,C;ElemType e;InitList(A);InitList(B);int n,i;// cout<<"Please input the list number ";cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(A, i, e);}cin>>n;for(i=1;i<=n;i++){ cin>>e;ListInsert(B, i, e);}cout<<"合并两个有序单链表："<<endl;MergeList(A,B,C);	ListTraverse(C,output) ;	
}/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{cin>>s;
}
void output(ElemType s)
{cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{if(a==b)return  1;elsereturn  0;
}/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表LL=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点if(!L) // 存储分配失败return ;L->next=NULL; // 指针域为空	
}int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  LinkList p,s;p = L;   int j = 0;while (p && j < i-1) {  // 寻找第i-1个结点p = p->next;++j;} if (!p || j > i-1) return 0;                   // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点s->data = e;  s->next = p->next;      // 插入L中p->next = s;return 1;	
}void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。//操作结果：依次对L的每个数据元素调用函数vi()LinkList p=L->next;while(p){vi(p->data);p=p->next;}printf("\n");	
}void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) 
{// 已知单链线性表La和Lb的元素按值非递减排列。// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。/********** Begin **********/ LinkList a,b,c;a=La->next;b=Lb->next;Lc=La;c=Lc;while(a && b){if(a->data <= b->data){c->next=a;c=a;a=a->next;}else{c->next=b;c=b;b=b->next;}}c->next=a?a:b;free(Lb);/********** End **********/
}

http://chatgpt.dhexx.cn/article/mLGV1T2r.shtml

相关文章

【数据结构】单链表的基本操作及实现

【数据结构】单链表的基本操作及实现

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素&#xff08;这组存储单元可以是连续的&#xff0c;也可以是不连续的&#xff09;。因此&#xff0c;为了表示每个数据元素与其直接后继数据元素之间的逻辑关系&#xff0c;对数据元素来说&#xff0c;除…
阅读更多...
单链表的基本操作C++

单链表的基本操作C++

定义一个结构体结构体里存有数据域以及指针域&#xff0c;Lnode跟Node意思一样只是为了方便而重新起名&#xff0c;Linklist 也就是Node 的意思也是为了方便 typedef struct Node {int data; //数据域Node* next;//指针域 指针域是用来存放下一个节点的}Lnode, * Linklist;…
阅读更多...
数据结构与算法 | 单链表的基本操作

数据结构与算法 | 单链表的基本操作

1024G 嵌入式资源大放送&#xff01;包括但不限于C/C、单片机、Linux等。关注微信公众号【嵌入式大杂烩】&#xff0c;回复1024&#xff0c;即可免费获取&#xff01; 线性表的存储结构有顺序存储结构&#xff08;顺序表&#xff09;和链式存储结构&#xff08;链表&#xff09…
阅读更多...
单链表的基本操作（完整代码）

单链表的基本操作（完整代码）

函数说明&#x1f603;&#xff1a; LinkList List_HeadInsert(LinkList& L)&#xff1a;用头插法建立单链表 LinkList List_TailInsert(LinkList& L)&#xff1a;用尾插法建立单链表 LNode * GetElem(LinkList L, int i):按照序号查找结点值 LNode * LocateElem(Link…
阅读更多...
【链表】单链表的基本操作详解(C语言)

【链表】单链表的基本操作详解(C语言)

本文是单链表的C语言实现方法&#xff0c;包括单链表的创建、插入、删除、修改、查找等基本操作。 链表的底层是通过指针将一个个零散的内存块连接起来&#xff0c;链表的每个内存块称为结点。 单链表结点结构体 单链表的结点上存储数据data和下个结点的地址——后继指针nex…
阅读更多...
单链表的基本操作（详细）

单链表的基本操作（详细）

目录 0.本帖的内容&#xff1a; 1.单链表的定义 2.初始化 3.这个帖子中的功能&#xff08;函数块&#xff09; 4.利用为尾插法创建单链表 5.打印单链表 6.在带有头结点的单链表L中第i个位置之前的插入元素e 7.当第i个元素存在时&#xff0c;把第i个元素赋值给e并返回ok…
阅读更多...
单链表基本操作

单链表基本操作

目录 结构体&#xff0c;这里讨论的都是带头节点的 一、单链表建立 1、头插法&#xff1a;利用头指针控制链表节点的增加 代码&#xff1a; 2、尾插法&#xff1a; 二、遍历 三、插入&#xff1a;&#xff08;pos代表要插入的位置&#xff09; 四、删除 五、销毁 六、…
阅读更多...
单链表的基本操作

单链表的基本操作

文章目录 单链表(含头结点)一、单链表二、单链表的创建(有头结点)三、单链表的结点查找(按位置查找)四、单链表的插入操作五、链表的删除操作六、链表的逆置七、链表的置空八、链表的销毁 单链表(含头结点) 一、单链表 1.1 关于单链表 单链表是一种采用链式存储的线性结构&am…
阅读更多...
单链表的操作（超详细），保证你看完不后悔

单链表的操作（超详细），保证你看完不后悔

&#x1f30d;新人小白的博客 ⌛️希望大家多多关注 &#x1f331;一起加油&#xff0c;共同成长 &#x1f383;以后会经常更新哒~&#x1f648; ⭐️个人主页&#xff1a; 收藏加关注&#xff0c;永远不迷路~⭐️ 数据结构系列&#x1f440; 一&#xff1a;顺序表的操作&…
阅读更多...
C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作 #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; //定义单链表结构 typedef struct Node {ElemType data;//数据域struct Node *next;//指针域&#xff0c;指向下一…
阅读更多...
java线程池的工作原理_JAVA线程池原理详解一

java线程池的工作原理_JAVA线程池原理详解一

线程池的优点 1、线程是稀缺资源，使用线程池可以减少创建和销毁线程的次数，每个工作线程都可以重复使用。 2、可以根据系统的承受能力，调整线程池中工作线程的数量，防止因为消耗过多内存导致服务器崩溃。 线程池的创建 1 public ThreadPoolExecutor(int corePoolSize, 2 in…
阅读更多...
线程池原理解析

线程池原理解析

1、为什么要用线程池&#xff0c;线程池的作用&#xff08;意义&#xff09;&#xff0c;如果使用线程池会有什么好处&#xff0c;说说你对线程池的了解&#xff1f; 创建和销毁线程的代价是很大的&#xff0c;线程不像创建普通object对象那样&#xff0c;在堆中分配点内存就好…
阅读更多...
Java 线程池原理及四种常用的线程池使用

Java 线程池原理及四种常用的线程池使用

推荐阅读&#xff1a;Java线程池实现原理及其在美团业务中的实践 文章目录 什么是线程池使用线程池的好处线程池的实现原理流程图分析源码分析 线程池的使用向线程池中提交任务newCachedThreadPoolnewFixedThreadPoolnewScheduledThreadPoolnewSingleThreadExecutor自定义线程池…
阅读更多...
Tomcat线程池监控及线程池原理分析

Tomcat线程池监控及线程池原理分析

目录 一、背景 二、tomcat线程池监控 三、tomcat线程池原理 四、总结 一、背景 我们都知道稳定性、高可用对于一个系统来讲是非常重要的&#xff0c;而为了保证系统的稳定性&#xff0c;我们一般都会进行各方面的监控&#xff0c;以便系统有任何异常情况时&#xff0c;开发人员…
阅读更多...
Python学习：线程池原理及实现

Python学习：线程池原理及实现

传统多线程方案会使用“即时创建&#xff0c; 即时销毁”的策略。尽管与创建进程相比&#xff0c;创建线程的时间已经大大的缩短&#xff0c;但是如果提交给线程的任务是执行时间较短&#xff0c;而且执行次数极其频繁&#xff0c;那么服务器将处于不停的创建线程&#xff0c;销…
阅读更多...
超详细的线程池原理解析

超详细的线程池原理解析

说明 线程池作为常用的并发工具重要性不言而喻&#xff0c;本文针对线程池进行了抽丝剥茧般的深入解析&#xff0c;希望大家看后会有帮助。 1 ThreadPoolExecutor结构关系图 2 参数结构 public ThreadPoolExecutor( int corePoolSize,//核心线程数量int maximumPoolSize,…
阅读更多...
从简单代码入手，分析线程池原理

从简单代码入手，分析线程池原理

一、线程池简介 1、池化思想 在项目工程中&#xff0c;基于池化思想的技术应用很多&#xff0c;例如基于线程池的任务并发执行&#xff0c;中间件服务的连接池配置&#xff0c;通过对共享资源的管理&#xff0c;降低资源的占用消耗&#xff0c;提升效率和服务性能。 池化思想…
阅读更多...
线程池原理与实现

线程池原理与实现

目录 1. 线程池是什么 2. 线程池的优点&#xff1a; 3. 线程池的应用场景 4. 线程池的实现 4.1 线程池实现原理 4.2 线程池基本框架 4.3 结构体&#xff1a; 4.4 提供的接口 4.5 线程池测试代码 5 线程池提高demo thrd_pool.h thrd_pool.c main.c 运行结果 6 re…
阅读更多...
线程池原理——高频面试题

线程池原理——高频面试题

1.高频面试题&#xff1a; 1.为什么使用线程池&#xff0c;优势是什么&#xff1b; 2.线程池如何使用&#xff1b; 3.线程池的几个重要的参数介绍&#xff1b; 4.线程池底层工作原理&#xff1b; 5.线程池用过吗&#xff1f;生产上你如何设置合理参数&#xff1b; 2.线程…
阅读更多...
Android线程池原理详解

Android线程池原理详解

简介 但凡有点开发经验的同学都知道&#xff0c;频繁的创建和销毁线程是会给系统带来比较大的性能开销的。所以线程池就营运而生了。那么使用线程池有什么好处呢&#xff1f; 降低资源消耗 可以重复利用已创建的线程降低线程创建和销毁造成的消耗。提高响应速度 当任务到达时…
阅读更多...
推荐文章

Copyright @ 2022~2023