[INA240] Data Structures and Practice 0. C Genetic Code [INA240] Data Structures and Practice Youn-Hee Han http://icl.kut.ac.kr

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

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

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

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 15 2003 Operating system will use it Data Structure

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Function Pointers For example: Result address of main = 00401290 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

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)(3.141592); // equivalent to sun(3.141592); Data Structure

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

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

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