Luyện tập #2
Bài học 11 trên 14 trong khóa học Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5 của Coddy.
Thử thách
DễViết một hàm (function) findMiddle nhận một mảng số nguyên arr (các giá trị của danh sách liên kết) và trả về giá trị ở giữa.
Với độ dài lẻ, lấy chính xác phần tử ở giữa. Với độ dài chẵn, lấy phần tử thứ hai trong hai phần tử ở giữa (chỉ số length / 2). Nếu danh sách rỗng, trả về -1.
Dùng danh sách liên kết để giải bài toán này! Cách làm kinh điển là dùng hai con trỏ: một con trỏ chậm và một con trỏ nhanh. Khi con trỏ nhanh đến cuối, con trỏ chậm sẽ ở giữa.
Bạn phải dùng lớp LinkedList (được cung cấp trong linkedlist.<ext> cùng với node.<ext>) — không dùng các tính năng có sẵn của ngôn ngữ như hàm đảo ngược mảng, cắt mảng hoặc các thao tác danh sách trong thư viện chuẩn để tính kết quả.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[8192];
if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
int arr[4096];
int len = 0;
char* tok = strtok(line, " \t\r\n");
while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int r = findMiddle(arr, len);
printf("%d\n", r);
return 0;
}
Tất cả bài học trong Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5
Tự luyện tập: Trình biên dịch C online