单链表的基本操作
数据结构--单链表的基本操作
·
第1关：单链表的插入操作
任务描述
本关任务：编写单链表的初始化、插入、遍历三个操作函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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));
if(!L) exit(-1);
L->next=NULL;
/********** End **********/
}
int ListInsert(LinkList L,int i,int e)
{
// 在带头结点的单链线性表L的第i个元素之前插入元素e
/********** Begin **********/
int j=0;
LinkList p=L,s;
while(p!=NULL && 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;
return 1;
/********** End **********/
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{
// 初始条件：单链表L已存在。
//操作结果：依次对L的每个数据元素调用函数vi()
/********** Begin **********/
LinkList p=L->next;
while(p){
vi(p->data);
p=p->next;
}
printf("\n");
/********** End **********/
}
第2关：单链表的删除操作
任务描述
本关任务：编写单链表的删除操作函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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++;
}
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查找数据元素值操作函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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关：单链表的按照值查找结点位序的操作
任务描述
本关任务：编写单链表的按照值查找结点位序的操作函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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 i=0;
LinkList p=L->next;
while(p){
i++;
if(equal(p->data,e)) return i;
p=p->next;
}
return 0;
/********** End **********/
}
第5关：单链表的逆置操作
任务描述
本关任务：编写单链表的逆置操作函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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 p,q;
p=L->next;
L->next=NULL;
while(p != NULL){
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
/********** End **********/
}
第6关：两个有序单链表的合并操作
任务描述
本关任务：分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表。要求合并后的单链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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 pa,pb,pc;
pa=La->next;
pb=Lb->next;
Lc=La;
pc=Lc;
while(pa && pb){
if(pa->data <= pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}else{
pc->next=pb;pc=pb;pb=pb->next;
}
}
pc->next=pa?pa:pb;
free(Lb);
/********** End **********/
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
16
0- 0
已为社区贡献6条内容
所有评论(0)