180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트

< 숙제 review >

1) 팰린드롬인지 판단한는 함수 재귀함수로 구현하기

#include <stdio.h>
#include <string.h>
 
int isP(char str[], int s, int e)
{
    if(s >= e) return 1;
    return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
}
 
int main()
{
    char str[100];
    scanf("%s", str);
    isP(str, 0, strlen(str)-1) ? puts("True") : puts("False");
    return 0;
}
 

>> 첫번째 인덱스와 마지막 인덱스의 문자가 같을때, 그 안의 문자열이 팰린드롬이면 팰린드롬이다.

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

void printList(List *list)
{
    Node *p = list->head;
    while(p != NULL) {
        printf("%d\n", p->data);
        p = p->next;
    }
}

< Tutoring >

< 연결리스트의 전체노드 삭제 >

void deleteList(List *list)
{
    Node *p = list->head;
    while(p != NULL) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    init(list);
}

>> 위 예제의 응용에 불과하다고 생각함.

>> 동적할당으로 생성된 변수는 free() 를 통해 해제를 시킬 수 있다.

>> 9번은 다 지우고 난 다음 초기화를 다시 해주는 역할 정도..

< 연결리스트에서 특정 노드의 삭제 >

void deleteNode(List *list, int pos)
{
    int k = 1;
    Node *prev, *cur = list->head;
    if(pos == 1) {
        list->head = list->head->next;
        free(cur);
        return ;
    }
    
    while(k < pos) {
        k++;
        prev = cur;
        cur = cur->next;
    }
    prev->next = cur->next;
    free(cur);
}

>> 11~14 에서 첫번째 노드가 1번 노드라고 할 때, k번째 노드는 cur 가 가리키게 된다.

>> 하지만 위의 코드는 pos 의 값이 노드의 갯수보다 큰 값이 들어오면 에러가 발생한다.

void deleteNode2(List *list, int pos)
{
    int k = 1;
    Node *prev, *cur = list->head;
 
    if(cur == NULL)
        return ;
 
    if(pos == 1) {
        list->head = list->head->next;
        free(cur);
        return ;
    }
    
    while(cur != NULL && k < pos) {
        k++;
        prev = cur;
        cur = cur->next;
    }
 
    if(cur == NULL) {
        puts("Position does not exist.");
        return ;
    }
 
    prev->next = cur->next;
    free(cur);
}

>> 어떤 부분들이 바뀌었는지 비교해봐 얘들아.. ㅎㅎ

>> 그외 List 주머니에 사이즈 관련 변수 하나 만들어서 노드의 개수를 카운트 해나가면서

     pos 값이 그 사이즈 안에 있는 값인지 체크하는 방법으로 해도 되고, 상황에 맞게 하면 될듯.!!

< 원형연결리스트의 삽입 (앞에) >

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
void CircularListAdd(List *list, int data)
{
    Node *p, *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
 
    if(list->head == NULL) {
        list->head = newNode;
        newNode->next = newNode;
        return ;
    }
 
    p = list->head;
    while(p->next != list->head)
        p = p->next;
 
    p->next = newNode;
    newNode->next = list->head;
    //list->head = newNode;
}
 
void printCircularList(List *list)
{
    Node *cur = list->head;
 
    if(cur == NULL) return ;
 
    do {
        printf("%d\n", cur->data);
        cur = cur->next;
    } while(cur != list->head);
}
 
int main()
{
    List list;
    init(&list);
    
    CircularListAdd(&list, 1);
    CircularListAdd(&list, 3);
    CircularListAdd(&list, 7);
    CircularListAdd(&list, 5);
 
    printCircularList(&list);    
 
    return 0;
}

>> 18 : 원형 연결리스트의 데이터를 삽입하는 함수.

>> 38 : 원형 연결리스트의 데이터를 출력하는 함수

>> 60 의 결과는 1, 3, 7, 5

>> 35 의 주석을 해제했을 때, 60의 결과는 5, 7, 3, 1

>> 즉 35가 없으면 뒤로 삽입, 있으면 앞으로 삽입을 하는 결과가 만들어진다.

>> 다만 위의 코드에서는 삽입을 할때, 항상 맨 마지막 노드를 찾아야 하는 번거로움(?)이 있다.

     하지만 헤드포인터를 테일이라고 생각하고 코드를 작성하면 그럴필요가 없어진다..!!

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

>> head 를 tail 이라고 생각하면 된다.

>> 12 가 없으면 앞으로 삽입, 12가 있으면 뒤로 삽입하는 코드가 된다.

< 원형연결리스트의 노드들 중 홀수의 갯수 세기 >

- printCircularList() 에서 홀수인지만 판단한는 조건만 추가하고 계산 후 그 값을 리턴하면 된다.

- 그러니 우리는 if(cur->data & 1) 이라는 표현에 대해 알아보자.

>> & 는 비트 연산자로 각 비트별 AND 연산을 수행한다.

>> 참고로 모든 홀수의  마지막 비트(2^0)은 항상 1 이다.

     모든 짝수의 마지막 비트는 항상 0 이다.

>> 1 은 8비트 기준 00000001 이다.

>> 그러므로 1과 & 연산을 하면, 마지막 비트를 제외한 비트는 1이든 0이든 AND 연산의 결과는

    0이 나온다. 그렇기 때문에 홀수와 1에 대해 &(AND) 연산을 하면 항상 1이 나온다.

>> 조건식에서 1은 참을 의미한다..

cf) -1 은 비트로 표현하면 1로만 구성이 된다. 8비트라면 11111111 이 된다.

>> 1을 더하면 0이 되므로 증명 끝..

>> -2는 -1에서 1을 빼면 된다. 그러므로 -2는 8비트기준 11111110 이 된다.

>> -3은 -1에서 2를 빼면 된다. 그러므로 -3은 8비트 기준 11111101 이 된다.

>> 작은 수들은 굳이 2의 보수 취하지 않고도 이런식으로 구할 수 있다.

< 양방향 연결리스트의 삽입 >

- 우리가 지금까지 했던 연결리스트는 한방향으로만 연결이 되어 있다.

  하지만, 양방향 연결리스트는 말 그대로 양방향으로 연결이 되어 있다. 그러므로 prev 같은 노드 

  포인터가 필요없어진다.

- 노드에 대한 디자인도 새로 해야한다.

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

>> 4 : 이전 노드를 가리키기 위한 포인터가 추가되었다.

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

>> 앞으로 삽입하는 코드. 

>> 6, 12번 줄이 추가가 된다.

< 더미노드를 이용한 양방향 연결리스트의 삽입 >

- 더미노드를 사용하면 list->head 가 가리키는 노드가 바뀌는 것에 대한 염려를 안해도 된다.

- 더미노드를 사용하면 init() 함수를 수정해주어야 한다. 

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

>> 그리고 삽입코드는 위와 같이 쓸 수 있다.

< 숙제 >

- 복습잘하기

- 이중연결리스트에서 position 값이 주어졌을 때, 해당 위치에 노드를 삭제하는 함수 만들기

- 양의 정수를 입력 받았을 때, 3자리 마다 , 를 찍어서 출력해주는 함수(재귀로)

   input : 1000000 >> output : 1,000,000

- 스택, 중위식을 후위식으로 표기하는 방법, 후위식을 계산하는 방법 예습해오기