데이터 구조 8

• Linked list 이어서...

-  head 삭제 ( 출력 후 삭제라고 봐도 됨 )

  알고리즘: 

 

1. (Empty 체크 후) 새로운 노드 A를 만든 후, 지울 내용을 복사한다. 

2. 새로운 노드 타입 포인터(*p)로 지울 노드를 가리켜서 잡아둔다.

( 목적 : head를 옮겨야하는데 안 잡아두고 옮기면 다시 접근할 방법이 없다.) 

3. head 포인터를 다음 포인터로 옮긴다.

4. p가 가리키는 노드 삭제.

5. 노드 A리턴

 

 

- Num of node

알고리즘:

 

1. 노드를 가리키는 포인터 p를 만들고, int count = 0; 을 만든다.

2. 반복문을 만든다

 2-1 . 조건: p의 시작점= NULL ; P!=NULL이 아닐 때까지 ; p-> link를 따라서   ( 이 부분이 생소할 수 있음 )

        for(p=NULL ; p!=NULL ; p->link)

 2-2 . 반복 내용 = count++;

3. return count

 

 

- List empty

알고리즘:

헤드가 NULL이면 Empty

 

 

Linked list - stack+Queue

 

- 스택

  → 리스트의 첫(방금 들어온) 노드를 항상 TOP으로 설정

     + Push, Pop 모두 TOP에서 수행한다.

 

- 큐  

  → 첫 원소 = Front (삭제할,먼저 출력될 위치)

  → 끝 원소 = Rear (추가할 위치)

 

## Rear 랑 Front 중에 어디로 들어가고 나가는지 잘 알기! 다들 헷갈려함 

 

 

• Linked list 응용

 

- Invert ( 순서 뒤집기 = 방향 역순으로 바꾸기 ) <<링크만 조절하는 거임

 

(교수님 자료로) 

                 (뒤집힌 쪽)   |  (안 뒤집힌 쪽)

                new head ↓    |    ↓  old head               

                   1 < 2 <  3    |    4 > 5 > 6

노드 타입  포인터 p ↑

 

뒤집는 알고리즘 :

Loop

  L - 1. New head가 가리키는 노드를 가리키는 노드타입 포인터 p 생성        →    Node p = New head;

  L - 2. New head가 Old head의 위치로                                                          →    New head = old head;

  L - 3. Old head가 한 칸 앞으로                                                                      →     old head = old head -> link;

  L - 4. New head의 link = p (p는 New head의 이동 전 자리에 있음)              →      New head ->link = p;

 

ex)

1> 2> 3> 4> 5 순서인 리스트에서

 

시작할 때, new head 는 NULL , tmp=new head이므로 NULL , old head는 head(=1)에서 시작.

 

변수가 3개인 이유: 조절 작업할 곳 = new head  /  바라볼 곳 =tmp  / 다음 단계 자리 맡아놓는 역할 = old head 

 

 

 

시작 : New head = NULL

          Old head = head;

 

반복 조건 : Old head !=NULL 

 

증가값 : p->link   (맞는지 확인 나중에 하기)

 

1번째 loop

tmp= new head (NULL)

new head = old head ;               // new head가 1로 이동

old head = old head ->link;       //old head가 2로 이동

new head -> link = p;                //1이 바라보는 곳을 NULL(p)로 바꿈

 

결과 : 위치-  p=NULL , new head=1 , old head=2

링크 : 1 2>3>4>5

 

 

 

2번째 loop

tmp= new head (1)

new head = old head ;               // new head가 2로 이동

old head = old head ->link;       //old head가 3으로 이동

new head -> link = p;                //2가 바라보는 곳을 1(p)로 바꿈

 

결과 : 위치-  p=1 , new head=2 , old head=3

링크 : 1 <2  3>4>5

 

 

3번째 loop

tmp= new head (2)

new head = old head ;               // new head가 3으로 이동

old head = old head ->link;       //old head가 4로 이동

new head -> link = p;                //3이 바라보는 곳을 2(p)로 바꿈

 

결과 : 위치-  p=2 , new head=3 , old head=4

링크 : 1 <2 < 3  4>5

 

 

4번째 loop

tmp= new head (3)

new head = old head ;               // new head가 4으로 이동

old head = old head ->link;       //old head가 5로 이동

new head -> link = p;                //4가 바라보는 곳을 3(p)로 바꿈

 

결과 : 위치-  p=3, new head=4 , old head=5

링크 : 1 <2 < 3 <4 5

 

 

5번째 loop

tmp= new head (4)

new head = old head ;               // new head가 5으로 이동

old head = old head ->link;       //old head가 NULL로 이동

new head -> link = p;                //5가 바라보는 곳을 4(p)로 바꿈

 

결과 : 위치-  p=4 , new head=5 , old head=NULL

링크 : 1 <2 < 3 < 4 < 5

 

종료 조건이 old head != NULL이므로 여기에서 종료.

 

 

 

 

시작 : New head = NULL 

          Old head = head;

 

반복 조건 : Old head !=NULL 

 

증가값 : p->link   (맞는지 확인 나중에 하기)

 

---

 

- List_equal 검사

 

리스트 두 개가 같은지 검사하는 함수

 

1. 검사하는 함수( 리스트 a , 리스트 b)

   return - 검사작업함수 ( a.head , b.head )

 

 ->  2 검사 작업 함수 ( node *p1 ,  node *p2 )

 

 [ 1) 구조 먼저 검사 ]

     if((p1==NULL) and(p2==NULL)) // 둘 다 NULL이면 

         return true;                              // 없긴해도 두 개 같으니 true;

       if((p1==NULL) or (p2==NULL)) // 둘 중에 하나만 NULL이면

         return false;                              // false;

[ 2) 내용 검사 ] 

    if ( 내용 검사(*p1, *p2) )            //  그럼 둘 다 NULL 아닐 때 내용 검사해서 같으면

         return(is_equal(p1->link, p2->link));  //그 다음 거 구조검사 딱 대

         else false;                             //내용 다르면 ㅃ

 

 

3. 내용 검사 함수 (node t1, node t2)

       if ( (t1.name == t2.name) and (t1.score == t2.score))         // 데이터 내용이 다 같으면 true

            return true;

          else

            return false;

 

 

 

 

 

 

 

 

++교수님이 알려주신 LOOP 팁

 

LOOP은 

1. 초기연산

2. 단위 연산

3. 종료 조건 ( = 수행 조건 )

을 알고 만들기

ex) for( 1; 3; 2 )

 

 

 

출처 : 한동대학교 김호준교수님 - 데이터구조 PPT