Tài liệu kiểm tra học phần môn cơ sở dữ liệu | Đại học Hoa Sen

Tổ chức lưu trữ dslk đơn typedef struct NODE { DATA info; NODE* pNext; } NODE; typedef struct { NODE* pHead; } LIST; Các thao tác cơ bản
Khởi tạo danh sách rỗng: gán pHead = NULL
void Initialize(LIST &list) { list.pHead = NULL; } Các thao tác cơ bản
Kiểm tra danh sách có rỗng hay không: kiểm tra pHead có bằng NULL hay không
Kiểm tra danh sách có đầy hay chưa: không kiểm tra được tính đầy đối với DSLK bool IsEmpty(LIST list) { if (list.pHead == NULL) return true; return false; } Duy t danh sách: cho con tr ệ p ch
ỏ y tạ đầầu đếến cuốếi danh sá ừ ch Ph i tha ả
y Process bằầng tến hàm t ng ươ ng ứ void Process (LIST list) { NODE* p = list.pHead; while (p != NULL) { p = p->pNext; } } Tìm kiếếm m t phầần t ộ trong danh s ử
ách: nếếu tm thầếy tr vếầ con tr ả p, ng ỏ c l ượ i tr ạ vếầ N ả ULL
NODE* Search(LIST list, DATA x) { NODE* p = list.pHead; while (p != NULL) { if (p->info == x) break; p = p->pNext; } return p; }
NODE* Search2(LIST list, DATA x, NODE* &q) { NODE* p = list.pHead; while (p != NULL) { if (p->info == x) break; q = p; p = p->pNext; } return p; } Thếm m t phầần t ộ v
ử ào danh sách • B1: T o m ạ t phầần t ộ trong b ử ộ nhớ NODE* CreateNode(DATA x) { NODE* p = new NODE; if (p != NULL) { p->info = x; p->pNext = NULL; } return p; } Thếm m t phầần t ộ v ử ào danh sách • B2: Gằến phầần t v ử a t ừ o v ạ ào danh sách
• Gằến vào đầầu danh sách
NODE* InsertHead(LIST &list, DATA x) { NODE* p = CreateNode(x); if (p != NULL) { p->pNext = list.pHead; list.pHead = p; } return p; } Thếm m t phầần t ộ v ử ào danh sách B2: Gằến phầần t v ử a t ừ o v ạ ào danh sách
Gằến vào sau phầần t q ử
NODE* InsertAfter(LIST &list, NODE* q, DATA x) { NODE* p = CreateNode(x); if (p != NULL) { p->pNext = q->pNext; q->pNext = p; } return p; } • Xóa m t phầần t ộ kh ử i danh sách ỏ • Xóa phầần t đ ử ng sau phầần t ứ q ử
bool DeleteAfter(LIST &list, NODE* q) { if (q != NULL) { NODE* p = q->pNext; if (p != NULL) { q->pNext = p->pNext; delete p; return true; } } return false; } Xóa m t phầần t ộ kh ử i danh sách ỏ • Xóa phầần t có gi ử á tr X ị
bool DeleteNode(LIST &list, DATA x) { NODE* q = NULL; NODE* p = Search2(list, x, q); if (p == NULL) return false; if (q == NULL) return DeleteHead(list); else return DeleteAfter(list, q); } Xóa hếết danh sách void DeleteAll(LIST &list) { while ( DeleteHead(list) ); } Stack và queue Khởi t o rốỗng ạ void Initialize(LIST &s) { s.pHead = NULL; } Ki m tra c ể ó rốỗng hay khống bool IsEmpty(LIST s) { if (s.pHead == NULL) return true; return false; } Thếm m t phầần t ộ v ử ào đ nh Stack ỉ
bool Push(LIST &s, DATA x) { NODE* p = InsertHead(s,x); if (p != NULL) return true; return false; } Lầếy ra m t phầần t ộ kh ử i đ ỏ nh Stac ỉ k DATA POP (LIST &s) { if ( !IsEmpty(s) ) { DATA x = s.pHead->info; DeleteHead(s); return x; } return NULL; } Xem thống tin phầần t ử đ ở nh Stack ỉ DATA GetTop(LIST s) { if ( !IsEmpty(s) ) { DATA x = s.pHead->info; return x; } return NULL; } L u tr ư ữ d i d ướ ng DSĐ ạ #define N 100 typedef struct { int front; int rear; DATA a[N]; } CQUEUE; L u tr ư ữ d i d ướ ng DSLK ạ typedef struct NODE { DATA info; NODE* pNext; } NODE; typedef struct { NODE* pHead; NODE* pTail; } LQUEUE; Khởi t o rốỗng ạ
void Initialize(LQUEUE &q) { q.pHead = NULL; q.pTail = NULL; } Ki m tra c ể ó rốỗng hay khống bool IsEmpty(LQUEUE q) { if (q.pHead == NULL) return true; return false; } Thếm m t phầần t ộ v ử ào cuốếi
Queue bool Push(LQUEUE &q, DATA x) { NODE* p = InsertTail(q,x); if (p != NULL) return true; return false; } Lầếy ra m t phầần t ộ ử đầầu Queue ở DATA Pop(LQUEUE &q) { if ( !IsEmpty(q) ) { DATA x = q.pHead->info; DeleteHead(q); return x; } return NULL; } DATA GetFront(LQUEUE q) { if ( !IsEmpty(q) ) { DATA x = q.pHead->info; return x; } } return NULL; } DATA GetRear(LQUEUE q) { if ( !IsEmpty(q) ) { { DATA x = q.pTail->info; return x; } return NULL; }
Bài 11-13: Cây, Cây nh phân, Câ ị y BST, Cây cân bằằng typedef struct BNODE { int info; BNODE* left; BNODE* right; } BNODE; BNODE* CreateNode(int x) { BNODE* p = new BNODE; if (p != NULL) { p->info = x; p->left = NULL; p->right = NULL; } return p; } typedef struct { BNODE* root; } BTREE;
void Initialize(BTREE &tree) { tree.root = NULL; }
void CreateBTree(BNODE* &p) { int x;
printf(“\n Nhap vao gia tri cua nut: “); scanf(“%d”, &x); if (x == -1) return; p = CreateNode(x); if (p != NULL) {
printf(“\n Nhap cay con ben trai cua nut %d: “,x); CreateBTree(p->left);
printf(“\n Nhap cay con ben phai cua nut %d: “,x); CreateBTree(p->right); } }
void PrintTree(BNODE* p, int k) { if (p == NULL) return;