Kỹ thuật lập trì nh
96
for (i=0; i<n-1;i++)
for (j=i+1; j<n; j++)
if ( strcmp(p[i],p[j]) >0)
{ tam = p[i];
p[i] = p[j];
p[j] = tam;
}
printf("\n Danh sach ho ten sau khi sap xep\n");
for (i=0; i<n;i++)
printf("%s\n", p[i]);
}
Lưu ý
: Chương trì nh trê n thực chấ t ta chỉ hoán đổi giá trị của mả ng con trỏ
p chứ mả ng chuỗi ds vẫ n như cũ.

Bà i tậ p:
1. Sắ p xế p lạ i danh sá ch học viê n theo thứ tự họ tă ng dầ n bằ ng con trỏ.
2. Sắ p xế p lạ i danh sá ch học viê n theo thứ tự tê n tă ng dầ n, nế u trùng tê n thì
sắ p theo họ bằ ng con trỏ.
3. Sắ p xế p lạ i danh sá ch học viê n theo thứ tự tê n tă ng dầ n, nế u trùng tê n thì
sắ p theo họ bằ ng mả ng chuỗi.

Kỹ thuật lập trì nh
97
CHƯƠNG 5 CáC THUậT TOáN TRÊN CấU TRúC
DANH SáCH LIÊN KếT (LINKED LIST)

I. Khái niệm:
Cấ u trúc danh sá ch liê n kế t là cấ u trúc động, việ c cấ p phá t nút và giả i

3




















First
1

2













Cá c phầ n tử trong danh sá ch đ ược kế t nối với nhau theo chùm liê n kế t như
hì nh trê n:
- First là con trỏ chỉ đế n phầ n tử đầ u của danh sá ch liê n kế t
- Phầ n tử cuối của danh sá ch liê n kế t với vùng liê n kế t có giá trị NULL
-Mỗi nút của danh sá ch có trường info chứa nội dung của nút và trường
next là con trỏ chỉ đế n nút kế tiế p trong danh sá ch.
* Lưu ý
:
- Cấ u trúc danh sá ch liê n kế t là cấ u trúc động, cá c nút đ ược cấ p phá t hoặ c
bị giả i phóng khi chương trì nh đang chạ y.
- Danh sá ch liê n kế t rấ t thí ch hợp khi thực hiệ n cá c phép toá n trê n danh
sá ch thường bị biế n động. Trong trường hợp xóa hay thê m phầ n tử trong danh
sá ch liê n kế t thì ta không dời cá c phầ n tử đi như trong mả ng mà chỉ việ c hiệ u
chỉ nh lạ i trường next tạ i cá c nút đang thao tác. Thời gian thực hiệ n cá c phép toá n
thê m và o và loạ i bỏ không phụ thuộc và o số phầ n tử của danh sá ch liê n kế t.
Nil
First

thà nh phầ n: First trỏ đế n phầ n tử đầ u tiê n của danh sá ch liê n kế t, và Last
trỏ đế n phầ n tử cuối của danh sá ch liê n kế t.
struct Linked_List;
{ First NODEPTR;
Last NODEPTR;
};
II. Các phép toán trên danh sách liên kết
:
II.1. Tạo danh sách
:
a. Khởi tạ o danh sá ch
(Initialize): dùng để khởi động một danh sá ch liê n
kế t, cho chương trì nh hiể u là hiệ n tạ i danh sá ch liê n kế t chưa có phầ n tử.
void Initialize(NODEPTR &First)
{
Kỹ thuật lập trì nh
99
First = NULL;
}
b. Cấ p phá t vùng nhớ
(New_Node): cấ p phá t một nút cho danh sá ch liê n
kế t. Hà m New_Node nà y trả về địa chỉ của nút vừa cấ p phá t.
Trong chương trì nh có sử dụng hà m malloc (trong <alloc.h>) , hà m nà y cấ p
phá t một khối nhớ tí nh theo byte từ bộ nhớ heap. Nế u cấ p phá t thà nh công, hà m
malloc trả về địa chỉ của vùng nhớ vừa cấ p phá t, ngược lạ i nó sẽ trả về NULL.
NODEPTR New_Node()
{
NODEPTR p;
p = (NODEPTR)malloc(sizeof(struct node));
return (p);

II.2. Cập nhật danh sách:
a. Giả i phóng vùng nhớ
(Free_Node): Hà m nà y dùng để hủy nút đ cấ p
phá t, và trả vùng nhớ về lạ i cho memory heap.
void Free_Node(NODEPTR p)
{
free(p);
}
b. Kiể m tra danh sá ch liê n kế t rỗng hay không
(Empty): hà m Empty trả về
TRUE nế u danh sá ch liê n kế t rỗng, và ngược lạ i.
int Empty(NODEPTR First)
{
return(First == NULL ? TRUE : FALSE);
}
c. Xóa phầ n tử đầ u của danh sá ch
(Delete_First): muốn xóa 1 phầ n tử khỏi
danh sá ch liê n kế t thì ta phả i kiể m tra xem danh sá ch có rỗng hay không. Nế u
danh sá ch có phầ n tử thì mới xóa đ ược.
void Delete_First (NODEPTR First)
{ NODEPTR p;
if (Empty(First))
printf("Danh sach rong nen khong the xoa");
else
{
p = First; // nut can xoa la nut dau
First = p->next;
Free_Node(p);
}
}