1
我一直在處理這個問題的時間超過了我現在要承認的時間，並且這讓我發瘋了！給定一個簡單的鏈表，比如只存儲一個整數（data），除了指向下一個節點（next）的指針之外，我想要一個算法去除沒有排序或依賴輔助函數的重複項。C：刪除未排序鏈接列表中的重複項
以前的問題已經被問到了Java中未被排序的鏈接列表，它們利用了Java提供的幫助函數。這與C沒有使用輔助函數是嚴格相關的。
我對代碼進行了修改，並且已經將它用於某些情況，但不是全部。下面是一個完整的，可覈查的例子 - 我已經包括push()函數來創建一個鏈表，並與測試用例main()，但我的問題是關於在removeDuplicates()單獨的邏輯：
#include <stdlib.h>
#include <stdio.h>
struct node {
int data;
struct node *next;
};
void push(struct node **headRef, int data) {
struct node *newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = *headRef;
*headRef = newNode;
}
void removeDuplicates(struct node **head) {
struct node *currentNode = *head; //The node we compare other nodes against
struct node *runningNode = (*head)->next; //The node we are comparing to
struct node *runningNodePrev = *head; //The node before the node we are comparing to
struct node *runningNodeNext = (*head)->next->next; // The node after the node we are comparing to
int count = -1;
while (currentNode->next != NULL) { //Ensure we are not looking at the last node -- cannot have comparisons past this node
count++;
if (count) {
//'Base Position'
currentNode = currentNode->next;
runningNodePrev = currentNode;
runningNode = currentNode->next;
runningNodeNext = runningNode->next;
}
printf("\nChecking for a match with %d ... \n", currentNode->data);
while (runningNode != NULL) { //Compare each node in the list until we reach the end of the list
printf("Inspecting next adjacent node ... \n");
if (runningNode->data == currentNode->data) {//If a duplicate is found
printf("Found match ... ");
//Ensure link is maintained before removing duplicate node
if (currentNode == runningNodePrev)
currentNode->next = runningNodeNext;
runningNodePrev->next = runningNodeNext;
free(runningNode);//Delete duplicate node
printf("Deleted duplicate.\n");
}
runningNode = runningNodeNext;//Continue searching for duplicates at the first unchecked node
runningNodeNext = runningNodeNext->next;//Move running node leader up the list.
}
}
}
int main(void) {
struct node *t1 = NULL;
struct node *t2 = NULL;
struct node *t4 = NULL;
struct node *t5 = NULL;
push(&t1, 1);
push(&t1, 1);
push(&t1, 1);
push(&t1, 1);
push(&t2, 6);
push(&t2, 1);
push(&t2, 2);
push(&t2, 3);
push(&t2, 4);
push(&t2, 5);
push(&t2, 6);
push(&t4, 4);
push(&t4, 2);
push(&t4, 3);
push(&t4, 2);
push(&t4, 1);
push(&t5, 0);
push(&t5, 0);
push(&t5, 1);
printf("Testing removeDuplicates()...\n");
printf("Case 1: Calling removeDuplicates({1,0,0}).\n");
printf("Expected result: { 1 0 }\n");
printf("Actual result: { ");
removeDuplicates(&t5);
ptr = t5;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("}\n");
printf("Case 2: Calling removeDuplicates({1,2,3,2,4}).\n");
printf("Expected result: { 1 2 3 4 }\n");
printf("Actual result: { ");
removeDuplicates(&t4);
ptr = t4;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("}\n");
printf("Case 3: Calling removeDuplicates({6,5,4,3,2,1,6}).\n");
printf("Expected result: { 6 5 4 3 2 1 }\n");
printf("Actual result: { ");
removeDuplicates(&t2);
ptr = t2;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("}\n");
printf("Case 4: Calling removeDuplicates({1,1,1,1}).\n");
printf("Expected result: { 1 }\n");
printf("Actual result: { ");
removeDuplicates(&t1);
ptr = t1;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("}\n");
}
我還包括描述邏輯的圖片，如果它不清楚我在做什麼：http://imgur.com/DbnBOq2
有什麼不對輔助功能？ –
爲什麼不修改'push'以*不插入*重複？ – StoryTeller
你可以使用散列表檢查重複項......然後你不需要檢查整個列表 – Thomas