728x90
반응형
단일 연결리스트의 ADT
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef char element;
typedef struct Listnode {
int data;
struct Listnode* next;
}Listnode;
typedef struct ListType {
struct Listnode* Head;
int size;
}ListType;
void init(ListType* DList) {
DList->Head = NULL;
DList->size = 0;
}
void insertFirst(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
//새로운 노드 동적할당
Listnode* p = DList->Head;
/*노드 추가 시 기본 알고리즘*/
new->data = e; // 새로운 노드에 값 저장
new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결
DList->Head = new;
DList->size++;
}
void insertLast(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;
while(p->next != NULL) {
if (p->next == NULL) {
break;
}
p = p->next;
}
new->data = e;
new->next = NULL;
if (p == NULL) DList->Head = new;
else p->next = new;
DList->size++;
}
void insert(ListType* DList, element e, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return ;
}
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;//임의의 노드 생성
if (rank == 1) {insertFirst(DList, e);}
else if (rank == DList->size + 1) {insertLast(DList, e);}//(맨 마지막 + 1)위치 추가
else {
for (int i = 1; i < rank-1; i++) {p = p->next;}//원하는 위치까지 이동
// printf("inserting...\n");
new->data = e;
new->next = p->next;
p->next = new;
DList->size++;
}
}
element deleteFirst(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
element ouput = p->data;
DList->Head = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}
element deleteLast(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
Listnode* prev = NULL;
while(p->next != NULL) {
prev = p;
p = p->next;
}element ouput = p->data;
if (prev == NULL) DList->Head = NULL; // 리스트에 노드가 하나만 있을 때
else prev->next = NULL; // 마지막 노드를 삭제하기 위해 이전 노드의 다음 노드를 NULL로 설정
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}
element delete(ListType* DList, int rank) {
element ouput ;
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1;
}
if (rank == 1) deleteFirst(DList);
else if (rank == DList->size) deleteLast(DList);
else {
Listnode* p = DList->Head;
Listnode* prev = NULL;
for (int i = 1; i < rank; i++) {
prev = p;
p = p->next;
}ouput = p->data;
prev->next = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
}
return ouput;
}
element getNode(ListType* DList, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1; // 유효하지 않은 순위일 경우 -1 반환
}
Listnode* p = DList->Head;
for (int i = 1; i < rank; i++) {
p = p->next;
}
return p->data;
}
void print(ListType* DList) {
for (Listnode* p = DList->Head; p != NULL; p = p->next) {
printf("[%c] -> ", p->data);
}printf("\b\b\b\b \n");
}
int main(){
//순환문이용
int n,m,tmp;
ListType DList_A,DList_B;
init(&DList_A);init(&DList_B);
// scanf("%d",&n);
// n = 5;
// srand(time(NULL));
// for(int i=0;i<n;i++){
// // scanf("%d",&tmp);
// tmp = rand() % 99 + 1;
// insert(&DList_A,i+1,tmp);
// }
printf("--------------insertFirst--------------\n");
insertFirst(&DList_A,'A');print(&DList_A);//printf("\n");
insertFirst(&DList_A,'B');print(&DList_A);//printf("\n");
insertFirst(&DList_A,'C');print(&DList_A);//printf("\n");
printf("---------------insertLast---------------\n");
insertLast(&DList_A,'D');print(&DList_A);//printf("\n");
printf("---------------insert [%d]---------------\n",2);
insert(&DList_A,'E',2);print(&DList_A);
printf("---------------insert [%d]---------------\n",4);
insert(&DList_A,'F',4);print(&DList_A);
printf("-------------deleteFirst-----------------\n");
deleteFirst(&DList_A);print(&DList_A);
printf("--------------deleteLast------------------\n");
deleteLast(&DList_A);print(&DList_A);
printf("---------------getNode--------------------\n");
printf("getNode[%d] = [%c]\n",1,getNode(&DList_A,1));
printf("getNode[%d] = [%c]\n",2,getNode(&DList_A,2));
printf("getNode[%d] = [%c]\n",3,getNode(&DList_A,3));
}아래 알고리즘에서 단일 연결리스트의 헤더노드는 값을 저장하는 유효 노드로서 작동한다.
함수 설명
init 함수: 연결리스트 초기화
① 리스트의 Head를 NULL로 선언한다. 이때 인자로 받는 같은 DListType 값이다.
② 리스트의 사이즈를 초기화한다.
쉽게 말해, 연결리스트를 담고 있는 '타입의 초기화'의 과정이다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef char element;
typedef struct Listnode {
int data;
struct Listnode* next;
}Listnode;
typedef struct ListType {
struct Listnode* Head;
int size;
}ListType;
void init(ListType* DList) {
DList->Head = NULL;
DList->size = 0;
}insertFirst 함수: 연결리스트의 첫 부분에 노드 추가
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.
③ 새로운 노드(new)에 값을 저장한다.
④ 연결리스트의 첫 부분에 노드를 추가하는 것이므로, new의 next를 Head노드와 연결한다.
⑤ Head노드에 new 노드를 저장한다. → 헤드노드의 위치를 바꾼다.
⑥ 노드의 사이즈를 증가한다.
void insertFirst(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
//새로운 노드 동적할당
Listnode* p = DList->Head;
/*노드 추가 시 기본 알고리즘*/
new->data = e; // 새로운 노드에 값 저장
new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결
if (p == NULL) {DList->Head = new;}//p가 널이면 헤드-테일을 각각 new로 초기화
else {DList->Head = new;}//연결리스트의 헤드를 new로 설정
DList->size++;
}insertLast 함수: 연결리스트의 끝 부분에 노드 추가
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.
③ 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회한다.
④ 순회 후 p가 NULL인 경우, 노드가 없는 경우이므로 헤드노드에 new를 저장한다.
⑤순회 후 p가 NULL이 아닌 경우, p의 next를 new로 지정한다.
⑥ 노드의 사이즈를 증가한다.
void insertLast(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;
while(p->next != NULL) {
if (p->next == NULL) {
break;
}
p = p->next;
}
new->data = e;
new->next = NULL;
if (p == NULL) DList->Head = new;
else p->next = new;
DList->size++;
}insert함수: 연결리스트의 노드 추가 함수(rank: 노드를 추가할 위치)
insert 함수의 기본 로직은 아래와 같다.
ⓞ 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 insertFirst함수를 실행한다.
④ rank의 값이 (DList->size + 1)이라면, 노드의 끝에 값을 추가하는 것이므로 insertLast함수를 실행한다.
⑤ rank의 값이 ③,④ 조건에 맞지 않는 경우 rank의 위치까지 이동한다.(순회)
⑥ new에 값을 저장한다.
⑦ new의 next를 순회가 끝난 p의 next로 설정한다.
⑧ 노드의 사이즈를 증가한다.
void insert(ListType* DList, element e, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return ;
}
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;//임의의 노드 생성
if (rank == 1) {insertFirst(DList, e);}
else if (rank == DList->size + 1) {insertLast(DList, e);}//(맨 마지막 + 1)위치 추가
else {
for (int i = 1; i < rank-1; i++) {p = p->next;}//원하는 위치까지 이동
// printf("inserting...\n");
new->data = e;
new->next = p->next;
p->next = new;
DList->size++;
}
}deleteFirst 함수: 연결리스트의 첫 부분에 노드 삭제
① DList->Head (헤드 노드)가 NULL이면 리턴한다. 즉, 아무것도 수행하지 않는다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ 헤드노드에 p의 next를 저장한다. 이는 헤드 노드가 값을 저장하는 유효 노드이기 때문에 가능하다.
④ 삭제할 노드의 값(output)을 저장한다.
⑤ 삭제할 노드(p)의 메모리를 해제한다.
⑥ 노드의 사이즈를 감소한다.
⑦ output을 반환한다.
element deleteFirst(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
element ouput = p->data;
DList->Head = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}deleteLast함수: 연결리스트의 끝 부분에 노드 삭제
단일 연결리스트는 이전 노드의 위치를 저장하는 prev 노드가 없으므로, 첫 번째 노드의 삭제가 아닌 경우 뒤 노드와 연결하기 위한 저장 연결리스트 노드가 필요하다. 이를 위해 임의로 prev 노드를 생성한다.
① DList->Head (헤드 노드)가 NULL이면 리턴한다. 즉, 아무것도 수행하지 않는다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ prev 노드를 생성한 후 NULL값을 저장한다.
④ 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회한다. 이때 prev에 초기화되기 전의 p를 저장한다.
⑤ 삭제할 노드의 값(output)을 저장한다.
⑥ prev의 값이 NULL일 때, 즉 리스트에 노드가 하나만 있을 때는 헤드에 NULL을 저장한다.
⑦ prev의 값이 NULL이 아닐 때, prev의 next에 NULL을 저장한다.
⑧ 노드의 사이즈를 감소한다.
⑨ output을 반환한다.
element deleteLast(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
Listnode* prev = NULL;
while(p->next != NULL) {
prev = p;
p = p->next;
}element ouput = p->data;
if (prev == NULL) DList->Head = NULL; // 리스트에 노드가 하나만 있을 때
else prev->next = NULL; // 마지막 노드를 삭제하기 위해 이전 노드의 다음 노드를 NULL로 설정
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}delete함수: 연결리스트의 노드 삭제 함수(rank: 노드를 삭제할 위치)
① 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
② rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 deleteFirst함수를 실행한다.
③ rank의 값이 (DList->size)이라면, 노드의 끝에 값을 추가하는 것이므로 deleteLast함수를 실행한다.
④ 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.
⑤ prev 노드를 생성한 후 NULL값을 저장한다.
⑤ rank의 위치까지 이동한다.(순회)
⑥ 삭제할 노드의 값(output)을 저장한다.
⑦ 삭제할 노드(p)의 메모리를 해제한다.
⑧ 노드의 사이즈를 감소한다.
⑨ output을 반환한다.
element delete(ListType* DList, int rank) {
element ouput ;
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1;
}
if (rank == 1) deleteFirst(DList);
else if (rank == DList->size) deleteLast(DList);
else {
Listnode* p = DList->Head;
Listnode* prev = NULL;
for (int i = 1; i < rank; i++) {
prev = p;
p = p->next;
}ouput = p->data;
prev->next = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
}
return ouput;
}getNode함수: 연결리스트의 값 확인 함수 rank: 노드를 확인할 위치)
① 노드를 확인할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
② 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.
③ rank의 위치까지 이동한다.
④ rank의 위치의 노드의 값을 반환한다.
element get(ListType* DList, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1; // 유효하지 않은 순위일 경우 -1 반환
}
Listnode* p = DList->Head;
for (int i = 1; i < rank; i++) {
p = p->next;
}
return p->data;
}print함수: 연결리스트 출력 함수
① 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.
② 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회하며 노드의 데이터를 출력한다.
void print(ListType* DList) {
for (Listnode* p = DList->Head; p != NULL; p = p->next) {
printf("[%d] -> ", p->data);
}printf("\b\b\b\b \n");
}이중 연결리스트의 ADT
#include <stdio.h>
#include <stdlib.h>
/*
실행 가능 확인 24.03.27
*/
typedef struct Node {
//연결리스트 본체: 가지고 있는 데이터 값과 전/후방 연결위치 저장
int data;
struct Node* next;
struct Node* pre;
}Listnode;
typedef struct list {
//리스트의 정보 : 리스트의 헤드노드와 테일 노드의 설정 구조체
int size;
Listnode* head;
Listnode* tail;
}list_info;
void add(list_info* list,int rank,char data)
{
Listnode* curr = list->head;
for (int i = 0; i < rank; i++) {
/*
rank위치까지반복(curr)
-> curr은 새로 생성할 new의 다음 노드가 되어야함.: new->next = curr;
-> curr의 뒷 노드는 new의 뒷 노드가 되어야함: new->pre = curr->pre;
-> curr의 뒷 노드의 다음 노드는 new가 되어야함: (curr->pre)->next = new;
-> curr의 뒷 노드는 new가 되어야함: curr->pre = new;
*/
curr = curr->next;
}
Listnode* new = (Listnode*)malloc(sizeof(Listnode)); //새로 추가할 노드
new->data = data;
new->next = curr;
new->pre = curr->pre;
(curr->pre)->next = new;
curr->pre = new;
list->size++;
}
void delete(list_info* list,int rank)
{
Listnode* del = list->head;
for (int i = 0; i < rank; i++) {
del = del->next; // rank의 위치까지 반복
}
/*
1. "지울 노드의 뒷 노드"의 다음 노드는 "지울 노드의 다음 노드"가 되어야함.
2. " '지울 노드의 다음 노드'의 '뒷 노드'"는 "지울 노드의 이전 노드"가 되어야함
*/
(del->pre)->next = del->next;
(del->next)->pre = del->pre;
list->size--;
}
void get(list_info* list,int rank) {
Listnode* p = list->head;
for (int i = 0; i < rank; i++) {
p = p->next; // rank 위치의 노드로 이동
}
printf("%c", p->data);
}
void print(list_info* list) {
Listnode* p = list->head->next;
while (p != list->tail) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
list_info* list = (list_info*)malloc(sizeof(list_info));
list->head = (Listnode*)malloc(sizeof(Listnode));
list->tail = (Listnode*)malloc(sizeof(Listnode));
list->head->pre = NULL;
list->head->next = list->tail;
list->tail->pre = list->head;
list->tail->next = NULL;
list->size = 0;
int n;
scanf("%d",&n);getchar();
char operator ;
for (int i = 0; i < n; i++) {
scanf("%c", &operator);
if (operator=='A') {
int r;char data;
scanf("%d %c", &r, &data);getchar();
if ((r > list->size + 1) || (r < 1)) {printf("invalid position\n");}
else add(list,r, data);
}
else if (operator=='D') {
int r;
scanf("%d", &r);getchar();
if ((r > list->size) || (r < 1)) {printf("invalid position\n");}
else delete(list, r);
}
else if (operator=='G') {
int r;
scanf("%d", &r); getchar();
if (r > list->size) {printf("invalid position\n");}
else get(list, r);
}
else if (operator=='P') {
getchar();
print(list);
}
}
return 0;
}728x90
반응형