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

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

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

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

1 #include
      
         2 #include
       
          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("请按输入元素：\n"); 60     for(i=0; i
        
         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\n"); 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("\n"); 92 } 93 int main() 94 { 95     LinkList L; 96     int Number; 97     InitLinkList(&L); 98     printf("请输入元素的个数：\n"); 99     scanf("%d",&Number);100     Create(&L,Number);101     printf("原先的元素有\n");102     Print(&L);103     Unique(&L);104     printf("去重后的元素有\n");105     Print(&L);106     return 0;107 }
        
       
      

更改后的去重背调函数：

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             else18             {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)