Thứ Năm, Tháng Ba 4, 2021
Thiện Tâm
  • Công nghệ
  • Giải trí
  • Học tập
  • Làm đẹp
  • Tổng Hợp
No Result
View All Result
Thiện Tâm
  • Công nghệ
  • Giải trí
  • Học tập
  • Làm đẹp
  • Tổng Hợp
No Result
View All Result
Thiện Tâm
No Result
View All Result
Home Công nghệ

Một số các thao tác trên danh sách liên kết đơn c++ mà bạn cần lưu ý

thientam by thientam
28 Tháng Một, 2021
in Công nghệ
0 0
0
các thao tác trên danh sách liên kết đơn c++

Trong bài ngày hôm nay, mình sẽ giới thiệu cho các bạn về danh sách liên kết đơn và một số thao tác trên danh sách liên kết đơn C++ mà bạn cần lưu ý. Có rất nhiều cách để thực hiện các thao tác trên, bạn không nhất thiết phải làm theo cách của mình nhưng quan trọng là bạn cần nắm vững được kiến thức về con trỏ và các cấp phát động trong C++. 

Đừng quên chia sẻ cho bạn bè và người thân nếu cảm thấy kiến thức bổ ích nhé. 

Một số các thao tác trên danh sách liên kết đơn C++ cơ bản

Thêm phần tử vào đầu danh sách:

– Đầu vào: DSLK đơn l, phần tử p cần thêm 

– Kết quả: DSLK đơn l sau khi thêm 

– Giải thuật: 

* Trường hợp 1: Nếu đơn l rỗng thì con trỏ đầu và cuối của danh sách bằng p 

* Trường hợp 2: (l khác rỗng) 

Bước 1: p trỏ kế tiếp vào đầu danh sách 

Bước 2: Gán con trỏ đầu = p 

– Cài đặt: void ThemDau(LIST &l, NODE *p) { if(l.pHead==NULL) l.pHead=l.pTail=p; else { p->pNext = l.pHead; l.pHead = p; } } 

Minh họa thêm phần tử vào đầu danh sách

các thao tác trên danh sách liên kết đơn c++

Thêm phần tử vào cuối danh sách

– Đầu vào: DSLK đơn l, phần tử p cần thêm 

– Kết quả: DSLK đơn l sau khi thêm 

– Giải thuật: 

* Trường hợp 1: Nếu đơn l rỗng thì con trỏ đầu và cuối của danh sách bằng p 

* Trường hợp 2: (l khác rỗng) 

Bước 1: Con trỏ cuối của danh sách trỏ kế tiếp vào p 

Bước 2: Gán con trỏ cuối = p 

– Cài đặt: void ThemCuoi(LIST &l, NODE *p) { if(l.pHead==NULL) l.pHead=l.pTail=p; else { l.pTail->pNext =p; l.pTail = p; } } 

Minh họa thêm phần tử vào cuối danh sách

các thao tác trên danh sách liên kết đơn c++

Thêm phần tử vào sau một phần tử cho trước

– Đầu vào: DSLK đơn l, phần tử k cần thêm và phần tử p 

– Kết quả: DSLK đơn l sau khi thêm k sau p 

– Giải thuật: 

* Trường hợp 1: Nếu p là con trỏ cuối của danh sách thì Thêm k vào cuối danh sách l 

* Trường hợp 2: là p khác con trỏ cuối 

Bước 1: pSau là con trỏ đứng sau p 

Bước 2: Cho p trỏ tới k 

Bước 3: Cho k trỏ tới pSau 

– Cài đặt: void ThemkSaup(LIST &l, NODE *p, NODE *k) { if(p==l.pTail) ThemCuoi(l, k); else { NODE *pSau = p->pNext; p->pNext = k; k->pNext = pSau; } }

Ảnh minh họa thêm phần tử vào sau một phần tử cho trước

các thao tác trên danh sách liên kết đơn c++

Thêm phần tử k vào trước một phần tử p cho trước

– Đầu vào: DSLK đơn l là phần tử k cần thêm và phần tử p 

– Kết quả: DSLK đơn l là sau khi thêm k ở trước p 

– Giải thuật: 

Bước 1: Thêm k vào sau p 

Bước 2: Hoán vị giá trị của p và k – Cài đặt: void ThemkTruocp(LIST &l, NODE *p, NODE *k) { ThemkSaup(l, p, k); int tam = p->Key; p->Key = k->Key; k->Key = tam; }

Xóa phần tử đầu 

– Đầu vào: DSLK đơn l 

– Kết quả: DSLK đơn l sau khi xóa phần tử đầu 

– Giải thuật: 

* Trường hợp 1: Nếu l rỗng thì kết thúc 

* Trường hợp 2: (l khác rỗng) 

Bước 1: pXoa là con trỏ đầu của danh sách 

Bước 2: Cho con trỏ đầu trỏ vào phần tử kế tiếp 

Bước 3: Xóa pXoa B4: Nếu con trỏ đầu = NULL thì gán con trỏ cuối = NULL

Ảnh minh họa xóa phần tử đầu liên kết

các thao tác trên danh sách liên kết đơn c++

Danh sách liên kết đơn

Danh sách liên kết đơn hay còn gọi là Single Linked List, đây là một cấu trúc dữ liệu động, một danh sách mà mỗi phần tử luôn liên kết với phần tử đứng kế sau nó trong danh sách. 

Mỗi phần tử hay còn gọi là một node hoặc nút trong danh sách liên kết đơn. Đây là một cấu trúc bao gồm hai thành phần chính:

  • Thành phần dữ liệu chuyên lưu thông tin về chính phần tử đó.
  • Thành phần liên kết thì lại chuyên lưu địa chỉ phần tử đứng sau nó trong danh sách, và nếu như phần tử đó đã là phần tử cuối cùng thì thành phần này = NULL.

Nếu phần tử cuối thì thành phần bằng NULL

các thao tác trên danh sách liên kết đơn c++

Các đặc điểm của danh sách liên kết đơn cần phải biết

Khi muốn tìm hiểu thao tác trên danh sách liên kết đơn C++ thì bạn nên nắm được một số đặc điểm cơ bản của danh sách liên kết đơn:

  • Khi chạy chương trình thì sẽ được cấp phát bộ nhớ
  • Thông qua việc thêm hoặc xóa phần tử thì có thể thay đổi được kích thước
  • Bộ nhớ khả dụng của RAM sẽ quyết định kích thước tối đa
  • Các phần tử sẽ được ngẫu nhiên lưu trữ một cách không liên tiếp trong RAM

Dựa vào tính liên kết của phần tử đầu và phần tử đứng sau nó nên có các đặc điểm sau:

  • Để có thể quản lý được danh sách chỉ cần nắm được phần tử đầu và cuối 
  • Đối với phần tử ngẫu nhiên cần phải duyệt từ đầu đến vị trí đó
  • Khi tìm kiếm thì chỉ có thể tìm kiếm tuyến tính một phần tử mà thôi.

Bài viết bên trên chỉ liệt kê một vài thao tác trên danh sách liên kết đơn C++ cơ bản mà bạn cần lưu ý. Nếu bạn muốn biết thêm nhiều thông tin nữa hay theo dõi ở những bài viết trên nhé!

ShareTweetShare
thientam

thientam

Next Post
hiệu ứng nào sau đây không phải của rìu sao băng thiên thạch?

Bạn có biết hiệu ứng nào sau đây không phải của rìu sao băng thiên thạch trong Blade & Soul?

Trả lời Hủy

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Đề Xuất

Top 5 loại sữa tăng cân cho trẻ sơ sinh tốt nhất 2021

Top 5 loại sữa tăng cân cho trẻ sơ sinh tốt nhất 2021

1 Tháng Ba, 2021
văn phòng đăng ký đất đai hà nội hoàng minh giám

Chia sẻ thông tin về văn phòng đăng ký đất đai Hà Nội Hoàng Minh Giám

27 Tháng Một, 2021
khám sức khỏe tổng quát bệnh viện đại học y

Những điều cần biết khi khám sức khỏe tổng quát bệnh viện đại học y Hà Nội

28 Tháng Một, 2021
vé tháng xe bus liên tuyến đi được những xe nào

Vé tháng xe bus liên tuyến đi được những xe nào tại Hà Nội?

27 Tháng Một, 2021
tàu ngầm hoạt động được nhờ vào 2 định luật cơ bản

[Giải đáp] tàu ngầm hoạt động được nhờ vào 2 định luật cơ bản nào?

28 Tháng Một, 2021
những thay đổi về địa giới hành chính tỉnh Đồng Nai từ năm 1976 đến nay

Tìm hiểu về những thay đổi về địa giới hành chính tỉnh Đồng Nai từ năm 1976 đến nay

28 Tháng Một, 2021
Thiện Tâm

Thiện Tâm cập nhật thông tin mới nhất về tin tức công nghệ, thủ thuật, giải trí,.... hot nhất hiện nay.

Chuyên Mục

  • Công nghệ
  • Đời sống
  • Giải trí
  • Học tập
  • Làm đẹp
  • Tổng Hợp

Bài Viết Mới

Top 5 loại sữa tăng cân cho trẻ sơ sinh tốt nhất 2021

Top 5 loại sữa tăng cân cho trẻ sơ sinh tốt nhất 2021

1 Tháng Ba, 2021
văn phòng đăng ký đất đai hà nội hoàng minh giám

Chia sẻ thông tin về văn phòng đăng ký đất đai Hà Nội Hoàng Minh Giám

27 Tháng Một, 2021

© 2021 thientam.vn - thiết kế và phát triển bởi Thiện Tâm

No Result
View All Result
  • Công nghệ
  • Giải trí
  • Học tập
  • Làm đẹp
  • Tổng Hợp

© 2021 thientam.vn - thiết kế và phát triển bởi Thiện Tâm

Welcome Back!

Login to your account below

Forgotten Password?

Create New Account!

Fill the forms bellow to register

All fields are required. Log In

Retrieve your password

Please enter your username or email address to reset your password.

Log In
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?