Khái Niệm Về Kiểu Dữ Liệu Tập Hợp / 2023 / Top 19 # Xem Nhiều Nhất & Mới Nhất 11/2022 # Top View | 2atlantic.edu.vn

Tổng Quan,Khái Niệm,Kiểu Dữ Liệu Và Cài Đặt Tập Hợp Tổng Quan,Khái Niệm,Kiểu Dữ Liệu Và Cài Đặt Tập Hợp Bởi: Unknown Tổng Quan Về Tập Hợp Mục Tiêu Sau / 2023

1 Tổng quan,khái niệm,kiểu dữ liệu và cài đặt tập hợp Bởi: unknown TỔNG QUAN VỀ TẬP HỢP Mục tiêu Sau khi học xong chương này, sinh viên phải: – Nắm vững khái niệm về kiểu dữ liệu trừu tượng tập hợp và một số loại tập hợp đặc biệt như từ điển, bảng băm, hàng ưu tiên. – Cài đặt tập hợp và các loại tập hợp đặc biệt bằng ngôn ngữ lập trình cụ thể. Kiến thức cơ bản cần thiết Để học tốt chương này, sinh viên cần biết lập trình căn bản như: Kiểu mẩu tin (record), kiểu mảng (array) và kiểu con trỏ (pointer). Các cấu trúc điều khiển, lệnh vòng lặp. – Lập trình theo từng modul (chương trình con) và cách gọi chương trình con đó. Lập trình đệ qui và gọi đệ qui. Kiểu dữ liệu trừu tượng danh sách. Tài liệu tham khảo [1] Aho, A. V., J. E. Hopcroft, J. D. Ullman. “Data Structure and Algorihtms”, Addison Wesley; 1983 [2] Đỗ Xuân Lôi. “Cấu trúc dữ liệu và giải thuật”. Nhà xuất bản khoa học và kỹ thuật. Hà nội, (chương 10- Trang 300) 1/10

2 [3] Nguyễn Trung Trực, “Cấu trúc dữ liệu”. BK tp HCM, (Chương 6 trang 397) [4] Lê Minh Trung ; Lập trình nâng cao bằng pascal với các cấu trúc dữ liệu ; 1997 (chương 9) Nội dung cốt lõi Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau: – Khái niệm tập hợp – Kiểu dữ liệu trừu tượng tập hợp. – Cài đặt tập hợp – Từ điển – Cấu trúc bảng băm – Hàng ưu tiên. KHÁI NIỆM TẬP HỢP Tập hợp là một khái niệm cơ bản trong toán học. Tập hợp được dùng để mô hình hoá hay biểu diễn một nhóm bất kỳ các đối tượng trong thế giới thực cho nên nó đóng vai trò rất quan trọng trong mô hình hoá cũng như trong thiết kế các giải thuật. Khái niệm tập hợp cũng như trong toán học, đó là sự tập hợp các thành viên (members) hoặc phần tử (elements). Tất cả các phần tử của tập hợp là khác nhau. Tập hợp có thể có thứ tự hoặc không có thứ tự, tức là, có thể có quan hệ thứ tự xác định trên các phần tử của tập hợp hoặc không. Tuy nhiên, trong chương này, chúng ta giả sử rằng các phần tử của tập hợp có thứ tự tuyến tính, tức là, trên tập hợp S có quan hệ < và = thoả mản hai tính chất: Với mọi a,b S thì a<b hoặc b<a hoặc a=b Với mọi a,b,c S, a<b và b<c thì a<c KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP Cũng như các kiểu dữ liệu trừu tượng khác, các phép toán kết hợp với mô hình tập hợp sẽ tạo thành một kiểu dữ liệu trừu tượng là rất đa dạng. Tùy theo nhu cầu của các ứng 2/10

3 dụng mà các phép toán khác nhau sẽ được định nghĩa trên tập hợp. Ở đây ta đề cập đến một số phép toán thường gặp nhất như sau Thủ tục UNION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A?B. Thủ tục INTERSECTION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy giao của hai tập A và B và trả ra kết quả là tập hợp C = A? B. Thủ tục DIFFERENCE(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = AB Hàm MEMBER(x,A) cho kết quả kiểu logic (đúng/sai) tùy theo x có thuộc A hay không. Nếu x A thì hàm cho kết quả là 1 (đúng), ngược lại cho kết quả 0 (sai). Thủ tục MAKENULLSET(A) tạo tập hợp A tập rỗng Thủ tục INSERTSET(x,A) thêm x vào tập hợp A Thủ tục DELETESET(x,A) xoá x khỏi tập hợp A Thủ tục ASSIGN(A,B) gán A cho B ( tức là B:=A ) Hàm MIN(A) cho phần tử bé nhất trong tập A Hàm EQUAL(A,B) cho kết quả TRUE nếu A=B ngược lại cho kết quả FALSE CÀI ĐẶT TẬP HỢP Cài đặt tập hợp bằng vector Bit Hiệu quả của một cách cài đặt tập hợp cụ thể phụ thuộc vào các phép toán và kích thước tập hợp. Hiệu quả này cũng sẽ phụ thuộc vào tần suất sử dụng các phép toán trên tập hợp. Chẳng hạn nếu chúng ta thường xuyên sử dụng phép thêm vào và loại bỏ các phần tử trong tập hợp thì chúng ta sẽ tìm cách cài đặt hiệu quả cho các phép toán này. Còn nếu phép tìm kiếm một phần tử xảy ra thường xuyên thì ta có thể phải tìm cách cài đặt phù hợp để có hiệu quả tốt nhất. Ở đây ta xét một trường hợp đơn giản là khi toàn thể tập hợp của chúng ta là tập hợp con của một tập hợp các số nguyên nằm trong phạm vi nhỏ từ 1.. n chẳng hạn thì chúng ta có thể dùng một mảng kiểu Boolean có n phần tử để cài đặt tập hợp (ta gọi là vectơ bít), bằng cách cho phần tử thứ i của mảng này giá trị TRUE nếu i thuộc tập hợp hoặc cho mảng lưu kiểu 0-1. Nếu nội dung phần tử trong mảng tại vị trí i là 1 nghĩa là i tồn tại trong tập hợp và ngược lại, nội dung là 0 nghĩa là phần tử i đó không tồn tại trong tập hợp. Ví dụ: Giả sử các phần tử của tập hợp được lấy trong các số nguyên từ 1 đến 10 thì mỗi tập hợp được biểu diễn bởi một mảng một chiều có 10 phần tử với các giá trị phần tử thuộc kiểu logic. Chẳng hạn tập hợp A=1,3,5,8 được biểu diễn trong mảng có 10 phần tử như sau: 3/10

4 Cách biểu diễn này chỉ thích hợp trong điều kiện là mọi thành viên của tất cả các tập hợp đang xét phải có giá trị nguyên hoặc có thể đặt tương ứng duy nhất với số nguyên nằm trong một phạm vi nhỏ. Có thể dễ dàng nhận thấy khai báo cài đặt như sau const maxlength = 100;

5 if ((a[i]==1) (b[i]==1)) c[i]=1; else c[i]=0; void SET_intersection (SET a,set b, SET c) int i; for (i=0;i<maxlength;i++) if ((a[i]==1)&&(b[i]==1)) c[i]=1; else c[i]=0; Các phép toán giao, hiệu,… được viết một cách tương tự. Việc kiểm tra một phần tử có thuộc tập hợp hay không, thủ tục thêm một phần tử vào tập hợp, xóa một phần tử ra khỏi tập hợp cũng rất đơn giản và xem như bài tập. Cài đặt bằng danh sách liên kết Tập hợp cũng có thể cài đặt bằng danh sách liên kết, trong đó mỗi phần tử của danh sách là một thành viên của tập hợp. Không như biểu diễn bằng vectơ bít, sự biểu diễn này dùng kích thước bộ nhớ tỉ lệ với số phần tử của tập hợp chứ không phải là kích thước đủ lớn cho toàn thể các tập hợp đang xét. Hơn nữa, ta có thể biểu diễn một tập hợp bất kỳ. Mặc dù thứ tự của các phần tử trong tập hợp là không quan trọng nhưng nếu một danh sách liên kết có thứ tự nó có thể trợ giúp tốt cho các phép duyệt danh sách. Chẳng hạn nếu tập hợp A được biểu diễn bằng một danh sách có thứ tự tăng thì hàm MEMBER(x,A) có thể thực hiện việc so sánh x một cách tuần tự từ đầu danh sách cho đến khi gặp một phần tử y x chứ không cần so sánh với tất cả các phần tử trong tập hợp. Một ví dụ khác, chẳng hạn ta muốn tìm giao của hai tập hợp A và B có n phần tử. Nếu A,B biểu diễn bằng các danh sách liên kết chưa có thứ tự thì để tìm giao của A và B ta phải tiến hành như sau: for (mỗi x thuộc A ) 5/10

6 Duyệt danh sách B xem x có thuộc B không. Nếu có thì x thuộc giao của hai tập hợp A và B; Rõ ràng quá trình này có thể phải cần đến n x m phép kiểm tra (với n,m là độ dài của A và B). Nếu A,B được biểu diễn bằng danh sách có thứ tự tăng thì đối với một phần tử e A ta chỉ tìm kiếm trong B cho đến khi gặp phần tử x e. Quan trọng hơn nếu f đứng ngay sau e trong A thì để tìm kiếm f trong B ta chỉ cần tìm từ phần tử x trở đi chứ không phải từ đầu danh sách lưu trữ tập hợp B. Khai báo typedef int ElementType; typedef struct Node ElementType Data; Node * Next; ; typedef Node * Position; typedef Position SET; Thủ tục UNION

7 InsertSET (Retrieve(p,A),*C); p=next(p,a); p=first(b); while (p!=endset (B)) if (Member(Retrieve(p,B),*C)==0) InsertSET (Retrieve(p,B),*C); p=next(p,b); Thủ tục INTERSECTION

10 while ((P!= EndSET(L)) && (Found == 0)) if (Retrieve(P,L) == X) Found = 1; else P = Next(P, L); return Found; 10/10

Kotlin Bài 5: Khái Niệm Dữ Liệu, Kiểu Dữ Liệu &Amp; Khai Báo Biến / 2023

Chào mừng các bạn đã đến với bài học Android – Kotlin thứ 5, bài học về Dữ liệu, Kiểu dữ liệu và các cách khai báo Biến. Đây là bài học trong chuỗi bài viết về lập trình ứng dụng Android bằng Kotlin của Yellow Code Books.

Cái khái niệm về hay Kiểu dữ liệu thường bị các tài liệu về lập trình bỏ qua (chính mình cũng quên không nói phần này ở các bài học Java). Nếu bạn đã rành về lập trình, thì dĩ nhiên 2 khái niệm này không xa lạ gì, bạn hiểu thấu đáo và nhuần nhuyễn như trở bàn tay vậy. Nhưng với những người mới tiếp cận lập trình, thì mình nghĩ nếu không nắm được kiến thức ban đầu về 2 khái niệm này, sẽ làm giảm đi khả năng tiếp cận với cái được gọi là và khai báo sắp tới.

Trong khi đó, khi lập trình, các lập trình viên chúng ta lại rất khó code theo ngôn ngữ này. Nên các ngôn ngữ lập trình đã định nghĩa ra vô số loại dữ liệu rất là “con người”. Như loại số thập phân, loại ký tự, loại chuỗi,… Để rồi khi biên dịch, trình biên dịch sẽ dựa trên các logic nhất định để chuyển đổi “con người” mà lập trình viên chúng ta viết ra, về thành “máy” như đã nói trên kia.

Các Loại Biến Trong Kotlin

Bạn đã biết cách đặt tên . Giờ chúng ta cùng đến với các loại trong Kotlin.

Trước tiên, lại phải so sánh với Java một chút. Ở Java hay các ngôn ngữ lập trình khác đều đưa ra 2 khái niệm , đó là và . Trong đó sẽ là nơi lưu trữ dữ liệu, và cho phép thay đổi dữ liệu trên một cách thoải mái. Thì lại là một “Biến đặc biệt”, sau khi lưu trữ dữ liệu lên bạn sẽ không thể nào thay đổi dữ liệu của nó được. Trong khi giúp lưu trữ các dữ liệu là các kết quả tính toán, hay các dữ liệu có thể thay đổi khác, thì thích hợp cho các trường hợp định nghĩa các dữ liệu tĩnh. Ví dụ như nếu bạn định nghĩa là số Sao tối đa mà một khách sạn được đánh giá, thì thay vì sử dụng con số trong suốt chương trình, bạn định nghĩa một Hằng và sử dụng tên này trong toàn bộ chương trình của bạn, sẽ rất trực quan.

Khai Báo Biến Và Hằng

var tên_biến: kiểu_dữ_liệu

Hoặc

var tên_biến: kiểu_dữ_liệu = giá_trị

Hoặc

var tên_biến = giá_trị

Trong đó.

– Chính là tên của biến, được đặt theo quy tắc mà mình có nói ở link trỏ qua bài học Java trên kia.

– Khi khai báo , bạn có thể “gán” cho một giá_trị ban đầu, việc gán giá trị này sẽ làm cho lưu trữ dữ liệu ban đầu ngay khi được tạo ra. Bạn có thể gán dữ liệu cho lúc khai báo này, hoặc về sau cũng được. Nhưng có một lưu ý, là với bạn có thể gán hay thay đổi dữ liệu sau này tùy ý, còn với nếu khi nào bạn gán giá trị cho nó, thì giá trị đó vĩnh viễn không thể thay đổi trên đó nữa. Một lưu ý thú vị tiếp theo là, nếu bạn gán giá trị cho hay ngay khi khai báo nó, thì bạn có thể bỏ qua kiểu_dữ_liệu trong quá trình khai báo này, vì Kotlin rất hay, nó dựa vào của hay mà đoán biết được kiểu_dữ_liệu của chúng luôn.

Thực Hành Khai Báo Biến Và Hằng

fun main() { val inchToCentimet = 2.54 var fromIn = 5.0 var toCm: Double toCm = fromIn * inchToCentimet println("$fromIn inches = $toCm centimeteres") } fun main() { val inchToCentimet: Double = 2.54 var fromIn: Double = 5.0 var toCm: Double toCm = fromIn * inchToCentimet println("$fromIn inches = $toCm centimeteres") }

Bạn sẽ nhận được kết quả tương tự khi thực thi code này thôi. Đến đây thì bạn có thể nghĩ ra nhiều ứng dụng để mà vọc chơi với Kotlin được rồi đấy. Thậm chí bạn không cần phải biết cụ thể các Kiểu dữ liệu ở Kotlin. Chẳng hạn bạn có thể viết một ứng dụng tính bình phương của .

fun main() { val aNumber = 30 var powerNumber = aNumber * aNumber println("Result is $powerNumber") }

– bên dưới mỗi bài nếu thấy thích.– bên dưới mỗi bài nếu có thắc mắc.– Để lại địa chỉ email của bạn ở thanh bên phải để nhận được thông báo sớm nhất khi có bài viết mới.– các bài viết của Yellow Code Books đến nhiều người khác.

Bài sau mình sẽ trình bày cụ thể từng Kiểu dữ liệu mà Kotlin hỗ trợ. Kotlin Bài 6: Đang được viết tiếp… →

Dữ Liệu Kiểu Tệp: Khái Niệm Và Sử Dụng (P1) / 2023

Tệp dữ liệu với dữ liệu được hiểu theo nghĩa rộng : đó có thể là chương trình, có thể là số liệu, có thể là các dữ liệu khác như kí tự, văn bản…

Tệp còn có tệp có định kiểu, tệp văn bản và tệp không định kiểu (sẽ học kĩ ở cuối chương) .

Để dễ hình dung ra tệp, chúng ta hãy xem tổ chức tủ phiếu của thư viện. Các dữ liệu cho một cuốn sách là tên sách, tên tác giả, giá tiền, số trang, nhà xuất bản… Các dữ liệu này được nhóm lại với nhau để tạo thành các tờ phiếu, mỗi tờ phiếu đóng vai trò là một phần tử của tệp dưới dạng một Record (bản ghi) . Đây cũng là lý do gắn liền khái niệm cấu trúc dữ liệu Record với cấu trúc File. Các phần tử của tệp (các Record) có cùng một kiểu dữ liệu (Ví dụ các phiếu thư viện đều giống nhau ở chỗ mỗi cái đều có tên sách, tên tác giả, nhà xuất bản…) . Các phiếu này được xếp lại thành một tệp (phiếu) và được để vào một ô ngăn kéo nào đó với một cái tên (tên tệp) . Ví dụ ngăn chữ A (tên tệp là A) là tệp các cuốn sách có tên bắt đầu bằng chữ A. Các ngăn kéo lại được chứa trong một cái tủ. Trong máy tính, một đĩa cứng hoặc một một đĩa mềm đóng vai trò là chiếc tủ.

File còn được gọi là hồ sơ, là tập tin.

Tệp thường được chứa trong một bộ nhớ ngoài như đĩa cứng, đĩa mềm, băng từ. Điều đó cũng có nghĩa là tệp được lưu trữ để dùng nhiều lần và tồn tại ngay cả khi chương trình kết thúc hoặc mất điện. Khác với các cấu trúc dữ liệu khác mà chúng ta đã học như : mảng, tập hợp, bản ghi, là các cấu trúc dữ liệu được tổ chức trên bộ nhớ trong (RAM) của máy tính nên một khi kết thúc chạy chương trình hoặc mất điện thì các dữ liệu này cũng mất luôn. Vì vậy những dữ liệu nào cần lưu trữ (như hồ sơ cán bộ, vật tư hàng hóa của kho, tín hiệu điện…) thì ta bắt buộc phải dùng đến tệp. Bên cạnh đó một số thiết bị ngoại vi như bàn phím, màn hình, máy in được coi như là một tệp (xem phần tệp văn bản ở sau) . Tệp cũng còn có thể tổ chức trong bộ nhớ trong của máy song đó là những tệp tạm thời, trung gian vì chúng không lưu trữ lại được khi dừng chương trình hoặc mất điện.

Tệp là một kiểu dữ liệu có cấu trúc. Định nghĩa của tệp có phần nào giống mảng ở chỗ chúng đều là tập hợp của các phần tử dữ liệu có cùng kiểu. Song mảng được định nghĩa và khai báo trong chương trình với số phần tử đã xác định còn số phần tử của tệp không được xác định khi định nghĩa.

Định nghĩa một kiểu tệp T với các phần tử có kiểu là KPT (Kiểu phần tử) được viết trong phần mô tả kiểu với từ khóa FILE OF như sau :

Type

T = File Of KPT ;

Sau đó khai báo một biến tệp (FileVar) trong phần khai báo biến :

Var

Biến_tệp : Kiểu_tệp ;

hoặc khai báo trực tiếp một biến tệp với mô tả kiểu :

Var

Biến_tệp : File Of Kiểu_phần_tử ;

Ví dụ:

Type

FileInteger = File Of Integer ;

FileReal = File Of Real ;

FileBoolean = File Of Boolean ;

NhanSu = Record

Ten : String[ 30 ] ;

Tuoi : Byte ;

Luong : Real ;

End ;

FileNhanSu = File Of NhanSu ;

Var (* khai báo các biến tệp *)

F1, F2 : FileInteger ; (* F1, F2 là hai biến tệp có các phần tử là số nguyên *)

F3 : FileReal ; (* F3 là tệp các số thực *)

FNS : FileNhanSu ; (* FNS là tệp các bản ghi nhân sự *)

F5 : File Of Char ;

F6 : File Of

Array[ 1.. 5 ] Of Integer ;

F6 là biến tệp được khai báo trực tiếp trong phần Var với các phần tử là mảng một chiều, độ dài mảng là 5.

FileInteger là kiểu tệp có các phần tử là số nguyên.

FileReal là kiểu tệp có các phần tử là số thực.

Kiểu của phần tử của tệp có thể là bất kỳ kiểu dữ liệu nào (kiểu vô hướng, kiểu có cấu trúc như mảng, tập, bản ghi) , trừ kiểu tệp nghĩa là không có kiểu tệp của tệp.

CẤU TRÚC VÀ VÀ PHÂN LOẠI TỆP

Các phần tử của một Array hoặc một Record có thể truy nhập được tùy ý (Random Access) thông qua tên biến, chỉ dẫn hoặc tên trường. Các phần tử của tệp không có tên và việc truy nhập không thể tùy tiện được. Các phần tử của tệp được sắp xếp thành một dãy và ở mỗi thời điểm chương trình chỉ có thể truy nhập vào một phần tử của tệp thông qua giá trị của một biến đệm (Tampon Variance). Biến đệm được dùng để đánh dấu vị trí truy nhập hay còn được gọi là cửa sổ (Window) của tệp.

Có những lệnh sẽ làm dịch chuyển cửa sổ sang vị trí tiếp theo hoặc về vị trí đầu của tệp. Ta có thể hình dung ra tệp như là một cuộn phim chụp ảnh. Mỗi một ảnh là một phần tử và ống kính là cửa sổ để nhìn vào nên tại mỗi thời điểm chỉ nhần thấy một ảnh. Sau mỗi lần chụp, cửa sổ sẽ nhìn vào ảnh ở vị trí tiếp theo.

Mỗi tệp đều được kết thúc bằng một dấu hiệu đặc biệt để báo hết tệp, hay gọi là EOF (End Of File). Pascal có một hàm chuẩn (Function) EOF, kiểu Boolean, với tham số là một biến tệp để thử xem cửa sổ đã đặt vào vị trí kết thúc tệp đó chưa. Nếu cửa sổ còn chưa trỏ vào phần tử cuối tệp thì EOF(F) có giá trị là False.

Việc phân loại tệp dựa trên việc bố trí các phần tử của tệp trong bộ nhớ ngoài và cách truy nhập vào tệp : tệp truy nhập tuần tự(Sequential Access), tệp truy nhập trực tiếp(Direct Access).

Thông dụng nhất là tệp có cấu trúc tuần tự : việc đọc một phần tử bất kỳ của tệp bắt buộc phải tuần tự đi qua các phần tử trước đấy. Còn muốn ghi hay thêm một phần tử vào tệp, ta cần phải đặt cửa sổ vào vị trí cuối tệp. Kiểu truy nhập này là đơn giản nhất trong việc xây dựng tệp cũng như xử lý tệp, song nó kém linh hoạt, Bộ nhớ ngoài điển hình tương ứng với cấu trúc này là băng từ.

Tệp truy nhập trực tiếp (direct access) là tệp có thể đặt cửa sổ vào một phần tử bất kỳ của tệp thông qua chỉ số thứ tự của phần tử trong tệp. Không phải loại bộ nhớ ngoài nào cũng có thể xây dựng tệp truy nhập trực tiếp do cấu tạo bộ nhớ. Ví dụ băng từ là loại chỉ có thể truy nhập tuần tự. Còn đĩa mềm, đĩa cứng là loại bộ nhớ có thể tạo tệp truy nhập trực tiếp do đầu từ ghi đọc có thể được điều khiển đặt vào một chỗ bất kỳ trên đĩa vào mọi thời điểm. Bạn có thể so sánh giữa băng từ ghi nhạc (bắt buộc truy nhập tuần tự) với đĩa hát (có khả năng truy nhập trực tiếp).

MỞ TỆP MỚI ĐỂ LƯU DỮ LIỆU

Chương trình chỉ có thể cất dữ liệu vào một tệp sau khi ta làm thủ tục mở tệp . Việc mở tệp có thể ví như muốn cất các phếu thư viện thì đầu tiên phải đóng ô phiếu mới và gắn tên ô phiếu .

Để mở tệp để ghi, Turbo Pascal dùng 2 cặp thủ tục đi liền nhau theo thứ tự :

Assign ( Biến_tệp, Tên_tệp ) ;

Rewrite ( Biến_tệp ) ;

hay bằng tiếng Anh ta có :

Assign ( FileVar, FileName ) ;

Rewrite ( FileVar )

Ví dụ:

Assign ( F,’nguyento.dat’ ); (* gán tên tệp chúng tôi cho biến F *)

Reset ( F );

Tên tệp ( FileName) là tên của tệp đặt trong thiết bị nhớ ngoài được đưa vào dưới dạng một String. Ta phải đặt tên tệp sao cho nó phản ánh được ý nghĩa hoặc bản chất, nội dung của tệp. Ví dụ biến tệp F chứa các số nguyên tố thì tệp được đặt tên là ‘ nguyento.dat’.

Tên tệp theo quy định chung gồm có hai phần cách nhau bằng dấu chấm (.) . Phần thứ nhất là phần tên riêng, có số chữ nhiều nhất là 8 . Phần tên này thể hiện nội dung của tệp đó . Phần thứ hai là phần mở rộng có nhiều nhất là 3 chữ, thông thường nói lên loại tệp .

Ví dụ :

* . Pas : là tệp chứa chương trình viết bằng Pascal .

* . Doc : là tệp chứa văn bản, tài liệu .

* . Txt : chứa tệp văn bản .

* . Com và * . Exe : là các tệp chứa chương trình dưới dạng mã mà máy có thể chạy ngay được trên máy tính .

* . Dat : chứa các dữ liệu cần xử lý ( Data )

Sau khi mở tệp xong, tệp sẽ rỗng vì chưa có phần tử nào, cửa sổ tệp sẽ không có giá trị xác định vì nó trỏ vào cuối tệp ( EOF). Đồng thời cần lưu ý khi mở tệp nếu trên bộ nhớ ngoài mà đã có sẵn tệp có tên trùng với tên tệp được mở thì tệp cũ sẽ bị xóa đi .

GHI CÁC GIÁ TRỊ VÀO TỆP VỚI THỦ TỤC WRITE :

Thủ tục WRITE sẽ đặt các giá trị mới vào tệp giống như ta bấm máy chụp ảnh . Mỗi lần chụp xong một ảnh, máy sẽ tự động đưa ống kính sang vị trí tiếp theo .

Cách viết :

Write ( FileVar, Item1, Item2, . ., ItemN ) ;

hay Write ( Biến_tệp, các giá trị cần đặt vào ) ;

Trong đó Item1, Item2, . . . ItemN có thể là các hằng, các biến, các biểu thức, tất nhiên các Item phải có giá trị cùng với kiểu phần tử của tệp.

Hoặc với I, J, K là các biến Integer thì ta hoàn toàn có thể viết :

Write ( F, 3, I + 2 * J, K ) ;

Bước cuối cùng của việc đặt dữ liệu vào tệp là đóng tệp lại bằng thủ tục

Close ( Biến_tệp ) ;

Ví dụ đối với tệp F1: Close ( F1 ) ;

Program TAO_TEP_1 ;

Var

I : Integer ;

F : File Of Integer ;

BEGIN

Assign ( F, ‘Nguyen.dat’ ) ;

Rewrite ( F ) ;

For I :=1 To 100 Do Write ( F, I ) ;

Close ( F ) ;

END .

Một tệp có thể đựoc dùng làm tham số của chương trình con (Procedure hoặc Function) với lời khai báo bắt buộc phải sau chữ Var tức là tệp được dùng làm tham biến

Ví dụ 2 :

Program TAO_TEP_2 ;

Type

F1 = File Of Integer ;

St30 = String [ 30 ] ;

Var

MyFile : F1 ;

FileName : St30 ;

Procedure TaoFile ( Var F : F1 ; Ten : St30 ) ;

Var

I : Integer ;

Begin

Assign ( F, Ten ) ;

Rewrite ( F ) ;

For I := 1 To 100 Do Write ( F, I ) ;

Close ( F ) ;

End ;

BEGIN

Write (‘ Ten tep : ‘) ;

Readln ( FileName ) ;

TaoFile ( MyFile, FileName ) ;

END .

Ví dụ trên còn gài thủ thuật gài tên rtệp vào khi chương trình chạy thông qua một biến FileName, tương ứng với tham số hình thức là Ten.

Võ Nhật Trường

Dữ Liệu Kiểu Mảng (Array) / 2023

DỮ LIỆU KIỂU MẢNG (ARRAY)

I. KHAI BÁO MẢNG

Cú pháp: hoặc khai báo trực tiếp: Ví dụ: TYPE  Mangnguyen = Array[1..100] of Integer; Matrix = Array[1..10,1..10] of Integer; MangKytu = Array[Byte] of Char; VAR                A: Mangnguyen; M: Matrix; C: MangKytu; hoặc: VAR                A: Array[1..100] of Integer; C: Array[Byte] of Char;

II. XUẤT NHẬP TRÊN DỮ LIỆU KIỂU MẢNG

– Để truy cập đến phần tử thứ k trong mảng một chiều A, ta sử dụng cú pháp: A[k].

– Để truy cập đến phần tử (i,j) trong mảng hai chiều M, ta sử dụng cú pháp: M[i,j].

– Có thể sử dụng các thủ tục READ(LN)/WRITE(LN) đối với các phần tử của biến kiểu mảng.

BÀI TẬP MẪU

Bài tập 5.1:     Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử.

Ý tưởng: – Cho số lớn nhất là số đầu tiên: Max:=a[1].

Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var    A:Mang; N,i,Max:Integer; Begin {Nhập mảng} Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; {Tìm phần tử lớn nhất} Max:=A[1]; For i:=2 To N Do If Max&lt;A[i] Then Max:=A[i]; {In kết quả ra màn hình} Writeln(‘Phan tu lon nhat cua mang: ’, Max); Readln; End.

Bài tập 5.2:     Viết chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử. Ý tưởng: Duyệt qua tất cả các phần tử A[i] trong mảng: Nếu A[i]<0 thì cộng dồn (A[i])2 vào biến S.

Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var    A:Mang; N,i,S:Integer; Begin {Nhập mảng} Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; {Tính tổng} S:=0; For i:=1 To N Do If A[i]&lt;0 Then S:=S+A[i]*A[i]; {In kết quả ra màn hình} Writeln(‘S= ’, S); Readln; End.

Bài tập 5.3: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình. Ý tưởng:

Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var    A:Mang; N,i,j,Tam:Integer; Begin {Nhập mảng} Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; {Sắp xếp} For i:=1 To N-1 Do For j:=i+1 To N Do If A[i]&gt;A[j] Then Begin Tam:=A[i]; A[i]:=A[j]; A[j]:=Tam; End; {In kết quả ra màn hình} Writeln(‘Ket qua sau khi sap xep:’); For i:=1 To N Do Write(A[i]:5); Readln; End.

Bài tập 5.4: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không? Ý tưởng: Nếu x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìm thấy).

Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var    A:Mang; N,i,x:Integer; Function TimKiem(x, N: Integer; A:Mang):Integer; Var i:Integer; Begin I:=1; While (I &lt;= N) and (X&lt;&gt;A[I]) do I:=I+1; If I &lt;= N Then Timkiem:=I  Else Timkiem:=0; End; Begin {Nhập mảng} Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; Write(‘Nhap X=’); Readln(x); {Kết quả tìm kiếm} If TimKiem(X,N,A)&lt;&gt;0 Then Writeln(‘Vi tri cua X trong mang la:’, TimKiem(X,N,A)) Else Writeln(‘X khong co trong mang.’); Readln; End.

Bài tập 5.5: Giả sử mảng A đã được sắp xếp theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay không? Ý tưởng: Sau đây là hàm cài đặt cho thuật toán này:

Function TimKiemNhiPhan(X, N: Integer; A: Mang):Integer; Var    dau,cuoi,giua:Integer; Found:Boolean; Begin dau:=1; {điểm mút trái của khoảng tìm kiếm} cuoi:=N; {điểm mút phải của khoảng tìm kiếm} Found:=False; {chưa tìm thấy} While (dau &lt;=cuoi) and (Not Found) Do Begin giua:=(dau + cuoi) Div 2; If  X = A[giua] Then Found:=True {đã tìm thấy} Else If X &gt; A[giua] Then dau:=giua+1 Else cuoi:=giua-1; End; If Found Then TimKiemNhiPhan:= giua Else TimKiemNhiPhan:=0; End;

Bài tập 5.6: Viết chương trình tìm ma trận chuyển vị của ma trận A. Ý tưởng: Dùng mảng 2 chiều để lưu trữ ma trận. Gọi B là ma trận chuyển vị của ma trận A, ta có: Bij = Aji.

Uses Crt; Type Mang = ARRAY[1..10,1..10] Of Integer; Var    A,B:Mang; m,n,i,j:Integer; Begin {Nhập ma trận} Write(‘Nhap số dòng m=’); Readln(m); Write(‘Nhap số cột n=’); Readln(n); For i:=1 To m Do For j:=1 To n Do Begin Write(‘A[‘,i,j,’]=’); Readln(A[i,j]); End; {Tìm ma trận chuyển vị} For i:=1 To m Do For j:=1 To n Do     B[i,j]:=A[j,i]; {In ma trận chuyển vị ra màn hình} For i:=1 To m Do Begin For j:=1 To n Do     Write(B[i,j]:5); Writeln; End; Readln; End.

Bài tập 5.7: Cho một mảng 2 chiều A cấp mxn gồm các số nguyên và một số nguyên x. Viết chương trình thực hiện các công việc sau: a/ Đếm số lần xuất hiện của x trong A và vị trí của chúng. b/ Tính tổng các phần tử lớn nhất của mỗi dòng.

Uses Crt; Type Mang = ARRAY[1..10,1..10] Of Integer; Var    A:Mang; m,n,i,j,x,dem,S,max:Integer; Begin {Nhập ma trận} Write(‘Nhap số dòng m=’); Readln(m); Write(‘Nhap số cột n=’); Readln(n); For i:=1 To m Do For j:=1 To n Do Begin Write(‘A[‘,i,j,’]=’); Readln(A[i,j]); End; {Nhập x} Write(‘Nhap x=’); Readln(x); {Đếm số lãn xuất hiện của x và vị trí của x} dem:=0; Writeln(‘Vi tri cua x trong mang A: ‘); For i:=1 To m Do For j:=1 To n Do If x=A[i,j] Then Begin Write(i,j,’ ; ‘); dem:=dem+1; End; Writeln(‘So lan xuat hien cua x trong mang A la: ‘,dem); {Tính tổng các phần tử lớn nhất của mỗi dòng} S:=0; For i:=1 To m Do {duyệt qua từng dòng} Begin {Tìm phần tử lớn nhất của dòng thứ i} Max:=A[i,1]; For j:=2 To n Do     {duyệt từng phần tử của dòng thứ i} If max&lt;A[i,j] Then max:=A[i,j]; {Cộng max vào biến S} S:=S+max; End; Writeln(‘Tong cac phan tu lon nhat cua moi dong la: ‘,S); Readln; End.

Bài tập 5.8: Giải phương trình bằng phương pháp chia nhị phân. Ý tưởng: Giả sử cần tìm nghiệm của phương trình f(x)=0 trên đoạn [a,b] với y=f(x) đồng biến và đơn trị trên đoạn [a,b]. Ta giải như sau:

Gọi m là trung điểm của đoạn [a,b]. Nếu f(m)*f(a)<0 thì giới hạn đoạn tìm nghiệm thành [a,m]. Tương tự đối với đoạn [m,b]. Quá trình này lặp lại cho đến khi f(m)<e, lức này ta có 1 nghiệm gần đúng là m.

Giả sử f(x) là một đa thức: f(x) = a0 + a1x + a2x2 + … + anxn. Lúc này, ta có thể dùng mảng một chiều để lưu trữ các hệ số ai của đa thức.

Uses Crt; Type HESO=Array[0..20] Of Real; Var    a:HESO; n:Byte; Min,Max,epsilon:Real; Procedure NhapDaThuc; Var i:Byte; Begin Write('Bac cua da thuc: n= '); Readln(n); Writeln('Nhap cac he so cua da thuc:'); For i:=0 To n Do Begin Write('a[',i,']='); Readln(a[i]); End; Writeln('Nhap doan tim nghiem:[a,b]'); Write('a= '); Readln(Min); Write('b= '); Readln(Max); Write('Nhap sai so cua phuong trinh: '); Readln(epsilon); End; {Tính giá trị của đa thức} Function f(x:Real):Real; Var    S,tam:Real; i:Byte; Begin S:=a[0]; tam:=1; For i:=1 To n Do Begin tam:=tam*x; S:=S+a[i]*tam; End; f:=S; End; Procedure TimNghiem(Min,Max:real); Var m:Real; Begin If f(Min)*f(Max)&gt;0 Then Writeln('Phuong trinh vo nghiem.') Else If abs(f(Min))&lt;epsilon Then Writeln('Nghiem la x=',min:0:2) Else If abs(f(Max))&lt;epsilon Then Writeln('Nghiem la x=',max:0:2) Else Begin m:=(Min+Max)/2; If abs(f(m))&lt;=epsilon Then Writeln('Nghiem la x=',m:0:2) Else If f(Min)*f(m)&lt;0 Then TimNghiem(Min,m) Else TimNghiem(m,Max); End; End; Begin NhapDaThuc; TimNghiem(Min,Max); Readln; End.

Bài tập 5.9: Viết chương trình nhập vào số tự nhiên N (N lẻ), sau đó điền các số từ 1 đến n2 vào trong một bảng vuông sao cho tổng các hàng ngang, hàng dọc và 2 đường chéo đều bằng nhau (bảng này được gọi là Ma phương).

Ví dụ: Với N=3 và N=5 ta có

Xuất phát từ ô bên phải của ô nằm giữa. Đi theo hướng đông bắc để điền các số 1, 2, … Khi điền số, cần chú ý một số nguyên tắc sau: – Nếu vượt ra phía ngoài bên phải của bảng thì quay trở lại cột đầu tiên. – Nếu vượt ra phía ngoài bên trên của bảng thì quay trở lại dòng cuối cùng. – Nếu số đã điền k chia hết cho N thì số tiếp theo sẽ được viết trên cùng một hàng với k nhưng cách 1 ô về phía bên phải.

Uses Crt; Var A:Array[1..20,1..20] Of Word; n,i,j,k:Word; Begin Write('Nhap N= '); Readln(n); Clrscr; {Định vị ô xuất phát} i:=n DIV 2 + 1; j:=n DIV 2 + 2; {Điền các số k từ 1 đến n*n} For k:=1 To n*n Do Begin A[i,j]:=k; If k MOD n=0 Then j:=j+2 Else Begin {Đi theo hướng đông bắc} j:=j+1; i:=i-1; End; If j&gt;n Then j:=j MOD n; If i=0 Then i:=n; End; {In kết quả ra màn hình} For i:=1 To n Do Begin For j:=1 To n Do write(a[i,j]:4); Writeln; End; Readln; End.

Bài tập 5.10: Viết chương trình nhập vào 2 mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập vào đã có trong mảng thì không bổ sung vào mảng. In ra màn hình các phần tử là giao của 2 tập hợp A, B. Ý tưởng: Duyệt qua tất cả các phần tử aiÎA. Nếu aiÎB thì viết ai ra màn hình.

Uses Crt; Type Mang=ARRAY[1..50] Of Integer; Var A,B:Mang; n,m:Byte; Function KiemTra(x:Integer; n:Byte; A:Mang):Boolean; Var i:Byte; Found:Boolean; Begin Found:=False; i:=1; While (i&lt;=n) AND (not Found) Do If x=A[i] Then Found:=True Else i:=i+1; KiemTra:=Found; End; Procedure NhapMang(Var n:Byte; Var A:Mang); Var ch:Char; x:Integer; Begin n:=0; Repeat Write('x='); Readln(x); If not KiemTra(x,n,A) Then Begin n:=n+1; A[n]:=x; End; Writeln('An ESC de ket thuc nhap!'); ch:=Readkey; Until ch=#27; End; Procedure GiaoAB(n:Byte; A:Mang;m:Byte; B:Mang); Var i:Byte; Begin For i:=1 To n Do If KiemTra(A[i],m,B) Then Write(A[i]:4); End; Begin Clrscr; Writeln('Nhap mang A: '); NhapMang(n,A); Writeln('Nhap mang B: '); NhapMang(m,B); Writeln('Giao cua 2 mang A&amp;B la: '); GiaoAB(n,A,m,B); Readln; End.

Bài tập 5.11: Cho một mảng số nguyên gồm n phần tử. Tìm dãy con gồm m phần tử  (m£n) sao cho dãy con này có tổng lớn nhất. (Dãy con là dãy các phần tử liên tiếp nhau trong mảng).

Uses Crt; Type Mang=ARRAY[1..50] Of Integer; Var A:Mang; n,m,i,j,k:Byte; S,Max:Integer; Begin Write('So phan tu cua mang: n= '); Readln(n); For i:=1 To n Do Begin Write('a[',i,']='); Readln(a[i]); End; Write('Nhap so phan tu cua day con: m= '); Readln(m); k:=1; {Vị trí phần tử đầu tiên của dãy con} {Giả sử m phần tử đầu tiên của mảng A là dãy con có tổng lớn nhất} Max:=0; For i:=1 To m Do Max:=Max+A[i]; {Tìm các dãy con khác} For i:=2 To n-m+1 Do Begin {Tính tổng của dãy con thứ i} S:=0; For j:=i To i+m-1 Do S:=S+A[j]; If S&gt;Max Then {Nếu dãy con tìm được có tổng lớn hơn dãy con trước} Begin Max:=S; {Thay tổng mới} k:=i;       {Thay vị trí đầu tiên của dãy con mới} End; End; Writeln('Day con co tong lon nhat la:'); For i:=k To k+m-1 Do Write(A[i]:5); Readln; End.

Bài tập 5.12: Viết chương trình in ra màn hình tam giác Pascal. Ví dụ, với n=4 sẽ in ra hình sau:

1

1          1

1          2          1

1          3          3          1

1          4          6          4          1

Ý tưởng: Tam giác Pascal được tạo ra theo qui luật sau: + Mỗi dòng đều bắt đầu và kết thúc bởi số 1. + Phần tử thứ j ở dòng k nhận được bằng cách cộng 2 phần tử thứ j-1 và j ở dòng thứ k-1.

Uses Crt; Var Dong:Array[0..20] Of Byte; n,i,j:Byte; Begin Write('n= '); Readln(n); Clrscr; Dong[0]:=1; Writeln(Dong[0]:4); {Khoi tao gia tri cua dong} For i:=1 To n Do Dong[i]:=0; {Voi moi dong i} For i:=1 To n Do Begin For j:=i DownTo 1 Do Begin Dong[j]:=Dong[j-1]+Dong[j]; Write(Dong[j]:4); End; Writeln(Dong[i]:4); End; Readln; End.

BÀI TẬP TỰ GIẢI

Bài tập 5.13: Viết chương trình nhập vào một dãy số thực và số thực x. Thông báo lên màn hình số lượng các phần tử trong dãy bằng x và vị trí của chúng. Bài tập 5.14: Nhập vào một mảng các số nguyên. a/ Xếp lại mảng đó theo thứ tự giảm dần. b/ Nhập vào một số nguyên từ bàn phím. Chèn số đó vào mảng sao cho mảng vẫn có thứ tự giảm dần. (không được xếp lại mảng) Gợi ý: – Tìm vị trí cần chèn: i. – Đẩy các phần tử từ vị trí i tới n sang phải 1 vị trí. – Gán: A[i]=x; Bài tập 5.15: Cho 2 mảng số nguyên: Mảng A có m phần tử, mảng B có n phần tử. a/ Sắp xếp lại các mảng đó theo thứ tự giảm dần. b/ Trộn 2 mảng đó lại thành mảng C sao cho mảng C vẫn có thứ tự giảm dần (Không được xếp lại mảng C). Gợi ý: – Dùng 2 chỉ số i,j để duyệt qua các phần tử của 2 mảng A, B và k là chỉ số cho mảng C. – Trong khi (i<=m) và (j<=n) thì: {Tức là khi đồng thời cả 2 dãy A, B đều chưa duyệt hết} + Ngược lại: C[k]:=B[j]; j:=j+1; – Nếu dãy nào hết trước thì đem phần còn lại của dãy kia bổ sung vào cuối dãy C. Bài tập 5.16: Viết chương trình tính tổng và tích 2 ma trận vuông A, B cấp n. Gợi ý: Công thức tính tổng 2 ma trận: Cij = Aij + Bij Công thức tính tích 2 ma trận: Cij = Bài tập 5.17: Viết chương trình nhập vào 2 dãy số nguyên (a)n và (b)m, m£n. Kiểm tra xem dãy {b} có phải là dãy con của dãy {a} không? Bài tập 5.18: Viết chương trình nhập vào một dãy số nguyên a1, a2, …, an. Tìm trong dãy {a} một dãy con tăng dần dài nhất (có số phần tử lớn nhất) và in ra màn hình dãy con đó.

Bài tập 5.19: Cho mảng 2 chiều A cấp mxn. Viết chương trình sắp xếp lại mảng A theo yêu cầu sau: a/ Các phần tử trên mỗi dòng được sắp xếp theo thứ tự giảm dần. b/ Các dòng được sắp xếp lại theo thứ tự tăng dần của tổng các phần tử trên mỗi dòng. Bài tập 5.20: Viết chương trình để kiểm tra một dãy các số nguyên được nhập vào từ bàn phím đã được sắp theo thứ tự tăng dần hay chưa theo 2 cách: Đệ qui và không đệ qui. Gợi ý: – Nếu dãy có 1 phần tử thì dãy tăng dần. – Ngược lại: + Ngược lại: Gọi đệ qui với dãy có n-1 phần tử (bỏ bớt đi phần tử cuối cùng). Bài tập 5.21: Viết chương trình nhập vào 2 mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập vào đã có trong mảng thì không bổ sung vào mảng. a/ In ra màn hình hợp của 2 tập hợp A, B. b/ In ra màn hình hiệu của 2 tập hợp A, B. Gợi ý: a/ – In ra màn hình tất cả các phần tử của  tập hợp A. – Duyệt qua tất cả các phần tử b­i­ÎB. Nếu biÏA thì in bi ra màn hình. b/ Duyệt qua tất cả các phần tử a­i­ÎA. Nếu aiÏB thì in ai ra màn hình. Bài tập 5.22: Viết chương trình tính tổng của 2 đa thức h(x) = f(x) + g(x). Trong đó, mỗi đa thức có dạng: a0 + a1x + a2x2 + … + anxn. Gợi ý: Dùng các mảng A, B, C để lưu trữ các hệ số ai của các đa thức f(x), g(x) và h(x).

Bài tập 5.23: Viết chương trình để tìm các phương án đặt 8 quân hậu trên bàn cờ vua (ma trận 8×8) sao cho các quân hậu không ăn được nhau. Gợi ý: Dùng giải thuật quay lui. Bài tập 5.24: Viết chương trình tính định thức của ma trận vuông cấp n. Gợi ý: Dùng cách tính định thức theo phương pháp GAUSE.

‹ CHƯƠNG TRÌNH CON: THỦ TỤC VÀ HÀM XÂU KÝ TỰ (STRING) ›