180206 튜터링 - 연결리스트

< 재귀함수 숙제 review >

- 1부터 n까지의 숫자중 홀수/짝수의 합 구하기

#include <stdio.h>
 
int oddSum(int n)
{
    if(n < 1) return 0;
    if(n%2 == 0) n--;
    return n + oddSum(n-2);
}
 
int evenSum(int n)
{
    if(n < 1) return 0;
    if(n%2 == 1) n--;
    return n + evenSum(n-2);
}
 
int main()
{
    int n = 100;
    printf("%d\n", oddSum(n)); 
    printf("%d\n", evenSum(n)); 
    return 0;
}

>> 6번째 줄을 if(!(n%2)) 로 쓸 수도 있다.

>> 13번째 줄은 if(n&1) 로 쓸 수 있다.

- 배열의 요소들 중에서 최대값 구하기.

#include <stdio.h>
 
int f(int arr[], int n)
{
    int k;
    if(n == 0) return arr[0];
    k = f(arr, n-1);
    return k > arr[n] ? k : arr[n];    
}
 
int main()
{
    int arr[] = {10, 2, 30, 11, 50, 33};
 
    printf("%d\n", f(arr, 5));
    return 0;
}

- 배열의 요소들 중에서 두번째 최대값 구하기.

#include <stdio.h>
 
int max;
 
int f2(int arr[], int n)
{
    int k;
    if(n == 1) {
        max = arr[n] > arr[n-1] ? arr[n] : arr[n-1];
        return arr[n] > arr[n-1] ? arr[n-1] : arr[n];
    }
    k = f2(arr, n-1);
    
    if(arr[n] < k) return k;
    if(arr[n] > max) { int t=max; max=arr[n]; return t; }
    return arr[n];
}
 
int main()
{
    int arr[] = {50, 10, 2, 30, 11, 33};
 
    printf("%d\n", f2(arr, 5));
    return 0;
}

>> n 은 마지막 인덱스

< 연결리스트 >

- 노드 디자인 하기

typedef struct node {
    int data;
    struct node *next;
} Node;

>> 자기참조 구조체

>> typedef 의 역할 // ex) typedef int INT;

>> 구조체는 자료형이다. 사용자 정의 자료형. 즉, 우리가 만든 자료형이다.

- List 주머니(?) 디자인 하기.

typedef struct list {
    Node *head;
} List;

- 리스트 생성 후 초기화 하기

#include <stdio.h>
 
typedef struct node {
    int data;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
int main()
{
    List list;
    init(&list);
 
    return 0;
}

>> 19 : List 타입의 list 변수 생성

>> 20 : list 를 초기화 하는 코드. C++에서 생성자를 수동으로 실행시킨다고 생각하면 될 것 같다.

- 데이터 삽입하기.

void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
 
    if(list->head == NULL)
        list->head = newNode;
    else {
        newNode->next = list->head;
        list->head = newNode;
    }
}

 

>> 3 : 동적할당으로 #include <stdlib.h> 헤더파일이 필요하며, 

   결과 값으로 이름없는 변수의 주소값을 리턴한다. 그리고 그 주소를 newNode 에 저장.

>> 3, 5, 1 순으로 삽입을 하면 (head)->(1)->(5)->(1)->NULL 모양의 리스트가 만들어 진다.

     즉, 앞쪽으로 데이터가 삽입이 된다.

     (그림은 머릿속으로.....)

>> newNode->data : newNode가 가리키는 변수의 멤버 data (고요속의 외침..ㅎㅎ)

>> 아래와 같이 분기를 하지 않아도 될 것 같다.

void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = list->head;
    list->head = newNode;
}

>> 검증은 못해봄. 누가 테스트 해보고 결과좀 알려줘. ㅎ

- 데이터 뒤로 삽입하기. 

1) 리스트 주머니 수정하지 않고 해보기.

2) 리스트 주머니를 수정해서 해보기.

1) 의 경우

void insertNodeBack(List *list, int data)
{
    Node *prev, *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
 
    if(list->head == NULL) {
        list->head = newNode;
    }
    else {
        prev = list->head;
        while(prev->next != NULL)
            prev = prev->next;
        prev->next = newNode;
    }
}

>> 12-13 : prev 를 통해 맨 마지막 노드를 찾는 코드이다. 

>> 14 : 맨 마지막 노드를 찾았으면, 거기에 새 노드를 연결하면 될 듯.

### 자료구조 공부할 때, 특히 포인터등이 헷갈릴때는 그림을 그려가면서 해봐 얘들아 ㅎㅎ

### 숙  제 ###

- 복습 잘하기.

- 어떤 문자열이 주어졌을 때, 해당 문자열이 팰린드롬(회문)인지 판단하는 함수 재귀함수로 만들기

- 리스트의 내용을 모두 출력하는 함수 만들기

- 양방향 연결4리스트, 환형 연결리스트 예습해오기.