Linked list _Gamma
"linked list.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 _LINKED_LIST_ #define _LINKED_LIST_ struct List_Node_Type { int data; struct List_Node_Type* Pointer_Link; }; struct Linked_List_Type { int Current_Element_Count; struct List_Node_Type Header_Node; }; struct Linked_List_Type* Create_Linked_List(void); int Add_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position, struct List_Node_Type element); int Remove_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position); struct List_Node_Type* Get_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position); void Clear_Linked_List(struct Linked_List_Type* Pointer_List); int Get_Linked_List_Length(struct Linked_List_Type* Pointer_List); void Delete_Linked_List(struct Linked_List_Type* Pointer_List); int Delete_Linked_List_Beta(struct Linked_List_Type* Pointer_List); #endif // !_LINKED_LIST_ #ifndef _COMMON_LIST_DEFINITION_ #define _COMMON_LIST_DEFINITION_ #define TRUE 1 #define FALSE 0 #endif // !_COMMON_LIST_DEFINITION_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #ifndef _OPTION_ #define _OPTION_ #define ABSOLUTE_VALUE(value) (value < 0) ? -(value) : (value) #define SWAP(current, next) {int temporary = current; current = next; next = temporary;} int Swapping_Of_List_Element(struct Linked_List_Type* Pointer_List, const int First_Target, const int Second_Target); int Swapping_Of_Non_Adjacent_List_Element(struct Linked_List_Type* Pointer_List, const int First_Target, const int Second_Target); int Swapping_Of_Adjacent_List_Element(struct Linked_List_Type* Pointer_List, const int Target_Index); int Reverse_Linked_List(struct Linked_List_Type* Pointer_List); int Concat_Linked_List(struct Linked_List_Type* Pointer_Current_List, struct Linked_List_Type* Pointer_Next_List); int Divide_Linked_List(struct Linked_List_Type* Pointer_List, struct Linked_List_Type* Pointer_New_List, int position); #endif // !_OPTION_ | cs |
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include "linked list.h" struct Linked_List_Type* Create_Linked_List(void) { struct Linked_List_Type* Pointer_Return = NULL; Pointer_Return = (struct Linked_List_Type*) malloc(1 * sizeof(struct Linked_List_Type)); if (!(struct Linked_List_Type*)Pointer_Return) { printf("Error! The dynamic memory allocation was failed. Create_Linked_List()\n"); return NULL; } (void*)memset((struct Linked_List_Type*)Pointer_Return, 0, 1 * sizeof(struct Linked_List_Type)); return (struct Linked_List_Type*)Pointer_Return; } int Add_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position, struct List_Node_Type element) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The list was null. Add_Linked_List_Element()\n"); return FALSE; } if (!(position >= 0 && position <= Pointer_List->Current_Element_Count)) { printf("Error! The list position exceeded tolerance. Index number : [%d] Add_Linked_List_Element()\n", position); return FALSE; } struct List_Node_Type* Pointer_New_Node = NULL; Pointer_New_Node = (struct List_Node_Type*) malloc(1 * sizeof(struct List_Node_Type)); if (!(struct List_Node_Type*)Pointer_New_Node) { printf("Error! The dynamic memory allocation was failed. Add_Linked_List_Element()\n"); return FALSE; } *Pointer_New_Node = *(struct List_Node_Type*) &element; Pointer_New_Node->Pointer_Link = NULL; struct List_Node_Type* Pointer_Previous_Node = NULL; Pointer_Previous_Node = (struct List_Node_Type*) &Pointer_List->Header_Node; int index = 0; for (index = 0; index < position; index++) { Pointer_Previous_Node = (struct List_Node_Type*)Pointer_Previous_Node->Pointer_Link; } Pointer_New_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Previous_Node->Pointer_Link; Pointer_Previous_Node->Pointer_Link = (struct List_Node_Type*)Pointer_New_Node; Pointer_List->Current_Element_Count++; return TRUE; } int Remove_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The list was null. Remove_Linked_List_Element()\n"); return FALSE; } if (!(position >= 0 && position < Get_Linked_List_Length((struct Linked_List_Type*)Pointer_List))) { printf("Error! The list position exceeded tolerance. Index number : [%d] Remove_Linked_List_Element()\n", position); return FALSE; } struct List_Node_Type* Pointer_Node = NULL; Pointer_Node = (struct List_Node_Type*) &Pointer_List->Header_Node; int index = 0; for (index = 0; index < position; index++) { Pointer_Node = (struct List_Node_Type*)Pointer_Node->Pointer_Link; } struct List_Node_Type* Pointer_Delete_Node = NULL; Pointer_Delete_Node = (struct List_Node_Type*) Pointer_Node->Pointer_Link; Pointer_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Delete_Node->Pointer_Link; free((struct List_Node_Type*)Pointer_Delete_Node); Pointer_List->Current_Element_Count--; return TRUE; } struct List_Node_Type* Get_Linked_List_Element(struct Linked_List_Type* Pointer_List, int position) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The list was null. Get_Linked_List_Element()\n"); return NULL; } if (!(position >= 0 && position < Pointer_List->Current_Element_Count)) { printf("Error! The list exceeded tolerance. Get_Linked_List_Element()\n"); return NULL; } struct List_Node_Type* Pointer_Node = NULL; Pointer_Node = (struct List_Node_Type*) &Pointer_List->Header_Node; int index = 0; for (index = 0; index <= position; index++) { Pointer_Node = (struct List_Node_Type*)Pointer_Node->Pointer_Link; } struct List_Node_Type* Pointer_Return = (struct List_Node_Type*)Pointer_Node; return (struct List_Node_Type*)Pointer_Return; } int Delete_Linked_List_Beta(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*) Pointer_List) { printf("Error! The list waw null. Delete_Linked_List_Beta()\n"); return FALSE; } struct List_Node_Type* Pointer_Node = NULL; Pointer_Node = (struct List_Node_Type*) &Pointer_List->Header_Node; int loop = 0; for (loop = Pointer_List->Current_Element_Count; loop; loop--) { struct List_Node_Type* Pointer_Delete_Node = NULL; Pointer_Delete_Node = (struct List_Node_Type*)Pointer_Node->Pointer_Link; Pointer_Node->Pointer_Link = (struct List_Node_Type*) Pointer_Delete_Node->Pointer_Link; free((struct List_Node_Type*)Pointer_Delete_Node); } Pointer_List->Current_Element_Count = loop; free((struct Linked_List_Type*)Pointer_List); return TRUE; } void Delete_Linked_List(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The list was null. Delete_Linked_List()\n"); return; } Clear_Linked_List((struct Linked_List_Type*)Pointer_List); free((struct Likned_List_Type*)Pointer_List); return; } void Clear_Linked_List(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*)Pointer_List) return; if (!(Pointer_List->Current_Element_Count > 0)) return; while (Pointer_List->Current_Element_Count) { Remove_Linked_List_Element((struct Linked_List_Type*)Pointer_List, 0); } return; } int Get_Linked_List_Length(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*)Pointer_List) return 0; return (int)Pointer_List->Current_Element_Count; } int Is_Empty(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*)Pointer_List) return FALSE; if (!(Pointer_List->Current_Element_Count == 0)) return TRUE; return FALSE; } | cs |
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 | #include <stdio.h> #include <stdlib.h> #include "linked list.h" #include "option.h" int Divide_Linked_List(struct Linked_List_Type* Pointer_List, struct Linked_List_Type* Pointer_New_List, int position) { if (!((struct Linked_List_Type*)Pointer_List && (struct Linked_List_Type*) Pointer_New_List)) { printf("Error! The linked list was empty. Divide_Linked_List()\n"); return FALSE; } if (Get_Linked_List_Length((struct Linked_List_Type*)Pointer_New_List)) { printf("Error! The node is in the new list. Divide_Linked_List()\n"); return FALSE; } else if (!(position >= 0 && position <= Get_Linked_List_Length((struct Linked_List_Type*)Pointer_List))) { printf("Error! The list index out of tolerance. Divide_Linked_List()\n"); return FALSE; } struct List_Node_Type* Pointer_Previous_Node_Of_Target = (struct List_Node_Type*) &Pointer_List->Header_Node; int Search_Target_Index = 0; for (Search_Target_Index = 0; Search_Target_Index < position; Search_Target_Index++) { Pointer_Previous_Node_Of_Target = (struct List_Node_Type*) Pointer_Previous_Node_Of_Target->Pointer_Link; } struct List_Node_Type* Pointer_Current_Node_Of_Target = (struct List_Node_Type*) Pointer_Previous_Node_Of_Target->Pointer_Link; Pointer_Previous_Node_Of_Target->Pointer_Link = NULL; struct List_Node_Type* Pointer_New_Node_Of_Target = (struct List_Node_Type*) &Pointer_New_List->Header_Node; Pointer_New_Node_Of_Target->Pointer_Link = (struct List_Node_Type*)Pointer_Current_Node_Of_Target; Pointer_New_List->Current_Element_Count += Pointer_List->Current_Element_Count - position; Pointer_List->Current_Element_Count -= Pointer_New_List->Current_Element_Count; return TRUE; } int Concat_Linked_List(struct Linked_List_Type* Pointer_Current_List, struct Linked_List_Type* Pointer_Next_List) { if (!((struct Linked_List_Type*)Pointer_Current_List && (struct Linked_List_Type*)Pointer_Next_List)) { printf("Error! The linked list was empty. Concat_Linked_List()\n"); return FALSE; } struct List_Node_Type* Pointer_Last_Node_Of_Current_List = (struct List_Node_Type*) &Pointer_Current_List->Header_Node; int To_Last_Node = 0; for (To_Last_Node = Get_Linked_List_Length((struct Linked_List_Type*)Pointer_Current_List); To_Last_Node; To_Last_Node--) { Pointer_Last_Node_Of_Current_List = (struct List_Node_Type*) Pointer_Last_Node_Of_Current_List->Pointer_Link; } struct List_Node_Type* Pointer_Header_Node_Of_Next_List = (struct List_Node_Type*) &Pointer_Next_List->Header_Node; Pointer_Last_Node_Of_Current_List->Pointer_Link = (struct List_Node_Type*) Pointer_Header_Node_Of_Next_List->Pointer_Link; Pointer_Current_List->Current_Element_Count += Pointer_Next_List->Current_Element_Count; free((struct Linked_List_Type*)Pointer_Next_List); Pointer_Next_List = NULL; return TRUE; } int Reverse_Linked_List(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The linked list was empty. Reverse_Linked_List()\n"); return FALSE; } struct List_Node_Type* Pointer_Next_Node = (struct List_Node_Type*)Pointer_List->Header_Node.Pointer_Link; struct List_Node_Type* Pointer_Current_Node = NULL; int loop = 0; for (loop = Get_Linked_List_Length((struct Linked_List_Type*)Pointer_List); loop; loop--) { struct List_Node_Type* Pointer_Previous_Node = (struct List_Node_Type*)Pointer_Current_Node; Pointer_Current_Node = (struct List_Node_Type*)Pointer_Next_Node; Pointer_Next_Node = (struct List_Node_Type*)Pointer_Next_Node->Pointer_Link; Pointer_Current_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Previous_Node; } Pointer_List->Header_Node.Pointer_Link = (struct List_Node_Type*)Pointer_Current_Node; return TRUE; } int Swapping_Of_List_Element(struct Linked_List_Type* Pointer_List, const int First_Target, const int Second_Target) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The linked list was empty. Linked_List_Swapping()\n"); return FALSE; } if (!(First_Target != Second_Target && First_Target >= 0 && Second_Target >= 0 && Pointer_List->Current_Element_Count >= First_Target && Pointer_List->Current_Element_Count >= Second_Target)) { printf("Error! The list index out of tolerance. Linked_List_Swapping()\n"); return FALSE; } int First_Index = First_Target, Second_Index = Second_Target; if (First_Index > Second_Index) { SWAP(First_Index, Second_Index); } int calculate = ABSOLUTE_VALUE(First_Index - Second_Index); if (calculate == 1) { Swapping_Of_Adjacent_List_Element((struct Linked_List_Type*)Pointer_List, First_Index); return TRUE; } else { Swapping_Of_Non_Adjacent_List_Element((struct Linked_List_Type*)Pointer_List, First_Index, Second_Index); return TRUE; } } int Swapping_Of_Non_Adjacent_List_Element(struct Linked_List_Type* Pointer_List, const int First_Target, const int Second_Target) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The linked list was empty. Non_Adjacent_Linked_List_Swapping()\n"); return FALSE; } if (!(First_Target != Second_Target && First_Target >= 0 && Second_Target >= 0 && Pointer_List->Current_Element_Count >= First_Target && Pointer_List->Current_Element_Count >= Second_Target)) { printf("Error! The list index out of tolerance. Non_Adjacent_Linked_List_Swapping()\n"); return FALSE; } struct List_Node_Type* Pointer_Previous_Node_Of_First_Target = (struct List_Node_Type*) &Pointer_List->Header_Node; int Search_Index = 0; for (Search_Index = 0; Search_Index < First_Target; Search_Index++) { Pointer_Previous_Node_Of_First_Target = (struct List_Node_Type*)Pointer_Previous_Node_Of_First_Target->Pointer_Link; } struct List_Node_Type* Pointer_Current_Node_Of_First_Target = (struct List_Node_Type*)Pointer_Previous_Node_Of_First_Target->Pointer_Link; struct List_Node_Type* Pointer_Next_Node_Of_First_Target = (struct List_Node_Type*)Pointer_Current_Node_Of_First_Target->Pointer_Link; struct List_Node_Type* Pointer_Previous_Node_Of_Second_Target = (struct List_Node_Type*)Pointer_Next_Node_Of_First_Target; int Remaining_Number = ABSOLUTE_VALUE(First_Target - Second_Target); for (Search_Index = 0; Search_Index < Remaining_Number - 1 - 1; Search_Index++) { Pointer_Previous_Node_Of_Second_Target = (struct List_Node_Type*)Pointer_Previous_Node_Of_Second_Target->Pointer_Link; } struct List_Node_Type* Pointer_Node_Of_Second_Target = (struct List_Node_Type*) Pointer_Previous_Node_Of_Second_Target->Pointer_Link; // swap Pointer_Previous_Node_Of_First_Target->Pointer_Link = (struct List_Node_Type*)Pointer_Node_Of_Second_Target; Pointer_Current_Node_Of_First_Target->Pointer_Link = (struct List_Node_Type*)Pointer_Node_Of_Second_Target->Pointer_Link; Pointer_Previous_Node_Of_Second_Target->Pointer_Link = (struct List_Node_Type*)Pointer_Current_Node_Of_First_Target; Pointer_Node_Of_Second_Target->Pointer_Link = (struct List_Node_Type*)Pointer_Next_Node_Of_First_Target; return TRUE; } int Swapping_Of_Adjacent_List_Element(struct Linked_List_Type* Pointer_List, const int Target_Index) { if (!(struct Linked_List_Type*)Pointer_List) { printf("Error! The linked list was empty. Adjacent_Linked_List_Swapping()\n"); return FALSE; } if (Target_Index < 0 || Pointer_List->Current_Element_Count < Target_Index) { printf("Error! The list index out of tolerance. Adjacent_Linked_List_Swapping()\n"); return FALSE; } struct List_Node_Type* Pointer_Previous_Node = (struct List_Node_Type*) &Pointer_List->Header_Node; int Search_Index = 0; for (Search_Index = 0; Search_Index < Target_Index; Search_Index++) { Pointer_Previous_Node = (struct List_Node_Type*)Pointer_Previous_Node->Pointer_Link; } struct List_Node_Type* Pointer_Current_Node = (struct List_Node_Type*) Pointer_Previous_Node->Pointer_Link; struct List_Node_Type* Pointer_Next_Node = (struct List_Node_Type*)Pointer_Current_Node->Pointer_Link; // swap Pointer_Previous_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Next_Node; Pointer_Current_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Next_Node->Pointer_Link; Pointer_Next_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Current_Node; return TRUE; } | cs |
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 | #include <stdio.h> #include <stdlib.h> #include "linked list.h" #include "option.h" void Display_Linked_List(struct Linked_List_Type* Pointer_List); int main(int argc, char** argv) { typedef struct Linked_List_Type Linked_List; typedef struct List_Node_Type List_Node; Linked_List* Pointer_List = (Linked_List*)Create_Linked_List(); if (!(Linked_List*)Pointer_List) return -1; List_Node node; int loop = 0, increase = 1; for (loop = 0; loop < 10; loop++) { node.data = increase++; Add_Linked_List_Element((Linked_List*)Pointer_List, loop, node); } Reverse_Linked_List((Linked_List*)Pointer_List); Swapping_Of_List_Element((Linked_List*)Pointer_List, 5, 1); Remove_Linked_List_Element((Linked_List*)Pointer_List, 0); Display_Linked_List((Linked_List*)Pointer_List); Linked_List* Pointer_Next_List = (Linked_List*)Create_Linked_List(); if (!(Linked_List*)Pointer_Next_List) return -2; int decrease = 50; for (loop = 0; loop < 10; loop++) { node.data = decrease--; Add_Linked_List_Element((Linked_List*)Pointer_Next_List, loop, node); } Concat_Linked_List((Linked_List*)Pointer_List, (Linked_List*)Pointer_Next_List); Display_Linked_List((Linked_List*)Pointer_List); Linked_List* Pointer_New_List = (Linked_List*)Create_Linked_List(); Divide_Linked_List((Linked_List*)Pointer_List, (Linked_List*)Pointer_New_List, 9); Display_Linked_List((Linked_List*)Pointer_List); Display_Linked_List((Linked_List*)Pointer_New_List); Delete_Linked_List_Beta((Linked_List*)Pointer_List); Delete_Linked_List_Beta((Linked_List*)Pointer_New_List); system("pause"); return 0; } void Display_Linked_List(struct Linked_List_Type* Pointer_List) { if (!(struct Linked_List_Type*) Pointer_List) { printf("Error! The list was null. Display_Linked_List()\n"); return; } printf("Current element count : %d\n", Pointer_List->Current_Element_Count); int index = 0; for (index = 0; index < Pointer_List->Current_Element_Count; index++) { printf("[%d], %d\n", index, Get_Linked_List_Element((struct Linked_List_Type*)Pointer_List, index)->data); } return; } | cs |
0 개의 댓글:
댓글 쓰기