Bài giảng Ngôn ngữ lập trình - Chương 8: Danh sách móc nối

CH ƯƠ NG VIIIDANH SÁCH MÓC NỐI 
	Ta th ươ ng sử dụng mảng cấu trúc đ ể xử lý với nhóm dữ liệu. Đây là một cách tiếp cận đ úng khi ta biết tr ư ớc chính xác số các cấu trúc cần có. Tuy nhiên, khi con số này không rõ ràng, mãng sẽ trở nên khá tốn kém vì chúng phải đư ợc cấp phát đ ủ bộ nhớ đ ể hoạt đ ộng. Bố nhớ này đư ợc đă ng ký và sẽ không dành cho nhứng tác vụ khác ngay cả khi ta chỉ dùng một sô nhỏ các phần tử mảng. 
	Ph ươ ng h ư ớng giải quyết cho vấn đ ề này là cho phép cấp phát bộ nhớ cho một cấu trúc mới khi cần thiết. 
	C cho phép ta thực hiện đ iều này thông qua cáhc cấp phát bộ nhớ đ ộng bằng: 
	 malloc() và calloc() 
	Nh ư ng các cấu trúc nếu đư ợc cấp pháp xong sẽ không có đ ảm báo nào rằng các cấu trúc sẽ đư ợc đ ặt liên tiếp nhau trong bộ nhớ. Do đ ó đ iều cần thiết là kỹ thuật đ ể nối kết tất cả các cấu trúc lại với nhau. 
	Ph ươ ng cách thông dụng đ ể kết nối các phần tử đ ó lại là dùng danh sách liên kết (Linked list) 
Danh sách liên kết đơ n: 
Định nghĩa 
	Cú pháp: 
	struct 
	{ 
	 ; 
	struct * 
	} 
	Ví dụ: Định nghĩa một danh sách liên kết đ ể chứa các số nguyên. 
	struct Point 
	{ 
	int info; 
	struct Point *Next; 
	}; 
Các phép toán trên danh sách liên kết 
Cấp phát bô nhớ cho biến con trỏ mới 
	Cú pháp: 
	Point_New = (struct Point_Name *) malloc 	(sizeof(struct Point_Name) 
Ví dụ: 
	typedef struct Point POINT; 
	POINT Head, Last, p; 
	CreatNode() 
	{ 
	p=(POINT *) malloc (POINT) 
	if (Head==(POINT* ) NULL) 
	Head=Last=p; 
	else 
	{ 
	Last=Head; 
	while (Last->Next!= (POINT*) NULL) 
	Last=Last->Next; 
	Last->Next=p; 
	Last=p; 
	} 
	printf(“\nInput information for Node”); 
	scanf(“%d”, p->.info); 
	Last->Next=(POINT *) NULL; 
	return; 
	} 
Xoá một con trỏ: 
	Cú pháp: 
	free(Point_Variable) 
	Giải phóng vùng nhớ đư ợc trỏ bởi Point_Variable 
Các phép toán th ươ ng dùng trong danh sách liên kết 
Tạo một phần t ư của danh sách 
	Điều phải làm là cấp pháp bộ nhớ cho cấu trúc và trả về con trỏ trỏ đ ến vùng nhớ này. 
	Ví dụ: 
	POINT	*CreatNode() 
	{ 
	POINT	*p; 
	p = (POINT *) malloc (sizeof(POINT)); 
	if (p==NULL) 
	{ 
	printf(“Malloc falled.\n”); 
	exit(1); 
	} 
	printf(“Input data for Node info = ”); 
	scanf(“%d”, p->info); 
	p->Next = NULL 
	return p; 
	} 
Bổ sung phần t ư vào danh sách 
	Hàm CreatNode() chỉ cấp phát bộ nhớ nh ư ng nó không nối phần tử này vào danh sách. Để làm đ iều này, ta cần thêm một hàm nữa, gọi là hàm AddNode(). Đ ư ợc đ ịnh nghĩa nh ư sau: 
	static POINT *Head; 
	void AddNode(POINT *e) 
	{ 
	POINT *p; 
	if (Head ==NULL) 
	{ 
	Head = e; 
	return; 
	} 
	for (p=Head; p->Next!=NULL; p=p->Next); 
	p->Next=e; 
	} 
Chú ý: 
	Biến Head là con trỏ trỏ đ ến đ ầu danh sách, nên cần đư ợc khai báo đ ầu ch ươ ng trình.(Sau phần khai đ ịnh nghĩa kiểu con trỏ). 
Chèn phần t ư vào danh sách 
	Để chèn phần tử vào danh sách liên kết, ta phải chỉ rỏ phần tử mới sẽ đư ợc chèn vào vị trí nào.Sau đ ây là hàm sẽ thực hiện công việc trên. 
	void InsertNode(POINT *p, POINT *q) 
	{ 
	if (p=NULL || q=NULL || p==q || q->Next ==p) 
	{ printf (“Cannot Insert \n”); 
	 return; 
	} 
	p->Next =q->Next; 
	q->Next=p; 
	}; 
Xoá phần t ư vào danh sách 
	Xoá một phần tử khỏi danh sách liên kết đơ n, ta cần phải tìm phần tử tr ư ớc phần tử cần xoá đ ể nhằm mục đ ích nối lại với phần tử sau phần tử cần xoá. Ta dùng hàm free() đ ể giải phống bộ nhớ chiếm bởi phần tử bị xoá. 
Có thể xây d ư ng là: 
	void DeleteNode(POINT *goner) 
	{ 
	POINT *p; 
	p=Head; 
	if (goner ==Head) 
	Head = goner->Next; 
	else 
	{ while (p!=NULL && p->Next!=goner) 
 	 p=p->Next; 
	 if (p=NULL) 
	{ 
	printf(“Cannot find Node \n”); 
	return; 
	} 
	p->Next=p->Next->Next; 
	}; 
	free(goner) 
}; 
Tìm phần t ư vào danh sách 
	Thật khó tạo một hàm FindNode() tổng quát, bởi vì khi tìm kiếm thì ta phải dựa vào một trong những tr ư ờng dữ liệu của cấu trúc, đ iều này phụ thuộc vào cấu trúc dang sử dụng. Để viết hàm FindNode() tổng quát ta phảisử dụng con trỏ trỏ đ ến hàm. 
	Với cấu trúc trên ta xây dựng hàm FindNode() nh ư sau: 
	POINT *FindNode(int *n) 
	{ 
	POINT *p; 
	for (p=Head; p!=NULL; p=p->Next) 
	if (p->Info=n) 
	return p; 
	return NULL; 
	}; 
Danh sách đ a liên kết 
	Định nghĩa: 
	Cú pháp: 
	struct 
	{ 
	 ; 
	struct *,; 
	} 
	Ví dụ: Định nghĩa một danh sách liên kết đ ể chứa các số nguyên. 
	struct Point 
	{ 
	int info; 
	struct Point *Next,*Previous; 
	}; 
STACK và QUEUE 
STACK 
	Là danh sách có móc nối đ ặc biệt. Mặc dầu ta có thể thực hiệm nhiều phép toán trên danh sách tổng quát, Stack vẫn có những tính chất riêng biệt: chỉ cho phép thêm và xoá bỏ các phần tử ở một vị trí duy nhất, tại đ ỉnh của Stack. 
	Với đ ặc tr ư ng nh ư vậy thì Stack có kiểu cấu trúc dữ liệu là LIFO (Last In First Out) 
Khởi tạo Stack 
	Sử dụng mảng: 
	int stack[100], p; 
	Stackinit() 
	{ 
	p=0; 
	} 
	Sử dụng danh sách liên kết	 
	struct Node { 
	 	 int info; 
 	 	 struct Node *Next; 
	 }; 
	typedef struct Node NODE; 
	NODE *Head, *p, *q; 
	StackInit() 
	{ 
	 Head = (NODE *) malloc (sizeof *Head); 
	 p=(NODE *) malloc (sizeof *p); 
 	Head->Next=p; 
 	Head->info=0; 
 	p->Next=NULL; 
 	return 0; 
	} 
Đẩy dữ liệu vào Stack 
	Sử dụng mảng: 
	Push (int x) 
	{ 
	stack[p++]=x; 
	} 
	Sử dụng danh sách liên kết: 
	Push(int a) 
	{ 
	q=(NODE *) malloc (sizeof *q); 
 	q->info=a; 
 	q->Next=Head->Next; 
 	Head->Next=q; 
 	return 0; 
	} 
Lấy giá trị ra khỏi Stack 
	Sử dụng mảng: 
	Pop (int x) 
	{ 
	return stack[p--]; 
	} 
	Sử dụng danh sách liên kết: 
	Pop() 
	{ 
 	int x; 
 	q=Head->Next; 
 	Head->Next=q->Next; 
 	x=q->info; 
 	free(q); 
 	return x; 
	} 
Kiểm tra Stack rỗng 
	Sử dụng mảng: 
	int stackempty() 
	{ 
	return !p; 
	} 
	Sử dụng danh sách liên kết: 
	int StackEmpty() 
	{ 
	return Head->Next==p; 
	} 
Ví dụ: Xây dựng stack bằng danh sách liên kêt: 
#include "stdio.h" 
#include "alloc.h" 
#define ESC 27 
struct Node 
 { 
 int info; 
 struct Node *Next; 
 }; 
typedef struct Node NODE; 
NODE *Head, *p, *q; 
StackInit() 
{ 
 Head = (NODE *) malloc (sizeof *Head); 
 p=(NODE *) malloc (sizeof *p); 
 Head->Next=p; 
 Head->info=0; 
 p->Next=NULL; 
 return 0; 
} 
Push(int a) 
{ 
 q=(NODE *) malloc (sizeof *q); 
 q->info=a; 
 q->Next=Head->Next; 
 Head->Next=q; 
 return 0; 
} 
Pop() 
{ 
 int x; 
 q=Head->Next; 
 Head->Next=q->Next; 
 x=q->info; 
 free(q); 
 return x; 
} 
int StackEmpty() 
{ 
return Head->Next==p; 
} 
void main() 
{ 
 int b; 
 char c; 
 StackInit(); 
 do 
 { 
 clrscr(); 
 printf("\nNhap gia tri vao Stack "); 
 scanf("%d",&b); 
 Push(b); 
	printf("\nAn Enter de tiep tuc/ESC de thoi nhap"); 
 c=getchar(); 
 c=getch(); 
 } 
 while(c!=ESC); 
 printf("\nCac gia tri trong Stack\n"); 
 while (!StackEmpty()) printf("%d ",Pop()); 
 printf("\nAn ESC de ket thuc"); 
 getch(); 
} 
Queue 
	Queue hay còn gọi là hàng đ ợi, đ ây là một kiểu danh sách đ ặc biệt. Các phần tử đư ợc thêm vào từ một đ ầu, đư ợc gọi là đ ầu sau, và lấy ra một đ ầu khác, đư ợc gọilà đ ầu tr ư ớc. 
	Cấu trúc này đư ợc sử dụng trong các tình huống lập trình cần xử lý một dãy các phần tử theo một trật tự cố đ ịnh. Việc xử lý này gọi là FIFO (First Int First Out).