Chủ Nhật, 24 tháng 3, 2013

Xương Tàn Hoang Đảo


Ta không ta, lòng ta khơi động nữa 
Muốn lửa tình tắt lịm kể từ đây 
Tháng với năm đừng xua đuổi ngày dài 
Ong bướm cũ đừng vui đùa trước cửa 

Ta những muốn hè về soi đỏ lửa 
Cho nhân gian, cho vạn vật trên đời 
Hè chớ về gieo rắc nỗi đơn côi 
Cho nhân thế buồn bởi sầu ly tán 

Cho ta xin một bình minh đầy ánh sáng 
Với nắng hồng trinh tiết của không gian 
Đừng sớm đi, cũng đừng đến muộn màng 
Cho tạo hóa xoay tròn theo cuộc sống 

Cho ta được bình an 
Ta muốn được bình an 
Ôi ! Tâm hồn ta là dãy núi lang tràn 
Sầu và mơ, đau buồn cao bất tận. 

Bay đi nhé ! Sầu tình cùng oán hận 
Đời đế vương hãy vẫn thế mà thôi 
Chán quá rồi cuộc tình quá tanh hôi 
Ân ái cũ nghĩ nhiều ta muốn mửa 

Cho ta xin được làm hoang đảo nhỏ. 
Chìm giữa đại dương cho mặc sóng gào 
Để muôn đời và mãi mãi về sau 
Nắm xương trắng của Hoàng ta tinh khiết. 

Nguyễn Ngọc Hoàng 
(Paris, thu 2000)

Hận đời

Đã từng đau cuộc đời cay đắng
Đã từng chửi cái thói đời trớ trêu
Đã nhiều lần ta cứ thế làm liều
Hận cuộc đời đổi thay màu đen bạc
Trên cánh tay gầy xương tàn xơ xác
Ta xăm đầy những vết hận thời gian

Rồi cũng qua, cũng đi những tháng ngày bặm bụi
Ngước nhìn đời có thấy lắm thương đau ?
Cánh tay gầy đâu phải đời đã chém
Chỉ do mình do ta chém đó thôi
Những vết xăm mang hai chữ Hận đời
Âu cũng là một thời ta nông nổi

Vinh Nhuc


Cái sân đình nơi Hạng Vũ ngày xưa
nâng cái đỉnh đi ba vòng không thấm
nói thật mất lòng, cổ nhân đừng giận
cái sân kia rộng lắm chỉ hơn sào
cái đỉnh nghìn cân ắt thiên hạ thêm vào
để xếp Ông vô hàng hữu dõng !
Tôi sức lực nhằm chi so Thánh Gióng
mà thân na cả một phận người
đã đi đến vòng thứ sáu mươi
trên cuộc đời mà Phật kêu là bể khổ
thì cái sân đình làng Ông xem ra quá nhỏ
và ba vòng sao sánh được sáu mươi !
Ông hỏng cuộc Bá, Vương;
tôi lỡ dở cuộc Người
há chẳng phải vô mưu dù hữu dõng
thiên hạ trước sau bên khinh bên trọng
hẳn Ông vui khi biết được điều này :
- tên Ông được quàng trong sử sách,- Vinh thay !
Thử hỏi như tôi ai người nghĩ tới
tôi mai một ngay khi đương sống gởi
thì mong chi để tiếng buổi thác về !
sáu mươi vòng đời xác mỏi, hồn ê
đời sắp sụm không làm nên trò trống
cuộc Bá, cuộc Người của Ông, tôi đều hỏng
nghĩ cho cùng chẳng tại vô mưu đâu !
Nói, không phải là nói an ủi nhau !

Chủ Nhật, 3 tháng 3, 2013

Đảo ngược danh sách



procedure dao_danh_sach ( var L: DS );
var L1, p , q: DS;
begin
{Buoc 1: kiem tra cac dieu kien truoc khi dao ds}
{neu L la ds rong thi ket thuc thu tuc vi khong hop le}
if L=nil then exit;
{neu ds L chi co duy nhat 1 nut thi ket thuc thu tuc vi khong the dao nguoc duoc 1 nut}
if L^.link = nil then exit;
{buoc 2: tien hanh dao nguoc ds L}
{neu L chi co 2 nut thi qua don gian}
L1:= L^.link;
if L1^.link=nil then
begin
L1^.link:= L;
L^.link:= nil;
L:= L1;
exit; {da dao xong va ket thuc thu tuc}
end;
{den day chac chan ds L co nhieu hon 2 nut, giai thuat nhu sau}
p:= L1^.link;
q:= L;
L^.link:= nil;
while p<>nil do
begin
L1^.link:= q; {nut L1 tro den nut q dung truoc no, tuc la tro theo chieu nguoc lai}
q:= L1;
L1:= p;
p:=p^.link;
end; 
L1^.link:= q;
L:=L1;
end;

Lý thuyết và bài tập pascal (Chương 9)



Lý thuyết và bài tập pascal (Chương 9)


Chương 9
DỮ LIỆU KIỂU CON TRỎ
I. KHAI BÁO
     Type
          <Tên kiểu con trỏ> = ^ <Kiểu của biến động>;
Var
          <Tên biến>:<Tên kiểu con trỏ>;
Ví dụ 1:
     Type
          TroNguyen : ^integer;
     Var
          p, q: TroNguyen;
Sau khai báo này các biến p và q là các biến con trỏ có thể trỏ đến các biến động có kiểu integer. Chương trình sẽ cấp phát 4 byte cho mỗi biến con trỏ. Còn vùng nhớ của các biến động chưa được cấp phát.
Ví dụ 2:
     Type
          TroSv = ^ Sinhvien;
          Sinhvien = Record
                                 Hoten: String[20];
                                 Diem: real;
                                 Tiep: TroSv;
                            End;
     Var
          p: TroSv;
     Trong ví dụ này, p là biến trỏ có thể trỏ đến các bản ghi có kiểu Sinhvien, trong bản ghi này lại có trường Tiep là một biến trỏ có thể trỏ đến biến động khác cũng có kiểu Sinhvien.
II. LÀM VIỆC VỚI BIẾN ĐỘNG
2.1. Cấp phát vùng nhớ
Dùng thủ tục New theo cú pháp:
          New(<biến trỏ>);
Phép gán giữa hai biến trỏ được thực hiện nếu chúng có cùng kiểu. Sau phép gán p:=q; các con trỏ p và q cùng trỏ đến một địa chỉ. Do đó mọi thay đổi của p^ cũng làm thay đổi q^. Như vậy, cần phân biệt hai phép gán p:=q và p^:=q^. Ngoài ra, các con trỏ cùng kiểu có thể được so sánh với nhau bằng các toán tử quan hệ = và <>.
Turbo Pascal cũng khai báo sẵn một con trỏ không trỏ tới một biến động nào gọi là con trỏ Nil. Giá trị con trỏ Nil là tương hợp với mọi kiểu con trỏ. Nil có thể được gán cho biến con trỏ để chỉ ra rằng con trỏ ấy hiện không được sử dụng. Chúng ta cũng có thể sử dụng Nil trong các phép so sánh.
2.2. Giải phóng vùng nhớ
     Dùng thủ tục Dispose(p);
     Trong đó p là một biến con trỏ. Thủ tục Dispose cho phép trả lại bộ nhớ động đã được cấp phát bởi thủ tục New.
III. DANH SÁCH ĐỘNG
3.1. Khái niệm
     Chúng ta đã từng làm quen với kiểu mảng, lưu danh sách gồm nhiều thành phần có cùng kiểu. Mỗi thành phần là một biến tĩnh và số lượng thành phần của danh sách là cố định. Ở đây chúng ta đề cập đến một dạng danh sách động theo nghĩa: mỗi thành phần là một biến động và số lượng thành phần của danh sách có thể thay đổi. Mỗi biến động trong danh sách được gọi là một nút.
3.2. Khai báo
     Để khai báo một danh sách động trước hết ta khai báo kiểu của mỗi nút trong danh sách.
Type <Trỏ nút> = ^ <Nút>;
  <Nút> = Record
                     Data: DataType;
                     Next: <Trỏ Nút>;
                   End;
Var    First: <Trỏ Nút>;
     First là địa chỉ của nút đầu tiên trong danh sách, dựa vào trường Tiep của nút này ta bết được địa chỉ của nút thứ hai, cứ như vậy ta biết được địa chỉ của tất cả các nút trong danh sách. Danh sách dạng này được gọi là danh sách liên kết đơn.
3.3. Các thao tác thường gặp trên danh sách liên kết đơn
Trong phần này chúng ta giả thiết rằng mỗi nút trong danh sách có hai trường: trường Info (lưu nội dung của biến động) và trường Next (lưu địa chỉ của nút tiếp theo). ta có khai báo danh sách như sau
Type TroNut = ^Nut;
     Nut = Record
                   Info: data; {data là kiểu dữ liệu đã định nghĩa trước}
                   Next: TroNut;
  End;
     Var First:TroNut;
3.3.1. Khởi tạo danh sách
     First:=Nil;
3.3.2. Bổ sung một nút vào đầu danh sách
{1. Tạo ra nút mới}
New(p);
p^.Info:=X;
{2. Bổ sung vào đầu danh sách}
     p^.Next:=First;
     First:=p;
3.3.3. Bổ sung một nút vào cuối danh sách
Xuất phát danh sách không có nút nào cả. Nút mới thêm vào sẽ nằm cuối danh sách. Khi đó ta cần hai biến con trỏ First và Last lần lượt trỏ đến các nút đầu và cuối danh sách.
Procedure Khoitao;
var p: TroNut;
Begin
     First:= nil; Last:= nil;
     While <còn thêm nút mới vào danh sách> do
          Begin   
New(p);
              Readln(p^.Info);
              p^.Next:= Nil;
              If First = Nil then
                        First:= p
              Else
                        Last^.next:= p;
              Last:= p;
          End;
End;
3.3.4. Duyệt danh sách
Duyệt danh sách là thăm và xử lý từng nút trong danh sách.
Procedure Duyet;
Var p: Tronut;
Begin
  p:= First;
  While p <> nil do
       Begin
            <Xử lý p>;
            p:= p^.Next; {duyệt qua nút tiếp theo}
       End;
End;
3.3.5. Bổ sung một nút vào sau nút được trỏ bởi p
Thủ tục sau thực hiện việc bổ sung một nút có nội dung x vào sau nút được trỏ bởi p.
     Procedure Bosung(p,x);
     Var    q: TroNut;
     Begin
          New(q);
          q^.info:=x;
          if first = nil then
              begin
                   q^.next := nil;    
first := q;
              end
          else
              begin
                   q^.next:= p^.next;
p^.next:= q;
               end;
     End;
3.3.6. Xoá một nút khỏi danh sách
Thủ tục sau thực hiện việc xóa một nút trỏ bởi p ra khỏi danh sách.
     Procedure Xoa(p);
     Var    q: TroNut;
     Begin
          if First = nil then
              exit;
          if p = First then
              First := First^.next
          else
              begin
                   q:= First;
                   While q^.next <> p do
                        q:= q^.next;
                   q^.next:= p^.next;
              end;
          Dispose(p);
     End;
BÀI TẬP MẪU
Bài tập 9.1: Trong các bài tập từ 9.1 đến 9.4, dùng danh sách liên kết đơn lưu một dãy số nguyên. Nút đầu tiên trong danh sách được trỏ bởi First. Cho khai báo mỗi nút trong danh sách như sau:
Type TroNut = ^ Nut;
     Nfut = Record
          GiaTri: Integer;
          Tiep: TroNut;
          End;
Var    First: TroNut;
Viết chương trình thực hiện các yêu cầu sau:
a. Nhập dãy các số nguyên và lưu vào danh sách có nút đầu trỏ bởi First, quá trình nhập dừng khi dữ liệu đưa vào không phải là số nguyên.
b. In giá trị các nút lớn hơn 0.
Program Vi_du_1;
Type TroNut = ^ Nut;
    Nut = Record
        GiaTri: Integer;
        Tiep: TroNut;
        End;
Var  First: TroNut;
    p: pointer;
Procedure Nhap;
Var
    n:integer;
    kq:boolean;
    last,p: tronut;
begin
    first:=nil;
    last:= nil;
    repeat
        write(‘Nhap gia tri mot nut – Ket thuc bang ky tu Q: ‘);
        {$I-}
        readln(n);
        {$I+}
        kq:= IOResult=0;
        if kq then
           begin
               new(p);
               p^.Giatri:=n;
               p^.Tiep:=nil;
               if first = nil then
                   first:= p;
               else
                   last^.Tiep:= p;
               last:=p;    
           end;
    until not kq;
end;
Procedure In_so_duong;
Var
    p: Tronut;
begin
    p:= first;
    while p <> nil do
        begin
           if p^.Giatri > 0 then
               write(p^.Giatri:8);
            p:=p^.Tiep;
        end;
end;
Begin
    Mark(p);
    Nhap;
    In_so_duong;
    Release(p);
    Readln;
End.
Bài tập 9.2: Viết thủ tục đếm số nút có giá trị lớn hơn 0 và tính giá trị trung bình cộng của các nút đó.
Procedure Nut_duong(var dem: word; tb:real);
Var
    p: Tronut;
    tong:longint;
begin
    dem:=0;
    tong:=0;
    p:= first;
    while p <> nil do
        begin
           if p^.Giatri > 0 then
               begin
                   inc(dem);
                   tong:=tong+p^.Giatri;   
               end;
           p:=p^.tiep;
    if dem = 0 then
        tb:=0
    else
        tb:= tong /dem;
end;
Bài tập 9.3: Giả sử dãy giá trị các nút trong danh sách đã được sắp tăng dần. Viết các thủ tục và hàm sau:
     aProcedure Insert(var first: TroNut; m: integer) thực hiện việc bổ sung một nút vào danh sách sao cho tính tăng dần được bảo toàn.
Procedure Insert(var first: TroNut; m: integer);
Var
    p,q: Tronut;
begin
    new(p);
    p^.Giatri:= m;
    if (first = nil) or (first^.Giatri < m ) then
        begin
           p^.Tiep:=nil;
           first:= p;
        end
    else
        begin
           q:= first;
           while (q^.Tiep <> nil) and ((q^.Tiep)^.Giatri < m) do
               q:= q^.Tiep;
           p^.Tiep:= q^.tiep;
           q^.Tiep:= p;
        end;
end;
     b. Procedure InitList thực hiện việc tạo danh sách có tính chất trên bằng cách nhập dữ liệu từ bàn phím và quá trinh nhập dừng khi nhấn phím ESC (yêu cầu: sử dụng thủ tục Insert).
Procedure InitList;
Var
    m: integer;
Begin
    first:= nil;
    repeat
        write(‘Nhap gia tri cua mot nut: ‘);
        readln(m);
        insert(first,m);
    until readkey = #27;
end;
     c. Procedure List(First: TroNut) in dãy giá trị các nút trong danh sách.
Procedure List(First: Tronut);
Var
    p:Tronut;
begin
    p:= first;
    while p <> nil do
        begin
           write(p^.Giatri);
           p:=p^.Tiep;
        end;
end;
     d. Procedure DeleteZero( Var First: TroNut) thực hiện việc xoá tất cả các nút có giá trị 0 trong danh sách.
Procedure DeleteZero(Var First: TroNut);
var  
    p,q: Tronut;
begin
    p:= first;
    while (p <> nil) and (p^.Giatri < 0) do
        begin  
           q:= p;             
p:= p^.Tiep;
        end;
    while (p <> nil) and (p^.Giatri = 0) do
        begin
           q^.Tiep:= p^.Tiep;
           dispose(p);
           p:= q^.Tiep;
        end;
end;
     e. Function TroMax(First: TroNut): TroNut trả về địa chỉ của nút đầu tiên đạt giá trị lớn nhất (tính từ đầu danh sách, nếu có, ngược lại hàm trả về giá trị Nil).
Function Tromax(First: TroNut);
var
    p.q: Tronut;
    m:integer;
begin
    if first = nil then
        TroMax:= nil
    else
        begin
           p:= first;
m:= p^.Giatri;
           q:= p^.Tiep;
           while (q <> nil) do
               begin          
if q^.Giatri > m then
                   begin
                       p:= q;
                       m:= p^.Giatri;
                   end;               
q:= q^.Tiep;
               end;
           TroMax:=p;  
  end;
end;
Bài tập 9.4: Giả sử danh sách khác rỗng. Viết các thủ tục và hàm sau:
     a. Function GiaTriMax(First: TroNut): integer trả về giá trị lớn nhất của nút có trong danh sách.
Function GiaTriMax(First: TroNut): integer;
var
    m: integer;
    p, q: Tronut;
begin
    p:= first;
    m:= p^.Giatri;
    q:= p^.Tiep;
    while q<> nil do
        begin
           if q^.Giatri > m then
               m:=q^.Giatri;
           q:= q^.Tiep;
    GiaTriMax:= m;
end;
b. Function GiaTriMin(First: TroNut): Integer trả về giá trị nhỏ nhất của nút có trong danh sách.
Function GiaTriMax(First: TroNut): integer;
var
    m: integer;
    p,q: Tronut;
begin
    p:= first;
    m:= p^.Giatri;
    q:= p^.Tiep;
    while q<> nil do
        begin
           if q^.Giatri < m then
               m:=q^.Giatri;
           q:= q^.Tiep;
    GiaTriMin:= m;
end;
Bài tập 9.5: Cho danh sách liên kết đơn có nút đầu trỏ bởi First, được khai báo như sau
Type
            TroNut = ^nut;
            Nut = Record
                        Info: real;
                        Next: TroNut;
                   End;
Var
            First: Tronut;
Viết các thủ tục và hàm sau:
     a. Function Search(First: TroNut; k: word): TroNut trả về địa chỉ của nút thứ k (nếu có, ngược lại, hàm trả về giá trị Nil).
Function Search(First: TroNut; k: word): Tronut;
Var
         d: word;
         p: Tronut;
Begin
         d:=0;
         p:=first;
         while (p <> nil) do
           begin
               inc(d);
               if d = k then
                   break;
               p:= p^.next;
         end;
         Search:= p;
End;
     b. Procedure Delete_K(Var First: TroNut; k: word) thực hiện việc xoá nút thứ k trong danh sách (nếu có).
Procedure Delete_K(Var first: Tronut; k:word);
var
         d: word;
         p,q: Tronut;
begin
         d:=1;
         p:= first;
         while (p<> nil) and (d <k) do
               begin
                   q:= p;
                   p:= p^.Next;
                   inc(d);
               end;
         if p <> nil then
               begin
                   if  p = first then
                       first:= first^.next
                   else
                       q^.next:= p^.next;
                   dispose(p);
               end;
end;  
     c. Procedure DeleteList thực hiện việc xoá tất cả các nút trong danh sách.
Procedure DeleteList;
var
    p: Tronut;
begin
    while first <> nil do
        begin
           p:= first;
           first:= first^.next;
           dispose(p);
        end;
end;
Bài tập 9.6: Cho file văn bản có tên NGUYEN.INP lưu các số nguyên, giữa các số trong file cách nhau một ký tự trắng hoặc dấu xuống dòng. Viết chương trình thực hiện các yêu cầu sau:
a. Lấy dữ liệu từ file NGUYEN.INP và lưu vào danh sách liên kết đơn có nút đầu trỏ bởi First.
b. Tính tổng giá trị các nút, tổng giá trị các nút dương, tổng giá trị các nút âm, số nút có giá trị âm, số nút có giá trị dương. Các kết quả tính đươc sẽ lưu vào file văn bản có tên KETQUA.OUT, dòng đầu chứa 3 giá tri tổng, dòng thứ hai chứa hai giá trị còn lại.
Program Vi_du_6;
type
    Contro = ^ Nut;
    Nut = Record
           info: integer;
           next: Contro;
        end;
var
    first: Contro;
Procedure Lay_du_lieu;
var
    p: Contro;
    so: integer;
    f: text;
Begin
    assign(f, ‘NGUYEN.INP’);
    reset(f);
    first:= nil;
    while not Eof(f) do
        begin      
read(f, so);
new(p);
p^.info:= so;
p^.next:= first;
first:= p;
        end;
    close(f);
End;
Procedure Tinh_toan;
var
    f:text;
    p: Contro;
    T, T_duong, T_am: longint;
    N_duong, N_am: word;
begin
    assign(f,’KETQUA.OUT’);
    rewrite(f);
    p:= first;
    T:= 0;
    T_duong: =0;
    T_am:= 0;
    N_duong:= 0;
    N_am:= 0;
    while p <> nil do
        begin
           T:= T + p^.info;
           if p^.info > 0 then
               begin
                   T_duong:= T_duong + p^.info;
                   inc(N_duong);
               end;
           if p^.info < 0 then
               begin
                   T_am:= T_am + p^.info;
                   inc(N_am);
               end;
           p:= p^.next;
        end;
    writeln(f, T,#32,T_duong,#32,T_am);
    writeln(f,N_duong,#32,N_am);
    close(f);
end;
Begin
    Lay_du_lieu;
    Tinh_toan;
End.
Bài tập 9.7: Người ta lưu thông tin các bệnh nhân của bệnh viện X trong danh sách liên kết đơn có nút đầu trỏ bởi First, mỗi bệnh nhân tương ứng với một nút trong danh sách được khai báo như sau:
Type St20 = String[20];
St5 = String[5];
St2 = String[2];
     TroBN = ^BenhNhan;
BenhNhan =     Record
                   MaBN: St5;        {Mã bệnh nhân}
Hoten: St20;      {Họ tên bệnh nhân}
                   Tuoi: byte;      {Tuổi}
                   Tiep: TroBN;
              End;
Chú ýHai ký tự đầu của mã bệnh nhân là mã của khoa điều trị.
Viết các thủ tục và hàm sau:
a.      Procedure BoSungBN(Var First: TroBN; Bma: St5; Bten: St20; Btuoi: byte)  bổ sung bệnh nhân có mã là Bma, họ tên là Bten, tuổi là Btuoi vào cuối danh sách có nút đầu trỏ bởi First (Lưu ý: Kiểm tra Bma chưa có trong danh sách mới bổ sung).
Procedure BoSungBN(var First: TroBN; Bma: St5; Bten: St20; Btuoi:byte);
var
    p,q: TroBN;
begin
    p:= first;
    while (p <> nil) and (p^.MaBN <> Bma) do
        begin
           q:= p;
           p:= p^.tiep;
        end;
    if p = nil then
        begin
           new(p);
           p^.MaBn:= Bma;
           p^.Hoten:= Bten;
           p^.tuoi:= Btuoi;
           p^.Tiep:= nil;
           if first = nil then
               first:= p
           else
               q^.tiep:= p;
end;
b.      Procedure KhoiTao(Var First: TroBN) nhập dữ liệu cho danh sách có nút đầu trỏ bởi First, quá trình nhập dừng khi mã bệnh nhân đưa vào là xâu rỗng (Yêu cầu sử dụng thủ tục BoSungBN).
Procedure KhoiTao(Var First: TroBN);
var
    bma:St5;
    bten: st20;
    btuoi: byte;
begin
    first:= nil;
    repeat
        write(‘Nhap ma benh nhan: ‘);
  readln(bma);
        if bma <> ‘’ then
           begin
               write(‘Ho ten benh nhan: ‘);
               readln(bten);
         write(‘Tuoi: ‘);
               readln(btuoi);
               BosungBN(first, bma, bten, btuoi);
           end;
    until bma = ‘’;
end;
c.      Function SoBN(First: TroBN; BKhoa: St2): word trả về số lương bệnh nhân điều trị tại khoa có mã BKhoa.
Function SoBN(First: TroBN; BKhoa: St2): word;
Var
    p: TroBN;
    dem:word;
Begin
    dem:= 0;
    p:= first;
    while p <> nil do
        begin
           if copy(p^.MaBN,1,2) = BKhoa then  inc(dem);
           p:= p^.tiep;
        end;
    SoBN:= dem;
End;
d.      Procedure LietKe(First: TroBN; n: byte) in thông tin của các bệnh nhân có tuổi nhỏ hơn hoặc bằng n.
Procedure LietKe(First: TroBN; n: byte);
Var
    p: TroBN;
Begin
    p:= first;
    while p <> nil do
        begin
           with p do
      if tuoi <= n then
             writeln(mabn, #32,hoten, #32, tuoi);
      p:= p^.tiep;
        end;
End;
e.      Procedure XoaBN(Var First: TroBN; Bma: St5) xoá bệnh nhân có mã Bma khỏi danh sách.
Procedure XoaBN(Var First: TroBN; Bma: St5);
Var
    p,q: TroBN;
Begin
    p:= first;
    while (p <> nil) and (p^.MaBN <> Bma) do
        begin
           q:= p;
           p:= p^.tiep;
        end;
    if p <> nil then
        begin
           if p = first then
               first:= first^.tiep
           else
               q^.tiep:= p^.tiep;
           dispose(p);
End;
Bài tập 9.8: Người ta lưu thông tin của mỗi đại lý trong công ty bởi một nút trong danh sách liên kết đơn và được khai báo như sau:
Type St6 = String[6];
     TroDL = ^ DaiLy;
     DaiLy = Record
              SoDT: St6;
              DoanhThu: LongInt;
              Next: TroDL;
          End;
Viết các thủ tục và hàm:
a.      Procedure BoSung(Var First: TroDL; Tel: St6; m: LongInt) để bổ sung một đại lý có số điện thoại Tel và doanh thu là m vào đầu danh sách có nút đầu trỏ bởi First.
Procedure BoSung(Var First: TroDL; Tel: St6; m: LongInt);
Var
    p: TroDL;
Begin
    new(p);
    p^.SoDt:= Tel;
    p^.Doanhthu:= m;
    p^.next:= first;
    first:= p;
End;
b.      Function DThu(First: TroDL; Tel: St6): LongInt trả về doanh thu của đại lý có số điện thoại là Tel, nếu không có đại lý đó thì hàm trả về giá trị 0.
Function DThu(First: TroDL; Tel: St6): LongInt;
Var
    p: TroDL;
Begin
    p:= first;
    while (p <> nil) and (p^.SoDT <> Tel) do
        p:= p^.next;
    if p <> nil then
        Dthu:= p^.doanhthu
    else
        Dthu:= 0;
End;
c.      Function TongDThu(First: TroDL): Real trả về tổng doanh thu của tất cả các đại lý trong công ty.
Function TongDThu(First: TroDL): Real;
Var
    p: TroDl;
    T: real;
Begin
    T:= 0;
    p:= first;
    while p <> nil do
        begin
           T:= T+ p^.Doanhthu;
           p:= p^.next;
        end;
    TongDthu:= T;
End;
d.      Function DemDL(First: TroDL; m: LongInt): Word trả về số đại lý của công ty có doanh thu lớn hơn m.
Function DemDL(First: TroDL; m: LongInt): Word;
Var
    p: TroDL;
    dem: word;
Begin
    dem:= 0; 
p:= first;
    while p <> nil do
        begin
           if p^.Doanhthu > m then
               inc(dem);
           p:= p^.next;
        end;
    DemDL:= dem;
End;
e.      Procedure XoaDL(Var First: TroDL; Tel: St6) xóa đại lý có số điện thoại Tel ra khỏi danh sách.
Procedure XoaDL(Var First: TroDL; Tel: St6);
Var
    p,q: TroDL;
Begin
    p:= first;
    while (p <> nil) and (p^.SoDT <> Tel) do
        begin
           q:= p;
           p:= p^.next;
        end;
    if p <> nil then
        begin
           if p = first then
               first:= first^.next
           else
               q^.next:= p^.next;
           dispose(p);
        end;
End;
BÀI TẬP TỰ GIẢI
Bài tập 9.9Viết một hàm để xác định xem một danh sách liên kết đã cho có thứ tự tăng dần hay không theo 2 cách: Không đệ qui và đệ qui.
Bài tập 9.10: Cho 2 danh sách liên kết đơn đại diện cho 2 tập hợp được trỏ bởi L1 và L2. Viết chương trình để hiển thị:
1.      Phần giao của 2 danh sách trên.
2.      Phần hợp của 2 danh sách trên.
3.      Phần hiệu của 2 danh sách trên.
Bài tập 9.11: Cho 2 danh sách liên kết L1 và L2.
1.      Sắp xếp lại 2 danh sách đó theo thứ tự tăng dần.
2.      Trộn 2 danh sách đó lại thành danh sách L3 sao cho L3 vẫn có thứ tự tăng dần.
Bài tập 9.12: Dùng danh sách móc nối để biểu diễn một đa thức Pn(x) = anxn + an-1xn-1 +...+ a0. Trong đó, mỗi số hạng của đa thức được xác định bởi 2 thành phần: hệ số ai và số mũ i.
     Như vậy, ta có thể xây dựng cấu trúc dữ liệu cho đa thức như sau:
          TYPE    DATHUC = ^SOHANG;
                        SOHANG = Record
                             HeSo: Real;
                             SoMu: Integer;
                             Next: DATHUC;
                        End;
Viết chương trình    thực hiện các công việc sau:
1.      Viết thủ tục nhập vào một đa thức.
2.      Viết thủ tục để sắp xếp lại các số hạng của đa thức theo thứ tự số mũ giảm dần.
3.      Viết thủ tục/hàm để cộng 2 đa thức.
4.      Viết hàm để tính giá trị của đa thức theo giá trị X.
Bài tập 9.13: Cho một file văn bản trong đó có chứa các từ. Các dấu phân cách từ là: ký tự trắng, dấu chấm, dấu phẩy, dấu chấm phẩy, dấu hai chấm, dấu than, dấu hỏi. Mọi từ đều bắt đầu bằng một ký tự trong tập ['A'..'Z'].
1. Viết thủ tục cho phép đọc các từ trong file văn bản đã cho và lưu các từ đó vào mảng các danh sách móc nối:
     TuDien : ARRAY['A'..'Z'] OF DanhSach;
Trong đó kiểu DanhSach được cho như sau:
     TYPE DanhSach = RECORD
                                           Tu : String[10];
                                           Next : DanhSach;
                                      END;
Mỗi danh sách móc nối trong từ điển đều phải được sắp thứ tự (tăng dần), và các từ được lưu trong từ điển phải khác nhau.
2. Viết một thủ tục hiển thị tất cả các từ trong từ điển ra màn hình theo thứ tự tăng dần.
3. Viết một thủ tục bổ sung một từ mới vào từ điển bằng cách đọc từ đó từ bàn phím, tìm nó trong từ điển.
     - Nếu tìm thấy, hiển thị thông báo:"Từ đã có trong từ điển".
     - Nếu không tìm thấy, chèn từ đó vào trong từ điển ở vị trí thích hợp.
Bài tập 9.14: Cho dãy số nguyên sắp theo thứ tự tăng dần và lưu trong một danh sách liên kết đơn có địa chỉ nút đầu danh sách là First.
a.      Viết chương trình xoá tất cả các nút trong danh sách có giá trị 0.
b.      Viết chương trình in ra các giá trị phân biệt của danh sách.
Bài tập 9.15: Cho hai dãy số thực lưu trong hai danh sách liên kết đơn, có địa chỉ của các nút đầu danh sách lần lượt là First1 và First2. Giả sử trong mỗi danh sách giá trị các nút đã được sắp tăng dần. Hãy viết chương trình tạo một danh sách liên kết đơn có nút đầu trỏ bởi List, chứa tất cả các phần tử của hai danh sách trên, danh sách mới này cũng được sắp thứ tự.
Bài tập 9.16: Một công ty du lịch quản lý tất cả các xe ô tô của họ bằng một danh sách liên kết, mỗi nút của danh sách được khai báo như sau:
Type
     TroXe = ^Xe;
     St6 = String[6];
     St20 = String[20];
     Xe = Record
          TaiXe: St20; { họ tên tài xế }
          BienSo: St6; { biển số xe }
          Socho: Byte;  { số chỗ ngồi }
          Tiep: TroXe;
            end;    
Var
     First: TroXe;
a.      Viết thủ tục Procedure Print(First: TroXe; n:byte); in họ tên tài xế, biển số xe của tất cả các xe có n chỗ ngồi được lưu trong danh sách.
b.      Viết hàm Function SoChoNgoi(First: TroXe; Bso: St6); trả về số chỗ của xe có biển số Bso.
Bài tập 9.17: Người ta quản lý các sách trong thư viện bằng một danh sách liên kết, sắp theo thứ tự của mã sách. Mỗi đầu sách tương ứng với một nút trong danh sách có khai báo như sau:
Type
     TroSach = ^Sach;
     St4 = String[4];
     St20 = String[20];
     Sach = Record
              Ma: St4;
              Ten, Tacgia: St20;
              NamXb: word;
              Soluong: Byte;
              Next: TroSach;
          end;
Var
     First: TroSach;
Chú ý: Các đầu sách được săp theo thứ tự mã sách.
a.      Viết thủ tục Procedure CapNhat(Var First: TroSach; Bma:St4; Bten, BTgia: St20; Bnam: word; n: byte); bổ sung vào thư viện đầu sách có mã là Bma, tên sách Bten, tác giả BTgia và số lượng bổ sung là n theo yêu cầu: Nếu đầu sách có mã là Bma đã có trong thư viện thì chỉ tăng số lượng lên n, ngược lại thêm một đầu sách mới vào thư viện với số lượng n và bảo toàn thứ tự của mã sách.
b.      Viết thủ tục Procedure LietKeNam(First: TroSach; Nam: word) in danh sách các đầu sách xuất bản vào năm Nam.
c.      Viết hàm Function So_Dau_Sach(First: TroSach; BTgia: St20) trả về số đầu sách của tác giả BTgia.
d.      Viết thủ tục Procedure LietKeten(First: TroSach; Bten: St20) in danh sách tất cả các đầu sách có tên sách là Bten.
Bài tập 9.18: Một cửa hàng kinh doanh vật liệu xây dựng quản lý lượng hàng tồn kho bằng một danh sách liên kết. Mỗi loại vật liệu tương ứng với một nút trong danh sách và có khai báo như sau:
Type
     St3 = String[3];
     St10 = String[10];
     TroVT = ^Vattu;
     Vattu = Record
              Ma: St3;
              Ten: St10;
              DVTinh: St10;    { đơn vị tính}
              Soluong: word;
              Tiep: TroVattu;
          End;
Var
     First: TroVattu;
a.      Viết thủ tục Procedure XuatKho(Var First: TroVattu; Bma: St3; Bdonvi: St10; n: word); lấy  ra khỏi kho n bdonvi loại vật tư có mã là Bma theo yêu cầu sau:
•        Nếu vật tư có mã Bma không có trong kho thì thông báo kho không có loại vât tư này và kết thúc thực hiện.
•        Ngược lại, kiểm tra Bdonvi có trùng với DVTinh của loại vật tư này không, nếu không trùng thì yêu cầu đổi theo đơn vị tính lưu trong danh sách trước khi thực hiện xuất kho.
•        Nếu số lượng trong kho của vật tư có mã Bma nhỏ hơn n thì đưa ra thông báo và hỏi lại có muốn xuất không, nếu muốn thì xuất với số lượng  bao nhiêu?
•        Sau khi xuất n đơn vị loại vật tư theo yêu cầu, giảm số lượng vật tư trong kho cho phù hợp và nếu số lượng của vật tư này bằng 0 thì xoá nó ra khỏi danh sách.
b.      Viết thủ tục Procedure NhapKho(Var First: TroVattu; Bma: St3; Bten, Bdv: St10; n: word); nhập vào kho n Bdv laọi vật tư có mã Bma theo yêu cầu:
•        Nếu loại vật tư có mã Bma đã có trong kho thì chỉ tăng số lượng vật tư này trong kho, nhớ kiểm tra đơn vị tính như câu a.
•        Ngược lại, bổ sung một loại vật tư mới vào kho với mã là Bma, tên vật tư là Bten, đơn vị tính là Bdv và số lương tương ứng là n.
c.      Viết hàm Function SoVattu(First: TroVattu; Bma:St3); trả về số lượng vật tư có mã là Bma còn tồn trong kho, nếu không có vật tư này, hàm trả về giá trị 0.
d.      Viết thủ tục Procedure ThongKe(First: TroVattu); in ra thông tin của tất cả các loại vật tư hiện có trong kho.
Bài tập 9.19: Cho danh sách các số nguyên được tổ chức như sau:
     Type  TRO = ^PT;
          PT = Record
                        X: Integer;
                        Link: TRO;
                   End;
1. Viết thủ tụNHAP(Var Dau:TRO); để nhập vào một danh sách các số nguyên có nút đầu tiên được trỏ bởi con trỏ Dau.
2. Viết thủ tụLIETKE(Dau:TRO); để in ra màn hình giá trị của tất cả các nút trong danh sách được trỏ bởi con trỏ Dau.
3. Giả sử Dau là con trỏ trỏ đến đầu của một danh sách chưa được sắp xếp, còn L được gán bằng NIL. Hãy viết thủ tụSAPCHON(Var Dau,L:TRO); cho phép chọn các phần tử trong danh sách Dau từ giá trị lớn đến bé, đưa vào danh sách L để cuối cùng Dau=Nil, còn L sẽ trở thành một danh sách đã được sắp xếp theo thứ tự tăng dần.
4. Viết hàTANG(Dau:TRO):Boolean; để xác định xem danh sách được trỏ bởi Dau đã có thứ tự tăng dần hay không theo 2 cách: Không đệ qui và đệ qui.
5. Viết thủ tụDAO(Var Dau:TRO); để đảo ngược các con trỏ của danh sách Dau.
Bài tập 9.20: Cho danh sách các số nguyên được tổ chức như sau:
     Type  TRO = ^PT;
          PT = Record
                        Gtri: Integer;
                        Tiep: TRO;
                   End;
1. Viết hàDXUNG(ds:TRO):Boolean; nhằm kiểm tra các giá trị trong danh dách ds có phải là đối xứng hay không theo 2 cách: Đệ qui và không đệ qui.(Ví dụ: danh sách chứa các dãy số sau đây là đối xứng: 2  3  6  3  2; 5  7  7  5).
2. Viết hàKhaDX(ds:TRO):Boolean; để kiểm tra xem với danh sách ds đã cho, có tồn tại một cách sắp xếp lại các phần tử để cuối cùng nhận được một danh sách đối xứng hay không?
3. Viết thủ tụSAPLAI(Var ds:TRO); để đưa ra một cách sắp xếp lại các phần tử để có một danh sách đối xứng (giả thiết điều này có thể làm đuợc nhờ hàKhaDX).

VI. VIẾT CHỮ TRONG CHẾ ĐỘ ĐỒ HỌA
6.1. Chọn Font ch
     Ta dùng thủ tục SETTEXTSTYLE(font,Dir,size:Word);
     - Các font có thể chứa các hằng sau:
          DefaultFont = 0;     TriplexFont = 1; SmallFont = 2;
          SansSerifFont = 3;      GothicFont = 4;
     - Dir có các hằng sau:
          HorizDir = 0  Từ trái qua phải.
          VetDir = 1 Từ dưới lên trên.
     - Size: độ lớn của chữ.
6.2. Chọn phân bố ch
     Dùng thủ tục SETTEXTJUSTIFY(Hz,Vt:Word);
     Chọn vị trí của chữ xung quanh tọa độ định sẵn.
     - Hz là phân bố chữ theo trục ngang. Có các hằng sau:
          LeftText = 0  Chữ viết nằm bên phải trục đứng.
          CenterText = 1   Chữ viết nằm ở giữa trục đứng.
          RightText = 2     Chữ viết nằm bên trái trục đứng.
     - Vt là bố trí chữ theo hướng dọc đối với tọa độ qui định xuất chuỗi. Các hằng liên quan:
          BottomText = 0 Chữ viết nằm bên trên trục ngang.
          CenterText = 1   Chữ viết nằm ở giữa trục ngang.
          TopText = 2        Chữ viết nằm bên dưới trục ngang.
6.3. Viết một xâu ký tự lên màn hình
     - Xuất một xâu ký tự tại vị trí con trỏ:
          Dùng thủ tục OUTTEXT(St:String);
     - Xuất một xâu ký tự tại tọa độ x,y:
          Dùng thủ tục OUTTEXTXY(x,y:Word; St:String);
Chú ý: Cách xuất chuỗi của hai thủ tục trên được qui định trong thủ tục SETTEXTJUSTIFY và SETTEXTSTYLE.