배열 리스트

 자료구조에는 여러 형식으로 데이터를 저장한다. 그리고 데이터를 저장하는 방식에 따라 기본형식, 선형형식, 비선형형식으로 나뉜다. 

• 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
• 비선형 구조 :  데이터를 1:n 관계로 나열 시킨 구조로, Heap, Tree가 해당 구조에 해당한다.

 이중에서, 제일 많이 사용하는 자료구조인 "List"는 일직선 상으로 차례대로 데이터를 저장하는 자료구조이다. 이때 차례대로란 데이터를 기준에 따라 저장하는 것이 아닌, 노드의 순서에 따라 1개씩 저장하는 것을 의미한다.

 

 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 해당 노드에 어떠한 데이터를 저장할지 결정한다. 

typedef struct ArrayListNodeType {
	int data;
} ArrayListNode;

 위의 구조는 노드의 타입을 나타내는 구조로, 모든 사용자가 알 수 있도록 구조체의 이름을 공용화한 형태이다.

 

배열 리스트

 배열 리스트란 노드가 모여 직선모양으로 줄지어 있는 자료구조로, 배열로 데이터를 연결하는 형태를 배열리스트라고 한다. 

 배열리스트는 인덱스를 통해서 검색을 하기에, 데이터의 검색이 빠르지만 배열의 크기가 선언하면 변경이 불가능한 정적배열이다.

typedef struct ArrayListType {
	int maxCount;		//배열의 최대 노드개수
	int currentCount;	//현재 사용중인 노드 개수
	ArrayListNode* pData; 	//데이터 저장을 위한 배열의 위치
}ArrayList;

 위의 구조는 배열에 대한 정보를 구조체로 만든 것으로, 구조체를 통해 배열의 정보를 확인할 수 있으며, 데이터 정보 삽입, 삭제에서 현재 사용중인 노드와 배열의 최대 노드 개수를 사용하기 위해 만드는 구조체다.

 

배열리스트 알고리즘

 배열리스트 데이터를 저장할 수 있는 노드가 줄지어있는 형태이기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 기능의 순서도를 구성하고, 소스코드로 구현해야 한다.

 

•  배열 생성함수 구현
  • 기능 : 포인터를 저장할 배열리스트를 생성하며, 해당 배열의 정보(최대 요소 수, 사용중인 요소 수) 저장
  • 함수의 자료형: ArrayList의 포인터(ArrayList*)
  • 매개변수: 노드의 최대갯수(count)
  • 필드 사용 변수
    1. count ←  노드의 최대 갯수
    2. pList ←  배열 정보 변수

알고리즘	순서도
배열 정보 변수를 동적 메모리로 생성 후, 변수의 주소를 포인터 변수에 저장 매개변수의 값을 배열 정보의 "maxCount"에 저장 배열 정보 중 "currentCount"를 초기화 동적 메모리로 사용할 배열 생성 후, 배열의 주소를 배열정보의 "pData"에 저장 배열의 내용을 0으로 초기화 리턴 값을 배열 정보를 가진 변수의 주소를 가진 포인터 변수로 지정

ArrayList* createList(int count) {
	ArrayList* pList = (ArrayList*)malloc(sizeof(ArrayList));

	pList->maxCount = count;
	pList->currentCount = 0;
	pList->pData = (ArrayListNode*)malloc(sizeof(ArrayListNode) * count);
	memset(pList->pData, 0, sizeof(ArrayListNode) * count);

	return pList;
}

 

• 데이터 추가 함수
  
  • 기능 
    • 데이터가 없는 노드 자리 : 해당 노드자리에 데이터 삽입
    • 데이터가 있는 노드 자리 : 기존 데이터는 뒤로 이동 후, 해당 노드자리에 데이터 삽입
  • 함수의 자료형 : 정수형
  • 매개변수: 데이터를 추가할 배열(pList), 배열 위치(position),
  • 필드 사용할 변수
    1. position  ←  자료를 추가하려는 위치 값
    2. i ←  마지막 자료의 위치값

데이터 추가 함수 기능

알고리즘	순서도
i>=position 위치 i에 있는 자료를 i+1위치에 복사 i = i-1 3)의 조건이 거짓이 될 때 까지 3)~5)반복 position위치에 새로운 데이터 추가

int addListData(ArrayList* pList, int position, int data) { //데이터를 추가할 배열, 배열 위치, 데이터값
	int i = 0;
	for (i = pList->currentCount - 1; i >= position; i--) {
		pList->pData[i + 1] = pList->pData[i];
	}

	pList->pData[position].data = data;
	pList->currentCount++;
	return 0;
}

 

• 데이터 삭제 함수
  • 기능 : 삭제할 노드를 기준으로 이후 노드의 데이터를 앞으로 이동
  • 매개변수 : 데이터 삭제할 배열(pList), 배열 위치(position)
  • 필드 사용 변수 
    1. i ←  position

알고리즘	순서도
매개변수 : 데이터 삭제할 배열(pList), 배열 위치(position) 필드 사용 변수 : i ←  position i < pList.currentCount -1  위치 i+1에 있는 자료를 i에 복사 i = i+1

int removeListData(ArrayList* pList, int position) {//데이터 삭제할 배열, 배열 위치
	int i = 0;
	for (i = position; i < pList->currentCount - 1; i++) {
		pList->pData[i] = pList->pData[i + 1];
	}
	pList->currentCount--;
	return 0;
}

 

• 데이터 출력 함수
  • 기능 : 노드에 저장되어 있는 데이터 출력
  • 매개변수 : 데이터 출력할 배열(pList), 배열 위치(position)

알고리즘	해당 함수에 배열의 위치에 있는 데이터 값을 return

int getListData(ArrayList * pList, int position) {//데이터 호출할 배열, 배열 위치
	return pList->pData[position].data;
}

 

• 배열 삭제 함수
  • 기능 : 사용하는 배열 제거
  • 매개변수 : 삭제할 배열(pList)

알고리즘	사용한 동적 메모리 배열과 변수를 free함수로 삭제

void deleteList(ArrayList * pList) {//삭제할 배열
	free(pList->pData);
	free(pList);
}

 

 배열 생성, 데이터 삽입, 데이터 삭제, 데이터 출력, 배열 삭제하는 함수를 구현했으며, 해당 함수들을 통해 소스코드를 생성하면 다음과 같다.

#include<stdio.h>
#include<stdlib.h>

//노드 정보
typedef struct ArrayListNodeType {
	int data;
} ArrayListNode;

//배열 정보
typedef struct ArrayListType {
	int maxCount;		//배열의 노드개수
	int currentCount;		//현재 사용중인 노드 개수
	ArrayListNode* pData; 	//데이터 저장을 위한 배열의 위치
}ArrayList;

//사용할 함수 선언
ArrayList* createList(int);
int addListData(ArrayList*,int,int);
int removeListData(ArrayList*, int);
int getListData(ArrayList*, int);
void deleteList(ArrayList*);

//main함수
int main(void){
	ArrayList* pList = createList(5);
	
	addListData(pList, 0, 30);
	addListData(pList, 1, 20);
	addListData(pList, 1, 10);
	addListData(pList, 3, 40);

	for (int i = 0; i < pList->maxCount; i++) {
		printf("%d\t", getListData(pList, i));
	}
	deleteList(pList);

	return 0;
}

//배열 생성 함수
ArrayList* createList(int count) {
	ArrayList* pList = (ArrayList*)malloc(sizeof(ArrayList));

	pList->maxCount = count;
	pList->currentCount = 0;
	pList->pData = (ArrayListNode*)malloc(sizeof(ArrayListNode) * count);
	memset(pList->pData, 0, sizeof(ArrayListNode) * count);

	return pList;
}

//데이터 추가 함수
int addListData(ArrayList* pList, int position, int data) { //데이터를 추가할 배열, 배열 위치, 데이터값
	int i = 0;
	for (i = pList->currentCount - 1; i >= position; i--) {
		pList->pData[i + 1] = pList->pData[i];
	}

	pList->pData[position].data = data;
	pList->currentCount++;
	return 0;
}

//데이터 삭제 함수
int removeListData(ArrayList* pList, int position) {//데이터 삭제할 배열, 배열 위치
	int i = 0;
	for (i = position; i < pList->currentCount - 1; i++) {
		pList->pData[i] = pList->pData[i + 1];
	}
	pList->currentCount--;
	return 0;
}

//배열의 데이터 호출
int getListData(ArrayList * pList, int position) {//데이터 호출할 배열, 배열 위치
	return pList->pData[position].data;
}

//배열 삭제
void deleteList(ArrayList * pList) {//삭제할 배열
	free(pList->pData);
	free(pList);
}