구조체 복습
구조체: 객체 지향 프로그래밍에서 말하는 클래스의 모체가 되는 것으로 여러 개의 자료형을 묶어서 새로운 자료형을 만들 수 있는 방법임.
- 여러 개의 데이터를 하나로 묶어서 사용할 수 있도록 하기 위해 만들어진 C언어의 문법으로 후에 이러한 구조체의 개념은 객체 지향 프로그래밍에서는 클래스라는 개념으로 확장되어 사용됨.
배열이 여러 개의 같은 자료형들을 하나로 묶는 것이었다면구조체는 서로 다른 자료형들을 하나로 묶어서 한꺼번에 다루는 것.
struct student {
int number;
char name[10];
double grade;
};
int main(void)
{
struct student s;
s.number = 20150001;
strcpy(s.name, "홍길동");
printf("학점을 입력하세요:");
scanf("%1f", &s.grade); // float은 f만 적으면 됨.
printf("학번: %d\n", s.number);
printf("이름: %s\n", s.name);
printf("학점: %.1f\n", s.grade);
return 0;
}
#include <stdio.h>
#include <math.h>
struct point{
int x;
int y;
};
int main(void) {
struct point p1, p2;
int xDiff, yDiff;
double distance;
printf("1번 점의 좌표를 입력하세요 : ");
scanf("%d %d", &p1.x, &p1.y);
printf("2번 점의 좌표를 입력하세요 : ");
scanf("%d %d", &p2.x, &p2.y);
xDiff = p1.x - p2.x;
yDiff = p1.y - p2.y;
distance = sqrt(xDiff * xDiff + yDiff * yDiff);
printf("두 점 사이의 거리는 %f입니다.\n", distance);
return 0;
}
linked list
#include <stdio.h>
#include <stdlib.h>
typedef struct node { // 노드 특성들을 넣어줄 구조체 선언
int data; // 노드 값
struct node *next; // 다음 노드를 가리키기 위한 포인터 선언 & struct node 자료형을 가리킬 포인터 변수 next 선언
} Node; // 구조체 별칭
typedef struct list { // 노드 집합의 head 노드와 tail 노드를 가리키는 포인터와 노드 개수를 기록하기 위한 구조체 선언
Node *head; // Node 자료형을 가리키는 head라는 포인터 변수 선언
Node *tail; // Node 자료형을 기리키는 tail이라는 포인터 변수 선언
int size; // Node를 생성할 때마다 갱신해줄 int형 size 변수 선언
} List;
void createlist(List *list) { // 초기 리스트에 head 및 tail 노드를 추가하고, list 구조체 내의 멤버 size를 0으로 초기화 해주기 위함
list->head = (Node*)malloc(sizeof(Node)); // 노드 하나를 위한 메모리를 할당하고 해당 노드를 가리키는 포인터값을 list 구조체 내의 멤버인 head 값에 저장
list->tail = (Node*)malloc(sizeof(Node)); // head와 동일
list->head->next = list->tail; // 헤드노드가 가리키는 노드의 주소값인 next에 list 구조체의 tail이 가리키는 노드 주소값을 저장. 즉, 헤드 노드가 가리키는 다음 노드의 주소값이 tail 노드를 가리키는 주소값으로 만들어주기 위함
list->tail->next = list->tail; // tail 노드가 가리키는 다음 노드는 tail 노드
list->size = 0; // 초기 리스트의 크기를 0으로 초기화
}
void addFirst(List *list,int data) {
Node *newNode = (Node*)malloc(sizeof(Node)); // 새로 삽입할 노드를 가리키는 포인터 값을 Node 자료형을 가리키는 newnode라는 포인터에 저장
newNode->data = data; // 삽입할 노드인 newNode의 데이터 값 초기화
newNode->next = list->head->next; // 새로운노드가 가리키는 노드가 기존 헤드노드가 가리키는 노드가 될 수 있게 해줌 -> newNode의 next라는 포인터 = head 노드가 가리키는 노드의 포인터??
list->head->next = newNode; // 헤드노드가 가리키는 next라는 포인터에 새로 삽입할 노드의 주소값 저장
list->size++; // 리스트 크기 1 증가
}
void addLast(List* list, int data) {
Node *last = list->head; // 테일 노드 앞에 새로운 노드를 삽입하기 위해서는 해당 위치를 탐색해야함. 그걸 위해 초기 탐색을 시작할 포인터 변수를 선언하고, head 노드를 기리키는 주소값으로 초기화
while (last->next != list->tail) // Node last의 포인터 next가 포인터 tail이 아닌 동안 반복
last = last->next; // 아닐 경우 한칸 전진을 위해 포인터 last는 포인터 last가 가리키는 노드 내의 멤버인 포인터 next 으로 갱신
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = list->tail; // 새로 삽입할 노드의 포인터 next가 tail 노드를 가리킬 수 있도록 수정
last->next = newNode; // 테일 노드 직전의 노드가 새로 삽입할 노드를 가리킬 수 있도록 수정
list->size++; // 리스트 크기 갱신
}
Node* searchNode(List *list, int data) {
Node *node = list->head->next; // 인자로 받은 데이터와 동일한 값을 갖고 있는 노드를 탐색하기 위한 포인터 변수 선언 및 초기화. head 노드는 데이터를 갖고 있지 않으므로 헤드 노드 다음 노드를 가리키는 포인터 변수로 초기화 해줌
while (node != list->tail) {
if (node->data == data)
return node; // 해당 노드의 데이터 값이 타겟 데이터 값과 같을 경우 해당 노드를 가리키는 포인터 변수를 리턴
node = node->next;
}
printf("데이터를 찾지 못했습니다.\n");
return NULL;
}
void removeNode(List *list, int data) {
Node *node = list->head; // 노드 삭제라는건 삭제할 노드의 이전 노드가 삭제할 노드가 가리키는 노드를 가리킬 수 있도록 해주는 것이기 때문에 탐색하는 위치에서 다음 노드가 삭제할 노드라는 것을 알 수 있어야 함.
while (node->next != list->tail) {
if (node->next->data == data) { // 현재 노드가 가리키는 노드의 데이터가 타겟 데이터와 같으면
Node *delNode = node->next; // 삭제할 노드는 현재 노드가 가리키는 다음 노드를 의미함
node->next = delNode->next; // 현재 노드가 삭제할 노드가 가리키는 노드를 가리킬 수 있도록 해줌
free(delNode); // 삭제할 노드의 데이터 반납
list->size--; // 노드 개수 갱신
return;
}
node = node->next;
}
printf("데이터를 찾지 못했습니다.\n");
}
void printList(List *list) {
Node *node = list->head->next;
int i = 1;
while (node != list->tail) {
printf("%d 번째 노드 데이터 :%d\n", i++, node->data);
node = node->next;
}
}
void distroyList(List *list) {
Node *node = list->head;
while (node != list->tail) {
Node *delNode = node;
node = delNode->next;
free(delNode);
}
free(list->head);
free(list->tail);
}
int main() {
int i;
List list;
createlist(&list);
for (i = 1; i <= 5; i++)
addLast(&list, i);
for (i = 11; i <= 15; i++)
addFirst(&list, i);
removeNode(&list, 11);
removeNode(&list, 15);
removeNode(&list, 5);
removeNode(&list, 4);
removeNode(&list, 50);
Node *node = searchNode(&list, 14);
printf("search :%d\n", node->data);
node=searchNode(&list,12);
printf("search :%d\n", node->data);
node = searchNode(&list, 3);
printf("search :%d\n", node->data);
printList(&list);
return 0;
}Binary Search Tree
#include <stdio.h>
typedef struct Treenode{
int key;
struct Treenode *left, *right;
} treenode;
treenode* search(treenode *node, int key){
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (node->key < key){
return search(node->right, key);
} else {
return search(node->left, key);
}
}
void insertnode(treenode **root, int key){
// *root : treenode 구조체를 가리키는 포인터를 가리키는 포인터
treenode *n, *t; // n: 새로만드는노드, t: 탐색하는 노드
treenode *p = NULL; // 부모노드
t = *root;
while (t != NULL){
if (t->key == key) return; // 동일한 key 값을 가질 경우 삽입할 수 없으므로 return
p = t; // 새로운 노드가 들어갈 자리를 찾고 난 후에 해당 노드의 부모 노드를 저장해놓기 위함
if (t->key < key){ // 새로운 노드의 key 값이 현재 노드의 key 값보다 클 경우 오른쪽으로 탐색
t = t->right; // 현재 노드를 오른쪽 자식 노드로 변경
} else { // 동일한 이유로 왼쪽으로 탐색
t = t->left;
}
}
// 새로운 노드 생성
n = (treenode*)malloc(sizeof(treenode));
n->key = key;
n->right = n->left = NULL; // 리프 노드는 자식 노드가 없으므로 NULL 값으로 초기화 해줌
if (p != NULL) {
if (p->key < key){ // 새로운 노드가 들어갈 자리의 부모 노드의 key 값보다 새로운 노드의 key 값이 클 경우 부모 노드의 오른쪽 자식에 새로운 노드 연결
p->right = n;
} else {
p->left = n;
}
} else {
*root = n; // 부모노드를 가리키는 포인터값이 NULL 일 경우 빈트리이므로 새로운 노드를 루트 노드로 설정
}
}
// 삭제 연산
void deletenode(treenode **root, int key){
treenode *p, *child, *succ, *succ_p, *t;
p = NULL;
t = *root;
// 삭제할 노드 탐색
while (t->key != key && t != NULL){
p = t; // 삭제할 노드의 부모 노드
if (t->key < key){
t = t->right;
} else {
t = t -> left;
}
}
if (t == NULL) return;
// 삭제할 노드의 서브트리 상태에 따라 케이스 분류
if (t->left == NULL && t->right == NULL){
if (p != NULL) {
if (p->right == t){
p->right = NULL;
} else {
p->left = NULL;
}
} else {
*root = NULL;
}
} else if (t->left == NULL || t->right == NULL){ // 하나의 서브트리를 가진 경우
child = (t->left == NULL) ? t->right: t->left; // 왼쪽 자식이 없는 경우 오른쪽 자식 노드가 후계자 노드가 됨.
if (p != NULL){
if (p->key < t->key){ // 삭제되는 노드의 key 값이 부모노드의 key 값 보다 클 경우 후계자 노드도 부모노드의 오른쪽에 존재함.
p->right = child; // 부모노드의 오른쪽 자식과 후계자 노드를 연결함.
} else {
p->left = child;
}
} else {
*root = child; // 부모노드는 없는데 자식 노드만 있는 경우 삭제되는 노드는 루트 노드
}
} else {
// 두 개의 서브트리를 갖고 있는 경우
// 오른쪽으로 탐색하는 기준
succ_p = t; // 후계자 노드의 부모 노드 = 삭제할 노드
succ = t->right; // 후계자 노드
while (succ->left != NULL){ // 삭제할 노드의 오른쪽 서브트리 중 가장 왼쪽에 있는 값을 찾기 위함
// 타겟 노드를 찾을때까지 후계자 노드의 부모 노드 및 후계자 노드를 갱신
succ_p = succ;
succ = succ->left;
}
if (succ_p->left == succ){ // 삭제할 노드의 오른쪽 서브트리에 왼쪽 자식이 있는 경우
succ_p->left = succ->right;
} else { // 오른쪽 서브트리에 왼쪽 자식이 없을 경우 오른쪽 자식을 가리킬 수 있도록 함
succ_p->right = succ->right;
}
t->key = succ->key; // 삭제할 노드의 key 값에 succ의 key 값을 넣어줌.
t = succ;
free(t);
}
}
int main(){
}
