xóa phần tử bất kỳ trong danh sách liên kết đơn

#1

Em có đồ án liên quan đến cấu trúc sách,trong đó có yêu cầu xóa sách.Yêu cầu chỉ dừng lại xóa node đầu hoặc cuối là đủ,và em đã làm xong rồi.Nhưng em muốn nâng cấp lên 1 tí,cụ thể là xóa sách theo ID.Em muốn nhập vào ID và duyệt danh sách sách liên kết đơn nếu gặp thì xóa node đó,nhưng em không biết làm sao để định vị được node trước nó???

void xoa(list l)
{
	int id; 
	printf_s("nhap ID sach can xoa: ");	scanf_s("%d", &id);
	for (node*p = l.phead; p; p = p->pnext)
	{
		if (p->key.ID == id)
		{

		}
	}
}
#2

Bạn cần một biến tạm để lưu node trước đó, chẳng hạn

void xoa(list l)
{
	int id; 
        node *previous;
	printf_s("nhap ID sach can xoa: ");	scanf_s("%d", &id);
	for (node*p = l.phead; p; p = p->pnext)
	{
		if (p->key.ID == id)
		{

		}
               previous = p;
	}
}
#3 
// thuc hiện đệ quy để xoá
Node * deleteLast(Node *cur,int id){
    if(!cur) return cur;
    Node *next=cur->next;
    
    if(cur->ID==id) {
          free(cur);// Node hien tai can xoa
          return deleteLast(next,id);
    } else {
          // giữ lại node cur
          cur->next=deleteLast(next,id);
          return cur;
    }
}
// list->head=deleteLast(list->head,id);
1 Like
#4

Bạn dùng 1 con trỏ temp cùng kiểu để lưu node phía trước node đang xét, khi gặp id cần xóa (node p) thì lấy temp->next = p->next. Xong rồi giải phóng node p nữa là ok.

Nếu chỉ xóa 1 phần tử thôi thì break luôn, còn không thì phải gán p = temp->next để xét tiếp

#5

dạ.cũng chính là vấn đề của em,không biết làm sao để định vị được nó,chứ gán temp->next=p->next thì em biết rồi.vấn đề làm sao xác định cái node temp ạ?

#6

Chia làm các trường hợp sau:

  • head == null: xong
  • xoá hết cái = id từ đầu
while(list->head->ID==id) {
    next=list->head;
    delete list->head;
    list->head=next
}
  • sau bước này nếu head null thì giống th1
  • th còn lại (để đảm bảo luôn có prev!=null)
prev= list->head;
cur=list->head->next;
while(cur){
    if(cur->ID==id){
          prev->next=cur->next;
          delete (cur);
    }
    cur=prev->next;
}

đến đây coi như hoang thành hàm xoá

#7

xác định temp sau khi xét node p hiện tại ấy. Mình chỉ lưu lại node trước của node đang xét thôi à
node *temp=NULL; For (node *p = list.head; p->next != NULL; p = p->next) { // xử lý ..... temp = p; }

#8

cái này là node temp = vs node p chứ đâu phải node temp là node đứng trước node p đâu ạ?

1 Like
#9

Bạn chưa hiểu rõ cách chương trình chạy rồi, lệnh temp = p sẽ được đặt ở cuối cùng của vòng for, trước các lệnh xử lý so sánh và xóa node.
Đến vòng lặp tiếp theo p trỏ đến node tiếp theo (p = p->next), nên temp sẽ là node trước đó của p cho đến khi gặp câu lệnh temp = p.

void xoa(list l)
{
	int id; 
        node *prev;
	printf_s("nhap ID sach can xoa: ");	
        scanf_s("%d", &id);
	for (node*p = l.phead; p; p = p->pnext)
	{
		if (p->key.ID == id)  // lúc này p là node tiếp theo, prev vẫn là node trước đó
		{
                     previous->next = p->next;
                     delete p;
		}
                prev = p;  // cho đến khi chạy đến đây
	}
}
1 Like
#11

Bằng vào cuối vòng lặp mà, lúc p= p->next thì temp sẽ là node trước của p hiện tại, bởi vậy mình mới để temp=p ở cuối

1 Like
#12

Cám ơn các tiền bối,để em thử.

#13

b giống t cũng chưa hiểu cái đoạn gán đó

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?