CHƯƠNG 9 : DANH SÁCH LIÊN KẾT ( MÓC NỐI)

- Danh sách liên kết : Nếu sử dụng mãng để quản lý danh sách sẽ rất tốn kèm và cứng
nhắc trong thao tác ă khắc phục = danh sách liên kết.
- Danh sách liên kết gồm các phần tử . Mỗi phần tử có 2 vùng chính : vùng dữ liệu và
vùng liên kết. Vùng liên kết là một hay nhiều con trỏ, trỏ đến các phần tử trước hoặc sau
nó tùy thuộc vào yêu cầu của công việc.
- Khai báo danh sách liên kết :
Typedef struct Kieu du lieu
{ <khai báo phần tử dữ li
ệu >;
Kiểu dữ liệu < các con trỏ >;
} Kiểu dữ liệu ;
- Dùng typedef struct kieu du lieu định nghĩa kiểu dữ liệu mới. Trong kiểu dữ liệu này có
2 phần, phần đầu tiên là phần khai báo các trường, phần thứ 2 là các con trỏ, trỏ đến
chính kiểu dữ liệu đó, dòng cuối cùng là cần thiết để các con trỏ được phép khai báo
chính là kiểu dữ liệu mà các con trỏ đó là thành phần.
- Ví dụ : typedef struct sinhvien
{ char hoten[30] ;
int diem ;
struct sinhvien *tiep ;
} sinhvien ;
sinhvien *head ; / con trỏ đặ
c biệt luôn trỏ tới đầu danh sách*/
- Mỗi một phần tử có một con trỏ, trỏ đến phần tử tiếp theo. Riêng phần tử cuối cùng con
trỏ sẽ trỏ đến một kiểu đặc biệt : Kiểu NULL( nghĩa là con trỏ đó không trỏ đến một phần
tử nào cả). Ban đầu con trỏ danh sách (head) được gán bằng NULL.
- Ðể cấp phát bộ nhớ, ta cần kiểm tra xem có đủ không ( tránh rối lo
ạn chương trình)
- Ví dụ :
#define size of (sinhvien)

#include <stdio.h>
#include<conio.h>
#include< stdlib.h>
#include<type.h>
#include<string.h>
void taomenu( )
void themsv ( );
void timkiem ( );
void loaibo( );
void danhsach( );
void vitrihv (char st[ ], int d ); /* tìm vị trí hợp lý */
void lietke ( );
#define sizesv size of (sinhvien)
typedef(truct sinhvien)
{ char hoten[30] ;
int diem ;
struct sinhvien *tiep ;
} sinhvien ;
sinhvien *head;
sinhvien *sv ;
void main ( )
{ clrscr ( );
gotoxy(1,12);
printf (" chương trình quản lý danh sách sinh viên (DSLK)\n");
getch ( ) ;
taomenu ( );
} /* kết thúc hàm main ( ) */
void taomenu ( )
{ char ch ;
do

if ( head = = NULL)
{ head = sv ; headă tiep = NULL ; }
else
{ /* tìm vị trí mới của phần tử trong danh sách */
find = head ; next = find ;
while ((find!=NULL) &&((kq=strcmp(findă hoten, sv ă hoten))< 0)
{ next = find ; find = findătiep ;}
if ( kq = = 0)
{ printf("sinh viên đã có trong danh sách . Ghi đè (Y/N) ? \n");
ch = getch( ); ch = toupper (ch);
if (ch = 'N')
{ free(sv) ; return ; }
else
find --> diem = d ;
free (sv) ;
return ;
}
/* nếu phần tử thêm vào đầu danh sách */
if (find = = head )
{ sv ă tiep = head ; head = sv ; }
else { sv ă tiep = find ; next ă tiep = sv ; }
}
}
void timkiem( )
{ char tensv[30] ; int kq ; clrscr ( );
printf(" tên sinh viên cần tìm :") ; gets(tensv);
if((tensv !=" " ) && (head1 = NULL))
{ sv = head ;
while ((sv! = NULL) &&((kq = strcmp(svăhoten, tensv))< 0)
sv = sv ă tiep ;

printf(" điểm : %d \n\n", svă diem);
sv = svătiep ;
}
getch( );
}

Bài tập : Hãy lập trình quản lý sinh viên sử dụng cấu trúc danh sách. Mỗi phần tử cấu trúc
như sau : họ và tên, điểm.
Yêu cầu : - In danh sách sinh viên có điểm >= 7.
- Sắp xếp theo điểm .
- Loại bỏ sinh viên nào đó ( nhập tên vào ).

Vns3curity(HCE)