[SOLVED]thực hiện Skip List trong C++
Vì vậy, tôi quyết định thử và tạo ra một danh sách bỏ qua gấp đôi liên kết được sắp xếp ...
Tôi chắc rằng tôi có một nắm bắt tốt về cách nó hoạt động. Khi bạn chèn x chương trình tìm kiếm danh sách cơ sở cho vị trí thích hợp để đặt x (vì nó được sắp xếp), (khái niệm) lật một đồng xu, và nếu "đồng tiền" rơi vào phần tử đó thì được thêm vào danh sách ở trên nó (hoặc một danh sách mới được tạo ra với phần tử trong nó), được liên kết với phần tử bên dưới nó, và đồng xu bị lật lại, vv Nếu "đồng tiền" chuyển sang b bất cứ lúc nào thì chèn xong. Bạn cũng phải có một-vô hạn được lưu trữ trong mỗi danh sách như là điểm khởi đầu để không thể chèn một giá trị nhỏ hơn điểm bắt đầu (có nghĩa là nó không bao giờ được tìm thấy.)
Để tìm kiếm x, bạn bắt đầu từ "trên cùng bên trái" (giá trị thấp nhất trong danh sách thấp nhất) và "di chuyển sang phải" thành phần tử tiếp theo. Nếu giá trị nhỏ hơn x, bạn tiếp tục với phần tử tiếp theo, v.v. cho đến khi bạn "đi quá xa" và giá trị lớn hơn x. Trong trường hợp này, bạn quay trở lại phần tử cuối cùng và di chuyển xuống một mức, tiếp tục chuỗi này cho đến khi bạn tìm thấy x hoặc x không bao giờ được tìm thấy.
Để xóa x, bạn chỉ cần tìm kiếm x và xóa nó mỗi khi nó xuất hiện trong danh sách.
Hiện tại, tôi chỉ cần tạo một danh sách bỏ qua lưu trữ số. Tôi không nghĩ rằng có bất cứ điều gì trong STL có thể hỗ trợ tôi, vì vậy tôi sẽ cần phải tạo một danh sách lớp chứa một giá trị số nguyên và có chức năng thành viên, tìm kiếm, xóa, và chèn.
Sự cố tôi gặp phải là xử lý các liên kết. Tôi khá chắc chắn rằng tôi có thể tạo một lớp để xử lý các liên kết "ngang" với một con trỏ đến phần tử trước và phần tử ở phía trước, nhưng tôi không chắc chắn cách xử lý các liên kết "dọc" (trỏ đến phần tử tương ứng) ? trong danh sách khác)
Nếu bất kỳ logic của tôi là thiếu sót xin vui lòng cho tôi biết, nhưng câu hỏi chính của tôi là:
- Làm thế nào để đối phó với các liên kết dọc và liệu liên kết ý tưởng của tôi là đúng
- Bây giờ Tôi đọc ý tưởng danh sách lớp của tôi Tôi nghĩ rằng một danh sách nên giữ một vectơ số nguyên chứ không phải là một số nguyên duy nhất. Trong thực tế, tôi khá tích cực, nhưng sẽ giống như một số xác nhận.
- Tôi giả định lật đồng xu đơn giản sẽ gọi hàm int trong đó rand()% 2 trả về giá trị 0 hoặc 1 và nếu 0 thì giá trị "tăng cấp" và nếu 0 thì giá trị chèn sẽ kết thúc. Điều này có đúng không?
- Làm thế nào để lưu trữ một giá trị tương tự như-vô hạn?
Chỉnh sửa: Tôi đã bắt đầu viết một số mã và đang cân nhắc cách xử lý hàm tạo Danh sách .... Tôi đoán rằng khi xây dựng, giá trị "-infinite" phải được lưu trữ trong tên vectơ [ 0] phần tử và tôi chỉ có thể gọi chèn vào nó sau khi tạo của nó để đặt x ở vị trí thích hợp.
Đối với 2 tôi có nghĩa là làm thế nào để đối phó với việc lưu trữ dữ liệu thực tế. Tôi giả định rằng Danh sách phải có một thành viên riêng: vector các số có chứa số được chèn. Đối với 4 tôi đoán rằng nó chỉ nên là giá trị số nguyên thấp nhất có thể? –
trikker
Đối với 2 bạn cần lưu trữ con trỏ đến những gì bạn muốn lưu trữ như * char hoặc * int hoặc * MyClass vv ... Đối với 4, không có cách nào để làm điều đó với số nguyên thông thường, bạn phải thực hiện của riêng bạn hoặc sử dụng điểm nổi. – Unknown
Tại sao nó chứa một véc tơ? Mỗi nút trong danh sách phải lưu trữ một số nguyên. Bạn có thể sử dụng std :: numeric_limits :: min() cho -infinity, nhưng tôi khuyên bạn nên làm cho nút đầu một trường hợp đặc biệt. –
Geerad