1. Toy模板网首页
  2. > Toy博客

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

8月前 作者：大数据秃头族 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了【头歌】单链表的基本操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

单链表的基本操作

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

任务描述

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

相关知识

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

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

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

头歌单链表的基本操作大数据秃头,【头歌】数据结构,c++,算法,数据结构,链表,Powered by 金山文档

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);

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

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

头歌单链表的基本操作大数据秃头,【头歌】数据结构,c++,算法,数据结构,链表,Powered by 金山文档

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

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

单链表的初始化操作

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

头歌单链表的基本操作大数据秃头,【头歌】数据结构,c++,算法,数据结构,链表,Powered by 金山文档

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

  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指向的结点之后。

头歌单链表的基本操作大数据秃头,【头歌】数据结构,c++,算法,数据结构,链表,Powered by 金山文档 
    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个整数； 第三行输入要插入元素的位置； 第四行输入要插入的数据元素的值。
输出说明 第一行输出插入是否成功的提示信息； 如果插入成功，第二行输出插入元素后的单链表所有元素；如果插入失败，则不输出第二行。

开始你的任务吧，祝你成功！文章来源地址https://www.toymoban.com/news/detail-843653.html

实例代码

#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个结点并释放结点空间。

头歌单链表的基本操作大数据秃头,【头歌】数据结构,c++,算法,数据结构,链表,Powered by 金山文档

设单链表的长度为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归并得到新的单链表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;
	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得到新的单链线性表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 **********/
}

到了这里，关于【头歌】单链表的基本操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 头歌 MySQL数据库 - 数据库和表的基本操作（一）答案

    头歌 MySQL数据库 - 数据库和表的基本操作（一）答案

    第1关：查看表结构与修改表名 编程要求 根据提示，在右侧编辑器补充代码： 把数据表 tb_emp 改名为 jd_emp ； 查看该数据库下数据表的列表； 查看数据表 jd_emp 的 基本结构 。 第2关：修改字段名与字段数据类型 编程要求 根据提示，在右侧编辑器补充代码: 把数据表 tb_emp 的字

    2024年02月01日
    浏览(156)
  • 【数据结构】单链表——单链表的定义及基本操作的实现（头插、尾插、头删、尾删、任意位置的插入与删除）

    【数据结构】单链表——单链表的定义及基本操作的实现（头插、尾插、头删、尾删、任意位置的插入与删除）

    🧑‍💻作者： @情话0.0 📝专栏：《数据结构》 👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！   顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但是插入和删除操作需要移动

    2024年02月19日
    浏览(205)
  • 单链表的基本操作

    单链表的基本操作

    目录 一.链表的基本概念和结构 二.链表的分类 三.单链表的基本操作  1.创建一个节点 2.打印 3.尾插 4.头插 5.尾删 6.头删 7.查找 8.指定位置插入 9.指定位置删除 10.销毁         概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表

    2024年01月22日
    浏览(47)
  • 【头歌】顺序表的基本操作

    【头歌】顺序表的基本操作

    任务描述 本关任务：编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识 顺序表的存储结构 顺序表的存储结构可以借助于高级程序设计语言中的数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言中动态分配的一维数

    2024年04月08日
    浏览(81)
  • 【C++】单链表——单链表的基本操作

    【C++】单链表——单链表的基本操作

     由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储—— 单链表 。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。 单

    2024年02月03日
    浏览(46)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

    数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

      头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。 LinkList.h test.cpp                  （下面所有函数都默认在类中实现）   我们以

    2024年02月07日
    浏览(58)

  • 单链表的基本操作代码实现(C语言版)

    目录 前言： 单链表的基本操作 准备工作（头文件、各种宏定义以及结构体定义） 一.较简单操作 1.单链表的初始化 2.判断单链表是否为空表 3.单链表的销毁 4.单链表的清空 5.求单链表的表长 二.较重要操作 1.单链表的取值 2.单链表元素的查找 3.单链表的结点插入 4.单链表的结

    2024年04月11日
    浏览(42)
  • 单链表——单链表的定义及基本操作（头插法尾插法建表、查找、插入、删除等）

    单链表——单链表的定义及基本操作（头插法尾插法建表、查找、插入、删除等）

    上一篇我们已经完成了顺序表的实现和基本操作元素的增加、删除和查找 (链接直达：线性表元素的基本操作（C语言）【数据结构】-CSDN博客) 我们知道顺序表支持随机访问，可以通过下标来直接访问，同时也可以进行排序等优点；但是仍存在局限性，对顺序表的中部进行增加

    2024年04月10日
    浏览(48)
  • 数据结构——单链表基本操作实现 (c++)

    数据结构——单链表基本操作实现 (c++)

    单链表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这里存储单元可以是连续的，也可以是不连续的），为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系，除了存储信息本身外还要存储一个指示其直接后继的信息（地址）. 这两部分信

    2024年02月03日
    浏览(68)
  • 【数据结构】单链表基本操作：查找、插入、删除、创建

    【数据结构】单链表基本操作：查找、插入、删除、创建

     链表由结点组成，结点由数据域和指针域组成。其中，数据域存放的就是数据元素，指针域存放下一个结点的地址。数据元素可以只有一个，也可以有多个不同类型的数据元素，甚至是数组。下图和代码来自《C Primer Plus》，该链表每个节结点同时含char类型和int类型。 ​​

    2024年02月02日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包