(10)[Chapter6]순차탐색_전진이동법,전위법(코드편) (작성중)

##연결리스트 구조체,삽입,출력 코드 :

 

##전진이동법 메소드 코드:

##전위법 메소드 코드 :

##전체 코드 :

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
typedef struct _Node {
    struct _Node* next;
    int data;
}Node;
 
void AppendList(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;
 
    if (*head == NULL) {
        *head = newNode;
        return;
    }
 
    Node* last = *head;
 
    while (last->next != NULL) {
        last = last->next;
    }
 
    last->next = newNode;
 
    return;
}
 
void PrintList(Node* head) {
    printf("Linked List : [ ");
    Node* trace = head;
    while (trace!=NULL) {
        printf("%d", trace->data);
        trace = trace->next;
        if (trace != NULL) {
            printf(", ");
        }
    }printf(" ]\n");
}
 
//전진이동법 메소드
Node* MFS(Node** head, int data) {
    //1_ 준비물
    Node* C = *head;
    Node* P = NULL;
    Node* M = NULL;
 
    //2_ 탐색 시작 + 못찾았다면,
    while (C != NULL)//2_1) 탐색 
    {
        if (C->data == data) //3_ 찾았다면 => Match에 기록 남기기
        {
            M = C; //기록 남기기
 
            if (P != NULL) {//4_ 찾은 노드가 2번째 이상 노드라면, H->.....->P->C->....->NULL 상황
 
                //4_1 : P링크 연결
                P->next = C->next;
                //4_2 : C링크 Head에 연결
                C->next = *head;
                //4_3 : Head 업데이트
                *head = C;
 
            }
            //else... 찾은게 head라면, => 아무 코드 처리 할 필요 없다
            break;//★
        }
        else//2_2) 못찾았다면, => 발자취 , Current이동
        {
            P = C;
            C = C->next;
        }
    }
 
    return M;//5_ Match 반환
}
 
//전위법 : 탐색된 노드를 한칸씩 이동시켜 정렬
Node* TPS(Node** head, int data) {
    //1_ 준비물(4가지) : Current, Previous, PPrevious, Match
    Node* C = *head;
    Node* PP = NULL;
    Node* P = NULL;
    Node* M = NULL;
 
    //2_ 탐색 + 못찾았다면,
    while (C!=NULL) {
        if (C->data==data) {//3_찾았다면,
            //3_1_Match에 기록 남기기
            M = C;
            
            //3_2_ Head == Current vs 2번째 이상 노드에 Current인 경우
            if (P != NULL) //2번째 이상 노드에 Current인 경우
            {
                //3번쨰 이상 노드 vs 2번째 노드 Current
                //ⓐ. Current 전전의 노드 링크 처리
                if (PP != NULL) 
                {//3번쨰 이상 노드 => PP의 링크 Current에 연결
                    PP->next = C;
                }
                else //2번째 노드 (H(P)->C->) => Head를 Current에 연결
                {
                    *head = C;
                }
 
                //ⓑ. Previous 링크 처리
                P->next = C->next;
 
                //ⓒ. Current의 링크 처리
                C->next = P;
 
 
            }
            //Head == Current 상황에서는 전위법을 처리할 것이 없다.
 
            //4_ 정지
            break;
 
        }
        else {//못찾았다면, =>PP의 발자취 , P의 발자취 , C의 발자취 
            if (P != NULL) PP = P;//P의 발자취
            P = C;//C의 발자취
            C = C->next;//C 이동
        }
    }
 
    return M;
}
 
int main() {
 
    //리스트 1
    Node* L1 = NULL;
 
    AppendList(&L1, 1);
    AppendList(&L1, 2);
    AppendList(&L1, 3);
    AppendList(&L1, 4);
    AppendList(&L1, 5);
 
    PrintList(L1);//1 2 3 4 5
 
    //3을 탐색, 전진 이동법
 
    Node* Search = TPS(&L1, 3);
 
    if (Search != NULL) {
        printf("%d\n", Search->data);//3출력
    }
    else {
        printf("못찾았습니다.\n");
    }
 
    PrintList(L1);// 1 3 2 4 5
 
    //6을 탐색, 전진 이동법
 
    Search = TPS(&L1, 3);
 
    if (Search != NULL) {
        printf("%d\n", Search->data);
    }
    else {
        printf("못ㅠ찾았습니다.\n");//6이 없으므로,
    }
 
    PrintList(L1);//3 1 2 4 5
 
    return 0;
}