Bài tập Cấu trúc dữ liệu và giải thuật | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

DSA09 Bài 1:
Em xin phép chú thích tại không vững chứ không phải AI đâu nha thầy :< #include #include typedef struct NodeType{ int data; struct NodeType* next; }Node;
typedef struct LinkedListType{ Node* head; }LinkedList; void init(LinkedList* list){ list->head=NULL; } Node* makeNode(int data){
Node* newNode = (Node*)malloc(sizeof(Node)); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return newNode; } newNode->data=data; newNode->next=NULL; }
void insertHead(int data, LinkedList* list){
Node* newNode=makeNode(data); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return; }
newNode->next=list->head; list->head=newNode; }
void deleteHead(LinkedList* list){
if (list->head == NULL) return; Node* temp= list->head;
list->head=list->head->next; free(temp); }
void printList(LinkedList* list){ Node* node = list->head; while (node != NULL) {
printf("Node address: %p | ", &(node->data));
printf("data = %d| ", node->data);
printf("next node address = %p\n ", node->next); node = node->next; } printf("\n"); }
void insertNodeAtIndex(int data, int k, LinkedList* list) { if (k == 0) { insertHead(data, list); return; } Node* temp = list->head; int index = 0;
while (temp != NULL && index < k - 1) { temp = temp->next; index++; } if (temp == NULL) {
printf("Vi tri k khong hop le (vuot qua do dai danh sach)!\n"); return; }
Node* newNode = makeNode(data); if (newNode == NULL) return;
newNode->next = temp->next; temp->next = newNode; }
void deleteNodeAtIndex(int k, LinkedList* list){ if (k == 0) { deleteHead(list); return; } Node* temp = list->head; int index = 0;
while (temp != NULL && index < k - 1) { temp = temp->next; index++; }
if (temp == NULL || temp->next == NULL) {
printf("Vi tri k khong hop le!\n"); return; } // Thực hiện xóa
// Lúc này: temp đang ở (k-1)
// nodeToDelete là node tại (k)
Node* nodeToDelete = temp->next;
// Nối dây từ (k-1) sang (k+1) -> Bỏ qua node k
temp->next = nodeToDelete->next;
// Giải phóng bộ nhớ node k free(nodeToDelete); } //Hàm main int main(){ LinkedList list; init(&list);
//Tạo danh sách tự động
printf("Danh sach ban dau: \n");
for(int i = 0; i < 8; i++) insertHead(i, &list); //In danh sách printList(&list);
printf("Danh sach sau insert tai vi tri k=3: \n");
insertNodeAtIndex(12,3,&list); printList(&list);
printf("Danh sach sau delete tai vi tri k=3: \n");
deleteNodeAtIndex(3,&list); printList(&list); return 0; } Bài 2: a) #include #include typedef struct NodeType{ int data; struct NodeType* next; }Node;
typedef struct LinkedListType{ Node* head; }LinkedList; void init(LinkedList* list){ list->head=NULL; } Node* makeNode(int data){
Node* newNode = (Node*)malloc(sizeof(Node)); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return newNode; } newNode->data=data; newNode->next=NULL; }
void insertHead(int data, LinkedList* list){
Node* newNode=makeNode(data); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return; }
newNode->next=list->head; list->head=newNode; }
void deleteHead(LinkedList* list){
if (list->head == NULL) return; Node* temp= list->head;
list->head=list->head->next; free(temp); }
void printList(LinkedList* list){ Node* node = list->head; while (node != NULL) {
printf("Node address: %p | ", &(node->data));
printf("data = %d| ", node->data);
printf("next node address = %p\n ", node->next); node = node->next; } printf("\n"); }
void insertNodeAtIndex(int data, int k, LinkedList* list) { if (k == 0) { insertHead(data, list); return; } Node* temp = list->head; int index = 0;
while (temp != NULL && index < k - 1) { temp = temp->next; index++; } if (temp == NULL) {
printf("Vi tri k khong hop le (vuot qua do dai danh sach)!\n"); return; }
Node* newNode = makeNode(data); if (newNode == NULL) return;
newNode->next = temp->next; temp->next = newNode; } // Thực hiện xóa
// Lúc này: temp đang ở (k-1)
// nodeToDelete là node tại (k)
Node* nodeToDelete = temp->next;
// Nối dây từ (k-1) sang (k+1) -> Bỏ qua node k
temp->next = nodeToDelete->next;
// Giải phóng bộ nhớ node k free(nodeToDelete); }
int checkListDecrease(Node* a){ if(a->next==NULL){ return 1; } Node* temp=a; if(a->datanext->data){ return 0; } else{
checkListDecrease(a->next); } }
int findIndex(LinkedList* list, int val){ int index=0; Node* temp=list->head; while(temp != NULL){ if(temp->data<=val){ return index; } index++; temp=temp->next; } return index; }
void insert(LinkedList* list, int data){
insertNodeAtIndex(data,findIndex(list,data),list); } //Hàm main int main(){ LinkedList list; init(&list);
//Tạo danh sách tự động
printf("Danh sach ban dau: \n");
for(int i = 0; i < 8; i++) insertHead(i, &list); //In danh sách printList(&list); Node* head=list.head; if(checkListDecrease(head)){
printf("Danh sach co thu giam dan \n"); int val=0;
printf("Nhap gia tri muon them: \n"); scanf("%d",&val); insert(&list, val);
printf("Danh sach sau khi them gia tri %d la: \n", val); printList(&list); }
else{ printf("danh sach khong hop le\n");} return 0; } b) #include #include typedef struct NodeType{ int data; struct NodeType* next; }Node;
typedef struct LinkedListType{ Node* head; }LinkedList; void init(LinkedList* list){ list->head=NULL; } Node* makeNode(int data){
Node* newNode = (Node*)malloc(sizeof(Node)); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return newNode; } newNode->data=data; newNode->next=NULL; }
void insertHead(int data, LinkedList* list){
Node* newNode=makeNode(data); if(newNode == NULL){
printf("Khong duoc khoi tao \n"); return; }
newNode->next=list->head; list->head=newNode; }
void deleteHead(LinkedList* list){
if (list->head == NULL) return; Node* temp= list->head;
list->head=list->head->next; free(temp); }
void printList(LinkedList* list){ Node* node = list->head; while (node != NULL) {
printf("Node address: %p | ", &(node->data));
printf("data = %d| ", node->data);
printf("next node address = %p\n ", node->next); node = node->next; } printf("\n"); }
void deleteNodeAtIndex(int k, LinkedList* list){ if (k == 0) { deleteHead(list); return; } Node* temp = list->head; int index = 0;
while (temp != NULL && index < k - 1) { temp = temp->next; index++; }
if (temp == NULL || temp->next == NULL) {
printf("Vi tri k khong hop le!\n"); return; } // Thực hiện xóa
// Lúc này: temp đang ở (k-1)
// nodeToDelete là node tại (k)
Node* nodeToDelete = temp->next;
// Nối dây từ (k-1) sang (k+1) -> Bỏ qua node k
temp->next = nodeToDelete->next;
// Giải phóng bộ nhớ node k free(nodeToDelete); }
int checkListIncrease(Node* a){ if(a->next==NULL){ return 1; } Node* temp=a;
if(a->data>a->next->data){ return 0; } else{
checkListIncrease(a->next); } }
int findIndex(LinkedList* list, int val){ int index=0; Node* temp=list->head; while(temp != NULL){ if(temp->data>=val){ return index; } index++; temp=temp->next; } return index; }
void delete(LinkedList* list, int data){
deleteNodeAtIndex(findIndex(list,data),list); } //Hàm main int main(){ LinkedList list; init(&list);
//Tạo danh sách tự động
printf("Danh sach ban dau: \n");
for(int i = 0; i < 8; i++) insertHead(8-i, &list); //In danh sách printList(&list); Node* head=list.head; if(checkListIncrease(head)){
printf("Danh sach co thu tang dan \n"); int val=0;
printf("Nhap gia tri muon xoa: \n"); scanf("%d",&val); delete(&list,val);
printf("Danh sach sau khi xoa gia tri %d la: \n", val); printList(&list); }
else{ printf("danh sach khong hop le\n");} return 0; } Bài 3: #include #include typedef struct NodeType{ int data; struct NodeType* next; } Node; typedef struct StackType{ Node* top; } Stack; void initStack(Stack* s){ s->top = NULL;