Bài giảng Cấu trúc dữ liệu và giải thuật - Trường THCN Công kỹ nghệ Việt Tiến

 	data;	list next;	 };Ví dụ: Khai báo một danh sách liên kết có tên là list, mỗi nút có chứa dữ liệu là số nguyên.typedef	struct node * list;	struct	node {	 int	data;	 	 list	 next;	 }; lui2. Khởi tạoInput(Vào): Biến con trỏ đầu (first-head) và cuối (last-tail)Output(Ra): Trả về con trỏ rỗng (NULL) cho đầu và cuối của danh sách liên kết.Cài đặt: void	khoitao(list	* first, list * last){	 *first = * last = NULL;}	3. Truy cậpG/s một nút p của danh sách liên kết gồm có hai trường là data và next.- Truy cập đến nút dữ liệu của nút p là: p -> data- Truy cập đến con trỏ chỉ đến nút tiếp mà p chứa là: p -> next datanextbài 2I. Thêm phần tửCác thuật toán trên DSLK1. Thêm vào đầu danh sách link2. Thêm vào cuối danh sách link 3. Thêm vào vị trí bất kỳ link 1. Thêm vào đầu danh sáchfirstlastpĐặc tả:Vào:	. first, last: con trỏ chỉ đến nút đầu và cuối của dslk	. Giá trị x cần chèn vào đầu dslk.Ra:	Dslk mới đã chèn nút có giá trị là x thành công vào đầu danh sách.Hướng dẫn:	Cấp phát vùng nhớ cho nút p (new), sau đó gán dữ liệu cần chèn x vào trường data và NULL vào trường next của nút p.	Nếu dslk rỗng thì: gán con trỏ first và last bằng con trỏ p. list p = new node; p - > data = x; p -> next = NULL; if(*first == NULL) *last = *first = p;12112	Ngược lại:	 . Gán trường next của con trỏ p bằng con trỏ first;	 . Cập nhập con trỏ first bằng con trỏ p;3 else { p -> next = *first; *first = p; }3Cài đặt:void chendau(list *first, list *last, int x){ list p = new (node); p -> data = x; p -> next = NULL; if(*first = = NULL) *first = *last = p; else { p -> next = *first; *first = p; }}123Bài tập:Viết chương trình thực hiện các thao tác sau trên danh sách liên kết theo cơ chế LIFO (Last In First Out = vào sau ra trước):Nhập từ bàn phím vào 1 dãy số nguyên (nhập số không để thoát)Xuất dãy số vừa nhập ra màn hình.p2. Thêm vào cuối danh sáchfirstlastHướng dẫn: Cấp phát vùng nhớ cho nút p, gán dữ liệu cần chèn x vào trường data và giá trị NULL vào trường next của nút p. Nếu dslk rỗng thì	. Gán con trỏ first và last bằng con trỏ p.12Hướng dẫn: list p = new (node); p - > data = x; p -> next = NULL; if(*first == NULL) *last = *first = p;12 Ngược lại	 . Gán trường next của con trỏ last bằng con trỏ p;	 . Cập nhật con trỏ last bằng con trỏ p;33Hướng dẫn: else { (*last)-> next = p; *last = p; }Bài tập:	Nhập từ bàn phím vào một danh sách liên kết theo cơ chế FIFO, kết thúc việc nhập bằng số không, xuất danh sách vừa nhập ra màn hình.Bài tập:Nhập/ xuất danh sách liên kết số nguyên (LIFO hoặc FIFO)Đếm xem trong danh sách có bao nhiêu nút.Tính tổng các giá trị của các nút.Tính trung bình cộng các nút.3. Thêm vào vị trí bất kỳqfirsttmpplastĐặc tả:Vào:	. Con trỏ first, last chỉ đến nút đầu và cuối của dslk.	. k: vị trí cần thêm.	. x: giá trị cần thêmRa:	. Danh sách mới sau khi thêm nút có giá trị x vào vị trí k của danh sách.Hướng dẫn:	Cấp phát vùng nhớ cho nút tmp, sau đó gán dữ liệu cần chèn x vào trường data và giá trị NULL vào trường next của nút tmp.	Nếu k = 1 thì:	. Thêm vào đầu danh sách.	Ngược lại:	. Xác định vị trí của p và q trong danh sách;	. Nếu k bằng tổng số nút và p khác NULL thì thêm nút (tmp) có dữ liệu cần thêm vào giữa con trỏ p và con trỏ q.	. Ngược lại, thông báo chèn không được2133.13.23.3Ví dụ: 1-> 2-> 3-> NULLk = 2, x = 10 => 1-> 10-> 2-> 3->NULLk = 1, x = 20 =>20-> 1-> 2->3-> NULLk = 5, x= 15 => Không chèn đượcBài tập: Viết chương trình thực hiện trên danh sách đơn:- Nhập / xuất danh sách ra màn hình (kết thúc bằng số không).- Thêm giá trị x vào vị trí k của danh sách.- Xuất danh sách sau khi thêm x vào vị trí k của danh sách.bài 2Các thuật toán trên DSLK1. Xóa vào đầu danh sách link2. Xóavào cuối danh sách link 3. Xóa vào vị trí bất kỳ link II. Xóa phần tử1. Xóa phần tử đầu danh sáchfirstlastĐặc tả:Vào:	. Con trỏ first, last chỉ đến nút đầu, cuối của dslk. Ra: 	. Danh sách mới sau khi đã xóa thành công nút đầu của danh sách.Hướng dẫn:	 Nếu ds rỗng thì thông báo: 	“ Danh sach rong, khong the xoa duoc”.	 Ngược lại: 	+ Gán con trỏ p bằng first; 	 + Nếu danh sách chỉ có một nút thì: *first = NULL;12	 	+ Ngược lại:	 .Tách p (nút đầu tiên) ra khỏi danh sách liên kết.	 + Huỷ con trỏ do p trỏ tới.2.12.22.3Bài tập: Viết chương trình thực hiện trên d.sách:+ Nhập/xuất một ds số thực, kết thúc việc nhập bằng số không. + Xóa phần tử đầu tiên của danh sách.+ Xuất danh sách sau khi xóa phần tử đầu tiên của danh sách. link2. Xóa phần tử cuối danh sáchppfirstĐặc tả:	 Vào:	. Con trỏ first, last chỉ đến nút đầu tiên của dslk. Ra: 	. Danh sách mới sau khi đã xóa thành công phần tử cuối của danh sách.Hướng dẫn:	 Nếu ds rỗng thì thông báo: 	“ Danh sach rong, khong the xoa duoc”.	 Ngược lại: 	 + Gán con trỏ p bằng f; + Nếu danh sách chỉ có một nút thì:	 .Gán f bằng giá trị NULL. + Ngược lại:	 . Xác định nút gần cuối cp của danh sách.	 . Tách nút cuối p ra khỏi danh sách.	 + Hủy con trỏ mà p trỏ tới.Bài tập: Viết chương trình thực hiện trên d.sách liên kết:+ Nhập /xuất danh sách.+ Xóa phần tử cuối cùng của danh sách.+ Xuất danh sách sau khi xóa phần tử cuối cùng của danh sách. link3. Xóa phần tử bất kỳpqfirstVào:	. Con trỏ first, last chỉ đến nút đầu tiên và nút cuối của dslk. 	. Vị trí của nút cần xóa (k).Ra: 	. Danh sách mới sau khi đã xóa thành công phần tử ở vị trí k của danh sách.Hướng dẫn:Nếu ds rỗng thì thông báo:	 “Danh sach rong, xoa khong duoc!”;Ngược lại:{	Nếu k bằng một thì: 	 	Xoá nút đầu của DS;Ngược lại:{ . Xác định vị trí của nút p và q trong danh sách (p ở vị trí k – 1, q ở vị trí k); . Nếu k bằng tổng số nút và q khác NULL thì tách nút q ra khỏi danh sách . Ngược lại, thông báo xóa không được } Hủy con trỏ p. }Bài tập: Viết chương trình thực hiện trên d.sách:+ Nhập /Xuất danh sách liên kết+ Xóa phần tử ở vị trí k của danh sách.+ Xuất danh sách sau khi xóa thành công phần tử ở vị trí k của danh sách.chương 3Ngăn xếp hàng đợi bài 1I. Khái niệm luiNgăn xếpII. Các thao tác trên ngăn xếp 1. Cài đặt link 2. Đẩy phần tử vào ngăn xếp link 3. Lấy phần tử ra khỏi ngăn xếp link Khái niệmNgăn xếp (stack) là một kiểu Ds tuyến tính đặc biệt mà phép bổ sung hay loại bỏ luôn thực hiện ở một đầu gọi là đỉnh.	Do vậy cơ chế thêm vào và lấy ra của ngăn xếp là Vào sau- Ra trước (LIFO) luiluibài 1I. Khái niệm luiNgăn xếpII. Các thao tác trên ngăn xếp 1. Cài đặt link 2. Đẩy phần tử vào ngăn xếp link 3. Lấy phần tử ra khỏi ngăn xếp link 1. Cài đặt- Khai báo: Dùng cấu trúc struct	typedef struct node *stack; struct	{	int value;	stack next;	}; - Khởi tạo ngăn xếp rỗngvoid init(stack * s)	{	*s=NULL;	}- Kiểm tra ngăn xếp rỗng:Ngăn xếp rỗng thì trả về giá trị 1, ngược lại trả về giá trị 0	int emty(stack s)	{	if (s= =NULL)	return 1; else	return 0;	} lui2. Đẩy phần tử vào ngăn xếpvoid push (stack *s, int x)	{	stack tmp;	tmp=new stack;	tmp->value=x;	tmp->next=*s;	*s=tmp;	} Ví Dụ	 Thêm phần tử 2 vào ngăn xếp: luiý tưởng:	+ Kiểm tra ngăn xếp: Nếu ngăn xếp rỗng. Ta không xóa được và thông báo ngăn xếp rỗng	if (empty(s)==1) 	 coutnext;	x=tmp->value;// lay gia tri o nut xoa	delete (tmp);Mô phỏngvoid pop(stack * s, int &x)	{	if(!empty(*s)) 	coutnext;	x=tmp->value;	delete (tmp);	}	}bài 2I. Khái niệm luiHàng đợiII. Các thao tác trên hàng đợi 1. Cài đặt link 2. Đẩy phần tử vào hàng đợi link 3. Lấy phần tử ra khỏi hàng đợi link Hàng đợi (Queue) là 1 kiểu danh sách tuyến tính mà phép bổ sung được thực hiện ở một đầu (gọi là lối sau - rear ), phép loại bỏ thực hiện ở một đầu khác (gọi là lối trước - front)Mô phỏngluibài 2I. Khái niệm luiHàng đợiII. Các thao tác trên hàng đợi 1. Cài đặt link 2. Đẩy phần tử vào hàng đợi link 3. Lấy phần tử ra khỏi hàng đợi link 1. Cài đặtKhai báotypedef struct Node * pointer;struct Node	{	int value;	pointer next;	}; struct Queue	{	pointer front;	pointer rear;	};Khởi tạo- Khởi tạo hàng đợi rỗngvoid Init (Queue *&q){	q->front=NULL;}Kiểm tra hàng đợi rỗng:- Hàng đợi rỗng khi front trỏ vào NULL- Hàm kiểm tra hàng đợi rỗng trả về giá trị 1 nếu hàng đợi rỗng, ngược lại trả về giá trị 0int Empty(Queue * q)	{ if(q->front==NULL ) return 1; return 0;}lui2. Đẩy phần tử vào hàng đợi- Thêm phần tử x vào hàng đợi q được thực hiện tại đầu rear.- Dùng thêm biến ok để dùng trong chương trình chính sau này:	+ Biến ok sẽ có tác dụng kiểm tra việc có thêm phần tử vào hàng đợi nữa hay không.	+Biến ok cũng dùng để kiểm tra hàng đợi còn phần tử để lấy ra không?void Add_Q (int x, Queue *& q, int & ok)	{ pointer tmp;	tmp=new Node;	tmp->value=x;	tmp->next=NULL;	if (Empty(q))	{ q->front=q->rear=tmp;	}	else 	{	(q->rear)->next=tmp;	(q->rear)	=tmp; }	ok=1; } luivoid Pop_Queue(Queue *&q, int &x,int &ok)	{ pointer tmp;	 if(Empty(q)) ok=0;	else	{	 ok=1;	 tmp=q->front;	 x=(q->front)->value;3. Lấy phần tử ra khỏi hàng đợiq->front=(q->front)->next;	 delete(tmp);	}	}CHương 4: câyI. Định nghĩaBài 1: Định nghĩa cây và các khái niệmII. Các khái niệm:1. Cấp	 link 2. Mứclink 3. Độ caolink I. Định nghĩa:Cây là 1 tập hợp T các phần tử (gọi là nút) trong đó có 1 nút đặc biệt đước gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2, .., Tn theo quan hệ phân cấp trong đó Ti cũng là cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp (i + 1). Quan hệ này người ta còn gọi là quan hệ cha- con.1. Cấp- Bậc của một nút: là số cây con của nút đó.- Cấp của một cây: là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). Cây có bặc n thì gọi là cây n - phân.II. Các khái niệm:2. Mức:Mức (gốc(T)) = 0Gọi T1, T2, .., Tn là các cây con của T0Mức (T1) = Mức (T2) = .. .= Mức (Tn) = Mức (T0) + 13. Độ cao:Bài 2: Cây nhị phânI. Khái niệm:II. Tạo cây:III. Duyệt cây:I. Khái niệm:1. Khái niệm:Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con.Ví dụ:Cây nhị phân có thể ứng dụng trong nhiều bài toán thông dụng. Ví dụ dưới đây cho ta hình ảnh của một biểu thức toán học2. Cài đặt:typedef struct TNODE TREE;	struct TNODE	{ 	Data Key;//Data là kdl ứng với t.tin lưu tại nỳt 	 TNODE *pLeft, *pRight; 	 }; II. Tạo cây:III. Duyệt cây: