小贝子编程

c-我有一个链表，我想删除重复的值



因此，我创建了一个代码，它在其中创建一个具有5个值的链表。我想知道删除这些值的重复项并在没有重复项的情况下再次打印链表的最佳方法是什么。

#include <stdio.h>
#include <stdlib.h>
/* self-referential structure*/
struct studentID{
int value;          //a data member which is an integer
struct studentID *next;         //a data member which is a pointer to next node
};

typedef struct studentID STUDENTID;     //creating a nickname for struct studentID as STUDENTID
typedef STUDENTID *STUDENTIDPtr;        //creating a nickname for STUDENTID as STUDENTIDPtr

//Global variables
STUDENTIDPtr previousPtr;           //pointer to previous node in list
STUDENTIDPtr currentPtr;            //pointer to current node in list

void printList(STUDENTIDPtr currentPtr){

while (currentPtr != NULL){         //while not the end of the list
printf("%d -> ", currentPtr->value);
currentPtr = currentPtr ->next;
}
}

int main(){
STUDENTIDPtr newPtr1;           //creating a pointer to create a new node
STUDENTIDPtr newPtr2;           //creating a pointer to create a new node
STUDENTIDPtr newPtr3;           //creating a pointer to create a new node
STUDENTIDPtr newPtr4;           //creating a pointer to create a new node
STUDENTIDPtr newPtr5;           //creating a pointer to create a new node

//creation of the first node
newPtr1 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr2 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr3 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr4 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr5 = malloc(sizeof(STUDENTID));            //This is when a node is created

newPtr1 -> value = 4; // assign data in first node 
newPtr1 -> next = newPtr2;

newPtr2 -> value = 4; // assign data in first node 
newPtr2 -> next = newPtr3;

newPtr3 -> value = 5; // assign data in first node 
newPtr3 -> next = newPtr4;

newPtr4 -> value = 2; // assign data in first node 
newPtr4 -> next = newPtr5;

newPtr5 -> value = 1; // assign data in first node 
newPtr5 -> next = NULL;

currentPtr = newPtr1;
printList(newPtr1);

return 0;
}

使用if-else并遍历每个链表会很容易吗？或者有更好的方法吗？

现在会想到两种方法，使用哪种方法取决于您的具体情况，以及您是否希望保留元素的原始顺序。

第一种方法：

使用双循环，一次拾取一个节点。然后在该节点之后迭代列表，如果发现重复，请移除。重复拾取节点，直到对整个列表进行迭代。

For every node of the list
For every next_node after node
If next_node.value == node.value
Remove that next_node

这种方法保留了元素的原始顺序。

我认为这种方法是你已经想到的。我建议你从这个开始。

示例：

1->2->3->4->1

我将从第一个节点(1)开始，检查第二个节点、第三个节点、最后一个节点，到目前为止什么都没有，没有发现重复的节点。我现在检查第五个节点，它也有值1(发现重复！)，所以我删除了它。

现在列表如下：

1->2->3->4

现在我正在查找第二个节点的重复项(我在上一次遍历中检查了第一个节点)。我检查了3个，我检查了4个，没有发现重复的。列表保持不变。

现在我正在寻找第三个节点的副本。我检查了4次，没有发现重复的。列表保持不变。

现在我正在寻找第四个节点的副本。下一个节点为NULL，这意味着第四个节点是最后一个节点(因为我们在第一次遍历中删除了第五个节点，作为1的副本)。没有什么可检查的，列表保持不变：

1->2->3->4

观察一下，对于我想检查是否存在重复的每个节点，我是如何遍历列表直到列表结束的。因此，对于每个节点，我都要进行O(N)遍历，其中N是列表的大小。

我有多少个节点？N

因此，这种方法的时间复杂度是N*O(N)=O(N2)

我强烈建议你自己尝试一下，然后练习。完成后，您可以阅读"从未排序的列表中删除重复项"来检查您的解决方案。

第二种方法：

对列表进行排序，现在列表将把重复的值分组在一起。因此，如果存在当前节点的副本，它将是其下一个节点。如果它是重复的，请删除下一个节点。

现在，如果存在当前节点的副本，它将是其下一个节点。因此，执行上面的操作，直到下一个节点是而不是当前节点的副本。

然后，将下一个节点设为当前节点，并执行相同的过程。

Sort list
current_node = head_node
While current_node != NULL
If current_node.value == current_node.next.value
Remove current_node.next
Else
current_node = current_node.next

这种方法不保留元素的原始顺序。

相同示例：

1->2->3->4->1

对列表进行排序：

1->1->2->3->4

我从1开始。我检查它的下一个节点，它也是1，发现了一个重复！删除下一个节点。现在的列表是：

1->2->3->4

当前节点仍然是1。我检查它的下一个节点，它是2。没有重复。列表保持不变。将下一个节点设置为当前节点。

当前节点为2。检查它的下一个节点，它是3，而不是重复的。列表保持不变。将下一个节点设置为当前节点。

当前节点为3。检查它的下一个节点，它是4，而不是重复的。列表保持不变。将下一个节点设置为当前节点。

当前节点为4。它没有下一个节点，没有什么可检查的，我完成了。列表保持不变：

1->2->3->4

注意，对于每个节点，我只检查它的下一个节点。然后，我继续检查最后一个下一个节点。这就是O(N)。

然而，我不得不对列表进行排序，以确保重复项被分组。可以用O(NlogN)对列表进行排序。

时间复杂度为O(NlogN)+O(N)=O(Nlog N)。

我在C中使用了"合并排序"对列表进行排序。另外还有"从排序列表中删除重复项"作为另一种解释。

在发布的代码中，您将"手动"添加列表前面的每个节点，因此第一步是创建一个这样做的函数。

然后，您可以创建另一个函数，在列表中添加一个节点，使其保持排序。它将遍历列表，找到正确的位置，并且只有在节点不存在的情况下才会添加另一个具有相同值的节点。

现在，您可以遍历原始列表(未排序的列表)，对于每个节点，尝试将其副本添加到排序列表中。如果已经存在，请从原始列表中删除该节点，否则将副本添加到排序列表中。

最后，您将看到两个独特元素的列表，其中一个已排序。

不要忘记创建一个函数来释放分配的内存。

您的意思似乎不仅仅是删除列表中相邻的重复值。

您需要的是编写一个函数，该函数将通过引用接受列表的头节点。函数可以返回删除的节点数。

请注意，声明全局变量是个坏主意

//Global variables
STUDENTIDPtr previousPtr;           //pointer to previous node in list
STUDENTIDPtr currentPtr;            //pointer to current node in list

此外，这些都是多余的。

这个typedef可能会混淆代码的读者

typedef STUDENTID *STUDENTIDPtr;

您还可以编写一个单独的函数，将一个节点添加到列表中。最初，您可以编写函数，使列表中的节点按值排序。

至于删除重复值的函数，它可以如下所示：iy如下面的演示程序所示。调查一下。

#include <stdio.h>
#include <stdlib.h>
/* self-referential structure*/
struct studentID{
int value;          //a data member which is an integer
struct studentID *next;         //a data member which is a pointer to next node
};

typedef struct studentID STUDENTID;     //creating a nickname for struct studentID as STUDENTID
typedef STUDENTID *STUDENTIDPtr;  
size_t remove_duplicates( STUDENTIDPtr *head )
{
size_t n = 0;
for ( ; *head != NULL; head = &( *head )->next )
{
for ( STUDENTIDPtr *next = &( *head )->next; *next != NULL; )
{
if ( ( *head )->value == ( *next )->value )
{
STUDENTIDPtr tmp = *next;
*next = ( *next )->next;
free( tmp );
++n;
}
else
{
next = &( *next )->next;
}
}
}
return n;
}
void printList(STUDENTIDPtr currentPtr){

for ( ; currentPtr != NULL; currentPtr = currentPtr ->next )
{
printf("%d -> ", currentPtr->value);
}
puts( "NULL" );
}
int main(void) 
{
STUDENTIDPtr newPtr1;           //creating a pointer to create a new node
STUDENTIDPtr newPtr2;           //creating a pointer to create a new node
STUDENTIDPtr newPtr3;           //creating a pointer to create a new node
STUDENTIDPtr newPtr4;           //creating a pointer to create a new node
STUDENTIDPtr newPtr5;           //creating a pointer to create a new node

//creation of the first node
newPtr1 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr2 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr3 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr4 = malloc(sizeof(STUDENTID));            //This is when a node is created
newPtr5 = malloc(sizeof(STUDENTID));            //This is when a node is created

newPtr1 -> value = 4; // assign data in first node 
newPtr1 -> next = newPtr2;

newPtr2 -> value = 4; // assign data in first node 
newPtr2 -> next = newPtr3;

newPtr3 -> value = 5; // assign data in first node 
newPtr3 -> next = newPtr4;

newPtr4 -> value = 2; // assign data in first node 
newPtr4 -> next = newPtr5;

newPtr5 -> value = 1; // assign data in first node 
newPtr5 -> next = NULL;

printList( newPtr1 );
size_t n = remove_duplicates( &newPtr1 );
printf( "There are removed %zu elementsn", n );
printList( newPtr1 );
return 0;
}

程序输出可能看起来像

4 -> 4 -> 5 -> 2 -> 1 -> NULL
There are removed 1 elements
4 -> 5 -> 2 -> 1 -> NULL

请记住，您还需要编写一个函数，该函数将为列表释放所有分配的内存。

以下解决方案仅适用于足够小的整数值，而不是非常大的整数值。我们在这里可以做的是取另一个数组作为关联容器。

  • 取一个数组。将该数组初始化为0
  • 开始遍历链表
  • if(arr[node->data]==0)；然后递增arr[节点->数据]。这将使其为1，标记一次出现
  • 否则如果(arr[node->data]==1)；然后删除该节点，因为这意味着当前节点已经包含以前遇到的整数

如果您想扩大规模，可以实现基于哈希或BST的DS，类似于cpp映射，作为关联容器。

如果你想要一个通用的算法，我建议你首先按照以下几行写一个暴力逻辑——

  • 遍历链接列表
  • 如果第一次找到"数据"，则忽略并继续
  • 如果下次找到"数据"，请调用删除逻辑

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium