Bài giảng Lập chương trình cho máy tính

áo cấu trúc dữ liệu cho stack struct StackPtr { 	int *Array;	// mảng các phần tử 	int TopOfStack; // vị trí phần tử đỉnh stack 	int MaxSize; // số phần tử tối đa trong stack } *Stack; static const StInitSize = 5; Kiểm tra Stack rỗng: StIsEmpty() // ------------ Kiểm tra Stack rỗng --------------- int StIsEmpty (const Stack S ) { StInsistGood ( S ); return (STopOfStack == -1); } Kiểm tra Stack tồn tại StInsistGood() // ------------------- Kiểm tra Stack có tồn tại ------------------- void StInsistGood ( const Stack S ) { if ( S == NULL ) 	{ printf( “Stack routin recived bad stack \n “ ); 	exit ( 1 ); 	} } Thêm phần tử vào đầu Stack – push() void push ( int newEle, Stack S) { StInsistGood ( S ); // kiểm tra stack hợp lệ if( ++STopOfStack == SMaxSize) { // nếu stack hiện thời đã đầy thì tăng gấp đôi kích thước. SMaxSize *= 2; SArray = realloc( SArray, sizeof(StEtype) * SMaxSize); if (SArray == NULL) { printf( “can not extend the stack\n” ); exit (-1); } SArray[ STopOfStack ] = newEle; } Stack – pop() // -------------- Pop: lấy một phần tử ra khỏi stack ------------- void pop( Stack S ) { if ( StIsEmpty( S ) ) 	printf( “ Error: can not Pop an empty stack\n” ); else 	STopOfStack --; } Stack –top() // ---------- Top: lấy giá trị của phần tử trên đỉnh stack --------- int top ( const Stack S ) { if ( StIsEmpty ( S ) ) 	printf ( “Error: can not Top an empty stack \n” ); else 	return SArray [ STopOfStack ]; } Stack – StRecycle() /* Sau khi sử dụng stack, trước khi dừng chương trình, gọi StRecycle để giải phóng bộ nhớ. */ int StRecycle ( Stack S ) { StInsistGood ( S ); free ( SArray ); free ( S ); } Hàng đợi - Queue Queue (hàng đợi) là cấu trúc dữ liệu trong đó các truy xuất đến phần tử trong queue chỉ thực hiện được với phần tử chèn vào trước nhất. FIFO: First In First Out – Vào trước ra trước Các thao tác trong Queue: Enqueue: chèn phần tử vào cuối hàng đợi. Dequeue: lấy phần tử ra khỏi hàng đợi ờ đầu hàng đợi và lấy thông tin của phần tử này. Front: kiểm tra phần tử đầu hàng đợi. Queue Khai báo kiểu Queue typedef struct QueueStr { int * Array; /* mảng các phần tử trong queue */ int Front; /* chỉ số của phần tử đầu queue */ int Back; /* chỉ số của phần tử cuối queue */ int Size; /* số phần tử hiện tại */ int MaxSize; /* Kích thước tối đa của Queue */ } * Queue; static const QuInitSize = 5; /* đầu tiên tạo queue có 5 phần tử */ Kiểm tra Queue rỗng int QuIsEmpty ( const Queue Q ) { QuInsisGood ( Q ); return (QSize == 0); } // ---- KIểm tra xem có cần tăng kích thước Queue ---- Int Increment ( int QParam, int Qsize) { if ( ++QParam == Qsize) 	return 0; else 	return QParam; } Queue - Khởi tạo Queue QuMakeEmpty ( Queue Q ) { if ( Q == NULL ) { if ( !( Q = malloc (sizeof( struct QueuStr)))) return NULL; Q->Array = malloc (sizeof( QuEType ) * QuInitSize ); if ( Q->Array == NULL) return NULL; Q->MaxSize = QuInitSize; } Q->Size = 0; Q->Front = 0; Q->Back = -1; return Q; } Lấy phần tử ra khỏi Queue // ----------- Dequeue ---------------- void Dequeue (QuEType * X, Queue Q ) { if ( QuIsEmpty (Q)) printf (“Error: cannot Dequeue an empty queue\n”); else { *X = Q->Array [Q->Front ]; Q->Front = Increment (Q->Front, Q->MaxSize); Q->Size--; } } Điều chỉnh Queue /* khi kích thước Queue được tăng lên gấp đôi, sự sắp xếp mảng có thể bị sai. Hàm FixWraparound giúp điều chỉnh lại và hạn chế số lần di chuyển các phần tử trong mảng */ void FixWraparound (Queue Q) { const int OrigSz = Q->MaxSize / 2; if (Q->Front Array[OrigSz], &Q->Array[0],	&Q->Front * sizeof(QuEType)); Q->Back += QrigSz; } else { memcpy (&Q->Array[OrigSz + Q->Front], &Q->Array[Q->Front],	(OrigSz – Q->Front) * sizeof(QuEType)); Q->Front += OrigSz; } } Đưa phần tử mới vào Queue void Enqueue (QuEType X, Queue Q) { QuInsistGood (Q); if (Q->Size == Q->MaxSize ) { Q->MaxSize *= 2; Q->Array = realloc (Q->Array, sizeof (QuEType) * Q->MaxSize); if (Q->Array == NULL) { printf ( “Cannot extend the queue\n” ); exit (-1); } if (Q->Front != 0) FixWraparound (Q); } Q->Back = Increment (Q->Back, Q->MaxSize); Q->Array[Q->Back] = X; Q->Size ++; } Lập chương trình cho máy tính CẤU TRÚC DỮ LIỆU – DANH SÁCH LIÊN KẾT (LINKED LISTS) Lê Hà Thanh Học kỳ 2, 2004-2005 Khái niệm Khái niệm: (xem giáo trình Bài giảng kỹ thuật lập trình ...) Cấu trúc danh sách liên kết là cấu trúc động, việc cấp phát nút và giải phóng nút trên danh sách xảy ra khi chương trình đang chạy. Ta thường cấp phát nút cho danh sách liên kết bằng biến động. Các phần tử sẽ được cấp phát vùng nhớ trong quá trình thực thi chương trình, do đó chúng có thể nằm rải rác ở nhiều nơi khác nhau trong bộ nhớ (phân bố không liên tục). Biểu diễn trong bộ nhớ First First Nil Liên Kết các nút trong danh sách Các phần tử trong danh sách liên kết kết nối với nhau theo dãy, trong đó: First là con trỏ chỉ đến phần tử đầu tiên của danh sách liên kết. Phần tử cuối của danh sách liên kết với vùng liên kết có nội dung NULL. Mỗi nút của danh sách có trường info chứa nội dung của nút và trường next là con trỏ chỉ đến nút kế tiếp trong danh sách. Các đặc tính Cấu trúc DSLK là cấu trúc động, các nút được cấp phát hoặc giải phóng khi chương trình đang chạy. DSLK rất thích hợp khi thực hiện các phép toán trên danh sách thường bị biến động. Trong trường hợp xoá hay thêm phần tử trong DSLK thì ta không dời các phần tử đi như trong mảng mà chỉ việc hiệu chỉnh lại trường next tại các nút đang thao tác. Thời gian thực hiện các phép toán thêm vào và loại bỏ không phụ thuộc và số phần tử của DSLK. Hạn chế của Danh Sách Liên Kết Vì mỗi nút của DSLK phải chứa thêm trường next nên DSLK phải tốn thêm bộ nhớ. Tìm kiếm trên DSLK không nhanh vì ta chỉ được truy xuất tuần tự từ đầu danh sách. Khai báo và Khởi tạo struct node { int info; struct node * next; }; typedef struct node *NODEPTR; Khai báo biến First quản lý DSLK:		NODEPTR First; Khởi tạo DSLK:	First = NULL; Chú ý Thành phần chứa nội dung có thể gồm nhiều vùng với các kiểu dữ liệu khác nhau. Thành phần liên kết cũng có thể nhiều hơn 1 nếu là danh sách đa liên kết hoặc danh sách liên kết kép. First là con trỏ trỏ đến phần tử đầu tiên của danh sách liên kết, nó có thể là kiểu con trỏ, và cũng có thể là một struct có hai thành phần: First – con trỏ trỏ đến phần tử đầu tiên của DSLK, và Last – con trỏ trỏ đến phần tử cuối cùng của DSLK.struct Linked_List {	NODEPTR First; 	NODEPTR Last; } Các Phép Toán Trên DSLK -Tạo Danh Sách Initialze: Khởi động một DSLK. Ban đầu DSLK chưa có phần tử.void Initialize (NODEPTR *First) {	* First = NULL; } New_Node(): cấp phát một nút cho DSLK. Hàm New_Node trả về địa chỉ của nút vừa được cấp phát.NODEPTR New_Node () {	NODEPTR p;	p = (NODEPTR) malloc (sizeof (struct node));	return (p);  } Tạo danh sách – Thêm vào đầu DS Insert_First(): thêm một nút có nội dung x vào đầu DSLK. void Insert_First (NODEPTR *First, int x) { 	NODEPTR p; 	p = New_Node (); 	p->info = x; 	p->next = *First; 	*First = p; } Tạo danh sách – Thêm vào cuối DS Insert_After(): thêm một nút có nội dung x vào sau nút có địa chỉ p trong DSLK First. void Insert_After (NODEPTR p, int x) { 	NODEPTR q; 	if (p == NULL) printf (“Cannot insert new node!\n”); 	else { 	 q = New_Node (); 	 q->info = x; q->next = p->next; 	 p->next = q; 	 } } Cập Nhật Danh Sách Free_Node(): hủy một nút đã cấp phát và trả vùng nhớ về cho memory heap.void Free_Node (NODEPTR p) {	free (p); } Empty(): Kiểm tra danh sách rỗng.int Empty (NODEPTR *First) {	return (*First == NULL ? TRUE : FALSE); } Xóa phần tử đầu DS Delete_First(): Xoá phần tử đầu danh sách.  void Delete_First (NODEPTR *First) { 	NODEPTR p; 	if (Empty (First)) 	 printf (“List is empty. No deletion performed!\n”); 	else { 	 p = *First; 	 *First = p->next; 	 Free_Node (p); 	 } } Xóa phần tử cuối DS Delete_After(): Xoá phần tử đứng sau nút có địa chỉ p.  void Delete_After (NODEPTR p) { 	NODEPTR q; 	if (p == NULL || p->next == NULL) 	 printf (“Cannot delete!\n”); 	else { 	 q = p->next; // q is the node that will be deleted 	 p->next = q->next; 	 Free_Node (q); 	 } } Xóa toàn bộ Danh Sách Delete_All(): Xoá toàn bộ danh sách.Có thể gán First = NULL để xóa toàn bộ danh sách nhưng phần vùng nhớ đã cấp cho các phần tử trong DS không được giải phóng. Do đó chúng ta dùng giải thuật sau.  void Delete_All (NODEPTR *First) { 	NODEPTR p; 	while (*First != NULL) // reach to end ? 	 { 	 p = *First; 	 *First = (*First)->next; // *First = p->next; 	 Free_Node (p); 	 } } Duyệt Danh Sách Traverse(): Duyệt qua toàn bộ danh sách (để liệt kê dữ liệu hoặc đếm số nút trong DS,...) void Traverse (NODEPTR *First) {	NODEPTR p; 	int count = 0; 	p = *First; 	if (p == NULL) 	 printf (“List is empty!\n”); 	while (p != NULL) { // reach to end ? 	 printf (“\n %5d%8d”, count++, p->info); 	 p = p->next; 	 } } Tìm Kiếm trong Danh Sách Search(): Tìm nút đầu tiên trong DS có info bằng với x. Do đây là DSLK nên ta phải tìm từ đầu DS.Nếu tìm thấy nút có (info == x) thì trả về địa chỉ của nút, nếu không, trả về NULL.  NODEPTR Search (NODEPTR *First, int x) {	NODEPTR p; 	p = *First; 	// not reach to end and not found 	while (p != NULL && p->info != x) 	 p = p->next; 	return (p); } Sắp Xếp trong Danh Sách Selection_Sort(): sắp xếp DSLK theo thứ tự info tăng dần.   Thuật toán: So sánh tất cả các phần tử của DS để chọn ra một phần tử nhỏ nhất đưa về đầu DS; sau đó, tiếp tục chọn phần tử nhỏ nhất trong các phần tử còn lại để đưa về phần tử thứ hai trong DS. Quá trình lặp lại cho đến khi chọn được phần tử nhỏ nhất thứ (n-1)  Sắp Xếp trong Danh Sách void Selection_Sort (NODEPTR *First) {	NODEPTR p, q, pmin; 	int min; 	for (p = *First; p->next != NULL; p = p->next) { 	 min = p->info; 	 pmin = p; 	 for (q = p->next; q != NULL; q = q->next) 	 if (min > q->info) { 	 min = q->info; 	 pmin = q; 	 } 	 // hoan doi truong info cua hai nut p va pmin 	 pmin->info = p->info; 	 p->info = min; 	 } }