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

Hoán vị nội dung các phần tử trong danh sách• Cài đặt lại trên xâu một trong những thuật toán sắp xếp đã biết trên mảng • Điểm khác biệt duy nhất là cách thức truy xuất đến các phần tử trên xâu thông qua liên kết thay vì chỉ số như trên mảng.
Nội dung trích xuất từ tài liệu:
Danh sách liên kết đơnDanh sách liên kết đơnDSLK - định nghĩa DSLK đơn là chuỗi các node, được tổ chức theo thứ tự tuyến tính Mỗi node gồm 2 phần: phần:  Phần Data, information : löu tröõ caùc thoâng tin veà baûn thaân phaàn töû .  Phần link hay con trỏ : löu tröõ ñòa chæ cuûa phaàn töû keá tieáp trong danh saùch, hoaëc löu tröõ giaù trò NULL neáu laø phaàn töû cuoái danh saùch. saùch. Data Link Node 2Cấu trúc dữ liệu của DSLK đơntypedef struct Node { int data; // Data là kiểu đã định nghĩa trước Node * link; //con trỏ chỉ đến cấu trúc NODE }; 3 Lưu trữ DSLK đơn trong RAM Địa chỉ 000 Ví dụ : Ta có danh sách theo dạng bảng sau Joe 100 140 Address ddress Name Age ge Link Bill 110 10 Joe 20 140 500 10 Bill ill 42 50 Marta 140 NULL 140 Marta 27 10 Sahra 230 230 Sahra ahra 25 NULL 140 … … … Kock 500 50 Koch 31 230 230 … 4 DSLK đơn truy xuất – Minh họa Địa chỉ  VD:first 100 140 100 ‘Joe’ 140 ‘Marta’ 110 110 500 ‘Bill’ 500 ‘Koch’ 230 230 ‘Bill’ NULL 5Tổ chức, quản lý Để quản lý một xâu đơn chỉ cần biết địa chỉ phần tử đầu xâu. Con trỏ First sẽ được dùng để lưu trữ địa chỉ phần tử đầu xâu, ta gọi First là đầu xâu. Ta có khai báo : NODE* first; Để tiện lợi, có thể sử dụng thêm một con trỏ last giữ địa chỉ phần tử cuối xâu. Khai báo last như sau : NODE* last; last first A B X Z Y 6DSLK – Khai báo phần Data typedef struct node { Cấu trúc DataType data; nodeDataType ? struct node * link; }NODE; typedef struct node typedef struct node { { int data; SinhVien data; struct node * link; struct node * link; }NODE; }NODE; 7Tổ chức, quản lýKhai báo kiểu của 1 phần tử và kiểu danh sách liên kết đơn và đểđơn giản ta xét mỗi node gồm vùng chứa dữ liệu là kiểu số nguyên : //kiểu của một phần tử trong danh sách typedef struct Node { int data; NODE * link; }NODE; typedef struct List // kiểu danh sách liên kết { NODE* first; NODE* last; }LIST; Trong thực tế biến data là một kiểu struct 8 Tạo một phần tử Thủ tục GetNode để tạo ra một phần tử cho danh sách với thông tin chứa trong x NODE* GetNode(int x) { NODE *p; // Cấp phát vùng nhớ cho phần tử p = (NODE*)malloc(sizeof(NODE))//p= new NODE; if (p==NULL) { coutlink = NULL; return p; } 9 Tạo một phần tửĐể tạo một phần tử mới cho danh sách, cần thực hiện câulệnh: new_ele = GetNode(x); new_ele sẽ quản lý địa chỉ của phần tử mới được tạo. 10Các thao tác cơ sở  Tạo danh sách rỗng  Thêm một phần tử vào danh sách  Tìm kiếm một giá trị trên danh sách  Trích một phần tử ra khỏi danh sách  Duyệt ...