Sau mảng, cấu trúc dữ liệu phổ biến thứ hai là Danh sách liên kết. Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính, được tạo bởi một chuỗi các nút, trong đó mỗi nút chứa một giá trị và một con trỏ đến nút tiếp theo trong chuỗi. Trong bài viết này, hãy xem cách triển khai danh sách liên kết trong C.
Danh sách liên kết trong C là gì?
Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính. Mọi danh sách được liên kết đều có hai phần, phần dữ liệu và phần địa chỉ chứa địa chỉ của phần tử tiếp theo trong danh sách, được gọi là nút.
Kích thước của danh sách được liên kết không cố định và các mục dữ liệu có thể được thêm vào bất kỳ vị trí nào trong danh sách. Điểm bất lợi là để đến một nút, chúng ta phải đi qua tất cả các con đường từ nút đầu tiên đến nút mà chúng ta yêu cầu. Danh sách Liên kết giống như một mảng nhưng không giống như một mảng, nó không được lưu trữ tuần tự trong bộ nhớ.
Các loại danh sách liên kết phổ biến nhất là:
Ví dụ về Danh sách được Liên kết
Định dạng: [dữ liệu, địa chỉ]
Đầu -> [3,1000] -> [43,1001] -> [21,1002]
Trong ví dụ, số 43 hiện diện ở vị trí 1000 và địa chỉ có ở nút trước đó. Đây là cách một danh sách liên kết được biểu diễn.
Các chức năng cơ bản của danh sách được liên kết
Có nhiều chức năng có thể được triển khai trên danh sách được liên kết trong C. Hãy cố gắng hiểu chúng với sự trợ giúp của một chương trình mẫu.Đầu tiên, chúng tôi tạo một danh sách, hiển thị nó, chèn vào bất kỳ vị trí nào, xóa một vị trí. Đoạn mã sau sẽ chỉ cho bạn cách thực hiện các thao tác trên danh sách.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf (' n 1. Tạo n') printf (' n 2. Hiển thị n') printf (' n 3. Chèn vào đầu n ') printf (' n 4.Chèn vào cuối n ') printf (' n 5.Chèn ở vị trí đã chỉ định n ') printf (' n 6.Xóa từ đầu n ') printf (' n 7.Xóa từ cuối n ') printf (' n 8.Xóa khỏi vị trí đã chỉ định n ') printf (' n 9. Thoát n ') printf (' n ----------------- --------------------- n ') printf (' Nhập lựa chọn của bạn: t ') scanf ('% d ', & lựa chọn) chuyển đổi (lựa chọn) {trường hợp 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Sai Lựa chọn: n') break}} return 0} với d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nNhập giá trị dữ liệu cho nút: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList rỗng: n ') return} else {ptr = start printf (' nCác phần tử trong danh sách là: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEnter the giá trị dữ liệu cho nút: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nNhập giá trị dữ liệu cho nút: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nNhập vị trí cho nút mới sẽ được chèn: t') scanf ('% d' , & pos) printf ('nNhập giá trị dữ liệu của nút: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Xử lý cẩn thận] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nPhần tử bị xóa là:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nPhần tử bị xóa là:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('n Phần tử đã xóa là:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nDanh sách rỗng: n') exit (0)} else {printf ('nNhập vị trí của nút sẽ bị xóa : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' n Phần tử đã xóa là:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('n Phần tử bị xóa là: % dt ', ptr-> thông tin) miễn phí (ptr)}}}Phần đầu tiên của mã này là tạo một cấu trúc. Cấu trúc danh sách liên kết được tạo để nó có thể chứa dữ liệu và địa chỉ khi chúng ta cần. Điều này được thực hiện để cung cấp cho trình biên dịch một ý tưởng về cách nút.
nút cấu trúc {int thông tin nút cấu trúc * tiếp theo}Trong cấu trúc, chúng ta có một biến dữ liệu gọi là thông tin để giữ dữ liệu và một biến con trỏ để trỏ đến địa chỉ. Có nhiều thao tác khác nhau có thể được thực hiện trên danh sách được liên kết, như:
việc sử dụng tuần tự hóa trong java là gì
- tạo nên()
- trưng bày()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Các chức năng này được gọi bởi chức năng chính hướng menu. Trong chức năng chính, chúng tôi lấy đầu vào từ người dùng dựa trên thao tác mà người dùng muốn thực hiện trong chương trình. Đầu vào sau đó được gửi đến hộp chuyển đổi và dựa trên đầu vào của người dùng.
Dựa trên những gì đầu vào được cung cấp, hàm sẽ được gọi. Tiếp theo, chúng ta có các chức năng khác nhau cần được giải quyết. Chúng ta hãy xem xét từng chức năng này.
Tạo chức năng
Đầu tiên, có một chức năng tạo để tạo danh sách liên kết. Đây là cách cơ bản để tạo danh sách liên kết. Hãy để chúng tôi nhìn vào mã.
void create () {struct node * temp, * ptr printf ('nNhập giá trị dữ liệu cho nút: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Đầu ra
Đầu tiên, hai con trỏ được tạo kiểu nút, ptr và tạm thời . Chúng tôi lấy giá trị cần được thêm vào danh sách liên kết từ người dùng và lưu trữ nó trong phần thông tin của biến tạm thời và gán tạm thời của tiếp theo là phần địa chỉ thành null. Có một con trỏ bắt đầu giữ đầu danh sách. Sau đó, chúng tôi kiểm tra phần bắt đầu của danh sách. Nếu đầu danh sách là null, thì chúng ta gán tạm thời cho con trỏ bắt đầu. Nếu không, chúng tôi sẽ chuyển đến điểm cuối cùng mà dữ liệu đã được thêm vào.
Đối với điều này, chúng tôi chỉ định ptr giá trị bắt đầu và đi qua ptr-> next = null . Sau đó chúng tôi chỉ định ptr-> tiếp theo địa chỉ của tạm thời. Theo cách tương tự, có mã được đưa ra để chèn vào đầu, chèn vào cuối và chèn tại một vị trí xác định.
Chức năng hiển thị
Đây là mã cho chức năng hiển thị.
void display () {struct node * ptr if (start == NULL) {printf ('nList rỗng: n') return} else {ptr = start printf ('nCác phần tử trong danh sách là: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}Đầu ra
Trong chức năng hiển thị, đầu tiên chúng ta kiểm tra xem danh sách có trống không và trả về nếu nó trống. Trong phần tiếp theo, chúng tôi gán giá trị bắt đầu cho ptr. Sau đó, chúng tôi chạy một vòng lặp cho đến khi ptr là null và in phần tử dữ liệu cho mỗi nút, cho đến khi ptr là null, chỉ định phần cuối của danh sách.
Xóa chức năng
Đây là đoạn mã để xóa một nút khỏi danh sách được liên kết.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('n Nhập vị trí của nút cần xóa: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' n Phần tử đã xóa là:% dt ', ptr-> thông tin ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe phần tử đã xóa là:% dt ', ptr-> thông tin) miễn phí (ptr)}}}Đầu ra
Trong quá trình xóa, trước tiên nó sẽ kiểm tra xem danh sách có trống không, nếu có thì nó tồn tại. Nếu nó không trống, nó sẽ yêu cầu người dùng xóa vị trí. Khi người dùng vào vị trí, nó sẽ kiểm tra xem đó có phải là vị trí đầu tiên hay không, nếu có nó sẽ chỉ định ptr để bắt đầu và di chuyển con trỏ bắt đầu đến vị trí tiếp theo và xóa ptr. Nếu vị trí không phải là số không , sau đó nó chạy một vòng lặp for từ 0 đến tận vị trí do người dùng nhập và được lưu trữ trong pos Biến đổi. Có một câu lệnh if để quyết định xem vị trí đã nhập không có mặt hay không. Nếu ptr bằng null , thì nó không có mặt.
Chúng tôi gán ptr cho tạm thời trong vòng lặp for, và ptr sau đó chuyển sang phần tiếp theo. Sau này khi vị trí được tìm thấy. Chúng tôi tạo biến tạm thời để giữ giá trị của ptr-> tiếp theo do đó bỏ qua ptr. Sau đó ptr bị xóa. Tương tự, nó có thể được thực hiện cho việc xóa phần tử đầu tiên và cuối cùng.
Danh sách được liên kết gấp đôi
Nó được gọi là danh sách liên kết kép vì có hai con trỏ , một điểm đến nút tiếp theo và điểm khác đến nút trước đó. Các hoạt động được thực hiện trong liên kết kép tương tự như hoạt động của một danh sách được liên kết đơn lẻ. Đây là mã cho các hoạt động cơ bản.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Vị trí trước Vị trí tiếp theo} void Insert (int x, Danh sách l, Vị trí p) {Vị trí TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> before = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Vị trí p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> p2 = p -> p1 tiếp theo - > next = p -> next if (p2! = NULL) // nếu nút không phải là nút cuối cùng p2 -> trước = p -> trước} else printf ('Phần tử không tồn tại !!! n')} void Display (Danh sách l) {printf ('Phần tử danh sách là ::') Vị trí p = l-> next while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> before = NULL l-> next = NULL List p = l printf ('THỰC HIỆN DANH SÁCH ĐƯỢC LIÊN KẾT ĐÔI CỦA L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnNhập lựa chọn :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Nhập phần tử cần chèn :: ') scanf ('% d', & x) printf ('Nhập vị trí của phần tử ::') scanf ('% d', & pos) for (i = 1 inext} Chèn (x, l, p) ngắt chữ hoa 2: p = l printf ('Nhập phần tử cần xóa ::') scanf ('% d', & x) Xóa (x, p) ngắt chữ hoa 3: Hiển thị (l) break}} trong khi (ch<4) } Đầu ra
Vì vậy, như bạn có thể thấy khái niệm hoạt động khá đơn giản. Danh sách liên kết kép có các hoạt động giống như danh sách liên kết đơn trong ngôn ngữ lập trình C. Sự khác biệt duy nhất là có một biến địa chỉ khác giúp duyệt danh sách tốt hơn trong danh sách được liên kết kép.
Tôi hy vọng bạn đã hiểu cách thực hiện các thao tác cơ bản trên danh sách liên kết đơn và kép trong C.
Nếu bạn muốn học Danh sách liên kết trong Java, đây là .
câu hỏi phỏng vấn đám mây dịch vụ salesforce
Nếu bạn gặp bất kỳ câu hỏi nào, vui lòng đặt tất cả câu hỏi của bạn trong phần nhận xét của “Danh sách được liên kết trong C” và nhóm của chúng tôi sẽ sẵn lòng trả lời.