<< Chapter < Page
  Cấu trúc dữ liệu     Page 15 / 15
Chapter >> Page >

Ví dụ trong Pascal thủ tục RESET mở một tập tin để READ và thủ tục REWRITE mở một tập tin để WRITE.

2/ READ

Phép toán READ chuyển nội dung của phần tử hiện hành của tập tin (được chỉ định bởi con trỏ tập tin) vào biến được chỉ định trong chương trình.

3/ WRITE

Phép toán WRITE tạo ra một phần tử mới của tập tin tại vị trí hiện hành và chuyển nội dung của biến chương trình được chỉ định vào phần tử mới.

4/ Kiểm tra cuối tập tin

Là phép toán xác định xem vị trí của con trỏ tập tin có nằm sau phần tử cuối cùng của tập tin hay không.

5/ CLOSE

Khi việc xử lý tập tin đã hoàn tất thì nó phải được đóng lại. Thông thường tập tin được đóng một cách tự động khi chương trình kết thúc. Tuy nhiên nếu muốn thay đổi mode truy nhập tập tin từ WRITE sang READ hoặc ngược lại thì tập tin phải được đóng một cách tường minh bằng phép toán CLOSE và sau đó mở lại cho mode mới.

Phép cài đặt

Trong hầu hết các hệ máy tính, thì hệ điều hành chịu trách nhiệm chủ yếu về việc cài đặt tập tin bởi vì tập tin được tạo ra và sử dụng bởi nhiều ngôn ngữ lập trình khác nhau. Ngôn ngữ lập trình chỉ làm một việc là cung cấp những cấu trúc dữ liệu cần thiết để giao diện với hệ điều hành.

Các phép toán trên tập tin được cài đặt một cách chủ yếu bằng cách gọi các phép toán của hệ điều hành.

Khi chương trình mở một tập tin, thì bộ nhớ lưu trữ một bảng thông tin về tập tin (FIT) (File Information Table) và một bộ nhớ đệm (buffer) được cung cấp. Phép toán OPEN của hệ diều hành sẽ lưu trữ thông tin về vị trí và các đặc tính của tập tin vào trong bảng FIT.

Nếu tập tin được mở để ghi thì khi phép toán WRITE chuyển một phần tử để nối vào cuối tập tin, thì dữ liệu được gửi cho phép toán WRITE của hệ điều hành. Phép toán WRITE của hệ điều hành sẽ lưu dữ liệu vào trong vị trí có thể của bộ nhớ đệm. Khi trong bộ nhớ đệm đã tích lũy được một khối các phần tử thì khối đó sẽ được chuyển sang bộ nhớ ngoài (đĩa hoặc băng từ). Quá trình tiếp tục của phép toán WRITE được thực hiện bằng cách lấp đầy bộ nhớ đệm cho đến khi một khối có thể được chuyển ra bộ nhớ ngoài.

Ðối với READ thì ngược lại, một khối các phần tử của tập tin sẽ được chuyển sang bộ nhớ đệm và mỗi một phép toán READ được thực hiện bởi chương trình lại chuyển một phần tử từ bộ nhớ đệm sang biến chương trình cho đến khi bộ nhớ đệm trở thành rỗng thì một khối lại được chuyển từ bộ nhớ ngoài vào bộ nhớ đệm.

Tập tin văn bản

Tập tin văn bản là một tập tin của các ký tự. Ðây là một loại tập tin rất thông dụng vì nó được sử dụng một cách dễ dàng trong tất cả các ngôn ngữ lập trình và các công cụ khác (Các loại tập tin khác không có được đặc điểm này). Tập tin văn bản cũng là một tập tin tuần tự nên các thao tác trên nó cũng tương tự như trên tập tin tuần tự. Ngoài ra còn có các phép toán đặc biệt khác cho phép chuyển đổi dữ liệu khác thành ký tự và ngược lại khi đọc hoặc ghi trên tập tin văn bản.

Tập tin truy xuất trực tiếp

Tập tin truy xuất trực tiếp là một tập tin được tổ chức sao cho bất kỳ một phần tử nào cũng được truy xuất một cách ngẫu nhiên. Ðể làm được điều đó mỗi một phần tử của nó phải có một khóa chẳng hạn khóa của mỗi phần tử là số thứ tự của nó trong tập tin. Ðể truy xuất phần tử bất kỳ, trước hết con trỏ của tập tin phải được di chuyển tới phần tử có khóa được chỉ định, sau đó phép toán READ hoặc WRITE mới được thực hiện. Phép toán WRITE có thể thay đổi nội dung đã có trong một phần tử đã tồn tại.

Câu hỏi ôn tập

  1. Nêu định nghĩa kiểu dữ liệu có cấu trúc.
  2. Nêu tên các thuộc tính của cấu trúc dữ liệu?
  3. Thế nào là cấu trúc dữ liệu đồng nhất?
  4. Thế nào là cấu trúc dữ liệu không đồng nhất?
  5. Thế nào là cấu trúc dữ liệu có kích thước cố định?
  6. Thế nào là cấu trúc dữ liệu có kích thước thay đổi?
  7. Cho ví dụ về một cấu trúc dữ liệu đồng nhất.
  8. Cho ví dụ về một cấu trúc dữ liệu không đồng nhất.
  9. Cho ví dụ về một cấu trúc dữ có kích thước cố định.
  10. Cho ví dụ về một cấu trúc dữ có kích thước không cố định.
  11. Trên cấu trúc dữ liệu thường có các phép toán nào?
  12. Kể tên các phương pháp lựa chọn một phần tử của cấu trúc dữ liêu?
  13. Nêu tên các phương pháp biểu diễn cấu trúc dữ liệu trong bộ nhớ?
  14. Phép toán lựa chọn trực tiếp (ngẫu nhiên) một phần tử của cấu trúc dữ liệu được biểu diễn tuần tự được thực hiện bằng cách nào?
  15. Có phải kiểu véctơ (mảng một chiều) là một cấu trúc dữ liệu có kích thước cố định?
  16. Cho biết công thức xác định số phần tử của một vectơ.
  17. Cho biết công thức xác định địa chỉ (vị trí) của phần tử V[i] của véctơ V.
  18. Có phải kiểu véctơ (mảng một chiều) là một cấu trúc dữ liệu có kích thước không cố định?
  19. Có phải kiểu véctơ (mảng một chiều) là một cấu trúc dữ liệu đồng nhất?
  20. Có phải kiểu véctơ (mảng một chiều) là một cấu trúc dữ liệu không đồng nhất?
  21. Ðể lưu trữ một véctơ trong bộ nhớ, người ta thường sử dụng biểu diễn tuần tự hay biểu diễn liên kết?
  22. Cho biết công thức xác định số phần tử của một ma trận M[LB1..UB1, LB2..UB2] (mảng hai chiều).
  23. Cho biết công thức xác định địa chỉ (vị trí) của phần tử M[i,j] của ma trận M[LB1..UB1, LB2..UB2]. Biết rằng các phần tử được lưu trữ theo trật tự dòng.
  24. Cho biết công thức xác định địa chỉ (vị trí) của phần tử M[i,j] của ma trận M[LB1..UB1, LB2..UB2]. Biết rằng các phần tử được lưu trữ theo trật tự cột.
  25. Giả sử có khai báo VAR A:array[0..3, 1..3] of integer; Các phần tử của ma trận A được lưu trữ trong bộ nhớ theo phương pháp khai triển theo cột (trật tự cột). Hãy vẽ mô hình biểu diễn sự lưu trữ này.
  26. Giả sử có khai báo VAR A:array[0..3, 1..3] of integer; Các phần tử của ma trận A được lưu trữ trong bộ nhớ theo phương pháp khai triển theo dòngt (trật tự dòng). Hãy vẽ mô hình biểu diễn sự lưu trữ này.
  27. Giả sử có khai báo VAR A:array[0..3, 1..3] of integer; Các phần tử của ma trận A được lưu trữ trong bộ nhớ theo phương pháp khai triển theo dòng (trật tự dòng), giả sử địa chỉ cơ sở của khối ô nhớ là , kích thước bộ mô tả là D, kích thước mỗi phần tử là E. Hãy tính địa chỉ (vị trí) của phân tử A[1,2].
  28. Giả sử có khai báo VAR A:array[0..3, 1..3] of integer; Các phần tử của ma trận A được lưu trữ trong bộ nhớ theo phương pháp khai triển theo cột (trật tự cột), giả sử địa chỉ cơ sở của khối ô nhớ là , kích thước bộ mô tả là D, kích thước mỗi phần tử là E. Hãy tính địa chỉ (vị trí) của phân tử A[1,2].
  29. Nêu tên các thuộc tính của kiểu mẩu tin.
  30. Có phải mẩu tin là một cấu trúc dữ liệu có kích thước cố định?
  31. Có phải mẩu tin là một cấu trúc dữ liệu có kích thước không cố định?
  32. Có phải mẩu tin là một cấu trúc dữ liệu đồng nhất?
  33. Có phải mẩu tin là một cấu trúc dữ liệu không đồng nhất?
  34. Ðể lưu trữ một mẩu tin trong bộ nhớ, người ta thường sử dụng biểu diễn tuần tự hay biểu diễn liên kết?
  35. Việc lựa chọn một phần tử của mẩu tin được thực hiện bởi sự lựa chọn tuần tự hay trực tiếp?
  36. Có phải mẩu tin có cấu trúc thay đổi là một cấu trúc dữ liệu có kích thước cố định?
  37. Có phải mẩu tin có cấu trúc thay đổi là một cấu trúc dữ liệu có kích thước thay đổi?
  38. Nêu tên các phương pháp đặc tả chuỗi ký tự.
  39. Nêu tên các phép toán thường có trên kiểu chuỗi ký tự.
  40. Cấp phát tĩnh được thực hiện vào lúc nào?
  41. Cấp phát động được thực hiện vào lúc nào?
  42. Cho biết các ưu nhược điểm của cấp phát động.
  43. Sử dụng cấp phát tĩnh, người lập trình có thể chủ động giải phóng ô nhớ không?
  44. Sử dụng cấp phát động, người lập trình có thể chủ động giải phóng ô nhớ không?
  45. Biến con trỏ được cấp phát động hay cấp phát tĩnh?
  46. Có những loại con trỏ nào?
  47. Nêu tên các phép toán thường có trên tập hợp.
  48. Nêu tên các phương pháp để biểu diễn một tập hợp.
  49. Giả sử một tập hợp được biểu diễn bởi một vectơ bit, hãy cho biết giải thuật để thực hiện các phép toán Hợp, Giao và Hiệu hai tập hợp.
  50. Sử dụng véctơ bit để biểu diễn cho một tập hợp thì có những ưu, nhược điểm gì?
  51. Sử dụng bảng băm để biểu diễn cho một tập hợp thì có những ưu, nhược điểm gì?
  52. Giả sử một không gian có 5 phần tử e1, e2, e3, e4, e5>Tập hợp { e2, e1, e5, e4} được biểu diễn bởi vector bit nào?
  53. Giả sử có ba tập hợp A, B, C được biiểu diễn bởi ba vector bit tương ứng là (1, 0, 1, 1, 1); (1, 0, 1, 0, 1) và (1, 1, 1, 0, 1). Cho biết biểu thức liên hệ giữa các tập A,B và C?
  54. Kể tên các phép toán thường có trên tập tin tuần tự.
  55. Trong tập tin tuần tự, chúng ta có thể nhảy đến một phần tử bất kỳ để truy xuất nó hay không?
  56. Trong tập tin truy xuất trực tiếp, chúng ta có thể nhảy đến một phần tử bất kỳ để truy xuất nó hay không?
  57. Trong tập tin truy xuất trực tiếp, chúng ta có thể truy xuất các phần tử một cách tuần tự từ đầu đến cuối tập tin hay không?

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Cấu trúc dữ liệu. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10766/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Cấu trúc dữ liệu' conversation and receive update notifications?

Ask