题目:在一个递增有序的线性表中,有数值相同的元素存在。若存储方式为单链表,设计算法去掉数值相同的元素,使表中不再有重复的元素,如(7,10,10,21,30,42,42,42,51,70)将其变为(7,10,21,30,42,51,70)。
算法思想:已知单链表递增有序,所以值相同的结点一定是相邻的,可以判断是否相同,然后覆盖掉相同结点即可。
代码:
void Delete_same(Linklist &L){
LNode *pre=L->next; // 初始化指针
LNode *p=pre->next; // p为工作指针,用来遍历
while(p!-NULL){
if(pre->data==p->data){ // 找到重复的点
pre->next=p->next; // 删除这个点,其实是通过指针移动进行对相等值的覆盖而达到删除的效果
free(p);
p=pre->next;
}
else{ // 不相等,指针就向后移动一位,然后继续比较
pre=p;
p=p->next;
}
}
}