Về cơ bản, một mảng là một tập hợp các đối tượng dữ liệu tương tự được lưu trữ trong các vị trí bộ nhớ tuần tự dưới một tiêu đề chung hoặc một tên biến.
Trong khi danh sách được liên kết là một cấu trúc dữ liệu chứa một chuỗi các phần tử trong đó mỗi phần tử được liên kết với phần tử tiếp theo của nó. Có hai trường trong một yếu tố của danh sách liên kết. Một là trường Dữ liệu và trường khác là trường liên kết, Trường dữ liệu chứa giá trị thực sẽ được lưu trữ và xử lý. Hơn nữa, trường liên kết giữ địa chỉ của mục dữ liệu tiếp theo trong danh sách được liên kết. Địa chỉ được sử dụng để truy cập vào một nút cụ thể được gọi là một con trỏ.
Một sự khác biệt đáng kể khác giữa một mảng và danh sách được liên kết là Array có kích thước cố định và được yêu cầu khai báo trước, nhưng Danh sách liên kết không bị giới hạn về kích thước và mở rộng và hợp đồng trong quá trình thực thi.
Biểu đồ so sánh
| Cơ sở để so sánh | Mảng | Danh sách liên kết |
|---|---|---|
| Căn bản | Nó là một tập hợp nhất quán của một số mục dữ liệu cố định. | Nó là một tập hợp được sắp xếp bao gồm một số lượng lớn các mục dữ liệu. |
| Kích thước | Được chỉ định trong khi khai báo. | Không cần chỉ định; phát triển và co lại trong quá trình thực hiện. |
| Phân bổ lưu trữ | Vị trí phần tử được phân bổ trong thời gian biên dịch. | Vị trí phần tử được chỉ định trong thời gian chạy. |
| Thứ tự của các yếu tố | Lưu trữ liên tiếp | Được lưu trữ ngẫu nhiên |
| Truy cập phần tử | Truy cập trực tiếp hoặc ngẫu nhiên, nghĩa là Chỉ định chỉ mục mảng hoặc chỉ mục. | Truy cập tuần tự, tức là, Traverse bắt đầu từ nút đầu tiên trong danh sách theo con trỏ. |
| Chèn và xóa phần tử | Chậm tương đối như thay đổi là cần thiết. | Dễ dàng hơn, nhanh chóng và hiệu quả. |
| Đang tìm kiếm | Tìm kiếm nhị phân và tìm kiếm tuyến tính | tìm kiếm tuyến tính |
| Cần có bộ nhớ | ít hơn | Hơn |
| Sử dụng bộ nhớ | Không hiệu quả | Hiệu quả |
Định nghĩa của mảng
Một mảng được định nghĩa là một tập hợp một số lượng nhất định các phần tử đồng nhất hoặc các mục dữ liệu. Nó có nghĩa là một mảng chỉ có thể chứa một loại dữ liệu, tất cả các số nguyên, tất cả các số dấu phẩy động hoặc tất cả các ký tự. Khai báo một mảng như sau:
int a [10];
Trong đó int chỉ định kiểu dữ liệu hoặc kiểu phần tử lưu trữ mảng. Số một tên là tên của một mảng và số được chỉ định trong dấu ngoặc vuông là số phần tử mà một mảng có thể lưu trữ, đây còn được gọi là kích thước hoặc độ dài của mảng.
Chúng ta hãy xem xét một số khái niệm cần nhớ về mảng:
- Các phần tử riêng lẻ của một mảng có thể được truy cập bằng cách mô tả tên của mảng, theo sau là chỉ mục hoặc chỉ mục (xác định vị trí của phần tử trong mảng) bên trong dấu ngoặc vuông. Ví dụ, để lấy phần tử thứ 5 của mảng, chúng ta cần viết một câu lệnh a [4].
- Trong mọi trường hợp, các phần tử của một mảng sẽ được lưu trữ trong một vị trí bộ nhớ liên tiếp.
- Phần tử đầu tiên của mảng có chỉ số zero [0]. Nó có nghĩa là phần tử đầu tiên và cuối cùng sẽ được chỉ định là [0] và [9] tương ứng.
- Số lượng phần tử có thể được lưu trữ trong một mảng, nghĩa là kích thước của một mảng hoặc chiều dài của nó được đưa ra theo phương trình sau:
(giới hạn trên-giới hạn dưới) + 1
Đối với mảng trên, nó sẽ là (9-0) + 1 = 10. Trong đó 0 là giới hạn dưới của mảng và 9 là giới hạn trên của mảng. - Mảng có thể được đọc hoặc viết thông qua các vòng lặp. Nếu chúng ta đọc mảng một chiều, nó yêu cầu một vòng lặp để đọc và một vòng khác để viết (in) mảng, ví dụ:
a. Để đọc một mảng
cho (i = 0; i <= 9; i ++)
{scanf (M %% dv, & a [i]); }
b. Để viết một mảng
cho (i = 0; i <= 9; i ++)
{printf (phiên bản% dv, a [i]); } - Trong trường hợp mảng 2 chiều, nó sẽ yêu cầu hai vòng và mảng n chiều tương tự sẽ cần n vòng.
Các hoạt động được thực hiện trên mảng là:
- Tạo mảng
- Đi qua một mảng
- Chèn các yếu tố mới
- Xóa các yếu tố cần thiết.
- Sửa đổi một yếu tố.
- Sáp nhập mảng
Thí dụ
Chương trình sau đây minh họa việc đọc và viết của mảng.
#include #include void main () { int a[10], i; printf("Enter the array"); for ( i= 0; i <= 9; i++) { scanf ( "%d", &a[ i ] ) ; } printf( "Enter the array" ); for (i = 0 ; i <= 9 ; i++) { printf ( "%d\n", a[ i ] ) ; } getch (); }
Định nghĩa của danh sách liên kết
Danh sách liên kết là một danh sách cụ thể của một số yếu tố dữ liệu được liên kết với nhau. Trong phần này, mọi phần tử đều trỏ đến phần tử tiếp theo thể hiện thứ tự logic. Mỗi phần tử được gọi là một nút, có hai phần.
Phần INFO lưu trữ thông tin và ĐIỂM chỉ đến phần tử tiếp theo. Như bạn đã biết để lưu trữ địa chỉ, chúng tôi có một cấu trúc dữ liệu duy nhất trong C được gọi là con trỏ. Do đó trường thứ hai của danh sách phải là một loại con trỏ.
Các loại danh sách được liên kết là danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết tròn, danh sách liên kết đôi.
Các hoạt động được thực hiện trên Danh sách liên kết là:
- Sự sáng tạo
- Đi qua
- Chèn
- Xóa
- Đang tìm kiếm
- Ghép
- Trưng bày
Thí dụ
Đoạn mã sau minh họa việc tạo danh sách được liên kết:
struct node { int num; stuct node *next; } start = NULL; void create() { typedef struct node NODE; NODE *p, *q; char choice; first = NULL; do { p = (NODE *) malloc (sizeof (NODE)); printf ("Enter the data item\n"); scanf ("%d", & p -> num); if (p == NULL) { q = start; while (q -> next ! = NULL) { q = q -> next } p -> next = q -> next; q -> = p; } else { p -> next = start; start = p; } printf ("Do you want to continue (type y or n) ? \n"); scanf ("%c", &choice) ; } while ((choice == 'y') || (choice == 'Y')); }
Sự khác biệt chính giữa mảng và danh sách liên kết
- Một mảng là cấu trúc dữ liệu chứa một tập hợp các phần tử dữ liệu loại tương tự trong khi danh sách Liên kết được coi là cấu trúc dữ liệu không nguyên thủy chứa một tập hợp các phần tử được liên kết không có thứ tự được gọi là các nút.
- Trong mảng, các phần tử thuộc về chỉ mục, nghĩa là, nếu bạn muốn vào phần tử thứ tư, bạn phải viết tên biến với chỉ mục hoặc vị trí của nó trong dấu ngoặc vuông.
Tuy nhiên, trong một danh sách được liên kết, bạn phải bắt đầu từ đầu và thực hiện theo cách của mình cho đến khi bạn đến phần tử thứ tư. - Mặc dù việc truy cập vào một mảng phần tử là nhanh trong khi danh sách Liên kết mất thời gian tuyến tính, do đó, nó chậm hơn một chút.
- Các hoạt động như chèn và xóa trong mảng tiêu tốn rất nhiều thời gian. Mặt khác, hiệu suất của các hoạt động này trong danh sách Liên kết là nhanh.
- Mảng có kích thước cố định. Ngược lại, danh sách Liên kết là động và linh hoạt và có thể mở rộng và hợp đồng kích thước của nó.
- Trong một mảng, bộ nhớ được gán trong thời gian biên dịch trong khi trong danh sách Liên kết, nó được cấp phát trong khi thực thi hoặc thời gian chạy.
- Các phần tử được lưu trữ liên tiếp trong các mảng trong khi nó được lưu trữ ngẫu nhiên trong danh sách Liên kết.
- Yêu cầu của bộ nhớ ít hơn do dữ liệu thực tế được lưu trữ trong chỉ mục trong mảng. Ngoài ra, cần có thêm bộ nhớ trong Danh sách được liên kết do lưu trữ các yếu tố tham chiếu tiếp theo và trước đó.
- Ngoài ra việc sử dụng bộ nhớ là không hiệu quả trong mảng. Ngược lại, sử dụng bộ nhớ là hiệu quả trong mảng.
Phần kết luận
Danh sách mảng và liên kết là các loại cấu trúc dữ liệu khác nhau về cấu trúc, phương thức truy cập và thao tác, yêu cầu bộ nhớ và sử dụng. Và có lợi thế và bất lợi đặc biệt so với việc thực hiện nó. Do đó, một trong hai có thể được sử dụng theo nhu cầu.
