单链表的应用1（去重）

水深无声 2022-07-25 20:26 109阅读 0赞

题目要求：在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    typedef struct node
    {
        int data;
        struct node*next;
    } Linklist;
    
    Linklist* Create()
    {
        Linklist *head;
        head=(Linklist*)malloc(sizeof(Linklist));
        if(head!=NULL)
        {
            head->next=NULL;
            return head;
        }
        else
            return NULL;
    }
    
    int InSert(Linklist *head,int e)
    {
        Linklist *p;
        Linklist *q=head;
        p=(Linklist*)malloc(sizeof(Linklist));
        if(p!=NULL)
        {
            p->data=e;
            p->next=NULL;
            //cout<<"!!!"<<endl;
            while(q->next!=NULL)
            {
                q=q->next;
            }
            q->next=p;
            return 1;
    //        if(head->next==NULL)
    //        {
    //            head->next=p;
    //            return 1;
    //        }
    //        else
    //        {
    //            Linklist *q=head;
    //            while(q!=NULL)
    //            {
    //                q=q->next;
    //            }
    //            q->next=p;
    //            return 1;
    //        }
        }
        return 0;
    }
    
    void DeletAgain(Linklist *head)
    {
        Linklist *p=head->next;
        Linklist *q=p->next;
        while(q!=NULL)
        {
            if(p->data == q->data)
            {
                Linklist *qq=q;
                q=q->next;
                p->next=q;
                free(qq);
            }
            else
            {
                p=p->next;
                q=q->next;
            }
        }
    }
    
    void Output(Linklist *head)
    {
        Linklist *p;
        p=head->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    
    void FreeLink(Linklist *head)
    {
        Linklist *p,*q;
        p=head;
        q=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            free(q);
        }
    }
    
    int main()
    {
        struct node *head;
        int n;
        int e,flag=0;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==-1)
                break;
            else
            {
                head=Create();
                if(head!=NULL)
                {
                    for(int i=0; i<n; i++)
                    {
                        scanf("%d",&e);
                        flag=InSert(head,e);
                        if(flag==0)
                        {
                            cout<<" Insert Fail "<<endl;
                            break;
                        }
                    }
                    if(flag==1)
                    {
                        Output(head);
                        DeletAgain(head);
                        Output(head);
                    }
                    if(flag==0)
                    {
                        cout<<" Insert Fail "<<endl;
                        break;
                    }
                    FreeLink(head);
                }
                else
                {
                    cout<<" Memory Full"<<endl;
                }
            }
        }
        return 0;
    }