Chap03. 연결 리스트

- 리스트는 구현방법에 따라 크게 두 가지로 나뉜다. 

• 순차 리스트 : 배열을 기반으로 구현된 리스트 
• 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 

- 리스트는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다. 

 

- 어떠한 자료구조든 자료구조의 구현과 구현된 자료구조의 활용은 완전히 구분되도록 추상 자료형 (ADT)를 정의해야 한다.

---

문제 03-1 [리스트 라이브러리의 활용]

자료구조의 구현이 아닌 자료구조의 ADT만 갖고 활용하는 능력도 필요하다.  

#include <stdio.h>
#include "ArrayList.h"

int main()
{
    // 리스트 생성, 초기화
    List list;
    ListInit(&list);

    // 정수 1부터 9까지 저장
    for(int i = 1; i <= 9; i++)
    {
        LInsert(&list, i);
    }

    // 리스트에 저장된 값을 순차적으로 참조하여 그 합을 계산, 출력
    int sum = 0; int data;
    if(LFirst(&list, &data))
    {
        sum += data; // 첫 요소 더함
        // 더이상 탐색 요소없다면 LNext는 false를 반환할것임
        while(LNext(&list, &data))
        {
            sum += data;
        }
    }
    printf("sum = %d\n", sum);

    // 리스트에 저장된 값들 중 2의 배수와 3의 배수에 해당하는 값 삭제
    if(LFirst(&list, &data))
    {
        if(data % 2 == 0 || data % 3 == 0)
            LRemove(&list);
        while(LNext(&list, &data))
        {
            if(data % 2 == 0 || data % 3 == 0)
                LRemove(&list);
        }
    }

    // 리스트에 저장된 데이터를 순서대로 출력
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        while(LNext(&list, &data)) printf("%d ", data);
    }
}

 

---

 

배열 기반 리스트 

ArrayList.h 

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE   1
#define FALSE  0

#define LIST_LEN   100
// LData에 대한 typedef 선언
typedef int LData;

typedef struct __ArrayList
{
    LData arr[LIST_LEN]; // 배열 기반의 리스트
    int numOfData; // 리스트에 담긴 데이터의 갯수
    int curPosition; // 참조 위치 기록
} ArrayList;



typedef ArrayList 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); // 저장된 데이터 수 반환

#endif

ArrayList.c

#include <stdio.h>
#include "ArrayList.h"

void ListInit(List *plist)
{
    plist->numOfData = 0;
    plist->curPosition = -1; // 최초에 아무 위치도 가르키지 않음
}

void LInsert(List *plist, LData data)
{
    if(plist->numOfData >= LIST_LEN)
    {
        puts("저장이 불가능합니다");
        return;
    }
    plist->arr[plist->numOfData] = data;
    plist->numOfData++;
}

int LFirst(List *plist, LData *pdata)
{
    if(plist->numOfData == 0) return FALSE;

    plist->curPosition = 0; // 첫번째 위치의 데이터로 참조 위치 초기화
    *pdata = plist->arr[0];
    return TRUE;
}

int LNext(List *plist, LData *pdata)
{
    // 리스트에 더 이상 참조할 데이터 없음
    if(plist->curPosition >= (plist->numOfData)-1) return FALSE;

    (plist->curPosition)++; // 참조 위치 다음으로 이동
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}

LData LRemove(List *plist)
{
    // 삭제할 데이터의 인덱스 값 참조
    int rpos = plist->curPosition;
    int num = plist->numOfData;
    int i;
    LData rdata = plist->arr[rpos]; // 삭제할 데이터 임시로 저장

    // 데이터 한칸씩 앞으로 이동
    // rpos 위치의 데이터를 삭제하는게 아닌 뒤의 데이터로 덮어버림
    for(i = rpos; i < num-1; i++)
        plist->arr[i] = plist->arr[i+1];

    (plist->numOfData)--;
    // 참조위치 한칸 되돌림, curPosition은 최근 참조가 이뤄진 데이터의 인덱스 정보 담고있어야함
    (plist->curPosition)--;
    return rdata; // 삭제된 데이터 반환
}

int LCount(List *plist)
{
    return plist->numOfData;
}

 

---

 

리스트에 구조체 변수 저장하기

 

Point.h 

#ifndef __POINT_H__
#define __POINT_H__

typedef struct __point
{
    int xpos;
    int ypos;
} Point;

void setPointPos(Point *ppos, int xpos, int ypos);
void ShowPointPos(Point *ppos);
int PointComp(Point *pos1, Point *pos2);

#endif

Point.c 

#include <stdio.h>
#include "Point.h"

void SetPointPos(Point *ppos, int xpos, int ypos)
{
    ppos->xpos = xpos;
    ppos->ypos = ypos;
}

void ShowPointPos(Point *ppos)
{
    printf("[%d, %d] \n", ppos->xpos, ppos->ypos);
}

int PointComp(Point *pos1, Point *pos2)
{
    if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
        return 0;
    else if(pos1->xpos == pos2->xpos)
        return 1;
    else if(pos1->ypos == pos2->ypos)
        return 2;
    else
        return -1;
}

 

위 구조체를 리스트에 저장하기 위해 ArrayList.h와 ArrayList.c 에 어느 정도 수정이 필요할까?

ArrayList.h 에서 데이터의 타입을 typedef int로 선언했기 때문에 typedef 선언만 바꿔주면 된다. 

typedef int LData 를 typedef Point *LData로 

 

 

#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"

int main()
{
    List list;
    Point comPos;
    Point *ppos;

    ListInit(&list);

    // 4개의 데이터 저장
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 2);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 2);
    LInsert(&list, ppos);

    // 저장된 데이터 출력
    printf("number of data: %d\n", LCount(&list));

    if(LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while(LNext(&list, &ppos))
            ShowPointPos(ppos);
    } printf("\n");

    // xpos가 2인 모든 데이터 삭제
    comPos.xpos = 2;
    comPos.ypos = 0;

    if(LFirst(&list, &ppos))
    {
        if(PointComp(ppos, &comPos) == 1)
        {
            // 삭제한 데이터 리턴, 여기선 Point 구조체 변수의 주소값
            ppos = LRemove(&list);
            free(ppos); // 삭제했으므로 메모리 해제
        }

        while(LNext(&list, &ppos))
        {
            if(PointComp(ppos, &comPos) == 1)
            {
                ppos = LRemove(&list);
                free(ppos);
            }
        }
    }

    // 삭제 후 남은 데이터 전체 출력
    printf("number of data: %d \n", LCount(&list));

    if(LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while(LNext(&list, &ppos)) ShowPointPos(ppos);
    }
    printf("\n");
}

 

일반적으로 메모리의 해제는 리스트가 책임을 지지 않는다! 

 

---

문제 03-2 [리스트의 활용]

마찬가지로 헤더파일 즉 추상 자료형만 보고 활용해보기.

 

NameCard.h

#ifndef __NAME_CARD_H__
#define __NAME_CARD_H__

#define NAME_LEN 30
#define PHONE_LEN 30

typedef struct __namecard
{
    char name[NAME_LEN];
    char phone[PHONE_LEN];
} NameCard;

// NameCard 구조체 변수 동적할당, 초기화 후 주소 값 반환
NameCard *MakeNameCard(char *name, char *phone);
// NameCard 구조체 변수 정보 출력
void ShowNameCardInfo(NameCard *pcard);
// 이름 같으면 0, 다르면 0 아닌 값 반환
int NameCompare(NameCard *pcard, char *name);
// 전화번호 정보를 변경
void ChangePhoneNum(NameCard *pcard, char *phone);

#endif

 

NameCard.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "NameCard.h"

NameCard *MakeNameCard(char *name, char *phone)
{
    NameCard *cpos = (NameCard*)malloc(sizeof(NameCard));
    strcpy(cpos->name, name);
    strcpy(cpos->phone, phone);
    return cpos;
}

void ShowNameCardInfo(NameCard *pcard)
{
    printf("name is %s\n", pcard->name);
    printf("phone number is %s\n\n", pcard->phone);
}

int NameCompare(NameCard *pcard, char *name)
{
    return strcmp(pcard->name, name);
}

void ChangePhoneNum(NameCard *pcard, char *phone)
{
    strcpy(pcard->phone, phone);
}

 

NameCardListMain.c

#include <stdio.h>
#include <stdlib.h>
#include "NameCard.h"
#include "ArrayList.h"

int main()
{
    List list;
    NameCard *cpos;
    ListInit(&list);

    // 1. 3명의 전화번호 정보 저장
    cpos = MakeNameCard("LEE", "111-111");
    LInsert(&list, cpos);
    cpos = MakeNameCard("PARK", "222-222");
    LInsert(&list, cpos);
    cpos = MakeNameCard("KIM", "333-333");
    LInsert(&list, cpos);

    // 2. 특정 이름 대상 탐색, 정보 출력
    printf("2. 특정 이름 대상 탐색, 정보 출력\n");
    if(LFirst(&list, &cpos))
    {
        if(NameCompare(cpos, "LEE")==0) ShowNameCardInfo(cpos);
        while(LNext(&list, &cpos))
            if(NameCompare(cpos, "LEE")==0) ShowNameCardInfo(cpos);
    }

    // 3. 특정 이름 대상 탐색 진행, 그 사람 전화번호 정보 변경
    if(LFirst(&list, &cpos))
    {
        if(NameCompare(cpos, "LEE")==0)
            ChangePhoneNum(cpos, "123-123");
        while(LNext(&list, &cpos))
            if(NameCompare(cpos, "LEE")==0)
                ChangePhoneNum(cpos, "123-123");
    }

    // 4. 특정 이름 대상 탐색, 그 사람 정보 삭제
    if(LFirst(&list, &cpos))
    {
        if(NameCompare(cpos, "KIM")==0)
        {
            cpos = LRemove(&list);
            free(cpos);
        }

        while(LNext(&list, &cpos))
        {
            if(NameCompare(cpos, "KIM")==0)
            {
                cpos = LRemove(&list);
                free(cpos);
            }
        }
    }

    // 삭제 후 남은 데이터 전체 출력
    printf("KIM 삭제후\n");
    printf("number of data: %d \n", LCount(&list));
    // 5. 출력
    if(LFirst(&list, &cpos))
    {
        ShowNameCardInfo(cpos);

        while(LNext(&list, &cpos))
            ShowNameCardInfo(cpos);
    }
}