영문자 리스트 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");
}
'학교 공부 > 자료구조' 카테고리의 다른 글
[자료구조] 연결 이진트리 구현 (0) | 2024.09.06 |
---|---|
[자료구조] 리스트 ADT (1) | 2024.09.04 |
[자료구조] 추상자료형 ADT (0) | 2024.09.04 |