Written by nodejs-style
on 2021-10-29

[ 자료구조 ] linked list 연결 리스트 , k값을 가진 노드 삭제 삽입 함수

728x90

리스트는 아무 곳에서나 삽입, 삭제가 일어날 수 있다.

k값을 가진 노드 삭제 함수

데이터 값이 k인 노드를 찾는다.

before : k값을 가진 노드의 앞 노드이다.

temp : k값을 가진 노드이다. 이 알고리즘에서 찾는 삭제할 노드이다.

before의 링크를 k값을 가지는 링크로 바꾼다. 그리고 반복문을 빠져나온다.

#include #include struct node { int data; struct node * link; }; typedef struct node list_node; typedef list_node * list_ptr; void delete(list_ptr p, int k) { list_ptr temp, before; // before는 temp앞 노드를 가리킨다. if(!p) return; // p가 null일경우 아무것도 반환하지 않는다. p가 참조하는 리스트가 없다는 뜻 before = NULL for(temp = p; temp!=NULL; temp = temp->data){ // temp!=NULL을 그냥 temp로 바꿀수 있다. 양수=true if(temp->data == k){ // temp의 data가 k인 것을 찾기 before->link = temp->link; // k를 찾은 뒤, before의 링크를 temp의 링크로 바꾸기 break; } before = temp; // k값을 찾을때까지 현재 노드의 주소를 before에 저장한다. } } int main() { list_ptr p; p = create(4); print_list(p); // 10 20 30 40 delete(p,30); print_list(p); // 10 20 40 }

728x90

Quiz) 만약 맨 처음 노드의 데이터가 k이면 어떻게 해야 하는가?

퍼스트의 링크 값을 퍼스트의 넥스트의 링크로 바꾼다.

// 리스트의 첫 노드, 삭제될 노드의 앞 노드, 삭제될 노드 void delete(list_ptr * p, list_ptr before, list_ptr temp) { if(temp == *p) // 삭제될 노드가 리스트의 첫 노드일때 *p = temp->link; // 첫번째 노드의 값을 삭제될 노드의 링크로 바꾼다. else // 삭제될 노드가 리스트의 첫 노드가 아닐때 before->link = temp->link; // 삭제될 앞 노드의 링크값을 현재 링크로 바꾼다. free(node); }

k값을 가진 노드 삽입 함수

데이터를 찾아가다가 자신보다 큰 데이터를 만나면, 큰 데이터를 가지는 노드 앞에 새로운 노드를 삽입해야 한다.

k = 35를 대입

// 데이터 값 35를 가진 노드를 새로 생성해 삽입한다.

temp1 : 새로 생성되는 노드 참조 포인터

// 따라서 데이터 값 35를 가지는 노드를 생성한다.

temp : k 보다 큰 값을 찾는 포인터, 노드를 순서대로 참조하다가 k 보다 큰 데이터를 만나면 멈춘다.

// 따라서 데이터 값 40을 가지는 노드를 참조한다.

// temp1 보다 큰 데이터 값을 가지는 뒤 노드

before : temp의 앞을 가리키는 포인터

// 따라서 데이터 값 30을 가지는 노드를 참조한다.

// temp1 보다 작은 데이터 값을 가지는 앞 노드

#include #include struct node { int data; struct node * link; }; typedef struct node list_node; typedef list_node * list_ptr; void insert(list_ptr p, int k){ list_ptr temp, before, temp1; // 순서대로 temp1 뒤 노드, temp1의 앞 노드, temp1 새로운 노드 포인터이다. if(!p) return; // p가 NULL이면 아무것도 반환하지 않는다. before = NULL; // 새로생긴 temp1의 앞 노드를 before에 저장한다? NULL로 초기화 for(temp = p; temp != NULL; temp = temp->link){ if(temp->data > k){ temp1 = (list_ptr)malloc(sizeof(list_node)); // 새로 생긴 노드 동적 할당 temp1->data = k; // 새로 생긴 노드에 k값 데이터 대입 temp1->link = temp; // (2) temp1(새로운)의 링크에 temp(뒤 노드)대입, 뒤를 연결 before->link = temp1; // (1) before(앞 노드)의 링크에 temp1(새로운) 노드 대입, 앞을 연결 break; // (temp->data)=40 일때 멈춘다 } before = temp; // temp가 계속 값을 찾을때까지 반복 연결됨 } } int main() { list_ptr p; p = create(4); print_list(p); // 10 20 30 40 insert(p, 35); print_list(p); // 10 20 30 35 40 }

(1) 앞 노드(before) 링크에 새 노드 (temp1) 대입

(2) 새 노드 (temp1)의 링크에 뒤 노드(temp) 대입

728x90

구조체 포인터의 포인터를 가진 노드 삽입 함수

변경하고 싶은 데이터를 값을 main 함수와 주고받을 때 구조체 포인터의 주소 값(*ptr)을 함수에 넘겨준다(&ptr;).

list_ptr *ptr = 구조체 포인터의 포인터이다.

구조체 포인터의 포인터를 준다

포인터가 가리키는 노드 30 다음에 새로운 노드 50을 삽입하려고 한다.

구조체 포인터의 포인터를 주는 것은 before을 알려주는 것과 같다.

변경해야 할 것 1 : 노드 30의 링크 주소,

변경해야 할 것 2 : 새 노드 50의 링크에 노드 20을 가리키는 링크 생성

연결 리스트 CASE

void insert(list_ptr *ptr, list_ptr aptr, int x){ list_ptr = temp; temp = (list_ptr)malloc(sizeof(list_node)); temp->data = 50; if(*ptr){ // 연결리스트가 빈리스트가 아닌 경우 temp->link = aptr->link; 현재 노드의 링크값을 앞 노드의 링크값으로 바꾼다. aptr->link = temp; 앞노드의 링크가 현재 노드를 가리키도록 한다. } else { // 연결리스트가 비어있는 경우 temp->link = NULL; *ptr = temp; }

1. 연결 리스트가 비어있는 경우

ptr 값이 변경된다.

따라서 prt 대신 ptr의 주소 값 *ptr을 인자로 받아야 한다.

함수에서 ptr 값 변경을 위해 주소를 전달하는 것이다.

2. 연결 리스트가 빈 리스트가 아닐 경우

현재 링크를 전 링크로 바꾸고

temp->link = aptr->link

전 링크가 현재 노드를 참조하도록 바꾼다

aptr->link = temp;

728x90

구조체 포인터의 포인터

void insert (list_ptr *ptr, list_ptr node) int main(){ insert (&ptr;, node); }

ptr의 주소 값을 인자로 전달하는 경우

#include #incldue struct node{ int data; struct node * link; // 자기참조 구조체 }; typedef struct node list_node; typedef list_node * list_ptr; void create1(list_ptr * ptr) // 구조체 포인터의 포인터를 받음 { list_ptr temp = NULL; temp = (list_ptr)malloc(sizeof(list_node)); // 새로운 temp 노드에 동적할당 temp->data = 10; temp->link = NULL; *ptr = temp; } int main() { list_ptr ptr = NULL; // 구조체 포인터 선언 create1(&ptr;); // 구조체 포인터의 주소값 전달 printf("%d

", ptr->data); }

728x90

from http://psy-er.tistory.com/60 by ccl(A) rewrite - 2021-10-29 01:00:19

Top