본문 바로가기

공부/자료구조 | 알고리즘

(23)
[자료구조] 연결리스트 노드 삭제 단순 연결리스트의 노드 삭제 pre가 NULL인 경우: 선행 노드가 없는 경우 pre가 NULL아 아닌 경우: 선행 노드가 있는 경우 1. pre가 NULL인 경우: 선행 노드가 없는 경우 연결 리스트의 첫 번째 노드를 삭제하고 헤드 포인터 변경 // head : 헤드 포인터 // x: 삭제될 노드가 가진 데이터 void remove_node(Node *head, int x) { Node *list = head; if( head == NULL ) return; // 삭제할 것이 없음 else if( head->data == x ) // 찾는 노드(삭제 노드)가 첫 노드인 경우 { // delete list; free(list); head = head->link; return; } else // 나머지 경..
[자료구조] 연결리스트 만들고 출력하기 Linked List 연결리스트 만들고 출력하기 - 아래 구조체를 사용하여, 정수 10, 20, 30, 40, 50, 60, 70, 80으로 구성된 연결리스트를 만들고 - 시작 노드의 주소를 헤드 포인터 head에 연결시키시오. class Node { int score; Node *link; }; - 또한 head를 시작으로 연결리스트의 노드들을 따라가면서 각 노드의 값을 출력하시오. - 10, 20, 30, 40, 50, 60, 70, 80 이 출력되는지 확인하시오. - 배열은 사용하지 말고, 연결 리스트만 사용하시오. - 주어진 값 대신 값을 입력 받도록 수정해 보시오. #include using namespace std; class Node { public: int score; //점수 Node *link; //다음 노..
[자료구조] 단순 연결리스트 노드 삽입 노드 삽입 방법 노드를 삽입할 위치(선행 노드)를 아는 경우 헤드포인터가 NULL인 경우: 공백 리스트에 삽입 pre가 NULL인 경우: 리스트의 맨 처음에 삽입 일반적인 경우: 리스트의 중간/마지막에 삽입 리스트의 제일 마지막에 노드를 추가하는 경우 리스트의 제일 처음 노드로 삽입하는 경우 -> 권장 1. 선행 노드를 아는 경우 // head: 리스트의 헤드 포인터 // pre : 선행 노드 // new_node : 삽입될 노드 (NULL이 아니라고 가정) void insert_node(Node *head, Node *pre, Node *new_node) { if( head == NULL ){// 공백리스트인 경우 // new_node->link = NULL; head = new_noe; } else ..
[자료구조] 단순 연결리스트 단순/단일 연결리스트 하나의 링크 필드를 이용하여 연결 마지막 노드의 링크값은 다음 노드가 없으므로 그 값을 NULL(‘\0’)로 설정 헤드 포인터는 첫 노드의 위치를 가리킴 단순 연결리스트의 구현 헤드포인터(head pointer) 연결 리스트의 맨 처음 노드를 가리키는 포인터 예) 위 그림에서 p1은 전체 리스트를 가리키는 헤드 포인터 역할 노드 : 데이터 필드와 링크 필드의 구조체로 정의 노드의 생성: new를 이용하여 동적 메모리 할당 데이터 필드와 링크 필드 설정 두번째 노드 생성과 첫번째 노드와의 연결 구현시 유의할 점 헤드 포인터 점검 연결 리스트에서 노드 삭제/삽입 등의 변경 작업시, 헤드 포인터가 계속 잘 유지되도록 신경을 쓰자! NULL 포인터 검사 포인터가 NULL값을 가지는 경우에 ..
[자료구조] 배열과 포인터 / 2차원 배열과 포인터 예제 배열과 포인터 배열명은 자체로 주소 정보도 가진다. 예를 들어, 인천공항라는 대표명은 동시에 주소/위치를 나타낸다. 배열명은 포인터의 성격을 갖는다. 배열명을 마치 포인터 변수와 동일하게 사용한다. 단, 포인터 변수는 그 값을 변경할 수 있으나, 배열명의 값을 변경할 수는 없다. -> 배열명은 포인터 상수라는 표현을 사용 포인터 변수가 배열을 가리킬 경우, 증가/감소의 의미한다. ++, +1 연산의 의미 : 다음 원소 --, -1 연산의 의미 : 이전 원소 배열명은 그 자체로 배열의 시작 주소를 의미한다. ‘배열명’과 ‘&배열명’, 그리고 ‘&배열첫원소’ 모두 동일한 주소값 배열 내 원소들은 연속된 기억장소를 차지한다. 2차원 배열과 포인터 배열명은 자체로 주소 정보도 가진다. 배열명은 포인터의 포인터(..
[자료구조] 동적 메모리 할당 / 반별, 과목별 평균 성적 구하기 예제 배열의 문제점 원소의 개수가 미리 파악이 안되는 경우 문제 발생 학생 성적 평균 예의 경우, 학생수를 모른다면? 아주 큰 배열로 선언할 수도 있으나, 비효율적임 실제 학생수에 맞는 배열 선언이 필요 학생수는 실행 도중 사용자로부터 입력을 받을 수도 있음 → 동적 메모리 할당의 필요성 ! 동적 메모리 할당 동적 메모리 할당 (Dynamic Memory Allocation) 실행 도중, 추가적인 메모리 영역을 배정받고자 하는 경우에 사용 malloc() 함수가 대표적으로 사용됨 void *malloc(int size) (char *) malloc(100); (int *) malloc(sizeof(int)*20); C++는 “new 객체명”과 같은 방식 주로 사용(보다 편리) 예) int *ptr = new ..
[자료구조] 배열 / 배열을 이용한 연도 및 분기별 통계 예제 배열 가장 기본적인 자료구조 같은 데이터 유형을 가진 자료들의 그룹/세트 연속된 기억장소를 배정받음 배열명 : 전체를 대표하는 명칭 원소 : 배열에 소속된 각 자료를 일컫는 용어 인덱스 : 각 원소의 위치를 나타내는 숫자 배열의 선언과 사용 자료형 배열이름 [ 원소개수 ] (예) int score[6]; 각 원소를 지칭할 때, score[0],…. score[5] 라고 사용 1차원 배열 1차원 배열의 선언 자료형 배열명 [ 원소개수 ] Int score[6], char answer[20], double data[12]; 배열 값의 초기화 배열 원소들은 초기화하지 않으면 임의의 값을 가짐 (예외 있음) 자료형 배열명 [ 원소개수 ] = { 초기값 리스트 } 2차원 배열 2차원 배열의 선언 자료형 배열명 [..