我需要一些幫助來洗掉 C 中雙向鏈表中的唯一字符。所以這是我嘗試實作的邏輯：我計算了雙向鏈表中每個字符的出現次數。如果它的出現是1次，那么它是唯一的元素，需要洗掉。我將對所有元素重復該程序。但是我在 remove_unique_dll() 函式中的代碼不能正常作業，請幫我修復它。這是我的代碼-
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char data;
struct node *next;
struct node *prev;
};
struct node *head, *tail = NULL; //Represent the head and tail of the doubly linked list
int len;
void addNode(char data)
{
struct node *newNode = (struct node*) malloc(sizeof(struct node)); //Create new node
newNode->data = data;
if (head == NULL)
{ //If dll is empty
head = tail = newNode; //Both head and tail will point to newNode
head->prev = NULL; //head's previous will point to NULL
tail->next = NULL; //tail's next will point to NULL, as it is the last node of the list
}
else
{
tail->next = newNode; //newNode will be added after tail such that tail's next points to newNode
newNode->prev = tail; //newNode's previous will point to tail
tail = newNode; //newNode will become new tail
tail->next = NULL; //As it is last node, tail's next will point to NULL
}
}
void remove_unique_dll()
{
struct node *current = head;
struct node *next;
struct node *prev;
int cnt;
while (current != NULL)
{
next = current->next;
cnt = 1;
//printf("!%c ",next->data);
while (next != NULL)
{
if (next->data == current->data)
{
cnt = 1;
next = next->next;
}
else
next = next->next;
//printf("@%c %d %c\n",next->data,cnt,current->data);
}
if (cnt == 1)
{
prev = current->prev;
//printf("@%c %d",prev->data,cnt);
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
if (next == NULL)
{
tail = prev;
}
else
{
next->prev = prev;
}
}
current = current->next;
//printf("#%c ",current->data);
}
head = current;
}
void display()
{
struct node *current = head; //head the global one
while (current != NULL)
{
printf("%c<->", current->data); //Prints each node by incrementing pointer.
current = current->next;
}
printf("NULL\n");
}
int main()
{
char s[100];
int i;
printf("Enter string: ");
scanf("%s", s);
len = strlen(s);
for (i = 0; i < len; i )
{
addNode(s[i]);
}
printf("Doubly linked list: \n");
display();
remove_unique_dll();
printf("Doubly linked list after removing unique elements: \n");
display();
return 0;
}
輸出是這樣的-
如果您取消注釋 remove_unique_dll() 中的 printf() 陳述句，您會注意到內部 while 回圈結束后沒有執行內部 while 回圈下面的代碼。這里有什么問題，解決方案是什么？
樣本輸入 - aacb
預期輸出 - a<->a<->NULL
uj5u.com熱心網友回復：
一些問題：
你不應該
head = current在最后分配，因為那時current是NULL您在洗掉部分使用的
next不是 的后繼current，所以這會產生錯誤的鏈接當您在串列中前進時，每個值都會在某個時候被視為唯一的：當它是最后一次出現時，您將不再找到重復項，因為您的邏輯只向前看，而不是向后看。
當你洗掉一個節點時，你應該釋放它的記憶體。
不是一個大問題，但沒有理由真正計算重復的數量。一旦找到第一個副本，就沒有理由再尋找另一個了。
您應該真正將演算法的不同步驟隔離在單獨的函式中，這樣您就可以分別除錯和測驗每個功能，并更好地理解您的代碼。
此外，要檢查重復項，您可能需要使用以下事實：如果串列中第一次出現的值與該值最后一次出現的節點相同，那么您知道它是唯一的。由于您的串列是雙重鏈接的，因此您可以使用向后遍歷來查找最后一次出現（并使用前向遍歷來查找第一次出現）。
這是一些建議的代碼：
struct node* findFirstNode(char data) {
struct node *current = head;
while (current != NULL && current->data != data) {
current = current->next;
}
return current;
}
struct node* findLastNode(char data) {
struct node *current = tail;
while (current != NULL && current->data != data) {
current = current->prev;
}
return current;
}
void removeNode(struct node *current) {
if (current->prev == NULL) {
head = current->next;
} else {
current->prev->next = current->next;
}
if (current->next == NULL) {
tail = current->prev;
} else {
current->next->prev = current->prev;
}
free(current);
}
void remove_unique_dll() {
struct node *current = head;
struct node *next;
while (current != NULL)
{
next = current->next;
if (findFirstNode(current->data) == findLastNode(current->data)) {
removeNode(current);
}
current = next;
}
}
uj5u.com熱心網友回復：
你至少有三個錯誤。
在計算一個專案的出現次數后，您可以next在幾個地方使用。但是，next已用于遍歷串列。它被移到最后，現在是一個空指標。您可以使用 重置它，next = current->next;也可以將使用的位置更改next為current->next。
最后remove_unique_dll，你有head=current;. 目前沒有理由更新head。每當從串列中洗掉第一個節點時，remove_unique_dll更新head. 所以它已經更新了。洗掉該行head=current;。
這將留下代碼，洗掉每個專案只出現一次。但是，根據您的示例輸出，您希望保留多次出現的專案。為此，您需要重新考慮remove_unique_dll決定洗掉哪些節點的邏輯。當它看到第一個a時，它會掃描串列的其余部分并看到第二個，因此它不會洗掉第一個a。當它看到第二個a時，它會掃描串列的其余部分并且沒有看到重復項，因此它會洗掉第二個a。你需要改變它。
uj5u.com熱心網友回復：
讓我們逐步考慮您的代碼。
您似乎認為在此宣告中
struct node *head, *tail = NULL; //Represent the head and tail of the doubly linked list
兩個指標head和tail都由 顯式初始化NULL。實際上只有指標tail被顯式初始化NULL。head僅由于將宣告置于檔案范圍內，該指標被隱式初始化為空指標。它將這樣的宣告放在塊范圍內，然后指標head將被取消初始化。
相反，你應該寫
struct node *head = NULL, *tail = NULL; //Represent the head and tail of the doubly linked list
當函式依賴于這些全域變數時，這也是一種非常糟糕的方法。在這種情況下，您將無法在一個程式中擁有多個串列。
還有len僅在 main 中用作全域變數的變數的宣告
int len;
也是個壞主意。而且這個宣告是多余的。
您需要再定義一個結構，該結構將包含指標head并tail作為資料成員，例如
struct list
{
struct node *head;
struct node *tail;
};
addNode當無法分配新節點時，該函式可以呼叫未定義的行為
void addNode(char data)
{
struct node *newNode = (struct node*) malloc(sizeof(struct node)); //Create new node
//...
您應該檢查一個節點是否分配成功，只有在這種情況下才更改其資料成員。并且您應該報告呼叫者是否創建了節點。
所以該函式應該回傳一個整數，它將報告成功或失敗。
remove_unique_dll在這個while回圈之后的函式中
while (next != NULL)
{
if (next->data == current->data)
{
cnt = 1;
next = next->next;
}
else
next = next->next;
//printf("@%c %d %c\n",next->data,cnt,current->data);
}
如果cnt等于1
if (cnt == 1)
//..
那么指標next等于NULL。next然后使用指標
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
是錯的。
您還需要檢查是否存在與當前節點的值相同的前一個節點。否則，您可以洗掉不是唯一的節點，因為在它之后沒有具有相同值的節點。
而這個說法
head = current;
沒有意義，因為在外部 while 回圈之后
while (current != NULL)
指標current等于NULL。
請注意，如果該函式將回傳已洗掉的唯一元素的數量，則該函式對用戶更有用。
這是一個演示程式，展示了如何remove_unique_dll定義串列和函式。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char data;
struct node *next;
struct node *prev;
};
struct list
{
struct node *head;
struct node *tail;
};
int addNode( struct list *list, char data )
{
struct node *node = malloc( sizeof( *node ) );
int success = node != NULL;
if (success)
{
node->data = data;
node->next = NULL;
node->prev = list->tail;
if (list->head == NULL)
{
list->head = node;
}
else
{
list->tail->next = node;
}
list->tail = node;
}
return success;
}
size_t remove_unique_dll( struct list *list )
{
size_t removed = 0;
for ( struct node *current = list->head; current != NULL; )
{
struct node *prev = current->prev;
while (prev != NULL && prev->data != current->data)
{
prev = prev->prev;
}
if (prev == NULL)
{
// there is no preceding node with the same value
// so the current node is possibly unique
struct node *next = current->next;
while (next != NULL && next->data != current->data)
{
next = next->next;
}
if (next == NULL)
{
// the current node is indeed unique
struct node *to_delete = current;
if (current->prev != NULL)
{
current->prev->next = current->next;
}
else
{
list->head = current->next;
}
if (current->next != NULL)
{
current->next->prev = current->prev;
}
else
{
list->tail = current->prev;
}
current = current->next;
free( to_delete );
removed;
}
else
{
current = current->next;
}
}
else
{
current = current->next;
}
}
return removed;
}
void display( const struct list *list )
{
for (const node *current = list->head; current != NULL; current = current->next)
{
printf( "%c<->", current->data );
}
puts( "null" );
}
int main()
{
struct list list = { .head = NULL, .tail = NULL };
const char *s = "aabc";
for (const char *p = s; *p != '\0'; p)
{
addNode( &list, *p );
}
printf( "Doubly linked list:\n" );
display( &list );
size_t removed = remove_unique_dll( &list );
printf( "There are removed %zu unique value(s) in the list.\n", removed );
printf( "Doubly linked list after removing unique elements:\n" );
display( &list );
}
程式輸出為
Doubly linked list:
a<->a<->b<->c<->null
There are removed 2 unique value(s) in the list.
Doubly linked list after removing unique elements:
a<->a<->null
當不再需要串列時，您至少需要再撰寫一個函式來釋放所有分配的記憶體。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/532305.html
標籤：C指针数据结构双向链表