[자료구조] 원형배열 ADT

원형배열이란?

기존 배열은 입력 시, 첫번째 인덱스에 값을 입력 시 뒤에 있는 원소들을 뒤로 밀어내야한다.

이를 해결하기 위해 첫번째 인덱스 앞이 배열에 뒤쪽과 연결되어 있는 앞과 뒤의 입력 및 삭제가 유연한 배열을 만들기 위해 구상된 ADT이다.

 

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



void invalidRankException();
void fullListException();
void emptyListException();
int Size(int N, int f, int l);
void Get(char* arr, int N, int f, int l, int r);
void Set(char* arr, int N, int f, int l, int r, char data);
void Add(char* arr, int N, int *f, int *l, int r, char data);
void Remove(char* arr, int N, int* f, int* l, int r);
void Print(char* arr, int N, int f, int l);

int main() {
	int f = 0, l = 1,  N = 0;
	char* arr;

	int cnt,r;
	char tmp,e;
	printf("배열의 크기: ");
	scanf("%d", &N);
	arr = (char*)malloc(sizeof(char) * N);

	printf("명령어 횟수: ");
	scanf("%d", &cnt);
	getchar();
	while (cnt--) {
		scanf("%c", &tmp);
		getchar();
		if (tmp == 'A') {
			scanf("%d %c", &r, &e);
			getchar();
			Add(arr, N,&f,&l,r,e);
		}

		if (tmp == 'R') {
			scanf("%d", &r);
			getchar();
			Remove(arr, N, &f, &l, r);
		}

		if (tmp == 'P') {
			Print(arr, N, f, l);
		}
	}
	
	return 0;
}

void invalidRankException() {
	printf("Invalid Rank\n");
	return;
}

void fullListException() {
	printf("Full List\n");
	return;
}
void emptyListException() {
	printf("Empty List\n");
	return;
}

int Size(int N, int f, int l) {
	return (N - f + l + 1) % N;
}

void Get(char* arr, int N, int f, int l ,int r) {
	if (r < 0 || r >= Size(N,f,l)) {
		invalidRankException();
		return;
	}
	printf("%c", arr[(f + r) % N]);
}
void Set(char* arr, int N, int f,int l, int r, char data) {
	if (r < 0 || r >= Size(N,f,l)) {
		invalidRankException();
		return;
	}
	arr[(f + r) % N] = data;
	printf("Data Changed!\n");

}

void Add(char* arr, int N, int* f, int* l, int r, char data) {
	int n = Size(N,*f,*l);

	if (n == N - 1) {
		fullListException();
		return;
	}
	if (r < 0 || r > n) {
		invalidRankException();
		return;
	}

	// 추가하려는게 시작점에 가까울때
	if (r < N / 2) {
		
		for (int i = 0; i < r - 1; i++) {
			arr[(N + *f + i ) % N] = arr[(*f + i+1) % N];
		}
		arr[(N + *f + r - 1) % N] = data;
		*f = (N + *f - 1) % N;
		
	}

	// 추가하려는게 마지막에 가까울때
	else {
		
		for (int i = n - 1; i >= r; i--) {
			arr[(*f + i + 1) % N] = arr[(*f + i) % N];
		}
		arr[(*f + r) % N] = data;
		*l = (*l + 1) % N;
	}
	
}

void Remove(char* arr, int N, int* f, int* l, int r) {
	int n = Size(N, *f, *l);
	if (n == 0) {
		emptyListException();
		return;
	}
	if (r < 0 || r > n) {
		invalidRankException();
		return;
	}
	int data = arr[(*f + r) % N];
	
	
		
		for (int i = r - 1; i >= 0;i--) {
			arr[(*f + i + 1) % N] = arr[(*f + i) % N];
		}
		*f = (*f + 1) % N;
	

}

void Print(char* arr, int N,int f, int l) {
	if (f < l) {
		for (int i = f; i <= l; i++) {
			printf("%c ", arr[i]);
		}
	}
	else {
		for (int i = f+1; i < N; i++) {
			printf("%c ", arr[i]);
		}
		for (int i = 0; i < l; i++) {
			printf("%c ", arr[i]);
		}
	}
	
	printf("\n");
}