[알고리즘] 기초 데이터구조(2) - 예제

[문제1] 이중연결리스트 + 헤더 및 트레일러 노드 프로그램

- addList: position과 element를 받아 list를 추가한다

- deletList: position을 받아 list에서 삭제한다

- getElement: position을 받아 element를 RETURN한다

- printList: list의 모든  element를 순서대로 출력한다

- freeList: list의 메모리할당을 해제한다

입력예시            출력예시

9 A 1 A A 2 B A 3 C A 3 D P D 2 P A 1 E P G 4

ABDC ADC EADC invalid position

#include<stdio.h> #include<stdlib.h> struct node { char element; struct node *next; struct node *prev; }; void addList(struct node *header, struct node *trailer, int position, char element) { struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->element = element; for (int i = 1; i < position; i++){ header = header->next; if (header == trailer){ printf("invalid position\n"); free(newnode); return; } } newnode->next = header->next; newnode->next->prev = newnode; newnode->prev = header; newnode->prev->next = newnode; } void deleteList(struct node *header, struct node *trailer, int position){ struct node *ptr = header; for (int i = 0; i < position; i++){ ptr = ptr->next; if (ptr == trailer){ printf("invalid position\n"); return; } } (ptr->prev)->next = ptr->next; (ptr->next)->prev = ptr->prev; free(ptr); } char getElement(struct node *header, struct node *trailer, int position){ for (int i = 0; i<position; i++){ header = header->next; if (header == trailer){ printf("invalid position\n"); return NULL; } } return header->element; } void printList(struct node *header){ struct node *ptr = header->next; while (ptr != NULL){ printf("%c", ptr->element); ptr = ptr->next; } printf("\n"); } void freeList(struct node *header) { struct node *ptr = header; while (ptr != NULL){ header = header->next; free(ptr); ptr = header; } } void main(){ int calculateNumber, position; char select, element; struct node *header = (struct node*)malloc(sizeof(struct node)); struct node *trailer = (struct node*)malloc(sizeof(struct node)); header->next = trailer; header->prev = NULL; trailer->prev = header; trailer->next = NULL; scanf("%d", &calculateNumber); getchar(); for (int i = 0; i < calculateNumber; i++){ scanf("%c", &select); getchar(); if (select == 'A') { scanf("%d %c", &position, &element); addList(header, trailer, position, element); getchar(); } else if (select == 'D') { scanf("%d", &position); deleteList(header, trailer, position); getchar(); } else if (select == 'G') { scanf("%d", &position); if (getElement(header, trailer, position) != NULL) { printf("%c\n", getElement(header, trailer, position)); } getchar(); } else if (select == 'P') { printList(header); } } freeList(header); }

[문제2] 다항식을 헤더 단일연결리스트로 표현하고, 다항식의 덧셈을 하는 프로그램(항은 내림차순으로 입력)

입력예시               출력예시

3 4 5 3 4 1 1 3 3 6 -3 4 2 1

3 6 4 5 3 1

#include<stdio.h> #include<stdlib.h> struct node { int coef; int exp; struct node *next; }; void addTerm(struct node *head, int coef, int exp){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->coef = coef; newnode->exp = exp; newnode->next = NULL; while (head->next != NULL){ head = head->next; } head->next = newnode; } struct node *addPoly(struct node *firstPolynomial, struct node *secondPolynomial){ struct node *first = firstPolynomial->next; struct node *second = secondPolynomial->next; struct node *sumPolynomial = (struct node*)malloc(sizeof(struct node)); sumPolynomial->next = NULL; int zeroCheck; while ((first != NULL) && (second != NULL)){ if (first->exp > second->exp){ addTerm(sumPolynomial, first->coef, first->exp); first = first->next; } else if (first->exp < second->exp){ addTerm(sumPolynomial, second->coef, second->exp); second = second->next; } else{ zeroCheck = first->coef + second->coef; if (zeroCheck != 0){ addTerm(sumPolynomial, zeroCheck, first->exp); } first = first->next; second = second->next; } } while (first != NULL){ addTerm(sumPolynomial, first->coef, first->exp); first = first->next; } while (second != NULL){ addTerm(sumPolynomial, second->coef, second->exp); second = second->next; } return sumPolynomial; } void printPolynomial(struct node *header) { struct node *ptr = header->next; while (ptr != NULL) { printf("%d %d ", ptr->coef, ptr->exp); ptr = ptr->next; } printf("\n"); } void freePolynomial(struct node *header) { struct node *ptr = header; while (ptr != NULL) { header = header->next; free(ptr); ptr = header; } } void main(){ int polynomialNumber, coef, exp; struct node *firstPolynomial = (struct node*)malloc(sizeof(struct node)); struct node *secondPolynomial = (struct node*)malloc(sizeof(struct node)); struct node *sumPolynomial; firstPolynomial->next = NULL; secondPolynomial->next = NULL; scanf("%d", &polynomialNumber); for (int i = 0; i < polynomialNumber; i++){ scanf("%d", &coef); scanf("%d", &exp); addTerm(firstPolynomial, coef, exp); } scanf("%d", &polynomialNumber); for (int i = 0; i < polynomialNumber; i++){ scanf("%d", &coef); scanf("%d", &exp); addTerm(secondPolynomial, coef, exp); } sumPolynomial = addPoly(firstPolynomial, secondPolynomial); printPolynomial(sumPolynomial); freePolynomial(firstPolynomial); freePolynomial(secondPolynomial); freePolynomial(sumPolynomial); }