【头歌】单链表的基本操作
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
单链表的基本操作
第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);一般情况下使用链表只关心链表中结点之间的逻辑关系并不关心链表的每个结点的实际存储位置通常用箭头来表示链域中的指针链表的逻辑结构可以直观的画成用箭头链接起来的结点序列。
单链表的逻辑示意图如下
用单链表作存储结构时对于链表的各种操作必须从头指针开始。这里讨论的单链表除特别指出外均指带头结点的单链表。
首先讨论如何进行单链表的初始化操作。
单链表的初始化操作
有时为了操作的方便还可以在单链表的第一个结点之前附设一个头结点头结点的数据域可以什么都不存储如果线性表为空表则头结点的指针域为“空”空的单链表逻辑示意图如下
带头结点的单链表具有以下两个优点
由于起始结点的位置被存放在头结点的指针域中所以在单链表的第一个位置上的操作与表中的其它位置上操作一致无须进行特殊处理
无论单链表是否为空其头指针都是指向头结点的非空指针空表中头结点的指针域空因此空表和非空表的处理也就统一了。
构建一个空的单链表
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) ;
}
else
cout<<"插入位置不合法插入失败"<<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;
else
return 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;
}
else
cout<<"删除位置不合法删除失败"<<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;
else
return 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 <= 0
if(!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;
}
else
cout<<"查找失败"<<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;
else
return 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))
{ // 初始条件单链表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;
}
else
cout<<"查找失败"<<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;
else
return 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))
{ // 初始条件单链表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;
else
return 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))
{ // 初始条件单链表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归并得到新的单链表LcLc的元素也按值非递减排列归并后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得到新的单链线性表LcLc的元素也按值非递减排列
测试说明
平台会对你编写的代码进行测试
测试输入 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;
else
return 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))
{ // 初始条件单链表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得到新的单链线性表LcLc的元素也按值非递减排列。
/********** 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 **********/
}