반응형
리스트
자료구조에서 리스트는 구현 방법에 따라서 순차 리스트(ArrayList)와 연결 리스트(LikedList)로 나뉜다. 순차 리스트는 배열을 기반으로 구현된 리스트이고, 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다.
배열 기반 리스트의 단점
* 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
* 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
배열 기반 리스트의 장점
* 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.
리스트의 ADT
List 자료구조의 ADT
* void ListInit(List * plist);
- 초기화할 리스트의 주소 값을인자로 전달한다.
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
* void LInsert(List * plist, LData data);
- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
* int LFirst(List * plist, LData * pdata);
- 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
- 데이터의 참조를 위한 초기화가 진행된다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
* int LNext(List * plist, LData * pdata);
- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
- 순차적인 참조를 위해서 반복 호출이 가능하다.
- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
* LData LRemove(List * plist);
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
- 삭제된 데이터는 반환된다.
- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
* int LCount(List * plist);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.
배열 기반 리스트
ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData;
typedef struct __ArrayList
{
LData arr[LIST_LEN];
int numOfData;
int curPosition;
} ArrayList;
/*** 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
Main.c
#include <stdio.h>
#include "ArrayList.h"
int main()
{
/*** ArrayList의 생성 및 초기화 ***/
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;
}
ArrayList.c
구현해보기
#include <stdio.h>
#include "ArrayList.h"
void ListInit(List* plist)
{
}
void LInsert(List* plist, LData data)
{
}
int LFirst(List* plist, LData* pdata)
{
return TRUE;
}
int LNext(List* plist, LData* pdata)
{
return TRUE;
}
LData LRemove(List* plist)
{
return rdata;
}
int LCount(List* plist)
{
return plist->numOfData;
}
구현
#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];
for (i = rpos; i < num - 1; i++)
plist->arr[i] = plist->arr[i + 1];
(plist->numOfData)--;
(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;
// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point* ppos, int xpos, int ypos);
// Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point* ppos);
// 두 Point 변수의 비교
int PointComp(Point* pos1, Point* pos2);
#endifpoint.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
해더파일이 조금 변경된다.
//new
#include "Point.h"
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
#define LIST_LEN 100
//old
//typedef int LData;
//new
typedef Point* 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);
#endifPointListMain.c
#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"
int PointListMain(void)
{
List list;
Point compPos;
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("현재 데이터의 수 : %d \n", LCount(&list));
if (LFirst(&list, &ppos))
{
ShowPointPos(ppos);
while (LNext(&list, &ppos))
ShowPointPos(ppos);
}
printf("\n");
// xpos가 2인 모든 데이터 삭제
compPos.xpos = 2;
compPos.ypos = 0;
if (LFirst(&list, &ppos))
{
if (PointComp(ppos, &compPos) == 1)
{
ppos = LRemove(&list);
free(ppos);
}
while (LNext(&list, &ppos))
{
if (PointComp(ppos, &compPos) == 1)
{
ppos = LRemove(&list);
free(ppos);
}
}
}
// 삭제 후 남은 데이터 전체 출력
printf("현재 데이터의 수: %d \n", LCount(&list));
if (LFirst(&list, &ppos))
{
ShowPointPos(ppos);
while (LNext(&list, &ppos))
ShowPointPos(ppos);
}
printf("\n");
return 0;
}반응형
