배열 리스트

 

리스트의 의미는 다음과 같다

 

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

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

 

배열리스트를 구현해보자

 

책(윤성우의 열혈 자료구조)에서 제공하는 배열 리스트의 자료구조 ADT는 다음과 같다.

 

Operations:

 

void ListInit(List * plist);

 - 초기화할 리스트의 주소 값을 인자로 전달한다.

 - 리스트 생성 후 제일먼저 호출되어야하는 함수이다.

 

void LInsert(List * plist , LData data);

 - 첫 번째 데이터가 pdata 가 가리키는 메모리에 저장된다.

 - 데이터의 참조를 위한 초기화가 진행된다.

 - 참조 성공시 TRUE(1), 실패 시 FALSE(0) 반환

 

void LNext(List * plist, LData * pdata);

 - 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.

 - 순차적인 참조를 위해서 반복 호출이 가능하다.

 - 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야한다.

 - 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

 

LData LRemove(List * plist);

 - LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.

 - 삭제된 데이터는 반환된다.

 - 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

 

 

 

이제 main 함수와 list.h를 보고 list.c를 구현해보자

 

Array_list.h

/*
 * Array_list.h
 *
 *  Created on: 2020. 10. 9.
 *      Author: jt.kim
 */

#ifndef ARRAY_LIST_H_
#define ARRAY_LIST_H_


#define TRUE	1
#define FALSE	0

#define LIST_LEN	100
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 /* ARRAY_LIST_H_ */

 

main.c

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

int main(void)
{
	List list;
	int data;
	ListInit(&list);

	LInsert(&list, 11);
	LInsert(&list, 11);
	LInsert(&list, 22);
	LInsert(&list, 22);
	LInsert(&list, 33);

	printf("현재 데이터의 수 : %d \n", LCount(&list));
	setvbuf(stdout, NULL, _IONBF, 0);

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		setvbuf(stdout, NULL, _IONBF, 0);

		while (LNext(&list, &data))
		{
			printf("%d ", data);
			setvbuf(stdout, NULL, _IONBF, 0);
		}
	}
	printf("\n\n");


	if (LFirst(&list, &data))
	{
		if (data == 22)
		{
			LRemove(&list);
		}

		while (LNext(&list, &data))
		{
			if (data == 22)
			{
				LRemove(&list);
				printf("데이터 제거 : %d\n", data);
			}

		}
	}
	printf("\n\n");
	printf("현재 데이터의 수 : %d \n", LCount(&list));


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

		while (LNext(&list, &data))
		{
			printf("%d ", data);

		}
	}
	printf("\n\n");

	return 0;
}

 

ListInit 함수는 구초체의 멤버 변수를 초기화 한다.

 

구현
void ListInit(List *plist)
{
	for (int i = 0; i < LIST_LEN; i++)
	{
		plist->arr[i] = 0;
	}

	plist->numOfData = 0;
	plist->curPosition = 0;
}

다운 받은 소스
void ListInit(List * plist)
{
	(plist->numOfData) = 0;
	(plist->curPosition) = -1;
}

 

다른 점은 curposition을 -1로 하느냐 0으로 하느냐 인데 취향차이 인거 같다.

 

LFirst 함수는 리스트의 첫번째 데이터를 나타내고 메모리에 저장한다.

 

구현
int LFirst(List *plist, LData *pdata)
{
	plist->curPosition = 0;
	*pdata = plist->arr[plist->curPosition];

	if (*pdata != 0)
	{
		return 1;
	}

	return 0;
}


다운받은 소스
int LFirst(List * plist, LData * pdata)
{
	if(plist->numOfData == 0)
		return FALSE;

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

작성하면서 보니 *pdata가 0이면 return 을 ERROR(0) 처리 함으로 써 저장된 값이 0이면 문제가 생긴다.

향 후 초기화를 0이 아닌 NULL 값으로 초기화 하고 *pdata도 NULL 값이면 return 0으로 하도록 수정이 필요하다.

 

LInsert 함수는 배열에 데이터를 저장한다.

 

구현
void LInsert(List *plist, LData data)
{
	plist->arr[plist->numOfData] = data;
	plist->numOfData++;
}

다운받은 소스
void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("에러메시지.");
		return;
	}

	plist->arr[plist->numOfData] = data;
	(plist->numOfData)++;
}

다운 받은 소스 코드에서는 numofData가 커지면 return 처리되어 더 저장되지 못하게 한다.

 

LNext 함수는 참조된 데이터의 다음 데이터를 나타낸다.

구현
int LNext(List *plist, LData *pdata)
{
	plist->curPosition++;
	*pdata = plist->arr[plist->curPosition];

	if (*pdata != 0)
	{
		return 1;
	}

	return 0;
}


다운받은 소스
int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1)
		return FALSE;

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

에러처리에 차리가 있다 구현 할 때  데이터가 0이면 ERROR로 포커스 잡았지만 책에서는 INDEX를 비교하여

에러처리한다.

 

LRemove 함수는 참조하고 있는 데이터를 삭제하고 삭제된 데이터를 반환한다.

구현
LData LRemove(List *plist)
{
	LData curr_data;
	int curr_idx, next_idx, tmp_idx;

	curr_data = plist->arr[plist->curPosition];
	tmp_idx = plist->curPosition;

	while (plist->arr[tmp_idx])
	{
		curr_idx = tmp_idx++;
		next_idx = tmp_idx;

		plist->arr[curr_idx] = plist->arr[next_idx];

	}
	plist->curPosition--;
	plist->numOfData--;

	return curr_data;
}


다운받은 소스
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;
}

구현하는데 시간을 제일 많이 잡아 먹었다.

삭제 하고  Main 마지막 구문 데이터 출력에서 33이 출력되지 않고 또는 22하나는 지워지지 않고 등등 문제가 있었다.

 

Lcount는 numofData를 반환하면 되므로 따로 적지 않았다.

 

실행 화면