[INA240] Data Structures and Practice

Presentation on theme: "[INA240] Data Structures and Practice"— Presentation transcript:

1 [INA240] Data Structures and Practice
1.5. C Genetic Code (p.17~28) [INA240] Data Structures and Practice Youn-Hee Han

2 Pointers Pointer: A data type whose value is used to refer to ("points to") another value stored elsewhere in the computer memory Pointer-related operators Address operator & Dereferencing operator * int i = 0; // variable int *pi = NULL; // pointer pi = &i; // &i: address of i i = 10; // store 10 to variable i *pi = 12; // store 12 to memory location pointed by pi Pointer variable variable i pi … 0x22ee18 i = 10 0x22ee14 pi = 0x22ee14 0x22ee10

3 Pointers Address Operator: & int date, month; int *p; p = &date;
‘Address of’ 변수 Date의 주소 값을 포인터 변수 p에 할당 변수에 대한 두가지 접근방법: date = 12; 또는 *p = 12; int date, month; int *p; p = &date; 주소 값 변수 200 date 204 month 200 date 204 month 200 12 date 204 month p=&date; *p=12 404 ? p 404 200 p 404 200 p Data Structure

4 p=(int*)malloc(sizeof(int));
Pointers Dynamic Memory Allocation (동적 메모리 할당) int *p; p = (int *)malloc(sizeof(int)); *p = 15; *p는 힙 메모리 (Heap Memory) 변수, p는 스택 메모리 (Stack Memory) 변수 익명 변수 (Anonymous Variable) 주소 값 변수 404 800 p p Address 800 p=(int*)malloc(sizeof(int)); 800 ??? 800 15 ? *p=15; 800 15 Data Structure

5 p=(int*)malloc(sizeof(int)); Operating system will use it
Pointers Dynamic Memory De-allocation (동적 메모리 해제) C 동적변수 할당 p = (int *)malloc(sizeof(int)); 동적변수 해제 free(p); p Address 800 p=(int*)malloc(sizeof(int)); 800 ??? *p=15; 800 15 free(p); 800 Operating system will use it Data Structure

6 Pointers Null Pointer 접근 위반 (Access Violation)
‘현재 아무 것도 가리키지 않고 있다’는 의미 free (p);             p가 가리키는 변수 공간을 반납 p = NULL;      p를 따라가지 않도록 접근 위반 (Access Violation) 변수 p 자체는 정적으로 할당된 변수임 free(p)에 의하여 p가 가리키는 동적 메모리 공간은 운영체제에 반납되지만 포인터 변수 p의 자체 공간은 프로그램이 끝날 때까지 반납이 안됨. 즉, free(p) 이후에도 p 에는 800이라는 주소값이 그대로 존재 운영체제는 800 주소에 해당하는 메모리를 활용하여 다른 변수 값을 저장하기 위하여 사용 가능 p의 값이 여전히 800이라고 해서 해당 포인터를 따라가서 그 값을 건드린다면 큰 문제 # define SAFE_FREE ( a ) { free ( a ) ; a = NULL ; } 주소 값 변수 404 800 p 404 NULL p Data Structure

7 Pointers Dangling Pointer int *p, *q; p = (int *) malloc(sizeof(int));
free (p); p = NULL; *q = 30; Data Structure

8 Pointers Garbage: 반납도 접근도 할 수 없는 공간 int *p; *q;
p = (int *)malloc(sizeof(int)); q = (int *)malloc(sizeof(int)); *p = 5; *q = 20; p = q; Data Structure

9 Structures Structure: collection of related elements, possibly of different types Structure declaration Direct selection operator (.) sam2.x, sam2.y, … For example: SAMPLE sam2; // structure variable sam2.x = 7; sam2.y = 3; sam2.t = 0.0; sam2.u = ‘A’; Data Structure

10 Structures 구조체 선언 및 사용 방법 typedef A B struct car { char Title[12];
int Year; int Price; }; struct car MyCar; typedef struct { } carType carType MyCar; carType MyCar {"RedSportCar", 2005, 2000}; carType CarArray[100]; typedef A B Ex.] typedef int* prtType; prtType p; Data Structure

11 Structures Referencing individual fields
Indirect selection operator (->) (*pointerName).fieldName  pointerName->fieldName For example: SAMPLE sam2; sam2.x = 7; sam2.y = 3; sam2.t = 0.0; sam2.u = ‘A’; SAMPLE *ptr = &sam2; (*ptr).x = 10; ptr->y=11; ptr->t=1.0; pSam->u = ‘B’; 주의점 (*ptr).x와 *ptr.x는 다르다. 연산자 우선순위에 의하여 . (dot) 연산자가 * (Asterisk) 연산자보다 우선 평가 Data Structure

12 self-referential structures
Linear Lists Linear lists Node struct Node { int data; struct Node *next; }; self-referential structures Data Structure

13 Linking Nodes How to make a code to generate the following linked list? 1. Declare nodes struct Node a, b; a.data = 10; b.data = 20; 2. Link nodes a.link = &b; b.link = NULL; a b data (10) link data (20) link a b data (10) link data (20) Link (NULL) Data Structure

14 Non-Linear Lists Non-linear lists 구조체 선언 예 1 구조체 선언 예 2 struct Node {
struct Node *l_link; int data; struct Node *r_link; }; 구조체 선언 예 2 struct Node { int data; struct Node *next[3]; }; Data Structure

15 Generic Code Motivation of Generic Code : we could need linked lists of many types. Linked list of int, char, user-defined types Generic code Write one set of code and apply it to any data type Language support for generic code C++, Java, C#, …: common base class, template C language Because C is strongly typed, operations such as assign and compare must use compatible types or be cast to compatible types. Solution for Genetic: void (generic) pointers function pointers Data Structure

16 Generic Code Void (Generic) Pointer
void *ptr; 선언시에는 가리키는 대상을 명시하지 않음 일반적으로 void *ptr = NULL; 포인터는 그것이 가리키는 변수의 타입이 수시로 바뀜 가리키는 변수의 타입에 따라 읽어와야 할 데이터의 분량이 달라짐. ptr = (float *)malloc(sizeof(float)); 캐스팅 (타입변환 연산자)에 의해 포인터의 타입을 할당 만약 float *Ptr; 로 선언되었다면 (float *)는 없어도 된다 그래도, Code Readability 효과를 기대하기 위해 사용하는 것이 바람직 void* p; int i; p = &i; Data Structure

17 A pointer to void cannot be dereferenced unless it is cast!!!
Void Pointer Void pointers store pointers to any type A pointer to void is a generic pointer that can be used to represent any data type during compilation or run time Normal variable  void pointer void *p = NULL; int i = 7; float f = 23.5; p = &i; p = &f; Accessing value through void pointer printf(“i contains: %d\n”, *((int*)p) ); printf(“f contains: %f\n”, *((float*)p) ); CIY: Program 1-1 A pointer to void cannot be dereferenced unless it is cast!!! Data Structure

18 Generic Code using Void Pointer
Linked list node // Program 1-2 typedef struct node { void *dataPtr; struct node* link; } NODE; Data Structure

19 Generic Code using Void Pointer
Creating node // Program 1-2 (파일명: P1-02.h) typedef struct node { void *dataPtr; struct node* link; } NODE; NODE* createNode (void* itemPtr) { NODE* nodePtr = NULL; nodePtr = (NODE*) malloc (sizeof (NODE)); nodePtr->dataPtr = itemPtr; nodePtr->link = NULL; return nodePtr; } // createNode … itemPtr 단순한 값 할당 Data Structure

20 Generic Code using Void Pointer
Creating node with a value // Program 1-2 #include <stdio.h> #include <stdlib.h> #include "P1-02.h" // Header file int main (void) { int* newData = NULL; int* nodeData = NULL; NODE* node = NULL; newData = (int*)malloc (sizeof (int)); *newData = 7; node = createNode (newData); nodeData = (int*)node->dataPtr; printf ("Data from node: %d\n", *nodeData); return 0; } // main Results: Data from node: 7 To assign a void pointer into a typed pointer, it must be cast!!! Data Structure

21 Create List with Two Linked Nodes
#include <stdio.h> #include <stdlib.h> #include "P1-02.h" // Header file int main (void) { int* newData; int* nodeData; NODE* node; newData = (int*)malloc (sizeof (int)); *newData = 7; node = createNode (newData); newData = (int*)malloc (sizeof (int)); *newData = 75; node->link = createNode (newData); nodeData = (int*)node->dataPtr; printf ("Data from node 1: %d\n", *nodeData); nodeData = (int*)node->link->dataPtr; printf ("Data from node 2: %d\n", *nodeData); return 0; } Structure for two linked nodes (Program 1-4) Data Structure

22 Function Pointers Address of function Function occupy memory
Name of a function = constant to its first byte of memory occupied by the function Data Structure

23 Function Pointers For example: Result
address of main = An address of function can be stored in a function pointer #include <stdio.h> int main() { printf("address of main = %p\n", main); return 0; } Data Structure

24 Function Pointers Declaring function pointers
void (*f1)(void); int (*f2)(int, int); double (*f3)(float); Assigning function pointer f1 = fun; f2 = pun; f3 = sun; Function call using function pointer (*f1)(); // equivalent to fun(); (*f2)(10, 20); // equivalent to pun(10, 20); (*f3)( ); // equivalent to sun( ); Data Structure

25 Generic Code using Function Pointer
Getting larger element (Program 1-5) void* larger (void* dataPtr1, void* dataPtr2, int (*ptrToCmpFun)(void*, void*) ) { if ((*ptrToCmpFun) (dataPtr1, dataPtr2) > 0) return dataPtr1; else return dataPtr2; } // larger P1-05.h Data Structure

26 Generic Code using Function Pointer
Comparing two integers (Program 1-6) #include <stdio.h> #include <stdlib.h> #include “P1-05.h” int compare (void* ptr1, void* ptr2); int main (void) { int i = 7 ; int j = 8 ; int lrg = 0; lrg = *(int*) larger (&i, &j, compare); printf ("Larger value is: %d\n", lrg); return 0; } int compare (void* ptr1, void* ptr2) { if (*(int*)ptr1 >= *(int*)ptr2) return 1; else return -1; } P1-06.c Data Structure

27 Generic Code using Function Pointer
Comparing two floating-point values (Program 1-7) #include <stdio.h> #include <stdlib.h> #include “P1-05.h” int compare (void* ptr1, void* ptr2); int main (void) { float f1 = 73.4 ; float f2 = 81.7 ; float lrg; lrg = *(float*) larger (&f1, &f2, compare); printf ("Larger value is: %5.1f\n", lrg); return 0; } int compare (void* ptr1, void* ptr2) { if (*(float*)ptr1 >= *(float*)ptr2) return 1; else return -1; } P1-07.c Data Structure

28 Generic Code using Function Pointer
Comparing two integers and two floats in a main() function #include <stdio.h> #include <stdlib.h> #include “P1-05.h” int compareInt (void* ptr1, void* ptr2); int compareFloat (void* ptr1, void* ptr2); int main (void) { int i = 7 ; int j = 8 ; int lrgInt = 0; float f1 = 73.4 ; float f2 = 81.7 ; float lrgFloat; lrgInt = *(int*) larger (&i, &j, compareInt); lrgFloat = *(float*) larger (&f1, &f2, compareFloat); printf ("Larger value is: %d\n", lrgInt); printf ("Larger value is: %5.1f\n", lrgFloat); return 0; } P1-08.c Data Structure

29 Generic Code using Function Pointer
Comparing two integers and two floats in a main() function int compareInt (void* ptr1, void* ptr2) { if (*(int*)ptr1 >= *(int*)ptr2) return 1; else return -1; } int compareFloat (void* ptr1, void* ptr2) { if (*(float*)ptr1 >= *(float*)ptr2) P1-08.c (cont.) Data Structure

30 Generic Code using Function Pointer
What if function pointer is not used? #include<stdio.h> int* compareInt (int* ptr1, int* ptr2); float* compareFloat (float* ptr1, float* ptr2); int main (void) { int i = 7 ; int j = 8 ; int lrgInt; float f1 = 73.4f ; float f2 = 81.7f ; float lrgFloat; lrgInt = *(int*) compareInt (&i, &j); lrgFloat = *(float*) compareFloat (&f1, &f2); printf ("Larger int value is: %d\n", lrgInt); printf ("Larger float value is: %5.1f\n", lrgFloat); return 0; } P1-09.c Data Structure

31 Generic Code using Function Pointer
What if function pointer is not used? int* compareInt (int* ptr1, int* ptr2) { if (*ptr1 >= *ptr2) return ptr1; else return ptr2; } float* compareFloat (float* ptr1, float* ptr2) { P1-09.c (Cont.) Data Structure