Cấu trúc dữ liệu và giải thuật - Công nghệ Website | Đại học Bách Khoa, Đại học Đà Nẵng

Cấu trúc dữ liệu và giải thuật - Công nghệ Website | Đại học Bách Khoa, Đại học Đà Nẵng giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học

26 13 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Công nghệ Web (CNWEB1)

Trường: Trường Đại học Bách khoa, Đại học Đà Nẵng

Thông tin:

36 trang 1 tháng trước

Tác giả:

Profile Kim Oanh
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.1
CHƯƠNG II
CẤU TRÚC DỮ LIỆU DANH SÁCH
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.2
I. TỔNG QUAN VỀ DANH SÁCH
1. Định nghĩa
Danh sách (List) là dãy các phần tử
a n
1
, ..., a
n
( 1)
với tính chất: nếu biết được a
i
sẽ biết a
i+1
.
Danh sách được sắp xếp tuyến tính theo vị trí của chúng.
Số các phần tử n gọi là độ dài của danh sách. Nếu n = 0, thì ta có danh sách
rỗng.
Ví dụ
- Danh sách nhân viên trong cơ quan.
- Danh sách sinh viên của lớp.
- Danh sách các môn học.
- Danh sách . các số tự nhiên không quá 100
2. Các phép toán trên danh sách
Để tạo lập, cập nhật, khai thác danh sách, người ta định nghĩa các phép toán sau.
a. Phép duyệt danh sách
Duyệt danh sách là duyệt qua tất cả phần tử danh sách thoả mãn <điều kiện> nào
đó để thực hiện công việc < > (chẳng hạn như hiển thị phần tử).xử lý
Ví dụ: Liệt kê danh sách nữ nhân viên trong cơ quan.
b. Phép tìm kiếm
Tìm kiếm là thao tác tìm phần tử trong danh sách thoả mãn điều kiện nào đó. Kết
quả phép tìm kiếm có thể là hoặc . Sau khi tìm thấy phần tử tìm thấy không tìm thấy
cần tìm ta có thể thực hiện các phép toán đối với phần tử đó như sửa đổi hay xoá.
Ví dụ: Trong danh sách nhân viên trong cơ quan, tìm nhân viên có tên là “Trần Công
Minh”.
c. Thêm phần tử vào danh sách
Đây là thao tác thêm phần tử mới vào danh sách. Phần tử có thể được thêm vào
cuối danh sách, đầu danh sách hoặc chèn vào giữa danh sách. Nếu danh sách đã đầy,
tức là số phần tử của danh sách đã bằng số cực đại cho phép thì phép toán thêm không
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.3
thực hiện được nữa. Nếu danh sách chưa đầy thì có thể thêm phần tử mới vào danh
sách và độ dài (số phần tử) của danh sách tăng thêm 1.
Ví dụ: Trong danh sách nhân viên trong cơ quan, thêm nhân viên mới hợp đồng có
tên là “Trần Công Minh”.
d. Loại bỏ phần tử khỏi danh sách
Đây là thao tác loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ phần tử, nếu
chưa xác định được phần tử loại bỏ, thì phải thực hiện phép tìm kiếm. Nếu không tìm
thấy thì không thể thực hiện phép loại bỏ. Nếu tìm thấy thì có thể thực hiện phép loại
bỏ và độ dài (số phần tử) của danh sách giảm đi 1.
Phần tử loại bỏ có thể ở cuối danh sách, đầu danh sách hoặc giữa danh sách.
Ví dụ. Trong danh sách nhân viên trong cơ quan, loại bỏ nhân viên cắt hợp đồng có
tên là “Trần Công Minh”.
e. Sửa đổi phần tử trong danh sách
Đây là thao tác hiệu chỉnh phần tử trong danh sách. Trước khi hiệu chỉnh phần tử,
nếu chưa xác định được phần tử hiệu chỉnh, thì phải thực hiện phép tìm kiếm. Nếu
không tìm thấy thì không thể thực hiện phép hiệu chỉnh. Nếu tìm thấy thì có thể thực
hiện phép hiệu chỉnh. Số phần tử của danh sách không thay đổi
Phần tử hiệu chỉnh có thể ở cuối danh sách, đầu danh sách hoặc giữa danh sách.
Ví dụ. Trong danh sách nhân viên trong cơ quan, hiệu chỉnh mức lương cho nhân
viên có tên là “Trần Công Minh”.
f. Sắp xếp thứ tự danh sách
Đây là thao tác sắp xếp lại thứ tự các phần tử trong danh sách theo một khoá nào
đó. Thứ tự phần tử có thể thay đổi, nhưng số phần tử vẫn giữ nguyên.
: Ví dụ Sắp xếp danh sách nhân viên trong cơ quan theo họ tên hoặc theo mức lương.
g. Tách một danh sách thành nhiều danh sách
Đây là thao tác tá ần hoặc lấy tất cả phần tử của một danh sách đưa sang ch một ph
danh sách khác.
. Ví dụ Từ danh sách nhân viên trong cơ quan tách riêng danh sách nữ nhân viên.
h. Ghép nhiều danh sách thành danh sách mới
Đây là thao tác lấy tất cả phần tử từ các danh sách khác nhau tạo thành một danh
sách mới. Các phần tử của cùng một danh sách con vẫn xếp cạnh nhau.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.4
Ví dụ. Từ danh sách nhân viên của các phòng ghép lại thành danh sách nhân viên
của toàn cơ quan.
i. Trộn nhiều danh sách thành danh sách mới
Đây là thao tác lấy tất cả phần tử từ các danh sách khác nhau tạo thành một danh
sách mới theo một cấu trúc nào đó. Các phần tử của cùng một danh sách con có thể sẽ
bị xáo trộn.
Ví dụ. Từ danh sách nhân viên của các phòng đã được sắp xếp theo họ tên trộn lại
thành danh sách nhân viên của toàn cơ quan sắp xếp theo họ tên.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.5
II. DANH SÁCH ĐẶC
1. Định nghĩa và khai báo
a. Định nghĩa
Danh sách đặc danh sách kề (condensed list) hay còn gọi là ( là contiguous list)
danh 1 sách mà các phần tử được lưu trữ kế tiếp nhau trong bộ nhớ, phần tử thứ i+
đứng ngay sau phần tử thứ i.
Hình sau mô tả danh sách đặc, trong đó các phần tử có kích thước bằng nhau và
xếp kế tiếp nhau.
a
1
a
2
...
...
a
i
a
i+1
...
....
a
n
1
a
n
add add add [1] [i] d [n]
Nếu các phần tử có độ dài d byte là như nhau và ký hiệu địa chỉ phần tử i
add i[ ], thì ta sử dụng công thức tính địa chỉ như sau:
add i i[ ] = add[1] + (
1)*d
b. Khai báo
Trong PASCAL:
Const ElemNo = <số phần tử tối đa của danh sách>;
Type
InfoType = <kiểu dữ liệu các trường không khóacủa >;
KeyType = <kiểu dữ liệu của trường khóa>;
Element = record
key : KeyType; {khoá}
info : InfoType; {dữ liệu}
end;
ListType = array .. ElemNo of Element; [1 ]
Var t: ListType; Lis
ListNum: integer; {số phần tử của danh sách, không được vượt quá
ElemNo}
Trong C:
#define ElemNo <s ố phần tử tối đa của danh sách>
typedef <kiểu dữ liệu của các trường không khóa > InfoType;
typedef <kiểu dữ liệu của các trường khóa > KeyType;
struct Element {
KeyType key; //khoá
InfoType info; // dữ liệu
};
struct Element List ; [ElemNo+1]
int ListNum; // số phần tử của danh sách, không được vượt quá ElemNo
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.6
2. Các phép toán
a. Khởi tạo danh sách
Ban đầu danh sách rỗng, nên ta khởi tạo đặt độ dài danh sách ListNum = 0.
Trong C
void Initialize ()
{
ListNum = 0;
}
b. Duyệt danh sách
Duyệt danh sách thoả mãn < > để <điều kiện xử lý>
Trong C
void Traverse ()
{
int i; //biến cục bộ
for ( i = ; i ListNum; i++ 1 <= )
if <điều kiện>
{
<xử lý List[i]>
}
}
c. Tìm kiếm tuyến tính
Giả sử ta phải tìm phần tử có trường Key = KeyValue.
Hàm Search trả về chỉ số của phần tử tìm thấy đầu tiên, hoặc trả về giá trị nếu 1
không tìm thấy.
Trường hợp danh sách không thứ tự
Trong PASCAL:
function Search KeyValue: KeyType : integer; ( )
var vi tri: integer;
begin
vitri := 1;
while <= ListNum and .key <> KeyValue do (vitri ) (List[vitri] )
vitri := vitri + ; 1
if ListNum then (vitri <= )
search := vitri
else
search := -1;{không tìm thấy}
end;
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.7
Trong C:
int Search KeyType KeyValue ( )
{
int ; vitri
vitri = 1;
while vitri <= ListNum .Key = KeyValue i++; (( ) && (List[vitri] ! )) vitr
if (vitri == ListNum+1) ; //không tì return -1 m thấy
else return vitri; //tìm thấy
}
Trường hợp danh sách có thứ tự
Trong PASCAL:
function Search KeyValue: KeyType : integer; ( )
var found: boolean;
vitri : integer;
begin
found := false;
vitri := 1;
while <= ListNum and not found do (vitri ) ( )
if List[vitri].key = KeyValue then
found := true
else
if (List[vitri].key > KeyValue then )
vitri := List Num + 1
else
vitri vitri := ; + 1
if found then
search := vitri
else
search := -1; {không tìm thấy}
end;
Trong C:
int Search KeyType KeyValue ( )
{
int ; vitri
vitri = 1;
while vitri <= ListNum .Key < KeyValue (( ) && (List[vitri] )) vitri++;
if (vitri == ListNum+1) //không tì return -1; m thấy
else return (List[vitri].Key == KeyValue vitri : ; ? -1)
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.8
: Độ phức tạp
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
Ghi chú : n ký hiệu số phần tử của danh sách.
d. Tìm kiếm nhị phân
Phương pháp này chỉ áp dụng với danh sách đặc. Điều kiện để có thể áp dụng giải
thuật là danh sách phải được sắp xếp thứ tự theo trường tìm kiếm . Key
Giả sử ta phải tìm phần tử có trường Key = KeyValue.
Hàm Search trả về chỉ số của phần tử tìm thấy đầu tiên, hoặc trả về giá trị -1 nếu
không tìm thấy.
Trong PASCAL
Trong C
function Search KeyValue: KeyType( ):
integer;
var found: boolean;
i, min, max : integer;
begin
found := false;
min := 1;
max := ListNum;
while min <= max and not found do ( ) ( )
begin
i := min + max div ( ) 2;
.key = KeyValue then if List[i]
found := true
else
.key < KeyValue then if List[i]
min := i + 1
else
max := i
1;
end;
if found then
search := i
else
search :=
1; {không tìm thấy}
end;
int Search KeyType KeyValue ( )
{
int found;
int i, min, max ;
found = 0;
min = 1;
max = ListNum;
while min <= max && (( ) (! ))found
{
i = min + max / ( ) 2;
.key == KeyValue if (List[i] )
found = 1;
else
.key < KeyValue if (List[i] )
min = i + 1;
else
max = i
1;
}
if ( found)
; return i
else
return
1;
}
. Độ phức tạp thuật toán là : O(log
2
(n))
e. Tìm kiếm nội suy
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.9
Yêu cầu để có thể áp dụng giải thuật là danh sách phải được sắp xếp thứ tự.
Giải thuật là cải tiến của phương pháp tìm kiếm nhị phân.
Xét biểu thức tính điểm giữa i ở thuật toán nhị phân
div (min + max) 2
Biểu thức trên có thể xấp xỉ bằng
min + max 0.5 (
min)
Trong thuật toán này ta thay hệ số 0.5 bằng
k =
keyListkeyList
keyListKeyValue
[min].[max].
[min].
Trong PASCAL:
function Search KeyValue: KeyType : integer; ( )
var found: boolean;
i, min, max : integer;
k : real;
begin
found := false;
min := 1;
max := ListNum;
while min <= max and not found do ( ) ( )
begin
k := (KeyValue - List .key - ; [min].key) / (List[max] List[min].key)
i := min + round k * - ( (max min));
if (List[i].key = KeyValue then found := true )
else
if then (List[i].key < KeyValue)
min := i + 1
else
max := i - ; 1
end;
if found then
search := i
else
search := -1;
end;
Trong C:
int Search KeyType KeyValue ( )
{
int found ;
int i, min, max ;
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.10
float k ;
found = 0;
min = 1;
max = ListNum;
while min <= max (( ) && !found)
{
k = (KeyValue - .key - List[min .key] ) / (List[max] List[min].key);
i = min + k * - min (max );
if (List[i].key == KeyValue )
found = 1;
else
if (List[i].key < KeyValue )
min = i + 1;
else
max = i - 1;
}
if (found) then
return i;
else
return - 1;
}
Độ phức tạp là : O(log
2
(n))
f. Chèn phần tử vào danh sách
Giả sử ta chèn phần tử mới vào vị trí thứ . Khi đó các phần tử từ NewElem k
List[k] đến List[ListNum] được di chuyển ra sau 1 vị trí và số phần tử danh sách
ListNum tăng lên 1.
Trong PASCAL
Trong C
procedure Insert ; (k:integer;NewElem:Element)
var i: integer;
begin
for i:= ListNum downto k do
List[i+1] := List ; [i]
List[k] := NewElem;
ListNum := ListNum + 1;
end;
void Insert(int k, Element NewElem )
{
int i;
for i ( = List i >= k; iNum; --)
L = List ; ist i+[ 1] [i]
List[k] = NewElem;
ListNum++;
}
Độ phức tạp
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.11
g. Loại phần tử khỏi danh sách
Giả sử ta loại phần tử ] khỏi danh sách. Khi đó các phần tử từ đến List[k List[k+1]
List ListNum List[ ] được di chuyển về trước 1 vị trí và số phần tử danh sách Num giảm
đi 1.
Trong PASCAL
Trong C
procedure Delete(k: integer);
var i: integer;
begin
for i:= k to ListNum- do 1
List[i] := List [i+1];
ListNum := List - ; Num 1
end;
void int k Delete( )
{
int i;
for i ( = k; i <= List ; i++Num–1 )
List[i] = List[i+1];
ListNum--;
}
Độ phức tạp
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
h. Trộn danh sách
Giả sử có hai danh sách số nguyên đã sắp xếp tăng dần. Hãy a ..m[1 ] và ] b[1..n
trộn hai danh sách này thành danh sách ] c[1..m+n cũng được sắp xếp tăng dần.
Trong PASCAL
Trong C
procedure TwoListMerging;
var i : integer; i1,i2,
begin
i1 i:=:=1; i2:=1; 1;
while i1 <=m and i2 <=n do (( ) ( ))
begin
< b if (a[i1] [i2]) then
begin c [i]:=a[i1]; inc i1( ) end
else
begin c ; end; [i :=b] [i2] inc i2( )
; inc(i)
end;
while do (i1<=m) {kiểm tra danh sách a}
begin c ; end; [i i]:=a[ 1] inc inc(i1); (i)
while (i2<=n) do{kiểm tra danh sách b}
begin c end; [i i]:=b[ 2]; inc(i2) (;inc i)
end;
void TwoListMerging()
{
int i1,i2,i;
i=i1=i2=1;
while i1 <=m && i2 <=n (( ) ( ))
{
< b if (a[i1] [i2])
c ; [i++ i1++]=a[ ]
else
c ; [i++ i2++]=b[ ]
}
while m tra danh sách a (i1<=m)//kiể
c ; [i++ i1++]=a[ ]
while m tra danh sách b (i2<=n)//kiể
c ; [i++ i2++]=b[ ]
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.12
) Độ phức tạp là : O(m+n
3. Đặc điểm của danh sách đặc
a. m Ưu điể
Sử dụng 100% dung lượng ô nhớ để lưu trữ thông tin (không tốn bộ nhớ lưu
địa chỉ như danh sách liên kết).
Truy xuất trực tiếp phần tử List[i].
Dễ dàng tìm kiếm phần tử bằng phương pháp nhị phân ội suy, nếu danh , n
sách có thứ tự.
Dễ dàng cài đặt các phương pháp sắp xếp.
b. Nhược điểm
Lãng phí bộ nhớ.
Không phù hợp với phép chèn và loại bỏ. Số lần di chuyển trung bình cho
một phép chèn hoặc loại bỏ là n/2.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.13
III. DANH SÁCH LIÊN KẾT ĐƠN
1. Định nghĩa và khai báo
a. Định nghĩa: danh sách liên kết đơn ( là danh sách mà các simple linked list)
phần tử được nối kết với nhau nhờ các địa chỉ liên kết.
Mỗi phần tử của danh sách gọi là nút gồm có hai phần: Phần thông tin và phần kết
nối chứa địa chỉ của nút tiếp theo.
Hình sau minh hoạ danh sách liên kết. Mỗi nút có 2 ô, ô trái chứa thông tin, mũi
tên ô phải chỉ liên kết đến nút kế tiếp. Ký hiệu có nghĩa là nút không kết nối đến
phần tử khác.
plist
A
B
C
.....
Z
b. Khai báo
Trong PASCAL
Trong C
Type InfoType = <kiểu dữ liệu chứa
trong nút>;
NodePointer = ^ ; Node
Node = record
info : InfoType;
next NodePointer; :
end;
Var
plist, p NodePointer; {plist là con:
trỏ danh sách}
…..
new (p);{cấp phát nút động cho p}
…
dispose (p); {giải phóng nút p}
typedef <kiểu dữ liệu chứa trong nút>
InfoType;
struct Node {
InfoType info;
struct Node *next;
};
typedef struct Node *NodePointer;
NodePointer plist, p;/* plist là con trỏ
danh sách */
…
p = struct (NodePointer malloc) (sizeof(
Node)); /*cấp phát nút động cho p*/
…
free(p); //giải phóng nút p
2. Các phép toán
a. Khởi tạo: , . danh sách rỗng plist là con trỏ danh sách
Trong C
void Initialize ()
{
plist = NULL ;
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.14
b. Duyệt danh sách
Duyệt các phần tử thoả mãn < > để thực hiện công việc <điều kiện xử lý>.
Trong C
void Traverse ()
{
NodePointer p;
p plist; =
while p = NULL ( ! )
{
if <điều kiện>
<xử lý>;
p = p next; ->
}
}
Ví dụ. Tính số nút của danh sách.
Trong C
int ListNum ()
{
NodePointer p; int count;
p plist; count = ; = 0
while p = NULL ( ! )
{
count++;
p = p->next;
}
return count;
}
c. Tìm kiếm
Giả sử ta phải tìm phần tử có info . = InfoValue
Hàm Search trả về địa chỉ của phần tử tìm thấy đầu tiên, hoặc trả về giá trị nil
(trong PASCAL) hoặc NULL nếu không tìm thấy. (trong C)
Trường hợp danh sách không thứ tự
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.15
Trong PASCAL
Trong C
function Search(InfoValue:InfoType):
NodePointer;
var found: boolean; p : NodePointer;
begin
found := false;
p := pli st;
while p <> nil and not found ( ) ( ) do
if p^.info = InfoValue then
found := true
else
p := p^.next;
S earch := p;
end;
NodePointer Search InfoType InfoValue ( )
{
int found; NodePointer p;
found = 0;
p = pli st;
while p = NULL(( ! ) && (! found))
{
if (p->info == InfoValue )
found = ; 1
else
p = p->next;
}
return p;
}
Trường hợp danh sách có thứ tự tăng dần ( )
Trong PASCAL
Trong C
function Search InfoValue: InfoType ( );
NodePointer;
var p : NodePointer;
begin
p := plist;
while p <> nil and p^.info < ( ) (
InfoValue) do
p := p^.next;
if (p <> nil and p^.info > ) (
InfoValue) then
p := nil;
search := p;
end;
NodePointer Search InfoType InfoValue ( )
{
NodePointer p;
p = plist;
while p = NULL p->info < (( ! ) && (
InfoValue))
p = p->next;
if ((p != NULL) && (p->info >
InfoValue))
p = NULL;
p; return
}
d. Chèn phần tử vào danh sách
Giả sử ta chèn phần tử có nội dung NewInfo vào danh sách.
Trường hợp chèn vào đầu danh sách
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.16
Trong PASCAL
Trong C
procedure Insert(NewInfo: InfoType ; )
var p : NodePointer;
begin
new ; (p)
p^.info := NewInfo;
p^.next plist; :=
plist := p;
end;
void InfoType NewInfo Insert( )
{
NodePointer p;
p = struct (NodePointer malloc) (sizeof(
Node));
p->info = NewInfo; p->next plist; =
plist = p;
}
Trường hợp chèn vào cuối danh sách
Trong C
procedure Insert(NewInfo: InfoType);
var p, q : NodePointer;
begin
new(p); {tạo nút p}
p^.info := NewInfo;
p^.next ; := nil
{tìm nút cuối danh sách q}
q := pli st;
while q^.next <> nil do ( )
q := q^.next;
q^.next := p; {liên kết nút q đến p;
p trở thành nút cuối của danh
sách}
end;
void Insert(InfoType NewInfo)
{
NodePointer p, q;
p = struct (NodePointer malloc) (sizeof(
Node));
p->info = NewInfo;
p->next = NULL;
// tìm nút cuối danh sách q
q = pli st;
while q->next NULL ( != )
q = q->next;
q->next = p;// liên kết nút q đến p; p trở
thành nút cuối của danh sách
}
Trường hợp chèn vào sau phần tử q
Trong PASCAL
Trong C
procedure Insert(NewInfo: InfoType;
q: NodePointer );
var p : NodePointer;
begin
new (p);
p^.info := NewInfo;
p^.next := q^.next;
q^.next := p;
end;
void Insert(InfoType NewInfo, NodePointer q )
{
NodePointer p;
p = struct (NodePoin mallocter) (sizeof(
Node));
p->info = NewInfo;
p->next q->next; =
q->next = p;
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.17
e. Loại phần tử khỏi danh sách
Trường hợp loại phần tử đầu danh sách
Trong PASCAL
Trong C
procedure Delete;
var p : NodePointer;
begin
p := pli st;
plist := p^.next;
dispose (p);
end;
void Delete()
{
NodePointer p;
p = plist;
plist = p->next;
free(p);
}
Trường hợp loại phần tử sau phần tử q
Trong PASCAL
Trong C
procedure Delete(q : NodePointer);
var p : NodePointer;
begin
p := q^.next;
if p <> nil then
begin
q^.next := p^.next;
dispose (p);
end;
end;
void NodePointer q Delete( )
{
NodePointer p;
p = q->next;
if (p NULL != )
{
q->next = p->next;
free(p);
}
}
f. G hép nhiều danh sách thành danh sách mới
Ghép danh sách vào có chỉ điểm đầu plist2 sau phần tử q của danh sách khác có chỉ
điểm đầu là . plist1
Trong PASCAL
Trong C
procedure Insert(q: NodePointer );
var p : NodePointer;
begin
if plist2 <> nil then
b egin
p := pli st2;
{tìm phần tử cuối}
while p^.next <> nil do
p := p^.next;
p^.next := q^.next;
q^.next plist2; :=
end;
end;
void NodePointer q Insert( )
{
NodePointer p;
if (plist2 != NULL )
{
p = pli st2;
/*tìm phần tử cuối*/
while p->next NULL ( != )
p = p->next;
p->next = q->next;
q->next = plist2;
}
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.18
Ghép danh sách sách khác có có chỉ điểm đầu plist2 vào sau phần tử cuối của danh
chỉ điểm đầu là plist1.
Trong PASCAL
Trong C
procedure Insert;
var p : NodePointer;
begin
if plist2 <> nil then
begin
p := plist1;
{tìm phần tử cuối của danh
sách 1}
while p^.next <> nil do
p := p^.next;
p^.next := plist2;
end;
end;
void Insert( )
{
NodePointer p;
if (plist2 != NULL )
{
p = plist1;
/*tìm ph danh sáchần tử cuối
1*/
while p->next NULL ( != )
p = p->next;
p->next = plist2;
}
}
g. Trộn nhiều danh sách thành danh sách mới
Giả sử ta cần trộn hai danh sách có cùng thứ tự g dần của trường với hai tăn Info
chỉ điểm đầu thứ tự với chỉ điểm đầu là , danh sách plist1 plist2 thành plist3.
Trong PASCAL
Trong C
procedure Merge_List;
var p1,p2,p3 : NodePointer;
begin
new (plist3);
p3 := plist3;
p1 := plist1;
p2 := plist2;
while p1 <> nil and p2 <> nil ( ) ( ) do
.info > p2^.info then if p1^
begin
p3^.next := p2;
p3 := p2;
p2 := p2^.next;
end
else
begin
p3^.next := p1;
p3 := p1;
p1 := p1^.next;
{ while} end; kết thúc
void Merge_List ()
{
NodePointer p1,p2,p3 ;
plist3 =
( (NodePointer) (malloc sizeof struct Node));
p3 = plist3;
p1 = plist1;
p2 = plist2;
while NULL p2 NULL ((p1 != )&& ( != ))
p1->info > p2->info if ( )
{
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
else
{
p3->next = p1;
p3 = p1;
p1 = p1->next;
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.19
if p1 = nil then
p3^.next := p2
else
p3^.next := p1;
p3 := plist3;
plist3 := plist3^.next; {gán phần tử
đầu}
dispose (p3);
end;
}
if p1 = ( = NULL)
p3->next = p2;
else
p3->next = p1;
p3 = plist3;
plist3 = pli ->next; // st3 gán phần tử đầu
free(p3);
}
3. Đặc điểm của danh sách liên kết
a. Ưu điểm
- Thích hợp phép chèn, loại bỏ, trộn, ghép danh sách.
- Rất phù hợp với các loại danh sách có nhiều biến động.
- Sử dụng bộ nhớ lưu các nút trong danh sách linh hoạt và tiết kiệm.
b. Nhược điểm
- Tốn vùng nhớ cho chỉ điểm liên kết.
- Không thích hợp cho tìm kiếm.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.20
IV. DANH SÁCH ĐA LIÊN KẾT
1. Định nghĩa
Danh sách đa liên kết là danh sách mà các phần tử được nối kết với nhau nhờ
nhiều vùng liên kết.
Ví dụ: Danh sách số điện thoại.
Ta cần in anh sách theo khách hàng hoặc theo số điện thoại. Khi đó tổ chức lưu d
trữ bằng danh sách đa liên kết sẽ thuận lợi hơn.
2. Tổ chức danh sách đa liên kết
Mỗi phần tử của danh sách đa liên kết bao gồm một vùng thông tin info và các
vùng liên kết và ứng với các vùng liên kết ta có các chỉ điểm next1, , ..., next2 nextn
đầu plist1, plist2, ..., . plistn
Phần tử của danh sách đa liên kết có dạng:
info
next1
next2
.....
nextn
Khai báo
Trong PASCAL
Trong C
Type InfoType = record
info1 : ...;
info2 : ...;
...
end;
NodePointer = ^Node;
Node = record
info : InfoType;
next1 : NodePointer;
next2 NodePointer; :
. . .
end;
Var
plist1, plist2, … : NodePointer;
typedef struct data
{ … info1;
… info2;
…
} InfoType;
struct Node {
InfoType info;
struct Node *next1;
struct Node *next2;
…
};
typedef struct Node *NodePointer;
NodePointer plist plist1,1, plist2, … ;//
plist2, … là con trỏ danh sách
3. Các phép toán
a. Khởi tạo: danh sách rỗng.
Trong PASCAL
Trong C
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.21
Procedure Initialize;
begin
plist1 := nil;
plist2 := nil;
…
end;
void Initialize ()
{
plist1 NULL; =
plist2 = NULL;
…
}
b. Duyệt danh sách
Duyệt danh sách theo từng liên kết, giải thuật giống như giải thuật duyệt danh
sách liên kết đơn.
c. Chèn phần tử vào danh sách
Xét danh sách đa liên kết có hai vùng liên kết next1 và next2 đã sắp xếp theo
thứ tự tăng dần theo trong bản ghi kiểu InfoTinfo1 và info2 ype.
Giả sử ta chèn phần tử có nội dung với giá trị NewInfo NewInfo1 và vào NewInfo2
danh sách.
Hàm Insert_Element trả về địa chỉ của phần tử mới thêm vào.
Trong PASCAL:
Function Insert_Element(NewInfo: InfoType NodePointer; ):
var p , {*phần tử mới thêm vào*}
q , {*phần tử phụ trợ*}
before {*phần tử đứng trước p *}
: NodePointer;
begin
new(p);
p^.info := N ewInfo; {* ghi dữ liệu vào phần tử p *}
{tìm phần tử trước p theo next1 }
q := pli st1;
while q <> nil and q^.info.info1 < NewInfo1 do ( ) ( )
begin
before := q;
q := q^.next1
end;
if q = plist1 then
plist1 := p
else
before^.next1 := p;
p^.next1 := q;
{tìm p 2 } hần tử trước p theo next
q := pli st2;
while q <> nil and q^.info.info2 < NewInfo2 do ( ) ( )
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.22
begin
before := q;
q := q^.next2
end
if q = plist2 then
plist2 := p
else
before^.next2 := p;
p^.next2 := q;
Insert_Element := p
end;
Trong C:
NodePointer InfoType NewInfo Insert_Element( )
{
NodePointer p , / / *phần tử mới thêm vào*
q , /*phần tử phụ trợ*/
before; / / *phần tử đứng trước p *
p = struct Node ; (NodePoin mallocter) (sizeof( ))
p->info = NewInfo; /* ghi dữ liệu vào phần tử p */
//tìm phần tử trước p theo next1
q = pli st1;
while q = NULL q->info.info1 < NewInfo1 (( ! ) && ( ))
{
before = q;
q = q->next1;
}
if (q == plist1 )
plist1 = p;
else
before->next1 = p;
p->next1 = q;
//tìm phần tử trước p theo next2
q = pli st2;
while q = NULL nfo.info2 < NewInfo2 (( ! ) && (q->i ))
{
before = q;
q = q->next2;
}
if (q == plist2 )
plist2 = p;
else
before->next2 = p;
p->next2 = q;
return p;
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.23
}
d. Loại phần tử khỏi danh sách
Xét danh sách đa liên kết có hai vùng liên kết đã sắp xếp next1 và next2 theo
thứ tự tăng dần theo trong bản ghi kiểu InfoTinfo1 và info2 ype.
Giả sử ta cần loại bỏ phần tử có nội dung . Thủ tục sẽ cài DelInfo Delete_Element
đặt thuật toán xoá phần tử khỏi danh sách.
Trong PASCAL:
Procedure Delete_Element(DelInfo : InfoType );
var q , {* phần tử phụ trợ dò tìm *}
q1 , { next1 *} * phần tử tìm thấy theo
before {* phần tử đứng trước q *}
: NodePointer;
begin
q := pli st1;
{ dò tìm theo vùng next1 }
while q <> nil and q^.info <> DelInfo) do ( ) (
if q^.info.info1 > DelInfo.info1 then
q := nil
else
begin
before := q;
q := q^.next1
end;
if q <> nil then { tìm thấy phần tử cần loại bỏ }
begin
q1 := q;
{ ngắt next1 }
if q = plist1 then
plist1 := q^.next1
else
before^.next1 := q^.next1;
{ dò tìm theo vùng next2 }
q := pli st2;
while q <> q1 do
begin
before := q;
q := q^.next2
end;
if q = plist2 then
plist2 := q^.next2
else
before^.next2 := q^.next2;
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.24
end;
dispose(q)
end;
Trong C:
void Delete_Element InfoType DelInfo ( )
{
NodePointer q , /* phần tử phụ trợ dò tìm */
q1 , / next1 */ * phần tử tìm thấy theo
before; /* phần tử đứng trước q */
q = pli st1;
// dò tìm theo vùng next1
while info ((q = NULL! ) && (q-> != DelInfo ))
if q->info.info1 > DelInfo.info1 ( )
q = NULL;
else
{
before = q;
q = q->next1;
}
if (q = NULL ! ) // tìm thấy phần tử cần loại bỏ
{
q1 = q;
// ngắt next1
if q == pli ( st1)
plist1 = q->next1;
else
before->next1 = q->next1;
//dò tìm theo vùng next2
q = pli st2;
while q = q1 ( ! )
{
before = q;
q = q->next2;
}
if q == pli ( st2)
plist2 = q->next2;
else
before->next2 = q->next2;
}
free(q);
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.25
V. DANH SÁCH L IÊN KẾT KÉP
1. Định nghĩa
Danh sách liên kết kép (doubly linked list) là danh sách mà mỗi phần tử có hai
vùng liên kết. Một vùng liên kết chỉ đến phần tử đứng ngay trước nó, gọi là liên kết
ngược (previous) và một vùng liên kết chỉ đến phần tử đứng ngay sau nó, gọi là liên
kết thuận ( next).
Ví dụ. Danh sách có thể thêm vào hoặc lấy ra ở hai đầu.
2. Tổ chức danh sách liên kết kép
Mỗi phần tử của danh sách liên kết kép bao gồm một vùng thông tin info và các
vùng liên kết à ứng với các vùng liên kết ta có các chỉ điểm đầu previous và vnext
f lastirst và chỉ điểm cuối .
Phần tử của danh sách liên kết kép có dạng:
previous
info
next
Tổ chức danh sách liên kết kép như sau:
f irst
. . . . .
last
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.26
Khai báo
Trong PASCAL
Trong C
Type InfoType = record
Info1 : ...;
Info2 : ...;
...
end;
NodePointer = ^Node;
Node = record
info : InfoType;
previous NodePointer; :
next : NodePointer;
end;
Var f last : NodePointer;irst, { con trỏ đầu
và con trỏ cuối danh sách}
typedef struct data
{ … info1;
… info2;
…
} InfoType;
struct Node {
InfoType info;
struct Node *previous;
struct Node *next;
};
typedef struct Node *NodePointer;
NodePointer first, last, … con trỏ đầu;//
và con trỏ cuối danh sách
3. Các phép toán
a. Khởi tạo: danh sách rỗng.
Trong PASCAL
Trong C
procedure Initialize;
begin
first := nil; last := nil;
end;
void Initialize ()
{
first = NULL; last = NULL;
}
b. Duyệt danh sách
Duyệt danh sách theo liên kết thuận hoặc theo liên kết ngược, giải thuật giống như
giải thuật duyệt danh sách liên kết đơn.
c. Chèn phần tử vào danh sách:
Giả sử ta chèn phần tử có nội dung NewInfo.
Trường hợp thêm phần tử vào đầu danh sách
Hàm Insert_First trả về địa chỉ của phần tử mới thêm vào.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.27
Trong PASCAL
Trong C
function Insert_First NewInfo: InfoType( ):
NodePointer;
var p {*phần tử mới *}: NodePo inter;
begin
new (p);
p^.info := NewInfo;{* ghi dữ liệu vào
phần tử p *}
p^.p revious := nil;
p^.next := first;
if first <> nil then
first^.previous := p;
first := p;
if last = nil then
last := p;
Insert_First := p
end;
NodePointer Insert_First InfoType (
NewInfo)
{
NodePointer p ;//phần tử mới
p = struct(NodePo mallocinter) (sizeof(
Node));
p->info = NewInfo;// ghi dữ liệu vào
phần tử p
p->previous = NULL;
p->next = first;
if irst (f != NULL)
revious = p; first->p
first = p;
if (last = NULL )
= p; last
return p;
}
Trường hợp thêm phần tử vào sau phần tử q
Hàm Insert_Element trả về địa chỉ của phần tử mới thêm vào.
Trong PASCAL
Trong C
function Insert_Element NewInfo:(
InfoType; q: NodePointer ointer; ): NodeP
Var p, { *} r :*phần tử mới
NodePointer;
begin
new (p);
p^.info := NewInfo;{* ghi dữ liệu vào
phần tử p *}
p^.next := q^.n ext;
p^.p revious := q;
q^.n ext := p;
r := p^.n ext;
if r <> nil then {thêm vào giữa danh
sách}
r^.p revious := p
else {thêm vào cuối danh sách}
last := p;
Insert_Element := p
end;
NodePointer Insert_Element (InfoType
NewInfo, NodePointer q )
{
NodePointer p , ; /*phần tử mới */ r
p = struct(NodePoin mallocter) (sizeof(
Node));
p->info = NewInfo;// ghi dữ liệu vào
phần tử p
p->next = q- >next;
p- revious = q; >p
q- >next = p;
r = p- >next;
if (r != NULL) /*thêm vào giữa danh
sách */
r- revious = p; >p
else /*thêm vào cuối danh sách */
last = p;
return p;
}
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.28
Trường hợp thêm phần tử vào danh sách đã có thứ tự
Hàm vào. Insert_Element trả về địa chỉ của phần tử mới thêm
Trong PASCAL:
function Insert_Element NewInfo: InfoType NodePointer; ( ):
var p , { êm vào*} *phần tử mới th
q, before : NodePointer;
begin
new(p);
p^.info := NewInfo; {* ghi dữ liệu vào phần tử p *}
{tìm phần tử before ngay trước phần tử p}
q := f irst;
while q <> nil and q^.info < N do ( ) ( ewInfo)
begin
before := q;
q := q^.next;
end;
if q = f irst then {thêm vào đầu danh sách}
begin
p^.next := f irst;
p^.previous := nil;
if first <> nil then
first^.previous := p;
first := p;
if last = nil then
last := p;
end
else {thêm vào sau before}
begin
p^.next := before^.next;
p^.previous := before;
before^.next := p;
if q <> nil then {thêm vào giữa danh sách}
q^.previous := p
else {thêm vào cuối danh sách}
last := p;
end
Insert_Element := p
end;
Trong C:
NodePointer InfoType NewInfo Insert_Element( )
{
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.29
NodePointer p , /*phần tử mới thêm vào*/
q, before;
p = struct Node (NodePoin mallocter) (sizeof( ));
p->info = NewInfo;// ghi dữ liệu vào phần tử p
{tìm phần tử before ngay trước phần tử p}
q = f irst;
while q = NULL q->info < N (( ! ) && ( ewInfo))
{
before = q;
q = q->next;
}
if (q == first ) //thêm vào đầu danh sách
{
p->next = first;
p->previous NULL; =
if irst (f != NULL)
first->previous = p;
first = p;
if (last == NULL )
last = p;
}
else e *//*thêm vào sau befor
{
p->next = before->next;
p->previous = before;
before->next = p;
if (q = NULL ! ) //thêm vào giữa danh sách
q->previous = p;
else //thêm vào cuối danh sách
last = p;
}
return p;
}
d. Loại phần tử khỏi danh sách
Giả sử ta cần loại bỏ phần tử có địa chỉ . Thủ tục sẽ xoá phần p Delete_Element
tử khỏi danh sách.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.30
Trong PASCAL
Trong C
procedure Delete_Element(p : NodePointer ; )
var
before, {* phần tử đứng trước p *}
a fter {* phần tử đứng sau p *}
: NodePointer;
begin
before := p^.previous;
aft er := p^.next;
if before <> nil then
before^.next := p^.next;
if after <> nil then
after^.previous := p^.previous;
if p = first then
first := after;
if p = last then
last := before;
dispose (p)
end;
void Delete_Element NodePointer p ( )
{
NodePointer before, /* phần tử
đứng trước p */
after ; // phần tử đứng sau p
before = p->previous;
after = p->next;
if (before = NULL ! )
before->next = p- ext; >n
if (after = NULL ! )
after->previous = p->previous;
if (p == first )
first = after;
if (p == last )
last = before;
free(p);
}
e. Tìm kiếm phần tử trong danh sách.
Có thể tìm theo vùng bắt đầu từ chỉ điểm (thứ tự tăng dần) hoặc theo next first
vùng previous bắt đầu từ chỉ điểm last (thứ tự giảm dần). Giải thuật giống như
đối với danh sách liên kết đơn.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.31
VI. DANH SÁCH LIÊN KẾT VÒNG
1. Định nghĩa
Danh sách liên kết vòng là danh sách liên kết mà vùng liên kết của phần tử cuối
trỏ đến phần tử đầu.
Có thể biểu diễn các phần tử danh sách liên kết vòng như sau:
first
. . . . .
Khai báo
Trong PASCAL
Trong C
Type InfoType = <kiểu dữ liệu chứa trong
phần tử>;
NodePointer = ^Node;
Node = record
info : InfoType;
next NodePointer; :
end;
Var first, p NodePointer ;: { first là con trỏ
danh sách}
struct Node {
InfoType info;
struct Node *next;
};
typedef struct Node *NodePointer;
NodePointer first, p;// first là con trỏ danh
sách
p = struct (NodePointer malloc) (sizeof(
Node));//cấp phát nút động cho p
2. Các phép toán trên danh sách
Các phép toán , duyệt, tìm kiếm, chèn xoá tương tự như trên danh sách liên kết
đơn. Tuy nhiên cần chú ý là vùng liên kết của phần tử cuối trỏ đến phần tử đầu.
Danh sách liên kết vòng thích hợp với các phép tách và ghép danh sách.
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.32
chèn Thủ tục phần tử vào cuối danh sách
Trong PASCAL
Trong C
procedure Insert(NewInfo: InfoType );
var p, q : NodePointer;
begin
{tạo nút p}
new (p);
p^.info := NewInfo;
p^.next ; := nil
{tìm nút cuối danh sách q}
q := first;
while q^.next <> first do ( )
q := q^.next;
q^.next } := p; {liên kết nút q đến p
p^.next := first;{ p trở thành nút cuối
của danh sách}
end;
void InfoType NewInfo Insert( )
{
NodePointer p, q;
p = struct(NodePointer malloc) (sizeof(
Node));
p->info = NewInfo;
p->next = NULL;
// tìm nút cuối danh sách q
q = fir st;
while q->next first ( != )
q = q->next;
q->next = p;// liên kết nút q đến p;
p->next = first;// p trở thành nút cuối
của danh sách
}
Thủ tục loại phần tử sau phần tử q
Trong PASCAL
Trong C
procedure Delete(q : NodePointer );
var p,r : NodePointer;
begin
p := q^.next;
if p <> nil then
begin
q^.next := p^.next;
end;
if p = first then
begin
{tìm nút cuối danh sách r}
r := first;
while next <> first do (r^. )
next; r := r^.
:= p^.next; first
r^.next := first;
end;
dispose (p);
end;
void NodePointer q Delete( )
{
NodePointer p, r;
p = q->next;
if (p NULL != )
{
q->next = p->next;
}
if (p ==first )
{
r = fir st;
while r->next first ( != )
r = r->next;
= p->next; first
r->next = first;
}
free(p);
}
Ví dụ: Bài toán Josephus
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Chương II Cấu trúc dữ liệu danh sách. II.33
Một nhóm binh sĩ bị kẻ thù bao vây và họ phải chọn một người đi cầu cứu viện n
binh. Việc chọn người được thực hiện như sau.
Cho trước một số nguyên Các binh sĩ xếp thành vòng tròn đánh s gọi là bước đếm.
số 1, 2, ... , n bắt đầu từ người chỉ huy.
Đếm từ người thứ nhất, khi đạt đến s thì binh sĩ tương ứng bị loại ra khỏi vòng.
Lại bắt đầu đếm từ người tiếp theo, khi đạt đến s thì binh sĩ tương ứng bị loại ra
khỏi vòng.
Quá trình này tiếp tục cho đến khi chỉ còn lại một binh sĩ, và người này chính là
người được điều đi cầu cứu viện binh.
Sau đây là chương trình cài đặt giải thuật của bài toán.
Trong PASCAL
Trong C
Type
NodePointer = ^Node;
Node = record
info : integer;
next NodePointer; :
end;
Var q, p, f NodePointer; irst :
n, {số binh sĩ}
s , {bước đếm}
i : integer;
Procedure Initialize; {*** khởi tạo ***}
begin
first := nil;
write( )„cho số binh sĩ : „ ; readln(n);
write(„cho số bước đếm: „); readln (s);
end;
Procedure CreateRing; {Tạo danh sách}
var p, last : NodePointer;
begin
{tạo nút đầu tiên}
new(first);
first^.info := 1;
first^.next := nil;
{nối tiếp n phần tử }-1
last := first;
for i := 2 to n do
begin
new (p);
p^.info := i;
struct node {
int v;/*dinh ke*/
struct node *link;
};
typedef struct node *nodeptr;
int n, s;
nodeptr first, last;
void addnode(int i);
void init(void); /*** khởi tạo ***/
main()
{
nodeptr p1, p;
int k, i;
clrscr();
printf("nhap n, s = " );
scanf("%d %d", &n, &s );
// Tạo danh sách
init();
for (k = 2; k <= n; k++ )
addnode (k);
//Xóa n-1 nút
p1 = last;
for (k = 1; k <= n- ; k++ 1 )
{
i = ; i < s; i++ for ( 1 )
p1 = p1->link;
p = p1->link;
p1->link = p->link;
free(p);
| 1/36
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật CHƯƠNG II
CẤU TRÚC DỮ LIỆU DANH SÁCH
Chương II Cấu trúc dữ liệu danh sách . II.1
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
I. TỔNG QUAN VỀ DANH SÁCH 1. Định nghĩa
Danh sách (List) là dãy các phần tử
a1, ..., an (n  1)
với tính chất: nếu biết được ai sẽ biết ai+1.
Danh sách được sắp xếp tuyến tính theo vị trí của chúng.
Số các phần tử n gọi là độ dài của danh sách. Nếu n = 0, thì ta có danh sách rỗng.  Ví dụ
- Danh sách nhân viên trong cơ quan.
- Danh sách sinh viên của lớp. - Danh sách các môn học.
- Danh sách các số tự nhiên không quá 100.
2. Các phép toán trên danh sách
Để tạo lập, cập nhật, khai thác danh sách, người ta định nghĩa các phép toán sau.
a. Phép duyệt danh sách
Duyệt danh sách là duyệt qua tất cả phần tử danh sách thoả mãn <điều kiện> nào
đó để thực hiện công việc (chẳng hạn như hiển thị phần tử).
 Ví dụ: Liệt kê danh sách nữ nhân viên trong cơ quan.
b. Phép tìm kiếm
Tìm kiếm là thao tác tìm phần tử trong danh sách thoả mãn điều kiện nào đó. Kết
quả phép tìm kiếm có thể là tìm thấy hoặc không tìm thấy. Sau khi tìm thấy phần tử
cần tìm ta có thể thực hiện các phép toán đối với phần tử đó như sửa đổi hay xoá.
Ví dụ: Trong danh sách nhân viên trong cơ quan, tìm nhân viên có tên là “Trần Công Minh”.
c. Thêm phần tử vào danh sách
Đây là thao tác thêm phần tử mới vào danh sách. Phần tử có thể được thêm vào
cuối danh sách, đầu danh sách hoặc chèn vào giữa danh sách. Nếu danh sách đã đầy,
tức là số phần tử của danh sách đã bằng số cực đại cho phép thì phép toán thêm không
Chương II Cấu trúc dữ liệu danh sách . II.2
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
thực hiện được nữa. Nếu danh sách chưa đầy thì có thể thêm phần tử mới vào danh
sách và độ dài (số phần tử) của danh sách tăng thêm 1.
 Ví dụ: Trong danh sách nhân viên trong cơ quan, thêm nhân viên mới hợp đồng có
tên là “Trần Công Minh”.
d. Loại bỏ phần tử khỏi danh sách
Đây là thao tác loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ phần tử, nếu
chưa xác định được phần tử loại bỏ, thì phải thực hiện phép tìm kiếm. Nếu không tìm
thấy thì không thể thực hiện phép loại bỏ. Nếu tìm thấy thì có thể thực hiện phép loại
bỏ và độ dài (số phần tử) của danh sách giảm đi 1.
Phần tử loại bỏ có thể ở cuối danh sách, đầu danh sách hoặc giữa danh sách.
Ví dụ. Trong danh sách nhân viên trong cơ quan, loại bỏ nhân viên cắt hợp đồng có
tên là “Trần Công Minh”.
e. Sửa đổi phần tử trong danh sách
Đây là thao tác hiệu chỉnh phần tử trong danh sách. Trước khi hiệu chỉnh phần tử,
nếu chưa xác định được phần tử hiệu chỉnh, thì phải thực hiện phép tìm kiếm. Nếu
không tìm thấy thì không thể thực hiện phép hiệu chỉnh. Nếu tìm thấy thì có thể thực
hiện phép hiệu chỉnh. Số phần tử của danh sách không thay đổi
Phần tử hiệu chỉnh có thể ở cuối danh sách, đầu danh sách hoặc giữa danh sách.
 Ví dụ. Trong danh sách nhân viên trong cơ quan, hiệu chỉnh mức lương cho nhân
viên có tên là “Trần Công Minh”.
f. Sắp xếp thứ tự danh sách
Đây là thao tác sắp xếp lại thứ tự các phần tử trong danh sách theo một khoá nào
đó. Thứ tự phần tử có thể thay đổi, nhưng số phần tử vẫn giữ nguyên.
 Ví dụ: Sắp xếp danh sách nhân viên trong cơ quan theo họ tên hoặc theo mức lương.
g. Tách một danh sách thành nhiều danh sách
Đây là thao tác tách một phần hoặc lấy tất cả phần tử của một danh sách đưa sang danh sách khác.
 Ví dụ. Từ danh sách nhân viên trong cơ quan tách riêng danh sách nữ nhân viên.
h. Ghép nhiều danh sách thành danh sách mới
Đây là thao tác lấy tất cả phần tử từ các danh sách khác nhau tạo thành một danh
sách mới. Các phần tử của cùng một danh sách con vẫn xếp cạnh nhau.
Chương II Cấu trúc dữ liệu danh sách . II.3
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
 Ví dụ. Từ danh sách nhân viên của các phòng ghép lại thành danh sách nhân viên của toàn cơ quan.
i. Trộn nhiều danh sách thành danh sách mới
Đây là thao tác lấy tất cả phần tử từ các danh sách khác nhau tạo thành một danh
sách mới theo một cấu trúc nào đó. Các phần tử của cùng một danh sách con có thể sẽ bị xáo trộn.
 Ví dụ. Từ danh sách nhân viên của các phòng đã được sắp xếp theo họ tên trộn lại
thành danh sách nhân viên của toàn cơ quan sắp xếp theo họ tên.
Chương II Cấu trúc dữ liệu danh sách . II.4
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật II. DANH SÁCH ĐẶC
1. Định nghĩa và khai báo
a. Định nghĩa
Danh sách đặc (condensed list) hay còn gọi là danh sách kề (contiguous list) là
danh sách mà các phần tử được lưu trữ kế tiếp nhau trong bộ nhớ, phần tử thứ i 1 +
đứng ngay sau phần tử thứ i.
Hình sau mô tả danh sách đặc, trong đó các phần tử có kích thước bằng nhau và xếp kế tiếp nhau. a1 a2 ... ... ai ai+1 ... .... a a n1 n add[1] add[i] d add[n]
Nếu các phần tử có độ dài d byte như nhau và ký hiệu địa chỉ phần tử i là
add[i], thì ta sử dụng công thức tính địa chỉ như sau:
add[i] = add[1] + (i1)*d b. Khai báo  Trong PASCAL: Const ElemNo = ; Type
InfoType = các trường không khóa>; KeyType = >; Element = record key : KeyType; {khoá}
info : InfoType; {dữ liệu} end;
ListType = array[1 .. ElemNo] of Element; Var Li t s : ListType;
ListNum: integer; {số phần tử của danh sách, không được vượt quá ElemNo}  Trong C:
#define ElemNo ố phần tử tối đa của danh sách>
typedef các trường không khóa > InfoType;
typedef các trường khóa > KeyType; struct Element { KeyType key; //khoá
InfoType info; // dữ liệu };
struct Element List[ElemNo+1];
int ListNum; // số phần tử của danh sách, không được vượt quá ElemNo
Chương II Cấu trúc dữ liệu danh sách . II.5
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật 2. Các phép toán
a. Khởi tạo danh sách
Ban đầu danh sách rỗng, nên ta khởi tạo đặt độ dài danh sách ListNum = 0. Trong PASCAL Trong C procedure Initialize;
void Initialize() begin { ListNum := 0; ListNum = 0; end; }
b. Duyệt danh sách
Duyệt danh sách thoả mãn <điều kiện> để Trong PASCAL Trong C procedure Traverse; void Traverse()
var i: integer; {biến cục bộ} { begin
int i; //biến cục bộ
for i := 1 to ListNum do
for ( i = 1; i <= ListNum; i++)
if <điều kiện> then
if <điều kiện> i]> { end; i]> } }
c. Tìm kiếm tuyến tính
Giả sử ta phải tìm phần tử có trường Key = KeyValue.
Hàm Search trả về chỉ số của phần tử tìm thấy đầu tiên, hoặc trả về giá trị 1 nếu không tìm thấy.
 Trường hợp danh sách không thứ tự  Trong PASCAL:
function Search(KeyValue: KeyType): integer; var vitri: integer; begin vitri := 1;
while (vitri <= ListNum) and (List[vitri].key <> KeyValue) do
vitri := vitri + 1;
if (vitri <= ListNum) then search := vitri else
search := -1;{không tìm thấy} end;
Chương II Cấu trúc dữ liệu danh sách . II.6
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật  Trong C:
int Search(KeyType KeyValue) { int vitri; vitri = 1;
while ((vitri <= ListNum) && (List[vitri].Key != KeyValue)) vitri++;
if (vitri == ListNum+1) return -1; //không tìm thấy
else return vitri; //tìm thấy }
 Trường hợp danh sách có thứ tự  Trong PASCAL:
function Search(KeyValue: KeyType): integer; var found: boolean; vitri : integer; begin found := false; vitri := 1;
while (vitri <= ListNum) and (not found) do
if List[vitri].key = KeyValue then found := true else
if (List[vitri].key > KeyValue) then vitri := ListNu m + 1 else
vitri := vitri + 1; if found then search := vitri else
search := -1; {không tìm thấy} end;  Trong C:
int Search(KeyType KeyValue) { int vitri; vitri = 1;
while ((vitri <= ListNum) && (List[vitri].Key < KeyValue)) vitri++;
if (vitri == ListNum+1) return -1; //không tìm thấy
else return (List[vitri].Key == KeyValue ? vitri : -1); }
Chương II Cấu trúc dữ liệu danh sách . II.7
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật  Độ phức tạp:
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
Ghi chú : n ký hiệu số phần tử của danh sách.
d. Tìm kiếm nhị phân
Phương pháp này chỉ áp dụng với danh sách đặc. Điều kiện để có thể áp dụng giải
thuật là danh sách phải được sắp xếp thứ tự theo trường tìm kiếm Key.
Giả sử ta phải tìm phần tử có trường Key = KeyValue.
Hàm Search trả về chỉ số của phần tử tìm thấy đầu tiên, hoặc trả về giá trị -1 nếu không tìm thấy. Trong PASCAL Trong C function
Search(KeyValue:
KeyType):int Search(KeyType KeyValue) integer; { var found: boolean; int found; i, min, max : integer; int i, min, max ; begin found = 0; found := false; min = 1; min := 1; max = ListNum; max := ListNum;
while ((min <= max) && (!found))
while (min <= max) and (not found) do { begin
i = (min + max) / 2;
i := (min + max) div 2;
if (List[i].key == KeyValue)
if List[i].key = KeyValue then found = 1; found := true else else
if (List[i].key < KeyValue)
if List[i].key < KeyValue then min = i + 1; min := i + 1 else else
max = i 1;
max := i 1; } end;
if ( found) if found then return i ; search := i else else return 1;
search := 1; {không tìm thấy} } end;
 Độ phức tạp thuật toán là : O(log2(n)).
e. Tìm kiếm nội suy
Chương II Cấu trúc dữ liệu danh sách . II.8
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Yêu cầu để có thể áp dụng giải thuật là danh sách phải được sắp xếp thứ tự.
Giải thuật là cải tiến của phương pháp tìm kiếm nhị phân.
Xét biểu thức tính điểm giữa i ở thuật toán nhị phân
(min + max) div 2
Biểu thức trên có thể xấp xỉ bằng
min + 0.5 (max min)
Trong thuật toán này ta thay hệ số 0.5 bằng
KeyValueList[min]. key k =
List[max]. key List[min]. key  Trong PASCAL:
function Search(KeyValue: KeyType): integer; var found: boolean; i, min, max : integer; k : real; begin found := false; min := 1; max := ListNum;
while (min <= max) and (not found) do begin
k := (KeyValue - List[min].key) / (List[max].key - List[min].key);
i := min + round(k * (max - min));
if (List[i].key = KeyValue) then found := true else
if (List[i].key < KeyValue) then min := i + 1 else max := i - 1; end; if found then search := i else search := -1; end;  Trong C:
int Search(KeyType KeyValue) { int found ; int i, min, max ;
Chương II Cấu trúc dữ liệu danh sách . II.9
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật float k ; found = 0; min = 1; max = ListNum;
while ((min <= max) &
& !found) {
k = (KeyValue - List[min].key) / (List[max].key - List[min].key);
i = min + k * (max - min);
if (List[i].key == KeyValue) found = 1; else
if (List[i].key < KeyValue) min = i + 1; else max = i - 1; }
if (found) then return i; else return -1; }
 Độ phức tạp là : O(log2(n))
f. Chèn phần tử vào danh sách
Giả sử ta chèn phần tử mới NewElem vào vị trí thứ k. Khi đó các phần tử từ
List[k] đến List[ListNum] được di chuyển ra sau 1 vị trí và số phần tử danh sách ListNum tăng lên 1. Trong PASCAL Trong C
procedure Insert(k:integer;NewElem:Element); void Insert(in
t k, Element NewElem) var i: integer; { begin int i ;
for i:= ListNum downto k do
for (i = ListNum ; i >= k; i--)
List[i+1] := List[i];
List[i+1] = List[i];
List[k] := NewElem;
List[k] = NewElem;
ListNum := ListNum + 1; ListNum++; end; }  Độ phức tạp
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
Chương II Cấu trúc dữ liệu danh sách . II.10
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
g. Loại phần tử khỏi danh sách
Giả sử ta loại phần tử List[k] khỏi danh sách. Khi đó các phần tử từ List[k+1] đến
List[ListNum] được di chuyển về trước 1 vị trí và số phần tử danh sách ListNum giảm đi 1. Trong PASCAL Trong C
procedure Delete(k: integer);
void Delete(int k) var i: integer; { begin int i ;
for i:= k to ListNum-1 do
for (i = k; i <= ListNum–1; i++)
List[i] := List[i+1];
List[i] = List[i+1]; ListNum := ListNu m - 1; ListNum--; end; }  Độ phức tạp
- Độ phức tạp trung bình : O(n/2)
- Độ phức tạp xấu nhất : O(n)
h. Trộn danh sách
Giả sử có hai danh sách số nguyên a[1..m] và b[1..n] đã sắp xếp tăng dần. Hãy
trộn hai danh sách này thành danh sách c[1..m+n] cũng được sắp xếp tăng dần. Trong PASCAL Trong C
procedure TwoListMerging;
void TwoListMerging() var i1,i2 i , : integer; { begin int i1,i2,i ;
i1:=1; i2:=1;i:=1; i=i1=i2=1;
while ((i1 <=m) and (i2 <=n)) do
while ((i1 <=m) && (i2 <=n)) begin {
if (a[i1]< b[i2]) then
if (a[i1]< b[i2])
begin c[i]:=a[i1]; inc(i1) end
c[i++]=a[i1++]; else else
begin c[i]:=b[i2]; inc(i2) end;
c[i++]=b[i2++]; inc(i); } end;
while (i1<=m)//kiểm tra danh sách a
while (i1<=m) do{kiểm tra danh sách a}
c[i++]=a[i1++];
begin c[i]:=a[i1]; inc(i1);inc(i) end; while (i2<=n)//kiểm tra danh sách b
while (i2<=n) do{kiểm tra danh sách b}
c[i++]=b[i2++];
begin c[i]:=b[i2]; inc(i2);inc(i) end; } end;
Chương II Cấu trúc dữ liệu danh sách . II.11
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
 Độ phức tạp là : O(m+n)
3. Đặc điểm của danh sách đặc
a. Ưu điểm
Sử dụng 100% dung lượng ô nhớ để lưu trữ thông tin (không tốn bộ nhớ lưu
địa chỉ như danh sách liên kết).
Truy xuất trực tiếp phần tử List[i].
Dễ dàng tìm kiếm phần tử bằng phương pháp nhị phân, nội suy, nếu danh sách có thứ tự.
Dễ dàng cài đặt các phương pháp sắp xếp.
b. Nhược điểm Lãng phí bộ nhớ.
Không phù hợp với phép chèn và loại bỏ. Số lần di chuyển trung bình cho
một phép chèn hoặc loại bỏ là n/2.
Chương II Cấu trúc dữ liệu danh sách . II.12
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
III. DANH SÁCH LIÊN KẾT ĐƠN
1. Định nghĩa và khai báo
a. Định nghĩa: danh sách liên kết đơn (simple linked list) là danh sách mà các
phần tử được nối kết với nhau nhờ các địa chỉ liên kết.
Mỗi phần tử của danh sách gọi là nút gồm có hai phần: Phần thông tin và phần kết
nối chứa địa chỉ của nút tiếp theo.
Hình sau minh hoạ danh sách liên kết. Mỗi nút có 2 ô, ô trái chứa thông tin, mũi
tên ô phải chỉ liên kết đến nút kế tiếp. Ký hiệu  có nghĩa là nút không kết nối đến phần tử khác. plist A  B  C  ..... Z  b. Khai báo Trong PASCAL Trong C
Type InfoType = typedef nút> trong nút>; InfoType; NodePointer = ^Node; struct Node { Node = record InfoType info; info : InfoType; struct Node *next; next : NodePointer; }; end;
typedef struct Node *NodePointer; Var
NodePointer plist, p;/* plist là con trỏ
plist, p : NodePointer; {plist là con danh sách */ trỏ danh sách} … …..
p = (NodePointer)malloc(sizeof(struct
new(p);{cấp phát nút động cho p}
Node)); /*cấp phát nút động cho p*/ … …
dispose(p); {giải phóng nút p}
free(p); //giải phóng nút p
2. Các phép toán
a. Khởi tạo: danh sách rỗng, plist là con trỏ danh sách. Trong PASCAL Trong C procedure Initialize;
void Initialize() begin { plist := nil; plist = NULL; end; }
Chương II Cấu trúc dữ liệu danh sách . II.13
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
b. Duyệt danh sách
Duyệt các phần tử thoả mãn <điều kiện> để thực hiện công việc . Trong PASCAL Trong C procedure Traverse; void Traverse() var p : NodePointer; { begin NodePointer p; p := plist; p = plist;
while (p <> nil) do
while (p != NULL) begin {
if <điều kiện> then
if <điều kiện> ; p := p^.next; p = p->next; end; } end; }
 Ví dụ. Tính số nút của danh sách. Trong PASCAL Trong C
function ListNum : integer; int ListNum()
var count:integer; p:NodePointer ; { begin
NodePointer p; int count;
p:=plist; count:=0;
p = plist; count = 0;
while (p <> nil) do
while (p != NULL) begin { count:=count+1; count++; p := p^.next; p = p->next; end; } ListNum := count; return count; end; } c. Tìm kiếm
Giả sử ta phải tìm phần tử có info = InfoValue.
Hàm Search trả về địa chỉ của phần tử tìm thấy đầu tiên, hoặc trả về giá trị nil
(trong PASCAL) hoặc NULL (trong C) nếu không tìm thấy.
Trường hợp danh sách không thứ tự
Chương II Cấu trúc dữ liệu danh sách . II.14
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Trong PASCAL Trong C function
Search(InfoValue:InfoType): NodePointer Search(InfoType InfoValue) NodePointer; {
var found: boolean; p : NodePointer;
int found; NodePointer p; begin found = 0; found := false; p = plist ; p := plist ;
while ((p != NULL) && (! found))
while (p <> nil) and (not found) do {
if p^.info = InfoValue then
if (p->info == InfoValue) found := true found = 1; else else p := p^.next; p = p->next; Search := p; } end; return p; }
Trường hợp danh sách có thứ tự (tăng dần) Trong PASCAL Trong C
function Search(InfoValue: InfoType); NodePointer Search(InfoType InfoValue) NodePointer; { var p : NodePointer; NodePointer p; begin p = plist; p := plist;
while ((p != NULL) && (p->info <
while (p <> nil) and (p^.info < InfoValue)) InfoValue) do p = p->next; p := p^.next;
if ((p != NULL) && (p->info >
if (p <> nil) and (p^.info > InfoValue)) InfoValue) then p = NULL; p := nil; return p; search := p; } end;
d. Chèn phần tử vào danh sách
Giả sử ta chèn phần tử có nội dung NewInfo vào danh sách.
Trường hợp chèn vào đầu danh sách
Chương II Cấu trúc dữ liệu danh sách . II.15
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Trong PASCAL Trong C
procedure Insert(NewInfo: InfoType); void Insert(InfoType NewInfo) var p : NodePointer; { begin NodePointer p; new(p);
p = (NodePointer)malloc(sizeof(struct p^.info := NewInfo; Node)); p^.next := plist;
p->info = NewInfo; p->next = plist; plist := p; plist = p; end; }
Trường hợp chèn vào cuối danh sách Trong PASCAL Trong C
procedure Insert(NewInfo: InfoType); void Insert(InfoType NewInfo) var p, q : NodePointer; { begin NodePointer p, q;
new(p); {tạo nút p}
p = (NodePointer)malloc(sizeof(struct p^.info := NewInfo; Node)); p^.next := nil; p->info = NewInfo;
{tìm nút cuối danh sách q} p->next = NULL; q := plist ;
// tìm nút cuối danh sách q
while (q^.next <> nil) do q = plist ; q := q^.next;
while (q->next != NULL)
q^.next := p; {liên kết nút q đến p; q = q->next;
p trở thành nút cuối của danh
q->next = p;// liên kết nút q đến p; p trở sách}
thành nút cuối của danh sách end; }
 Trường hợp chèn vào sau phần tử q Trong PASCAL Trong C
procedure Insert(NewInfo: InfoType; void Insert(InfoType NewInfo, NodePointer q) q: NodePointer); { var p : NodePointer; NodePointer p; begin
p = (NodePointer)malloc(sizeof(struct new(p); Node)); p^.info := NewInfo; p->info = NewInfo; p^.next := q^.next;
p->next = q->next; q^.next := p; q->next = p; end; }
Chương II Cấu trúc dữ liệu danh sách . II.16
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
e. Loại phần tử khỏi danh sách
 Trường hợp loại phần tử đầu danh sách Trong PASCAL Trong C procedure Delete; void Delete() var p : NodePointer; { begin NodePointer p; p := plist ; p = plist; plist := p^.next; plist = p->next;
dispose(p); free(p); end; }
 Trường hợp loại phần tử sau phần tử q Trong PASCAL Trong C
procedure Delete(q : NodePointer);
void Delete(NodePointer q) var p : NodePointer; { begin NodePointer p; p := q^.next; p = q->next; if p <> nil then
if (p != NULL) begin { q^.next := p^.next;
q->next = p->next;
dispose(p); free(p); end; } end; }
f. Ghép nhiều danh sách thành danh sách mới
 Ghép danh sách có chỉ điểm đầu plist2 vào sau phần tử q của danh sách khác có chỉ
điểm đầu là plist . 1 Trong PASCAL Trong C
procedure Insert(q: NodePointer);
void Insert(NodePointer q) var p : NodePointer; { begin NodePointer p;
if plist2 <> nil then
if (plist2 != NULL) begin { p := plist2; p = plist2;
{tìm phần tử cuối}
/*tìm phần tử cuối*/
while p^.next <> nil do
while (p->next != NULL) p := p^.next; p = p->next; p^.next := q^.next;
p->next = q->next; q^.next := plist2; q->next = plist2; end; } end; }
Chương II Cấu trúc dữ liệu danh sách . II.17
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
 Ghép danh sách có chỉ điểm đầu plist2 vào sau phần tử cuối của danh sách khác có
chỉ điểm đầu là plist1. Trong PASCAL Trong C procedure Insert; void Insert( ) var p : NodePointer; { begin NodePointer p;
if plist2 <> nil then
if (plist2 != NULL) begin { p := plist1; p = plist1;
{tìm phần tử cuối của danh
/*tìm phần tử cuối danh sách sách 1} 1*/
while p^.next <> nil do
while (p->next != NULL) p := p^.next; p = p->next; p^.next := plist2; p->next = plist2; end; } end; }
g. Trộn nhiều danh sách thành danh sách mới
Giả sử ta cần trộn hai danh sách có cùng thứ tự tăng dần của trường Info với hai
chỉ điểm đầu plist1, plist
2 thành danh sách thứ tự với chỉ điểm đầu là plist3. Trong PASCAL Trong C procedure Merge_List;
void Merge_List()
var p1,p2,p3 : NodePointer; { begin NodePointer p1,p2,p3 ;
new(plist3); plist3 = p3 := plist3;
(NodePointer)malloc(sizeof(struct Node)); p1 := plist1; p3 = plist3; p2 := plist2; p1 = plist1;
while (p1 <> nil) and (p2 <> nil) do p2 = plist2;
if p1^.info > p2^.info then
while ((p1 != NULL)&& (p2 != NULL)) begin if
(p1->info > p2->info) p3^.next := p2; { p3 := p2; p3->next = p2; p2 := p2^.next; p3 = p2; end p2 = p2->next; else } begin else p3^.next := p1; { p3 := p1; p3->next = p1; p1 := p1^.next; p3 = p1;
end; {kết thúc while} p1 = p1->next;
Chương II Cấu trúc dữ liệu danh sách . II.18
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật if p1 = nil then } p3^.next := p2
if (p1 == NULL) else p3->next = p2; p3^.next := p1; else p3 := plist3; p3->next = p1;
plist3 := plist3^.next; {gán phần tử p3 = plist3; đầu} plist3 = plist -
3 >next; //gán phần tử đầu
dispose(p3);
free(p3); end; }
3. Đặc điểm của danh sách liên kết
a. Ưu điểm
- Thích hợp phép chèn, loại bỏ, trộn, ghép danh sách.
- Rất phù hợp với các loại danh sách có nhiều biến động.
- Sử dụng bộ nhớ lưu các nút trong danh sách linh hoạt và tiết kiệm.
b. Nhược điểm
- Tốn vùng nhớ cho chỉ điểm liên kết.
- Không thích hợp cho tìm kiếm.
Chương II Cấu trúc dữ liệu danh sách . II.19
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
IV. DANH SÁCH ĐA LIÊN KẾT 1. Định nghĩa
Danh sách đa liên kết là danh sách mà các phần tử được nối kết với nhau nhờ nhiều vùng liên kết.
 Ví dụ: Danh sách số điện thoại.
Ta cần in danh sách theo khách hàng hoặc theo số điện thoại. Khi đó tổ chức lưu
trữ bằng danh sách đa liên kết sẽ thuận lợi hơn.
2. Tổ chức danh sách đa liên kết
Mỗi phần tử của danh sách đa liên kết bao gồm một vùng thông tin info và các
vùng liên kết next1, next2, ..., nextn và ứng với các vùng liên kết ta có các chỉ điểm
đầu plist1, plist2, ..., plist . n
Phần tử của danh sách đa liên kết có dạng: info next1 next2 ..... nextnKhai báo Trong PASCAL Trong C Type InfoType = recor d typedef struct data info1 : ...; { … info1; info2 : ...; … info2; ... … end; } InfoType; NodePointer = ^Node; struct Node { Node = record InfoType info; info : InfoType; struct Node *next1; next1 : NodePointer; struct Node *next2; next2 : NodePointer; … . . . }; end;
typedef struct Node *NodePointer; Var
NodePointer plist1, plist2, … ;// plist1,
plist1, plist2, … : NodePointer;
plist2, … là con trỏ danh sách 3. Các phép toán
a. Khởi tạo: danh sách rỗng. Trong PASCAL Trong C
Chương II Cấu trúc dữ liệu danh sách . II.20
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Procedure Initialize;
void Initialize() begin { plist1 := nil; plist1 = NULL; plist2 := nil; plist2 = NULL; … … end; }
b. Duyệt danh sách
Duyệt danh sách theo từng liên kết, giải thuật giống như giải thuật duyệt danh sách liên kết đơn.
c. Chèn phần tử vào danh sách
Xét danh sách đa liên kết có hai vùng liên kết next1 và next2 đã sắp xếp theo
thứ tự tăng dần theo info1 và info2 trong bản ghi kiểu InfoType.
Giả sử ta chèn phần tử có nội dung NewInfo với giá trị NewInfo1 và NewInfo2 vào danh sách.
Hàm Insert_Element trả về địa chỉ của phần tử mới thêm vào.  Trong PASCAL:
Function Insert_Element(NewInfo: InfoType): NodePointer;
var p , {*phần tử mới thêm vào*}
q , {*phần tử phụ trợ*}
before {*phần tử đứng trước p *} : NodePointer; begin new(p);
p^.info := NewInfo; {* ghi dữ liệu vào phần tử p *}
{tìm phần tử trước p theo next1 } q := plist1;
while (q <> nil) and (q^.info.info1 < NewInfo1) do begin before := q; q := q^.next1 end; if q = plist1 then plist1 := p else before^.next1 := p; p^.next1 := q;
{tìm phần tử trước p theo next2 } q := plist2;
while (q <> nil) and (q^.info.info2 < NewInfo2) do
Chương II Cấu trúc dữ liệu danh sách . II.21
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật begin before := q; q := q^.next2 end if q = plist2 then plist2 := p else before^.next2 := p; p^.next2 := q; Insert_Element := p end;  Trong C:
NodePointer Insert_Element(InfoType NewInfo) {
NodePointer p , /*phần tử mới thêm vào*/
q , /*phần tử phụ trợ*/
before; /*phần tử đứng trước p */
p = (NodePointer)malloc(sizeof(struct Node));
p->info = NewInfo;/* ghi dữ liệu vào phần tử p */
//tìm phần tử trước p theo next1 q = plist1;
while ((q != NULL) && (q->info.info1 < NewInfo1)) { before = q; q = q->next1; }
if (q == plist1) plist1 = p; else before->next1 = p; p->next1 = q;
//tìm phần tử trước p theo next2 q = plist2;
while ((q != NULL) && (q->info.info2 < NewInfo2)) { before = q; q = q->next2; }
if (q == plist2) plist2 = p; else before->next2 = p; p->next2 = q; return p;
Chương II Cấu trúc dữ liệu danh sách . II.22
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật }
d. Loại phần tử khỏi danh sách
Xét danh sách đa liên kết có hai vùng liên kết next1 và next2 đã sắp xếp theo
thứ tự tăng dần theo info1 và info2 trong bản ghi kiểu InfoType.
Giả sử ta cần loại bỏ phần tử có nội dung DelInfo. Thủ tục Delete_Element sẽ cài
đặt thuật toán xoá phần tử khỏi danh sách.  Trong PASCAL:
Procedure Delete_Element(DelInfo : InfoType);
var q , {* phần tử phụ trợ dò tìm *}
q1 , {* phần tử tìm thấy theo next1 *}
before {* phần tử đứng trước q *} : NodePointer; begin q := plist1; { dò tìm theo vùng next1 }
while (q <> nil) and (q^.info <> DelInfo) do
if q^.info.info1 > DelInfo.info1 then q := nil else begin before := q; q := q^.next1 end;
if q <> nil then { tìm thấy phần tử cần loại bỏ } begin q1 := q; { ngắt next1 } if q = plist1 then plist1 := q^.next1 else
before^.next1 := q^.next1;
{ dò tìm theo vùng next2 } q := plist2; while q <> q1 do begin before := q; q := q^.next2 end; if q = plist2 then plist2 := q^.next2 else
before^.next2 := q^.next2;
Chương II Cấu trúc dữ liệu danh sách . II.23
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật end;
dispose(q) end;  Trong C:
void Delete_Element(InfoType DelInfo) {
NodePointer q , /* phần tử phụ trợ dò tìm */
q1 , /* phần tử tìm thấy theo next1 */
before; /* phần tử đứng trước q */ q = plist1; // dò tìm theo vùng next1
while ((q != NULL) && (q->info != DelInfo))
if (q->info.info1 > DelInfo.info1) q = NULL; else { before = q; q = q->next1; }
if (q != NULL) // tìm thấy phần tử cần loại bỏ { q1 = q; // ngắt next1
if (q == plist1) plist1 = q->next1; else
before->next1 = q->next1;
//dò tìm theo vùng next2 q = plist2;
while (q != q1) { before = q; q = q->next2; }
if (q == plist2) plist2 = q->next2; else
before->next2 = q->next2; } free(q); }
Chương II Cấu trúc dữ liệu danh sách . II.24
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
V. DANH SÁCH LIÊN KẾT KÉP 1. Định nghĩa
Danh sách liên kết kép (doubly linked list) là danh sách mà mỗi phần tử có hai
vùng liên kết. Một vùng liên kết chỉ đến phần tử đứng ngay trước nó, gọi là liên kết
ngược (previous) và một vùng liên kết chỉ đến phần tử đứng ngay sau nó, gọi là liên kết thuận (next).
Ví dụ. Danh sách có thể thêm vào hoặc lấy ra ở hai đầu.
2. Tổ chức danh sách liên kết kép
Mỗi phần tử của danh sách liên kết kép bao gồm một vùng thông tin info và các
vùng liên kết previous và next và ứng với các vùng liên kết ta có các chỉ điểm đầu
first và chỉ điểm cuối last.
Phần tử của danh sách liên kết kép có dạng: previous info next
Tổ chức danh sách liên kết kép như sau: firs t     . . . . .     last
Chương II Cấu trúc dữ liệu danh sách . II.25
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Khai báo Trong PASCAL Trong C Type InfoType = record typedef struct data Info1 : ...; { … info1; Info2 : ...; … info2; ... … end; } InfoType; NodePointer = ^Node; struct Node { Node = record InfoType info; info : InfoType; struct Node *previous;
previous : NodePointer; struct Node *next; next : NodePointer; }; end;
typedef struct Node *NodePointer;
Var first, last : NodePointer;{ con trỏ đầu NodePointer first, last, … ;// con trỏ đầu
và con trỏ cuối danh sách}
và con trỏ cuối danh sách 3. Các phép toán
a. Khởi tạo: danh sách rỗng. Trong PASCAL Trong C procedure Initialize;
void Initialize() begin {
first := nil; last := nil;
first = NULL; last = NULL; end; }
b. Duyệt danh sách
Duyệt danh sách theo liên kết thuận hoặc theo liên kết ngược, giải thuật giống như
giải thuật duyệt danh sách liên kết đơn.
c. Chèn phần tử vào danh sách:
Giả sử ta chèn phần tử có nội dung NewInfo.
Trường hợp thêm phần tử vào đầu danh sách
Hàm Insert_First trả về địa chỉ của phần tử mới thêm vào.
Chương II Cấu trúc dữ liệu danh sách . II.26
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Trong PASCAL Trong C
function Insert_First(NewInfo: InfoType): NodePointer Insert_First(InfoType NodePointer; NewInfo)
var p {*phần tử mới *}: NodePointer; { begin
NodePointer p ;//phần tử mới new(p);
p = (NodePointer)malloc(sizeof(struct
p^.info := NewInfo;{* ghi dữ liệu vào Node)); phần tử p *}
p->info = NewInfo;// ghi dữ liệu vào p^.previous := nil; phần tử p p^.next := first; p->previous = NULL;
if first <> nil then p->next = first; first^.previous := p;
if (first != NULL) first := p;
first->previous = p; if last = nil then first = p; last := p;
if (last = NULL) Insert_First := p last = p; end; return p; }
Trường hợp thêm phần tử vào sau phần tử q
Hàm Insert_Element trả về địa chỉ của phần tử mới thêm vào. Trong PASCAL Trong C function
Insert_Element(NewInfo: NodePointer Insert_Element(InfoType
InfoType; q: NodePointer): NodePointer; NewInfo, NodePointer q)
Var p, {*phần tử mới *} r : { NodePointer;
NodePointer p , /*phần tử mới */ r; begin
p = (NodePointer)malloc(sizeof(struct new(p); Node));
p^.info := NewInfo;{* ghi dữ liệu vào
p->info = NewInfo;// ghi dữ liệu vào phần tử p *} phần tử p p^.next := q^.next;
p->next = q->next; p^.previous := q; p->previous = q; q^.next := p; q->next = p; r := p^.next; r = p->next;
if r <> nil then {thêm vào giữa danh
if (r != NULL) /*thêm vào giữa danh sách} sách */ r^.previous := p r->previous = p;
else {thêm vào cuối danh sách}
else /*thêm vào cuối danh sách */ last := p; last = p; Insert_Element := p return p; end; }
Chương II Cấu trúc dữ liệu danh sách . II.27
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Trường hợp thêm phần tử vào danh sách đã có thứ tự
Hàm Insert_Element trả về địa chỉ của phần tử mới thêm vào.  Trong PASCAL:
function Insert_Element(NewInfo: InfoType): NodePointer; var
p , {*phần tử mới thêm vào*}
q, before : NodePointer; begin new(p);
p^.info := NewInfo; {* ghi dữ liệu vào phần tử p *}
{tìm phần tử before ngay trước phần tử p} q := first;
while (q <> nil) and (q^.info < NewInfo) do begin before := q; q := q^.next; end;
if q = first then {thêm vào đầu danh sách} begin p^.next := first; p^.previous := nil;
if first <> nil then first^.previous := p; first := p; if last = nil then last := p; end
else {thêm vào sau before} begin p^.next := before^.next; p^.previous := before; before^.next := p;
if q <> nil then {thêm vào giữa danh sách} q^.previous := p
else {thêm vào cuối danh sách} last := p; end Insert_Element := p end;  Trong C:
NodePointer Insert_Element(InfoType NewInfo) {
Chương II Cấu trúc dữ liệu danh sách . II.28
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
NodePointer p , /*phần tử mới thêm vào*/ q, before;
p = (NodePointer)malloc(sizeof(struct Node));
p->info = NewInfo;// ghi dữ liệu vào phần tử p
{tìm phần tử before ngay trước phần tử p} q = first;
while ((q != NULL) && (q->info < NewInfo)) { before = q; q = q->next; }
if (q == first) //thêm vào đầu danh sách { p->next = first; p->previous = NULL;
if (first != NULL)
first->previous = p; first = p;
if (last == NULL) last = p; }
else /*thêm vào sau before */ {
p->next = before->next; p->previous = before; before->next = p;
if (q != NULL) //thêm vào giữa danh sách q->previous = p;
else //thêm vào cuối danh sách last = p; } return p; }
d. Loại phần tử khỏi danh sách
Giả sử ta cần loại bỏ phần tử có địa chỉ p. Thủ tục Delete_Element sẽ xoá phần tử khỏi danh sách.
Chương II Cấu trúc dữ liệu danh sách . II.29
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật Trong PASCAL Trong C
procedure Delete_Element(p : NodePointer); void Delete_Element(NodePointer p) var {
before, {* phần tử đứng trước p *}
NodePointer before, /* phần tử
after {* phần tử đứng sau p * } đứng trước p */ : NodePointer;
after ; // phần tử đứng sau p begin
before = p->previous; before := p^.previous; after = p->next; after := p^.next;
if (before != NULL)
if before <> nil then
before->next = p->next;
before^.next := p^.next;
if (after != NULL)
if after <> nil then
after->previous = p->previous;
after^.previous := p^.previous;
if (p == first) if p = first then first = after; first := after;
if (p == last) if p = last then last = before; last := before; free(p);
dispose(p) } end;
e. Tìm kiếm phần tử trong danh sách.
Có thể tìm theo vùng next bắt đầu từ chỉ điểm first (thứ tự tăng dần) hoặc theo
vùng previous bắt đầu từ chỉ điểm last (thứ tự giảm dần). Giải thuật giống như
đối với danh sách liên kết đơn.
Chương II Cấu trúc dữ liệu danh sách . II.30
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
VI. DANH SÁCH LIÊN KẾT VÒNG 1. Định nghĩa
Danh sách liên kết vòng là danh sách liên kết mà vùng liên kết của phần tử cuối
trỏ đến phần tử đầu.
Có thể biểu diễn các phần tử danh sách liên kết vòng như sau: first   . . . . .    Khai báo Trong PASCAL Trong C
Type InfoType = struct Node { phần tử>; InfoType info; NodePointer = ^Node; struct Node *next; Node = recor d }; info : InfoType;
typedef struct Node *NodePointer;
next : NodePointer; NodePointer first, p;// first là con trỏ danh end; sách
Var first, p: NodePointer ;{ first là con trỏ p = (NodePointer)malloc(sizeof(struct danh sách}
Node));//cấp phát nút động cho p
2. Các phép toán trên danh sách
Các phép toán duyệt, tìm kiếm, chèn, xoá tương tự như trên danh sách liên kết
đơn. Tuy nhiên cần chú ý là vùng liên kết của phần tử cuối trỏ đến phần tử đầu.
Danh sách liên kết vòng thích hợp với các phép tách và ghép danh sách .
Chương II Cấu trúc dữ liệu danh sách . II.31
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Thủ tục chèn phần tử vào cuối danh sách Trong PASCAL Trong C
procedure Insert(NewInfo: InfoType);
void Insert(InfoType NewInfo)
var p, q : NodePointer; { begin NodePointer p, q; {tạo nút p}
p = (NodePointer)malloc(sizeof(struct new(p); Node)); p^.info := NewInfo; p->info = NewInfo; p^.next := nil; p->next = NULL;
{tìm nút cuối danh sách q}
// tìm nút cuối danh sách q q := first; q = first ;
while (q^.next <> first) do
while (q->next != first) q := q^.next; q = q->next;
q^.next := p; {liên kết nút q đến p}
q->next = p;// liên kết nút q đến p;
p^.next := first;{ p trở thành nút cuối
p->next = first;// p trở thành nút cuối của danh sách} của danh sách end; }
 Thủ tục loại phần tử sau phần tử q Trong PASCAL Trong C
procedure Delete(q : NodePointer);
void Delete(NodePointer q) var p,r : NodePointer; { begin NodePointer p, r; p := q^.next; p = q->next; if p <> nil then
if (p != NULL) begin { q^.next := p^.next;
q->next = p->next; end; } if p = first then
if (p ==first) begin {
{tìm nút cuối danh sách r} r = first ; r := first;
while (r->next != first)
while (r^.next <> first) do r = r->next; r := r^.next; firs t = p->next; firs t := p^.next; r->next = first; r^.next := first; } end; free(p);
dispose(p); } end;
 Ví dụ: Bài toán Josephus
Chương II Cấu trúc dữ liệu danh sách . II.32
Trần Quốc Chiến Cấu trúc dữ liệu và giải thuật
Một nhóm n binh sĩ bị kẻ thù bao vây và họ phải chọn một người đi cầu cứu viện
binh. Việc chọn người được thực hiện như sau.
Cho trước một số nguyên s gọi là bước đếm. Các binh sĩ xếp thành vòng tròn đánh
số 1, 2, ... , n bắt đầu từ người chỉ huy.
Đếm từ người thứ nhất, khi đạt đến s thì binh sĩ tương ứng bị loại ra khỏi vòng.
Lại bắt đầu đếm từ người tiếp theo, khi đạt đến s thì binh sĩ tương ứng bị loại ra khỏi vòng.
Quá trình này tiếp tục cho đến khi chỉ còn lại một binh sĩ, và người này chính là
người được điều đi cầu cứu viện binh.
Sau đây là chương trình cài đặt giải thuật của bài toán. Trong PASCAL Trong C Type struct node { NodePointer = ^Node; int v;/*dinh ke*/ Node = record struct node *link; info : integer; }; next : NodePointer;
typedef struct node *nodeptr; end; int n, s; Var q, p, first : N odePointer; nodeptr first, last; n, {số binh sĩ}
void addnode(int i);
s, {bước đếm}
void init(void); /*** khởi tạo ***/ i : integer; main()
Procedure Initialize; {*** khởi tạo ***} { begin nodeptr p1, p; first := nil; int k, i;
write(„cho số binh sĩ : „); readln(n); clrscr();
write(„cho số bước đếm: „); readln(s);
printf("nhap n, s = "); end;
scanf("%d %d", &n, &s);
Procedure CreateRing; {Tạo danh sách}
// Tạo danh sách
var p, last : NodePointer; init(); begin
for (k = 2; k <= n; k++)
{tạo nút đầu tiên}
addnode(k);
new(first); //Xóa n-1 nút
first^.info := 1; p1 = last; first^.next := nil;
for (k = 1; k <= n-1; k++)
{nối tiếp n-1 phần tử } { last := first;
for (i = 1; i < s; i++)
for i := 2 to n do p1 = p1->link; begin p = p1->link; new(p);
p1->link = p->link; p^.info := i;
free(p);
Chương II Cấu trúc dữ liệu danh sách . II.33