从排序的链接列表中一次删除“2个重复”元素

Question

void del_duplicated(struct node *first) { 
    struct node *current = listfirst, *prev = listfirst, *tmp; 
    if (current == NULL) 
     printf("Nothing to delete !\n"); 
    while (current != NULL) { 
     /* Keeping traverse the list to find the duplicated elements. */ 
     prev = current; 
     current = current->next; 

     /* for the first and second duplicated node such as 1 1 2 3 5 */ 
     if (prev->data == listfirst->data && current->data == listfirst->data) { 
      listfirst = current->next; 
      printf("LIST FIRST NOW AT %d", listfirst->data); 
     } 
     /* The rest requirement such as 1 2 4 4 5 convert to 1 2 5 */ 
     else if ((prev->next)->data == (current->next)->data) { 
      (prev->next) = (current->next)->next; /*this is point 2 to 5*/ 
      tmp = current;     /*delete the node*/ 
      free(tmp); 
      tmp = current->next; 
      free(tmp); 
     } 
    } 
} 

我有一个链表问题，需要我从列表中删除“2个重复节点”。 这就像1 1 2 3 5转换为2 3 5。 和1 2 4 4 5将被转换为1 2 5。

但我的程序崩溃，因为指针指向一个陌生的地方，我不知道为什么。 （.exe已停止工作） 我认为我的移动指针的逻辑确定，但是.... error like this 我的逻辑附加在我的源代码的注释中。

我是一名在台湾学习计算机科学的新手。 请原谅我的坏英语。

编辑 1小时后。

我在我的两位法官声明中添加了BREAK，并且运行良好。 但我不知道为什么。所有的

void del_duplicated(struct node *first) { 
    struct node *current = listfirst, *prev = listfirst, *tmp, *tmp2; 
    if (current == NULL) 
     printf("Nothing to delete !\n"); 
    while (current != NULL) { 
     /* Keeping traverse the list to find the duplicated elements. */ 
     prev = current; 
     current = current->next; 
     //printf("prev %d,current %d\n", prev->data, current->data); 
     //system("pause"); 
     /* for the first and second duplicated node such as 1 1 2 3 5 */ 
     if (prev->data == listfirst->data && current->data == listfirst->data) { 
      listfirst = current->next; 
      system("pause"); 
      break; 
     } 
     /* The rest requirement such as 1 2 4 4 5 convert to 1 2 5 */ 
     else if (current->data == (current->next)->data) { 
      (prev->next) = (current->next)->next; /* this is point 2 to 5 */ 
      tmp = current->next; 
      tmp2 = current;     /* delete the node */ 
      current = (current->next)->next; 
      free(tmp); 
      free(tmp2); 
      break; 
     } 
    } 
} 

Answer 1

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

typedef struct node NODE; 
struct node{ 
    int   data; 
    NODE  *next; 
    NODE  *prev; 
}; 


NODE * find_node(NODE *first, int value){ 
    while(first){ 
     if(first->data == value) 
      return first; 
     first = first->next; 
    } 
    return NULL; 
} 

NODE* delete_node(NODE **pnd){ 

    NODE *tmp, *nd; 

    if(!pnd || !*pnd) 
     return NULL; 

    nd =  *pnd; 
    tmp =  nd->next; 



    if(nd->next) 
     nd->next->prev = nd->prev; 

    if(nd->prev) 
     nd->prev->next = nd->next; 

    free(nd); 

    *pnd=NULL; 

    return tmp; 
} 


void del_duplicated(NODE **first) { 
    NODE *tmp, 
      *dup, 
      *current=*first; 
    int val; 
    while(current){ 

     dup = find_node(tmp,current->data); // find in next nodes 
     tmp = current->next; 
     val= current->data; 
     while(1){ 
      dup=find_node(tmp,val); 
      if(!dup) break; 

      while(dup){       // delete all occurences 
       if(dup == tmp) 
        tmp = dup->next; 
       delete_node(&dup); 
       dup=find_node(tmp,val); 
      } 
      delete_node(&current);    // delete current one aswell 
     }  
     current=tmp;         

    } 
} 


NODE *new_node(NODE *parent,int value){ 

    NODE *nd = malloc(sizeof(NODE)); 
    nd->prev = parent; 

    if(parent){ 
     nd->next =  parent->next; 
     if(parent->next) 
      parent->next->prev = nd; 

     parent->next = nd; 
    }else 
     nd->next =  NULL; 

    nd->data =   value; 

    return nd; 

} 



void free_nodes(NODE *root){ 
    NODE *tmp; 

    if(root && root->prev){ 
     root->prev->next = NULL; 
    } 
    while(root){ 
     tmp =    root; 
     root =    root->next; 
     free(tmp); 
    } 
} 

void print_nodes(NODE *root, char *text){ 

    if(text) 
     printf("%s:\n", text); 

    while(root){ 
     printf("%d ", root->data); 
     root = root->next; 
    } 
    printf("\n"); 
} 

int main(void){ 
    NODE  *root; 
    root =  new_node(NULL,10); 

    new_node(root, 25); 
    new_node(root, 25); 
    new_node(root, 25); 
    new_node(root, 20); 
    new_node(root, 15); 
    new_node(root, 16); 
    new_node(root, 16); 
    new_node(root, 5); 

    print_nodes(root ,"\nWith duplicated items"); 
    del_duplicated(&root); 
    print_nodes(root ,"\nDuplicated items removed"); 

    free_nodes(root); 
    return 0; 
} 

Answer 2

首先，你必须采用参数列表你的函数del_duplicated的， 使得它能够删除第一个元素了。使用struct node **first而不是 struct node *first。要删除2个相等的元素，使用一个指向元素的指针并前进，直到元素的数据与其后继数据相等。因为你有一个指向元素的指针，所以你可以很容易地删除元素及其后继者。

void del_duplicated(struct node **first) 
{ 
    struct node **current = first; 

    if (current == NULL || *current == NULL) 
     return; 

    // One step forward as long as there is a a successor node 
    // and data of node and data of successor node are not equal 
    while ((*current)->next != NULL && 
      (*current)->data != (*current)->next->data) 
    { 
     current = &((*current)->next); 
    } 

    if ((*current)->next != NULL) 
    { 
     if ((*current)->prev != NULL) 
      (*current)->prev->next = (*current)->next->next; // successor of predecesor is successor of successor 
     if ((*current)->next->next != NULL) 
      (*current)->next->next->prev = (*current)->prev; // predecesor of successor of successor is predecesor 

     // delete this node and successor node 
     free((*current)->next); 
     free(*current); 
     *current = NULL // may be it was first 
    } 
}