Bài giảng Cấu trúc dữ liệu

+ Tận dụng được không gian nhớ để lưu trữ.
+ Việc bổ sung hay loại bỏ được thực hiện dễ dàng.
+ Dễ dàng kết nối hay phân rã danh sách.
- Nhược điểm: Truy xuất tuần tự.
2.3.2.4. So sánh giữa danh sách liên kết và mảng.
Danh sách liên kết có số phần tử có thể thay đổi và không cần chỉ rõ kích thước tối đa của danh sách trước. Ngược lại mảng là các cấu trúc có kích thước cố định.
Chúng ta có thể sắp xếp lại, thêm và xóa các phần tử khỏi danh sách liên kết chỉ với một số cố định các thao tác. Với mảng các thao tác này thường tương đương với kích thước mảng.
Để tìm đến phần tử thứ i trong một danh sách liên kết chúng ta cần phải đi qua i-1 phần tử đứng trước nó trong danh sách (i-1 thao tác) trong khi với mảng để làm điều này chỉ mất 1 thao tác.
Tương tự kích thước của một danh sách không phải hiển nhiên mà biết được trong khi chúng ta luôn biết rơ kích thước của một mảng trong chương trình (tuy nhiên có một cách đơn giản để khắc phục điều này).
2.3.3. Danh sách liên kết kép.
2.3.3.1. Biểu diễn danh sách.
Với danh sách liên kết đơn ta chỉ có thể duyệt danh sách theo một chiều. Trong một số ứng dụng đôi khi vẫn xuất hiện yêu cầu đi ngược lại. Để được hai khả năng, cần phải đặt ở mỗi nút hai con trỏ, một con trỏ trỏ tới nút đứng trước nó và một trỏ tới nút đứng sau nó. Như vậy nghĩa là qui cách của một nút sẽ như sau:
 Left	INFO	Right
Với Left là con trỏ trái, trỏ tới nút đứng trước.
Còn Right là con trỏ phải, trỏ tới nút đứng sau nó.
Còn INFO vẫn giống như danh sách liên kết đơn (chứa giá trị).
Type Tro=^Nut;
Nut = Record
Info: Element;
Left, Right:Tro;
End;
Var First, Last: Tro;
2.3.3.2. Các thao tác trên danh sách.
1. Chèn một phần tử trong danh sách
- Chèn vào đầu danh sách:
Procedure ChenDau(X:Element; Var First,Last:Tro);
Var p:Tro;
Begin
New(p);
P^.info:=X;
P^.left:=nil;
P^.Right:=Nil;
If First=nil then
Begin
First:=Nil;
Last:=nil;
End
Else
Begin
P^.Right:=First;
First^.Left:=p;
First:=p;
End;
End;
- Chèn vào cuối danh sách:
Procedure ChenCuoi(X:Element; Var First,Last:Tro);
Var p:Tro;
Begin
New(p);
P^.info:=X;
P^.left:=nil;
P^.Right:=Nil;
If First=nil then
Begin
First:=Nil;
Last:=nil;
End
Else
Begin
Last^.Right:=p;
P^.Left:=Last;
Last:=p;
End;
End;
- Chèn một phần tử vào giữa danh sách:
Procedure ChenGiua(X:Element; q:Tro);
Var p,r:Tro;
Begin
New(p);
P^.Info:=X;
P^.Left:=Nil; P^.Right:=Nil;
r:=Q^.Right;
If r=Nil then
Begin
q^.Right:=p;
p^.left:=q;
Last:=p;
End
Else
Begin
p^.Right:=r; r^.left:=p;
q^.Right:=p; P^.Left:=q;
End;
End;
2. Duyệt qua các nút trong danh sách.
Procedure duyet(First:Tro);
var p:Tro;
Begin
P:=First;
While (pnil) do
begin
p:=p^.Right;
end;
End;
3. Tìm kiếm một phần tử trong danh sách.
Function TimKiem(X:Element;First:Tro):Tro;
Var P:Tro;Found:Boolean;
Begin
P:=First; found:=False;
While (PNil) and (not found) do
Begin
If X=P^.Info then
Begin
TimKiem:=P;
found:=True;
End
Else
P:=P^.Right;
End;
If (not thoat) then TimKiem:=Nil;
End;
4. Loại bỏ một phần tử trong danh sách.
- Loại bỏ phần tử đầu danh sách:
Procedure XoaDau(Var First,Last:Tro);
Var P:Tro;
Begin
If FirstNil Then
Begin
P:=First;
First:=First^.Right;
First^.Left:=Nil;
Dispose(P);
If First=Nil then Last:=Nil
Else First^.Left:=Nil;
End;
End;
- Loại bỏ phần tử cuối danh sách:
Procedure XoaCuoi(Var First,Last:Tro);
Var P:Tro;
Begin
If LastNil then
Begin
P:=Last;
Last:=Last^.Left;
Last^.Right:=Nil;
Dispose(P);
If First=Nil then Last:=Nil
Else First^.Left:=Nil;
End;
End;
- Loại bỏ phần tử ở giữa danh sách:
Procedure XoaGiua(P:Tro;Var First,Last:Tro);
Var
Begin
If (P^.Left=Nil) and (P^.Right=Nil) then
Begin
First:=Nil; Last:=Nil;
End
Else
If P^.left=Nil then
Begin
First:=First^.Right;
First^.Left:=Nil;
End
Else
If P^.Right=Nil then
Begin
Last:=Last^.Left;
Last^.Right:=Nil;
End
Else
Begin
P^.Left^.Right:=P^.Right;
P^.Right^.Left:=P^.Left;
End;
P^.Right:=Nil;
P^.Left:=Nil;
Dispose(P);
End;
2.3.3.3. Ưu nhược điểm và ứng dụng
- Ưu điểm: Danh sách liên kết kép có mối liên kết hai chiều nên từ một phần tử bất kỳ có thể truy xuất một phần tử bất kỳ khác. Trong khi danh sách liên kết đơn chỉ có thể truy xuất phần tử đứng sau nó.
- Nhược điểm: Danh sách liên kết tốn chi phí gấp đôi so với danh sách liên kết đơn cho việc lưu trữ các mối liên kết. Điều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp.
- Ứng dụng: Danh sách liên kết kép thích hợp sử dụng cho việc quản lý danh sách học sinh – sinh viên.
2.4. Danh sách hạn chế.
2.4.1. Ngăn xếp (Stack).
2.4.1.1. Định nghĩa.
Ngăn xếp (Stack) là một danh sách tuyến tính mà cả hai phép thêm vào và loại bỏ phần tử đều tiến hành 1 đầu của danh sách.
Như vậy phần tử nào được thêm vào sau, thì loại bỏ trước, vì vậy Stack còn gọi là danh sách LIFO (Last In First Out).
Vi dụ: Hình ảnh của một chồng đĩa.
- Đỉnh (top) của một stack là nơi thêm vào hay loại bỏ một phần tử khỏi stack.
- Đáy (Bottom) của một stack là nơi chứa phần tử khó truy xuất nhất, và nó sẽ không bị loại bỏ cho đến khi tất cả các phần tử khác bị loại bỏ.
2.4.1.2. Biểu diễn ngăn xếp.
a. Biểu diễn Stack dùng mảng
Ta có thể tạo một stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N (ví dụ, N có thể bằng 1000).
	VD:
Tạo stack S và quản lý đỉnh stack bằng biến T. Nếu T là địa chỉ của phần tử đỉnh của stack thì T sẽ có giá trị biến đổi khi stack hoạt động. Như vậy khi stack rỗng thì T=0. Một phần tử được bổ sung vào Stack thì T sẽ tăng lên một đơn vị. Khi một phần tử bị loại bỏ khỏi stack thì T se giảm đi một đơn vị.
Có thể thấy cấu trúc lưu trữ của stack như hình sau:
b. Biểu diễn Stack dùng danh sách liên kết đơn.
Việc cài đặt stack bằng cách dùng danh sách móc nối là khá tự nhiên. Chẳng hạn với danh sách móc nối đơn trỏ bởi First thì có thể coi first như con trỏ trỏ tới đỉnh stack. Bổ sung một nút vào stack chính là bổ sung mộ nút vòa thành nút đầu tiên của danh sách, loại bỏ một nút ra khỏi stack chính là loại bỏ nút đầu tiên của danh sách. Trong thủ tục bổ sung với stack móc nối ta không phải kiểm tra hiện tượng Tràn như đối với stack tổ chức bằng mảng, vì stack móc nối không hề bị giới hạn về kích thước, nó chỉ phụ thuộc vào giới hạn của bộ nhớ.
Stack là một danh sách liên kết được khai báo như sau:
Type
Tro = ^nut;
Nut = record
Info : element;
Link : tro;
End;
Var
Sp : Tro;{Sp trỏ đến đầu ngăn xếp}
2.4.1.3. Các thao tác.
a. Dùng cấu trúc mảng để biểu diễn ngăn xếp.
- Khai báo stack
Type Stack = array[1..n] of element;
Var T:integer; {T là đỉnh stack, chỉ vị trí phần tử cuối cùng được lưu vào stack}
S:Stack;
X:element; { chú ý n là kích thước là một hằng số đã được khai báo}
- Khởi tạo stack
Procedure khoitao;
Begin
T:=0;
End;
- Thêm một phần tử vào stack
Pocedure Push(Var S:Stack;Var T:integer;X:element);
Begin
If T=n then
Write(‘Tran stack’)
Else
Begin
T:=T+1;
S[T]:=X;
End;
End;
- Loại bỏ một phần tử (hay lấy một phần tử từ stack ra)
Pocedure Pop(Var S:Stack;Var T:integer;X:element);
Begin
If T=0 then
Write(‘Stack can’)
Else
Begin
X:=S[T];
T:=T-1;
End;
End;
b. Biểu diễn Stack dùng danh sách liên kết đơn.
- Khởi tạo stack:
Khi khởi tạo, stack là rỗng, ta cho sp có giá trị là nil.
Thuật toán:
Procedure Initialize;
begin	
	Sp:= nil ;
end;
- Thêm một phần tử vào stack:
Thủ tục Insert_stack sau cho phép đẩy một phần tử có giá trị NewInfo vào ngăn xếp có đỉnh là Sp.
Thuật toán:
Procedure Insert_stack (NewInfo : Element; Var Sp:Tro);
var
	p : Tro;
begin
	New(p);
	p^.Info := NewInfo;
	p^.Link := Sp;
	Sp:= p;
end;
- Loại bỏ một phần tử của stack (lấy ra):
Biến succ có giá trị true nếu stack khác rỗng và nội dung lấy ra là Infor. Biến succ có giá trị false nếu stack rỗng.
Thủ tục Delete-Stack cho phép lấy một phần tử ở đỉnh ngăn xếp và chứa vào biến Infox.
Thuật toán:
Procedure Delete_stack(var Infox:Element; var succ :boolean);
var
	p: tro;
begin
	succ := false;
	if Sp nil then
	begin
	succ := true ;
	p := Sp;
	sp := p^. Link ;
	Infox := p^.Info ;
	Dispose (p) ;
	end
end;
4. Ứng dụng.
a. Chuyển đổi từ số thận phân sang hệ nhị phân.
Thuật giải: Gọi số cần chuyển là n
1. Nếu N=0àkq=0 dừng
2. While N0 do
- Tính số dư của N chia cho 2:R
- Gửi R vào ngăn xếp: Push(S,T,R)
- Thay n:=n div 2
3. Hiển thị số nhị phân
While stack không rỗng do
- Lấy R từ đỉnh stack: Pop(S,T,V)
- Hiển thị V: write(V)
{việc chuyển đổi thuật toán thành chương trình xem như bài tập.
b. Ký pháp nghịch đảo balan
Trong hầu hết ngôn ngữ lập trình, các biểu thức số học được viết dưới dạng ký pháp trung tố (infix notation), nghĩa là mỗi ký hiệu của phép toán hai ngôi được đặt giữa các toán hạng. Tuy nhiên các bộ dịch chương trình cần tạo ra các chỉ thị máy để đánh giá các biểu thức, do vậy các biểu thức số học cần biến đổi dạng biểu diễn để việc đánh giá cơ học là dễ dàng hơn. Dạng biểu thức này còn gọi là ký pháp hậu tố (Postfix) hay tiền tố (prefix).
Ví dụ 1:
- Biểu thức trung tố: 7*(9-5)
+ Có thể biểu diễn dưới dạng hậu tố (RPN-Reverse Polish Notation-ký pháp nghịch đảo Balan) như sau: 7 9 5 - *
+ Có thể biểu diễn dưới dạng tiền tố: * 7 – 9 5
Ví dụ 2:
- Xét biểu thức trung tố: (1+5)*(8-(4-1))
- Biểu thức hậu tố tương ứng: 1 5 + 8 4 1 - - *
- Cách thức tính biểu thức hậu tố này như sau:
+ Đọc từ trái sang phải cho đến khi gặp một toán tử. Hai toán hạng cuối cùng trước toán tử này sẽ được kết hợp bởi toán tử này, (1+5=6) thay kết quả vào biểu thức ta có biểu thức RPN mới 6 8 4 1 - - *
+ Tương tự như bước 1 ta có RPN: 6 8 3 - *
+ Tiếp tục ta có RPN: 6 5 *
+ giá trị cuối cùng của RPN sẽ là 6*5 = 30.
Phương pháp đánh giá biểu thức RPN này đòi hỏi phải lưu trữ các toán hạng cho đến khi 1 toán tử được đọc từ trái sang phải, tại một thời điểm này 2 toán hạng cuối cùng phải được tìm ra và kết hợp với toán tử này. Như vậy, phải hoạt động theo cơ chế « vào sau ra trước », nghĩa là phải dùng stack để lưu trữ các toán hạng. Cứ mỗi lần đọc được một toán tử, hai giá trị lấy ra từ ngăn xếp, sẽ được tác động bởi toán tử này, xong kết quả được đưa vào stack.
Các giải thuật liên quan.
* Thuật toán chuyển từ biểu thức trung tố sang hậu tố RPN
1. Khởi động 1 stack rỗng
2. While not(lỗi) and (chưa kết thúc biểu thức) do
- đọc một phần tử của biểu thức trung tố: pt
- Case pt of
+ Toán hạng: hiển thị
+ Toán tử: 
Nếu stack rỗng : Lấy và hiển thị phần tử ở đỉnh stack nếu phần tử ở đỉnh ưu tiên hơn, tiếp tục so sánh pt với phần tử ở đỉnh stack.
Nếu stack = rỗng hay pt ưu tiên hơn phần tử ở đỉnh stack thì đẩy pt vào stack.
+ Dấu ngoặc trái thì đẩy vào ngăn xếp.
+ Dấu ngoặc phải thì lấy và hiển thị các phần tử của stack cho đến khi gặp dấu ngoặc trái. Nếu ngăn xếp rỗng thì lỗi.
3. Khi kết thúc biểu thức trung tố hiển thị các phần tử của stack cho đến khi stack rỗng. 
Ví dụ 3 :
Minh họa chuyển biểu thức 7*8-(2+3).
	Biểu thức	stack	kết quả
* Thuật toán đánh giá biểu thức RPN
1 Khởi tạo Stack
2. Lặp lại cho đến khi kết thúc biểu thức RPN
- Đọc phần tử của biểu thức RPN
- Nếu phần tử là toán hạng
+ Toán hạng thì đẩy nó vào stack
+ Toán tử :
Lấy từ đỉnh stack 2 phần tử (nếu không chứa đủ hai phần tử thì lỗi và dừng)
Áp dụng toán tử cho hai giá trị vừa lấy ra
Đẩy kết quả vào stack.
3. Khi gặp dấu kết thúc, giá trị biểu thức ở đỉnh stack.
2.4.2. Hàng đợi (Queue)
2.4.2.1. Định nghĩa.
Hàng đợi là một danh sách tuyến tính mà phép thêm vào được tiến hành ở một đầu danh sách và phép loại bỏ được tiến hành ở 1 đầu còn lại của danh sách.
Hàng đợi chứa các đối tượng làm việc theo cơ chế FIFO (First In First Out) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế "Vào trước ra trước".
Hàng đợi
2.4.2.2. Biểu diễn hàng đợi.
a. Biểu diễn dùng mảng:
Ta có thể tạo một hàng đợi bằng cách sử dụng một mảng 1 chiều với kích thước tối đa là N (ví dụ, N có thể bằng 1000). Dùng 2 biến F, R để trỏ đến đầu loại bỏ và đầu bổ sung của queue.
Trạng thái hàng đợi lúc bình thường:
Q – biến hàng đợi, f quản lý đầu hàng đợi, r quản lý phần tử cuối hàng đợi.
b. Dùng danh sách liên kết
Ta có thể tạo một hàng đợi bằng cách sử dụng một danh sách liên kết đơn.
Ta khai báo:
Type
Tro = ^ nut;
Nut = record
info : Element;
Link : tro;
End;
Var Front, Rear :ref;
2.4.2.3. Các thao tác.
a. Dùng cấu trúc mảng để biểu diễn hàng đợi.
* Các phép toán.
- Khai báo cấu trúc queue bằng mảng.
Const N=100;
Type
Queue:Array[1..n] of element;
Var
Q:queue;
F,R:Byte;
- Khởi tạo Queue
Procedure khoitao;
Begin
F:=0;
R:=0;
End;
- Thêm một phần tử vào queue:
Mỗi lần thêm một phần tử vào Queue thì R tăng lên một đơn vị. Tuy nhiên, do tính chất của queue, queue có khả năng bị tràn giả tạo khi F>1, R=N
Có hai phương pháp khắc phục tình trạng trên
- Phương pháp di chuyển tịnh tiến.
- Phương pháp di chuyển vòng.
Mỗi lần bổ sung một phần tử, kiểm tra số phần tử hiện tại của queue (R-F+1). Nếu số phần tử queue < n, dịch chuyển các phần tử sao cho các phần tử F có chỉ số là 1.
+ Phương pháp di chuyển tịnh tiến.
Procedure Insert1(Var Q:Queue;Var F,R:Byte; X:element);
Var i:Byte;
Begin
If R-F+1 =n then Write(‘TRAN’)
Else
If F=0 then F:=1
Else
If R=n then
Begin
For i:=F to R do q[i-F+1]:=q[i];
R:=n-F+1;
F:=1;
End;
R:=R+1;
Q[R]:=X;
End;
+ Phương pháp di chuyển vòng.
Sau khi lưu trữ xong phần tử thứ n sẽ kiểm tra phần tử 1 rỗng không, nếu có thì sẽ tiến hành bổ sung vào phần tử 1 (R=1). Tiếp tục như trên, trong trường hợp này queue bị đầy khi:
R-F+1=0
Hoặc
R-F+1=n
Procedure Insert2(Var Q:Queue;Var F,R:Byte; X:element);
Begin
If (R-F+1 =0) or (R-F+1 =n) then Write(‘TRAN’)
Else
If F=0 then F:=1
Else
Begin
If R=n then R:=0;
R:=R+1;
Q[R]:=X;
End;
End;
- Loại bỏ một phần tử khỏi queue:
+ Phương pháp di chuyển tịnh tiến.
Procedure Del_Queue(Var Q:Queue;Var X:element);
Begin
If F=0 then Write(‘CAN’)
Else
Begin
X:=Q[F];
F:=F+1;
If F>R then
Begin
F:=0;
R:=0;
End;
End;
End;
+ Phương pháp di chuyển vòng.
Procedure Del_Queue(Var Q:Queue;Var X:element);
Begin
If F=0 then Write(‘CAN’)
Else
Begin
X:=Q[F];
If F=R then
Begin
F:=0;
R:=0;
End
Else
Begin
F:=F+1;
If F>n then F:=1;
End;
End;
End;
b. Dùng danh sách liên kết để biểu diễn hàng đợi.
Rear là đầu thêm vào và Front là đầu loại bỏ
* Các phép toán.
- Khởi tạo hàng đợi:
	Khi khởi tạo, hàng đợi là rỗng, ta cho Front và Rear có giá trị là nil.
Thuật toán:
Procedure Initialize;
Begin
Front := nil;
Rear := nil;
end;
- Thêm một phần tử vào hàng đợi:
Khi dùng danh sách liên kết để biểu diễn hàng đợi thì phép thêm vào hàng đợi thì tương tự như thêm một phần tử vào cuối danh sách liên kết.
Giả sử ta cần một phần tử mới p có nội dung là NewInfo vào hàng đợi.
Thuật toán:
Procedure Insert_queue ( NewInfo : Element; Var Front, Rear:Tro );
Var
q,p :tro;
Begin
New(p) ;
p^.Info := NewInfo ;
P^. Link := nil;
If Front = nil then
Begin
Front := p;
Rear:=p;
End;
Else
Begin
Rear^.Link := p;
Rear := p;
End;
End;
- Loại bỏ một phần tử của hàng.
Biến succ có giá trị là true nếu hàng đợi khác rỗng và nội dung lấy ra là Infox. Biến succ có nội dung là false nếu hàng đợi rỗng.
Thuật toán:
Procedure Delete_queue (Var Infox : Element; Var succ :boolean; Var Front, Rear:Tro);
Var
P:Tro;
Begin
succ := false ;
If Front nil then
Begin
succ := true;
p := Front;
Front := p^.Link ;
Infox := p^.Info ;
if Front = nil then Rear := nil ;
Dispose(p);
End;
End;
2.4.2.4. Ứng dụng.
Trong thực tế Queue có nhiều ứng dụng
Bộ đệm bàn phím.
Hàng đợi lệnh trong CPU.
Bộ đệm giữa máy tính và máy in.
BÀI TẬP CHƯƠNG 2
Bài tập 1: Viết chương trình chuyển đổi số nguyên (đơn vị giây) sang dạng giờphútgiây.
Dạng mẫu của chương trình khi chạy có thể như sau:
Đưa vào số nguyên (đơn vị giây): 3812
3812 giây = 1 giờ 3 phút 32 giây.
Bài tập 2: Viết chương trình đọc một số nguyên rồi hiển thị
a. Các chữ số của số ấy, và tổng của các chữ số đó.
b. Số đảo ngược.
c. Hiệu của số đó với số đảo ngược
Bài 3: Viết chương trình đọc một số nguyên, rồi hiển thị giá trị sau:
S = 1-2+3-4+5-6++(-1)n*n
Bài 4: Viết chương trình hiển thị tất cả các số nguyên gồm có 3 chữ số sao cho tổng tất cả các chữ số bằng tích của chúng.
Bài 5: Viết chương trình nhập vào một chuỗi chứa ho, tên và chữ lót rồi chuyển sang dạng tên, họ và chữ lót. Ví dụ, nếu chuỗi là “Hoàng Nguyệt Kim” chương trình sẽ chuyển thành “Nguyệt Hoàng Kim”.
Bài 6: Viết chương trình đọc một chuỗi (một dòng văn bản) rồi hiển thị mỗi từ trên một hàng và số các từ trong câu ấy.
Bài tập 7: 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 8: 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 9: 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}
	+ Nếu A[i]>B[j] thì: C[k]:=A[i]; i:=i+1;
	+ 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 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.
	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ử biÎ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ử aiÎA. Nếu aiÏB thì in ai ra màn hình.
Bài tập 11: 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 12 :
Cho DSLK mỗi phần tử là một bản ghi tự trỏ bao gồm các thành phần sau :
Mã sinh viên.	
Họ sinh viên
Lớp
Điểm TB (ĐTB)
Yêu cầu : Viết chương trình bao gồm các chức năng sau :
1. Tạo DSLK cho đến khi nhấn phím escape thì dừng.
2. In DSLK vừa nhập.
3. Xóa 1 phần tử trong DSLK có họ tên được nhập từ bàn phím.
4. Thêm một phần tử vào trong DSLK có mã sinh viên, họ sinh viên, lớp, ĐTB được nhập vào từ bàn phím.
5. Tìm 1 phần tử trong DSLK dựa vào mã sinh viên.
6. Sắp xếp các phần tử trong DSLK tăng dần theo điểm trung bình.
Bài 13: Viết chương trình bao gồm các chức năng sau:
Tạo danh sách liên kết, chứa các số nguyên nhập từ bàn phím trên một hàng, quá trình nhập dừng khi nhập số 0.
Hiển thị các phần tử trong danh sách nói trên.
Đếm số nút trong danh sách liên kết.
Tính giá trị trung bình của các phần tử trong danh sách.
Xác định nút cuối cùng trong danh sách.
Thêm một nút vào cuối danh sách.
Chèn một nút vào sau nút thứ n trong danh sách, với n cho trước.
Xóa một phần tử thứ n trong danh sách với n cho trước.
Bài 14: Viết chương trình trộn hai danh sách liên kết có thứ tự tăng dần và tạo thành danh sách thứ 3 cũng tăng dần (trong hai trường hợp: 2 danh sách ban đầu được bảo toàn và không bảo toàn).
Bài 15: Giả sử L1 và L2 là hai danh sách liên kết cho trước. Viết thuật toán hiển thị:
Phần giao của hai danh sách.
Phần hội của hai danh sách.
Hiệu của hai danh sách. 
Bài 16: Viết chương trình dùng ngăn xếp để chuyển một số thập phân sang dạng nhị phân.
Bài 17: Dùng các phép toán cơ bản trên ngăn xếp để lấy ra một phần tử ở đáy ngăn xếp nhưng để lại nguyên nội dung.