선형 검색(Linear Search)

배열의 각 요소를 처음부터 끝까지 순차적으로 탐색하여 일치하는지 판단하는 방법이다.

 

선형 검색의 종료 조건

• 검색할 값을 발견한 경우
• 배열 끝까지 검색해도 검색할 값을 찾지 못한 경우

 

simple linked list로 구현하기

// 연결 리스트의 노드를 나타내는 구조체의 정의
struct Node {
    int data;
    struct Node* next;
}
// 연결 리스트에 노드를 추가하는 함수
struct Node* insertNode(struct Node* head, int data){

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node -> data = data;
    new_node -> next = NULL;
    
    if(head == NULL)
    	head = new_node;
    else{
    	struct Node* temp = head;
        while(temp->next != NULL){
        	temp = temp -> next;
        }
        temp -> next = new_nodel
    }
    
    return head;
}

void displayList(struct Node* head){
    if(head == NULL){
    	cout << " 리스트가 비어 있다." << endl;
        return;
    }
    
    struct Node* temp = head;
    while(temp != NULL){
    	cout << "->" << temp-> data;
        temp = temp -> next;
    }
    cout << endl;
}
// linear search를 사용하여 연결 리스트에서 값 찾는 함수
struct Node* linearSearch(struct Node* head, int key){
    struct Node* temp = head;
    
    while(temp != NULL){
    	if(temp -> data == key) return temp;
        temp = temp -> next;
    }
    
    return NULL; // 값을 찾지 못한 경우
}

int main(){
    struct Node* head = NULL;
    int value, n;
    
    cout << "원소의 개수를 입력하세요: ";
    cin >> n;
    
    for(int i=0; i<n; ++i){
    	cout << "원소를 입력하세요 : ";
        cin >> value;
        head = insertNode(head, value);
    }
    
    cout << "입력된 연결 리스트 : ";
    displayList(head);
    
    return 0;
}