Data Structure [C]/문돌이도 할 수 있는 [C언어 자료구조] (30) 썸네일형 리스트형 #30 다항식을 연결리스트로 구현하기 다항식을 연결 리스트로 구현하는 방법을 알아보자. 굳이 왜 연결 리스트로 구현할까? 다음과 같은 다항식의 구조를 생각해보면 이해하기 쉽다. A(x) 다항식엔 계수인 a와 지수인 e의 정보만 포함되면 된다. 각 항을 노드로 구성하면 쉽게 해결할 수 있다. [계수(coef) + 지수(expon) + 포인터(link)]로 하나의 노드를 구성하는 방법을 생각해볼 수 있다. 일단 구현해보면 좋은 일이 생기지 않을까? 하는 개떡같은 마음으로 다항식을 분해해보자. 실제로 다항을 계산해야하는 복잡한 연산코드를 짜는 사람들이 아니라면 실무에서 잘 쓰이진 않는다. 꿈꾸고 사랑하고 열렬히 행하고 성공하기 위하여 다항식을 연결 리스트로 표현하기 다항식 자체를 나타내는 것은 아래와 같은 식으로 표현할 수 있다. [계수(coef.. #29 [C 자료구조] 연결 리스트 연결 및 역순 만들기 오늘은 연결 리스트를 연결하고 또 이의 역순을 만드는 방법을 배워볼 것이다. 내가 배워야 한다. 문득 든 생각인데, 파이썬 할 때는 자료구조는 생각지도 않고 그저 알고리즘만 생각했다. 그러나 c언어를 공부하면서 배우는 자료형 공부도 끝이 없는 것 같다. 쉽게 클래스로 쉽게 쉽게 해결했던 것들이, 사실은 기본적이고 필수적인 프로그래밍의 기초였던 것이다. 뭐, 어쨌건 우리는 공부를 이어나가야 한다. 연결 리스트끼리 연결하기 1) 연결 리스트 스트럭쳐 만들기 typedef struct listNode listPointer; typedef struct listNode { int data; listPointer *link; } 이제는 눈감고도 만들 수 있는 연결 리스트 스트럭쳐 2) 두 개의 연결 리스트 세트를 .. #28 [C 자료구조] 원형 연결 리스트/이중 연결 리스트 리스트도 큐와 마찬가지로 원형 연결 리스트가 있다! 워후! 또한 앞 뒤로 연결이 가능한 이중 연결 리스트도 있다! 워후! 다재다능한 두 리스트의 활용법을 오늘 알아보도록 하자. 한 번에 많은 포스팅을 올리니 체력 고갈이 심하다. 원형 연결 리스트(Circular Linked List) 마지막 노드가 리스트의 첫 노드를 가리키는 형태의 리스트다. 마지막 노드에 대한 포인터 last가 그대로 있다. 이는 새로운 노드 삽입용!! 원형 연결 리스트 생성 코드를 봐보자 1) 노드 생성 스트럭쳐 구성 typedef struct listNode NODE; struct listNode { int data; NODE *link; } 기계와 같이 연결리스트를 만들어 준다. 이제 프로라면 가능해야한다. 일단 난 아님 2) .. #27 [C 자료구조] 연결 리스트: 스택/큐/덱 구현하기 이전 포스팅에서 살펴봤던당했던 스택/큐/덱은 연결 리스트로 구현하면 훨씬 더 효율적으로 표현할 수 있다. 그래서 실제로 연결리스트로 구현되는 것들이 대부분이다. 오늘 세 가지 부분에 대해서 DEEEEEEEEEEEP하게 들어가 보도록 하자. 반드시 스택/큐 에 대한 일반적인 구현 방식에 대해 선행지식이 있어야 한다. 파이팅하자 파이리썬!! 스택 with 연결 리스트 연결 리스트로 구현한 스택은 다음과 같은 장점을 가지고 있다. - 다 음 - 1) 노드 추가에만 메모리를 할당, 이전보다 효율적 2) top 노드를 포인터 변수가 가리키고 포인터 변수로 직접 접근 3) 그러나 포인터 연산 필요 연결 리스트로 오면서 값 별 포인터가 추가된 모습이다. 바로 연결리스트로 구현한 스택을 코드로 봐보자. 1) 스택형 연.. #26 [C 자료구조] 단순하지 않은: 단순 연결 리스트 오늘은 단순 연결 리스트의 코딩 법에 대해서 빡세게 알아볼 예정이다. 이전의 #18 자기 참조 구조체의 포스팅을 한 번 보고 오면 도움이 될 것이다. 기본적인 연결 리스트를 만드는 문장을 짜보자. 0) 공백의 노드 만들기 typedef struct lintNode NODE; struct listNode { int data NODE *link; }; 이러면 1개의 데이터와 1개의 주소 값(다른 노드를 가리킬)을 가지는 노드를 만드는 struct를 짠 것이다. 1) 포인터를 생성하고(공백의 포인터를 만들어놔야 노드를 각각 만들 때 메모리 할당이 가능하다.) NODE *ptr = NULL; 2) 공백 메모리인지 확인한 뒤 #define IS_EMPTY(ptr) (!(ptr)) 3) 동적 메모리를 할당해보자 p.. #25 [C 자료구조] 리스트 개념: 가장 많이 쓰이는 선형 자료형 파-하! (파이리썬에 얼떨결에 구글링 해서 들어온 사람들 하이라는 뜻) 오늘은 리스트에 대해서 알아볼 것이다. 리스트는 그 모오오오오든 자료구조형에서 가장 많이 쓰이고 종류도 더럽게 많은 자료형이다. 기억 날지 모르겠지만 아래의 자료형 그래프를 보자. 자료구조 단순구조 (Simple) 정수(int) 실수(float, double) 문자열(char) 선형구조 (Linear) 리스트(List) 선형리스트 연결리스트 스택(Stack) 큐(Queue) 데크(DeQue) 비선형구조 (Non-Linear) 트리(Tree) 일반 트리 이진 트리 그래프(Graph) 방향 그래프 무방향 그래프 파일 구조 (File Organization) 순차파일 색인파일 직접파일 다른 언어 혹은 C언어를 깊이 공부해본 사람이라면 리스.. #24 [C 자료구조] 큐 with 동적 할당 배열 지난, 지지난 포스팅에서 큐에 대해서 간략하게 설명했다! 큐 또한 다른 배열과 마찬가지로 동적 메모리를 할당할 수 있다ㅎㅎ 이 죽일 놈의 사랑 코드를 n배 어렵게 하는 동적 할당 배열을 큐와 함께 사용해보자. 아이 신나! 동적 할당 배열 큐 개념 동적 할당 배열은 정적 배열의 큐가 메모리가 부족해지는 경우에 대비해서 만들어졌다. (+메모리 낭비 방지) 따라서 다음과 같이 확장해야 한다. 우리는 이미 포화된 큐, 그리고 마지막 인수가 중간에 있는 원형 큐에서 메모리를 확장해야 한다. 1) 이렇게 되면 다음과 같이 중간에 빵꾸가 나게 된다. 따라서 배열 크기를 확장 후 원소의 위치를 복사해서 조정해야 한다. 2) 먼저 아래와 같이 잘라내어 값을 붙여 넣기 한 뒤 3) ABCDEFG 위치를 다 같이 조정해준다.. #23 [C 자료구조] 큐의 개념 큐는 이전에 언급했듯이 놀이공원에 줄서는 것과 같다고 볼 수 있다. 먼저 온 사람이 먼저 입장하고 나중에 온 사람은 늦게 들어가는 FIFO(First In First Out) 형식을 띈다. 자료구조에서는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터를 출력하는 방식이라 생각하면 된다. 즉 스택과 다르게, 삽입은 큐의 제일 끝에서, 삭제는 큐의 제일 앞에서 일어나는 것이다. 큐 사용 예시 CPU의 태스크 스케쥴링 네트워크 프린터 실시간 시스템 인터럽트 처리 다양한 이벤트 구동 방식 컴퓨터 시뮬레이션 콜센터 전화 처리 이진 트리의 레벨 순화 그래프에서 너비 우선 탐색 큐의 구현 방법 큐의 구현 방법은 스택과 마찬가지로 배열과 연결리스트가 있다. 또한 마지막 데이터가 첫 데이터를 참조하는 원형.. 이전 1 2 3 4 다음
