第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; 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 **********/ }
