C Language

Step by step

My diary

...

Search
breakinformation. Powered by Blogger.

2019년 1월 17일 목요일

array heap

  1월 17, 2019    

"arrayheap.h"
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
#ifndef _ARRAY_HEAP_
#define _ARRAY_HEAP_
 
struct Heap_Element_Type {
 
    int key;
    //char data;
};
 
struct Array_Heap_Type {
 
    int Maximum_Element_Count;
    int Current_Element_Count;
    struct Heap_Element_Type* Pointer_Element;
};
 
typedef struct Heap_Element_Type    Heap_Node;
typedef struct Array_Heap_Type        Array_Maximum_Heap, Array_Minimum_Heap;
 
Array_Maximum_Heap* Create_Array_Maximum_Heap(int Maximum_Element_Count);
void Delete_Array_Maximum_Heap(Array_Maximum_Heap* Pointer_Array_Heap);
void Insert_Maximum_Heap_Array_Heap(Array_Maximum_Heap* Pointer_Array_Heap, Heap_Node element);
Heap_Node* Delete_Maximum_Heap_Array_Heap(Array_Maximum_Heap* Pointer_Array_Heap);
 
#endif // !_ARRAY_HEAP_
 
#ifndef _COMMON_TREE_DEFAULT_
#define _COMMON_TREE_DEFAULT_
 
#define TRUE    1
#define FALSE    0
 
#endif // !_COMMON_TREE_DEFAULT_
 
cs
"arrayheap.c"
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
99
100
101
102
103
104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arrayheap.h"
 
Array_Maximum_Heap* Create_Array_Maximum_Heap(int Maximum_Element_Count) {
 
    if (Maximum_Element_Count <= 0) {
 
        printf("Error! The count must be greater then zero. Create_Array_Maximum_Heap()\n");
        return NULL;
    }
 
    Array_Maximum_Heap* Pointer_Return = (Array_Maximum_Heap*)malloc(1 * sizeof(Array_Maximum_Heap));
    if ((Array_Maximum_Heap*)Pointer_Return == NULL) {
 
        printf("Error! Dynamic memory allocation(1). Create_Array_Maximum_Heap()\n");
        return NULL;
    }
 
    Pointer_Return->Maximum_Element_Count = Maximum_Element_Count;
    Pointer_Return->Current_Element_Count = 0;
    (struct Heap_Element_Type*)Pointer_Return->Pointer_Element = (struct Heap_Element_Type*)malloc((Maximum_Element_Count + 1) * sizeof(struct Heap_Element_Type));
    if ((struct Heap_Element_Type*)Pointer_Return->Pointer_Element == NULL) {
 
        printf("Error! Dynamic memory allocation(2). Create_Array_Maximum_Heap()\n");
        free((Array_Maximum_Heap*)Pointer_Return);
        return NULL;
    }
    (void*)memset((struct Heap_Element_Type*)Pointer_Return->Pointer_Element, 0, (Maximum_Element_Count + 1) * sizeof(struct Heap_Element_Type));
 
    return (Array_Maximum_Heap*)Pointer_Return;
}
 
void Insert_Maximum_Heap_Array_Heap(Array_Maximum_Heap* Pointer_Heap, Heap_Node element) {
 
    if ((Array_Maximum_Heap*)Pointer_Heap == NULL) {
 
        printf("Error! The heap is null. Insert_Maximum_Heap_Array_Heap()\n");
        return;
    }
    else if (Pointer_Heap->Maximum_Element_Count == Pointer_Heap->Current_Element_Count) {
 
        printf("Error! The heap is full. [%d], Insert_Maximum_Heap_Array_Heap()\n", Pointer_Heap->Maximum_Element_Count);
        return;
    }
 
    Pointer_Heap->Current_Element_Count++;
    int index = 0;
    for (index = Pointer_Heap->Current_Element_Count; index != 1 && element.key > (*(Pointer_Heap->Pointer_Element + (index / 2))).key; index /= 2) {
 
        (*(Pointer_Heap->Pointer_Element + index)) = (*(Pointer_Heap->Pointer_Element + (index / 2)));
    }
    (*(Pointer_Heap->Pointer_Element + index)) = element;
 
    return;
}
 
Heap_Node* Delete_Maximum_Heap_Array_Heap(Array_Maximum_Heap* Pointer_Heap) {
 
    if ((Array_Maximum_Heap*)Pointer_Heap == NULL && Pointer_Heap->Current_Element_Count <= 0) return NULL;
 
    Heap_Node* Pointer_Return = (Heap_Node*)malloc(1 * sizeof(Heap_Node));
    if ((Heap_Node*)Pointer_Return == NULL) {
 
        printf("Error! Dynamic memory allocation. Delete_Maximum_Heap_Array_Heap()\n");
        return NULL;
    }
 
    *(Pointer_Return + 0) = *(Pointer_Heap->Pointer_Element + 1);
 
    int index = Pointer_Heap->Current_Element_Count;
    Heap_Node* Pointer_Temporary = Pointer_Heap->Pointer_Element + index;
    Pointer_Heap->Current_Element_Count--;
 
    int parent = 1, child = 2;
    for (index; child <= Pointer_Heap->Current_Element_Count; child *= 2) {
 
        if (child <= Pointer_Heap->Current_Element_Count && (*(Pointer_Heap->Pointer_Element + child)).key < (*(Pointer_Heap->Pointer_Element + child + 1)).key) {
 
            child++;
        }
        if (Pointer_Temporary->key >= (*(Pointer_Heap->Pointer_Element + child)).key) break;
 
        *(Pointer_Heap->Pointer_Element + parent) = *(Pointer_Heap->Pointer_Element + child);
        parent = child;
    } // end-of-for
 
    *(Pointer_Heap->Pointer_Element + parent) = *Pointer_Temporary;
    return (Heap_Node*)Pointer_Return;
}
 
void Delete_Array_Maximum_Heap(Array_Maximum_Heap* Pointer_Heap) {
 
    if ((struct Heap_Element_Type*)Pointer_Heap->Pointer_Element != NULL) {
 
        free((struct Heap_Element_Type*)Pointer_Heap->Pointer_Element);
    }
    if ((Array_Maximum_Heap*)Pointer_Heap != NULL) {
 
        free((Array_Maximum_Heap*)Pointer_Heap);
    }
    return;
}
cs
"main.c"
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
#include <stdio.h>
#include <stdlib.h>
#include "arrayheap.h"
 
void Display_Array_Heap(Array_Maximum_Heap* Pointer_Heap);
 
int main(int argc, char** argv) {
 
    int Maximum_Heap_Size = 20;
    Array_Maximum_Heap* Pointer_Heap = (Array_Maximum_Heap*)Create_Array_Maximum_Heap(Maximum_Heap_Size);
    if ((Array_Maximum_Heap*)Pointer_Heap == NULL) return -1;
 
    Heap_Node element[5] = { 0, };
    element[0].key = 10;
    element[1].key = 40;
    element[2].key = 30;
    element[3].key = 20;
    element[4].key = 50;
 
    Insert_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap, element[0]);
    Insert_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap, element[1]);
    Insert_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap, element[2]);
    Insert_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap, element[3]);
    Insert_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap, element[4]);
 
    Display_Array_Heap((Array_Maximum_Heap*)Pointer_Heap);
 
    Heap_Node* Pointer_Node = Delete_Maximum_Heap_Array_Heap((Array_Maximum_Heap*)Pointer_Heap);
    if ((Heap_Node*)Pointer_Node != NULL) {
 
        printf("Delete_Maximum_Heap_Array_Heap()-[%d]\n", Pointer_Node->key);
        free((Heap_Node*)Pointer_Node);
    }
 
    Display_Array_Heap((Array_Maximum_Heap*)Pointer_Heap);
 
    Delete_Array_Maximum_Heap((Array_Maximum_Heap*)Pointer_Heap);
 
    return 0;
}
 
void Display_Array_Heap(Array_Maximum_Heap* Pointer_Heap) {
 
    if ((Array_Maximum_Heap*)Pointer_Heap == NULL) return;
    int index = 0;
    for (index = 1; index <= Pointer_Heap->Current_Element_Count; index++) {
 
        printf("[%d], %d\n", index, (*(Pointer_Heap->Pointer_Element + index)).key);
    }
    return;
}
cs

  No Comments

0 개의 댓글:

댓글 쓰기

피드 구독하기: 댓글 (Atom)