第1章第2节练习题5 删除重复结点

问题描述

在一个递增有序的单链表中，有数据相同的结点存在。试设计一个算法，删除数值相同的结点，使表中不再有重复的结点。
例如（7,10,10,21,30,42,42,42,51,70）将变作（7,10,21,30,42,51,70）

算法思想

考虑到本题中的单链表逻辑上有序，因此若存在数据域相同的结点那么它们必定是连续的。本算法中使用指针p完成对单链表的一次遍历，指针pre指向指针p所指结点的前驱结点。如果pre->data与p->data相等，那么删除指针p所指向的结点，p后移一位；如果继续相等则步骤同上。

算法描述

void DelRrepeat(LNode *head)
{
    LNode *pre=head;
    LNode *p=head->next;
while(p){
while(pre->data==p->data){
            pre->next=p->next;
free(p);
            p=pre->next;
        }
        pre=p;
        p=p->next;
    }
}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
struct LNode *next;
}LNode, *LinkList;

LinkList CreatList(LNode*);
void DelRrepeat(LNode*);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head->next=NULL;
    head=CreatList(head);
    Print(head);

    DelRrepeat(head);

    Print(head);
return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode *head)
{
    LNode *r=head;
    LNode *s;
    ElemType x;
scanf("%d",&x);
while(x!=999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
scanf("%d",&x);
    }
    r->next=NULL;
return head;
}
//查找并删除重复值
void DelRrepeat(LNode *head)
{
    LNode *pre=head;
    LNode *p=head->next;
while(p){
while(pre->data==p->data){
            pre->next=p->next;
free(p);
            p=pre->next;
        }
        pre=p;
        p=p->next;
    }
}
//打印所结点
void Print(LNode *head)
{
    LNode *p=head->next;
while(p){
printf("%4d",p->data);
        p=p->next;
    }
printf("\n");
}