Giáo trình Ngôn ngữ lập trình Pascal (Phần 2)

ý. Trong Write, Writeln có thể dùng cách in có quy cách nh− đã trình bày. c. Đọc dữ liệu từ tập tin văn bản Chúng ta có thể đọc không những các kí tự từ tập tin văn bản mà còn có thể đọc lại các số nguyên, thực, logic từ tập tin văn bản thông qua các thủ tục: Dạng 1. Read(,, ,...,); Dạng 2. Readln(,,,...,): Dạng 3. Readln(); trong đó ,,..., là các biến thuộc kiểu kí tự, Nguyên, Thực, Logic, Chuỗi. Dạng 1 đọc một hay nhiều phần tử mà không chuyển cửa sổ tập tin xuống dòng. Dạng 2 t−ơng tự dạng 1 nh−ng chuyển cửa sổ tập tin sang đầu dòng tiếp theo sau khi đã lần lần l−ợt đọc các biến t−ơng ứng. Dạng 3 đ−a cửa sổ tập tin sang đầu dòng tiếp theo mà không đọc gì cả. Ví dụ 18. Ch−ơng trình sau đây đọc và in ra màn hình nội dung của tập tin kiểu Text file có tên Vanban.txt đ−ợc tạo ra từ ch−ơng trình sau: Program Doc_File; Uses Crt; 94 Var F: Text; Dong:String[80]; Begin Clrscr; Assign(F,’VanBan.txt’); Reset(F); While Not EOF(F) Do Begin Readln(F,dong); Writeln(dong); End; Close(F); Readln; End. d. Thủ tục thêm dòng – Thủ tục Append(Var F:Text); Mở tập tin văn bản để thêm vào các dòng. Thủ tục Append mở tập tin theo lối ghi, định vị cửa sổ tập tin, sau đó nếu gặp thủ tục Write hay Writeln nội dung thêm vào sẽ đ−ợc đặt vào cuối tập tin. Ví dụ 19. Ch−ơng trình sau đây thêm hai dòng vào cuối tập tin VanBan.txt Program Them; Var F:Text; Begin Assign(F;’VanBan.txt’); Append(F); Writeln(F,’Day la dong thu nhat them vao’); Writeln(F,’Day la dong thu hai them vao’); Close(F); End. e. Các tập tin thiết bị 95 Một số phần mềm của Pascal coi các thiết bị ngoài nh− các tập tin văn bản. Nghĩa là việc xuất nhập đ−ợc thực hiện bằng các thao tác nh− với tập tin văn bản. Chẳng hạn đối với Turbo Pascal ta có thể sử dụng các tập tin chuẩn sau : (Không cần khai báo lại). – OUTPUT là tập tin xuất cơ bản. Thông th−ờng OUTPUT đã đ−ợc tự động gán cho màn hình. Khi dùng biến tập tin OUTPUT, các thủ tục Write, Writeln không cần ghi rõ OUTPUT. Đó cũng chính là cách viết Write, Writeln mà ta đã học từ đầu. Chẳng hạn, lệnh Writeln(a,b,c); đ−ợc hiểu ngầm là Writeln(Output,a,b,c); – INPUT là tập tin nhập cơ bản t−ơng ứng với tập tin chứa dữ liệu nguồn vào, th−ờng đ−ợc tự động gán cho bàn phím (tr−ớc đây có thể máy đọc bìa, đọc băng). INPUT không phải ghi vào vị trí FileVar trong thủ tục Read hay Readln. Chẳng hạn, Read(Var); đ−ợc hiểu là Read(Input,Var) – LST : Trong Turbo Pascal, máy in đ−ợc định nghĩa là biến tập tin có tên LST. Biến này đ−ợc đặt trong đơn vị ch−ơng trình PRINTER.TPU, vì vậy cần khai báo unit Uses PRINTER sau đó có thể sử dụng các thủ tục thủ tục Write(LST,...), Writeln(LST,...). Ví dụ 20. Ch−ơng trình sau in tập tin VanBan.txt ra máy in. Program In_File; Uses Printer; Var F:Text; Dong:String[80]; Begin Assign(F,‘Vaban.txt’); Reset(F); While Not Eof(F) Do Begin Readln(F,dong); Writeln(Lst,dong); End; Close(F); Writeln; End. 96 Câu hỏi – Bài tập Ch−ơng 9 1. Viết ch−ơng trình quản lí điểm của mỗi lớp học gồm các công việc sau: – Nhập hồ sơ của mỗi học sinh gồm có họ tên, năm sinh, điểm trung bình học kì I, điểm trung bình học kì II. – In danh sách các học sinh của lớp có điểm trung bình toàn năm từ 5 điểm trở lên và theo thứ tự giảm dần của điểm trung bình toàn năm. – In danh sách các học sinh phải thi lại (điểm trung bình toàn năm d−ới 5) theo thứ tự abc của tên. – In bảng thống kê tần suất (số lần xuất hiện) của các loại điểm trung bình toàn năm. 2. Viết ch−ơng trình in ra phiếu thanh toán tiền thuê máy tính theo mẫu sau: Phiếu thanh toán tiền thuê máy tính Họ và tên ng−ời sử dụng: Đơn vị công tác: Ngày thuê máy: Từ giờ: đến giờ: Tổng số giờ thuê máy: Số tiền phải trả: Thủ quỹ Các số liệu nhập vào từ bàn phím. Tiền 1 giờ thuê máy là 2000 đồng. Cuối cùng in ra bảng tổng kết ngày có dạng: Thống kê tiền thuê máy Ngày tháng năm STT Họ và tên Đơn vị Số giờ Số tiền 1 2 ... Tổng cộng: Thủ quỹ 97 3. Viết ch−ơng trình quản lí điểm thi học phần của sinh viên bao gồm các tr−ờng sau : Họ tên, Điểm Tin, Điểm Ngoại Ngữ, Điểm trung bình, Xếp loại. Thực hiện các công việc sau: a) Nhập vào danh sách sinh viên của một lớp (không quá 30 ng−ời) : Họ tên, Điểm Tin, Điểm Ngoại ngữ. b) Tính điểm trung bình và xếp loại cho từng sinh viên. c) In ra màn hình danh sách sinh viên của lớp đó theo dạng sau: Họ tên Điểm Điểm Điểm Xếp loại tin Ngoại ngữ Trung bình Trần Văn An 8 9 8.5 Giỏi Lê Thị Bích 7 5 6.0 T.Bình ... ... ... ... ... d) In ra màn hình danh sách các sinh viên phải thi lại (nợ một trong hai môn). e) In ra danh sách những sinh viên xếp loại Giỏi. f) Tìm những sinh viên có điểm trung bình cao nhất lớp. g) Sắp xếp lại danh sách sinh viên theo thứ tự Alphabet. h) Sắp xếp lại danh sách sinh viên theo thứ tự giảm dần của điểm trung bình. 4. Viết ch−ơng trình quản lí sách ở th− viện gồm các tr−ờng sau : Mã số sách, Nhan đề, Tên tác giả, Nhà xuất bản, Năm xuất bản. a) Nhập vào kho sách của th− viện (gồm tất cả các tr−ờng). b) Tìm một cuốn sách có mã số đ−ợc nhập vào từ bàn phím. c) Tìm tất cả các cuốn sách có cùng tác giả. d) Lọc ra các cuốn sách đ−ợc xuất bản trong cùng một năm nào đó. e) Tìm các cuốn sách mà Nhan đề có chứa từ TIN HOC. 5. Viết ch−ơng trình hiển thị nội dung của một file văn bản đã có trên đĩa (Lệnh TYPE). 6. Viết ch−ơng trình nối 2 file văn bản thành một file thứ 3 (Lệnh COPY dạng 2). 7. Viết ch−ơng trình đếm số dòng có trong một file văn bản. 8. Viết ch−ơng trình đếm số từ có trong một file văn bản 9. Cho 2 file số nguyên đã có thứ tự tăng dần. Hãy nối 2 file đó lại với nhau sao cho file mới vẫn có thứ tự tăng dần. 2 n 10. Cho đa thức P(x) = a0 + a1x + a2x + ... + anx , 98 trong đó n là bậc của đa thức và a0, a1, ... , an là các hệ số của đa thức đ−ợc l−u trong một file văn bản với quy −ớc sau: – Dòng đầu của file văn bản chứa bậc của đa thức và giá trị của x. – Dòng tiếp theo chứa các hệ số của đa thức. Chẳng hạn, P(x) = 3 + 2x – 5x2 + 4x3 , x = 2.5 sẽ đ−ợc l−u trong file văn bản nh− nhau: 3 2.5 3 2 –5 4 Viết ch−ơng trình đọc file văn bản trên để lấy các số liệu rồi tính giá trị của đa thức. 11. Viết ch−ơng trình quản lí sinh viên (dùng dữ liệu kiểu File để l−u trữ) gồm các công việc chính sau: – Nhập vào danh sách, l−u vào File. – Bổ sung một số sinh viên mới. – Sửa đổi một số dữ liệu (Nếu dữ liệu trong File ch−a chính xác). – Đọc danh sách sinh viên l−u vào bộ nhớ (l−u vào Mảng). – Sắp xếp lại danh sách sinh viên theo thứ tự Alphabet. – Tính toán điểm, xếp loại cho từng sinh viên. – L−u danh sách từ bộ nhớ vào đĩa. 99 Ch−ơng 10 Kiểu con trỏ và biến động Khi sử dụng mảng để l−u trữ danh sách có nhiều phần tử dữ liệu th−ờng xảy ra một trong hai hiện t−ợng sau : – Khai báo thiếu, có nghĩa là không gian nhớ không đủ để bổ sung phần tử vào mảng và do đó ch−ơng trình không tiếp tục thực hiện đ−ợc. – Khai báo thừa, tức là không gian nhớ dành cho mảng quá lớn so với yêu cầu dẫn đến lãng phí bộ nhớ. Để khắc phục những nh−ợc điểm này, Turbo Pascal cho phép dùng biến động (dynamic variable). Các biến này đ−ợc l−u trữ trong vùng HEAP (danh sách các từ máy) khi cần chúng có thể tạo ra để chứa dữ liệu, khi không cần có thể xoá đi để giải phóng bộ nhớ. Do vậy mà số biến này hoàn toàn không đ−ợc xác định từ tr−ớc. Biến động có tên và do con trỏ quản lí. 10.1. Biến con trỏ Biến con trỏ (Pointer Variable) là một loại biến đặc biệt có kích th−ớc 2 byte, không dùng để chứa dữ liệu, mà dùng để chứa địa chỉ của các biến động. 10.1.1. Khai báo biến con trỏ (Pointer) Trong Turbo Pascal, biến kiểu con trỏ đ−ợc định nghĩa nh− sau: TYPE = ^; trong đó là tên biến dùng để kí hiệu một kiểu con trỏ, là một kiểu nào đó. Thông th−ờng là kiểu bản ghi có chứa một vài tr−ờng có kiểu con trỏ. Để mô tả biến kiểu con trỏ ta có thể sử dụng tên đã định nghĩa hoặc mô tả thông qua định nghĩa trực tiếp. Chẳng hạn, ta có thể mô tả biến trỏ Ptr nh− sau: Var Ptr : ; Hoặc Var Ptr : ^; Để thâm nhập vào biến động có địa chỉ nằm trong biến con trỏ Ptr ta dùng kí hiệu Ptr^. Ví dụ 1. Sau đây là một vài định nghĩa kiểu con trỏ và mô tả biến trỏ. Type 100 Danh_sach=^Nhansu; Nhansu = Record Hoten: String[30]; Ngaysinh: String[8]; Diachi: String[40] Luong: Real; Tiep: Danhsach; End; Var ds1, ds2: Danh_sach; 10.1.2. Các thao tác đối với con trỏ (Pointer) a. Phép gán (:=) Hai biến cùng một kiểu con trỏ có thể gán cho nhau. Chẳng hạn, với mô tả : Var P, Q : ^ Byte; Ta có thể thực hiện phép gán : P := Q; b. So sánh hai con trỏ cùng kiểu Với dữ liệu kiểu con trỏ, chúng ta không thể thực hiện các phép toán so sánh: , = mà chỉ có thể so sánh = (bằng nhau) và so sánh (khác nhau). c. Hằng con trỏ NIL NIL là một giá trị hằng đặc biệt dành cho các biến con trỏ để báo con trỏ không trỏ vào đâu cả. Ta có thể gán NIL cho bất kì biến con trỏ nào. Chẳng hạn khi gán P:=NIL thì P không trỏ đến dữ liệu nào cả. 10.2. Biến động (Dynamic Variable) 10.2.1. Cấp phát vùng nhớ cho biến động Để cấp phát vùng nhớ cho các biến động do con trỏ P trỏ tới ta dùng thủ tục NEW nh− sau: NEW(P); Thực chất đây là thủ tục tạo ra một vùng nhớ có kiểu và kích th−ớc do P quy định, h−ớng con trỏ P tới vùng biến động trên. Nếu trong một ch−ơng trình ta dùng n lần NEW(P) liên tục thì cuối cùng ta có n biến động, song con trỏ P sẽ chỉ vào biến động đ−ợc tạo ra lần cuối cùng. Ví dụ 2. Nếu chúng ta có dãy lệnh: NEW(P); 101 P^.Ho_Ten:= ‘Nguyen Mot’; P^.dtb:=1 ; New(P); P^.Ho_Ten:= ‘Le Hai’; P^.dtb:=2; thì sau khi thực hiện dãy lệnh này trong bộ nhớ sẽ xuất hiện hiện t−ợng sau: Nguyen Mot Biến động 1 p Le Hai Biến động 2 đ−ợc tạo ra Tóm lại, sau mỗi lần dùng New(P) thì con trỏ sẽ chứa địa chỉ của P^ vừa đ−ợc tạo ra, còn các biến động đ−ợc tạo ra bằng New(P) tr−ớc đó sẽ không đ−ợc P trỏ vào nữa. Muốn truy nhập vào các biến động đ−ợc tạo ra từ tr−ớc đó, ta phải có biện pháp l−u trữ chúng lại. 10.2.2. Giải phóng hay thu hồi ô nhớ của biến động Khi một biến động không đ−ợc dùng tới nữa trong ch−ơng trình ta có thể thu hồi lại ô nhớ mà nó chiếm dụng để dùng vào việc khác bằng thủ tục DISPOSE. Để giải phóng ô nhớ của biến động P^, ta dùng lệnh : DISPOSE(P); Ví dụ 3. Var P1, P2: ^Integer; Begin New(P1); P1^:=1595; P2:= P1; Writeln(‘Nam sinh’,P2^); Dispose(P2) ; End. 10.2.3. Phân bố bộ nhớ HEAP và STACK HEAP là vùng nhớ mà Turbo Pascal dùng để l−u trữ các biến động mà nó sẽ đ−ợc tạo ra bởi hàm New. Thông th−ờng Turbo Pascal dùng tất cả các vùng nhớ tự do (th−ờng rất lớn) của máy 102 PC cho HEAP. Turbo Pascal quản lí HEAP thông qua con trỏ của HEAP. Con trỏ của HEAP luôn luôn trỏ vào byte (ô nhớ) tự do đầu tiên của vùng ô nhớ còn tự do của HEAP. Mỗi lần gọi hàm New, con trỏ của Heap đ−ợc dịch chuyển về phía đỉnh của vùng ô nhớ tự do một số byte t−ơng ứng với kích th−ớc của biến động mới đ−ợc tạo ra. STACK là vùng nhớ dành cho các biến cục bộ đ−ợc ch−ơng trình con sử dụng. Kích th−ớc mặc định của nó là 10KB. Tuy vậy có thể dùng Memory Size trên bảng chọn Option để thay đổi kích th−ớc dành cho Stack. Hình d−ới đây cho thấy cách bố trí ch−ơng trình, Stack, Heap trong bộ nhớ của máy PC. Bộ nhớ ch−ơng trình và biến tĩnh Con trỏ của Stack ↓ Vùng bộ nhớ Stack Vùng ô nhớ còn tự do Con trỏ của Heap ↑ Heap : vùng ô nhớ dành cho biến động Có hai hàm để kiểm soát HEAP là MemAvail và MaxAvail. Hàm MemAvail cho tổng số byte còn rỗi trên Heap. Hàm MaxAvail cho số byte liên tục lớn nhất còn rỗi trên Heap. Các vùng nhớ còn rỗi trên Heap th−ờng bị phân thành các chuỗi nhỏ do máy cấp phát và giải toả các vùng nhớ trên Heap không theo một trật tự nào. Khi tạo biến cấp phát động trên Heap thì điều cần quan tâm là kích th−ớc của khối chứ không phải là tổng số vùng nhớ còn rỗi trên Heap. Để tránh tràn Heap tr−ớc khi cấp phát bộ nhớ cho một đối t−ợng có kích th−ớc lớn (nh− mảng, mảng bản ghi) ta nên dùng hàm MaxAvail để kiểm tra có đủ bộ nhớ không. 10.2.4. Giải toả vùng Heap Thủ tục Dispose chỉ có tác dụng xoá một biến động. Nhiều khi ta cần giải toả một vùng nhớ đang bị chiếm bởi nhiều biến, thậm chí cần xoá toàn bộ Heap. Để giải quyết yêu cầu đó ta dùng thủ tục Mark và Release. – Thủ tục MARK(); trong đó là một con trỏ dùng nh− để đánh dấu vị trí đầu của vùng ô nhớ cần giải phóng sau này. Thủ tục này sẽ gán giá trị của con trỏ Heap cho . Sau thủ tục Mark, ta có thể dùng một loạt lời gọi hàm New để tạo các biến động khác nhau và chúng sẽ chiếm ô nhớ kể từ vị trí đã đ−ợc đánh dấu. – Thủ tục RELEASE(); 103 Thủ tục này xoá tất cả các biến động đã tạo từ khi đánh dấu bởi Mark. Ví dụ 4. Ch−ơng trình sau đây cho thấy một ứng dụng của các thủ tục Mark và Release. Program Tong; Var PMark : Pointer; Pds : Array[1..20] Of ^Integer; S, i : Integer; Begin {Danh dau vung Heap} Mark(PMark); For i:=1 to 20 Do Begin New(Pds[i]; Readln(Pds[i]^); End; S:=0; For i:=1 to 20 Do S:=S+Pds[i]^; Release(PMark); Write(‘Tong = ’,S); End. 10.2.5. Khai báo các mảng cỡ lớn Khi xử lí các bài toán thực tế, ta th−ờng phải sử dụng các mảng số thực cỡ lớn. Khi dùng lệnh New(P) ta chỉ có thể tạo đ−ợc mảng số thực có độ lớn nhiều nhất là 10922 phần tử (vì mỗi số thực kiểu real chiếm 6 byte bộ nhớ và 64 Kbyte= 65536 byte). Nh− vậy, với bộ nhớ quy −ớc là 640 Kbyte ta chỉ có thể khai báo 9 mảng số thực 10922 phần tử là cùng. Khi những mảng lớn không còn dùng đến nữa ta nên dùng lệnh Dispose(P) để giải phóng vùng nhớ trên Heap nhằm khai báo các mảng lớn khác. 10.3. Danh sách liên kết (Linhked List) Khi muốn lập một danh sách, ví dụ danh sách học viên, mà biết tr−ớc đ−ợc số ng−ời thì ta có thể sử dụng cấu trúc dữ liệu kiểu mảng. Tuy nhiên khi số phần tử của danh sách lại không đ−ợc biết tr−ớc, nếu sử dụng mảng thì bao giờ cũng cho số phần tử cực đại có thể dùng tới để khai báo mảng và nếu ta dùng không hết thì gây ra lãng phí ô nhớ có thể đang thiếu cho việc khác. Nếu ta dùng biến động thì cần đến đâu sẽ tạo ra đến đó. Hoặc nhiều khi ô nhớ bị hạn chế, nên ta không 104 thể đồng thời sử dụng nhiều biến tĩnh cùng một lúc. Do đó, một trong các biện pháp khắc phục là dùng biến con trỏ để xây dựng một danh sách các phần tử móc nối với nhau gọi là danh sách liên kết. 10.3.1. Định nghĩa Danh sách liên kết là một danh sách mà các phần tử đ−ợc nối kết lại với nhau thông qua vùng liên kết của chúng. Một phần tử của danh sách liên kết bao gồm hai vùng chính: Một vùng chứa thông tin gọi là vùng Info, một vùng chứa địa chỉ gọi là vùng liên kết Link. Hình ảnh của một từ máy (hay còn gọi là nut) nh− sau: Info Link Ngoài các phần tử thuộc danh sách liên kết, ta còn dùng một biến chỉ điểm đầu First (kiểu Pointer) chứa địa chỉ của phần tử đầu tiên của danh sách liên kết. Tổ chức của danh sách liên kết nh− sau FIRST → | ↓ | ↓ | ↓ NIL Ví dụ 5. Danh sách học viên có sắp xếp theo thứ tự tăng dần đ−ợc chứa trong một danh sách liên kết nh− sau: Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyễn Châu Ph−ơng 0110 0064 Lê Thị Lan 0096 0096 Võ Thành Lộc 0032 0110 Hà Hải Quân 0000 FIRST 0064 105 a. Loại bỏ một phần tử trong danh sách Để loại bỏ một phần tử trong danh sách ta chỉ cần thay đổi vùng liên kết của phần tử đứng ngay tr−ớc nó. Ví dụ 6. Muốn loại bỏ tên học viên Võ Thành Lộc, ta chỉ cần sửa vùng liên kết của Lê Thị Lan từ 0096 thành 0032 và các vùng liên kết của các phần tử còn lại vẫn giữ nguyên. Kết quả ta có danh sách liên kết mới nh− sau : Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyễn Châu Ph−ơng 0110 0064 Lê Thị Lan 0032 0110 Hà Hải Quân 0000 FIRST 0064 b. Thêm một phần tử mới vào danh sách Để thêm một phần tử mới vào danh sách, ta có thể chứa phần tử này ở một vùng bất kì trong bộ nhớ và cho vùng liên kết của phần tử đứng ngay sau nó. Ví dụ 7. Muốn thêm tên học viên Trần Phúc Quyền vào danh sách, ta sửa vùng liên kết của Hà Hải Quân từ 0000 thành 0200 và gán giá trị vùng liên kết của Trần Phúc Quyền là 0000. Ta có danh sách liên kết nh− sau : 106 Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyên Châu Ph−ơng 0110 0064 Lê Thị Lan 0096 0096 Võ Thành Lộc 0032 0110 Hà Hải Quân 0200 0200 Trần Phúc Quyền 0000 FIRST 0064 Danh sách liên kết có −u điểm: Tốc độ thực hiện các phép toán thêm vào, loại bỏ phần tử nhanh chóng, không phụ thuộc vào số phần tử của danh sách. Nó phù hợp với loại danh sách có nhiều biến động. Nh−ợc điểm : Thêm vào một vùng biến liên kết (tốn thêm bộ nhớ). 10.3.2. Các phép toán trên danh sách liên kết a. Khởi tạo danh sách liên kết Khi khởi tạo danh sách thì danh sách là rỗng, ta cho First là NIL. Giải thuật : First:=NIL; b. Thêm một phần tử vào danh sách liên kết Phần tử mới có địa chỉ là P với nội dung là Newinfor và danh sách sau của phần tử là q. Giải thuật : New(P) p^.info:=NewInfo; p^.Link:=q^.Link; {Tao 1} q^.Link:=p {Tao 2} c. Loại bỏ phần tử trong danh sách liên kết Loại bỏ phần tử có địa chỉ p ngay sau phần tử có địa chỉ q. Giải thuật : p:=q^.Link; If pNIL Then 107 Begin q^.Link:=p^Link; Dispose(p) End. d. Tìm kiếm một phần tử trong danh sách Giả sử danh sách đ−ợc sắp xếp thứ tự tăng dần theo vùng Info. Ta tìm kiếm một phần tử có Info là X. Giải thuật : p:=First; While p NIL Do Begin If p^.Info = X Then {...} ; If p^.Info < X Then p=p^.Link ; If p^.Info > X Then {...} ; End; 10.3.3. Ví dụ về các danh sách liên kết Ch−ơng trình sau đây thực hiện tổ chức danh sách sinh viên và thực hiện một số thao tác trên danh sách. Độc giả có thể tìm thấy các phép xử lí trên danh sách thông qua các thủ tục trong ch−ơng trình. User Crt; Type svPointer=^sinhvien; sinhvien = Record Maso :String[6]; Hoten : String[30]; dtb : real; Next : svPointer; End; 108 Var First, Last, p, q: svPointer; Masv : String[6]; Chon1 : Byte ; Traloi : Char; Procedure Menu(Var cho : Byte); Begin Window(50,14,80,25): Writeln (‘ ’); Writeln (‘ Cac thao tac ’); Writeln (‘ 1. Tao danh sach sinh vien ’); Writeln (‘ 2. Duyet danh sach sinh vien ’); Writeln (‘ 3. Bo sung vao cuoi danh sach ’); Writeln (‘ 4. Loai bo ’); Writeln (‘ 5. Cham dut ’); Writeln (‘ **Chon so: ’); GotoXY(21,8); Readln(Chon); Clrscr; End; { Menu } (*------------------------------------------------------------------*) Procedure Taosd; Var Ptr : svPointer; i:Integer ; Begin First:=NIL; i:=1 ; Repeat Write(i:3,‘>Mã số SV(Enter : Kết thúc):’); 109 Readln(masv); If masv ‘ ’ Then Begin new(ptr); Ptr^.maso:=masv; Write(‘Ho va ten:’ ); Readln(Ptr^.Hoten); Write(‘Diem trung binh:’); Readln(Ptr^.dtb); Ptr^.Next:=NIL; If First =NIL Then First:=Ptr Else Last^.Next:=Ptr; Last:=Ptr; i:=i+1; End; Until masv=‘ ’; End; { Taods } (*-----------------------------------------------------------*) Procedure DuyetDS; Var Ptr :svPointer; i: Integer; Begin Writeln(‘ DANH SACH SINH VIEN ’); Writeln(‘ ==============================’); Writeln(‘ STT Ma so Ho va ten DTB’); Writeln(‘ ==============================’); i:=1; Ptr :=First; While PtrNIL Do 110 Begin Writeln(i:3,’ ‘,Ptr^.maso:5,’ ‘,Ptr^.hoten:25,’ ‘,Ptr^.dtb:5:2); Ptr:=Ptr^.Next; i:=i+1; End; End; { DuyetDS } (*---------------------------------------------------------------*) Procedure Themsv; Var Ptr:Pointer; Begin New(Ptr); Writeln(‘Nhap thong tin mot sinh vien moi’); Write(‘Mã số:’); Readln(Ptr^.maso); Write(‘Họ tên:’); Readln(Ptr^.hoten); Write(‘Điểm TB:’); Readln(Ptr^.dtb); Ptr^.Next:=NIL; Last^.Next:=Ptr; Last :=Ptr; End; { ThemSV } (*--------------------------------------------------------------*) Procedure XoaSV; Var Timco: Boolean; Begin Write(‘Ma so sinh vien can loai khoi danh sach:’); Readln(masv); p:=First; If p NIL Then Begin Timco:=False; While(pNIL) And Not Timco Do 111 If p^.maso=masv Then Timco:=True Else Begin q:=p; p:=p^.Next; End; If Timco Then Begin If p=First Then First:=p^.Next Else q^.Next=p^.Next; If p^.Next=NIL Then Last :=q; Dispose(p); End; End; End; { Xoa SV } (*-----------------------------------------------------------*) Begin Clrscr; Writeln(‘ VI DU DANH SACH LIEN KET ‘); Writeln(‘ ==========================’); Repeat Menu(chon1); Case chon1 Of 1: TaoDS; 2: DuyetDS 3: Begin Repeat Themsv ; Write(‘Co tiep tuc khong (C/K) ?:’); Readln(Traloi); Until Upcase(Traloi)=’K’; 112 End; 4: Begin Repeat XoaSV; Write(‘Co tiep tuc nua khong (C/K)? :’); Readln(Traloi); Until Upcase (Traloi)=‘K’; End; End; { Of Case } Until chon1 = 5; End. Câu hỏi – Bài tập Ch−ơng 10 1. Sử dụng hàm Radomize (Hàm khởi tạo bộ nhớ ngẫu nhiên) và hàm Random (Hàm tạo một số ngẫu nhiên trên đoạn [0,1]) để tạo một mảng ngẫu nhiên gồm 10000 phần tử. 2. Lập ch−ơng trình nhân hai ma trận A(m,n) và B(n,p) để đ−ợc ma trận tích C(m,p). Các mảng A,B,C đều khai báo d−ới dạng biến con trỏ. 3. Viết ch−ơng trình tạo một danh sách liên kết chứa các số nguyên nhập vào từ bàn phím. Từ đó viết thuật toán : a) Đếm xem danh sách có bao nhiêu nút. b) Tính giá trị trung bình của các phần tử trong danh sách. c) Xác định nút cuối cùng của danh sách đó. d) Xác định nút có giá trị lớn nhất của danh sách đó. e) Xác định nút có giá trị âm đầu tiên của danh sách đó (nếu có). f) Chèn một số nguyên X vào sau nút thứ n trong danh sách. g) Xoá 1 phần tử n trong danh sách, n là số nguyên cho tr−ớc. 4. Viết ch−ơng trình nhập vào một dãy số thực có số phần tử tuỳ ý và sắp xếp dãy số đó theo thứ tự tăng dần. 5. Viết ch−ơng trình nhập vào một dãy số thực đã đ−ợc sắp xếp theo thứ tự tăng dần (số phần tử tuỳ ý) và một số thực X. Viết ch−ơng trình chèn số X vào danh sách sao cho dãy số mới cũng có thứ tự tăng dần. 113 6. Viết ch−ơng trình nhập vào một danh sách các sinh viên (số sinh viên tuỳ ý), mỗi sinh viên có 2 tr−ờng : họ tên, tuổi. In ra danh sách đó theo thứ tự ng−ợc lại. 7. Hãy lập ch−ơng trình đọc vào hai dãy số và tổ chức chúng thành hai danh sách liên kết. Thực hiện các phép xử lí sau đây trên hai danh sách : a) Phần giao của 2 danh sách. b) Phần hợp của 2 danh sách. c) Hiệu của danh sách thứ nhất và danh sách thứ hai. Ghi chú : không cần phải tạo danh sách mới trong mỗi thuật toán. 8. Viết ch−ơng trình cho phép nhập vào 2 dãy số tăng dần và l−u vào 2 danh sách liên kết, trộn 2 danh sách trên bằng cách tạo ra một danh sách mới sao cho dãy số hợp thành cũng tăng dần. 9. Viết ch−ơng trình tạo ra 2 danh sách liên kết (tuỳ ý) và nối 2 danh sách đó lại thành 1 danh sách. 10. Viết ch−ơng trình nhập vào một dãy số và l−u trữ trong một danh sách liên kết sau đó xác định xem các phần tử danh sách có giá trị tăng dần hay không. 11. Viết ch−ơng trình để biểu diễn một số nguyên lớn (Ví dụ : 1234567891234567) thành một danh sách tuyến tính động. 12. Viết ch−ơng trình tính tổng của 2 số nguyên có độ lớn tuỳ ý. 13. Dùng cấu trúc dữ liệu để thực hiện tính n! mà không dùng đệ quy. 14. Một đa thức đã cho có thể đ−ợc biểu diễn d−ới dạng một danh sách tuyến tính động, trong đó mỗi nút của danh sách gồm 2 tr−ờng : * Tr−ờng chứa hệ số ai. * Tr−ờng chứa số mũ i (ai 0, ∀i). Hãy viết ch−ơng trình : a) Nhập vào 2 đa thức. b) Cộng 2 đa thức đó. c) Tính f(x) với x là 1 số cho tr−ớc. 114 Chịu trách nhiệm nội dung: Ts. Nguyễn văn hòa Biên tập: Tổ công nghệ thông tin Phòng khảo thí - đảm bảo chất l−ợng giáo dục Đơn vị phát hành: trung tâm đào tạo từ xa - đại học huế 115