Có phải bạn đang làm bài tập môn cấu trúc dữ liệu danh sách liên kết ? Trong khoa học máy tính, danh sách liên kết (tiếng Anh: linked list) là một tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử chỉ đến phần tử tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện một dãy.
- Giới thiệu List trong thư viện C++
#include <iostream>
#include <list>
using namespace std;
int main(){
list<int>* lst = new list<int>;
lst->push_back(1); // them vao duoi phan tu so 1
lst->push_back(2); // them vao duoi phan tu so 2
// in ra cac phan tu
list<int> :: iterator it;
for(it = lst->begin(); it != lst->end(); ++it)
cout << '\t' << *it;
cout << '\n';
// ket qua ra : 1 2
// Vay no hoat dong và cai dat nhu nao ????
}
- Cài Đặt
Bài tập về danh sách liên kết. Các chức năng: thêm vào đầu, thêm vào đuôi, xóa đầu, xóa đuôi, chèn trước, chèn sau, sắp xếp, chèn sắp xếp, kiểm tra rỗng, truy cập index, xóa, xóa toàn bộ, tính chiều dài, tìm vị trí
#include <iostream>
/* author: Tuan Hoang
email: [email protected]
last fix date: 1/22/2019
MIT license (C) Coppyright TuanHoang on github
LinkedList full methods:
- isEmpty()
- pushHead( newElemnt)
- pushBack( newElement)
- insertAfter( index, newElement)
- insertBefore( index, newElement)
- freeAll() -> delete all
- popHead()
- popBack()
- getBack()
- getHead()
- length()
- at( index)
- removeAt( index)
- insertSort( newElement)
- indexOf( elemnt)
*/
template <class T>
class Node{
public:
T value;
Node* next;
Node()
{
value = 0;
next = NULL;
}
~Node()
{
delete value;
delete next;
next = NULL;
}
Node(const T& value)
{
this->value = value;
this->next = NULL;
}
Node* linkTo(Node* node)
{
this->next = node;
return this;
}
};
template <class T>
class LinkedList{
Node<T>* head;
Node<T>* tail;
Node<T>* nodeAt(int N)
{
Node<T>* cur = head;
for(int i=0; i<N; i++)
cur = cur->next;
return cur;
}
void remove_when_having_1_element()
{
delete head;
head = tail = NULL;
}
Node<T>* getNodeHasValue(const T& lookupedValue)
{
Node<T>* cur = head;
while (cur != NULL)
{
if (cur->value == lookupedValue)
break;
else
cur = cur->next;
}
return cur;
}
public:
LinkedList()
{
head = tail = NULL;
}
bool isEmpty()
{
return head == NULL;
}
void pushHead(const T& newValue)
{
if ( this->isEmpty())
{
head = tail = new Node<T>(newValue);
return;
}
Node<T>* newNode = new Node<T>(newValue);
newNode->linkTo(head);
head = newNode;
}
void pushBack(const T& newValue)
{
if( isEmpty())
{
head = tail = new Node<T>(newValue);
return;
}
tail->linkTo(new Node<T>(newValue));
tail = tail->next;
}
void insertAfter(int n, const T& newValue)
{
Node<T>* A = nodeAt(n);
Node<T>* B = A->next;
Node<T>* newNode = new Node<T>(newValue);
newNode->linkTo(B);
A->linkTo(newNode);
if(A == tail)
tail = tail->next;
}
void insertBefore(int n, const T& newValue)
{
Node<T>* A = nodeAt(n);
/* step1: A_vA -- B
/
NEW_vA
*/
Node<T>* newNode = new Node<T>;
*newNode = *A;
/* step2: A_vA B
| /
NEW_vA
*/
A->linkTo(newNode);
/* step3: A_vNew B
| /
NEW_vA
*/
A->value = newValue;
// if A is tail, newNode is new tail pos. the tail pass tail flag to newNode
if( A == tail )
tail = tail->next;
}
void freeAll()
{
Node<T>* followerHead;
while (head != NULL)
{
followerHead = head;
head = head->next;
delete followerHead;
}
}
void popHead()
{
if(head == tail)
{
remove_when_having_1_element();
return;
}
Node<T>* helper = head;
head = head->next;
delete helper;
}
void popBack()
{
if( head == tail)
{
this->remove_when_having_1_element();
return;
}
Node<T>* cur = head;
while (cur->next != tail)
cur = cur->next;
Node<T>* previousTail = cur;
delete tail;
tail = previousTail;
tail->linkTo(NULL);
}
T getBack()
{
return tail->value;
}
T getHead()
{
return head->value;
}
int length()
{
int count = 0;
for(Node<T>* cur = head; cur != NULL; cur = cur->next)
count++;
return count;
}
int at(int n)
{
return nodeAt(n)->value;
}
void removeAt(int n)
{
// to delete A, step1: let A become B, step 2: delete B
if (head == tail)
{
remove_when_having_1_element();
return;
}
Node<T>* A = nodeAt(n);
if(A == tail)
this->popBack();
Node<T>* B = A->next;
//step1: A become B
*A = *B;
//step2:
delete B;
}
void insertSort(const T& newValue)
{
if( this->isEmpty()){
this->pushBack(newValue);
return;
}
Node<T>* A = (new Node<T>)->linkTo(head);
Node<T>* B = head;
while( B != NULL && B->value < newValue)
{
A = A->next;
B = B->next;
}
Node<T>* newNode = new Node<T>(newValue);
A->linkTo(newNode);
newNode->linkTo(B);
if ( A == tail)
tail = tail->next;
if ( B == head)
head = newNode;
}
int getPosOf(const T& cmpValue)
{
Node<T>* target = getNodeHasValue(cmpValue);
if(target == NULL)
return -1;
int pos = 0;
for ( Node<T>* cur = head; cur != target; cur = cur->next)
pos++;
return pos;
}
void show(){
std::cout << "---------------------------------------\n";
std::cout << "length of list: " << this->length() << std::endl;
std::cout << "elemetns : ";
for ( Node<T>* cur = head; cur != NULL; cur = cur->next)
std::cout<< cur->value << ", ";
std::cout<< std::endl;
std::cout<< "head : " << getHead() << std::endl;
std::cout<< "tail : " << getBack() << std::endl;
std::cout << "---------------------------------------\n";
}
};
int main(){
LinkedList<int>* lst = new LinkedList<int>;
lst->insertSort(5);
lst->insertSort(2);
lst->insertSort(3);
lst->insertSort(4);
lst->show();
}
Để tạo một list các bạn sử dụng con trỏ và toán tử new trong C++, sau đó các bạn dùng toán tử -> để gọi các phương thức. Chúc các bạn 10 điểm môn cấu trúc dữ liệu <3
Tác Giả src: Tuan Hoang
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?