Tôi có một ma trận số nguyên nên hành động như một bộ đệm:C: cách thông minh để "dịch chuyển" ma trận?
x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};
Bây giờ nếu tôi thêm một hàng mới {3, 3, 3, 3, 3}, ma trận mới sẽ giống như thế:
x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};
Có một cách thông minh để làm điều này mà không cần sao chép tất cả các yếu tố xung quanh?
Làm thế nào về hoạt động modulo?
Nếu bạn truy cập vào các yếu tố như matrix[x + SZ * y] bạn có thể thay đổi nó thành:
matrix[x + SZ * ((y + FIRST_ROW) % SZ)]. Bằng cách này để thực hiện thay đổi này, bạn chỉ cần đặt dòng mới {3, 3, 3 ..} trong đó dòng {0, 0, 0} là và tăng số đếm FIRST_ROW để trỏ đến hàng bắt đầu mới.
Rất tốt, cảm ơn! Nơi này đầy những người sáng tạo. :-) –
+1 dựa trên đặc điểm kỹ thuật bổ sung trong phần nhận xét cho câu hỏi ban đầu, đây có lẽ là giải pháp thay thế sẽ mang lại hiệu suất tốt nhất. –
Bây giờ tôi đã triển khai nó và nó hoạt động tốt. Cảm ơn một lần nữa, và cảm ơn guys cho tất cả các câu trả lời khác! –
Sử dụng danh sách được liên kết.
struct node
{
int row[5];
struct node *next;
};
Gắn thêm hàng đơn giản như đi danh sách đến cuối, sau đó thay thế con trỏ tiếp theo NULL bằng nút mới (con trỏ tiếp theo là NULL).
Điều này làm việc cho các thuật toán, nhưng nó sẽ không cho kết quả cực kỳ chậm khi bạn thực sự làm việc với ma trận? – alternative
Điều đó tùy thuộc vào những gì bạn đang làm với nó. Nếu bạn không mở rộng ma trận của bạn tất cả các thời gian, bạn có lẽ tốt hơn off ngâm lên memcpy thường xuyên. – nmichaels
Lưu ý rằng trong câu hỏi hàng mới không được thêm vào ma trận, mà thay thế hàng thứ nhất. Vì vậy, nếu bạn chọn giải pháp danh sách được liên kết, hãy đảm bảo bạn đã hủy mục đầu tiên của mình trong danh sách. – ysap
Bạn có thể tăng x để nó trỏ đến hàng thứ hai, sau đó giải phóng hàng đầu tiên? Rõ ràng, bạn sẽ cần phải phân bổ một hàng tại một thời điểm và điều này sẽ không đảm bảo rằng ma trận là tiếp giáp. Nếu bạn yêu cầu điều đó, bạn có thể phân bổ một khối bộ nhớ lớn để giữ ma trận của bạn và sau đó clobber các phần không sử dụng khi bạn đạt đến kết thúc.
Nếu ma trận của bạn được định nghĩa là int ** và bạn phân bổ riêng từng hàng, thì bạn sẽ chỉ phải trao đổi các con trỏ hàng.
Nghe hay đấy. Tôi thực sự cần phải học cách suy nghĩ theo hướng con trỏ hơn. :) –
Chỉ có vấn đề là không giống như giải pháp danh sách được liên kết được đề xuất ở nơi khác, ở đây bạn phải phân bổ trước con trỏ tới số hàng tối đa bạn sẽ có. Nếu không, nó là một cách hiệu quả hơn so với danh sách liên kết. ** EDIT ** Tôi chỉ nhận thấy rằng trong câu hỏi của bạn, bạn vẫn còn với 3 hàng sau khi thêm hàng mới. Nếu đây là đại diện, thì bạn tốt với câu trả lời của @ mikerobi. Bạn chỉ cần quản lý con trỏ của bạn một khi các hàng được đổi chỗ. – ysap
@ysap, hoạt động O (n) không thường xuyên để tăng số lượng hàng, thường sẽ hiệu quả hơn khi một O (n) thường xuyên truy cập một giá trị. – mikerobi
Nếu bạn sử dụng một mảng con trỏ tới mảng (thay vì mảng hai chiều thông thường), bạn có thể sao chép chỉ các con trỏ tới hàng thay vì sao chép tất cả các phần tử.
Và nếu bạn đồng ý với việc phân bổ mảng con trỏ, bạn có thể thêm một con trỏ mới vào cuối và chuyển con trỏ đến "bắt đầu" của mảng. Nhưng đây sẽ không phải là một ý tưởng tốt nếu bạn có khả năng muốn thực hiện loại thay đổi này nhiều lần. Và tất nhiên bạn muốn chắc chắn rằng bạn có con trỏ ban đầu ở đâu đó để bạn có thể thích hợp free() tài nguyên của mình.
Lười biếng để viết ví dụ mã - bạn có thể sử dụng modulo arithmetics để xử lý các hàng. Khi đẩy một hàng mới, chỉ đơn giản là tăng một biến bù đắp bắt đầu, thêm chiều cao ma trận và modulo kết quả theo chiều cao ma trận. Bằng cách này bạn sẽ có được một ma trận hình tròn mà không cần phải sao chép toàn bộ ma trận và giữ mảng ma trận nhỏ gọn.
Nhiều câu trả lời dưới đây là chính xác về mặt kỹ thuật, nhưng tất cả đều liên quan đến sự cân bằng khác nhau. Bạn có thể mở rộng sử dụng dự kiến của mình một chút không? Các ma trận này sẽ lớn đến cỡ nào? Làm thế nào thường mong đợi để thêm một hàng, so với số lần bạn sẽ truy cập dữ liệu từ các ma trận? Bạn sẽ truy cập các phần tử riêng lẻ của ma trận, hay nó sẽ chỉ được đọc như một thực thể toàn bộ từ đầu đến cuối? Bạn có muốn để có thể giải phóng các phần của ma trận theo thời gian? Nếu vậy, chỉ từ cuối, hoặc từ đầu, hoặc từ một hàng tùy ý? –
Ma trận không lớn (như 100 phần tử trong tổng số).Tôi sẽ luôn luôn truy cập toàn bộ ma trận, hàng "cũ" có thể biến mất (hành vi nămo-hàng đợi), các cập nhật diễn ra rất thường xuyên. –
Trong trường hợp đó, phương pháp modulo được đề xuất bởi @ruslik có lẽ là cược tốt nhất của bạn. Chỉ cần cấp phát một mảng có thể xử lý kích thước tối đa, duy trì một con trỏ đến đầu hiện tại và quấn quanh đầu của mảng khi bạn hết phòng. –