Xóa một nút giữa khỏi danh sách liên kết đơn khi con trỏ đến nút trước đó không khả dụng
Có thể xóa một nút giữa trong danh sách liên kết đơn khi thông tin duy nhất chúng tôi có là con trỏ đến nút cần xóa và không phải là con trỏ đến nút trước đó? Sau khi xóa nút trước đó sẽ trỏ đến nút bên cạnh nút bị xóa.
Đó chắc chắn là một bài kiểm tra hơn là một vấn đề thực sự. Tuy nhiên, nếu chúng ta được phép đưa ra một số giả định, nó có thể được giải quyết trong O(1) thời gian. Để thực hiện điều đó, các điểm danh sách phải được sao chép. Thuật toán là như tiếp theo:
Chúng tôi có một danh sách trông giống như: ... -> Nút (i-1) -> Nút (i) -> Nút (i + 1) -> ... và chúng tôi cần xóa Nút (i).
- Sao chép dữ liệu (không phải con trỏ, chính dữ liệu) từ Nút (i + 1) sang Nút (i), danh sách sẽ có dạng: ... -> Nút (i-1) -> Nút (i + 1) -> Nút (i + 1) -> ...
- Sao chép NEXT của Nút thứ hai (i + 1) thành một biến tạm thời.
- Bây giờ Xóa Nút thứ hai (i + 1), nó không yêu cầu con trỏ đến nút trước đó.
Mã giả:
void delete_node(Node* pNode)
{
pNode->Data = pNode->Next->Data; // Assume that SData::operator=(SData&) exists.
Node* pTemp = pNode->Next->Next;
delete(pNode->Next);
pNode->Next = pTemp;
}
Mike.
Hãy giả sử một danh sách với cấu trúc
A -> B -> C -> D
Nếu bạn chỉ có một con trỏ đến B và muốn xóa nó, bạn có thể làm một cái gì đó như
tempList = B->next;
*B = *tempList;
free(tempList);
Danh sách sau đó sẽ giống như
A -> B -> D
nhưng B sẽ giữ các nội dung cũ của C, xóa hiệu quả những gì có trong B. Điều này sẽ không hoạt động nếu một đoạn mã khác đang giữ một con trỏ tới C. Nó cũng sẽ không hoạt động nếu bạn đang cố xóa nút D. Nếu bạn muốn thực hiện loại hoạt động này, bạn sẽ cần xây dựng danh sách với nút đuôi giả không thực sự được sử dụng để bạn đảm bảo rằng không có nút hữu ích nào sẽ có con trỏ tiếp theo NULL. Điều này cũng hoạt động tốt hơn cho các danh sách trong đó lượng dữ liệu được lưu trữ trong một nút là nhỏ. Một cấu trúc như
struct List { struct List *next; MyData *data; };
sẽ ổn thôi, nhưng một trong đó
struct HeavyList { struct HeavyList *next; char data[8192]; };
sẽ là một chút gánh nặng.
Không thể.
Có hack để bắt chước xóa.
Nhưng không ai trong số đó thực sự sẽ xóa nút mà con trỏ đang trỏ tới.
Giải pháp phổ biến là xóa nút sa và sao chép nội dung của nó vào nút thực tế sẽ bị xóa có tác dụng phụ nếu bạn có con trỏ ngoài trỏ đến các nút trong danh sách, trong trường hợp đó, một con trỏ bên ngoài trỏ đến nút sau sẽ trở nên lơ lửng.
Tôi đánh giá cao sự khéo léo của giải pháp này (xóa nút tiếp theo), nhưng nó không trả lời câu hỏi của vấn đề. Nếu đây là giải pháp thực tế, câu hỏi chính xác phải là "xóa khỏi danh sách được liên kết, GIÁ TRỊ có trong một nút mà con trỏ được đưa ra". Nhưng tất nhiên, câu hỏi chính xác cho bạn một gợi ý về giải pháp. Vấn đề như đã được đưa ra, nhằm mục đích gây nhầm lẫn cho người đó (điều này thực tế đã xảy ra với tôi, đặc biệt là vì người phỏng vấn thậm chí không đề cập rằng nút nằm ở giữa).
Một cách tiếp cận sẽ là chèn null cho dữ liệu. Bất cứ khi nào bạn duyệt qua danh sách, bạn theo dõi nút trước đó. Nếu bạn tìm thấy dữ liệu null, bạn sửa danh sách và đi đến nút tiếp theo.
Cách tiếp cận tốt nhất vẫn là sao chép dữ liệu của nút tiếp theo vào nút cần xóa, đặt con trỏ tiếp theo của nút sang con trỏ tiếp theo của nút tiếp theo và xóa nút tiếp theo.
Các vấn đề của con trỏ bên ngoài trỏ đến nút sẽ bị xóa, trong khi đúng, cũng sẽ giữ cho nút tiếp theo. Hãy xem xét các danh sách được liên kết sau đây:
A-> B-> C-> D-> E-> F và G-> H-> I-> D-> E-> F
Trong trường hợp bạn phải xóa nút C (trong danh sách được liên kết đầu tiên), theo cách tiếp cận được đề cập, bạn sẽ xóa nút D sau khi sao chép nội dung vào nút C. Điều này sẽ dẫn đến các danh sách sau:
A-> B-> D-> E-> F và G-> H-> I-> con trỏ lơ lửng.
Trong trường hợp bạn xóa hoàn toàn NODE C, danh sách kết quả sẽ là:
A-> B-> D-> E-> F và G-> H-> I-> D-> E-> F.
Tuy nhiên, nếu bạn muốn xóa nút D và bạn sử dụng cách tiếp cận trước đó, vấn đề về con trỏ bên ngoài vẫn còn đó.
Gợi ý ban đầu là biến đổi:
a -> b -> c
đến:
a ->, c
Nếu bạn giữ thông tin xung quanh, giả sử, một bản đồ từ địa chỉ của nút đến địa chỉ của nút tiếp theo thì bạn có thể sửa chuỗi vào lần tiếp theo để duyệt qua danh sách. Nếu cần xóa nhiều mục trước lần duyệt tiếp theo thì bạn cần theo dõi thứ tự xóa (nghĩa là danh sách thay đổi).
Giải pháp tiêu chuẩn là xem xét các cấu trúc dữ liệu khác như danh sách bỏ qua.
Có thể làm một xóa mềm? (tức là, đặt cờ "đã xóa" trên nút) Bạn có thể xóa danh sách sau nếu cần.
Được
A -> B -> C -> D
và một con trỏ tới mục B, bạn sẽ xóa nó bằng cách
[.__.] 1. giải phóng mọi bộ nhớ thuộc về các thành viên của B
[.__.] 2. sao chép nội dung của C vào B (bao gồm con trỏ "tiếp theo" của nó)
[.__.] 3. xóa toàn bộ mục C
Tất nhiên, bạn sẽ phải cẩn thận về các trường hợp Edge, chẳng hạn như làm việc trên danh sách của một mục.
Bây giờ khi có B, bạn có C và bộ lưu trữ đã từng là C được giải phóng.
Không nếu bạn muốn duy trì khả năng truyền tải của danh sách. Bạn cần cập nhật nút trước để liên kết với nút tiếp theo.
Làm thế nào bạn kết thúc trong tình huống này, dù sao? Bạn đang cố gắng làm gì khiến bạn hỏi câu hỏi này?
Bạn sẽ phải di chuyển xuống danh sách để tìm nút trước đó. Điều đó sẽ giúp xóa O nói chung (n ** 2). Nếu bạn là mã duy nhất thực hiện xóa, bạn có thể thực hiện tốt hơn trong thực tế bằng cách lưu vào nút trước đó và bắt đầu tìm kiếm ở đó, nhưng điều này có phụ thuộc vào kiểu xóa hay không.
void delself(list *list)
{
/*if we got a pointer to itself how to remove it...*/
int n;
printf("Enter the num:");
scanf("%d",&n);
while(list->next!=NULL)
{
if(list->number==n) /*now pointer in node itself*/
{
list->number=list->next->number;
/*copy all(name,rollnum,mark..) data of next to current, disconect its next*/
list->next=list->next->next;
}
list=list->next;
}
}
vâng, nhưng bạn không thể xóa nó. Nếu bạn không quan tâm đến việc làm hỏng bộ nhớ, hãy tiếp tục ;-)
Đoạn mã sau sẽ tạo LL, n sau đó yêu cầu người dùng đưa con trỏ tới nút cần xóa. nó sẽ in danh sách sau khi xóa Nó thực hiện tương tự như được thực hiện bằng cách sao chép nút sau khi nút bị xóa, qua nút bị xóa và sau đó xóa nút tiếp theo của nút sẽ bị xóa. I E
a B C D
sao chép c vào b và c miễn phí để kết quả là
a-c-d
struct node
{
int data;
struct node *link;
};
void populate(struct node **,int);
void delete(struct node **);
void printlist(struct node **);
void populate(struct node **n,int num)
{
struct node *temp,*t;
if(*n==NULL)
{
t=*n;
t=malloc(sizeof(struct node));
t->data=num;
t->link=NULL;
*n=t;
}
else
{
t=*n;
temp=malloc(sizeof(struct node));
while(t->link!=NULL)
t=t->link;
temp->data=num;
temp->link=NULL;
t->link=temp;
}
}
void printlist(struct node **n)
{
struct node *t;
t=*n;
if(t==NULL)
printf("\nEmpty list");
while(t!=NULL)
{
printf("\n%d",t->data);
printf("\t%u address=",t);
t=t->link;
}
}
void delete(struct node **n)
{
struct node *temp,*t;
temp=*n;
temp->data=temp->link->data;
t=temp->link;
temp->link=temp->link->link;
free(t);
}
int main()
{
struct node *ty,*todelete;
ty=NULL;
populate(&ty,1);
populate(&ty,2);
populate(&ty,13);
populate(&ty,14);
populate(&ty,12);
populate(&ty,19);
printf("\nlist b4 delete\n");
printlist(&ty);
printf("\nEnter node pointer to delete the node====");
scanf("%u",&todelete);
delete(&todelete);
printf("\nlist after delete\n");
printlist(&ty);
return 0;
}
Có, nhưng danh sách của bạn sẽ bị phá vỡ sau khi bạn loại bỏ nó.
Trong trường hợp cụ thể này, duyệt qua danh sách một lần nữa và lấy con trỏ đó! Nói chung, nếu bạn đang hỏi câu hỏi này, có thể tồn tại một lỗi trong những gì bạn đang làm.
void delself(list *list)
{
/*if we got a pointer to itself how to remove it...*/
int n;
printf("Enter the num:");
scanf("%d",&n);
while(list->next!=NULL)
{
if(list->number==n) /*now pointer in node itself*/
{
list->number=list->next->number; /*copy all(name,rollnum,mark..)
data of next to current, disconnect its next*/
list->next=list->next->next;
}
list=list->next;
}
}
Để đến mục danh sách trước đó, bạn sẽ cần duyệt qua danh sách từ đầu cho đến khi bạn tìm thấy mục nhập có con trỏ next trỏ đến mục hiện tại của bạn. Sau đó, bạn sẽ có một con trỏ tới từng mục mà bạn phải sửa đổi để xóa mục hiện tại khỏi danh sách - chỉ cần đặt previous->next đến current->next sau đó xóa current.
chỉnh sửa: Kimbo đánh bại tôi chưa đầy một phút!
Bạn có thể thực hiện trì hoãn việc xóa trong đó bạn đặt các nút sẽ được xóa khỏi danh sách bằng một cờ và sau đó xóa chúng trên đường ngang thích hợp tiếp theo. Các nút được đặt để được xóa sẽ cần được xử lý đúng bằng mã thu thập danh sách.
Tôi cho rằng bạn cũng có thể duyệt qua danh sách một lần nữa từ đầu cho đến khi bạn tìm thấy thứ chỉ vào mục của bạn trong danh sách. Khó tối ưu, nhưng ít nhất là một ý tưởng tốt hơn nhiều so với việc trì hoãn.
Nói chung, bạn nên biết con trỏ đến mục bạn vừa xuất phát và bạn sẽ chuyển qua đó.
(Chỉnh sửa: Ick, với thời gian tôi phải gõ một câu trả lời hoàn hảo, ba người mê mẩn bao phủ gần như tất cả những điểm tôi sẽ đề cập đến. :()
Cách hợp lý duy nhất để làm điều này là duyệt qua danh sách với một vài con trỏ cho đến khi nút đầu tiên tìm thấy nút bị xóa, sau đó cập nhật trường tiếp theo bằng cách sử dụng con trỏ.
Nếu bạn muốn xóa các mục ngẫu nhiên khỏi danh sách một cách hiệu quả, nó cần phải được liên kết đôi. Tuy nhiên, nếu bạn muốn lấy các mục từ đầu danh sách và thêm chúng vào phần đuôi, tuy nhiên, bạn không cần phải liên kết đôi toàn bộ danh sách. Singly liên kết danh sách nhưng làm cho trường tiếp theo của mục cuối cùng trong danh sách trỏ đến mục đầu tiên trong danh sách. Sau đó, làm cho danh sách "đầu" chỉ vào mục đuôi (không phải đầu). Sau đó, thật dễ dàng để thêm vào đuôi của danh sách hoặc loại bỏ khỏi đầu.
Bạn có người đứng đầu danh sách, phải không? Bạn chỉ cần đi qua nó.
Giả sử rằng danh sách của bạn được trỏ đến bởi "head" và nút để xóa nó "del".
Mã giả kiểu C (dấu chấm sẽ là -> trong C):
prev = head
next = prev.link
while(next != null)
{
if(next == del)
{
prev.link = next.link;
free(del);
del = null;
return 0;
}
prev = next;
next = next.link;
}
return 1;
Nếu bạn có một danh sách được liên kết A -> B -> C -> D và một con trỏ tới nút B. Nếu bạn phải xóa nút này, bạn có thể sao chép nội dung của nút C vào B, nút D vào C và xóa D. Nhưng chúng ta không thể xóa nút như vậy trong trường hợp danh sách liên kết đơn vì nếu chúng ta làm như vậy, nút A cũng sẽ bị mất. Mặc dù chúng tôi có thể quay lại A trong trường hợp danh sách liên kết đôi.
Tôi có đúng không
Đây là một đoạn mã tôi ghép lại để thực hiện những gì OP yêu cầu và thậm chí có thể xóa phần tử cuối cùng trong danh sách (không phải theo cách thanh lịch nhất, nhưng nó đã được thực hiện). Đã viết nó trong khi học cách sử dụng danh sách liên kết. Hy vọng nó giúp.
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>
using namespace std;
struct node
{
int nodeID;
node *next;
};
void printList(node* p_nodeList, int removeID);
void removeNode(node* p_nodeList, int nodeID);
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode);
node* addNewNode(node* p_nodeList, int id)
{
node* p_node = new node;
p_node->nodeID = id;
p_node->next = p_nodeList;
return p_node;
}
int main()
{
node* p_nodeList = NULL;
int nodeID = 1;
int removeID;
int listLength;
cout << "Pick a list length: ";
cin >> listLength;
for (int i = 0; i < listLength; i++)
{
p_nodeList = addNewNode(p_nodeList, nodeID);
nodeID++;
}
cout << "Pick a node from 1 to " << listLength << " to remove: ";
cin >> removeID;
while (removeID <= 0 || removeID > listLength)
{
if (removeID == 0)
{
return 0;
}
cout << "Please pick a number from 1 to " << listLength << ": ";
cin >> removeID;
}
removeNode(p_nodeList, removeID);
printList(p_nodeList, removeID);
}
void printList(node* p_nodeList, int removeID)
{
node* p_currentNode = p_nodeList;
if (p_currentNode != NULL)
{
p_currentNode = p_currentNode->next;
printList(p_currentNode, removeID);
if (removeID != 1)
{
if (p_nodeList->nodeID != 1)
{
cout << ", ";
}
cout << p_nodeList->nodeID;
}
else
{
if (p_nodeList->nodeID !=2)
{
cout << ", ";
}
cout << p_nodeList->nodeID;
}
}
}
void removeNode(node* p_nodeList, int nodeID)
{
node* p_currentNode = p_nodeList;
if (p_currentNode->nodeID == nodeID)
{
if(p_currentNode->next != NULL)
{
p_currentNode->nodeID = p_currentNode->next->nodeID;
node* p_temp = p_currentNode->next->next;
delete(p_currentNode->next);
p_currentNode->next = p_temp;
}
else
{
delete(p_currentNode);
}
}
else if(p_currentNode->next->next == NULL)
{
removeLastNode(p_currentNode->next, nodeID, p_currentNode);
}
else
{
removeNode(p_currentNode->next, nodeID);
}
}
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode)
{
node* p_currentNode = p_nodeList;
p_lastNode->next = NULL;
delete (p_currentNode);
}