第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 <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;elsereturn  0;
}
int comp(ElemType a,ElemType b)
{if(a>b)return  1;elseif(a<b)return  -1;elsereturn  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 **********/
}