[자료구조] 영문자 리스트 ADT

영문자 리스트 ADT 구현

이중 연결 리스트 사용!

 

• add (r 위치에 e를 갖는 노드 추가하기):
  • 리스트의 r번째 위치에 값 e를 갖는 노드를 추가합니다.
  • 위치가 잘못되면 "invalid position"을 출력해야 합니다.
  • 이중 연결 리스트이기 때문에 노드가 추가될 때 이전 노드와 다음 노드의 연결을 적절히 갱신해야 합니다.
• delete (r 위치에 있는 노드 제거하기):
  • 리스트의 r번째 위치에 있는 노드를 제거합니다.
  • 삭제할 위치가 잘못되면 "invalid position"을 출력해야 합니다.
  • 삭제 시, 삭제된 노드의 이전과 다음 노드를 서로 연결해야 합니다.
• get (r 위치에 있는 노드의 값 출력):
  • 리스트의 r번째 위치에 있는 노드의 값을 출력합니다.
  • 위치가 잘못되면 "invalid position"을 출력해야 합니다.
• print (리스트 출력하기):
  • 리스트의 모든 노드를 차례대로 출력합니다.
  • 리스트가 비어 있으면 아무것도 출력하지 않습니다.

node, list 만들기

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
	struct node* next;
	struct node* prev;
	char elem;
}Node;

typedef struct list {
	struct node* H;
	struct node* T;
	int size;
}List;

list 초기화, 함수 선언

List* init()
{
	List* list = (List*)malloc(sizeof(List));
	list->H = (Node*)malloc(sizeof(Node));
	list->T = (Node*)malloc(sizeof(Node));
	list->H->prev = NULL;
	list->H->next = list->T;
	list->T->prev = list->H;
	list->T->next = NULL;
	list->size = 0;
	return list;
}

void add(List* list, int r, char e);
void delete(List* list, int r);
char get(List* list, int r);
void print(List* list);

main 함수

int main()
{
	int n;
	char a;
	int m;
	char s;
	List* list = init();
	scanf("%d", &n);
	getchar();
	for (int i = 0; i < n; i++)
	{
		scanf("%c", &a);
		getchar();
		if (a == 'A')
		{
			scanf("%d %c", &m, &s);
			getchar();
			add(list, m, s);
		}
		else if (a == 'D')
		{
			scanf("%d", &m);
			getchar();
			delete(list, m);
		}
		else if (a == 'G')
		{
			scanf("%d", &m);
			getchar();
			char b = get(list, m);
			if (b == '0')
				continue;
			printf("%c\n",b);
		}
		else if (a == 'P')
		{
			print(list);
		}
	}
	return 0;
}

add 함수

void add(List* list, int r, char e) {
	//만드려는 위치가 list->size+1보다 크다면 예시) 4번을 만드려고 했는데 size가 2이면 못지움 3이면 Trailer로 가서 만들 수 있음

	if (r > list->size + 1 || r < 1) {
		printf("invalid position\n");
		return;
	}

	Node* current = list->H;
	for (int i = 0; i < r; i++)
	{
		//현재 노드의 다음이 없으면 invalid position 출력
		if (current->next == NULL)
		{
			printf("invalid position\n");
			return;
		}
		current = current->next;
	}
	//생성 하는 부분
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->elem = e;

	newnode->prev = current->prev;
	newnode->next = current;

	current->prev->next = newnode;
	current->prev = newnode;
	list->size++;
}

delete 함수

void delete(List* list, int r)
{
	//지울려는 위치가 list->size보다 크다면 예시) 4번을 지우려고 했는데 size가 3이면 못지움
	if (r > list->size)
	{
		printf("invalid position\n");
		return;
	}
	Node* current = list->H;
	for (int i = 0; i < r; i++)
	{
		//현재 노드의 다음이 없으면 invalid position 출력
		if (current->next == NULL)
		{
			printf("invalid position\n");
			return;
		}
		current = current->next;
	}

	current->prev->next = current->next;
	current->next->prev = current->prev;
	free(current);
	list->size--;
}

get 함수

char get(List* list, int r)
{
	if (r > list->size)
	{
		printf("invalid position\n");
		return '0';
	}
	Node* current = list->H; 
	for (int i = 0; i < r; i++)
	{
		if (current->next == NULL)
		{
			printf("invalid position\n");
			return '0';
		}
		current = current->next;
	}
	return(current->elem);
}

print 함수

void print(List* list)
{
	Node* current = list->H->next;  // Head 다음 노드부터 시작
	for (int i = 0; i < list->size; i++)
	{
		printf("%c", current->elem);
		current = current->next;
	}
	printf("\n");
}