Roopretelcham

리스트 자료구조는 크게 두가지로 나뉨

순차 리스트 : 배열을 기반으로 구현된 리스트

연결 리스트 : 메모리 동적할당을 기반으로 구현된 리스트

리스트 자료 구조의 특성

: 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.

아래 예제 파일을 열어 ArrayList.c는 가급적 열지 않고 직접 구현해보도록

 ArrayList.7z

* 자료 구조의 내부 구현을 모르고도 해당 자료구조의 활용이

가능하도록 ADT를 정의하는 것이 맞다.

리스트의 데이터 참조 과정

순서대로 참조하려면 먼저 LFirst를 호출해 첫번째 데이터를 얻는다.

두 번째 이후의 데이터는 LNext를 호출해서 얻는다.

LFirst 함수와 LNext 함수는 더 이상 참조할 데이터가 없으면 

FALSE를 반환한다.

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

int main(void)
{
	/*** ArrayList의 생성 및 초기화 ***/
	List list;
	int data;
	int i;
	int sum = 0;

	ListInit(&list);

	/*** 정수 1부터 9까지 데이터 저장 ***/
	for (i = 1; i < 10; i++)
		LInsert(&list, i);

	/*** 저장된 데이터의 합 출력 ***/	
	if (LFirst(&list, &data))
	{
		sum = sum + data;				

		while (LNext(&list, &data))
			sum = sum + data;		
	}
	
	/*** 저장된 데이터의 전체 출력 ***/
	printf("현재 데이터 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		while (LNext(&list, &data))
			printf("%d ", data);
	}
	printf("\n합 : %d \n\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);
		}
	}

	/*** 저장된 데이터의 전체 출력 ***/
	printf("현재 데이터 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		while (LNext(&list, &data))
			printf("%d ", data);
	}
	printf("\n");

	return 0;
}

Output :

현재 데이터 수 : 9

1 2 3 4 5 6 7 8 9

합 : 45

현재 데이터 수 : 3

1 5 7

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

typedef ArrayList List; // List는 배열 기반 리스트

typedef LinkedList List; // List는 연결 기반 리스트

List에 다른 이름을 부여하는 것만으로 사용하는 리스트의 종류를 바꿀 수 있다.

typedef int LData; 도 마찬가지로 다른 이름을 부여해 활용할 수 있다.

ArrayList.c    // 가급적 스스로 구현을 연습해보는 것이 좋다.

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

void ListInit(List * plist)	// 리스트 초기화
{
	(plist->numOfData) = 0;
	(plist->curPosition) = 0;	// -1에서 0으로 참조 위치 초기화, 첫번째 데이터 참조
}

void LInsert(List * plist, LData data)
{
	if (plist->numOfData >= LIST_LEN)	// 데이터 개수가 배열 총 길이보다 많거나 같으면 저장불가
	{
		puts("데이터 저장불가");
		return;
	}

	plist->arr[plist->numOfData] = data; // 데이터 저장, numOfData를 index값으로 활용
	(plist->numOfData)++;
}

int LFirst(List * plist, LData * pdata)	// 첫번째 데이터가 pdata가 가리키는 메모리에 저장
{
	if (plist->numOfData == 0) // 저장된 데이터가 없으면 
		return FALSE;// FALSE 반환

	(plist->curPosition) = 0; // 현재 참조위치가 초기화
	*pdata = plist->arr[0];	// plist->arr[plist->curPosition]와 같은 의미지만 강조를 위한 것
	return TRUE;
}

int LNext(List * plist, LData * pdata)
{
	if (plist->curPosition >= (plist->numOfData) - 1)	
		// 더 이상 참조할 데이터가 없을 때(현재 참조위치와 데이터 수 비교)		
		return FALSE; // FALSE 반환

	(plist->curPosition)++;
	*pdata = plist->arr[plist->curPosition];
	return TRUE;
}

LData LRemove(List * plist)
{
	int rmPos = plist->curPosition;	// 현재 위치가 삭제할 위치가 된다.
	LData rmData = plist->arr[rmPos];	// 삭제할 인덱스의 데이터를 rmData에 저장

	// 해당 인덱스 삭제후, 한칸씩 왼쪽 이동해 그 빈칸을 메움
	int i;
	for (i = rmPos; i < (plist->numOfData) - 1; i++)
		plist->arr[i] = plist->arr[i + 1];	// 오른쪽의 인덱스가 왼쪽으로 이동

	(plist->numOfData)--;
	(plist->curPosition)--;
	// curPosition이 참조가 이뤄지지않은, 이동한 데이터를 가리키므로 참조위치를 왼쪽으로 옮겨야 함
	return rmData;	// 삭제된 데이터는 반환해야 한다. (이것은 메모리의 공간 해제를 위한 것)
}

int LCount(List * plist)	// 리스트에 저장된 데이터 수(numOfData) 반환
{
	return plist->numOfData;
}

배열 기반 리스트의 장 단점

장점

인덱스 값을 기준으로 쉽게 참조가 가능하다.

단점

배열 길이가 초기에 결정되며 변경 불가능하다.

삭제 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

프로그램이란 데이터를 표현하고, 표현된 데이터를 처리하는 것.

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  // 자료구조화, 데이터의 표현에 저장의 의미가 포함(int형 변수 선언이나, 배열 선언 등)

for(idx=0; idx<10; idx++)  // 배열에 저장된 값의 합을 구하기 위한 알고리즘 측면의 코드

sum += arr[idx];

: 자료구조에 따라 이를 위한 알고리즘은 달라지며, 따라서 알고리즘은 자료구조에 의존적이다.

먼저 자료구조를 결정하고, 이에 대한 효율적 알고리즘을 짜는 것이다.

알고리즘의 성능분석 방법

처리해야 할 데이터의 수 n에 대한, 연산횟수의 함수 T(n)을 가지고 식을 구성

데이터를 처리할 양이 많을 때, 로그식과 같은 알고리즘이 가장 이상적일 것이다.

시간복잡도 : 어떤 알고리즘이 어떠한 상황에서 더 빠르고 느린가

공간복잡도 : 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰거나 많이 쓰는가

알고리즘을 평가할 때는 속도에 대한 것을 우선으로 둔다. 이는 c언어의 입문 과정에서도 배운 내용이다.(공간 최적화와 속도 최적화) 

알고리즘 A와 B를 비교하면 데이터의 수가 적을 땐 B가 더 빠르지만, 일정 데이터 수 이후에는 A가 빠름을 알 수 있다.

하지만 데이터의 수가 적을 때의 시간 차는 미미하기 때문에 보통은 A를 좋은 알고리즘이라 한다.

다만, 구현이 쉽고 데이터의 수가 적을 때는 알고리즘 B를 쓰는 경우도 있다. 선택은 프로그래머의 몫이다.

시간 복잡도의 평가

: 중심이 되는 특정 연산의 횟수를 먼저 구하고, 

데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

순차 탐색 예제

#include <stdio.h>

int LSearch(int ar[], int len, int target) // 순차탐색 함수(배열, 길이, 타겟)

{

int i;

for(i=0; i<len; i++)

{

if(ar[i]==target)

return i;    // 찾은 대상의 인덱스 값 반환

}

return -1;    // 찾지 못했음을 의미하는 값 반환

}

int main(void)

{

int arr[]={3, 5, 2, 4, 9};

int idx;

idx=LSearch(arr, sizeof(arr)/sizeof(int), 4);

if(idx==-1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d \n", idx);

idx=LSearch(arr, sizeof(arr)/sizeof(int), 7);

if(idx==-1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d \n", idx);

return 0;

}

결과: 

타겟 저장 인덱스: 3

탐색 실패

순차 탐색 알고리즘에서 최악의 경우, 시간 복잡도    

: 최악의 경우 마지막 인덱스에서 찾거나 타켓 탐색에 실패할 수 있다.

여기서 중심이 되는 특정 연산은 ==이고 <와 ++은 이에 의존적이다.

따라서 최악의 경우 t(n)=n 이 된다.

평균적인 경우를 구하는 것은 예상하거나 증명하는 것이 쉽지않고 일정한 상황이 아니기 때문에, 

"일반적으론" 최악의 경우를 구하는 것이다.

이진탐색 알고리즘 구현

길이가 9인 배열 정의. 

배열 인덱스의 시작과 끝은 각각 0과 8이다. (arr[0]~arr[8])

이를 오름차순을 기준으로 정렬한다.

{1, 2, 3, 7, 9, 12 , 21, 23, 27}

탐색 대상은 3.

0과 8을 합하여 그 결과를 2로 나눈다. 

결과 인덱스 4, 즉 가운데 인덱스를 기준으로 우리가 찾고자하는 값이 왼쪽 또는 오른쪽 배열에 있는지 확인하다. 

오름차순이기 때문에 어느 매개를 탐색대상으로 해야하는지 분명해진다.

{1, 2, 3, 7, 9, ...}

인덱스4의 숫자는 9이고, 우리가 찾는 대상보다 큰 값이기 때문에 탐색 대상은 왼쪽의 0~3 인덱스로 제한된다.

0과 3을 합하여 그 결과를 2로 나눈다. 1이 나오고 나머지는 버려짐

인덱스 1에 숫자 3이 있는지 확인한다. 숫자 2가 확인

 arr[1] < 3이므로 아래와 같이 인덱스 2,3으로 탐색이 제한된다.

{1, 2, 3, 7, 9, ...}

2와 3을 더하고 다시 2로 나눈다. 몫이 2가 나온다.

인덱스2의 숫자가 3인지 확인.

탐색 끝.

이진 탐색 알고리즘은 매 과정마다 탐색 대상을 절반으로 줄여나간다. 

기준을 가지고 정렬해야 하는 대신에  순차 탐색에 비해 좋은 성능을 보이며, 이는 이 알고리즘의 단점이자 장점이다.