허리 통증으로 병원다니고, 어머니 잠시 입원하고, 컴퓨터 하드도 맛이 가서 고치고,
보안 기사 시험 접수도 했고~
대신 사무자동화 시험을 100점으로 합격하는 영광(?)을 누렸다.
보안 기사 시험(7/6) 까지는 당분간 자료구조 공부는 중단해야겠다.
연결 리스트 2까지만 일단 복습해 보겠다~
---------------------------------------------------------------------------------
3장은 배열에 의한 리스트였다. 즉, 자료가 쭈~~~욱 다 연결되어 있는 배열 형태라는 거다.
배열의 단점이 길이가 정해져 있기 때문에 잘못하면
오버플로우가 걸리는 비극이 일어난다는 것이다.
그래서 연결 리스트2 는 이것을 동적으로 메모리 연결을 하겠다는 것이다.
아따 동적 연결은 또 뭐당가??
그야말로 필요할 때마다 동적(?)으로 메모리를 야금야금 잡아먹으면서 늘였다 줄였다 하며 자료를 저장하겠다는 것이다.
동적으로 하기 위해서 필요한 요소가 몇가지 있다.
1. 메모리 할당
2. 메모리 접근
3. 메모리 해제
뭐 너무도 당연한 것이지만 함 써봤다.
배열에는 배열 번호(정확히는 주소)가 있어서 쉽게 접근이 가능했으나
동적인 연결리스트에서는 다음 자료가 어디에 붙어 있는지 찾아가는 주소가 있어야 한다.
이 주소가 없으면 그냥 뒷자료는 유실되고, 상사에게 조낸 쳐맞는거다.
여기에선 당연하게 포.인.터. 가 나온다.
벌써 포인터 이야기만 듣고 나가는 사람은 없길 바란다.
포인터를 쉽게 생각해보자.
윈도우 단축 아이콘을 바탕화면에 끌어다 쓰지 않는가??
그 단축 아이콘에는 실제 실행되는 파일의 "위치 정보"가 있다.
이 위치 정보가 바로 "포인터 주소"인 것이다!!
어째든 연결 리스트에는 각 노드(책에서는 자료를 담은 바구니로 표현했다)마다 다음 노드의 위치를 기억을 해놓는 것이다.
마치 사슬이 하나하나 연결되듯이 자료가 여기저기 흩어져있지만(메모리 상에)
이걸 연결 해서 쓰는게 동적 연결 리스트 구조인 것이다!!
신혼부부가 몸으로 대화하듯이(어머>.<) 개발자는 코드로 대화를 해야한다. 코드를 닥치고 보자
---------------------------------------------------------------------------------
LiinkedRead.c
#include <stdio.h>
#include <stdlib.h>
typedef struct _node
{
int data;
struct _node * next; //재귀함수
} Node;
int main(void)
{
Node * head = NULL; // NULL 포인터 초기화
Node * tail = NULL;
Node * cur = NULL;
Node * newNode = NULL;
int readData;
/**** 데이터를 입력 받는 과정 ****/
while(1)
{
printf("자연수 입력: ");
scanf("%d", &readData);
if(readData < 1)
break;
/*** 노드의 추가과정 ***/
newNode = (Node*)malloc(sizeof(Node));
newNode->data = readData;
newNode->next = NULL;
if(head == NULL)
head = newNode;
else
tail->next = newNode;
tail = newNode;
}
printf("\n");
/**** 입력 받은 데이터의 출력과정 ****/
printf("입력 받은 데이터의 전체출력! \n");
if(head == NULL)
{
printf("저장된 자연수가 존재하지 않습니다. \n");
}
else
{
cur = head;
printf("%d ", cur->data); // 첫 번째 데이터 출력
while(cur->next != NULL) // 두 번째 이후의 데이터 출력
{
cur = cur->next;
printf("%d ", cur->data);
}
}
printf("\n\n");
/**** 메모리의 해제과정 ****/
if(head == NULL)
{
return 0; // 해제할 노드가 존재하지 않는다.
}
else
{
Node * delNode = head;
Node * delNextNode = head->next;
printf("%d을(를) 삭제합니다. \n", head->data);
free(delNode); // 첫 번째 노드의 삭제
while(delNextNode != NULL) // 두 번째 이후의 노드 삭제 위한 반복문
{
delNode = delNextNode;
delNextNode = delNextNode->next;
printf("%d을(를) 삭제합니다. \n", delNode->data);
free(delNode); // 두 번째 이후의 노드 삭제
}
}
return 0;
}
---------------------------------------------------------------------------------
자~ 이걸 이제 조금 분석해 보자.
구조체 Node를 선언했다.
이건 계속 다음 노드를 보면서 next로 이동이동 하는 것이다.
그럼 메인안에 있는 변수들을 보자.
뭔 놈의 포인터 변수가 이리 많냐~? 하는 분들은 좌절하지 말라.
head 는 노드의 시작 지점, tail 은 끝 지점, cur 은 다음 노드의 위치 값
을 저장하는 곳 포인터 변수이다.
연결 리스트에서 삽입/삭제시 가장 중요하게 해야할 일이 있다.
노드를 끊기 전에는 반드시 다음 노드의 주소 값을 보존해야 한다는 것이다.
걍 아무 생각 없이 끊어버리면 다음 주소 이후의 데이터는 접근이 불가능해져서 없어져 버린다는 것이다.
이건 그림을 보고 이해하는 것이 빠른데 여긴 그림 그리기 도구도 없는 후진 블로그라서 걍 책으로 이해하길 바란다-_-;
뒤로 훨씬 긴 이야기가 있지만 지금 위의 소스를 삽입/삭제/조회/정렬 로 디테일하게 들어간 것이니 역시 책을 보고 이해를 할 수 밖에 없다 ㅡㅡ;;;
위 소스에는 정렬 부분이 없으니 정렬만 따로 언급하겠다.
정렬에 필요한 요소가 3가지 있다.
1. 정렬 기준이 되는 SetSortRule 함수
2. SetSortRule 함수를 통해서 전달된 함수 정보를 저장하기 위한 LinkedList의 멤버comp
3. comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SLinsert 함수
역시 개발자는 코드로 설명해야 한다. 코드를 보자 -_-
---------------------------------------------------------------------------------
//헤더 부분
#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int LData;
typedef struct _node
{
LData data;
struct _node * next;
} Node;
typedef struct _linkedList
{
Node * head;
Node * cur;
Node * before;
int numOfData;
int (*comp)(LData d1, LData d2);
} LinkedList;
typedef LinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, LData data);
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
LData LRemove(List * plist);
int LCount(List * plist);
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));
#endif
---------------------------------------------------------------------------------
//연결리스트 부분
#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
void ListInit(List * plist)
{
plist->head = (Node*)malloc(sizeof(Node));
plist->head->next = NULL;
plist->comp = NULL;
plist->numOfData = 0;
}
void FInsert(List * plist, LData data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = plist->head->next;
plist->head->next = newNode;
(plist->numOfData)++;
}
void SInsert(List * plist, LData data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
Node * pred = plist->head;
newNode->data = data;
while(pred->next != NULL &&
plist->comp(data, pred->next->data) != 0)
{
pred = pred->next;
}
newNode->next = pred->next;
pred->next = newNode;
(plist->numOfData)++;
}
void LInsert(List * plist, LData data)
{
if(plist->comp == NULL)
FInsert(plist, data);
else
SInsert(plist, data);
}
int LFirst(List * plist, LData * pdata)
{
if(plist->head->next == NULL)
return FALSE;
plist->before = plist->head;
plist->cur = plist->head->next;
*pdata = plist->cur->data;
return TRUE;
}
int LNext(List * plist, LData * pdata)
{
if(plist->cur->next == NULL)
return FALSE;
plist->before = plist->cur;
plist->cur = plist->cur->next;
*pdata = plist->cur->data;
return TRUE;
}
LData LRemove(List * plist)
{
Node * rpos = plist->cur;
LData rdata = rpos->data;
plist->before->next = plist->cur->next;
plist->cur = plist->before;
free(rpos);
(plist->numOfData)--;
return rdata;
}
int LCount(List * plist)
{
return plist->numOfData;
}
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
plist->comp = comp;
}
---------------------------------------------------------------------------------
//메인함수 부분
#include <stdio.h>
#include "DLinkedList.h"
int WhoIsPrecede(int d1, int d2)
{
if(d1 < d2)
return 0; // d1이 정렬 순서상 앞선다.
else
return 1; // d2가 정렬 순서상 앞서거나 같다.
}
int main(void)
{
// List의 생성 및 초기화 ////////////
List list;
int data;
ListInit(&list);
SetSortRule(&list, WhoIsPrecede);
// 5개의 데이터 저장 ///////////////
LInsert(&list, 11); LInsert(&list, 11);
LInsert(&list, 22); LInsert(&list, 22);
LInsert(&list, 33);
// 저장된 데이터의 전체 출력 ////////////
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
// 숫자 22을 검색하여 모두 삭제 ////////////
if(LFirst(&list, &data))
{
if(data == 22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data == 22)
LRemove(&list);
}
}
// 삭제 후 저장된 데이터 전체 출력 ////////////
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
return 0;
}
---------------------------------------------------------------------------------
이렇게 보기엔 무지하게 복잡하고 어이 없어 보이지만
간단하게 요약해 보겠다.
1. 앞 값과 뒷 값을 비교한다.
2. 정렬 기준에 따라 0이나 1을 반환한다.
3. 정렬 기준에 따라 노드의 위치를 바꾼다.
3-1. 같은 값은 냅둔다.
1~3을 죽어라 반복한다.
4. 완료되었으면 출력하고 끝낸다.
내가 봐도 너무 대충 설명한 거 같아서 좀 찔린다 ㅡㅡ;;
역시 이것은 복습의 장소이지 공부의 장은 아니다.
책을 보고, 직접 해보고 이해하는 수밖에 없다.
날씨도 점점 더워지고, 허리도 아프고, 자격증 시험의 압박도 있고,
잠시 자료구조 공부는 중단하기로 했다.
책은 "윤성우의 자료구조" 이다.
그럼 당분간 빠이여~~ ;;;
