Bài giảng Cấu trúc dữ liệu và giải thuật: Xây dựng tập tin có cấu trúc (Structured files) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Xây dựng tập tin có cấu trúc (Structured files) - Nguyễn Tri Tuấn

1. Data Structure & Algorithm Xây dựng tập tin cócấu trúc (Structured files) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Structured files Giới thiệu Tập tin văn bản thô (plain text) Tập tin nhị phân (binary) Tập tin hình ảnh PCX Tập tin CSDL DBF Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
2. Giới thiệu ªCác thuật ngữ thường dùng: File structure File format File header Website tham khảo: Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu (tt) ªFile làmột cách thức lưu trữ dữ liệu phổ biến trên bộ nhớ phụ ªDữ liệu lưu trữ trên file cócấu trúc thích hợp à hiệu suất truy xuất cao Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
3. Giới thiệu (tt) ªDữ liệu lưu trữ trên file thường theo 2 dạng phổ biến: Dữ liệu text thô (plain text) Dữ liệu nhị phân (binary) File dữ liệu plain textFile dữ liệu nhị phân Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Structured files Giới thiệu Tập tin văn bản thô (plain text) Tập tin nhị phân (binary) Tập tin hình ảnh PCX Tập tin CSDL DBF Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
4. Plain text ªPlain text phi cấu trúc: Không phân hoạch theo ý nghĩa, chức năng Rất khóxửlý Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Plain text, cócấu trúc [SQL Server (32 bit)] Driver=H:\WINNT\System32\sqlsrv32.dll Setup=H:\WINNT\System32\sqlsrv32.dll 32Bit=1 Tập tin định cấu hình Tập tin định driver WinCommander kết nối DB (ODBC.INI) (WINCMD.INI) [left] path=I:\DCIM\101MSDCF\ ShowAllDetails=1 show=1 sortorder=3 negative Sortorder=1 [right] path=F:\Nguyen Tri Tuan\ Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
5. Plain text, cócấu trúc (tt) ªĐịnh nghĩa: Dữ liệu được chuyển thành dạng chuỗi (string) và lưu lên file theo một qui tắc nhất định ªCác tính chất: Dễ truy xuất vàxửlý Dễ thay đổi nội dung khi cần Độ bảo mật kém Tốc độ truy xuất chậm Kích thước lớn VD. Lưu số nguyên 12345 ở dạng binary (2 bytes) vàdạng chuỗi (5 bytes) Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Plain text, cócấu trúc (tt) ªCác dạng thường gặp: File cấu hình phần mềm (*.INI, *.CFG) File *.HTML, *.XML Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
6. Plain text, cócấu trúc (tt) // Minh họa đoạn code tạo file WINCMD.INI FILE *f; char path[MAX_LEN]; intshowAllDetails, show; intsortOrder, negativeSortOrder; f = fopen(“wincmd.ini”, “wt”); fprintf(f, “[left]\n”); fprintf(f, “path=%s\n”, path); fprintf(f, “ShowAllDetails=%i\n”, showAllDetails); fprintf(f, “show=%i\n”, show); fprintf(f, “sortorder=%i\n”, sortOrder); fprintf(f, “negative Sortorder=%i\n”, negativeSortOrder); fclose(f); Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Structured files Giới thiệu Tập tin văn bản thô (plain text) Tập tin nhị phân (binary) Tập tin hình ảnh PCX Tập tin CSDL DBF Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
7. Tập tin nhị phân ªĐịnh nghĩa: Dữ liệu được lưu trên file giống như cách mànó thường được lưu trong bộ nhớ chính Dữ liệu thường lưu dạng record typedef struct { unsigned int ID; ID 4 bytes charname[30]; floatavgPoint; } STUDENT; name 30 bytes // strucsize (in memory) avgPoint 4 bytes // = 38 bytes Memory block of STUDENT Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Tập tin nhị phân (tt) // Minh họa đoạn code đọc dữ liệu file STUDENTS.DAT FILE *f; STUDENT oneStudent; // open file to read f = fopen(“students.dat”, “rb”); while (fread(&oneStudent, sizeof(STUDENT), 1, f)) { // xử lý record oneStudent } fclose(f); Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
8. Tập tin nhị phân (tt) #define MAX_LEN 128 path 128 bytes typedef struct { char path[MAX_LEN]; 4 bytes int showAllDetails; showAllDetails int show; int sortOrder; show 4 bytes int negativeSortOrder; } WINCMD_CFG; sortOrder 4 bytes // strucsize (in memory) negativeSortOrder 4 bytes // = 144 bytes Memory block of WINCMD_CFG Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Tập tin nhị phân (tt) // Minh họa đoạn code tạo file WINCMD.CFG FILE *f; WINCMD_CFG leftPanelCfg, rightPanelCfg; // tạo file f = fopen(“wincmd.cfg”, “wb”); // tạo 1st record fwrite(&leftPanelCfg, sizeof(WINCMD_CFG), 1, f); // tạo 2nd record fwrite(&rightPanelCfg, sizeof(WINCMD_CFG), 1, f); fclose(f); Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
9. Tập tin nhị phân (tt) ªCác tính chất: Dễ truy xuất vàxửlý Tốc độ truy xuất nhanh Tính bảo mật cao hơn ªChiếm phần lớn số file đang được dùng trên máy tính Các file dữ liệu riêng, cócấu trúc tự tổ chức *.DOC, *.XLS, *.PDF, *.PPT *.JPG, *.PCX, *.BMP, *.TIF *.MP3, *.WAV, *.AVI, Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Tập tin nhị phân (tt) ªHai dạng file nhị phân thường dùng: File cócấu trúc riêng, tự tổ chức File cócấu trúc chuẩn Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
10. Tập tin nhị phân (tt) ªFile cócấu trúc riêng, tự tổ chức: Thường được thiết kế chuyên biệt cho ứng dụng Cấu trúc file được qui ước ngầm định trong ứng dụng Cấu tạo không phức tạp VD. File students.dat vàfile wincmd.cfg Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 Tập tin nhị phân (tt) ªFile cócấu trúc chuẩn: Được công nhận rộng rãi Cấu tạo thường phức tạp Thường được tổ chức dạng file cóheader VD. *.DOC, *.XLS, *.DBF, *.PCX, Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
11. Tập tin nhị phân (tt) ªFile cócấu trúc chuẩn: (tt) Header: làphần dữ liệu (thường lưu ở đầu file) để cung cấp thông tin về cấu trúc chi tiết của file đó Header: Header: kích thước ảnh (W, H); Số field; tên các số màu; bảng màu; độ field; kiểu dữ liệu phân giải; các field; số record; ngày cập nhật; Dữ liệu điểm ảnh Dữ liệu các record File ảnh (bitmap) File CSDL (table) Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Tập tin nhị phân (tt) ªHeader: (tt) Có2 dạng header phổ biến: Header tĩnh: Kích thước của header không thay đổi trong mọi trường hợp Dùng cho các file cócấu tạo không phức tạp; vàcác thành phần cấu tạo không thay đổi VD. File ảnh bitmap PCX: header 128 bytes Header động: Kích thước header thay đổi tùy file Dùng cho các file cóthành phần cấu tạo biến thiên VD. Bảng (table) cósố field thay đổi từ 1 –255 fields Ảnh bitmap cóbảng màu thay đổi từ 2 màu –16 triệu màu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
12. Structured files Giới thiệu Tập tin văn bản thô (plain text) Tập tin nhị phân (binary) Tập tin hình ảnh PCX Tập tin CSDL DBF Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 Tập tin hình ảnh *.PCX ªLịch sử hình thành, công dụng ªẢnh bitmap ªCấu trúc header ªLưu trữ dữ liệu điểm ảnh Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM24 12
13. Tập tin hình ảnh *.PCX (tt) ª Lịch sử hình thành, công dụng: Được xây dựng ~1985, bởi công ty ZSoft Corporation Làmột trong các chuẩn tập tin dùng để lưu ảnh bitmap đầu tiên; được dùng trong phần mềm PC PaintBrush Cho phép lưu các ảnh bitmap đơn; dạng 2 màu, 16 màu, 256 màu, 16 triệu màu Được hỗ trợ trong nhiều phần mềm xử lý ảnh Làdạng file nhị phân cócấu trúc header tĩnh Mã Version 0 2.5 (dùng cho PC Paintbrush –DOS) 2 2.8 cóbảng màu (palette) 3 2.8 không cóbảng màu 4 Dùng cho PC Paintbrush Windows 5 3.0 (dùng cho PC Paintbrush, Publisher’s Paintbrush). Thể hiện được ảnh 24 bits màu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM25 Tập tin hình ảnh *.PCX (tt) ªẢnh bitmap: Làmột ma trận các điểm ảnh (pixel) Kích thước W cột, H dòng (W*H pixels) Cómột số lượng hữu hạn màu để thể hiện các pixel Loại ảnh trắng đen (2 màu) Loại ảnh 16 màu Loại ảnh 256 màu Loại ảnh 16 triệu màu Các màu được lưu thành bảng màu (Palette) Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM26 13
14. Tập tin hình ảnh *.PCX (tt) ªẢnh bitmap: (tt) Mỗi màu được tạo thành từ 3 thành phần cơ bản (Red, Green, Blue), mỗi thành phần biểu diễn bằng 1 byte à cần 3 bytes/màu Mỗi pixel được biểu diễn bằng 1 số lượng bit tùy theo số lượng màu 2 màu à 1 bit/pixel 16 màu à 4 bits/pixel 256 màu à 8 bits/pixel 16 triệu màu à 24 bits/pixel Các thông số khác: Độ phân giải (DPI) Hình thức nén dữ liệu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM27 Tập tin hình ảnh *.PCX (tt) ªCấu trúc header: Header: Header: kích thước ảnh (W, H); kích thước ảnh (W, H); số màu; bảng màu; độ số màu; bảng màu; độ phân giải; phân giải; (Header size = 128 (Header size = 128 bytes) bytes) Dữ liệu điểm ảnh Dữ liệu điểm ảnh Header mở rộng (768 File *.PCX: 2, 16 màu hay 16 bytes) = bảng màu 256 triệu màu màu File *.PCX: 256 màu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM28 14
15. Tập tin hình ảnh *.PCX (tt) ª Cấu trúc header: (tt) OffsetChiều dàiThành phầnÝ nghĩa 01ManufacturerHằng số để nhận dạng loại file PCX (= 10: ZSoft .PCX) 11VersionVersion 21EncodingCờcho biết hình thức mã hóa dữ liệu pixel (1: nén PCX RLE; 0: không nén) 31BitsPerPixelSốbit dữ liệu dùng cho 1 pixel (trên 1 scan line). Giátrị 1, 4, 8 42XminTọa độ X của góc trên trái 62YminTọa độ Y của góc trên trái 82XmaxTọa độ X của góc dưới phải 102YmaxTọa độ Y của góc dưới phải Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM29 Tập tin hình ảnh *.PCX (tt) ª Cấu trúc header: (tt) OffsetChiều dàiThành phầnÝ nghĩa 122HDPI Độ phân giải ngang (DPI) 142VDPI Độ phân giải dọc (DPI) 1648ColorPaletteBảng màu của ảnh 2/16 màu (2/16 entries) 641ReservedDành riêng (= 0) 651ColorPlaneGiátrị Color Plane 662BytesPerLineSốbyte thực sự được lưu cho 1 scan line. Luôn làm tròn word 682PaletteInfoThông tin về Palette (1: Color/B&W; 2: Grayscale) 7058FilterKhông dùng (= 0) Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM30 15
16. Tập tin hình ảnh *.PCX (tt) ª Cấu trúc header: (tt) W = Xmax –Xmin + 1 (cột) H = Ymax –Ymin + 1 (dòng) Số màu: BitPerPixel Color Plane Số màu 1 1 B/W 1 4 16 màu 4 1 16 màu 8 1 256 màu 8 3 24 bits màu (16 tr màu) Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM31 Tập tin hình ảnh *.PCX (tt) // Cấu trúc mô tả 1 thành phần màu (RGB) typedef struct RGB_ENTRY { unsigned char R; unsigned char G; unsigned char B; }; Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM32 16
17. Tập tin hình ảnh *.PCX (tt) // Cấu trúc dữ liệu để lưu PCX Header typedef struct PCX_HEADER { unsigned charmanufacturer; unsigned charversion; unsigned charencoding; unsigned charbitsPerPixel; unsigned intxMin, yMin, xMax, yMax; unsigned inthDPI; unsigned intvDPI; RGB_ENTRYcolorPalette[16]; unsigned charreserved; unsigned charcolorPlane; unsigned intbytesPerLine; unsigned intpaletteInfo; charfilter[58]; }; Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM33 Tập tin hình ảnh *.PCX (tt) // Chương trinh minh họa đọc *.PCX header FILE *f; PCX_HEADER pcxHeader; RGB_ENTRY_256ExtendColorPalette[256]; f = fopen(“xyz.pcx”, “rb”); fread(&pcxHeader, sizeof(PCX_HEADER), 1, f); // Nếu file 256 màu à đọc palette mở rộng ở cuối file if (pcxHeader.bitsPerPixel==8 && pcxHeader.colorPlane==1){ int n = 256*sizeof(RGB_ENTRY); fseek(f, -n, SEEK_END); fread(_256ExtendColorPalette, sizeof(RGB_ENTRY), 256, f); } Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM34 17
18. Tập tin hình ảnh *.PCX (tt) ªLưu trữ dữ liệu điểm ảnh: Pixel trên ảnh Dữ liệu được lưu trữ 0 0 1 0 1 0 Ảnh B/W (1 bit/pixel) –Không cần sử dụng Palette Black à bit = 0 White à bit = 1 8 pixels à 1 byte dữ liệu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM35 Tập tin hình ảnh *.PCX (tt) ªLưu trữ dữ liệu điểm ảnh: (tt) 0 Pixel trên ảnh 1 2 . . Dữ liệu được lưu trữ . 0 0 0 1 1 0 0 1 9 15 Ảnh 16 màu (4 bits/pixel) –Palette có16 phần tử 2 pixels à 1 byte dữ liệu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM36 18
19. Tập tin hình ảnh *.PCX (tt) ªLưu trữ dữ liệu điểm ảnh: (tt) 0 1 Pixel trên ảnh 2 . . Dữ liệu được lưu trữ . 41 0 0 1 0 1 0 0 1 255 Ảnh 256 màu (8 bits/pixel) –Palette có256 phần tử 1 pixel à 1 byte dữ liệu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM37 Tập tin hình ảnh *.PCX (tt) ªLưu trữ dữ liệu điểm ảnh: (tt) Pixel trên ảnh Dữ liệu được lưu trữ 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 RGB Ảnh 16 triệu màu (24 bits/pixel) –Không cần dùng Palette 1 pixel à 3 bytes dữ liệu Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM38 19
20. Thank you for your attention Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM39 QQ && AA Sprint 2006Data Structure & Algorithm -Structured files -Nguyen Tri Tuan, DH.KHTN Tp.HCM40 20