循环单链表的基本操作

第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 LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void InitList(LinkList &L);
int ListInsert(LinkList L,int i,ElemType e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int ListLength(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;
	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
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=L; // 指针域为L	
}

// 求循环链表长度
int ListLength(LinkList L){
	LinkList q=L->next;
	int i=0;
	while(q!=L){
		i++;
		q=q->next;
	}
	return i;
}
int ListInsert(LinkList L,int i,ElemType e) 
{
	// 在带头结点的循环单链表L的第i个元素之前插入元素e  
	/********** Begin **********/ 
	int j=0;
	LinkList p=L,s;
	if(i<1 || i>ListLength(L)+1)
		return 0;
	while(j<i-1){
		p=p->next;
		j++;
	}
	s=(LinkList)malloc(sizeof(LNnode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return 1;
	/********** End **********/
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	//依次对循环单链表L的每个数据元素调用函数vi()
	LNnode *p=L->next;
   while (p!=L)
   {	
		vi(p->data);
		p=p->next;
   }
   printf("\n");	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

第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,ElemType e) ;
int ListDelete(LinkList L,int i,ElemType &e);
void ListTraverse(LinkList L,void(*vi)(ElemType));
int ListLength(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;
	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=L; // 指针域为L	
}
int ListInsert(LinkList &L,int i,ElemType e) 
{
	// 在带头结点的循环单链表L的第i个元素之前插入元素e  
	int j=1;
   LNnode *pre=L,*p=pre->next,*s;
   if (i<=0) return 0;	//参数i错误返回0
   while (p!=L && j<i)	//查找第i个结点p和其前驱结点pre
   {	
	j++;
	pre=p;
	p=p->next;	//pre、p同步后移一个结点
   }
   if (p==L && i>=j+1) return 0;//参数i>n+1时错误返回0
   else				//成功查找到第i个结点的前驱结点pre
   {	
	s=(LNnode *)malloc(sizeof(LNnode));
	s->data=e;		//创建新结点用于存放元素x
	s->next=pre->next;	//将s结点插入到pre结点之后
	pre->next=s;
	return 1;		//插入运算成功,返回1
   }
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	//依次对循环单链表L的每个数据元素调用函数vi()
	LNnode *p=L->next;
   while (p!=L)
   {	
		vi(p->data);
		p=p->next;
   }
   printf("\n");	
}

// 计算循环链表的长度
int ListLength(LinkList L){
	int i=0;
	LinkList q=L->next;
	while(q!=L){
		q=q->next;
		i++;
	}
	return i;
}


int  ListDelete(LinkList L,int i,ElemType &e) // 不改变L
{ 
	// 在带头结点的循环单链表L中，删除第i个元素，并由e返回其值
	/********** Begin **********/ 
	int j=0;
	LinkList p=L,r;
	if(i<1 || i>ListLength(L))
		return 0;
	while(j<i-1){
		p=p->next;
		j++;
	}
	r=p->next;
	p->next=r->next;
	e=r->data;
	free(r);
	return 1;
	/********** End **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

第3关：将两个循环单链表合并成一个循环单链表

任务描述

本关任务：设有两个带头结点的循环单链表LA=（a1，a2，…，an），LB=（b1，b2，…，bm），编写一个算法，将LA、LB这两个循环单链表合并为一个循环单链表LA=（a1，…，an，b1，…bm），其头指针为LA。

测试说明

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

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

预期输出：
12 47 5 8 6 92 45 63 75 38 24 75 86 9 45 63 12 34

输入说明
第一行输入循环单链表LA的长度M；
第二行输入循环单链表LA的M个整数；
第三行输入循环单链表LB的长度N；
第四行输入循环单链表LB的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));
LinkList   merge_1(LinkList LA,LinkList LB);
int main()               //main() function 
{	
  LinkList A,B;
  ElemType e;
  InitList(A);
  InitList(B);
  int n,m,i;
  cin>>n;
  for(i=1;i<=n;i++)
  { 
    cin>>e;
    ListInsert(A, i, e);
  }
  cin>>m;
  for(i=1;i<=m;i++)
  { 
    cin>>e;
    ListInsert(B, i, e);
  }
  A=merge_1(A,B);
  ListTraverse(A,output) ;   
  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
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=L; // 指针域为L	
}
int ListInsert(LinkList &L,int i,ElemType e) 
{
	// 在带头结点的循环单链表L的第i个元素之前插入元素e  
	int j=1;
   LNnode *pre=L,*p=pre->next,*s;
   if (i<=0) return 0;	//参数i错误返回0
   while (p!=L && j<i)	//查找第i个结点p和其前驱结点pre
   {	
	j++;
	pre=p;
	p=p->next;	//pre、p同步后移一个结点
   }
   if (p==L && i>=j+1) return 0;//参数i>n+1时错误返回0
   else				//成功查找到第i个结点的前驱结点pre
   {	
	s=(LNnode *)malloc(sizeof(LNnode));
	s->data=e;		//创建新结点用于存放元素x
	s->next=pre->next;	//将s结点插入到pre结点之后
	pre->next=s;
	return 1;		//插入运算成功,返回1
   }
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	//依次对循环单链表L的每个数据元素调用函数vi()
	LNnode *p=L->next;
   while (p!=L)
   {	
		vi(p->data);
		p=p->next;
   }
   printf("\n");	
}

LinkList   merge_1(LinkList LA,LinkList LB)
{  
  //将两个采用头指针的循环单链表的首尾连接起来
  /********** Begin **********/ 
  LNnode *p,*q;
  p=LA;q=LB;
  while(p->next != LA) p=p->next;
  while(q->next != LB) q=q->next;
  q->next=LA;
  p->next=LB->next;
  free(LB);
  return LA;
  /********** End **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121