thankyou010587
New Member
Download miễn phí Bài giảng Cấu trúc dữ liệu động
DS có thứ tự là DS mà các phần tử được sắp xếp theo
một thứ tự nào đó dựa trên trường khoá. Ðể sắp xếp
một danh sách, có 2 phương án:
Phương án 1: Hoán vị nội dung các phần tử trong danh sách
Sử dụng các thuật toán sắp xếp như trên mảng, dựa trên việc
hoán vị nội dung của các phần tử
Phương pháp này đòi hỏi sử dụng vùng nhớ trung gian, số lần
hoán vị có thể lên đến bậc n^2. Làm cho thao tác sắp xếp chậm
không tận dụng được các ưu điểm của DSLK
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
b;}
7
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Trong trường hợp, tại thời ñiểm biên dịch không thể xác
ñịnh trước kích thước chính xác của ñối tượng dữ
liệu(do chúng phụ thuộc vào ngữ cảnh). Các ñối tượng
dữ liệu này ñược khai báo như biến ñộng.
Biến ñộng là những biến thỏa:
3.1.3. Biến ñộng
Không ñược khai báo tường minh.
ðược cấp phát/giải phóng bộ nhớ khi yêu cầu.
Các biến này không theo qui tắc phạm vi.
Vùng nhớ của biến ñược cấp phát trong Heap.
Kích thước thay ñổi trong quá trình sống.
8
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Các thao tác trên biến ñộng:
Tạo biến ñộng và cho con trỏ p trỏ ñến:
Các hàm cấp phát bộ nhớ:
void* malloc(size); // trả về con trỏ chỉ ñến một vùng
// nhớ size byte vừa ñược cấp phát.
void* calloc(n,size);// trả về con trỏ chỉ ñến một vùng
// nhớ vừa ñược cấp phát gồm n
//phần tử,mỗi phần tử có kích
//thước size byte
new // hàm cấp phát bộ nhớ trong C++
9
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Hủy một biến ñộng do p chỉ ñến:
Hàm free(p): Huỷ vùng nhớ cấp phát bởi hàm
malloc do p trỏ tới
Hàm delete p: huỷ vùng nhớ cấp phát bởi hàm
new do p trỏ tới
10
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ:
//Trong C
int* p1, p2;
//Cấp phát vùng nhớ cho 1 biến ñộng kiểu int
p1 = (int*)malloc(sizeof(int));
//ðặt giá trị 5 cho biến ñộng p1
p1* = 5;
//Cấp phát biến ñộng kiểu mảng 10 p.tử kiểu int
p2 = (int*)calloc(10, sizeof(int));
//ðặt giá trị 0 cho phần tử thứ 4 của mảng p2
(p2+3)* = 0;
free(p1); free(p2);
//Trong C++
int* p;
p=new int;
delete p;
11
3.2. Danh Sách Liên Kết
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa
3.2.2. Các hình thức tổ chức danh sách
12
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa
Kiểu danh sách Tx gồm các phần tử thuộc kiểu T
ñược ñịnh nghĩa là:
Tx =
trong ñó:
Vx = {tập hợp có thứ tự các phần tử kiểu T ñược
móc nối với nhau theo trình tự tuyến tính};
Ox = {Tạo danh sách; Tìm 1 phần tử trong danh
sách; Chèn một phần tử vào danh sách; Huỷ một phần
tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh
sách ...}
13
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví du: Hồ sơ các học sinh của một trường ñược tổ
chức thành danh sách gồm nhiều hồ sơ của từng học
sinh; số lượng học sinh trong trường có thể thay ñổi
do vậy cần có các thao tác thêm, hủy một hồ sơ; ñể
phục vụ công tác giáo vụ cần thực hiện các thao tác
tìm hồ sơ của một học sinh, in danh sách hồ sơ ...
14
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.2. Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử ñược thể hiện ngầm:
Mỗi phần tử trong danh sách ñược ñặc trưng
bằng chỉ số.
Cặp phần tử xi, xi+1 ñược xác ñịnh là kế cận
Với hình thức tổ chức này, các phần tử của danh
sách phải lưu trữ liên tiếp trong bộ nhớ, công thức
xác ñịnh ñịa chỉ phần tử thứ I là.
Cách biểu diễn này cho phép truy xuất ngẫu nhiên,
ñơn giản và nhanh chóng ñến một phần tử bất kỳ
trong danh sách, nhưng lại hạn chế về mặt sử
dụng bộ nhớ bị lãng phí.
15
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Mối liên hệ giữa các phần tử thể hiện tường minh:
Mỗi phần tử ngoài các thông tin còn chứa một liên
kết (ñịa chỉ) ñến phần tử kế trong danh sách nên
còn ñược gọi là danh sách móc nối.
Với hình thức này các phần tử trong danh sách
không cần lưu trữ kế cận trong bộ nhớ nên
khắc phục ñược các khuyết ñiểm của hình thức tổ
chức mảng, nhưng việc truy xuất ñến một phần tử
ñòi hỏi phải thực hiện truy xuất qua một số phần tử
khác.
16
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Có các kiểu tổ chức liên kết giữa các phần tử.
Danh sách liên kết ñơn
Danh sách liên kết kép
Danh sách liên kết vòng
17
3.3. Danh Sách Liên Kết ðơn
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết
3.3.2. Các thao tác cơ bản trên danh sách ñơn
18
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết
Mỗi phần tử là một cấu trúc chứa 2 thông tin :
- Thành phần dữ liệu: Lưu trữ các thông tin về bản thân
phần tử .
- Thành phần mối liên kết: lưu trữ ñịa chỉ của phần tử
kế tiếp trong danh sách, hay lưu trữ giá trị NULL nếu
là phần tử cuối danh s ách.
Ta có ñịnh nghĩa tổng quát
struct tNode
{
DataType key;
tNode* pNext;
};
19
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ: Ðịnh nghĩa danh sách ñơn lưu trữ hồ sơ SV
struct tSinhVien
{
char Ten[30];
int MaSV;
};
typedef struct tSinhVien Sinhvien;
struct SinhvienNode
{
Sinhvien Info;
SinhvienNode* pNext;
};
typedef struct SinvienNode SVNode;
20
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Nếu biết ñược ñịa chỉ của phần tử ñầu tiên trong danh
sách ñơn thì có thể dựa vào thông tin pNext của nó ñể
truy xuất ñến phần tử thứ 2, thứ 3... ðể quản lý một
xâu ñơn chỉ cần biết ñịa chỉ phần tử ñầu xâu. Con trỏ
Head dùng ñể lưu trữ ñịa chỉ phần tử ñầu xâu
Khai báo:
NODE *pHead;
Ðể tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ
ñịa chỉ phần tử cuối xâu.
Khai báo:
NODE *pTail;
21
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.2. Các thao tác cơ bản trên danh sách ñơn
22
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Các ñịnh nghĩa, Khởi tạo danh sách LK ðơn:
struct tNode{
int key;
tNode *pnext;
};
typedef struct tNode *Node;
void Khoitao(List &L){
L.pHead=L.pTail=NULL;
}
struct tList{
node *pHead;
node *pTail;
};
typedef struct tList List;
23
© Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Các hàm con tạo Nút và Huỷ nút :
Node * Taonut(int x){
Node *p;
p=new Node;
p->key=x;
p->pNext=NULL;
return p;
}
void Huy(List &L){
Node *p;
while(L.pHead) {
p=L.pHead;
L.pHead=L.pHead->pNext;
delete p;
}
}
24
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Chèn một phần tử vào ñầu danh sách
Thu
t toán :
Bắt ñầu:
Nếu Danh sách rỗng Thì
B11 : Head = new_elelment;
B12 : Tail = Head;
Ngược lại
B21 : new_ele ->pNext = Head;
B22 : Head = new_ele ;
void Themdau(List &L, Node *p){
if(L.pHead==NULL)
L.pHead=L.pTail=p;
else {
p->pNext=L.pHead;
L.pHead=p;
}
}
25
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void Nhap(List &L)
{
int x;
Node *p;
Khoitao(L);
do
{
cout<<"Nhap gia tri vao danh sach (Nhap 0 ket thuc): ";
cin>>x;
if(x==0)
break;
p=Taonut(x);
Themdau(L,p);
}while(true);
}
26
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void Xuat(List L){
Node *p=L.pHead;
while(p)
{
coutKey<<" ";
p=p->pNext;
}
}
void main()
{
List L;
Nhap(L);
cout<<"\nDanh sach vua nhap: ";
Xuat(l);
Huy(L);
}
27
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Chèn một phần tử vào cuối danh sách
Thu
t toán :
Bắt ñầu :
Nếu Danh sách rỗng Thì
B11 : Head = new_elel...