[INA240] Data Structures and Practice

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

1 [INA240] Data Structures and Practice
0. C Genetic Code [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 = 10; // store 10 to memory location pointed by pi pointer variable i pi … 0x22ee18 i = 10 0x22ee14 pi = 0x22ee14 0x22ee10

3 Pointers Address Operator: Ampersand, & int date, month; int *p;
‘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 Ex.] typedef int* prtType; prtType p;
Structures 구조체 선언 및 사용 방법 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 Linked list nodes are self-referential structures
Linear Lists Linear lists Node struct Node { int data; struct Node *next; }; Linked list nodes are 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 Linear lists Non-linear lists Node Node struct Node {
int data; struct Node *next; }; Non-linear lists Node struct Node { int data; struct Node *next[3]; }; Data Structure

15 Generic Code Motivation: 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 and 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 효과를 기대하기 위해 사용하는 것이 바람직 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) ); A pointer to void cannot be dereferenced unless it is cast!!! Data Structure

18 Generic Code using Void Pointer
Link list node // filename: P1-02.h typedef struct node { void *dataPtr; struct node* link; } NODE; Data Structure

19 Generic Code using Void Pointer
Allocating node // filename: 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 // filename: main.c #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 While we can store an address in a void pointer without knowing its type, the reverse is not true!!! Data Structure

21 Create List with Two Linked Nodes
Structure for two linked nodes Data Structure

22 Create List with Two Linked Nodes
Structure for 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; } Data Structure

23 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

24 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

25 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

26 Generic Code using Function Pointer
Getting larger element void* larger (void* dataPtr1, void* dataPtr2, int (*ptrToCmpFun)(void*, void*) ) { if ((*ptrToCmpFun) (dataPtr1, dataPtr2) > 0) return dataPtr1; else return dataPtr2; } // larger Data Structure

27 Generic Code using Function Pointer
Comparing two integers 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; } // main int compare (void* ptr1, void* ptr2) { if (*(int*)ptr1 >= *(int*)ptr2) return 1; else return -1; } // compare Data Structure

28 Generic Code using Function Pointer
Comparing two integers 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; } // main int compare (void* ptr1, void* ptr2) { if (*(float*)ptr1 >= *(float*)ptr2) return 1; else return -1; } // compare Data Structure