Lỗi bài toán sắp xếp DSLK đơn tăng dần bằng đệ quy

#1

Dạ chào mọi người! Hiện em đang làm một bài toán sắp xếp DSLK theo thứ tăng dần bằng đệ quy. Nhưng khi chạy thì nó bị lỗi!

Em không biết tại sao lại sai như vậy? Và sửa lại chương trình như thế nào?! Mong mọi người chỉ em!

void increasingSortLList(node&head)
{
	if (head==NULL) return;
	increasingSortLList(head->next);
	int a = head->data;
	int b = (head->next)->data;
if (a < b )
{
	swap(a,b);
	increasingSortLList(head->next);
}
}

P/s: Thật ra em đã làm một bài giống vậy trong mảng nhưng nó vẫn chạy ok đến khi qua bên DSLK thì nó bị lỗi T_T.

#2

Anh/chị có thể nói rõ hơn về lỗi là output không đúng hay là không run được hay như thế nào được không ạ.

Hmm…
Chỗ này hình như sao sao ấy…

  • a và b là biến cục bộ vậy đổi value của a với b cho nhau có tác dụng gì nhỉ.

  • If(a<b) thì đệ quy vậy còn a>=b thì thoát khỏi hàm luôn đúng không nhỉ :grin:

  • So sánh 2 node liên tiếp với nhau như trên thì có giống như bbsort mà dùng 1 for loop không nhỉ :thinking: .
    Nhược điểm của dslk đơn là phải duyệt trâu từ đầu đến cuối vì thế nên hình như thiếu thiếu gì đó :thinking:

Còn nữa…
Hình như chủ thớt đang mải nên quên nhiều thứ quá :no_mouth:

1 Like
#3
  1. head trong bài ng` ta hay viết là con trỏ :smiley: viết tham chiếu hơi mất công.
  2. Điều kiện dừng bị thiếu.
2 Likes
#4

Lúc mình debug thì nó báo lỗi theo mình tìm hiểu trên mạng thì nó bảo là không xác nhận con trỏ (hay là không nhận được con trỏ kiểu dạng vậy á! )

Thật ra lúc đầu mình không có ý định đặt biến a,b đâu. Lúc sau mình đặt vậy để cho dể nhìn để tìm lỗi cho chỗ sai đó bạn!

Cái chỗ (a<b) mình không xét dấu bằng vì mình đang sắp xếp tăng dần á, mình chỉ cần xét nó lớn hơn thì đổi chỗ cho nhau thôi đó! Dấu bằng thì ở yên không cần đổi chỗ nên mình nghĩ dấu bằng không cần thiết.( Việc a>=b thì nó không thoát ra khỏi hàm đâu bạn tại về bản chất thì mình đã test việc sắp xếp này trên mảng một chiều rồi đó!)

Mình đang mải nên quên gì vậy bạn?! Mình không hiểu ý bạn lắm ^^( Bạn nói rõ để mình sửa được không?)

1 Like
#5
  1. Theo sách mà mình đọc thì mình thấy nó hay để là &head, thì lúc đó mình cũng hỏi là tại sao lại dùng còn trỏ thì thầy mình có bảo trong trường hợp này nó được xem như nhau( ý là chỗ increasingSortLList(&node) hay để increasingSortLList(*node) nó cũng hiểu là như nhau!)
  2. Điều kiện dừng của mình thiếu thiếu j vậy bạn?!
#6

Em hơi thắc mắc ở đây 1 chút anh giải thích cho em được không ạ. Em xin phép sử dụng mảng thay cho dslk để dễ tưởng tượng để giải thích cách hiểu của em như sau:
Khi chương trình chạy đến if (a < b ) thì chương trình sẽ xét xem a < b hay không. Nếu nhỏ hơn thì thực hiện cụm lệnh bên trong dấu ngoặc nhọn. Nếu không thì sẽ thực hiện cụm lệnh ở dấu ngoặc nhọn bên else. Nếu không có else sẽ tiếp tục thực hiện những câu lệnh bên dưới.

a[5] = { 1 ; 5 ; 4 ;3 };

Ở mảng bên trên ta sẽ thấy đệ quy như sau:

Lần 1 : a = 1 ; b = 5 => a < b == true => đệ quy;
Lần 2 : a = 5 ; b = 4 => a < n == false 
=> Không thực hiện lệnh trong cụm if 
=> Không đệ quy
=> Thoát hàm

Em xin trình bày ý kiến của em 1 chút là &head đây là kiểu tham chiếu chứ không phải là con trỏ.

Vì thế nên chỗ này hiểu như nhau thì em nghĩ là không đúng và khi cố truyền 1 con trỏ vào đối số tham chiếu sẽ bị lỗi.

Hình ảnh lỗi

image
image1600×900 155 KB

Không biết em có hiểu sai gì không mong mọi người chỉ ra ạ.

Em nghĩ là anh ấy nói anh thiếu head->next == NULL

1 Like
#7
  1. Đây là đoạn code mình làm đệ quy trong mảng:
void increasingSort(int a[], int n)
{
		if (n == 1) return;
		increasingSort(a, n - 1);
		if (a[n - 1] < a[n - 2])
		{
				swap(&a[n - 1], &a[n - 2]);
				increasingSort(a, n - 1);
		}
}

( Đây là mình tham khảo trong sách Kĩ thuật lập trình ngoài ra mình cũng thấy có nhiều trên mang bạn có thể lên mạng tham khảo để biết nó hoạt động như thế nào nha!)

  • Ở cái ví dụ mà bạn đưa thì theo mình ( đây là ý kiến của mình thôi nên cũng không chắc đúng 100% nha bạn!. Đoạn code ở trên bị sai á! Đoạn code đúng nè :
void increasingSortLList(node& head)
{
	if (head->next == NULL) return;
	increasingSortLList(head->next);
	if (head->data > head->next->data)
	{
		swap(&head->data, &head->next->data);
		increasingSortLList(head->next);
	}
}

).
Nên mình giải thích lại chỗ mấy trường hợp của bạn nha!

  • Ở lần 1: 1>5 => false=> nó sẽ chạy tiếp=> đệ quy!
  • Ở lần 2: 5>4=> true=> swap=> chạy tiếp=> đệ quy!
    => Chương trình này sẽ chạy tiếp đến khi nào con trỏ next của head trỏ đến NULL nó sẽ thoát ra khỏi chương trình ! ( if(head->next==NULL) được gọi là điệu kiền dừng của đệ quy!, găp điều kiện dừng thì nó mới thoát khỏi đệ quy nha!)

  1. Tất nhiên là con trỏ và tham chiếu không thể nào gióng nhau rồi bạn ^^, mình chỉ nói là nó có thể hiều như nhau trong trường hợp này thôi á bạn! ( Vì hiện tại mình không có nhiều thời gian nên không thể giải thích rõ cho bạn được bạn có thể đọc trong link này :https://www.stdio.vn/article/phan-biet-tham-chieu-va-con-tro-trong-c-IkmL21. Hoặc mong có cao nhân nào qua đây chỉ về phần này tại thực chất mình cũng chỉ là một người học lại và tìm hiều thôi nên không chắc chắn và giải thích đúng 100%, nếu bạn không chắc có thể code thử để cho chắc chắn nha! Sr bạn nhiều!)

  2. Cái điều kiện dừng head->next==NULL khiến mình hơi thắc mắc nhiều nên mình muốn hỏi lại cho chắc ! Tại mấy cái bài đảo mảng, tìm vị trí trùng lập, … ở lần trước mình làm mình đều làm điều kiện dừng là head==NULL đều ok những không biết tại sao đến bài sắp xếp này lại sai! Vì không hiểu rõ tại sao lại sai như vậy ?! Nên mình gửi code lên để mong có một lời giải thích chính xác á! ( Với lại còn cách sửa nào khác không !)

P/s: Đây là ý kiến cá nhân mình không chắc chắn đúng 100% nên mong bạn và mọi người thông cảm.

2 Likes
#8

Đệ quy kép. Gọi đệ quy, trong đệ quy lại có gọi đến hàm đệ quy khác. Tương đương với 2 vòng lặp dùng để sắp xếp. Tùy thuật toán, mình hay dùng Sắp xếp chọn (Selection sort) để làm ví dụ cho nhanh.

Cách của bạn giống với Sắp xếp nổi bọt (Bubble sort), nhưng bạn chỉ cho nó “nổi bọt” 1 lần. Tức là chỉ có 1 phần tử đúng với vị trí cần sắp xếp, còn n - 2 lần “nổi bọt” nữa.

4 Likes
#9

Cái ví dụ em đưa là do em chưa đọc kĩ phần code :grin: . Do return không để trong ngoặc nhọn nên em nhìn nhầm cả return với dòng dưới là 1 cụm nên bỏ qua dòng gọi đệ quy bên dưới luôn 🤦. Mắt kém tay mờ rồi huhu.
Phần giải thích ví dụ thì đợi lát em đọc kĩ đã. Onl trộm nên cứ đọc được câu lại hụt mất câu. Phụ huynh ganh suốt ngày :sob:.
Còn phần giải thích điều kiện dừng thì anh hiểu được tại sao ở duyệt mảng lại dừng khi n==1 là có thể hiểu được tại sao lại phải là head->next

#10

Tăng dần theo chiều nào?
Nếu tăng dần từ head -> tail thì code trên sai bét nha.

4 Likes
#11

Em xin lỗi nhưng cái em muốn hỏi ở đây là về đối số của hàm. Node& ở đây tượng trưng cho kiểu tham chiếu của 1 biến truyền vào của kiểu dữ liệu node. Bên dưới anh sử dụng dấu -> nhưng bên trên lại truyền vào giá trị.
Em có thắc mắc không biết trong hàm main anh khai báo head là con trỏ hay 1 biến thông thường. LList thì chắc là con trỏ rồi.

  • Nếu head là 1 biến kiểu node thì truyền vào đúng nhưng lại truy xuất bằng dấu -> là sai.
  • Nếu truyền vào là 1 con trỏ thì đối số phải là 1 tham chiếu của con trỏ tức node *&head thì anh mới có thể truy xuất bằng toán tử -> .

Trên đây là lí do em nói là không thể hiểu con trỏ và tham chiếu như nhau ngay cả trong trường hợp này được. Nếu có sai điều gì mong mọi người chỉnh sửa ạ. :grin:

Do ngược dấu đúng không anh @hungaya nhỉ. :thinking:
Như anh @hungaya đã nói thì lí do là do trong code với mảng anh đưa ra là duyệt ngược nhưng làm việc với LList thì lại bắt buộc duyệt xuôi nên nếu cứ dùng dấu như duyệt ngược với mảng là sai hết.
À mà có cách nào duyệt ngược được không nhỉ. Em biết phi lí nhưng vẫn tò mò.
P/s : Chủ thớt học trường gì và năm mấy ấy ạ :grin: . Tìm hiểu rồi 2 năm nữa thi đại học vào cùng trường với chủ thớt rồi tìm chủ thớt xem sao :rofl::rofl: (cái này em đùa còn chủ thớt mà trả lời thì em cảm ơn :rofl::rofl:). Đừng nhìn avt mà mừng hụt vì em là con trai nha :rofl::rofl:

2 Likes
#12

Yep, nếu nó chạy đúng thì linked list sẽ sắp xếp theo chiều giảm dần.

Còn vì sao nó lỗi thì swap nhầm đối tượng, cái cần swap là node->data chứ không phải là a và b.

Để tạo linked list tăng dần thì đổi dấu so sánh: từ a < b thành a > b.

5 Likes
#13

Thực chất thớt đang duyệt ngược đấy.

Code này thực ra là 3 vòng lồng nhau.

2 Likes
#14

Minh đã gửi đoạn code đúng ở trên rồi á bạn ! Mình cũng đã nói là đoạn code trên bị sai mà ^^

1 Like
#18

Tại mấy phần trên ( ý là còn một vài bài trên mình dùng điều kiện dừng là head==NULL là ok đó bạn nên mình khá thắc mắc là tại sao chỉ có thằng sắp xếp tăng dần là phải head->next=NULL thì mới được đó bạn !

Mình cũng không dám giải thích cho bạn hiểu rõ như thế nào vì thực chất bản thân mình cũng đã hiểu không rõ lắm, và thầy cũng giải thích khá dài dòng nên để giải thích cho bạn hiểu thì chắc mong một cao nhân nào đó qua đây thấy và giải thích ! ( Ngoài ra bạn có thể đọc tham khảo cái link mà mình gửi, mình đọc trong đó rồi suy từ từ ra, mà nói z thôi chứ mình cũng không hiểu 100% đâu bạn !)

Theo trong tầm hiểu biết của mình thì không nha bạn !

À hiện tại mình mới năm nhất thôi nha bạn và vẫn đang tìm hiểu nè ^^ ( tại mình lên 12 mới chọn ngành nên học muốn sắp mặt luôn T_T, nếu thích bạn có thể học Khoa học Tư Nhiên nha! Rất mong được chung trường với ban! À với lại mình là con gái đó nên không sao đâu nha bạn !

2 Likes
#19 
void increasingSortLList(node& head)
{
	if (head->next == NULL) return;
	increasingSortLList(head->next);
	if (head->data > head->next->data)
	{
		swap(&head->data, &head->next->data);
		increasingSortLList(head->next);
	}
}

Gửi bạn đoạn code đúng nè! Vs lại bạn có thể giải thích cho mình là tại sao điều kiện dừng của nó là if(head->next ==NULL) không z? ( Tại mấy bài khác mình làm nó chỉ cần head==NULL là ok rồi !)

2 Likes
#20

Nếu head->next là NULL thì dòng so sánh lỗi ngay vì truy cập NULL. Nói chung phải kiểm tra NULL trước, cái này là chung nhất.

Bài này thì bạn so sánh head với phần tử ngay sau thì: nếu head là phần tử cuối cùng thì thôi :smiley:

6 Likes
#21

À! Ok bạn mình hiểu rồi ! ( Mình quên mất tiêu đây là bài toán sắp xếp, nó phải so sánh với thằng sau nó :V) Thanks bạn nhiều !!!

3 Likes
#22

Bạn tên gì, học lớp nào v, tui cũng học KHTN nè

1 Like
#23

Z bạn tên gì, học lớp nào vậy ^^

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