Bài giảng Kỹ thuật lập trình - Chương 7, Phần 1: Cấu trúc dữ liệu

Download

CẤU TRÚC DỮ LIỆU

Dữ liệu, kiểu dữ liệu &

cấu trúc dữ liệu

Machine Level Data Storage

0100110001101001010001

3.1415

'A'

Primitive Data Types

Basic Data Structures

array

stack

queue

list

High-Level Data Structures

hash table

tree

Các

kiểu dữ liệu

Kiểu dữ liệu cơ bản

(primitive data type)

▪Đại diện cho các dữ liệu

giống nhau, không thể

phân chia nhỏ hơn được

nữa

▪Thường được các ngôn

ngữ lập trình định nghĩa

sẵn

Kiểu dữ liệu có cấu trúc

(structured data type)

▪Được xây dựng từ các

kiểu dữ liệu (cơ bản, có

cấu trúc) khác

▪Có thể được các ngôn

ngữ lập trình định nghĩa

sẵn hoặc do lập trình viên

tự định nghĩa

▪Ví dụ

▫C/C++: int, long, char, bool...

▫Thao tác trên các số nguyên:

+ - * / ...

Nội dung

1. Mảng

2. Danh sách

3. Ngăn xếp

4. Hàng đợi

5. Cây

Mảng

Array

Mảng

Array

▪ Dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên

▪ Một hay nhiều chiều

▫ C không giới hạn số chiều của mảng

Cú pháp

DataType ArrayName[size];

mảng nhiều chiều

DataType ArrayName[size 1][size 2]...[size n];

Khởi tạo giá trị

mảng

▪ C1. Khi khai báo

float y[5] = { 3.2, 1.2, 4.5, 6.0, 3.6 }

int m[6][2] = { { 1, 1 }, { 1, 2 }, { 2, 1 }, { 2, 2

}, { 3, 1 }, { 3, 2 } };

char s1[6] = { 'H', 'a', 'n', 'o', 'i', '\0' }; //hoặc

char s1[6] = "Hanoi";

char s1[] = "Dai hoc Bach Khoa Hanoi"; //L = 24

int m[][] = { { 1, 2, 3 }, { 4, 5, 6 } };

▪ C2. Khai báo rồi gán giá trị cho từng phần tử của mảng.

int m[4];

m[0] = 1; m[1] = 2; m[2] = 3; m[3] = 4;

Danh sách

List

Danh sách

List

▪ Danh sách

▫ Tập hợp các phần tử cùng kiểu

▫ Số lượng các phần tử của danh sách không cố định

▪ Phân loại

▫ Danh sách tuyến tính:

▸Có phần tử đầu tiên, phần tử cuối cùng

▸Thứ tự trước / sau của các phần tử được xác định rõ ràng, ví dụ

sắp theo thứ tự tăng dần, giảm dần hay thứ tự trong bảng chữ cái

▸Các thao tác trên danh sách phải không làm ảnh hưởng đến trật

tự này

▫ Danh sách phi tuyến tính: các phần tử trong danh sách không

được sắp thứ tự

Danh sách

List

▪ Lưu trữ

▫ Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ  danh sách kế

tiếp

▫ Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ  danh

sách móc nối

▸Danh sách nối đơn

▸Danh sách nối kép

Thao tác trên

danh sách

. Khởi tạo danh sách (create)

. Kiểm tra danh sách rỗng (isEmpty)

. Kiểm tra danh sách đầy (isFull)

. Tính kích thước (sizeOf)

. Xóa rỗng danh sách (clear)

. Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert)

. Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách

(remove)

. Lấy một phần tử tại một vị trí cụ thể (retrieve)

. Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace)

. Duyệt danh sách và thực hiện một thao tác tại các vị trí trong

danh sách (traverse)

Danh sách

kế tiếp

▪ Sử dụng một vector lưu trữ gồm một số các ô nhớ liên tiếp

▫ Các phần tử liền kề nhau được lưu trữ trong những ô nhớ liền

kề nhau

▫ Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ tự

được lưu trữ trong vector

▫ Tham chiếu đến các phần tử sử dụng địa chỉ được tính giống

như lưu trữ mảng.

last

n-1

Danh sách

kế tiếp

▪ Ưu điểm

▫ Tốc độ truy cập vào các phần tử của danh sách nhanh

▪ Nhược điểm

▫ Cần phải biết trước kích thước tối đa của danh sách

▫ Thực hiện các phép toán bổ sung các phần tử mới và loại bỏ các

phần tử cũ khá tốn kém

Thêm vào

danh sách kế tiếp

▪ Điều kiện tiên quyết:

▫ Danh sách phải được khởi tạo rồi

▫ Danh sách chưa đầy

▫ Phần tử thêm vào chưa có trong danh sách

▪ Điều kiện hậu nghiệm:

▫ Phần tử cần thêm vào có trong danh sách

insert(3, ‘z’)

0 1 2 3 4 5 6 7 8 9

a b c d e f g h

count=98

Thêm vào

danh sách kế tiếp

Algorithm Insert

Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào

Output: tình trạng danh sách

if list đầy

return overflow

if index nằm ngoài khoảng [0..count]

return range_error

//Dời tất cả các phần tử từ index về sau 1 vị trí

for i = count-1 down to index

entry[i+1] = entry[i]

entry[index] = element // Gán element vào vị trí index

count++

// Tăng số phần tử lên 1

return success;

End Insert

Xóa khỏi

danh sách kế tiếp

remove(3, ‘d’)

0 1 2 3 4 5 6 7 8 9

a b c d e f g

count=7

Xóa khỏi

danh sách kế tiếp

Algorithm Remove

Input: index là vị trí cần xóa bỏ, element là giá trị lấy ra được

Output: danh sách đã xóa bỏ phần tử tại index

if list rỗng

return underflow

if index nằm ngoài khoảng [0..count-1]

return range_error

element = entry[index] //Lấy element tại vị trí index ra

count--

//Giảm số phần tử đi 1

//Dời tất cả các phần tử từ index về trước 1 vị trí

for i = index to count-1

entry[i] = entry[i+1]

return success;

End Remove

Duyệt

danh sách kế tiếp

Algorithm Traverse

Input: hàm visit dùng để tác động vào từng phần tử

Output: danh sách được cập nhật bằng hàm visit

//Quét qua tất cả các phần tử trong list

for index = 0 to count-1

Thi hành hàm visit để duyệt phần tử entry[index]

End Traverse

Danh sách

nối đơn

INFO

▪ Một phần tử trong danh

sách bằng một nút

▪ Thành phần một nút:

▫ INFO: chứa thông tin

(nội dung, giá trị) ứng

với phần tử

▫ NEXT: chứa địa chỉ

của nút tiếp theo

▪ Cần nắm được địa chỉ

của nút đầu tiên trong

danh sách

Danh sách

nối đơn

▪ Nút = dữ liệu + móc nối

▪ Định nghĩa:

typedef struct hoso

{ ……

};

typedef struct node {

struct hoso data;

struct node *next; } Node;

▪ Tạo nút mới:

Node *p = malloc(sizeof(Node))

▪ Giải phóng nút:

free(p);

Tải về để xem bản đầy đủ

118 trang Thùy Anh 16380 Free

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 7, Phần 1: Cấu trúc dữ liệu", để 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_ky_thuat_lap_trinh_chuong_7_phan_1_cau_truc_du_lie.pdf