CTDL và giải thuật - In ra màn hình các phần tử ở chỉ số k đến n-1 rồi từ chỉ số 0 đến k-1

Nhập vào một số nguyên dương n, tiếp theo là n số nguyên của một dãy số, hãy cài đặt nó vào một danh sách liên kết vòng. Tiếp theo cho một số nguyên k, (0 ≤ k < n).
Hãy in ra màn hình các phần tử ở chỉ số k đến n-1 rồi từ chỉ số 0 đến k-1, sau một phần tử có một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    4
    1 2 3 4
    2

    3 4 1 2

    Với l = [1, 2, 3, 4] và k = 2 thì kết quả mong muốn là:
    "3 4 1 2".
     
  • Test mẫu 2:
     
    Input Output

    8
    1 2 3 4 5 6 7 8
    5

    6 7 8 1 2 3 4 5

    Với l = [1, 2, 3, 4, 5, 6, 7, 8] và k = 5 thì kết quả mong muốn là:
    "6 7 8 1 2 3 4 5 ".

Lý thuyết.

Giới thiệu danh sách liên kết vòng.

Danh sách liên kết vòng (Circular Linked List) là một biến thể của Danh sách liên kết (Linked List), trong đó phần tử đầu tiên trỏ tới phần tử cuối cùng và phần tử cuối cùng trỏ tới phần tử đầu tiên.

Cả hai loại Danh sách liên kết đơn (Singly Linked List) và Danh sách liên kết đôi (Doubly Linked List) đều có thể được tạo thành dạng Danh sách liên kết vòng.

Hình ảnh danh sách liên kết vòng:

Tạo tử danh sách liên kết đơn.

 

Tạo từ danh sách liên kết đôi:

 

Việc xử lý trên danh sách liên kết vòng cũng tương tự như danh sách liên kết, nhưng chú ý là không được làm mất tính liên kết vòng trong lúc xử lý.

 

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

struct node{
	int data;
	node *next;
};
node *createNode(int x){
    node *temp = new node;
    temp->next = temp;
    temp->data = x; 
    return temp;
}
void printList(node *l, int k){
	node *p = l;
	for (int i = 0; i < k; i++){
		p = p->next;
	}
	cout << p->data << " ";
	node *p2 = p->next;
	while (p2 != p){
		cout << p2->data << " ";
		p2 = p2->next;
	}
}
node *addTail(node *l, int x){
	node *p = l;
	while (p->next != l){
		p = p->next;
	}
	node *temp = new node;
	temp->data = x;
	temp->next = l;
	p->next = temp;
	p = temp;
	return l;
}
int main(){
	int n, x, k;
	cin >> n;
	cin >> x;
	node *l = createNode(x);
	node *p = l;
	for (int i = 1; i < n; i++){
		cin >> x;
		l = addTail(l, x);
	}
	cin >> k;
	printList(l, k);
	return 0;
}