Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là cực kỳ quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt danh sách liên kết của bài viết này sẽ chỉ trình bày về danh sách liên kết đơn.
I. Danh Sách Liên Kết Đơn C++
Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử (được gọi là một node hay nút) trong danh sách liên kết đơn là một cấu trúc có hai thành phần:
- Thành phần dữ liệu: lưu thông tin về bản thân phần tử đó.
- Thành phần liên kết: lưu địa chỉ phần tử đứng sau trong danh sách, giả dụ phần tử đó là phần tử cuối cùng thì thành phần này bằng NULL.
Đặc điểm của danh sách liên kết đơn
Do danh sách liên kết đơn là 1 cấu trúc dữ liệu động, được tạo nên nhờ việc cấp phát động nên nó có một số đặc điểm sau đây:
- Được cấp phát bộ nhớ khi chạy chương trình
- Có thể đổi thay kích thước qua việc thêm, xóa phần tử
- Kích thước tối đa phụ thuộc vào bộ nhớ khả dụng của RAM
- Các phần tử được lưu trữ ngẫu nhiên (không liên tiếp) trong RAM
Và do tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó mang những đặc điểm sau:
- Chỉ cần nắm được phần tử đầu và cuối là có thể quản lý được danh sách
- Truy cập tới phần tử ngẫu nhiên phải duyệt từ đầu đến vị trí đó
- Chỉ có thể tìm kiếm tuyến tính một phần tử
II. Nối 2 Danh Sách Liên Kết Đơn C++
Bài tập C: Nối hai danh sách liên kết đơn
Bài tập C này giúp bạn làm quen dần với cách tạo danh sách liên kết đơn và cách nối hai danh sách liên kết đơn trong C. Để giải bài tập này, mình sử dụng cấu trúc struct trong C.
Chương trình C
Dưới đây là chương trình C để giải bài tập nối hai danh sách liên kết đơn trong C:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *even = NULL;
struct node *odd = NULL;
struct node *list = NULL;
//tao danh sach lien ket
void insert(int data) {
// cap phat bo nho cho node moi;
struct node *link = (struct node*) malloc(sizeof(struct node));
struct node *current;
link->data = data;
link->next = NULL;
if(data%2 == 0) {
if(even == NULL) {
even = link;
return;
}else {
current = even;
while(current->next != NULL)
current = current->next;
// chen link vao phan cuoi cua list
current->next = link;
}
}else {
if(odd == NULL) {
odd = link;
return;
}else {
current = odd;
while(current->next!=NULL)
current = current->next;
// chen link vao phan cuoi cua list
current->next = link;
}
}
}
void display(struct node *head) {
struct node *ptr = head;
printf("[head] =>");
while(ptr != NULL) {
printf(" %d =>",ptr->data);
ptr = ptr->next;
}
printf(" [null]\n");
}
void combine() {
struct node *link;
list = even;
link = list;
while(link->next!= NULL) {
link = link->next;
}
link->next = odd;
}
int main() {
int i;
for(i=1; i<=10; i++)
insert(i);
printf("Danh sach chan: ");
display(even);
printf("Danh sach le: ");
display(odd);
combine();
printf("Sau khi noi: \n");
display(list);
return 0;
}
Biên dịch chương trình C trên sẽ cho kết quả:
III. Đảo Ngược Danh Sách Liên Kết Đơn C++
Đảo ngược Danh sách liên kết
Với hoạt động này, bạn cần phải cẩn thận. Chúng ta cần làm cho nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết.
Đầu tiên, chúng ta duyệt tới phần cuối của danh sách. Nút này sẽ trỏ tới NULL. Bây giờ điều cần làm là làm cho nút cuối này trỏ tới nút phía trước của nó.
Chúng ta phải đảm bảo rằng nút cuối cùng này sẽ không bị thất lạc, do đó chúng ta sẽ sử dụng một số nút tạm (temp node – giống như các biến tạm trung gian để lưu giữ giá trị). Tiếp theo, chúng ta sẽ làm cho từng nút bên trái sẽ trỏ tới nút trái của chúng.
Sau đó, nút đầu tiên sau nút head sẽ trỏ tới NULL.
Chúng ta sẽ làm cho nút head trỏ tới nút đầu tiên mới bởi sử dụng các nút tạm.
Bây giờ Danh sách liên kết đã bị đảo ngược.
Chương trình minh họa Danh sách liên kết (Linked List) trong C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node
{
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//hien thi danh sach
void printList()
{
struct node *ptr = head;
printf("\n[ ");
//bat dau tu phan dau danh sach
while(ptr != NULL)
{
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//chen link tai vi tri dau tien
void insertFirst(int key, int data)
{
//tao mot link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//tro link nay toi first node cu
link->next = head;
//tro first toi first node moi
head = link;
}
//xoa phan tu dau tien
struct node* deleteFirst()
{
//luu tham chieu toi first link
struct node *tempLink = head;
//danh dau next toi first link la first
head = head->next;
//tra ve link bi xoa
return tempLink;
}
//kiem tra list co trong hay khong
bool isEmpty()
{
return head == NULL;
}
int length()
{
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next)
{
length++;
}
return length;
}
//tim mot link voi key da cho
struct node* find(int key){
//bat dau tim tu first link
struct node* current = head;
//neu list la trong
if(head == NULL)
{
return NULL;
}
//duyet qua list
while(current->key != key){
//neu day la last node
if(current->next == NULL){
return NULL;
}else {
//di chuyen toi next link
current = current->next;
}
}
//neu tim thay du lieu, tra ve link hien tai
return current;
}
//xoa mot link voi key da cho
struct node* deleteKey(int key){
//bat dau tu first link
struct node* current = head;
struct node* previous = NULL;
//neu list la trong
if(head == NULL){
return NULL;
}
//duyet qua list
while(current->key != key){
//neu day la last node
if(current->next == NULL){
return NULL;
}else {
//luu tham chieu toi link hien tai
previous = current;
//di chuyen toi next link
current = current->next;
}
}
//cap nhat link
if(current == head) {
//thay doi first de tro toi next link
head = head->next;
}else {
//bo qua link hien tai
previous->next = current->next;
}
return current;
}
// ham sap xep
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
// ham dao nguoc list
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Danh sach ban dau: ");
//in danh sach
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nGia tri bi xoa:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nDanh sach sau khi da xoa gia tri: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nPhuc hoi danh sach: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL){
printf("Tim thay phan tu: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else {
printf("Khong tim thay phan tu.");
}
deleteKey(4);
printf("Danh sach, sau khi xoa mot phan tu: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL){
printf("Tim thay phan tu: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else {
printf("Khong tim thay phan tu.");
}
printf("\n");
sort();
printf("Danh sach sau khi duoc sap xep: ");
printList();
reverse(&head);
printf("\nDanh sach sau khi bi dao nguoc: ");
printList();
}
Kết quả
Biên dịch và chạy chương trình C trên sẽ cho kết quả:
IV. Nhập Xuất Danh Sách Liên Kết Đơn C++
Tùy theo kiểu danh sách bạn là gì mà cách nhập xuất khác nhau. Bài viết này mình nhập xuất số nguyên nên có phần đơn giản hơn
Mình sẽ nhập vào phần tử cho danh sách liên kết đơn bằng con trỏ. Nếu nhập vào bằng 0 thì sẽ dừng nhập. Thêm phần tử vào danh sách mình sử dụng hàm chèn cuối Insert_Last
// Hàm nhập danh sách số nguyên từ bàn phím
void Input(List &L){
Init(L);
item x;
int i=1;
do{
cout<<"\nNhap phan tu thu "<<i<<": ";
cin>>x;
if (x!=0){
Insert_Last(L,x);
i++;
}
}
while (x!=0); // Nếu nhập x = 0 thì dừng nhập
//Ban co the dung cach khac
V. Sắp Xếp Danh Sách Liên Kết Đơn C++
Ở phần sắp xếp phần tử trong danh sách liên kết đơn, mình sẽ thực hiện sắp xếp bằng cách so sánh và đổi thay giá trị data chứ không thay đổi Node. Tức là chỉ so sánh các giá trị data rồi sắp xếp, các Node vẫn giữ nguyên không dịch chuyển.
Thao tác sắp xếp trong danh sách về căn bản tương tự như những thuật toán sắp xếp khác, đơn giản chỉ là duyệt từng phần tử rồi so sánh với nhau, sau ấy hoán đổi vị trí của chúng.
Đầu tiên ta có một vòng lặp For sử dụng biến pTmp để lặp từng phần tử trong danh sách, vòng lặp For thứ hai sử dụng biến pTmp2 để lặp từng phần tử trong danh sách.
Nếu pTmp > pTmp2 thì hoán đổi vị trí giữa chúng, nếu pTmp < pTmp2 thì tiếp tục so sách những phần tử tiếp theo, cứ như vậy cho tới hết danh sách.
/* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */
void SortList(SingleList &list)
{
// for loop thứ nhất
for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext)
{
//for loop thứ hai
for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
{
if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí
{
int tmp=pTmp->data;
pTmp->data=pTmp2->data;
pTmp2->data=tmp;
}
}
}
}
VI. Cài Đặt Danh Sách Liên Kết Đơn C++
Trước lúc đi vào cài đặt danh sách liên kết đơn, hãy chắc chắn rằng bạn đã nắm vững phần con trỏ và cấp phát động trong C++. Do danh sách liên kết đơn là một cấu trúc dữ liệu động, nếu bạn không nắm vững con trỏ và cấp phát động sẽ rất khó để bạn hiểu được bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời gian để xem bài viết này của mình. Còn bây giờ thì bắt đầu thôi!
Tạo node
Danh sách liên kết đơn được tạo thành từ nhiều node, do đó, chúng ta sẽ cùng đi từ node trước. Một node gồm hai thành phần là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu có thể là kiểu dữ liệu có sẵn hoặc bạn tự định nghĩa (struct hay class…), trong bài viết này để đơn giản mình sẽ dùng kiểu int cho phần dữ liệu. Thành phần liên kết là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này trỏ đến node tiếp theo, do đó, con trỏ này là con trỏ trỏ vào 1 node.
struct Node
{
int data;
Node* next;
};
Để tạo một node mới, ta thực hiện cấp phát động cho node mới, khởi tạo giá trị ban đầu và trả về địa chỉ của node mới được cấp phát.
Tạo danh sách liên kết đơn
Ta đã có được thành phần tạo nên danh sách liên kết đơn là node, tiếp theo chúng ta cần quản lý chúng bằng phương pháp biết được phần tử đầu và cuối. Vì mỗi phần tử đều liên kết với phần tử kế vậy nên tả chỉ cần biết phần tử đầu và cuối là có thể quản lý được danh sách này. Vậy đơn giản ta cần tạo 1 cấu trúc lưu trữ địa chỉ phần tử đầu (head) và phần tử cuối (hay phần tử đuôi tail).
struct LinkedList
{
Node* head;
Node* tail;
};
Khi mới tạo danh sách, danh sách sẽ không có phần tử nào, do đó head và tail không trỏ vào đâu cả, ta sẽ gán chúng bằng NULL. Ta xây dựng hàm tạo danh sách như sau:
void CreateList(LinkedList& l)
{
l.head = NULL;
l.tail = NULL;
}
Bây giờ để tạo một danh sách, ta làm như sau:
LinkedList list; CreateList(list); // Gán head và tail bằng NULL
Thêm phần tử vào danh sách
Thêm vào đầu
Để thêm node vào đầu danh sách, trước tiên ta cần kiếm tra xem danh sách đó có rỗng hay không, nếu danh sách rỗng, ta chỉ cần gán head và tail của danh sách bằng node đó. Ngược lại nếu danh sách không rỗng, ta thực hiện trỏ thành phần liên kết vào head, sau đó gán lại head bằng node mới.
Như trong hình trên, chúng ta thêm node có data bằng 0 vào danh sách. Ta thực hiện trỏ next của node đó vào head của danh sách (chính là node đầu tiên của danh sách có data bằng 1), sau đó ta trỏ head vào node có data 0 vừa được thêm. Vậy là phần tử đó đã nằm ở đầu danh sách rồi.
Thêm vào cuối
Tương tự, để thêm node vào cuối danh sách, đầu tiên ta đánh giá xem danh sách rỗng hay không, rỗng thì gán head và tail đều bằng node mới. Nếu không rỗng, ta thực hiện trỏ tail->next vào node mới, sau đó gán lại tail bằng node mới (vì bây giờ node mới thêm chính là tail).
Trong hình trên, chúng ta thực hiện thêm node có data bằng 6 vào danh sách. Tail hiện tại là node có data 5, thực hiện gán tail->next bằng node mới để nối thêm nó vào đuôi danh sách, lúc này node mới trở thành phần tử cuối danh sách nên ta gán tail lại bằng node mới.
Thêm vào sau node bất kỳ
Để thêm một node p vào sau node q bất kỳ, đầu tiên ta cần kiếm tra xem node q có NULL hay không, nếu node q là NULL tức là danh sách rỗng, vậy thì ta sẽ thêm vào đầu danh sách. Nếu node q không NULL, tức là tồn tại trong danh sách, ta thực hiện trỏ p->next = q->next, sau đó q->next = p. Tiếp theo chúng ta kiểm tra xem node q trước đó có phải là node cuối hay không, nếu node q là node cuối thì thêm p vào, p sẽ thành node cuối nên ta gán lại tail = p.
Trong hình trên, ta thêm node có data bằng 4 (node p) vào sau node có data bằng 3 (node q). Ta trỏ next của node p vào next của node q tức là node có data bằng 5, sau đó trỏ next của node q vào node p vậy là node p đã được thêm vào danh sách.
Xóa phần tử khỏi danh sách
Xóa ở đầu
Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách đó có rỗng hay không, nếu rỗng, ta không cần xóa, trả về kết quả là 0. Nếu danh sách không rỗng, ta thực hiện lưu node head lại, sau đó gán head bằng next của node head, sau đó xóa node head đi. Tiếp theo ta cần kiểm tra xem danh sách vừa bị xóa đi node head có rỗng hay không, nếu rỗng ta gán lại tail bằng NULL luôn sau đó trả về kết quả 1.
Lưu ý trước khi xóa node head đi, ta dùng biến tham chiếu x để lưu trữ lại giá trị của node bị hủy để sử dụng.
Trong hình trên, mình thực hiện xóa node đầu tiên có data bằng 0. Mình trỏ head đến next của node 0 (hiện đang là head), thì head lúc này sẽ là node 1, sau đó mình hủy đi node 0 là được.
Xóa ở sau node bất kỳ
Để xóa một node p sau node q bất kỳ, ta kiểm tra xem node q có NULL hay không, nếu node q NULL thì không tồn tại trong danh sách, do đó trả về 0, không xóa. Nếu node q khác NULL nhưng next của q là NULL, tức là p bằng NULL thì không xóa, trả về 0 (do sau q không có node nào cả, q là tail). Nếu node p tồn tại, ta thực hiện kiểm tra xem node p có phải là tail hay không, nếu node p là tail thì gán lại tail là q, tức là node trước đó để xóa node p đi.
Trong hình trên, ta thực hiện xóa node có data 3 (node p) sau node có data 2 (node q). Ta trỏ next của node q vào next của node p tức là node có data 4, sau đó xóa node p đi là xong.
Duyệt danh sách và in
Sau khi có các thao tác thêm, xóa, chúng ta có thể in ra danh sách để kiểm tra xem có hoạt động đúng hay không. Để in danh sách, ta duyệt từ đầu đến cuối danh sách và in ra trong lúc duyệt. Ta gán một node bằng head, sau đó kiểm tra xem node đó có NULL hay không, không thì in ra data của node đó, sau đó gán tiếp node đó bằng next của chính nó tức node đó bây giờ là node tiếp theo, cứ như vậy cho đến hết.
Lấy giá trị node bất kỳ
Để lấy giá trị phần tử trong danh sách, ta thực hiện duyệt tương tự như khi in phần tử. Ta sẽ tạo một biến đếm để biết vị trí hiện tại, duyệt qua các node cho đến khi node bằng NULL hoặc biến đếm bằng với vị trí node cần lấy. Kiểm tra xem nếu node khác NULL và biến đếm bằng vị trí cần lấy, ta sẽ trả về địa chỉ của node đó, ngược lại trả về NULL (danh sách rỗng hoặc là vị trí cần lấy nằm ngoài phạm vi của danh sách).
Tìm kiếm phần tử trong danh sách
Ý tưởng tìm kiếm phần tử cũng là duyệt danh sách, nếu như chưa tìm thấy thì tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ cần kiểm tra xem node duyệt có bằng NULL hay không, nếu không tức là đã tìm thấy, ta sẽ trả về địa chỉ của node đó.
Đếm số phần tử của danh sách
Đếm số phần tử thì cũng tương tự, ta áp dụng duyệt từ đầu đếm cuối và đếm số node.
Xóa danh sách
Để xóa danh sách, ta cần hủy tất cả các node tức là duyệt và hủy từng node. Ở đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán một node bằng head, kiểm tra nếu node đó khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp, cứ lặp như vậy cho đến khi node đó NULL thì thôi. Sau khi xóa hết tất cả phần tử thì gán lại tail bằng NULL.
VII. Code Danh Sách Liên Kết Đơn Sinh Viên C++
Đề bài: Xây dựng chương trình quản lý sinh viên bằng DSLK đơn
Cho 1 sinh viên có cấu trúc: mã (int), tên (char *). Dùng danh sách liên kết đơn với con trỏ phead để thao tác:
- Khởi tạo list dạng con trỏ
- Thêm node vào cuối danh sách
- Sắp xếp theo mã
- Xóa node
Chương trình quản lý sinh viên sử dụng DSLK đơn
Chúng ta sẽ lần lượt tạo cấu trúc sinh viên, cấu trúc danh sách liên kết đơn và các thao tác liên quan.
Đầu tiên chúng ta buộc phải tạo một cấu trúc sinh viên với mã số sinh viên ma và tên sinh viên ten.
//tao cau truc sinh vien
struct SinhVien
{
int ma;
char ten[150];
};
Tiếp đến tạo cấu trúc dữ liệu của danh sách liên kết đơn với giá trị data và con trỏ pNext. Khởi tạo giá trị cho pHead và pTail bằng NULL.
//tao cau truc danh sach lien ket don
struct Node
{
SinhVien *data;
Node *pNext;
};
struct SingleList
{
Node *pHead;
};
//khoi tao danh sach lien ket don
void Initialize(SingleList *&list)
{
list=new SingleList;
list->pHead=NULL;
}
Tạo 1 hàm NhapSinhVien() dùng cấu trúc SinhVien để nhập những thông tin của sinh viên như: MSSV và tên sinh viên
SinhVien *NhapSinhVien()
{
SinhVien *sv=new SinhVien;
cout<<"Nhap MSSV:";
cin>>sv->ma;
cin.ignore();
cout<<"Nhap ho va ten:";
gets(sv->ten);
return sv;
}
Bây giờ chúng ta bắt đầu tạo Node với các thông tin của cấu trúc SinhVien, sau đó thêm Node vào cuối danh sách.
//tao node sinh vien
Node *CreateNode(SinhVien *sv)
{
Node *pNode=new Node;
if(pNode!=NULL)
{
pNode->data=sv;
pNode->pNext=NULL;
}
else
{
cout<<"cap phat bo nho that bai!!!";
}
return pNode;
}
//them node vao cuoi danh sach
void InsertLast(SingleList *&list,SinhVien *sv)
{
Node *pNode=CreateNode(sv);
if(list->pHead==NULL)
{
list->pHead=pNode;
}
else
{
Node *pTmp=list->pHead;
while(pTmp->pNext!=NULL)
{
pTmp=pTmp->pNext;
}
pTmp->pNext=pNode;
}
}
Sau lúc thêm Node vào danh sách ta thực hiện những thao tác theo đề nghị của đề bài. Đầu tiên là việc sắp xếp các sinh viên theo MSSV.
Ở bài tìm kiếm và sắp xếp trong danh sách liên kết đơn mình đã giới thiệu các bạn thao tác sắp xếp. Dựa vào đó ta chỉ cần biến đổi một chút sẽ có ngay hàm sắp xếp SortList() theo MSSV.
void SortList(SingleList *&list)
{
for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext)
{
for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
{
SinhVien *svTmp=pTmp->data;
SinhVien *svTmp2=pTmp2->data;
if(svTmp2->ma<svTmp->ma)
{
int ma=svTmp->ma;
char ten[150];
strcpy(ten,svTmp->ten);
svTmp->ma=svTmp2->ma;
strcpy(svTmp->ten,svTmp2->ten);
svTmp2->ma=ma;
strcpy(svTmp2->ten,ten);
}
}
}
}
Tương tự như hàm sắp xếp, để xóa một sinh viên dựa vào tên ta thực hiện vòng lặp while lặp từng phần tử trong danh sách. Nếu phần tử đó trùng với phần tử được nhập vào từ bàn phím ta thực hiện delete phần tử đó ra khỏi danh sách.
void RemoveNode(SingleList *&list,int ma)
{
Node *pDel=list->pHead;
if(pDel==NULL)
{
cout<<"Danh sach rong!";
}
else
{
Node *pPre=NULL;
while(pDel!=NULL)
{
SinhVien *sv=pDel->data;
if(sv->ma==ma)
break;
pPre=pDel;
pDel=pDel->pNext;
}
if(pDel==NULL)
{
cout<<"khong tim thay MSSV: "<<ma;
}
else
{
if(pDel==list->pHead)
{
list->pHead=list->pHead->pNext;
pDel->pNext=NULL;
delete pDel;
pDel=NULL;
}
else
{
pPre->pNext=pDel->pNext;
pDel->pNext=NULL;
delete pDel;
pDel=NULL;
}
}
}
}
Sau khi thực hiện tạo các thao tác, ta chỉ cần tạo hàm main() và gọi các thao tác đó ra để sử dụng.
int main(int argc, char** argv) {
SingleList *list;
Initialize(list);
SinhVien *teo=NhapSinhVien();
InsertLast(list,teo);
SinhVien *ty=NhapSinhVien();
InsertLast(list,ty);
SinhVien *bin=NhapSinhVien();
InsertLast(list,bin);
PrintList(list);
SortList(list);
cout<<"\nSau khi sap xep:\n";
PrintList(list);
cout<<"\Ban muon xoa sinh vien co MSSV: ";
int ma;
cin>>ma;
RemoveNode(list,ma);
cout<<"\nSau khi xoa:\n";
PrintList(list);
}
Full code:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
//tao cau truc sinh vien
struct SinhVien
{
int ma;
char ten[150];
};
//tao cau truc danh sach lien ket don
struct Node
{
SinhVien *data;
Node *pNext;
};
struct SingleList
{
Node *pHead;
};
//khoi tao danh sach lien ket don
void Initialize(SingleList *&list)
{
list=new SingleList;
list->pHead=NULL;
}
//nhap thong tin sinh vien
SinhVien *NhapSinhVien()
{
SinhVien *sv=new SinhVien;
cout<<"Nhap MSSV:";
cin>>sv->ma;
cin.ignore();
cout<<"Nhap ho va ten:";
gets(sv->ten);
return sv;
}
//tao node sinh vien
Node *CreateNode(SinhVien *sv)
{
Node *pNode=new Node;
if(pNode!=NULL)
{
pNode->data=sv;
pNode->pNext=NULL;
}
else
{
cout<<"cap phat bo nho that bai!!!";
}
return pNode;
}
//them node vao cuoi danh sach
void InsertLast(SingleList *&list,SinhVien *sv)
{
Node *pNode=CreateNode(sv);
if(list->pHead==NULL)
{
list->pHead=pNode;
}
else
{
Node *pTmp=list->pHead;
while(pTmp->pNext!=NULL)
{
pTmp=pTmp->pNext;
}
pTmp->pNext=pNode;
}
}
//hien thi danh sach
void PrintList(SingleList *list)
{
Node *pTmp=list->pHead;
if(pTmp==NULL)
{
cout<<"Danh sach rong";
return;
}
while(pTmp!=NULL)
{
SinhVien *sv=pTmp->data;
cout<<sv->ma<<"\t"<<sv->ten<<"\n";
pTmp=pTmp->pNext;
}
}
//sap xep
void SortList(SingleList *&list)
{
for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext)
{
for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
{
SinhVien *svTmp=pTmp->data;
SinhVien *svTmp2=pTmp2->data;
if(svTmp2->ma<svTmp->ma)
{
int ma=svTmp->ma;
char ten[150];
strcpy(ten,svTmp->ten);
svTmp->ma=svTmp2->ma;
strcpy(svTmp->ten,svTmp2->ten);
svTmp2->ma=ma;
strcpy(svTmp2->ten,ten);
}
}
}
}
//xoa
void RemoveNode(SingleList *&list,int ma)
{
Node *pDel=list->pHead;
if(pDel==NULL)
{
cout<<"Danh sach rong!";
}
else
{
Node *pPre=NULL;
while(pDel!=NULL)
{
SinhVien *sv=pDel->data;
if(sv->ma==ma)
break;
pPre=pDel;
pDel=pDel->pNext;
}
if(pDel==NULL)
{
cout<<"khong tim thay MSSV: "<<ma;
}
else
{
if(pDel==list->pHead)
{
list->pHead=list->pHead->pNext;
pDel->pNext=NULL;
delete pDel;
pDel=NULL;
}
else
{
pPre->pNext=pDel->pNext;
pDel->pNext=NULL;
delete pDel;
pDel=NULL;
}
}
}
}
int main(int argc, char** argv) {
SingleList *list;
Initialize(list);
SinhVien *teo=NhapSinhVien();
InsertLast(list,teo);
SinhVien *ty=NhapSinhVien();
InsertLast(list,ty);
SinhVien *bin=NhapSinhVien();
InsertLast(list,bin);
PrintList(list);
SortList(list);
cout<<"\nSau khi sap xep:\n";
PrintList(list);
cout<<"\Ban muon xoa sinh vien co MSSV: ";
int ma;
cin>>ma;
RemoveNode(list,ma);
cout<<"\nSau khi xoa:\n";
PrintList(list);
cout<<"\n---------------------------\n";
cout<<"Chuong trinh nay duoc dang tai Freetuts.net";
}
Kết quả:
VIII. Xóa Phần Tử Trong Danh Sách Liên Kết Đơn C++
Trong chỉ dẫn này mình sẽ giới thiệu tới các bạn cách xóa Node trong danh sách liên kết đơn.
Chúng ta sẽ cùng nhau tìm hiểu 3 ví dụ lúc xóa 1 Node khỏi danh sách liên kết đơn:
- Xóa Node ở đầu danh sách liên kết đơn.
- Xóa Node ở cuối danh sách liên kết đơn.
- Xóa Node ở giữa danh sách liên kết đơn.
+ Xóa Node ở đầu danh sách liên kết đơn
Trong trường hợp chúng ta muốn xóa một Node, mà Node đó lại nằm ở đầu danh sách. Đây là một trường hợp đặc biệt, các bạn hãy xem các bước thực hiện sau đây:
Giả sử chúng ta có một Node pDel là Node cần xóa và một danh sách liên kết đơn.
Bước 1: Vì Node cần xóa ở đầu danh sách, tức là ngay node pHead. Vì vậy chúng ta cần di chuyển pHead từ pDel sang Node kế tiếp: list.pHead = list.pHead -> pNext
Bước 2: Sau khi di chuyển pHead sang Node kế tiếp, chúng ta sẽ ngắt mối liên kết giữa pDel với Node phía sau nó: pDel -> pNext = Null.
Bước 3: Bây giờ pDel không còn liên kết với bất kì Node nào trong danh sách nữa, chúng ta đã có thể xóa Node này. delete pDel
// Nếu pDel == list.pHead, tức là số cần xóa ở đầu danh sách
if(pDel == list.pHead){
list.pHead = list.pHead -> pNext;
pDel -> pNext = NULL;
delete pDel;
pDel = NULL;
}
+ Xóa Node ở cuối danh sách liên kết đơn.
Trong trường hợp Node muốn xóa lại nằm ở cuối danh sách, tương tự như việc xóa ở đầu danh sách. Ta chỉ cần di chuyển pTail về Node trước đó (pPre) và thay đổi pNext = NULL.
Sau khi di chuyển pTail về Node trước đó và ngắt mối liên kết giữa pPre với pDel, ta thực hiện xóa Node pDel: delete pDel
//Nếu pDel == list.pTail, tức là số cần xóa ở cuối danh sách
if(pDel -> pNext == NULL){
list.pTail = pPre;
pPre -> pNext = NULL;
delete pDel;
pDel = NULL;
}
+ Xóa Node ở giữa danh sách liên kết đơn.
Và trường hợp cuối cùng, khi xóa Node mà Node đó không nằm đầu cũng không nằm cuối danh sách, ta thực hiện các bước như sau:
Khi ta muốn xóa một Node ở giữa danh sách, đầu tiên ta cần xác định Node cần xóa pDel và Node đứng trước nó pPre.
Sau khi xác định được pDel và pPre, ta thay đổi mối liên kết giữa pPre đến pTail (pPre -> pNext = pDel -> pNext) và cho pDel -> pNext == NULL. Các bạn có thể xem hướng mũi tên để biết được các bước thực hiện của nó.
Ta có thể xóa Node pDel khi đã ngắt mối liên kết giữa nó với các Node khác: delete pDel
// và trường hợp cuối cùng số muốn xóa nằm ở giữa danh sách
else{
pPre -> pNext = pDel -> pNext;
pDel -> pNext = NULL;
delete pDel;
pDel = NULL;
}
+ Ví dụ xóa Node trong danh sách liên kết đơn
Chúng ta sẽ sử dụng dữ liệu ở ví dụ trước để thực hiện xóa cho ví dụ này, vừa có thể ôn lại kiến thức cũ vừa áp dụng kiến thức mới.
#include <iostream>
using namespace std;
/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
int data;// giá trị data của node
Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
Node *pHead; //Node đầu pHead
Node *pTail; // Node cuối pTail
};
/* khởi tạo giá trị cho Node đầu và Node cuối */
void Initialize(SingleList &list)
{
list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}
/* Đếm số phần tử trong danh sách */
int SizeOfList(SingleList list)
{
Node *pTmp=list.pHead;
int nSize=0;
while(pTmp!=NULL)
{
pTmp=pTmp->pNext;
nSize++;
}
return nSize;
}
/* tạo Node trong danh sách liên kết đơn */
Node *CreateNode(int d)
{
Node *pNode=new Node; //sử dụng pNode để tạo một Node mới
if(pNode!=NULL) // Nếu pNode != Null, tức là pNode có giá trị thì
{
pNode->data=d; // gán giá trị data cho d
pNode->pNext=NULL;// và cho con trỏ pNext trỏ tới giá trị Null
}
else // Nếu pNode == Null, tức là pNode không có giá trị thì xuất thông tin
{
cout<<"Error allocated memory";
}
return pNode;//trả về pNode
}
/* chèn Node đầu danh sách */
void InsertFirst(SingleList &list,int d)
{
Node *pNode=CreateNode(d);
if(list.pHead==NULL)
{
list.pHead=list.pTail=pNode;
}
else
{
pNode->pNext=list.pHead;
list.pHead=pNode;
}
}
/* chèn node vào cuối danh sách */
void InsertLast(SingleList &list,int d)
{
Node *pNode=CreateNode(d);
if(list.pTail==NULL)
{
list.pHead=list.pTail=pNode;
}
else
{
list.pTail->pNext=pNode;
list.pTail=pNode;
}
}
/* chèn node vào giữa danh sách */
void InsertMid(SingleList &list, int pos, int d){
// Nếu pos < 0 hoặc pos lớn hơn kích thước của danh sách thì reuturn
if(pos < 0 || pos >= SizeOfList(list)){
cout<<"Không thể chèn Node!!!";
return;
}
// Nếu pos == 0 thì gọi hàm InsertFirst
if(pos == 0){
InsertFirst(list, d);
}
//Nếu pos == SizeOfList - 1 thì gọi hàm InsertLast
else if(pos == SizeOfList(list)-1){
InsertLast(list, d);
}
//Ngược lại thì thay đổi mối liên kết giữa các phần tử, cụ thể:
else{
Node *pNode = CreateNode(d);
Node *pIns = list.pHead;
Node *pPre = NULL;
int i = 0;
//thực hiện vòng lặp tìm pPre và pIns
while(pIns != NULL){
if(i == pos)
break;
pPre = pIns;
pIns = pIns ->pNext;
i++;
}
//sau khi tìm được thì thay đổi con trỏ pNext
pPre ->pNext=pNode;
pNode->pNext=pIns;
}
}
/* xóa node khỏi danh sách liên kết */
void RemoveNode(SingleList &list, int d){
Node *pDel = list.pHead; // tạo một node pDel để xóa
//Nếu pDel == Null thì danh sách rỗng
if(pDel == NULL){
cout<<"Danh sách rỗng!!";
}
//ngược lại thì xét điều kiện
else{
Node *pPre = NULL;
//dùng vòng lặp while để tìm ra pDel và pPre (vị trí đứng trước pDel)
while(pDel != NULL){
if(pDel -> data == d){
break;
}
pPre = pDel;
pDel = pDel -> pNext;
}
//Nếu pDel == null tức là không tìm thấy số cần xóa
if(pDel == NULL){
cout<<"Không tìm thấy số cần xóa";
}
// Ngược lại tiếp tục xét điều kiện
else{
// Nếu pDel == list.pHead, tức là số cần xóa ở đầu danh sách
if(pDel == list.pHead){
list.pHead = list.pHead -> pNext;
pDel -> pNext = NULL;
delete pDel;
pDel = NULL;
}
//Nếu pDel == list.pTail, tức là số cần xóa ở cuối danh sách
else if(pDel -> pNext == NULL){
list.pTail = pPre;
pPre -> pNext = NULL;
delete pDel;
pDel = NULL;
}
// và trường hợp cuối cùng số muốn xóa nằm ở giữa danh sách
else{
pPre -> pNext = pDel -> pNext;
pDel -> pNext = NULL;
delete pDel;
pDel = NULL;
}
}
}
}
/* hàm xuất dữ liệu */
void PrintList(SingleList list)
{
Node *pTmp=list.pHead;
if(pTmp==NULL)
{
cout<<"The list is empty!";
return;
}
while(pTmp!=NULL)
{
cout<<pTmp->data<<" ";
pTmp=pTmp->pNext;
}
}
int main() {
SingleList list;
Initialize(list);
//Thêm node đầu danh sách
InsertFirst(list, 5);
InsertFirst(list, 7);
InsertFirst(list, 3);
cout<<"Các Node trong danh sách sau khi InsertFirst là: ";
PrintList(list);
//Thêm node cuối danh sách
InsertLast(list, 4);
InsertLast(list, 2);
InsertLast(list, 6);
cout<<"\nCác Node trong danh sách sau khi InsertLast là: ";
PrintList(list);
//Thêm node giữa danh sách
InsertMid(list, 4, 11);
InsertMid(list, 2, 12);
InsertMid(list, 3, 13);
cout<<"\nCác Node trong danh sách sau khi InsertMid là: ";
PrintList(list);
//Xóa node khỏi danh sách
RemoveNode(list, 3);
RemoveNode(list, 11);
RemoveNode(list, 6);
cout<<"\nCác Node trong danh sách sau khi xóa là: ";
PrintList(list);
cout<<"\n-------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}
Kết quả:
IX. Bài Tập Danh Sách Liên Kết Đơn C++
Bài tập danh sách liên kết đơn dưới đây là 1 dạng bài tập tổng hợp giúp những bạn ôn luyện lại kiến thức về danh sách liên kết đơn cũng như các kiến thức khác về lập trình C. Sau bài học này, bên cạnh kiến thức về danh sách liên kết đơn, bạn cũng sẽ nắm được:
- Đọc ghi tệp trong ngôn ngữ C
- Cách xử lý dữ liệu văn bản trong C: tách chuỗi, chuyển chuỗi về số, …
- Làm việc với kiểu dữ liệu tự định nghĩa (structure)
- Và các kiến thức căn bản khác của lập trình C
Đề bài tập danh sách liên kết đơn
Viết chương trình trong ngôn ngữ C thực hiện các bắt buộc sau:
- Khai báo cấu trúc dữ liệu để tổ chức danh sách liên kết đơn quản lý các tỉnh/thành phố của Việt Nam. Thông tin của mỗi tỉnh/thành phố bao gồm: Mã tỉnh, tên tỉnh, diện tích, dân số.
- Cài đặt các thao tác cơ bản (thêm ở vị trí bất kỳ; sửa, xóa theo mã (code), duyệt danh sách).
- Tính tổng diện tích của tất cả các tỉnh thành.
- Tìm vị trí của node của tỉnh có diện tích lớn nhất.
- Tìm tỉnh/thành phố có dân số lớn nhất.
- Sắp xếp danh sách theo mã tỉnh/thành phố.
- Sắp xếp danh sách tăng dần theo diện tích.
Yêu cầu:
- Viết chương trình cụ thể hóa những chức năng trên, người sử dụng có thể tương tác qua menu cho phép lựa chọn chức năng mà họ muốn.
- Ban đầu, danh sách tỉnh/thành phố được nhập tự động từ 1 tập tin (Text file .txt) cho trước có nội dung
Lời giải bài tập danh sách liên kết đơn
+ Xây dựng các kiểu dữ liệu cần thiết
- Chúng ta cần định nghĩa kiểu dữ liệu City theo yêu cầu của đề bài, gồm có các trường mã (code), tên (name), diện tích (area) và dân số (population).
- Chúng ta cũng cần định nghĩa kiểu dữ liệu cho 1 Node của danh sách liên kết, mỗi Node sẽ gồm dữ liệu và con trỏ next.
- Trong bài này, mình giả sử code (mã tỉnh,thành phố) là không trùng lặp nên sẽ bỏ qua bước kiểm tra.
// Khai báo kiểu cấu trúc City
struct City {
int code;
char name[100];
float area;
int population;
};
// Định nghĩa cho kiểu "struct City" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct City" thì ta chỉ cần dùng "City"
typedef struct City City;
// Khai báo kiểu cấu trúc LinkedList
struct LinkedList{
City city;
struct LinkedList *next;
};
// Định nghĩa cho kiểu "struct LinkedList" 1 tên mới ngắn gọn hơn, thay vì khai báo kiểu "struct LinkedList" thì ta chỉ cần dùng "Node"
typedef struct LinkedList *Node;
+ Xây dựng các hàm khởi tạo
- Với danh sách liên kết, chúng ta cũng cần khởi tạo Node đầu tiên cho nó, việc khởi tạo rất đơn giản chỉ bằng cách gán Node đó bằng NULL, tức là chưa có dữ liệu (chưa có Node nào cả)
// Hàm khởi tạo Node đầu tiên của LinkedList
Node initHead(){
Node head;
head = NULL;
return head;
}
- Chúng ta cũng sẽ cần hàm khởi tạo 1 Node khi đã có dữ liệu của Node đó. Sau khi khởi tạo thì chúng ta có thể thêm nó vào danh sách.
// Hàm tạo mới 1 Node trong LinkedList
Node createNode(City city){
Node temp; // Khai báo 1 Node
temp = (Node)malloc(sizeof(struct LinkedList)); // Cấp phát vùng nhớ cho Node
temp->next = NULL;// Cho next trỏ tới NULL
temp->city = city; // Gán giá trị cho Node
return temp;
}
Lưu ý: Ta cần cho con trỏ next của Node được khởi tạo bằng NULL, tức là chưa trỏ tới đâu. Tránh trường hợp nó trỏ lung tung trong bộ nhớ.
- Chúng ta cần có 1 hàm khởi tạo giá trị cho kiểu City đã định nghĩa ở trên qua stdin (nhập từ console). Lý do là bởi chương trình của chúng ta có chức năng thêm, sửa dữ liệu của 1 Node. Khi đó, ta sẽ gọi tới hàm này để tạo dữ liệu thông qua stdin.
City createCity(){
City newCity;
printf("Nhap code: ");
scanf("%d", &newCity.code);
printf("Nhap ten: ");
getchar(); // Bỏ qua '\n' trong bộ đệm
fgets(newCity.name, 100, stdin);
// Xóa \n ở cuối chuỗi vừa nhập nếu có
if ((p=strchr(newCity.name, '\n')) != NULL){
*p = '\0';
}
printf("Nhap dien tich: ");
scanf("%f", &newCity.area);
printf("Nhap dan so: ");
scanf("%d", &newCity.population);
return newCity;
}
Lưu ý:
- Chúng ta cần hàm getchar() để xóa bộ đệm, cụ thể là xóa bỏ ký tự ‘\n’ còn sót ở lần nhập mã tỉnh/thành phố trước đó. Nếu không xóa, hàm nhập chuỗi sẽ nhận biết ‘\n’ trong bộ đệm là hành động kết thúc nhập chuỗi.
- Hàm fgets() đọc cả newline, nên ta cần xóa đi nếu không muốn trường name (tên) có ký tự này.
+ Các hàm thao tác với danh sách liên kết
Trong bài toán này, chúng ta có các hành động thêm, sửa, xóa Node. Do đó, chúng ta cần xây dựng các hàm sau:
- Hàm addHead: Thêm Node vào đầu DSLK
- Hàm addTail: Thêm Node vào cuối DSLK
- Hàm addAt: Thêm Node vào chỉ số bất kỳ, kế thừa sử dụng hàm addHead và addTail
- Hàm traverser: Duyệt danh sách
- Hàm delHead: Xóa Node đầu tiên của DSLK
- Hàm delTail: Xóa Node cuối của DSLK
- Hàm delAt: Xóa Node tại chỉ số bất kỳ, cũng sẽ kế thừa hàm delHead và delTail ở trên
- Hàm findIndexByCode: Tìm chỉ số của Node trong danh sách theo mã code (mã tỉnh/thành)
Các hàm này đều là hàm cơ bản của DSLK đã được mình trình bày chi tiết tại bài danh sách liên kết đơn. Do vậy, bạn nào chưa hiểu thì có thể quay lại đọc bài đó trước nha.
- Các thao tác với danh sách, mình thích để trong vòng lặp để người dùng có thể lặp lại thao tác đó nếu cần. Người dùng sẽ có quyền chọn có thực hiện thao tác đó tiếp hay không ngay sau khi hoàn thành thao tác.
char option;
while (TRUE) {
// Thao tác ở đây
scanf("%c", &option);
if (option == 'N' || option == 'n'){
break;
}
}
# Hàm duyệt danh sách
void traverser(Node head){
printf("Danh sach hien tai:\n");
printf("------------------------------------------------------------------------------------------------------------\n");
printf("%10s%50s%20s%20s\n", "Ma Tinh/TP", "Tinh thanh", "Dien tich", "Dan so");
for(Node p = head; p != NULL; p = p->next){
printf("%10d%50s%20f%20d\n", p->city.code, p->city.name, p->city.area, p->city.population);
}
printf("------------------------------------------------------------------------------------------------------------\n");
}
- Ở đây, ta đơn giản là bắt đầu từ Node đầu tiên (head) cho tới khi không thể nhảy sang Node tiếp theo.
- Chúng ta in ra dạng bảng bằng cách sử dụng format trong hàm printf().
# Các hàm phục vụ thêm Node
// Thêm vào cuối
Node addTail(Node head, City value){
Node temp,p;// Khai báo 2 Node tạm temp và p
temp = createNode(value);//Gọi hàm createNode để khởi tạo Node temp có next trỏ tới NULL và giá trị là value
if(head == NULL){
head = temp; //Nếu linked list đang trống thì Node temp là head luôn
}
else{
p = head;// Khởi tạo p trỏ tới head
while(p->next != NULL){
p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là Node có next = NULL
}
p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà)
}
return head;
}
// Thêm vào đầu
Node addHead(Node head, City value){
Node temp = createNode(value); // Khởi tạo Node temp với data = value
if(head == NULL){
head = temp; // //Nếu linked list đang trống thì Node temp là head luôn
}else{
temp->next = head; // Trỏ next của temp = head hiện tại
head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà)
}
return head;
}
// Thêm vào ở "chỉ số" (bắt đầu từ 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ 1) thì giảm position đi 1 đơn vị
Node addAt(Node head, City value, int position){
position = position - 1; // Thêm theo vị trí
if(position == 0 || head == NULL){
head = addHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu
}else{
// Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí
int k = 1;
Node p = head;
while(p != NULL && k != position){
p = p->next;
++k;
}
if(k != position){
// Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối
// Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ
head = addTail(head, value);
// printf("Vi tri chen vuot qua vi tri cuoi cung!\n");
}else{
Node temp = createNode(value);
temp->next = p->next;
p->next = temp;
}
}
return head;
}
Kết hợp với hàm khởi tạo City (createCity) phía trên, chúng ta có thể hoàn chỉnh thao tác thêm Node vào danh sách với hàm dưới đây:
Node delHead(Node head){
if(head == NULL){
printf("\nCha co gi de xoa het!");
}else{
head = head->next;
}
return head;
}
Node delTail(Node head){
if (head == NULL || head->next == NULL){
return delHead(head);
}
Node p = head;
while(p->next->next != NULL){
p = p->next;
}
p->next = p->next->next; // Cho next bằng NULL
return head;
}
// Xóa Node ở "chỉ số" (bắt đầu từ 0) bất kỳ
Node delAt(Node head, int position){
if(position == 0 || head == NULL || head->next == NULL){
head = delHead(head); // Nếu vị trí xóa là 0, tức là thêm vào đầu
}else{
// Bắt đầu tìm vị trí cần xóa. Ta sẽ dùng k để đếm cho vị trí
int k = 1;
Node p = head;
while(p->next->next != NULL && k != position){
p = p->next;
++k;
}
if(k != position){
// Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối
// Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ
head = delTail(head);
// printf("Vi tri xoa vuot qua vi tri cuoi cung!\n");
}else{
p->next = p->next->next;
}
}
return head;
}
Ở trên, chúng ta đã có hàm xóa ở chỉ số bất kỳ, vậy để xóa Node theo mã (code) cung cấp. Ta cần viết thêm 1 hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code trùng với giá trị được cung cấp:
// Hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code của nó trùng với giá trị cần tìm
int findIndexByCode(Node head, int code){
int index = -1;
for(Node p = head; p != NULL; p = p->next){
index++;
if (p->city.code == code){
return index;
}
}
return -1; // Không tìm thấy
}
Như vậy, để hoàn chỉnh thao tác xóa Node theo mã tỉnh/thành phố. Ta sẽ thêm 1 hàm sau:
Node removeNode(Node head){
int code;
char option;
while (TRUE) {
printf("========== Chon Node muon xoa ===============\n");
printf("Nhap ma tinh/thanh pho can xoa: ");
scanf("%d", &code);
int position = findIndexByCode(head, code);
if (position < 0){
printf("Khong tim thay du lieu can xoa! Xoa tiep (Y/n)? ");
}else {
head = delAt(head, position);
printf("Xoa thanh cong? Xoa tiep (Y/n)? ");
}
getchar(); // Bỏ qua '\n' trong bộ đệm
scanf("%c", &option);
if (option == 'N' || option == 'n'){
break;
}
}
return head;
}
Các chức năng thêm, xóa Node của danh sách đều có thể thay đổi Node head (Ex: xóa Node head). Do đó, các hàm này đều cần trả về giá trị là Node head mới sau khi thay đổi (có thể vẫn giữ nguyên).
# Hàm sửa giá trị Node trong DSLK
- Hàm này chắc chắn không thể thay đổi Node head, do đó chúng ta sẽ dùng kiểu void
- Đơn giản là ta duyệt qua danh sách, nếu tìm thấy mã code tương ứng, sẽ cho người dùng nhập dữ liệu mới cho Node đó.
void editNode(Node head){
int code;
char option;
City newCity;
while (TRUE) {
printf("========== Chon Node muon sua ===============\n");
printf("Nhap ma tinh/thanh pho can sua: ");
scanf("%d", &code);
int found = 0;
for(Node p = head; p != NULL; p = p->next){
if (p->city.code == code){
found = 1;
newCity = createCity();
p->city = newCity;
break;
}
}
if (found) {
printf("Sua thanh cong! Sua tiep (Y/n)? ");
}else {
printf("Khong tim thay du lieu! Sua tiep (Y/n)? ");
}
getchar(); // Bỏ qua '\n' trong bộ đệm
scanf("%c", &option);
if (option == 'N' || option == 'n'){
break;
}
}
}
# Hàm sắp xếp danh sách
void swapCityData(City *a, City *b){
City tmp = *a;
*a = *b;
*b = tmp;
}
// Hàm sắp xếp
// Nếu sort theo code, thì byCode = 1, byArea = 0
// Nếu sort theo area, thì byCode = 0, byArea = 1
// Nếu sắp xếp tăng dần thì desc = 0, giảm dần thì desc = 1
void sortCities(Node head, int byCode, int byArea, int desc){
for(Node p = head; p != NULL; p = p->next){
for(Node q = p->next; q != NULL; q = q->next){
if (desc){
if (byCode && p->city.code < q->city.code){
swapCityData(&p->city, &q->city);
}else if (byArea && p->city.area < q->city.area){
swapCityData(&p->city, &q->city);
}
}else {
if (byCode && p->city.code > q->city.code){
swapCityData(&p->city, &q->city);
}else if (byArea && p->city.area > q->city.area){
swapCityData(&p->city, &q->city);
}
}
}
}
}
- Hàm swap chúng ta cần dùng con trỏ để hàm sử dụng trực tiếp giá trị được truyền vào. Ta chỉ cần đổi giá trị của chúng cho nhau, chứ không cần đổi 2 Node (rắc rối lắm).
- Mình cố ý rút gọn code bằng cách cho các option sắp xếp vào trong hàm sortCities. Mặc dù không tường minh lắm nhưng tách ra thì dài quá.
- Hàm sắp xếp không thay đổi Node head, nên hàm cũng không cần trả về giá trị như các hàm thêm hay xóa Node.
# Các hàm chức năng khác
Ngoài các hàm thêm, sửa, xóa trên, đề bài còn yêu cầu một số hàm tính tổng diện tích, tìm tỉnh/thành phố có diện tích/dân số lớn nhất, và cả sắp xếp danh sách.
Về cơ bản, các hàm này chỉ cần dựa trên thao tác duyệt danh sách (traveser) là có thể hoàn thành rồi.
// Hàm tính tổng diện tích các thành phố trong DSLK
float sumArea(Node head){
float sum = 0;
for(Node p = head; p != NULL; p = p->next){
sum += p->city.area;
}
return sum;
}
// Hàm tìm chỉ số của Node có diện tích lớn nhất (giả sử chỉ có 1)
// Nếu dữ liệu có nhiều hơn 1, chúng ta tìm max rồi duyệt lại 1 lần nữa để tìm ra các Node có giá trị = max đó
int indexOfMaxArea(Node head){
int maxIndex = 0, index = 0;
int maxArea = head->city.area;
for(Node p = head; p != NULL; p = p->next){
if (p->city.area > maxArea){
maxArea = p->city.area;
maxIndex = index;
}
index++;
}
return maxIndex;
}
// Hàm tìm Node có dân số lớn nhất
City maxByPopulation(Node head){
City city = head->city;
for(Node p = head; p != NULL; p = p->next){
if (p->city.population > city.population){
city = p->city;
}
}
return city;
}
Thao tác đọc dữ liệu từ tệp
Đề bài yêu cầu chúng ta cần khởi tạo danh sách ban đầu bằng cách đọc dữ liệu từ tệp. Do đó, chúng ta cần thêm 1 số hàm con nữa.
– Do dữ liệu tên tỉnh/thành phố có dấu cách nên mình chỉ biết cách đọc từng dòng vào xử lý. Do vậy, mình cần:
- Hàm handleLineData: Tách dòng ra các thành phần con, cụ thể là cho 1 dòng dữ liệu, phải trả về cho mình 1 City. Mình dùng hàm strtok để làm việc tách chuỗi.
- Hàm readData: Đọc dữ liệu từ file, mỗi dòng đọc được sẽ gọi tới hàm handleLineData phía trên. Sau khi có City, ta thêm nó vào danh sách bằng cách gọi tới addTail hoặc addHead hoặc addAt
// Hàm tách các thành phần của 1 dòng trong file
City handleLineData(char *line){
City city;
city.code = INVALID_CITY_CODE; // Khởi tạo giá trị không hợp lệ. Về sau ta có thể kiểm tra.
const char delimiter[] = "\t";
char *tmp;
tmp = strtok(line, delimiter);
if (tmp == NULL) {
printf("Du lieu khong dung dinh dang: %s", line);
exit(EXIT_FAILURE);
}
city.code = atoi(tmp);
int index = 0;
for (;;index++) {
tmp = strtok(NULL, delimiter);
if (tmp == NULL)
break;
if (index == 0){
strcpy(city.name, tmp);
}else if (index == 1){
city.area = (float)atof(tmp);
}else if (index == 2){
city.population = atoi(tmp);
}else {
printf("Du lieu khong dung dinh dang: %s", line);
exit(EXIT_FAILURE);
}
}
return city;
}
// Hàm đọc dữ liệu từ tập tin
Node readData(Node head, const char* fileName){
FILE* file = fopen(fileName, "r");
if(!file){
printf("Co loi khi mo file : %s\n", fileName);
exit(EXIT_FAILURE);
}
char line[500];
while (fgets(line, sizeof(line), file)) {
City city = handleLineData(line);
if (city.code != INVALID_CITY_CODE) {
head = addTail(head, city);
}
}
fclose(file);
return head;
}
Như vậy là hoàn thiện, việc còn lại chỉ là đưa chúng vào hàm main theo 1 trật tự do chúng ta quy định.
X. Danh Sách Liên Kết Đơn Quản Lý Sinh Viên C++
Hôm nay mình định viết về phần tiếp theo của opencv xử lý ảnh nhưng còn bài tập môn cấu trúc dữ liệu chưa hoàn thành , sẵn tiện mình vừa làm vừa ra bài này luôn .
Đề bài
Code
#include"iostream"
#include"string"
#include"stdlib.h"
using namespace std;
struct SinhVien {
int mssv;
string name;
string diachi;
string ngaysinh;
string lop;
};
typedef struct SinhVien sinhvien;
struct node {
sinhvien *data;
struct node* link;
};
typedef struct node Node;
struct list {
Node* pHead;
Node* pTail;
};
typedef struct list List;
void KhoiTaoList(List &l) {
l.pHead = l.pTail = NULL;
}
void Input_ThongTin(sinhvien *sv) {
cin.ignore();
cout << "Nhap Ten sinh vien: \n";
fflush(stdin);
getline(cin,sv->name);
cout << "Nhap Ma so sinh vien : ";
cin >> sv->mssv;
cin.ignore();
cout << "Nhap dia chi sinh vien :\n";
getline(cin,sv->diachi);
fflush(stdin);
cout << "Nhap ngay sinh cua sinh vien:\n";
getline(cin, sv->ngaysinh);
fflush(stdin);
cout << "Nhap lop cua sinh vien : ";
getline(cin, sv->lop);
}
Node *KhoiTaoNode() {
sinhvien* sv = new sinhvien;
Input_ThongTin(sv);
Node* p = new Node;
if (p == NULL) {
cout << "full ram ko thể tao thêm\n";
return 0;
}
p->data = sv;
p->link = NULL;
return p;
}
void ThemVaoDauMotSinhVien(List &l, Node *p) {
if (l.pHead == NULL) {
l.pHead = l.pTail= p;
}
else {
p->link = l.pHead;
l.pHead = p;
}
}
void Show(List l) {
for (Node* k = l.pHead; k != NULL; k = k->link) {
cout << "MSSV : " << k->data->mssv<<endl;
cout << "Ten : " << k->data->name << endl;
cout << "Dia Chi : " << k->data->diachi << endl;
cout << "Ngay Sinh : " << k->data->ngaysinh << endl;
cout << "Lop : " << k->data->lop << endl;
cout << "==============================SV================\n";
}
}
void showNode(Node *k) {
cout << "==============================SV================\n";
cout << "MSSV : " << k->data->mssv << endl;
cout << "Ten : " << k->data->name << endl;
cout << "Dia Chi : " << k->data->diachi << endl;
cout << "Ngay Sinh : " << k->data->ngaysinh << endl;
cout << "Lop : " << k->data->lop << endl;
}
void DelSinhVien(List& l) {
string del;
cin.ignore();
cout << "Nhap Ma So SV hoac Ten SV Can Xoa : \n";
fflush(stdin);
getline(cin, del);
Node* g = new Node;
if (del.compare(l.pHead->data->name) == 0 && l.pHead->link ==NULL) {
l.pHead = NULL;
}
else{
for (Node* k = l.pHead; k != NULL; k = k->link) {
if (del.compare(k->data->name) == 0) {
g->link = k->link;
k = g;
}
g = k;
}
}
}
void search(List l ) {
int mssv;
cout << "nhap Ma So Sinh Vien Can Tim Kiem : ";
cin >> mssv;
for (Node* k = l.pHead; k != NULL; k = k->link) {
if (k->data->mssv == mssv) {
showNode(k);
}
}
}
void upgrade(List& l) {
int mssv;
cout << "Nhap Ma So sinh vien can chinh sua thong tin : ";
cin >> mssv;
for (Node* k = l.pHead; k != NULL; k = k->link) {
if (k->data->mssv == mssv) {
cout << "Moi ban sua thong tin sinh vien co ma so : " << mssv << endl;
Input_ThongTin(k->data);
}
}
}
void DanhSachSinhVienChuaXepLop(List l) {
for (Node* k = l.pHead; k != NULL; k = k->link) {
if (k->data->lop == "") {
cout << "Danh Sach Sinh Vien Chua Xep Lop " << endl;
showNode(k);
}
}
}
void ChucNang(List &l) {
int n;
cout << "======Danh Sach Chuc Nang=========\n";
cout << "1 => Nhap 1 sinh vien moi .\n";
cout << "2 => In danh sach sinh vien .\n ";
cout << "3 => Tim kiem sinh vien theo ma so .\n";
cout << "4 => Sua thong tin sinh vien\n";
cout << "5 => Xoa sinh vien khoi danh sach\n";
cout << "6 =>Lay danh sach sinh vien chua xep lop\n";
cout << "0 = >Thoat chuong trinh\n";
while (1){
cout << "Nhap chuc nang ban chon : ";
cin >> n;
if (n == 1) {
cout << "Moi Ban nhap thong tin 1 sinh vien : \n";
Node* p = KhoiTaoNode();
ThemVaoDauMotSinhVien(l, p);
}
if (n == 3) {
search(l);
}
if (n == 2) {
cout << "Danh Sach Sinh Vien : \n";
Show(l);
}
if (n == 4) {
upgrade(l);
}
if (n == 5) {
DelSinhVien(l);
}
if (n == 6) {
DanhSachSinhVienChuaXepLop(l);
}
if (n == 0) {
break;
}
}
}
//hàm in danh sách sinh vien
int main() {
List l;
KhoiTaoList(l);
ChucNang(l);
system("pause");
return 0;
}
The post Danh Sách Liên Kết Đơn C++ first appeared on Techacademy.
source https://techacademy.edu.vn/danh-sach-lien-ket-don-c/
Nhận xét
Đăng nhận xét