Bài giảng Lập chương trình cho máy tính: Ngôn ngữ lập trình C

= 0; printf ( “Filename: “ ); gets (filename); if ((fp = fopen (filename, “r” )) == NULL ) // mở tập tin mới để đọc { printf ( “Open file error \n”); exit (1); }168Lập trình C - CNTT2. 2002 - 2005 while (( ch = getc ( fp ) ) != EOF ) // đọc cho đến hết tập tin { if (( ch >= ‘a’ && ch = ‘A’ && ch #include /* Chép từ SourceFile sang DestFile và trả về số ký tự đọc đươc 172Lập trình C - CNTT2. 2002 - 2005feof(); fscanf(), fprintf(); fflush()feof: cho biết đã đến cuối tập tin chư a(EOF). int feof (FILE *fp );fprintf:  int fprintf ( FILE *fp, const char * Format, ... );fscanf:  int fscanf ( FILE *fp, const char * Format, ...);fflush:  int fflush ( FILE * fp );Buộc ghi ra tập tin các dữ liệu có trong buffer.173Lập trình C - CNTT2. 2002 - 2005Tập tin Nhị phânTập tin nhị phân là một chuỗi các ký tự, không phân biệt ký tự in được hay không in được.Tập tin nhị phân thường dùng để lưu trữ các cấu trúc (struct) hoặc union.Khai báo: FILE * fp;Truy xuất tập tin nhị phân theo khối dữ liệu nhị phân.174Lập trình C - CNTT2. 2002 - 2005Tập tin Nhị phânCác chế độ mở tập tin nhị phân:“rb” : mở chỉ đọc“wb” : ghi (ghi đè lên tập tin cũ hoặc tạo mới nếu tập tin không có trên đĩa)“ab” : ghi nối vào cuối tập tin.“rb+” : đọc/ghi. Tập tin phải có trên đĩa.“wb+” : tạo mới tập tin cho phép đọc ghi.“ab+” : đọc, ghi vào cuối tập tin. Tạo mới tập tin nếu tập tin chưa có trên đĩa.175Lập trình C - CNTT2. 2002 - 2005Đọc ghi tập tin Nhị phânfread() : đọc size_t fread ( void *Ptr, size_t ItemSize,  size_t NumItem, FILE * fp );fread đọc NumItem khối dữ liệu, mỗi khối có kích thước ItemSize từ fp và chứa vào vùng nhớ xác định bởi Ptr.fread trả về số khối dữ liệu đọc được.Nếu có lỗi hoặc EOF thì giá trị trả về nhỏ hơn NumItemfwrite() : ghi  size_t fwrite ( const void *Ptr, size_t ItemSize, size_t NumItem, FILE * fp );fwrite ghi khối (NumItem x ItemSize) xác dịnh bởi Ptr ra fp.176Lập trình C - CNTT2. 2002 - 2005Chép 3 mục từ tập tin filename vào vùng nhớ trỏ bởi ptrptrfpfilename177Lập trình C - CNTT2. 2002 - 2005Con trỏ FILEMột tập tin sau khi mở được quản lý thông qua một con trỏ FILE.Khi mở tập tin (wb, rb), con trỏ FILE chỉ đến đầu tập tin.Khi mở tập tin (ab), con trỏ FILE chỉ đến cuối tập tin.Con trỏ FILE chỉ đến từng byte trong tập tin nhị phân.Sau mỗi lần đọc tập tin, con trỏ FILE sẽ di chuyển đi một số byte bằng kích thước (byte) của khối dữ liệu đọc được.178Lập trình C - CNTT2. 2002 - 2005fseek(), Các hằng dùng trong di chuyển con trỏ FILE#define SEEK_SET 0#define SEEK_CUR 1#define SEEK_END 2int fseek( FILE *fp, long int offset, int whence );fseek di chuyển con trỏ fp đến vị trí offset theo mốc whence offset: khoảng cách (byte) cần di chuyển tính từ vị trí hiện tại. (offset > 0: đi về phía cuối tập tin, offset 0 nếu di chuyển có lỗi179Lập trình C - CNTT2. 2002 - 2005ftell() và rewind()rewind đặt lại vị trí con trỏ về đầu tập tin. void rewind ( FILE * fp );tương đương với fseek ( fp, 0L, SEEK_SET);ftell trả về vị trí offset hiện tại của con trỏ long int ftell ( FILE * fp );Nếu có lỗi, ftell trả về -1L180Lập trình C - CNTT2. 2002 - 2005Ví dụ: xác định kích thước tập tin....// khai báo biến cẩn thậnif ( fp = fopen ( FileName, “rb” ) ) == NULL ) fprintf( stderr, “Cannot open %s\n”, FileName );else { fseek( fp, 0, SEEK_END ); FileSize = ftell( fp ); printf( “File size : %d bytes\n “, FileSize ); fclose( fp ); }181Lập trình C - CNTT2. 2002 - 2005Vị trí con trỏ: fgetpos() và fsetpos()với các tập tin có kích thước cực lớn fseek và ftell sẽ bị giới hạn bời kích thước của offset.Dùng  int fgetpos ( FILE *fp, fpos_t *position); int fsetpos ( FILE *fp, const fpos_t *position); 182Lập trình C - CNTT2. 2002 - 2005Xóa và đổi tên tập tin Thực hiện xoá  int remove(const char *filename);đổi tên tập tin  int rename(const char *oldname, const char *newname);183Lập trình C - CNTT2. 2002 - 2005Chú ý khi làm việc với tập tinKhi mở tập tin filename, tập tin này phải nằm cùng thư mục của chương trình hoặcphải cung cấp đầy đủ đường dẫn đến tập tinvd: C:\baitap\taptin.datviết như thế nào?  fp = fopen( “C:\baitap\taptin.dat”, “rb” );SAI RỒIvì có ký tự đặc biệt ‘\’ nên viết đúng sẽ là: fp = fopen( “C:\\baitap\\taptin.dat”, “rb” );184Lập trình C - CNTT2. 2002 - 2005Tham số dòng lệnh chương trìnhKhi gọi chạy một chương trình, chúng ta có thể cung cấp các tham số tại dòng lệnh gọi chương trình.ví dụ: dir A:\*.c /w“copy”, “A:\*.c” và “/w” là hai tham số điều khiển chương trình.command-line arguments.Các tham số dòng lệnh được tham chiếu qua hai đối số khai báo trong hàm main. main ( int argc, char * argv[ ] ) { ... }argc: argument countargv: argument vector185Lập trình C - CNTT2. 2002 - 2005Tham số dòng lệnh – ví dụ... // addint.c  addint.exevoid main (int argc, char * argv [ ]) { int res = 0; printf (“ Program %s\n “, argv[0]); for ( int i = 1; i addint 3 –2 1 5 6 -2 112186Lập trình C - CNTT2. 2002 - 2005Lập chương trình cho máy tínhCẤU TRÚC DỮ LIỆU – STACK và QUEUELê Hà ThanhHọc kỳ 2, 2004-2005Cấu trúc dữ liệuStackQueueCác phép toán trên stack và queueBiểu diễn stack và queue bằng mảng188Lập trình C - CNTT2. 2002 - 2005StackStack là cấu trúc dữ liệu trong đó các truy xuất đến phần tử trong stack chỉ thực hiện được với phần tử được chèn vào mới nhấtLIFO: Last In First Out - vào sau ra trước.Các thao tác trong stack:push: chèn phần tử mới vào stackpop: lấy phần tử đầu stack ra khỏi stacktop: kiểm tra phần tử đầu stack189Lập trình C - CNTT2. 2002 - 2005StackPushPopTop190Lập trình C - CNTT2. 2002 - 2005Khai báo cấu trúc dữ liệu cho stackstruct 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;191Lập trình C - CNTT2. 2002 - 2005Kiểm tra Stack rỗng: StIsEmpty()// ------------ Kiểm tra Stack rỗng ---------------int StIsEmpty (const Stack S ) { StInsistGood ( S ); return (STopOfStack == -1); }192Lập trình C - CNTT2. 2002 - 2005Kiể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 ); } }193Lập trình C - CNTT2. 2002 - 2005Thê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; }194Lập trình C - CNTT2. 2002 - 2005Stack – 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 --; }195Lập trình C - CNTT2. 2002 - 2005Stack –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 ]; }196Lập trình C - CNTT2. 2002 - 2005Stack – 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 ); }197Lập trình C - CNTT2. 2002 - 2005Hàng đợi - QueueQueue (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ướcCá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.198Lập trình C - CNTT2. 2002 - 2005QueueEnqueueFrontDequeue199Lập trình C - CNTT2. 2002 - 2005Khai báo kiểu Queuetypedef 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ử */200Lập trình C - CNTT2. 2002 - 2005Kiểm tra Queue rỗngint 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; }201Lập trình C - CNTT2. 2002 - 2005Queue - Khởi tạoQueue 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; }202Lập trình C - CNTT2. 2002 - 2005Lấ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--; } }203Lập trình C - CNTT2. 2002 - 2005Đ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; } }204Lập trình C - CNTT2. 2002 - 2005Đưa phần tử mới vào Queuevoid 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 ++; }205Lập trình C - CNTT2. 2002 - 2005Lập chương trình cho máy tínhCẤU TRÚC DỮ LIỆU – DANH SÁCH LIÊN KẾT (LINKED LISTS)Lê Hà ThanhHọc kỳ 2, 2004-2005Khái niệmKhá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).207Lập trình C - CNTT2. 2002 - 2005Biểu diễn trong bộ nhớ3124FirstFirstNil208Lập trình C - CNTT2. 2002 - 2005Liên Kết các nút trong danh sáchCá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.209Lập trình C - CNTT2. 2002 - 2005Các đặc tínhCấ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.210Lập trình C - CNTT2. 2002 - 2005Hạn chế của Danh Sách Liên KếtVì 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.211Lập trình C - CNTT2. 2002 - 2005Khai báo và Khởi tạostruct 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;212Lập trình C - CNTT2. 2002 - 2005Chú ý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; }213Lập trình C - CNTT2. 2002 - 2005Các Phép Toán Trên DSLK -Tạo Danh SáchInitialze: 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);  }214Lập trình C - CNTT2. 2002 - 2005Tạo danh sách – Thêm vào đầu DSInsert_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; }215Lập trình C - CNTT2. 2002 - 2005Tạo danh sách – Thêm vào cuối DSInsert_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; } }216Lập trình C - CNTT2. 2002 - 2005Cập Nhật Danh SáchFree_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); }217Lập trình C - CNTT2. 2002 - 2005Xóa phần tử đầu DSDelete_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); } }218Lập trình C - CNTT2. 2002 - 2005Xóa phần tử cuối DSDelete_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); } }219Lập trình C - CNTT2. 2002 - 2005Xóa toàn bộ Danh SáchDelete_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); } }220Lập trình C - CNTT2. 2002 - 2005Duyệt Danh SáchTraverse(): 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; } }221Lập trình C - CNTT2. 2002 - 2005Tìm Kiếm trong Danh SáchSearch(): 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); }222Lập trình C - CNTT2. 2002 - 2005Sắp Xếp trong Danh SáchSelection_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) 223Lập trình C - CNTT2. 2002 - 2005Sắp Xếp trong Danh Sáchvoid 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; } }224Lập trình C - CNTT2. 2002 - 2005