Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách (List) - Đỗ Ngọc Như Loan

Danh sách (List) 
GV: Đỗ Ngọc Như Loan 
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 
Danh sách liên kết đơn 
Danh sách liên kết đơn là một tập các nút biểu diễn cấu trúc dữ liệu gồm các đối tượng được sắp đặt theo một trật tự tuyến tính 
Trật tự tuyến tính trong danh sách liên kết được xác định bởi các pointer kết hợp với mỗi đối tượng 
Danh sách liên kết cung cấp một sự biểu diễn mềm dẻo và đơn giản cho các tập động, hỗ trợ các thao tác như tìm kiếm , chèn, xóa v.v 
Ví dụ về một danh sách liên kết đơn 
Mỗi nút x trong DS lưu trữ một đối tượng có một khóa ( có thể có thông tin khác) và một pointer next chỉ đến nút ( đối tượng) kế tiếp 
Nếu next[x]= NULL, thì x là nút cuối cùng còn gọi là đuôi của danh sách 
Danh sách L là rỗng khi L = NULL 
Các thao tác trên danh sách liên kết 
ListInitialize (L) 
ListSearch (L, k) 
ListInsert (L, k) 
ListDelete (L, k) 
ListWalk (L) 
ĐỊNH NGHĨA DANH SÁCH LIÊN KẾT ĐƠN TRONG C++ 
Danh sách các đối tượng có khóa là số nguyên 
typedef struct CELL *LIST; 
struct CELL { 
	 int key; 
	 LIST next; 
	 }; 
LIST L; 
ListInitialize 
void ListInitialize(LIST &L ) 
{ 
	L=NULL ; 
} 
ListSearch 
Thao tác ListSearch(L, k) tìm một đối tượng có khóa k trong danh sách L 
Nếu có đối tượng có khóa k, thủ tục sẽ trả về một pointer chỉ đến đối tượng này 
Nếu không có đối tượng nào có khóa bằng k trong danh sách , thủ tục trả về NULL 
ListSearch 
LIST ListSearch(LIST L, int k) 
{ 
	LIST x; 
	x=L ; 
	while(x !=NULL && x->key!=k) x=x->next; 
	return x; 
} 
ListInsert 
Thao tác ListInsert(L, k) thực hiện đơn giản bằng cách chèn đối tượng x có khóa k vào đầu của L 
ListInsert 
void ListInsert(LIST &L, int k) 
{ 
	LIST x; 
	x=new(CELL ); 
	x- >key=k; 
	x- >next=L; 
	L=x ; 
} 
ListDelete 
Thao tác ListDelete(L, k) xóa đối tượng x có khóa k khỏi L 
Được thực hiện bằng cách tìm x và cập nhật lại các con trỏ nút y đi trước x để loại x ra khỏi danh sách 
ListDelete 
void ListDelete(LIST &L,int k) 
{ 
 LIST x, y; 
 if(L != NULL) 
 { 
	 y = NULL; x =L; 
	 while(x !=NULL && x->key!=k) 
	 { 
	 y=x ; x=x->next; 
	 } 
	 if(x !=NULL) //Tìm thấy 
	 { 
	 if(y ==NULL) L=x->next; //nút cần xóa ở đầu DS 
	 else y->next=x->next; // Loại bỏ nút x khỏi DS 
	 delete x; // Xóa khỏi bộ nhớ 
	 } 
 } 
} 
ListWalk (Duyệt DS) 
void ListWalk(LIST L) 
{ 
	if(L !=NULL) 
	{ 
	cout key)<<' '; 
	ListWalk(L- >next); 
	} 
} 
ĐỘ PHỨC TẠP CÁC THAO TÁC 
ListSearch(L , k) có độ phức tạp trung bình T(n) = O(n) 
ListInsert(L , k) có độ phức tạp T(n)=O(1) 
ListDelete(L , k) có độ phức tạp trung bình T(n) = O(n) 
DANH SÁCH LIÊN KẾT KÉP 
Danh sách liên kết kép là cấu trúc dữ liệu trong đó các đối tượng được sắp đặt theo một trật tự tuyến tính 
Trật tự tuyến tính trong danh sách liên kết kép được xác định bởi một cặp pointer trong mỗi đối tượng 
ĐỊNH NGHĨA DANH SÁCH LIÊN KẾT KÉP TRONG C++ 
Danh sách các đối tượng có khóa là số nguyên 
typedef struct CELL *LIST; 
struct CELL { 
	int key; 
	LIST prev, next; 
	}; 
LIST L; 
ListInitialize 
void ListInitialize(LIST &L ) 
{ 
	L=NULL ; 
} 
ListSearch 
Thao tác ListSearch(L, k) tìm một phần tử có khóa k trong danh sách L 
Nếu có phần tử có khóa k, thủ tục sẽ trả về một pointer chỉ đến phần tử này 
Nếu không có đối tượng nào có khóa bằng k trong danh sách , thủ tục trả về NULL 
ListSearch 
LIST ListSearch(LIST L, int k) 
{ 
	LIST x; 
	x=L ; 
	while(x !=NULL && x->key!=k) x=x->next; 
	return x; 
} 
ListInsert 
Thao tác ListInsert(L, x) thực hiện đơn giản bằng cách chèn x vào đầu của DS 
void ListInsert(LIST &L, int k) 
{ 
	LIST x; 
	x=new(CELL); x->key=k; 
	 x- > prev=NULL; 
	x->next=L; 
	if(L!=NULL) L->prev=x; 
	L = x; 
} 
ListDelete 
Thao tác ListDelete(L, x) xóa x khỏi L 
Được thực hiện bằng cách cập nhật lại các con trỏ khi biết con trỏ tới x để loại x ra khỏi danh sách 
ListDelete 
void ListDelete(LIST &L, int k) 
{ 
	LIST x=L; 
	while(x !=NULL && x->key!=k) x=x->next; 
	if(x !=NULL) 
	{ 
	if(x- >prev!=NULL) x->prev->next=x->next; 
	else L = x->next; 
	if(x- >next!=NULL) x->next->prev=x->prev; 
	delete x; 
	} 
} 
ListWalk (Duyệt DS) 
void ListWalk(LIST L) 
{ 
	if(L !=NULL) 
	{ 
	cout key)<<' '; 
	ListWalk(L- >next); 
	} 
} 
ĐỘ PHỨC TẠP CÁC THAO TÁC 
Độ phức tạp các thao tác trên DSLK kép tương tự như trên DSLK đơn 
Thuật toán sắp xếp nào? 
Điểm khác nhau giữa 
Danh sách liên kết và Mảng ? 
Yêu cầu: Cho dãy số nguyên. Hãy tính tổng của dãy số này. 
Dữ liệu vào từ file TONG.INP có dạng: 
	- Dòng đầu là số nguyên N 
	- Dòng thứ hai gồm N số nguyên 
Kết quả ra file TONG.OUT chứa 1 số nguyên là tổng cần tìm. 
Ví dụ: 
TONG.INP 
5 
3 5 2 7 1 
TONG.OUT 
18 
Giải bài toán này bằng cách sử dụng danh sách liên kết 
Yêu cầu: Cho dãy số nguyên. Hãy xóa các số chẵn trong dãy. 
Dữ liệu vào từ file XOACHAN.INP có dạng: 
	- Dòng đầu là số nguyên N 
	- Dòng thứ hai gồm N số nguyên 
Kết quả ra file XOACHAN.OUT chứa dãy số sau khi đã xóa các số chẵn. 
Ví dụ: 
XOACHAN.INP 
5 
3 5 2 7 1 
XOACHAN.OUT 
3 5 7 1 
Giải bài toán này bằng cách sử dụng danh sách liên kết 
Yêu cầu: Cho dãy số nguyên có N phần tử và số nguyên x. Hãy chèn số x vào vị trí k trong dãy (vị trí tính bắt đầu từ 0, k < N). 
Dữ liệu vào từ file CHEN.INP có dạng: 
	- Dòng đầu là số nguyên N, x, k 
	- Dòng thứ hai gồm N số nguyên 
Kết quả ra file CHEN.OUT chứa dãy số sau khi đã chèn x. 
Ví dụ: 
CHEN.INP 
5 9 3 
3 5 2 7 1 
CHEN.OUT 
3 5 2 9 7 1 
Giải bài toán này bằng cách sử dụng danh sách liên kết 
Liệt kê 3 loại danh sách liên kết đã học? 
Độ phức tạp trung bình của các thao tác ListSearch(L,k), ListInsert(L,k) là bao nhiêu? 
Chỉnh sửa lại đoạn code trong thao tác ListDelete để có thể xóa phần tử cuối của danh sách liên kết đơn. 
Có bao nhiêu người trả lời đúng hết 3 câu trên? 
STACK 
QUEUE 
STACK (NGĂN XẾP) 
Biểu diễn một tập động (dynamic set) mà thao tác chèn và xóa theo nguyên lý vào sau ra trước (last in, first out hay LIFO) 
Stack là mô hình dữ liệu được ứng dụng nhiều trong thực tế 
Trong khoa học máy tính stack được dùng để quản lý quá trình gọi và thực thi chương trình con 
CÁC THAO TÁC TRÊN STACK 
StackInitialize(S ): Khởi tạo stack 
Push(S , x): Chèn vào stack S một phần tử 
Pop(S ): Loại khỏi stack một phần tử 
StackEmpty(S ): Kiểm tra stack rỗng 
StackFull(S ): Kiểm tra stack đầy 
BIỂU DIỄN STACK 
Dùng mảng một chiều n phần tử S[1..n] 
Dùng danh sách được liên kết (khi số phần tử trong stack không bị hạn chế) 
BIỂU DIỄN STACK BẰNG MẢNG 
Ký hiệu top[S] là đỉnh stack (chỉ đến phần tử được chèn vào gần nhất) 
Tại một thời điểm stack bao gồm các phần tử S[1], S[2 ], , S[top[S]] 
Trong đó S[1] là phần tử ở đáy và S[top[S]] là phần tử ở đỉnh stack 
BIỂU DIỄN STACK BẰNG MẢNG 
Nếu top[S] = 0, stack rỗng 
Nếu top[S] = n, stack đầy 
Mỗi lần thao tác push thực hiện top[S] tăng lên 1 
Mỗi lần thao tác pop thực hiện top[S] giảm đi 1 
BIỂU DIỄN STACK BẰNG MẢNG 
Ví dụ: 
9 
2 
8 
9 
2 
8 
3 
9 
2 
8 
3 
1 
t op[S] = 3 
t op[S] = 4 
t op[S] = 5 
1 2 3 4 5 6 
BIỂU DIỄN STACK BẰNG MẢNG 
Biểu diễn stack trong C++, mỗi phần tử là một số nguyên 
#define MAX 200 
struct STACK{ 
	int a[MAX]; 
	int top; 
	int N; //kich thuoc stack 
}; 
STACK S; 
StackInitialize 
void StackInitialize(STACK &S) 
{ 
	S.top=0 ; 
	S.N=30 ; 
} 
StackEmpty 
bool StackEmpty(STACK S) 
{ 
	if(S.top ==0) return true; 
	else return false; 
} 
StackFull 
bool StackFull(STACK S) 
{ 
	if(S.top ==S.N) return true; 
	else return false; 
} 
Push 
void Push(STACK &S, int x) 
{ 
	if(StackFull(S )) cout<<"overflows"; 
	else { 
	S.top=S.top+1 ; 
	S.a[S.top ]=x; 
	} 
} 
POP 
int pop(STACK &S) 
{ 
	if(StackEmpty(S )) { 
	 	cout <<"underflows"; 
	 	return -1 ; 
	 } 
	 else { 
	S.top=S.top-1 ; 
	return S.a[S.top+1]; 
	} 
} 
BIỂU DIỄN STACK BẰNG DSLK 
Tại một thời điểm stack bao gồm một tập (không bị hạn chế ) các phần tử 
Phần tử đầu tiên của stack là phần tử đầu tiên của DS được trỏ bởi top[S] 
Phần tử ở đáy của stack là phần tử cuối cùng của DS 
BIỂU DIỄN STACK BẰNG DSLK 
Ðịnh nghĩa stack trong C ++ 
typedef struct CELL *STACK; 
struct CELL { 
	int Obj; 
	STACK next; 
}; 
STACK S; 
StackInitialize 
void StackInitialize(STACK & S) 
{ 
	S=NULL ; 
} 
StackEmpty 
bool StackEmpty(STACK S) 
{ 
	if(S ==NULL) return true; 
	else return false; 
} 
StackFull 
bool StackFull(STACK S) 
{ 
	return false; 
} 
PUSH 
void Push(STACK &S, int x) 
{ 
	STACK p; 
	p=new(CELL ); 
	p- >Obj=x; 
	p- >next=S; 
	S=p ; 
} 
POP 
int Pop(STACK &S) 
{ 
	 int x; 
	STACK p; 
	if(StackEmpty(S )) {cout<<"underflows"; return -1;} 
	else { 
	p=S ; 
	S=p- >next; 
	x=p- >Obj; 
	delete(p ); 
	return x; 
	}	 
} 
QUEUE (HÀNG ĐỢI) 
Biểu diễn một tập động (dynamic set) mà thao tác chèn và xóa theo nguyên lý vào trước ra trước (First in, first out hay FIFO ) 
Queue là mô hình dữ liệu được ứng dụng nhiều trong thực tế 
Queue có thể được ứng dụng trong quá trình quản lý và thực thi có trật tự các chương trình của một hệ điều hành 
CÁC THAO TÁC TRÊN QUEUE 
QueueInitialize(Q ): Khởi tạo hàng đợi 
Enqueue(Q , x): Chèn vào queue một phần tử 
Dequeue(Q ): Loại khỏi queue một phần tử 
QueueEmpty(Q ): Kiểm tra queue rỗng 
QueueFull(Q ): Kiểm tra queue đầy 
BIỂU DIỄN QUEUE 
Có thể dùng một mảng một chiều với n phần tử Q[1.. n] để biểu diễn một hàng đợi tối đa n - 1 phần tử 
Có thể dùng danh sách liên kết 
Mỗi hàng đợi có một đầu (head) và một đuôi (tail) 
Một phần tử được đưa vào hàng đợi tại đuôi của nó 
Phần tử bị loại khỏi hàng đợi là phần tử ở đầu hàng đợi 
BIỂU DIỄN QUEUE BẰNG MẢNG 
Ký hiệu head[Q] và tail[Q] là đầu và đuôi của hàng đợi 
Các phần tử trong hàng đợi được đặt tại các vị trí head[Q], head[Q]+1,..., tail[Q ] và coi vị trí 1 đi ngay sau vị trí n trong một trật tự “vòng ” 
head[Q] = tail[Q] = 0 thì hàng đợi rỗng (khởi tạo hàng đợi rỗng : head[Q] = tail[Q] = 0) 
Khi head[Q] = tail[Q] + 1 hoặc tail[Q]=n và head[Q] = 1 thì hàng đợi đầy 
BIỂU DIỄN QUEUE BẰNG MẢNG 
Ví dụ: 
8 
3 
1 
9 
8 
3 
1 
4 
9 
3 
1 
4 
8 
3 
1 
4 
1 2 3 4 5 6 
head[Q] = 3 
tail[Q] = 5 
head[Q] = 3 
tail[Q] = 6 
head[Q] = 3 
tail[Q] = 1 
head[Q] = 4 
tail[Q] = 1 
BIỂU DIỄN QUEUE 
typedef struct QUEUE{ 
	int a[MAX]; 
	int head, tail; 
	int n; 
}; 
QUEUE Q; 
QueueInitialize 
void QueueInitialize(QUEUE &Q) 
{ 
	Q.head=Q.tail=0; 
	Q.n=20 ; //tùy chọn 
} 
QueueEmpty 
bool QueueEmpty(QUEUE Q) 
{ 
	if (Q.head==0) return true; 
	else return fasle; 
} 
QueueFull 
bool QueueFull(QUEUE Q) 
{ 
	if ((Q.tail==Q.n&&Q.head==1 )|| 
	 	( Q.head==Q.tail+1)) 
	return true; 
	else return fasle; 
} 
Enqueue 
void Enqueue(QUEUE &Q, int x) 
{ 
	if(QueueFull(Q )) cout<<"overflow"; 
	else { 
	if(Q.tail ==Q.n) Q.tail=1; 
	else Q.tail=Q.tail+1 ; 
	Q.a[Q.tail ]=x ; 
	if (Q.head==0) Q.head = 1; 
	} 
} 
Dequeue 
int Dequeue(QUEUE &Q) 
{	int x; 
	if(QueueEmpty(Q )){ 
	 	cout <<"underflow"; 
	 	return -1 ; 
	 } else { 
	x=Q.a[Q.head]; 
	 	if (Q.head==Q.tail) // chi con 1 phan tu 
	Q.head = Q.tail = 0; 
	else { 
	if(Q.head ==Q.n) Q.head=1; 
	else Q.head=Q.head+1 ; } 
	return x; 
	} 
} 
BIỂU DIỄN QUEUE BẰNG DSLK 
Tại một thời điểm queue bao gồm một tập (không bị hạn chế ) các phần tử 
Phần tử đầu tiên của DS là phần tử ở đầu của queue được trỏ bởi head[Q] 
Phần tử cuối của queue là phần tử cuối của DS được trỏ bởi tail[Q] 
BIỂU DIỄN QUEUE BẰNG DSLK 
Định nghĩa queue mà mỗi phần tử là một số nguyên 
typedef struct CELL *LIST; 
struct CELL { 
	int Obj; 
	LIST next; 
	}; 
struct QUEUE { 
	LIST head, tail; 
}; 
QUEUE Q; 
QueueInitialize 
void QueueInitialize(QUEUE &Q) 
{ 
	Q.head=Q.tail=NULL ; 
} 
QueueEmpty 
bool QueueEmpty(QUEUE Q) 
{ 
	if(Q.head ==NULL) return true; 
	else return false; 
} 
Enqueue 
void Enqueue(QUEUE &Q,int x) 
{ 
	LIST p; 
	p=new(CELL ); 
	p- >Obj=x; 
	p- >next=NULL; 
	if(Q.head ==NULL) Q.head=p; 
	else Q.tail->next=p; 
	Q.tail=p ; 
} 
Dequeue 
int Dequeue(QUEUE &Q) 
{ 
	int x; 
	LIST p; 
	if(QueueEmpty(Q )){cout<<"underflows"; return -1;} 
	else { 
	p=Q.head ; 
	x=p- >Obj; 
	if(Q.head ==Q.tail) {Q.head=Q.tail=NULL;} 
	else Q.head=p->next; 
	delete p; 
	return x; 
	} 
} 
ĐỘ PHỨC TẠP CÁC THAO TÁC TRÊNSTACK VÀ QUEUE 
Các thao tác trên stack có độ phức tạp là O(1) 
Các thao tác trên queue có độ phức tạp là O(1) 
HÀNG ÐỢI Ư U TIÊN 
Hàng đợi ưu tiên (priority queue) gồm một tập đối tượng trong đó đối tượng có khoá ưu tiên được xử lý trước 
Dùng max-heap để biểu diễn hàng đợi ưu tiên theo khóa lớn hơn 
Dùng min-heap để biểu diễn hàng đợi ưu tiên theo khóa nhỏ hơn 
BIỂU DIỄN HÀNG ĐỢI ƯU TIÊN BẰNG MAX-HEAP 
# define MAX 1000 
struct HEAP { 
	int heap_size; 
	int x[MAX]; 
}; 
CÁC THAO TÁC TRÊN HÀNG ĐỢI  ƯU TIÊN 
Thao tác trên hàng đợi ưu tiên (theo khóa lớn ) 
QueueInitialize(Q ) 
QueueInsert(Q , x) 
QueueExtractMax(Q ) 
QueueIncreaseKey(Q , x, k) 
QueueInitialize 
void QueueInitialize(HEAP &Q) 
{ 
	Q.heap_size=0 ; 
} 
QueueExtractMax 
QueueExtractMax(Q) loại phần tử được ưu tiên nhất ra khỏi hàng đợi Q 
int QueueExtractMax(HEAP &Q) 
{ 
	int max; 
	if(Q.heap_size<1 ) { 
	cout <<“Error Heap Undeflow!\n "; 
	return -1; 
	} 
	else { 
	max=Q.x[1 ]; 
	Q.x[1 ]=Q.x[Q.heap_size]; 
	Q.heap_size = Q.heap_size-1; 
	MaxHeapify(Q,1 ); 
	return max ; 
	| 
} 
QueueExtractMax 
void MaxHeapify(HEAP &Q, int i) 
{ 
	int l, r, largest; 
	l = Left(i); r = Right(i); 
	if(l Q.x[i ]) largest=l ; 
	else largest=i; 
	if(r Q.x[largest]) 	largest=r ; 
	if(largest !=i) 
	{ 
	Exchange(Q.x[i ], Q.x[largest]); 
	MaxHeapify(Q,largest ); 
	} 
} 
QueueExtractMax 
Thời gian chạy của QueueExtractMax(Q) là O(log 2 n ) trên một heap n phần tử 
QueueIncreaseKey 
QueueIncreaseKey(Q , i, key) tăng khoá tại nút i lên thành khoá key 
D i chuyển phần tử có khóa key từ nút i hướng đến gốc để tìm nơi chính xác cho nút nhận khoá này 
QueueIncreaseKey 
void QueueIncreaseKey(HEAP &Q, int i, int key) 
{ 
	if(key<Q.x[i ]) cout<<“ Error: new key is smaller current key!\n"; 
	Q.x[i ]=key; 
	while ((i>1)&&(Q.x[parent(i)]<Q.x[i])) 
	{ 
	Exchange(Q.x[i ], Q.x[parent(i)]); 
	i=parent(i ); 
	} 
} 
QueueIncreaseKey 
Thời gian chạy của QueueIncreaseKey tối đa là O(log 2 n) trên một heap n phần tử 
QueueInsert 
QueueInsert(Q , key) chèn một phần tử có khoá key vào một hàng đợi ưu tiên (max-heap) 
Đầu tiên, mở rộng heap bằng cách thêm vào một lá mới 
Áp dụng QueueIncreaseKey để tăng khóa key cho nút lá này 
QueueInsert 
void QueueInsert(HEAP &Q, int key) 
{ 
	Q.heap_size = Q.heap_size+1; 
	Q.x[Q.heap_size]=-1000000; 
	QueueIncreaseKey(Q , Q.heap_size, key); 
} 
QueueInsert 
Thời gian chạy của QueueInsert tối đa là O(log 2 n ) trên một heap n phần tử 
Yêu cầu: Cho dãy số nguyên. Hãy tính tổng của dãy số này. 
Dữ liệu vào từ file SUM.INP có dạng: 
	- Dòng đầu là số nguyên N 
	- Dòng thứ hai gồm N số nguyên 
Kết quả ra file SUM.OUT chứa 1 số nguyên là tổng cần tìm. 
Ví dụ: 
SUM.INP 
5 
3 5 2 7 1 
SUM.OUT 
18 
Giải bài toán này bằng cách sử dụng QUEUE 
Yêu cầu: V iết chương trình đổi 1 số từ hệ thập phân sang hệ nhị phân 
Dữ liệu vào từ file NP.INP chứa số nguyên N ở hệ thập phân 
Kết quả xuất ra file NP.OUT chứa kết quả sau khi đã đổi N sang hệ nhị phân 
Ví dụ: 
NP.INP 
9 
NP.OUT 
1001 
Giải bài toán này bằng cách sử dụng STACK