이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
목표 : 내가 헤더파일을 보고 구현해보고 구현한 함수들을 자료형을 바꿔가며 자유롭게 메인함수를 짜보자.
헤더 파일과 구현된 함수들 및 메인함수를 이해하기 위해 필요한 지식
1.SetSortRule
void SetSortRule(List plist, int(comp)(LData d1,LData d2));
는 LData 자료형을 가지는 변수 2개를 매개변수로 가지는 함수 포인터를 매개변수로 가진다.
(함수명은 함수포인터)
이 때 이 함수 포인터는 정렬기준을 정의하는 함수로
d1,d2를 받고 d1이 앞서면 0, d2가 앞서면 1을 리턴하는 함수이다.
즉, 이 comp에 들어갈 함수만 정의해주면 정렬은 알아서 해준다는 것이다.
2. 더미노드
헤더가 더미노드를 가리키게 함으로서 코드를 좀더 일관성있게 짤 수 있게 된다.
3.구현
(1)헤더파일
#ifndef D_LINKED_LIST_H
#define D_LINKED_LIST_H
#define TRUE 1
#define FALSE 0
typedef int LData;//일단 int를 LData로 사용
typedef struct _node
{
LData data;//int형 데이터를 가지고
struct _node * next;//다음 node의 주소를 가진 구조체를
} Node;//Node라고 한다.
typedef struct _linkedList//연결리스트 구조체는
{
Node head;//헤드와
Node cur;//cur와
Node before;//before에 대한 정보를 가진다. before는 삭제시 사용된다. 삭제시 before의 정보를 가지고 cur를 삭제후 before ->next = cur->next로 바꾸는 것이다. cur->next는 삭제 함수 내부에 정의된 임시변수 Node temp 등에 담겠지
int numOfData;//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);//LFirst함수 즉, head->next로 가는 함수이다.
int LNext(List plist, LData pdata);//cur->next로 가는 함수, 이전처럼 data변수의 주소를 받아와서 data변수에 이 값을 저장할 것이다.
LData LRemove(List plist);//plist의 주소를 받아와서 cur에 저장되어 있는 노드 삭제
int LCount(List plist);
void SetSortRule(List plist, int (comp)(LData d1, LData d2));//함수를 받아와서 list -> comp에 등록
void FInsert(List * plist, LData data)//comp가 NULL일 때 호출,즉 리스트 맨처음에 data추가
(이 코드는 data를 넣는 순서와 반대로 저장
ex. 1 2 3 4 5순서대로 입력 head부터 출력시 5 4 3 2 1출력)
void SInsert(List * plist, LData data)//comp가 NULL이 아닐 때 호출, 즉 List에 데이터를 정렬하여 삽입
#endif
(2)소스 파일
#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
void ListInit(List plist)
{
plist->head = (Node)malloc(sizeof(Node));//더미
plist->head->next = NULL;//더미의 next는 NULL로 설정
plist->comp = NULL;//정렬 기준 초기화
plist->numOfData = 0;//아직 저장X이니 numOfData는 0
}
void FInsert(List plist, LData data)//comp가 NULL일 때 호출
{
Node newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = plist->head->next;// 이 코드는 head에서부터 자료를 집어넣고 있다.
plist->head->next = newNode;
//ex. 1 2 3 4 5순으로 집어넣으면
head 1(헤드의 넥스트)
head 2(이전 헤드의 넥스트를 넥스트로 가진다. 자신은 헤드의 넥스트가 된다.) 1(이전 헤드의 넥스트)
같은 순서로 head 3 2 1
head 4 3 2 1
head 5 4 3 2 1 이 된다.
(plist->numOfData)++;}
void SInsert(List plist, LData data)
{
Node newNode = (Node)malloc(sizeof(Node));
Node pred = plist->head;//헤드의 주소가 pred에 저장
newNode->data = data;
while(pred->next != NULL &&
plist->comp(data, pred->next->data) != 0)
//헤드의 넥스트가 0이면 pred = head
삽입할 데이터가 pred의 next의 data보다 앞에 있어야 하면 comp에서 0리턴됨.
{
pred = pred->next;
}
newNode->next = pred->next;
pred->next = newNode;
//1. 헤드의 넥스트가 0이어서 pred=head인 경우
새로운 노드의 넥스트는 헤드의 넥스트 즉, 널이 되고 head의 넥스트는 널이 된다. 즉, 첫데이터 삽입 완료
2.0이 리턴되면
새로운 노드의 넥스트는 pred의 넥스트 즉, newNode의 다음이 pred->next가 된다.
pred의 다음은 newNode가 된다.
ex. 0 1 2 4 5 오름차순 정렬
3 삽입
1이 pred면 comp는 1리턴
2가 pred면 comp는 0리턴, comp(3,4)는 0을 리턴하기 때문
그럼 2의 next가 3을 데이터로 가진 새로운 노드
3의 next가 4를 가진 노드가 되므로 연결리스트는 0 1 2 3 4 5가 된다.
(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;//cur의 before은 헤드
plist->cur = plist->head->next;
*pdata = plist->cur->data;
return TRUE;//LFirst를 찾으면 즉, 데이터가 있으면 1이 리턴, 쓸모가 많다. ex. 모두 삭제되면 0이 반환되겠지}
int LNext(List plist, LData pdata)
{
if(plist->cur->next == NULL)//cur->next에 저장된 데이터가 없으면
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;//삭제할 주소는 cur
LData rdata = rpos->data;//삭제할 데이터(리턴할 준비)
plist->before->next = plist->cur->next;
plist->cur = plist->before;//매우 중요하다. 마지막으로 검토한 데이터의 주소로 cur를 돌리는 과정, 이래야 모든 연결리스트의 자료가 삭제의 영향을 받지 않고 탐색가능하다.
free(rpos);//malloc으로 할당받았으므로 free해줘야 한다.
(plist->numOfData)--;
return rdata;//삭제한 데이터 리턴}
int LCount(List * plist)
{
return plist->numOfData;
}
void SetSortRule(List plist, int (comp)(LData d1, LData d2))
{
plist->comp = comp;
}
(3)메인 함수
#include <stdio.h>
#include "DLinkedList.h"
int main(void)
{
// List의 생성 및 초기화 /////////////////////////////
List list;
int data;
ListInit(&list);
// 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;}
