Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 2, Phần 1: Các cấu trúc dữ liệu cơ bản - Nguyễn Duy Hiệp
REVIEW
• Dùng định lý thợ để đưa ra các tiệm cận chặt cho các công
thức đệ quy sau
푛
a) 푇 푛 = 3푇 + 푛
2
푛
b) 푇 푛 = 5푇 + 푛2
2
Chapter 2
Các cấu trúc dữ liệu
cơ bản
Nội dung
• Các khái niệm cơ bản
• Mảng và mảng động
• Con trỏ và cấu trúc liên kết
• Danh sách tuyến tính
2.1 CÁC KHÁI NIỆM CƠ BẢN
2.1 Khái niệm cơ bản
• Xử lý dữ liệu trên máy tính xét cho cùng là xử lý
với các bit
• Một kiểu dữ liệu (data type): là một tập các giá
trị và nhóm các phép toán được thực hiện trên
các giá trị đó.
• Chỉ ra cách sử dụng các nhóm bit và các phép toán
thực hiện trên các nhóm bit
• VD. Kiểu số nguyên char
số bit : 8 bit
các phép toán +, -, *, /, %
Khái niệm cơ bản
• Các kiểu dữ liệu dựng sẵn (Built-in data types): được xây
dựng sẵn trong ngôn ngữ lập trình
Macintosh
Metrowerks CW
(Default)
IBM PC
Windows XP
Linux on a PC Windows NT
ANSI C
Minimum
Type
char 8
8
8
8
int
32
32
16
32
64
32
16
32
64
16
16
32
64
short 16
long 32
long long 64
Ngôn ngữ lập trình C
Khái niệm cơ bản
• Kiểu dữ liệu trừu tượng (Abstract DataType - ADT) gồm:
• Tập các giá trị
• Tập các phép toán có thể thực hiện trên các giá trị này
• Cách biểu diễn cụ thể bị bỏ qua khi xét đến ADT.
• Làm trừu tượng hóa kiểu dữ liệu, không phụ thuộc ngôn ngữ lập
trình cụ thể.
• Cài đặt ADT là biểu diễn ADT bởi một
ngôn ngữ lập trình cụ thể
• Xét đến một biểu diễn cụ thể cho ADT
• Các kiểu dữ liệu dựng sẵn chính là
cài đặt của các ADT tương ứng bằng
ngôn ngữ lập trình cụ thể.
Khái niệm cơ bản
• Cấu trúc dữ liệu (data structure): Gồm các kiểu dữ liệu và
cách liên kết giữa chúng.
• Cấu trúc dữ liệu mô tả cách tổ chức và lưu trữ dữ liệu trên
máy tính để sử dụng một cách hiệu quả nhất.
• Hai vấn đề của một cấu trúc dữ liệu:
• Các thao tác mà nó hỗ trợ, và
• Cách cài đặt các thao tác này
Khái niệm cơ bản
• Thay đổi cấu trúc dữ liệu không làm thay đổi tính chính xác
của chương trình. Tuy nhiên nó sẽ làm thay đổi hiệu quả của
chương trình.
• Tốt nhất nên chọn cấu trúc dữ liệu cho hiệu quả cao nhất ngay
từ khi thiết kế chương trình!
Cấu trúc liên tục VS liên kết
• Các cấu trúc dữ liệu có thể được chia thành liên tục (contiguous)
hoặc liên kết(linked), tùy vào việc nó được cài đặt dựa trên
mảng hay con trỏ.
Cấu trúc được cấp phát liên tục:
được cấp phát thành vùng bộ nhớ
liên tục. VD mảng, ma trận, đống
(heap), và bảng băm
Cấu trúc dữ liệu liên kết: gồm các đoạn(chunk)
trong bộ nhớ (không nằm liên tục) và được liên
kết với nhau thông qua con trỏ. VD, danh sách,
cây, và đồ thị danh sách kề.
2.2 ARRAY – MẢNG
Mảng
• Mảng : gồm các bản ghi có kiểu giống nhau, có kích thước cố
định. Mỗi phần tử được xác định bởi chỉ số (địa chỉ)
• Mảng là cấu trúc dữ liệu được cấp phát liên tục cơ bản.
Mảng
• Ưu điểm của mảng:
• Truy cập phần tử với thời gian hằng số 휪(ퟏ): vì thông qua
chỉ số của phần tử ta có thể truy cập trực tiếp vào ô nhớ
chứa phần tử.
• Sử dụng bộ nhớ hiệu quả: chỉ dùng bộ nhớ để chứa dữ liệu
nguyên bản, không lãng phí bộ nhớ để lưu thêm các thông
tin khác.
• Tính cục bộ về bộ nhớ: các phần tử nằm liên tục trong 1
vùng bộ nhớ, duyệt qua các phần tử trong mảng rất dễ dàng
và nhanh chóng.
• Nhược điểm: không thể thay đổi kích thước của mảng khi
chương trình đang thực hiện.
Mảng
• Mảng động (dynamic array): cấp phát bộ nhớ cho mảng một
cách động trong quá trình chạy chương trình.
Trong C là malloc và calloc, trong C++ là new
• Sử dụng mảng động ta bắt đầu với mảng chỉ có 1 phần tử, mỗi
khi số lượng phần tử vượt quá khả năng của mảng thì ta lại
gấp đôi kích thước của mảng cũ và copy các phần tử mảng cũ
vào nửa đầu của mảng mới.
• Ưu điểm: tránh lãng phí bộ nhớ khi phải khai báo mảng có
kích thước lớn ngay từ đầu
• Nhược điểm: phải thực hiện thêm các thao tác copy phần tử
mỗi khi thay đổi kích thước.
Mảng động
• Từ mảng 1 phần tử tới 푛 phần tử, số lần phải thay đổi kích
thước là log 푛
2
• Số phần tử phải di chuyển
log 푛
log 푛
∞
푛
푖
푖
푀 = 푖 ∗ = 푛 ∗ < 푛 ∗ = 2푛
2푖 2푖 2푖
푖=1
푖=1
푖=1
Thời gian để duy trì mảng chỉ là Ο(푛)
• Nhược điểm: một số thời gian thực hiện một số thao tác
không còn đúng là hằng số nữa
2.3 CON TRỎ VÀ CẤU TRÚC LIÊN KẾT
• Con trỏ và cấu trúc liên kết
• Danh sách liên kết đơn
• Các dạng khác của danh sách liên kết
Con trỏ và cấu trúc liên kết
• Con trỏ lưu trữ địa chỉ của một vị trí trong bộ nhớ.
VD. Visiting card có thể xem như con trỏ trỏ đến nơi làm việc
của một người nào đó.
• Trong cấu trúc liên kết con trỏ được
dùng để liên kết giữa các phần tử.
• Trong C/C++ :
• *p chỉ p là một biến con trỏ
• &x chỉ địa chỉ của biến x
trong bộ nhớ
• Con trỏ NULL chỉ biến con trỏ
chưa được gán giá trị
(không trỏ vào đâu cả)
Con trỏ và cấu trúc liên kết
• Tất cả các cấu trúc liên kết đều có đặc điểm giống với khai báo
danh sách liên kết đơn (singly-linked list)sau:
typedef struct list {
item_type item; /* data item */
struct list *pNext; /* point to successor */
} list;
• Mỗi nút có 1 hay nhiều trường dữ liệu (item) chứa dữ liệu ta
cần lưu trữ
• Mỗi nút có ít nhất 1 con trỏ trỏ đến nút tiếp theo (pNext). Do
đó cấu trúc kết nối cần nhiều bộ nhớ hơn cấu trúc liên tục.
• Cuối cùng, ta cần 1 con trỏ trỏ đến đầu cấu trúc để chỉ ra phần
tử bắt đầu của cấu trúc.
Cấu trúc liên kết
Head
20
45
75
85
NULL
• Đặc điểm của cấu trúc liên kết:
• Cần thêm bộ nhớ phụ để lưu các con trỏ
• Không cho phép truy cập phần tử một cách ngẫu nhiên
Tải về để xem bản đầy đủ
49 trang
19320
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 2, Phần 1: Các cấu trúc dữ liệu cơ bản - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
