Phạm Lê Huy Hoàng • 3 tháng trước
typedef struct SinhVien {
char maSo[11];
char hoTen[41];
float diemTrungBinh;
struct SinhVien *next;
} SinhVien;
SinhVien taoNode(char maSo, char *hoTen, float diemTrungBinh) {
SinhVien *sv = (SinhVien*)malloc(sizeof(SinhVien));
strcpy(sv->maSo, maSo);
strcpy(sv->hoTen, hoTen);
sv->diemTrungBinh = diemTrungBinh;
sv->next = NULL;
return sv;
} void themCuoi(SinhVien **head, SinhVien *sv) {
if (*head == NULL) {
*head = sv;
} else {
SinhVien *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = sv;
}
}
void xuatDanhSach(SinhVien *head) {
SinhVien *p = head;
while (p != NULL) {
printf("%s - %s - %.2f\n", p->maSo, p->hoTen, p->diemTrungBinh);
p = p->next;
}
}
int main() {
SinhVien *head = NULL;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char maSo[11], hoTen[41];
float diemTrungBinh;
scanf("%s", maSo);
scanf(" %[^\n]", hoTen);
scanf("%f", &diemTrungBinh);
SinhVien *sv = taoNode(maSo, hoTen, diemTrungBinh);
themCuoi(&head, sv);
}
xuatDanhSach(head);
return 0;
}
bài b
typedef struct SinhVien {
char maSo[11];
char hoTen[41];
float diemTrungBinh;
struct SinhVien *next;
} SinhVien;
SinhVien* taoNode(char maSo[], char hoTen[], float diemTrungBinh) {
SinhVien *sv = (SinhVien*)malloc(sizeof(SinhVien));
strcpy(sv->maSo, maSo);
strcpy(sv->hoTen, hoTen);
sv->diemTrungBinh = diemTrungBinh;
sv->next = NULL;
return sv;
}
void themVaoCuoi(SinhVien **head, SinhVien *sv) {
if (*head == NULL) {
*head = sv;
} else {
SinhVien *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = sv;
}
}
void locSinhVien(SinhVien *head) {
SinhVien *temp = head;
while (temp != NULL) {
if (temp->diemTrungBinh > 5) {
printf("%s - %s - %.2f\n", temp->maSo, temp->hoTen, temp->diemTrungBinh);
}
temp = temp->next;
}
}
int main() {
int n;
scanf("%d", &n);
SinhVien *head = NULL;
for (int i = 0; i < n; i++) {
char maSo[11], hoTen[41];
float diemTrungBinh;
scanf("%s", maSo);
getchar();
fgets(hoTen, sizeof(hoTen), stdin);
hoTen[strcspn(hoTen, "\n")] = '\0';
scanf("%f", &diemTrungBinh);
SinhVien *sv = taoNode(maSo, hoTen, diemTrungBinh);
themVaoCuoi(&head, sv);
}
locSinhVien(head);
return 0;
} bài c
typedef struct SinhVien {
char maSo[11];
char hoTen[41];
float diemTrungBinh;
struct SinhVien *next;
} SinhVien; SinhVien* taoNode(char maSo[], char hoTen[], float diemTrungBinh) {
SinhVien *sv = (SinhVien*)malloc(sizeof(SinhVien));
strcpy(sv->maSo, maSo);
strcpy(sv->hoTen, hoTen);
sv->diemTrungBinh = diemTrungBinh;
sv->next = NULL;
return sv;
}
void themVaoCuoi(SinhVien **head, SinhVien *sv) {
if (*head == NULL) {
*head = sv;
} else {
SinhVien *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = sv;
}
}
void timKiemSinhVien(SinhVien *head, char maSo[]) {
SinhVien *temp = head;
while (temp != NULL) {
if (strcmp(temp->maSo, maSo) == 0) {
printf("%s - %s - %.2f\n", temp->maSo, temp->hoTen, temp->diemTrungBinh);
return;
}
temp = temp->next;
}
printf("Not Found\n");
}
int main() {
int n;
scanf("%d", &n);
SinhVien *head = NULL;
for (int i = 0; i < n; i++) {
char maSo[11], hoTen[41];
float diemTrungBinh;
scanf("%s", maSo);
getchar(); // Đọc ký tự xuống dòng thừa
fgets(hoTen, sizeof(hoTen), stdin);
hoTen[strcspn(hoTen, "\n")] = '\0';
scanf("%f", &diemTrungBinh);
SinhVien *sv = taoNode(maSo, hoTen, diemTrungBinh);
themVaoCuoi(&head, sv);
}
char maSoTimKiem[11];
scanf("%s", maSoTimKiem);
timKiemSinhVien(head, maSoTimKiem);
return 0;
} bài d
typedef struct SinhVien {
char maSo[11];
char hoTen[41];
float diemTrungBinh;
struct SinhVien *next;
} SinhVien;
SinhVien* taoNode(char maSo[], char hoTen[], float diemTrungBinh) {
SinhVien *sv = (SinhVien*)malloc(sizeof(SinhVien));
strcpy(sv->maSo, maSo);
strcpy(sv->hoTen, hoTen);
sv->diemTrungBinh = diemTrungBinh;
sv->next = NULL;
return sv;
}
void themVaoCuoi(SinhVien **head, SinhVien *sv) {
if (*head == NULL) {
*head = sv;
} else {
SinhVien *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = sv;
}
}
void hienThiDanhSach(SinhVien *head) {
SinhVien *temp = head;
while (temp != NULL) {
printf("%s - %s - %.2f\n", temp->maSo, temp->hoTen, temp->diemTrungBinh);
temp = temp->next;
}
}
void sapXepDanhSach(SinhVien **head) {
if (*head == NULL || (*head)->next == NULL) {
return;
}
SinhVien *i, *j;
for (i = *head; i != NULL; i = i->next) {
for (j = i->next; j != NULL; j = j->next) {
if (i->diemTrungBinh < j->diemTrungBinh) {
char tempMaSo[11], tempHoTen[41];
float tempDiem;
strcpy(tempMaSo, i->maSo);
strcpy(tempHoTen, i->hoTen);
tempDiem = i->diemTrungBinh;
strcpy(i->maSo, j->maSo);
strcpy(i->hoTen, j->hoTen);
i->diemTrungBinh = j->diemTrungBinh;strcpy(j->maSo, tempMaSo);
strcpy(j->hoTen, tempHoTen);
j->diemTrungBinh = tempDiem;
}
}
}
}
int main() {
int n;
scanf("%d", &n);
SinhVien *head = NULL;
for (int i = 0; i < n; i++) {
char maSo[11], hoTen[41];
float diemTrungBinh;
scanf("%s", maSo);
getchar(); // Đọc ký tự xuống dòng thừa
fgets(hoTen, sizeof(hoTen), stdin);
hoTen[strcspn(hoTen, "\n")] = '\0';
scanf("%f", &diemTrungBinh);
SinhVien *sv = taoNode(maSo, hoTen, diemTrungBinh);
themVaoCuoi(&head, sv);
}
sapXepDanhSach(&head);
hienThiDanhSach(head);
return 0;
} bài e
using namespace std;
// Sinh viên khai báo thu vi?n t?i dây struct Node {
int data;
Node* left;
Node* right;
int height;
};
// Sinh viên khai báo các bi?n toàn c?c t?i dây (n?u có)
// Sinh viên khai báo hàm t?i dây int height(Node node); int getBalance(Node node); Node rightRotate(Node y); Node leftRotate(Node x); Node insert(Node node, int data); bool search(Node node, int key); void printInOrder(Node node); Node inputAVL(Node root); Node createRandomAVL(int n); void countIntermediateNodes(Node node, int &count); Node deletePerfectSquare(Node root); Node findParent(Node root, int x); void printSubtree(Node* root, int x);
// Sinh viên vi?t câu l?nh trong hàm main int main() {
Node* root = NULL;
int choice;
while (true) {
cout << "\nMenu:\n";
cout << "1. Nhap cay AVL\n";
cout << "2. Xuat cay AVL\n";
cout << "3. Tao ngau nhien cay AVL\n";
cout << "4. Tim kiem x co ton tai trong cay AVL hay khong?\n";
cout << "5. Dem so nut trung gian cua cay AVL\n";
cout << "6. Xoa node co gia tri la so chinh phuong cua cay AVL\n";
cout << "7. Input so nguyen x. Xuat ra man hinh\n";
cout << "0. Thoat\n";
cout << "Chon: ";
cin >> choice;
switch (choice) {
case 1:
root = inputAVL(root);
break;
case 2:
cout << "Cay AVL (In-order): ";
printInOrder(root);
break;
case 3:
cout << "Nhap so node n: ";
int n;
cin >> n;
root = createRandomAVL(n);
cout << "Cay AVL ngau nhien da duoc tao.\n";
break;
case 4:
{
int x;
cout << "Nhap gia tri x: ";
cin >> x;
if (search(root, x)) {
cout << "Gia tri " << x << " ton tai trong cay AVL.\n";
} else {
cout << "Gia tri " << x << " khong ton tai trong cay AVL.\n";
}
}
break;
case 5:
{
int count = 0;
countIntermediateNodes(root, count);
cout << "So nut trung gian trong cay AVL: " << count << endl;
}
break;
case 6:
root = deletePerfectSquare(root);
break;
case 7:
{
int x;
cout << "Nhap gia tri x: ";
cin >> x;
Node* parent = findParent(root, x);
if (parent != NULL) {
cout << "Gia tri cha cua node " << x << ": " << parent->data << endl;
} else {
cout << "Khong tim thay cha cua node " << x << endl;
}
printSubtree(root, x);
}
break;
case 0:
cout << "Thoat chuong trinh.\n";
return 0;
default:
cout << "Chon sai, vui long chon lai.\n";
}
}
return 0;
}
// Sinh viên vi?t n?i dung hàm tuong ?ng sau dòng này
int height(Node* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
int getBalance(Node* node) {
if (node == NULL) {
return 0;
}
return height(node->left) - height(node->right);
}
Node rightRotate(Node y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node leftRotate(Node x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
Node insert(Node node, int data) {
if (node == NULL) {
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->height = 1;
return newNode;
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
} else {
return node;
}
node->height = max(height(node->left), height(node->right)) + 1;
int balance = getBalance(node);
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
bool search(Node* node, int key) {
if (node == NULL) {
return false;
}
if (node->data == key) {
return true;
} else if (key < node->data) {
return search(node->left, key);
} else {
return search(node->right, key);
}
}
void printInOrder(Node* node) {
if (node == NULL) return;
printInOrder(node->left);
cout << node->data << " ";
printInOrder(node->right);
}
Node inputAVL(Node root) {
int n, value;
cout << "Nhap so luong nut: ";
cin >> n;
cout << "Nhap gia tri cua cac nut:\n";
for (int i = 0; i < n; i++) {
cin >> value;
root = insert(root, value);
}
return root;
}
Node* createRandomAVL(int n) {
Node* root = NULL;
for (int i = 0; i < n; i++) {
int value = rand() % 100;
root = insert(root, value);
}
return root;
}
void countIntermediateNodes(Node* node, int &count) {
if (node == NULL) return;
if (node->left != NULL && node->right != NULL) {
count++;
}
countIntermediateNodes(node->left, count);
countIntermediateNodes(node->right, count);
}
Node deletePerfectSquare(Node root) {
if (root == NULL) return NULL;
if (root->data == (int)sqrt(root->data) * (int)sqrt(root->data)) {
return NULL; // Xóa node chính phuong
}
root->left = deletePerfectSquare(root->left);
root->right = deletePerfectSquare(root->right);
return root;
}
Node findParent(Node root, int x) {
if (root == NULL || (root->left == NULL && root->right == NULL)) return NULL;
if ((root->left != NULL && root->left->data == x) || (root->right != NULL && root->right->data == x)) {
return root;
}
Node* leftSearch = findParent(root->left, x);
if (leftSearch != NULL) return leftSearch;
return findParent(root->right, x);
}
void printSubtree(Node* root, int x) {
if (root == NULL) return;
if (root->data == x) {
cout << "Cay con cua node: " << x<<endl;
if (root->left != NULL) {
cout << "Left child: " << root->left->data << endl;
printInOrder(root->left);
}
if (root->right != NULL) {
cout << "Right child: " << root->right->data << endl;
printInOrder(root->right);
}
}
printSubtree(root->left, x);
printSubtree(root->right, x);
}
Bình luận: