Danh Sách Móc Nối - Danh Sách Liên Kết

CẤU TRÚC TUYẾN TÍNH

Danh sách móc nối

Các nội dung chính
– Con trỏ và cấp phát bộ nhớ cho đối tượng động
– Mô tả cấu trúc lưu trữ móc nối (danh sách móc nối)
– Các loại danh sách móc nối
• Danh sách nối đơn
– Danh sách nối đơn thẳng
– Danh sách nối đơn vòng
• Danh sách nối kép
– Danh sách nối kép thẳng
– Danh sách nối kép vòng
– Cài đặt LIFO, FIFO bằng cấu trúc lưu trữ móc nối
• LIFO
• FIFO

Con trỏ và cấp phát bộ nhớ cho đối tượng động

― Con trỏ (pointer): là một kiểu dữ liệu (datatype) mà giá trị của nó chỉ dùng để chỉ đến một giá trị khác chứa trong bộ nhớ.

– Các thao tác cơ bản
• Khởi tạo (khai báo): int * P;
• Lấy địa chỉ 1 đối tượng: int A=20; P = &A;
• Truy nhập vào đối tượng được trỏ: *P = 20;
• Cấp phát bộ nhớ động cho đối tượng DL động: P = new int;
• Giải phóng đối tượng DL động: delete P;

Mô tả cấu trúc lưu trữ móc nối (danh sách móc nối)
• Là tập hợp các phần tử dữ liệu không liên tục được kết nối với nhau thông qua một liên kết (thường là con trỏ)
• Cho phép ta quản lý bộ nhớ linh động
• Các phần tử được chèn vào danh sách và xóa khỏi danh sách một cách dễ dàng
• Tại mỗi nút có hai thành phần:

• Dữ liệu trong nút
• Con trỏ trỏ đến phần tử kế tiếp

Phân loại danh sách móc nối

• Phân loại theo hướng con trỏ (hay số con trỏ trong 1 nút)
– Danh sách nối đơn (single linked list):
• con trỏ luôn chỉ theo một hướng trong danh sách

– Danh sách nối kép (double linked list)
• 2 con trỏ chỉ theo hai hướng trong danh sách

• Phân loại theo cách móc nối vòng hoặc thẳng
– Danh sách nối thẳng: truy cập vào danh sách thông qua điểm truy nhập H

– Danh sách nối vòng (circularly linked list): bất cứ nút nào trong danh sách cũng có thể coi là nút đầu hay nút cơ sở (mọi nút có vai trò như nhau)

Cài đặt danh sách nối đơn thẳng
• Dùng 1 con trỏ luôn chỉ theo một hướng trong danh sách
• Phần tử (nút) cuối của danh sách có con trỏ NULL
• Các nút sắp xếp tuần tự trong danh sách

struct Node {
    Type info;
    Node* next;
};
typedef Node* PNode; //Kiểu con trỏ nút
typedef Node* LinkedList; //Kiểu danh sách nối đơn

Các thao tác cơ bản

• Khởi tạo danh sách: tạo ra một danh sách rỗng
• Kiểm tra trạng thái hiện tại của DS:

• Rỗng (Empty): khi con trỏ H = NULL

• Phép xen một phần tử mới vào danh sách

• Xen phần tử mới vào trước phần tử hiện tại Q: InsertAfter

• Xen phần tử mới vào sau phần tử hiện tại Q: InsertBefore

• Phép xoá phần tử khỏi danh sách: Delete
• Phép tìm kiếm phần tử có dữ liệu = x: Search
• Phép duyệt danh sách: Traverse

• Khởi tạo danh sách: gán con trỏ H=Null

void InitList ( LinkedList & H ) {
    H = NULL;
}

• Kiểm tra danh sách rỗng: kiểm tra con trỏ H có bằng Null không

bool IsEmpty ( LinkedList H ) {
    return (H == NULL);
}

• Thao tác bổ sung một phần tử mới K vào đầu danh sách H

• Thao tác bổ sung một phần tử mới K vào sau phần tử hiện tại được trỏ bởi P trong d/s H. Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung . Nếu không cần trả về phần tử vừa bổ sung thì sửa thế nào?

• Thao tác bổ sung một phần tử mới vào trước phần tử hiện tại P trong d/s H.
Thao tác này sau đó trả về con trỏ trỏ vào nút vừa bổ sung (bổ sung một cách khác bằng việc dùng node trung gian,)

• Phép xóa phần ở đầu danh sách H

• Phép xóa phần tử hiện tại mà con trỏ P trỏ tới trong danh sách H

• Phép tìm kiếm một phần tử trong danh sách H có dữ liệu bằng K cho trước. Hàm trả về địa chỉ của phần tử đó

• Thao tác duyệt danh sách, ứng dụng vào tính số phần tử của danh sách

Danh sách nối kép
– Với danh sách đơn sử dụng một con trỏ, ta chỉ có thể duyệt danh sách theo một chiều
– Danh sách nối kép (double linked list):
• Con trỏ trái (nextL): trỏ tới thành phần bên trái (phía trước)
• Con trỏ phải (nextR): trỏ tới thành phần bên phải (phía sau)
– Đặc điểm
• Sử dụng 2 con trỏ, giúp ta luôn xem xét được cả 2 chiều của danh sách
• Tốn bộ nhớ nhiều hơn

struct DNode {
  Type info;
  DNode * nextL, * nextR;
};
typedef DNode * PDNode;
typedef struct {
  PDNode H; //con trỏ đầu
  PDNode T; //con trỏ cuối
} DoubleLinkedList;

Các phép toán

• Khởi tạo danh sách: NewDList
• Phép xen một phần tử mới vào danh sách
• Xen phần tử mới vào trước phần tử hiện tại Q: InsertAfter
• Xen phần tử mới vào sau phần tử hiện tại Q: InsertBefore
• Phép xoá phần tử khỏi danh sách: Delete
• Phép tìm kiếm phần tử có dữ liệu = x: Search
• Phép duyệt danh sách: Traverse

Cài đặt LIFO (Stack) bằng CTLT móc nối

– Cách tổ chức:
• Chỉ cần một con trỏ S vừa là đỉnh, vừa là điểm truy nhập
– Khai báo cấu trúc

struct Node {
  Type info;
  Node * next;
};
typedef Node * PNode;
typedef PNode Stack;

– Lưu ý: danh sách liên kết có kích thước động, không bị giới hạn trước, sự tăng kích thước chỉ phụ thuộc vào khả năng cấp phát bộ nhớ của máy tính cho nên ta có thể coi ngăn xếp có kích thước vô hạn.

– Các phép toán:

void Initialize (Stack & S ) {
    S = NULL;
}

– Kiểm tra trạng thái của ngăn xếp

• Biểu diễn LIFO hay ngăn xếp (Stack)
– Các phép toán: bổ sung 1 phần tử vào đỉnh

• Phép toán lấy một phần tử khỏi ngăn xếp

• Phép toán tính số phần tử của ngăn xếp

int StackLength(Stack S) {
  Pnode P;
  P = S;
  count = 0;
  while (P != NULL) {
    count++;
    P = P -> next;
  }
  return count;
}

Cài đặt FIFO (Queue) bằng CTLT móc nối

– Cấu trúc

struct Node {
  Type info;
  Node * next;
};
typedef Node * PNode;
typedef struct {
  PNode F, R;
}
Queue;

– Lưu ý: danh sách liên kết có kích thước động, không bị giới hạn trước. Sự tăng kích thước chỉ phụ thuộc vào khả năng cấp phát bộ nhớ của máy tính cho nên ta có thể coi hàng đợi của chúng ta có kích thươc vô hạn.

– Các phép toán:

void Initialize(Queue & Q) {
  Q.F = Q.R = NULL;
}

bool isEmpty(Queue Q) {
  return (Q.F == NULL);
}

– Phép toán thêm phần tử vào hàng đợi

void InsertQ(Type x, Queue & Q) {
  Pnode P;
  P = new PNode;
  P -> info = x;
  P -> next = NULL;
  if (isEmpty(Q)) {
    Q.F = Q.R = P;
  } else {
    Q.R -> next = P;
    Q.R = P;
  }
}

– Phép toán xóa phần tử khỏi hàng đợi

void DeleteQ(Type & x, Queue & Q) {
  Pnode P;
  if (isEmpty(Q)) printf(“Empty”);
  else {
    P = Q.F;
    x = Q.F -> info;
    Q.F = Q.F -> next;
    delete P;
  }
}

Bài tập
• Bài 1: Cài đặt một danh sách số nguyên bằng cấu trúc lưu trữ móc nối kép. Việc cài đặt bao gồm:
– Nêu cách tổ chức danh sách
– Định nghĩa cấu trúc
– Cài đặt các hàm thực hiện các thao tác cơ bản: khởi tạo, bố sung một phần tử vào trước 1 phần tử hiện tại, bổ sung một phần tử vào sau một phần tử hiện tại, loại bỏ một phần tử hiện tại.
• Bài 2: Cài đặt Queue bằng cấu trúc móc nối kép:
– Định nghĩa cấu trúc
– Cài đặt các thao tác cơ bản: Khởi tạo, bổ sung, loại bỏ

• Bài 3: cài đặt một danh sách các môn học, mỗi môn học gồm các thông tin: mã môn, tên môn, số tín chỉ. Danh sách luôn được sắp xếp theo thứ tự tăng dần của số tín chỉ. Yêu cầu:
– Sử dụng cấu trúc lưu trữ móc nối đơn để cài đặt danh sách
– Cài đặt các thao tác: khởi tạo, bổ sung 1 môn, loại bỏ một môn có mã môn cho trước, in ra nội dung của DS.