[C 언어] 링크드 리스트 Node삽입 (Linked list node insert at nth node)

공부/- 링크드_리스트 2016. 6. 1. 09:31

이번에는 단일 링크드 리스트(Single Linked List)에서... 특정 위치에 Node를 삽입하여 

저장하는 코드입니다.


head -> 1_번node -> 2_번Node -> 3_번Node -> NULL(자료의 끝)


위와 같이 Node들이 연결되어 있다면,


2번에 새로운 new_node를 삽입하는 함수를 만들었습니다.


void InsertNode(int data, int n);

data는 넣을 자료값, n은 몇번째 node에 넣을지 알려줍니다.

주의 사항은, Node를 1번부터 시작한다고 약속한 점이고,

추가로... 신규 new_node를 2번에 넣는다면, 기존 2번Node는 뒤로 밀리고,

새로운 new_node가 2번Node가 되는 형태로 작성하였으니...


아래의 for(i=0 ; i<n-2 ; i++) 내용에서 n-2로 위치를 지정한 것을 참고하세요.


또한 원하는 node로 이동하는 것이나, Node를 모두 탐색하는 것은

둘 다 현재_node = 현재_node->next; 의 방식을 사용하는 점이 동일합니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// insert a node at nth position
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    printf("Good bye");
}
 
cs




이 코드에서 추가로 n번째 자료를 지우는 부분도 추가합니다.


지우는 함수도 Insert 함수와 유사합니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void DeleteNode(int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void DeleteNode(int n)
{
    int i;
    Node_T *temp1 = head;
    if (n == 1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }
    
    for (i = 0; i < n - 2; i++)
        temp1 = temp1->next;
        
    Node_T * del_node = temp1->next;
    temp1->next = del_node->next;
    free(del_node);
    
//    delete_node = NULL;  
    // 주의 delete_node가 가르키는 malloc된 공간을 free해야하며
    // delete_node 포인터 자체는... NULL로 하면 안된다.
    
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    DeleteNode(1);
    DeleteNode(2);
    PrintNodes();
    printf("Good bye");
}
 
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

[C 언어] 포인터를 이용한 sort, swap 함수 구현

공부/- 포인터 2016. 6. 1. 08:59

Pointer(포인터)를 이용해서, 문자열을 알파벳 순서로 정렬(sort)하는 예제 코드 입니다.


어제 포스팅한 single linked list의 3번째 예제처럼 포인터의 포인터(포인터의 주소)를

전달하여, swap함수에서 두 자료를 교환하고 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// swap 함수 2016/6/1
 
void swap(char **a, char **b);
void sort(char *ary[], int cnt);
 
 
void swap(char **a, char **b)
{
    char *temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
//sort a, b, c...
void sort(char *ary[], int cnt)
{
    int i, j, min;
    for (i = 0; i < cnt - 1; i++)
    {
        min = i;
        for (j = i + 1; j < cnt;j++)
        {
            if (strcmp(ary[min], ary[j]) > 0)
                min = j;
        }
        swap(&ary[min], &ary[i]);
    }
}
 
void main(void)
{
    int i;
    char *arr[] = { "abecd", "ddbeeddd", "cedvae","hhxxz" };
    sort(arr, 4);
    for (i = 0; i < 4; i++)
    {
        printf("%s, ", arr[i]);
    }
    printf("Good bye\n");
}
 
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

[c 언어] 링크드 리스트의 3가지 표현법(Linked List)

공부/- 링크드_리스트 2016. 5. 31. 18:34



C언어를 배우면서... 가장 어려운 것이 포인터이고...


그리고, 이 포인터를 쓰는... 링크드 리스트(Linked List)도 역시나 어렵습니다.


저도 공부하면서... 가장 실수를 많이 한 것이 링크드 리스트인데...




공부해보니 특히나... head 노드 변수를 어느 위치에서 선언하느냐에 따라 


구현 방식의 차이가 있더군요.


이러한 방식은 아래 3가지로 구분할 수 있습니다.




1. 전역 변수로 head를 선언한다.


2. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형으로 Node의 Point를 사용하는 경우


3. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형 없이, Head Node의 주소를 입력 받는 방법



그럼 예제로 설명드리겠습니다. 이 예제는 single linked list로 구현했고, Insert Node를 하면

가장 앞에 새로운 값이 저장되도록 작성되어 있습니다.



< 사진 출처 = https://wiki.cs.auckland.ac.nz/compsci105ss/index.php/Linked_Lists >



1. 전역 변수로 head를 선언한다.


먼저, 아래 Node_T * head; 를 보면... main함수 외부에 전역 변수로 선언되어 있습니다.

그러므로, 이 코드에 있는 어떠한 함수에서도 바로 head에 접근이 가능합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 1 : use global variable for Head
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNodeAtHead(int value    );
void PrintNode(void);
 
void InsertNodeAtHead(int value    )
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = head;
    
    head = temp;
}
 
void PrintNode(void)
{
    Node_T * temp = head;
    printf("List :");
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        InsertNodeAtHead(x);
    }
    PrintNode();
    printf("Good Bye!");
 
}
 
cs





2. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형으로 Node의 Point를 사용하는 경우



두번째로는... Node_T * head가 main함수 안쪽으로 가서

main함수의 지역변수로 사용되었습니다.


그러므로 다른 함수에서 head를 받기 위해 parameter로 전달을 해야합니다.

그리고 다시 return으로 head를 받아와야 합니다.


Node_T * InsertNodeAtHead(Node_T * head, int value)


head = InsertNodeAtHead(head, x);



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 2 : use local variable for Head
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * InsertNodeAtHead(Node_T * head, int value);
void PrintNode(Node_T *node);
 
Node_T * InsertNodeAtHead(Node_T * head, int value)
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = head;
 
    head = temp;
    return head;
}
 
void PrintNode(Node_T * node)
{
    Node_T * temp = node;
 
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
 
    Node_T * head;  // Head node is local variable
 
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        head = InsertNodeAtHead(head, x);
    }
    PrintNode(head);
    printf("Good Bye!");
 
}
cs


3. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형 없이, Head Node의 주소를 입력 받는 방법


마지막으로... 두번째에서 확인한 파라미터로 head를 전달하고, return으로 head를 다시

받는 형태를 좀더 간략히 하기 위해, 파라미터로 전달시 head의 주소로 전달하여

InsertNodeAtHead()함수에서 바로 head를 접근할 수 있도록 합니다.


void InsertNodeAtHead(Node_T ** head, int value);


// 포인터의 포인터이므로, &head로 주소 연산자를 하나 붙여줍니다.

InsertNodeAtHead(&head, x);



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 3 : use local variable for Head, 
// and don't use parameter for Insert
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
void InsertNodeAtHead(Node_T ** head, int value);
void PrintNode(Node_T *node);
 
void InsertNodeAtHead(Node_T ** head, int value)
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = *head;
 
    *head = temp;
}
 
void PrintNode(Node_T * node)
{
    Node_T * temp = node;
 
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
 
    Node_T * head;// Head node is local variable
 
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        InsertNodeAtHead(&head, x);
    }
    PrintNode(head);
    printf("Good Bye!");
}
 
cs



코드 참고 : <mycodeschool : https://www.youtube.com/channel/UClEEsT7DkdVO_fkrBw0OTrA >



저작자표시 비영리 변경금지
Posted by 고무함지
,

[c 언어] 포인터의 크기 : 이중배열 사용시

공부/- 포인터 2016. 5. 31. 15:08

포인터 사용시 주의해야할 것은 포인터 변수의 크기를 알아 내는 것입니다.

크기를 알아야 자료 복사나, 메모리 할당등을 할 수 있기 때문입니다.


여러가지 예제로 확인해보니, 주의할 점이 보이더군요.


1. 포인터 변수 자체의 크기인 경우


2. 포인터가 가르키는 것이 배열인 경우 그.. 배열의 크기가 됨.


3. 포인터가 가르키는 것이 배열인지, 행 하나인지 주의 할 것



아래 내용으로 어떤 차이들이 있는지 확인해보시기 바랍니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void main(void)
{
    int arr[3][4] = { {1,2},{3,4,5},{6,7,8,9} };
    //0행 : 1, 2, 0, 0
    //1행 : 3, 4, 5, 0
    //2행 : 6, 7, 8, 9
    printf(" %d,", arr[2][1]);   
    // 배열 2행 1열의 값은 (0열 다음값인) -> 7
 
    printf(" %d,", *(*(arr+2)+1) );
    // 배열 2행 1열의 값은 역시 -> 7
 
    printf(" %d,", sizeof(arr));
    // arr은 전체 배열의 크기인 3x4x4byte = 48
 
    printf(" %d,", sizeof(arr+0));
    // 이건 arr과 동일한 결과가 나올 것으로 예상했으나, 명시적으로 0번째 행을 
    // 지칭 하기 위해서 + 0 을 하는 것임. 0번 행의 포인터이므로 .. 포인터의 크기는 4byte
 
    printf(" %d,", sizeof(arr+1));  // 역시 포인터의 크기 -> 4
    printf(" %d,", sizeof(arr+2));  // 포인터의 크기   -> 4
    printf(" %d,", sizeof(*(arr+2))); 
    // 포인터가 가르치는 곳(*연산자)이므로... 행의 크기 4x4byte = 16
 
    printf(" %d,", sizeof(*(arr + 2)+1));  
    // 포인터의 포인터가 가르키는 곳(**)이므로... 열의 하나의 크기 -> 4 byte
 
    printf("Good bye");
    // 결과  7, 7, 48, 4, 4, 4, 16, 4,
}
 
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

[c 언어] 포인터의 free 시 런타임 에러 예제

공부/- 포인터 2016. 5. 31. 13:48



아래 에러가 발생하였다. 무슨 상황일까?


"Invalid address specified to RtlValidateHeap"

( 참고로 프로그램 작성중 debug모드로 실행시 발행하는 메시지이며...)


( exe파일을 직접 실행할 경우... 아래의 메시지 팝업 창이 발생합니다.)

"프로그램이름.exe의 작동이 중지되었습니다."


포인터를 선언하고, malloc을 이용하여 heap 메모리 영역에 동적으로 메모리할당을 할 경우...

그 메모리를 다 쓴 경우 해제를 하여, 메모리의 낭비를 줄여야 한다.


이건 동적 메모리의 장점인데... 다만 메모리 관리를 하지 않으면, 실행하다가 메모리 부족으로

프로그램이 일정 시간이 지나면서 죽어버리는 문제가 발생한다.


바로 문제가 나올 수도 있고, 몇시간 또는 며칠이 될수 도 있다.


여하튼... 나도 간혹 실수하는 부분을 적어본다.


오늘의 내용은... 동적으로 할당한 메모리를 free할 때... 오류가 발생하는 상황을 설명하려 한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void main(void)
{
    int *currArr = NULL;
    int Arr[5] = { 0,1,2,3,4 };
    int index, currSize = 5, newSize = 10;
    currArr = (int*)malloc(sizeof(int)*currSize);
 
#if 0
    currArr = Arr;   // make run time error : "Invalid address specified to RtlValidateHeap"
#else
    strcpy(currArr, Arr); // use string copy instead of address copy
#endif
    
    free(currArr);
    printf("Good ~ ! ");
}
 
cs


위의 내용을 보면, currArr을 동적으로 할당하여 5 x 4byte(int형의 크기) = 20 byte의 크기로 할당하고...

Arr 배열의 주소를 currArr에 넣어줬다. 

그리고 나서... free(currArr)을 할 경우..

다음과 같은 에러가 프로그램이 동작하는 도중에 발생한다. (Runtime Error)


"Invalid address specified to RtlValidateHeap"


이는 아마도... Arr라는 배열까지 free가 되려는 상황 같다.


이를 구분하기 위해 배열만 따로 선언하고, free를 해봤다.


1
2
3
4
5
6
7
8
void main(void)
{
    int *currArr = NULL;
    int Arr[5] = { 0,1,2,3,4 };
    
    free(Arr);
    printf("Good ? ");
}

c


이 경우에 free(Arr)을 하는 순간 동일하게 런타임 에러가 발생했다.


이를 보면 이러한 상황을 피하기 위해서는 포인터에 배열의 주소를 대입하기 보단...

배열의 내용을 복사하기로 하는 것이 좋다.



1
2
3
4
5
6
7
8
9
10
11
12
void main(void)
{
    int *currArr = NULL;
    int Arr[5] = { 0,1,2,3,4 };
    int index, currSize = 5, newSize = 10;
    currArr = (int*)malloc(sizeof(int)*currSize);
 
    strcpy(currArr, Arr); // use string copy instead of address copy
    
    free(currArr);
    printf("Good result");
}
cs


아까 위의 내용에서 안전한 코드만 다시 정리하였다.


이 시간 이후로...좀 고려할 내용으론... 배열과 포인터간 주소 대입을 한다면, malloc하지 않고

배열로 포인터를 초기화하는 방법도 있겠다.

그리고 물론 배열은 free를 하지 않는다고 나는 알고 있다.



1
2
3
4
5
6
7
8
void main(void)
{
    int *currArr = NULL;
    int Arr[5] = { 0,1,2,3,4 };
    currArr = Arr;
    
    printf("Good result");
}
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

티스토리툴바