ที่นี่เราจะมาดูวิธีค้นหาความยาวของรายการที่เชื่อมโยงโดยใช้วิธีการวนซ้ำและแบบเรียกซ้ำ หากระบุส่วนหัว เราต้องทำตามขั้นตอนเหล่านี้เพื่อให้ได้ความยาว
-
สำหรับการทำซ้ำ -
-
เป็นผู้นำของรายการ จนกว่าตัวชี้ปัจจุบันจะไม่เป็นโมฆะ ไปที่โหนดถัดไปและเพิ่มจำนวน
-
-
สำหรับวิธีการแบบเรียกซ้ำ -
- ส่งส่วนหัวเป็นอาร์กิวเมนต์ เงื่อนไขพื้นฐานคือเมื่ออาร์กิวเมนต์เป็นโมฆะ จากนั้นคืนค่า 0 มิฉะนั้น ให้ป้อนรายการซ้ำในรายชื่อและส่งโหนดถัดไปจากโหนดปัจจุบัน คืนค่า 1 + ความยาวของรายการย่อย
ตัวอย่าง
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int data) {
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = (*start);
(*start) = new_node;
}
int count_recursive(Node* start) {
if (start == NULL)
return 0;
return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
int count = 0;
Node* current = start;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
int main() {
Node* start = NULL;
append(&start, 1);
append(&start, 3);
append(&start, 1);
append(&start, 2);
append(&start, 1);
cout << "Node count using iterative approach: " << count_iterative(start) << endl;
cout << "Node count using recursion: " << count_recursive(start);
} ผลลัพธ์
Node count using iterative approach: 5 Node count using recursion: 5
