链表去重

数据结构上机实验上的一道题。

设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。

提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。

解题思路：按照提示的意思就是一个双重循环的查找，像是暴力算法从母串中查找子串？我最开始就直接使用编写好的删除函数套在双重循环里面，这样做是可以的，但是时间复杂度有点高，O（n^3）!!!

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct Node
  4 {
  5     int data;
  6     struct Node * next;
  7 } Node,*LinkList;
  8 int Delete(LinkList * L,int Location)
  9 {
 10     LinkList q,p;
 11     int counts=0;
 12     int k=Location+1;
 13     q=(*L);
 14     p=(*L)->next;
 15     while(p->next)
 16     {
 17         q=q->next;
 18         p=p->next;
 19         counts++;
 20         if(counts==Location)
 21         {
 22             q->next=p->next;
 23         }
 24     }
 25     return 1;
 26 }
 27 int Unique(LinkList *L)
 28 {
 29     LinkList p,q;
 30     int counts=1;
 31     int ans=0;
 32     p=(*L)->next;
 33     while(p)
 34     {
 35         q=p->next;
 36         counts=ans+1;;
 37         while(q)
 38         {
 39             if(p->data==q->data)
 40             {
 41                 Delete(L,counts);
 42             }
 43             else
 44             {
 45                 counts++;
 46             }
 47             q=q->next;
 48         }
 49         p=p->next;
 50         ans++;
 51     }
 52     return 1;
 53 }
 54 int Create(LinkList *L,int n)
 55 {
 56     LinkList p,q;
 57     int Elem,i;
 58     q=(*L);
 59     printf("请按输入元素：
");
 60     for(i=0; i<n; i++)
 61     {
 62         p=(LinkList)malloc(sizeof(Node));
 63         scanf("%d",&Elem);
 64         p->data=Elem;
 65         q->next=p;
 66         q=p;
 67     }
 68     p->next=NULL;
 69     return 1;
 70 }
 71 int InitLinkList(LinkList * L)
 72 {
 73     (*L)=(LinkList)malloc(sizeof(Node));
 74     if((*L)==NULL)
 75     {
 76         printf("ERROR
");
 77         return 0;
 78     }
 79     (*L)->next=NULL;
 80     return 1;
 81 }
 82 void Print(LinkList *L)
 83 {
 84     LinkList p;
 85     p=(*L)->next;
 86     while(p)
 87     {
 88         printf("%d ",p->data);
 89         p=p->next;
 90     }
 91     printf("
");
 92 }
 93 int main()
 94 {
 95     LinkList L;
 96     int Number;
 97     InitLinkList(&L);
 98     printf("请输入元素的个数：
");
 99     scanf("%d",&Number);
100     Create(&L,Number);
101     printf("原先的元素有
");
102     Print(&L);
103     Unique(&L);
104     printf("去重后的元素有
");
105     Print(&L);
106     return 0;
107 }

View Code

更改后的去重背调函数：

 1 int Unique(LinkList *L)
 2 {
 3     LinkList p,q,k;
 4     q=p=(*L)->next;
 5     while(p->next)///查找和节点p重复的节点，重复则删除。
 6     {
 7         q=p;
 8         k=q->next;
 9         while(k)
10         {
11             if(k->data==p->data)///重复判断
12             {
13                 q->next=k->next;///从链表里删除
14                 free(k); ///实际删除节点，释放内存
15                 k=q->next; ///保持k=q->next;
16             }
17             else
18             {
19                 q=k;
20                 k=k->next;
21             }
22         }
23         if(p->next)
24         {
25             p=p->next;
26         }
27     }
28     return 1;
29 }

能够将时间复杂度将到O(n^2)