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

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

任务描述

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

相关知识

单链表结点类型定义如下：

typedef struct LNode // 结点类型定义
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; // LinkList为结构指针类型
typedef int ElemType;
数据元素的类型ElemType为int类型。

在有序单链表中删除重复的结点，重复的元素必然相邻，删除算法的关键步骤如下：

只要单链表不为空，定义3个结点指针：ppre、pcur、pdel。pcur作为活动指针，初始指向第一个数据元素的结点，而ppre初始指向pcur的前驱结点，pdel用于指向待删除的结点。
用一个循环控制ppre和pcur向后移动，当ppre指向的结点值和pcur指向的结点值相等，那么ppre的指向的位置保持不动，将pcur的指向先传递给pdel，然后pcur向后移一个位置，再将ppre指向的结点作为pcur指向的结点的前驱，这两个结点再次保持相邻，最后释放pdel指向结点的空间，达到删除多余结点的效果。如果后面还有和ppre指向的结点值相同的结点，便通过循环重复执行这些操作。循环执行的过程中ppre就相当于一个基准，不会发生移动。只有当ppre指向的结点值和此时pcur指向的结点值不相等时，ppre才会向后移动一个位置，再将pcur指向ppre指向位置的下一个位置。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表按照值的大小插入函数的定义，具体要求如下：

int ListSortInsert(LinkList &L,ElemType e,int(*compare)(ElemType, ElemType) ); //带头结点的单链表L，其结点存储的数据是递增有序的，将e插入L，并保持该单链表的有序性

说明：

用函数指针equals来实现调用判断ElemType类型数据元素是否相等的函数。
用函数指针compare来实现调用ElemType类型数据元素进行比较大小的函数。
调用本函数将一个有重复数据的有序单链表，改造成所有元素的值均不相同的有序单链表。

测试说明

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

测试输入：
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 
#include 
#include 
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
154