有序单链表的插入删除操作

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

任务描述

本关任务：已知带头结点的单链表中的元素以值递增有序排列，要求实现一个算法，在单链表中插入一个新整数，并保持该单链表仍然以值递增有序。

测试说明

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

测试输入：
5
12 47 5 8 69

预期输出：
5 8 12 47 69

输入说明
第一行输入单链表的数据元素的个数N；
第二行输入单链表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);
int comp(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void InitList(LinkList &L);
int ListSortInsert (LinkList &L, ElemType e,int (*comp)(ElemType,ElemType));
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;
         ListSortInsert(A, e,comp);
      }
	 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;
}
int comp(ElemType a,ElemType b)
{
	if(a>b)
		return  1;
	else
		if(a<b)
			return  -1;
	else	return  0;
}


/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 
	// 操作结果：构造一个空的单链表L
	/********** Begin **********/ 
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空
	/********** 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 **********/
}

int ListSortInsert (LinkList &L, ElemType e,int (*comp)(ElemType,ElemType))
{ 
	/********** Begin **********/ 
	LinkList s,p,q;
	s=(LinkList)malloc(sizeof(LNnode));
	if(!s) return 0;
	s->data=e;
	if(L==NULL || comp(e,L->data)==-1){
		s->next=L;
		L=s;
	}else{
		q=L;
		p=q->next;
		while(p!=NULL && comp(e,p->data)==1){
			q=p;
			p=p->next;
		}
		s->next=p;
		q->next=s;
		
	}
	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

第2关：有序单链表中值相同的多余结点的删除操作

任务描述

本关任务：已知单链表中的元素以值递增有序排列，试写一高效的算法，删除表中所有值相同的多余元素，使得操作后的单链表中所有元素的值均不相同，同时释放被删结点空间，例如初始单链表为：（1 2 2 2 3 3 4 4 4 4 5 6 6） ，执行删除算法后单链表为：（1 2 3 4 5 6）。

测试说明

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

测试输入：
14
1 1 2 2 2 3 3 4 4 4 4 5 6 6

预期输出：
1 1 2 2 2 3 3 4 4 4 4 5 6 6
1 2 3 4 5 6

输入说明
第一行输入有序单链表的数据元素的个数N；
第二行输入N个有序有重复值的整数。

输出说明
第一行输出初始的有重复值的有序单链表；
第二行输出所有元素的值均不相同的有序单链表。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;


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

void InitList(LinkList &L);
int ListSortInsert (LinkList &L, ElemType e,int (*compare)(ElemType,ElemType));
void ListTraverse(LinkList L,void(*vi)(ElemType));
void ListDeleteSameNode(LinkList &L,int (*equals)(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;
         ListSortInsert(A, e,comp);
      }
	ListTraverse(A,output) ;
 	ListDeleteSameNode(A, equals);
 	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;
}
int comp(ElemType a,ElemType b)
{
	if(a>b)
		return  1;
	else
		if(a<b)
			return  -1;
		else
		return  0;
}


/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 
	// 操作结果：构造一个空的单链表L
	/********** Begin **********/ 
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空
	/********** 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 **********/
}

int ListSortInsert (LinkList &L, ElemType e,int (*compare)(ElemType,ElemType))
{ 	// 在带头结点的有序单链线性表L中插入元素e后仍然有序
	/********** Begin **********/ 
	 LNnode *curPtr ,*prePtr;
	int flag = 0;//检测是否成功插入；
	 LNnode *insPtr = (LNnode *)malloc(sizeof(LNnode));
	if(!insPtr) // 存储分配失败
		return 0;
	insPtr->data = e;
	curPtr = L->next;
	prePtr = L;
	while(curPtr)
	{
		if(compare(curPtr->data,  insPtr->data) > 0 )
		{
			prePtr->next = insPtr;
			insPtr->next = curPtr;
			flag = 1;
			break;
		}
		else
		{
			curPtr = curPtr->next;
			prePtr = prePtr->next;
		}
	}
	if(flag == 0)
	{
		prePtr->next = insPtr;
		insPtr->next = NULL;
	}
	return 1;
	/********** End **********/
}

void ListDeleteSameNode(LinkList &L,int (*equals)(ElemType,ElemType) )
{   // 在带头结点的有序单链线性表L中删除值相同的多余结点
	/********** Begin **********/ 
	LinkList p,q,pre;
	p=L;
	while(p){
		pre=p;
		p=p->next;
		if(p && equals(p->data,pre->data)==1){
			pre->next=p->next;
			q=p;
			p=pre;
			free(q);
		}
	}
	/********** 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
146
147
148
149
150
151
152
153