ㅇ이중연결리스트: 노드 간의 링크가 두 개
활용) 영문자 리스트 ADT
순위는 1부터 시작한다고 가정하며 순위 정보가 유효하지 않으면 화면에 에러 메시지 "invalid position"을 출력하고, 해당 연산을 무시한다
두 가지 방법이 있다
첫 번째 방법: 전역변수 사용 x
- 헤더노드, 트레일러노드, 리스트의 크기에 대한 전역변수 사용 x
(전체코드)
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE {
char e; // element
struct NODE* prev;
struct NODE* next;
} NODE;
void add(NODE* head, int r, char e);
void delete(NODE* head, int r);
void get(NODE* head, int r);
void print(NODE* head);
int main() {
int N;
char cmd;
int r; // rank
char e; // element
NODE* head = (NODE*)malloc(1 * sizeof(NODE));
NODE* tail = (NODE*)malloc(1 * sizeof(NODE));
head->prev = NULL;
head->next = tail;
tail->prev = head;
tail->next = NULL;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf(" %c", &cmd);
if (cmd == 'A') {
scanf(" %d %c", &r, &e);
add(head, r, e);
}
else if (cmd == 'D') {
scanf(" %d", &r);
delete(head, r);
}
else if (cmd == 'G') {
scanf(" %d", &r);
get(head, r);
}
else if (cmd == 'P') {
print(head);
}
}
while (head != NULL) {
NODE* temp = head;
head = head->next;
free(temp);
}
return 0;
}
void add(NODE* head, int r, char e) {
if (r == 0) {
printf("invalid position\n");
return;
}
for (int i = 0; i < r; i++) {
head = head->next;
if (head == NULL) {
printf("invalid position\n");
return;
}
}
NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
newNode->e = e;
newNode->next = NULL;
newNode->prev = NULL;
// 포인터 교체 작업1: 왼쪽
newNode->prev = head->prev;
(head->prev)->next = newNode;
// 포인터 교체 작업2: 오른쪽
newNode->next = head;
head->prev = newNode;
}
void delete(NODE* head, int r) {
if (r == 0) {
printf("invalid position\n");
return;
}
for (int i = 0; i < r; i++) {
head = head->next;
if (head->next == NULL) {
printf("invalid position\n");
return;
}
}
(head->prev)->next = head->next;
(head->next)->prev = head->prev;
free(head);
}
void get(NODE* head, int r) {
if (r == 0) {
printf("invalid position\n");
return;
}
for (int i = 0; i < r; i++) {
head = head->next;
if (head->next == NULL) {
printf("invalid position\n");
return;
}
}
printf("%c\n", head->e);
}
void print(NODE* head) {
head = head->next;
while (head->next != NULL) {
printf("%c", head->e);
head = head->next;
}
printf("\n");
}
/*
5
A 1 S
A 2 t
A 3 r
A 3 a
P
9
A 1 D
A 2 a
A 3 y
D 1
P
G 3
A 1 S
P
G 3
*/
두 번째 방법: 전역변수 사용 o
- 헤더노드, 트레일러노드, 리스트의 크기에 대한 전역변수 사용 o
(전체코드)
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE {
char e;
struct NODE* prev;
struct NODE* next;
} NODE;
NODE* g_pHeader = NULL; // 리스트의 헤더 노드를 고정으로 가리키는 전역 노드 포인터
NODE* g_pTrailer = NULL; // 리스트의 트레일러 노드를 고정으로 가리키는 전역 노드 포인터
int g_n = 0; // 리스트의 크기를 저장하는 전역 변수
void add(int r, int e);
void delete(int r);
NODE* get(int r);
void print();
int main() {
int N;
char cmd;
int r;
char e;
scanf("%d", &N);
// 리스트 및 헤더 노드와 트레일러 노드 초기화
g_pHeader = (NODE*)malloc(1 * sizeof(NODE));
g_pTrailer = (NODE*)malloc(1 * sizeof(NODE));
// 헤더와 트레일러 노드를 연결
g_pHeader->prev = NULL;
g_pHeader->next = g_pTrailer;
g_pTrailer->prev = g_pHeader;
g_pTrailer->next = NULL;
for (int i = 0; i < N; i++) {
scanf(" %c", &cmd);
if (cmd == 'A') {
scanf(" %d %c", &r, &e);
add(r, e);
}
else if (cmd == 'D') {
scanf(" %d", &r);
delete(r); // 해당 위치의 노드를 삭제하고 반환
}
else if (cmd == 'G') {
scanf(" %d", &r);
NODE* result = get(r); // 해당 위치의 노드를 반환
if (result != NULL) {
printf("%c\n", result->e); // 반환된 노드의 문자 데이터 출력
}
}
else if (cmd == 'P') {
print();
}
}
while (g_pHeader != NULL) {
NODE* temp = g_pHeader;
g_pHeader = g_pHeader->next;
free(temp);
}
g_pHeader = NULL;
return 0;
}
void add(int r, int e) { // 노드를 특정 위치에 추가
if (r < 1 || r > g_n + 1) { // 예외처리 - 유효하지 않은 위치
printf("invalid position\n");
return;
}
// 새로운 노드를 생성하고 할당 후에 문자 데이터를 저장
NODE* newNode = (NODE*)malloc(sizeof(NODE));
newNode->e = e;
NODE* temp = g_pHeader;
for (int i = 0; i < r; i++) { // r번째 위치까지 이동
temp = temp->next;
}
// 교체 작업 1: 왼쪽
newNode->prev = temp->prev;
(temp->prev)->next = newNode;
// 교체 작업 2: 오른쪽
newNode->next = temp;
temp->prev = newNode;
g_n++; // 리스트 크기++
}
void delete(int r) { // 특정 위치의 노드를 삭제하고 반환
if (r < 1 || r > g_n) { // 예외처리 - 유효하지 않은 위치
printf("invalid position\n");
return NULL;
}
NODE* targetNode = g_pHeader;
for (int i = 0; i < r; i++) { // r번째 노드까지 이동
targetNode = targetNode->next;
}
// 삭제할 노드의 이전 노드와 다음 노드를 연결
(targetNode->prev)->next = targetNode->next;
(targetNode->next)->prev = targetNode->prev;
/*
NODE* prevNode = targetNode->prev;
prevNode->next = targetNode->next;
targetNode->next->prev = prevNode;
*/
g_n--; // 리스트 크기--
free(targetNode); // 삭제된 노드 할당 해제
return;
}
NODE* get(int r) { // 특정 위치의 노드를 반환
if (r < 1 || r > g_n) { // 예외처리 - 유효하지 않은 위치
printf("invalid position\n");
return NULL;
}
NODE* targetNode = g_pHeader;
for (int i = 0; i < r; i++) {
targetNode = targetNode->next;
}
return targetNode; // 해당 위치의 노드를 반환
}
void print() { // 리스트의 모든 노드를 출력
NODE* cur = g_pHeader->next;
while (cur->next != NULL) { // 트레일러까지 반복
printf("%c", cur->e);
cur = cur->next;
}
printf("\n");
}
/*
5
A 1 S
A 2 t
A 3 r
A 3 a
P
9
A 1 D
A 2 a
A 3 y
D 1
P
G 3
A 1 S
P
G 3
*/
참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)
'Computer Science > 자료구조' 카테고리의 다른 글
[자료구조] ep4) 집합(Set) (0) | 2024.05.03 |
---|---|
[자료구조] ep3-3) 다중연결리스트(Multi Linked List) (0) | 2024.05.03 |
[자료구조] ep3-1) 단일연결리스트(Single Linked List) (1) | 2024.05.03 |
[자료구조] ep2+) 하노이 탑 구현 (1) | 2024.04.07 |
[자료구조] ep2) 재귀(Recursion) (0) | 2024.04.07 |