CTDL và giải thuật - Xuất danh sách tăng và giảm theo số N

Nhập vào một số nguyên dương n, hãy cài đặt một danh sách lên kết đôi để lưu các số từ n giảm về 1 và từ 1 tăng đến n (xem ví dụ để rõ hơn). In ra danh sách liên kết đó, phía sau mỗi phần tử có một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    3

    3 2 1 2 3

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

    7

    7 6 5 4 3 2 1 2 3 4 5 6 7

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

Lý thuyết.

Giới thiệu danh sách liên kết đôi.

Danh sách liên kết đôi (Doubly Linked List) là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa:

  • Một giá trị (Data).
  • Một con trỏ (Next) sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của douList.
  • Một con trỏ (Pre) sẽ trỏ đến phần tử trước của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử đầu tiên của doulist.

Hình ảnh mình họa cho một node trong douList.

 

Hình ảnh đầy đủ của một danh sách liên kết đôi.

 

Khai báo dánh sách liên kết đôi (ngôn ngữ C++).

struct node{
	int data;
	node *next;
	node *pre;
};
struct douList{
	node *head;
	node *tail;
};

Mỗi node trong danh sách liên kết đôi sẽ có hai liên kết là phần tử đầu và cuối của node đó, cho nên để quản lý danh sách liên kết này chúng ta có thể sử dụng hai node là head và tail để lưu node đầu và node cuối của danh sách.

Tạo một node trong dánh sách liên kết đôi l với giá trị của node đầu là x:

douList *createList(int x){
	douList *l = new douList;
	l->head = new node;
	l->head->data = x;
	l->head->pre = NULL;
	l->head->next = NULL;
	l->tail = l->head;
	return l;
}

Thêm phần tử vào đầu douList.

Việc thêm phần tử vào đầu của dánh sách liên kết đôi cũng tương tự như danh sách liên kết đơn với độ phức tạp là O(1).

douList *addHead(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->pre = NULL;
	temp->next = l->head;
	l->head->pre = temp;
	l->head = temp;
	return l;
}

Thêm phần tử vào cuối dánh sách liên kết đôi.

Trong khi để thêm một phần tử và cuối của dánh sách liên kết đơn ta cần độ phức tạp O(n) vì cần phải xác định được node của cùng của danh sách liên kết đơn đó thì đối với danh sách đôi, node cuối cùng đã hoàn toàn đươc xác định (node tail) nên khi ta thêm phần tử vào cuối cùng của douList chỉ cần độ phức tạp là O(1).

douList *addTail(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->next = NULL;
	temp->pre = l->tail;
	l->tail->next = temp;
	l->tail = temp;
	return l;
}

Duyệt dánh sách liên kết đôi.

Để duyệt danh sách liên kết đôi ta có thể dùng hai cách: duyệt từ phần tử đầu, hoặc duyệt từ phần tử cuối.

Ví dụ như để in ra một dánh sách liên kết đơn ta có hai cách sau:

Cách 1: Duyệt theo phần tử đầu:

void printList(douList *l){
	node *p = l->head;
	while (p != NULL){
		cout << p->data << " ";
		p = p->next;
	}
}

Cách 2: Duyệt theo phần tử cuối:

void printList(douList *l){
	node *p = l->tail;
	while (p != NULL){
		cout << p->data << " ";
		p = p->pre;
	}
}

 

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

Với bài này ta có nhiều cách, một trong các cách đó là:

  • Tạo một danh sách liên kết đôi với một giá trị là 1.
  • Thêm các giá trị từ 2 đến n và đầu và cuối của douList.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

struct node{
	int data;
	node *next;
	node *pre;
};
struct douList{
	node *head;
	node *tail;
};
douList *createList(int x){
	douList *l = new douList;
	l->head = new node;
	l->head->data = x;
	l->head->pre = NULL;
	l->head->next = NULL;
	l->tail = l->head;
	return l;
}
douList *addHead(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->pre = NULL;
	temp->next = l->head;
	l->head->pre = temp;
	l->head = temp;
	return l;
}
douList *addTail(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->next = NULL;
	temp->pre = l->tail;
	l->tail->next = temp;
	l->tail = temp;
	return l;
}
void printList(douList *l){
	node *p = l->head;
	while (p != NULL){
		cout << p->data << " ";
		p = p->next;
	}
}

int main(){
	int n;
	cin >> n;
	douList *l = createList(1);
	for (int i = 2; i <= n; i++){
		l = addHead(l, i);
		l = addTail(l, i);
	}
	printList(l);
	return 0;
}