01/10/2018, 12:30

Hàm đệ quy in linked list chỉ in ra phần tử cuối

Em đoạn code xây dựng danh sách liên kết đơn như sau.

//Định nghĩa struct
#include<stdlib.h>
#include<stdio.h>
struct node {
	int data;
	struct node* next;
};
typedef struct node* _ref;
_ref getNode(int x);
void addFirst(_ref& head, _ref& tail, int k);
void detroyList(_ref head);

// Khởi tạo một node
_ref getNode(int x) {
	_ref p;
	p = (_ref)malloc(sizeof(_ref));
	if(!p) {
		printf("Cap phat khong thanh cong");
		exit(0);
	}
	else {
		p->data = x;
		p->next = NULL;
	}
	return p;
}
// thêm phần tử đầu vào danh sách
void addFirst(_ref* head, _ref* tail, int k) {
	_ref p =getNode(k);
	if(!head) {
		*head = *tail = p;
	}
	else {
		p->next = *head;
		*head = p;
	}
}
// in danh sach bang de quy
_ref DQprintLIst(_ref head) {
         _ref p =head
          if(p->next!=NULL)   {
          return DQprintLIst(p->next);
          printf("%d",p->data);
          }
}
// huy danh sach
void detroyList(_ref head) {
	_ref p ;
	while(head) {
		p = head;
		head = p -> next;
		free(p);
	}
}

int main() {
	_ref head = NULL, tail = NULL;
	int k;
	while(1) {
		printf("
 nhap k = 0 de thoat ");
		scanf("   %d",&k);
		if(!k) break;
		else {
			addFirst(&head,&tail,k);
		}

	}

	DQprintLIst(head);
	detroyList(head);
}

em không hiệu tai sao cái hàm đệ quy em viết lại in được mỗi giá trị cuối vậy ạ.

Pham Van Hai viết 14:34 ngày 01/10/2018

_ref p =head

  • code ban chưa chạy được, dòng này bị lỗi không build được.

if(p->next!=NULL) {
return DQprintLIst(p->next);
printf("%d",p->data);
}

  • Hàm in danh sách của bạn sẽ không in được gì vì bạn đã return (thoát ra khoải hàm) trước khi in rồi.
  • Code của bạn là C++ chứ không phải C. Bạn nên tìm hiểu kỹ sự khác nhau giữa C và C++. Dùng lẫn lộn dễ gây lỗi.
Nobita viết 14:37 ngày 01/10/2018

Tại em quen mồm, em chỉ dùng cái tham chiều của C++ để viết cho dễ đỡ phải truyền con trỏ . Vậy cái hàm đệ quy của em sữa như thế nào thì được vậy bác,
Em nghĩ là cho dù return thoát ra khỏi hàm, nhưng do là đệ quy nên hàm printf vẫn được đưa vào stack , em sai chỗ nào vậy bác.

Lê Cường viết 14:44 ngày 01/10/2018

Nhìn code bác em thấy bối rối quá @@.

Pham Van Hai viết 14:37 ngày 01/10/2018
  • Các câu lệnh sau return sẽ không được chạy.
  • Bạn tham khảo theo cách này (http://www.geeksforgeeks.org/write-a-recursive-function-to-print-reverse-of-a-linked-list/)
/* Function to reverse the linked list */
void printReverse(struct Node* head)
{
    // Base case  
    if (head == NULL)
       return;
 
    // print the list after head node
    printReverse(head->next);
 
    // After everything else is printed, print head
    printf("%d  ", head->data);
}
Nobita viết 14:46 ngày 01/10/2018

lỗi trình bày hay lỗi gì vậy bác. Bác nói để em xem xét rồi sửa chữa.

Nobita viết 14:33 ngày 01/10/2018

Bạn cho mình hỏi câu lệnh return; trong đó ý nghĩa như nào với.

Pham Van Hai viết 14:45 ngày 01/10/2018

// Base case
if (head == NULL)
return;

lướt đến phần tử cuối cùng thì thoát ra khỏi hàm

Nobita viết 14:37 ngày 01/10/2018

bạn giải thích cho mình cách mà nó in ngược và đưa vào stack như thế nào với.

Bài liên quan
0