Giáo trình Cấu trúc dữ liệu

y con p không đòi hỏi thay đổi về cấu trúc cây.
2. h = 1: nút p đã nhận thêm một nút anh em.
3. h = 2: cây con p đã tăng chiều cao.
Giải thuật 
void Search(int x, node *p, int &h)
{
	node* p1,*p2;
	if (p == NULL)//từ chưa có trên cây, thêm từ vào cây
	{
	p = new node;
	h = 2;
	p®key = x;
	count = 1;
	left = NULL; right = NULL;
	lh = 0; rh = 1;
	}
	else if (x < p®key)
	{
	Search(x,p®Left,h);
	if (h != 0)
	if (p®lh)
	{
	p1 =p®Left;
	h = 2;
	p®lh = 0;
	if (p1®lh)
	{
	p®Left = p1®Right;
	p1®Right = p;
	p1®lh = 0;
	p = p1;
	}
	else if (p1®rh)
	{
	p2 = p1®Right;
	p1®rh = 0;
	p1®right = p2®Left;
	p2®Left = p1;
	p®Left = p2®Right;
	p2®Right = p;
	p = p2;
	}
	}
	else
	{
	h = h -1;
	if (h != 0) 
	p®lh = 1;
	}
	}
	else if (x > p®key)
	{
	Search(x,p®Right,h);
	if (h != 0)
	if (p®rh)
	{
	p1 = p®Right;
	h = 2;
	p®rh = 0;
	if (p1®rh)
	{
	p®Right = p1®Left;
	p1®Left = p;
	p1®rh = 0;
	p = p1;
	}
	else if (p1®lh)
	{
	p2 =p1®Left;
	p1®lh = 0;
	p1®Left = p2®Right;
	p2®Right = p1;
	p®Right = p1®Left;
	p1®Left = p;
	p = p2;
	}
	}
	else
	{
	h = h -1;
	if (h != 0) 
	p®rh = 1;
	}
	}
	else
	{
	p®Count += 1;
	h = 0;
	}
}
BÀI TẬP CHƯƠNG 4
Bài tập lý thuyết
1- Hãy trình bày các vấn đề sau đây:
 a- Định nghĩa và đặc điểm của cây nhị phân tìm kiếm.
 b- Thao tác nào thực hiện tốt trong kiểu này.
 c- Hạn chế của kiểu này là gì?
2- Xét thuật giải tạo cây nhị phân tìm kiếm. Nếu thứ tự các khoá nhập vào như sau:
8 3 5 2 20 11 30 9 18 4
thì hình ảnh cây tạo được như thế nào?
Sau đó, nếu hủy lần lượt các nút theo thứ tự sau:
20
thì cây sẽ thay đổi như thế nào trong từng bước hủy, vẽ sơ đồ (nêu rõ phương pháp hủy khi nút có cả 2 cây con trái và phải)
3- Áp dụng thuật giải tạo cây nhị phân tìm kiếm cân bằng để tạo cây với thứ tự các khóa nhập vào như sau:
5 7 2 1 3 6 10
thì hình ảnh cây tạo được như thế nào? Giải thích rõ từng tình huống xảy ra khi thêm từng khóa vào cây và vẽ hình minh họa.
Sau đó, nếu hủy lần lượt các nút theo thứ tự như sau:
5 6 7 10
thì cây sẽ thay đổi như thế nào trong từng bước hủy, vẽ sơ đồ và giải thích.
4- Viết các hàm xác định các thông tin của cây nhị phân T
Số nút lá
Số nút có đúng 1 cây con
Số nút có đúng 2 cây con
Số nút có khoá nhỏ hơn x (giả sử T là CNPTK)
Số nút có khoá lớn hơn x (giả sử T là CNPTK)
Số nút có khoá lớn hơn x và nhỏ hơn y (giả sử T là CNPTK)
Chiều cao của cây
In ra tất cả các nút ở tầng (mức) thứ k của cây T
In ra tất cả các nút theo thứ tự từ tầng 0 đến tầng thứ h-1 của cây T (h là chiều cao của cây)
Kiểm tra xem T có phải là cây cân bằng hoàn toàn không.
Độ lệch lớn nhất trên cây. (Độ lệch của một nút là độ lệch giữa chiều cao của cây con trái và cây con phải của nó. Độ lệch lớn nhất trên cây là độ lệch của nút có độ lệch lớn nhất).
5- Xây dựng cấu trúc dữ liệu biểu diễn cây N-phân (2<N£20).
Viết chương trình con duyệt cây N-phân và tạo sinh cây nhị phân tương ứng với các khoá của cây N-phân.
Giả sử khoá được lưu trữ chiếm k-byte, mỗi con trỏ chiếm 4 byte, vậy dùng cây nhị phân thay cây N-phân thì có lợi gì trong việc lưu trữ các khoá?.
6- Viết hàm chuyển một cây N-phân thành cây nhị phân.
Giả sử A là một mảng các số thực đã có thứ tự tăng. Hãy viết hàm tạo một cây nhị phân tìm kiếm có chiều cao thấp nhất từ các phần tử của A.
7- Viết chương trình con đảo nhánh (nhánh trái của một nút trên cây trở thành nhánh phải của nút đó và ngược lại) một cây nhị phân.
Bài tập thực hành:
8- Cài đặt chương trình mô phỏng trực quan các thao tác trên cây nhị phân tìm kiếm.
9- Cài đặt chương trình mô phỏng trực quan các thao tác trên cây AVL.
10- Viết chương trình cho phép tạo, tra cứu và sửa chữa từ điển Anh-Việt.
11- Viết chương trình duyệt cây theo mức.
HƯỚNG DẪN
Chương 1
Câu 6:
typedef struct
{
	char MNV[9];
	char hoten[31];
	char tinhTrang;
	int soCon;
	char vanHoa[3];
	float luongCB;
}nhanVien;
typedef struct
{
	int coPhep;
	int khongPhep;
	int lamThem;
	char danhGia[3];
	float thucLinh;
}chamCong;
Chương 2
Câu 2:
Trước hết ta đặt giá trị lớn nhất tạm thời bằng số đầu tiên. (Giá trị lớn nhất tạm thời này chính là giá trị lớn nhất ở mỗi giai đoạn của hàm).
So sánh số kế tiếp trong dãy với giá trị lớn nhất tạm thời và nếu nó lớn hơn giá trị lớn nhất tạm thời thì đặt cho giá trị lớn nhất tạm thời bằng số này.
Lặp lại bước 2 nếu còn số trong dãy chưa được xét tới.
Dừng nếu không còn số trong dãy được xét tới. Giá trị lớn nhất tạm thời lúc này chính là giá trị lớn nhất trong dãy số.
Câu 10:
//Day con tang co nhieu phan tu nhat
#include 
void main()
{
 int a[10], i, maxstart, maxend, maxlen, tmpstart, tmpend, 	tmplen;
 printf("\nNhap vao 10 phan tu nguyen cua day :");
 for (i=0; i<10; i++)
	 scanf("%d", &a[i]);
 printf("Day da cho :\n");
 for (i=0; i<10; i++)
	 printf("%6d", a[i]);
 maxstart = maxend = tmpstart = tmpend = 0;
 maxlen = tmplen = 1;
 for (i=1; i< 10; i++)
 {
	 if (a[i] < a[tmpend])
	 {
	 if (maxlen < tmplen)
	 {
	maxstart = tmpstart;
	maxend = tmpend;
	maxlen = tmplen;
	 }
	 tmpstart = tmpend = i;
	 tmplen = 1;
	 }
	 else
	 {
	 tmplen++;
	 tmpend++;
	 }
 }
 if (maxlen < tmplen)
 {
	 maxstart = tmpstart;
	 maxend = tmpend;
 }
 printf("\nDay tang co so phan tu nhieu nhat la : \n");
 for (i=maxstart; i<=maxend; i++)
	 printf("%6d", a[i]);
 getch();
}
Câu 13:
/* Tron hai mang tang dan thanh 1 mang tang dan */
#include 
#define MAX 10
void main()
{
int a[MAX], b[MAX], c[2*MAX], n1, n2, i, i1, i2;
printf("Cho biet so phan tu cua mang thu nhat : ");
scanf("%d", &n1);
printf("Nhap vao cac phan tu (tang dan) cua mang thu nhat : ");
for (i=0; i<n1; i++)
scanf("%d", &a[i]);
 printf("Cho biet so phan tu cua mang thu hai : ");
	 scanf("%d", &n2);
	 printf("Nhap vao cac phan tu (tang dan) cua mang 	 thu hai : ");
	 for (i=0; i<n2; i++)
	scanf("%d", &b[i]);
i1 = i2 = 0;
for (i=0; i<n1 + n2; i++)
{
if (i1 >= n1 || i2 >= n2)
break;
if (a[i1] < b[i2])
{
c[i] = a[i1];
i1++;
}
else
{
c[i] = b[i2];
i2++;
}
 	}
if (i1 < n1)
while (i1 < n1)
c[i++] = a[i1++];
if (i2 < n2)
while (i2 < n2)
c[i++] = b[i2++];
printf("\nCac phan tu cua mang tron : ");
for (i=0; i<n1+n2; i++)
printf("%d ", c[i]);
getch();
}
Chương 3
Câu 13: 
typedef struct INFO
{	
	int HeSo;
	int SoMu;
}INFOTYPE;
typedef struct tagSNODE
{
INFOTYPE Info;//phan thong tin
struct tagSNODE*pNext;//con tro den phan tu ke tiep//
}SNODE;
typedef SNODE *PSNODE;//dinh kieu con tro den
//kieu SNODE
typedef struct tagHEAD_SLIST
{
int nItems;//so phan tu cua danh sach
PSNODE pFirst;//con tro den dau danh sach
PSNODE pLast;//con tro den cuoi danh sach
PSNODE pCurr;//con tro hien hanh trong 
//danh sach
}HEAD_SLIST;
typedef HEAD_SLIST *PHEAD_SLIST;//dinh kieu
/*Khoi tao mot danh sach rong*/
PHEAD_SLIST	Create(void)
{
	PHEAD_SLIST	pHead;
	pHead	=	(PHEAD_SLIST)malloc(sizeof(HEAD_SLIST));
	if (pHead == NULL)
	return NULL;
	pHead->nItems	=	0;
	pHead->pFirst	=	NULL;
	pHead->pLast	=	NULL;
	pHead->pCurr	=	NULL;
	return pHead;
}
/*Huy toan bo danh sach ke ca dau quan ly*/
void	Destroy(PHEAD_SLIST pHead)
{
	PSNODE	pSList;
	pSList	=	pHead->pFirst;
	while (pSList)
	{
	free(pSList);
	pSList	=	pSList->pNext;
	}
	free(pHead);
}
/*Huy tat ca cac phan tu cua danh sach*/
void	RemoveAll(PHEAD_SLIST pHead)
{
	PSNODE	pSList;
	pSList	=	pHead->pFirst;
	while (pSList)
	{
	free(pSList);
	pSList	=	pSList->pNext;
	}
	pHead->pFirst	=	NULL;
	pHead->pLast	=	NULL;
	pHead->pCurr	=	NULL;
	pHead->nItems	=	0;
}
int GetcCount(PHEAD_SLIST pHead)
{ 
	return pHead->nItems;
}
/*Kiem tra danh sach co rong hay khong*/
int	IsEmpty(PHEAD_SLIST pHead)
{
	return (pHead->nItems == 0) ? 1 : 0;
}
/*	Lay so luong phan tu cua danh sach*/
int	GetCount(PHEAD_SLIST pHead)
{
	return pHead->nItems;
}
/*	Dat con tro hien hanh*/
void	SetCurrent(PHEAD_SLIST pHead, PSNODE pCurr)
{
	pHead->pCurr	=	pCurr;
}
PSNODE	GetCurrent(PHEAD_SLIST pHead)
{
	return pHead->pCurr;
}
/*	lay phan tu dau tien trong danh sach*/
PSNODE	FirstItem(PHEAD_SLIST pHead)
{
	pHead->pCurr	=	pHead->pFirst;
	return pHead->pCurr;
}
/*	lay phan tu ke tiep trong danh sach*/
PSNODE	NextItem(PHEAD_SLIST pHead)
{
	if (pHead->pCurr)
	{
	pHead->pCurr = pHead->pCurr->pNext;
	return pHead->pCurr;
	}
	else
	return NULL;
}
/*	them phan tu vao cuoi danh sach*/
void	AddTail(PHEAD_SLIST pHead, PSNODE pNew)
{
	if (pHead->pLast == NULL)
	{
	pNew->pNext	=	NULL;
	pHead->pFirst	=	pNew;
	pHead->pLast	=	pNew;
	}
	else
	{
	pNew->pNext	=	NULL;
	pHead->pLast->pNext	=	pNew;
	pHead->pLast	=	pNew;
	}
	pHead->nItems++;
}
/*	them phan tu vao dau danh sach*/
void	AddHead(PHEAD_SLIST pHead, PSNODE pNew)
{
	if (pHead->pFirst == NULL)
	{
	pNew->pNext	=	NULL;
	pHead->pFirst	=	pNew;
	pHead->pLast	=	pNew;
	}
	else
	{
	pNew->pNext	=	pHead->pFirst;
	pHead->pFirst	=	pNew;
	}
	pHead->nItems++;
}
/*chen phan tu vao truoc phan tu moc cua danh sach */
void	InsertBefore(PHEAD_SLIST pHead, PSNODE pHospot, PSNODE pNew)
{
	if (pHead->pFirst == pHospot)
	AddHead(pHead, pNew);
	else
	{
	PSNODE	pPrev, pCurr;
	pCurr	=	pHead->pFirst;
	while (pCurr)
	{
	pPrev	=	pCurr;
	pCurr	=	pCurr->pNext;
	if (pCurr == pHospot)
	break;
	}
	if (pCurr != NULL)
	{
	pPrev->pNext	=	pNew;
	pNew->pNext	=	pCurr;
	}
	}
}
/*chen phan tu vao sau phan tu moc cua danh sach*/
void	InsertAfter(PHEAD_SLIST pHead, PSNODE pHospot, PSNODE pNew)
{
	if (pHead->pLast == pHospot)
	AddTail(pHead, pNew);
	else
	{
	PSNODE	pCurr;
	pCurr	=	pHead->pFirst;
	while (pCurr)
	{
	if (pCurr == pHospot)
	break;
	pCurr	=	pCurr->pNext;
	}
	if (pCurr != NULL)
	{
	pNew->pNext = pCurr->pNext;
	pCurr->pNext = pNew;
	}
	}
}
/*huy phan tu moc cua danh sach*/
void	RemoveAt(PHEAD_SLIST pHead, PSNODE pHospot)
{
	if (IsEmpty(pHead))
	return;
	if (pHospot == pHead->pFirst)
	{
	pHead->pFirst = pHead->pFirst->pNext;
	free(pHospot);
	}
	else
	{
	PSNODE	pPrev, pCurr;
	pCurr	=	pHead->pFirst;
	while (pCurr)
	{
	pPrev	=	pCurr;
	pCurr	=	pCurr->pNext;
	if (pCurr == pHospot)
	break;
	}
	if (pPrev != pHead->pLast)
	{
	pPrev->pNext = pCurr->pNext;
	if (pCurr == pHead->pLast)
	pHead->pLast = pPrev;
	free(pCurr);
	}
	}
	pHead->nItems--;
}
void hoanvi(INFO &P,INFO &Q)
{
	INFO T;
	T=P;
	P=Q;
	Q=T;
}
//Sort List
void ListStraiSelection(PHEAD_SLIST	pHead)
{
	PSNODE P,Q,Min;
	P=pHead->pFirst;
	while(P)
	{	
	Q=P->pNext; Min=P;
	while(Q)
	{	
if(Q->Info.SoMuInfo.SoMu)
	Min=Q;
	Q=Q->pNext;
	}
	hoanvi(Min->Info,P->Info);
	P=P->pNext;
	}
 }
void Traverse(PHEAD_SLIST pHead)
{
PSNODE pSList;
	pSList=	FirstItem(pHead);
	textcolor(YELLOW);
	if(pSList)
	{
	while (pSList->pNext)
{
printf ("%dX^%d+",pSList->Info.HeSo,pSList->Info.SoMu);
	pSList	 = NextItem(pHead);
	}
printf("%dX^%d",pSList->Info.HeSo,pSList->Info.SoMu);
}
}
PSNODE Search(PHEAD_SLIST pHead, PSNODE pNew)
{	
PSNODE	pSList, pR;
	int Found=0;
	pSList	=	pHead->pFirst;
	while ((pSList) && (!Found))
if((pSList->Info.HeSo==pNew->Info.HeSo)&&(pSList->Info.SoMu==pNew->Info.SoMu)) 
Found=1;
	else
	pSList	=	pSList->pNext;
return pSList;
}
PSNODE SearchSoMu(PHEAD_SLIST pHead, PSNODE pNew)
{	
PSNODE	pSList;
	int Found=0;
	pSList	=	pHead->pFirst;
	while ((pSList) && (!Found))
	if(pSList->Info.SoMu==pNew->Info.SoMu)
Found=1;
	else
	pSList	=	pSList->pNext;
	return pSList;
}
void InsertDT(PHEAD_SLIST pHead, PSNODE pNew)
{
	 PSNODE pCurrent,pSList;
	 pSList	=FirstItem(pHead);
 while ((pSList)&&(pSList->Info.SoMu > pNew->Info.SoMu))
	 {
	 	pCurrent	=	pSList;
	pSList	=	NextItem(pHead);
	 }
	if(pSList->Info.SoMu==pNew->Info.SoMu)
	pSList->Info.HeSo+=pNew->Info.HeSo;
	 else
{	 
pNew->pNext=pSList;
	if(pSList==FirstItem(pHead)) 
pHead->pFirst=pNew;
	else 
pCurrent->pNext=pNew;
}
}
void	main(void)
{
	randomize();
	PHEAD_SLIST pHead1 ,	pHead2;
	PSNODE	pSList1,pSList2,;
PSNODE 	pR,P,pN,P1,PNew,pCurrent;
	long	i,x;
	int ch,SM,HS;
	clrscr();
	 pHead1	=	Create();
	 pHead2	=	Create();
	do
	{
	textattr(26);
	printf("\n1.Nhap DaThuc \n");
	printf("2.Cong DaThuc\n");
	printf("3.Nhan DaThuc\n");
	printf("4.Chia DaThuc\n");
	printf("5.DeleteX DaThuc\n");
	printf("6.SearchX DaThuc\n");
	printf("7.Sort DaThuc\n");
	printf("8.Traverse DaThuc\n");
	printf("9.Sum Node DaThuc\n");
	printf("10.Dao Ham DaThuc\n");
	printf("0.Exit\n");
	switch(ch)
	{	
case 1:{
	printf("\nNhap Dathuc 1:\n");
pSList1=(PSNODE)malloc(sizeof(SNODE));
	if (pSList1 == NULL)
	break;
	printf("\nNhap HS: ");
	scanf("%d",&HS);
	pSList1->Info.HeSo=HS;
	printf("\Nhap SM: ");
	scanf("%d",&SM);
	pSList1->Info.SoMu=SM;
	InsertDT(pHead1,pSList1);
	Traverse(pHead1);
	printf("\nNhap Dathuc 2:");
	pSList2	=(PSNODE)malloc(sizeof(SNODE));
	if (pSList2 == NULL)
	break;
	printf("\nNhap HS: ");
	scanf("%d",&HS);
	pSList2->Info.HeSo=HS;
	printf("\Nhap SM: ");
	scanf("%d",&SM);
	pSList2->Info.SoMu=SM;
	InsertDT(pHead2,pSList2);
	Traverse(pHead2);
	}break;
	case 2:{
	pN=FirstItem(pHead2);
	while(pN)
	{
	InsertDT(pHead1,pN);
	pN = NextItem(pHead2);
	 }
	 textcolor(RED);
	 cprintf("\nTong 2 Da Thuc: ");
	Traverse(pHead1);
	}break;
	case 3:{
	}break;
	case 4:{
	}break;
	case 5:{
	printf("\nNhap HS: ");
	scanf("%d",&HS);
	PNew->Info.HeSo=HS;
	printf("\Nhap SM: ");
	scanf("%d",&SM);
	PNew->Info.SoMu=SM;
	pR=Search(pHead1,PNew);
	RemoveAt(pHead1,pR);
	}break;
	case 6:{
	}break;
	case 7:{
Traverse(pHead1);
printf("\n Da Thuc 1 sau khi sort\n");
	ListStraiSelection(pHead1);
	Traverse(pHead1);
	Traverse(pHead2);
printf("\nDa Thuc 2 sau khi sort\n");
	ListStraiSelection(pHead2);
	Traverse(pHead2);
	}break;
	case 8:{
	printf("\nDa thuc 1: \n");
	Traverse(pHead1);
	printf("\nDa thuc 2: \n");
	Traverse(pHead2);
}break;
	case 9: 
printf("\nSum Node List:%4d ",GetCount(pHead1));
	break;
	case 10: break;
	}
	printf("\nChoice(1.2.3.4.5.6.7.8.9.10.0): ");
	scanf("%d",&ch);
	clrscr();
	}while(ch);
}
Chương 04
Câu 4: Chương trình đếm số lá của cây
typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;
NODE *root;
void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}
void insert(NODE *tmp, NODE **root)
{
if (tmp->element element)
if ((*root)->left)
insert(tmp, &(*root)->left);
 	else
(*root)->left = tmp;
else
 	if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}
void insert_node(element_type e, NODE **root)
{
NODE *tmp;
tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}
void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}
int dem_nut_la(NODE *root)
{
if (root == NULL)
return 0;
else
if (root->left != NULL || root->right != NULL)
return dem_nut_la(root->left) + dem_nut_la(root->right);
else
 return 1;
}
void main()
{
int tong_nut_la;
khoi_tao_cay(&root);
nhap_cay(&root);
tong_nut_la = dem_nut_la(root);
printf("\nTong so nut la = %d", tong_nut_la);
getch();
}
Câu 11:
#define MAX 100
typedef int element_type;
typedef struct node {
 element_type element;
 struct node *left, *right;
} NODE;
NODE *queue[MAX + 1];
int front, rear, queue_size;
void khoi_tao_queue()
{
 front = rear = 0;
 queue_size = 0;
}
int is_empty()
{
 return (queue_size == 0);
}
int is_full()
{
 return (queue_size == MAX);
}
int push(NODE *value)
{
 if (queue_size < MAX)
 {
 queue_size++;
 queue[rear++] = value;
 if (rear == MAX)
 rear = 0;
 }
 return rear;
}
int pop(NODE **value)
{
 if (queue_size > 0)
 {
 *value = queue[front++];
 if (front > MAX)
 front = 0;
 queue_size--;
 }
 return front;
}
NODE *root;
void khoi_tao_cay(NODE ** root)
{
 *root = NULL;
}
void insert(NODE *tmp, NODE **root)
{
 if (tmp->element element)
 if ((*root)->left)
 insert(tmp, &(*root)->left);
 else
 (*root)->left = tmp;
 else
 if ((*root)->right)
 insert(tmp, &(*root)->right);
 else
 (*root)->right = tmp;
}
void insert_node(element_type e, NODE **root)
{
 NODE *tmp;
 tmp = (NODE *)malloc(sizeof(NODE));
 tmp->element = e;
 tmp->left = NULL;
 tmp->right = NULL;
 if (*root == NULL)
 *root = tmp;
 else
 insert(tmp, root);
}
void nhap_cay(NODE **root)
{
 element_type e;
 do {
 printf("\nNhap element (-1 de ket thuc) : ");
 scanf("%d", &e);
 if (e != -1)
 insert_node(e, root);
 } while (e != -1);
}
void duyet_cay_level(NODE *root)
{
 NODE *p;
 khoi_tao_queue();
 if (root != NULL)
 push(root);
 while (!is_empty())
 {
 pop(&p);
 printf("%d ", p->element);
 if (p->left != NULL)
 push(p->left);
 if (p->right != NULL)
 push(p->right);
 }
}
void main()
{
 khoi_tao_cay(&root);
 nhap_cay(&root);
 duyet_cay_level(root);
 getch();
}
TÀI LIỆU THAM KHẢO
–&—
Trần Hạnh Nhi – Dương Anh Đức : Giáo trình Cấu trúc dữ liệu và Giải thuật – Đại học quốc gia thành phố Hồ Chí Minh – 2001.
Nguyễn Trung Trực : Cấu trúc dữ liệu – Trường Đại học Bách khoa thành phố Hồ Chí Minh – 1994
Niklaus Wirth : Algorithms + Data Structures = Programs – Prentice Hall – 1976
Robert Sedgewick : Cẩm nang thuật toán – Nhà xuất bản Khoa học Kỹ thuật – 1994
Th. Cormen, Ch. E. Leiserson, R. L. Rivest, Introduction to Algorithms (MIT Press, 1998).
A.V. Aho, J.E Hopcroft, J.D Ulman, Data structures and algorithms (Addison Wesley, 1983).
Mục lục
Chương 1: Các cấu trúc dữ liệu cơ bản và giải thuật	3
1- Vai trò của cấu trúc dữ liệu	3
2- Các tiêu chuẩn đánh giá cấu trúc dữ liệu	7
3- Khái niệm về kiểu dữ liệu	10
 3.1-Định nghĩa kiểu dữ liệu	10
 3.2-Các kiểu dữ liệu cơ bản	11
 3.3-Các kiểu dữ liệu có cấu trúc	13
 3.4-Một số kiểu dữ liệu có cấu trúc cơ bản	15
4- Đánh giá độ phức tạp của giải thuật	20
 4.1-Các bước phân tích bài toán	22
 4.2-Sự phân lớp các thuật toán	24
 4.3-Phân tích trường hợp trung bình	26
Chương 2: Các thuật toán tìm kiếm và sắp xếp nội	33
1. Các thuật toán tìm kiếm	33
 1.1. Tìm tuyến tính	33
 1.2. Tìm nhị phân	36
2. Các thuật toán sắp xếp nội	41
 2.1. Các thuật toán cơ bản	42
 2.2. Sắp xếp với độ dài bước giảm dần – Shell Sort	55
 2.3. Sắp xếp dựa trên phân hoạch – Quick Sort 	59
Chương 3: Danh sách liên kết	74
1- Giới thiệu	74
2- Kiểu con trỏ	74
 2.1- Biến không động (biến tĩnh, biến nửa tĩnh)	74
 2.2-Kiểu con trỏ	75
3- Danh sách	76
 3.1. Danh sách đơn	77
 3.2. Danh sách vòng	87
 3.3. Danh sách kép	90
 3.4. Danh sách có nhiều mối liên kết	93
4. Stack	93
 4.1. Ðịnh nghĩa	93
 4.2. Biểu diễn Stack dùng mảng	95
 4.3. Stack được tổ chức theo danh sách liên kết	98
5. Hàng đợi (Queue)	101
 5.1. Định nghĩa	101
 5.2. Cài đặt hàng đợi dùng mảng	102
 5.3. Hàng đợi được tổ chức theo danh sách liên kết	104
Chương 4: Cây	111
1. Cây	111
 1.1. Ðịnh nghĩa	111
 1.2. Một số khái niệm cơ bản	111
 1.3. Nhận xét	112
2. Cây nhị phân	112
 2.1. Ðịnh nghĩa	112
 2.2. Biểu diễn cây nhị phân T	113
3. Cây nhị phân tìm kiếm	114
 3.1. Ðịnh nghĩa	114
 3.2. Các thao tác trên cây nhị phân tìm kiếm	114
4. Cây cân bằng	120
 4.1. Ðịnh nghĩa	120
 4.2. Chỉ số cân bằng của một nút	120
5. Cây nhiều nhánh0	134
 5.1. Định nghĩa	134
 5.2. B-cây	134
6. B-cây nhị phân (Binary B-câytree)	158
 6.1. Giới thiệu	158
 6.2. Các thao tác trên BB-cây	160
Hướng dẫn	173
Tài liệu tham khảo	198
Mục lục 	199