[INA240] Data Structures and Practice

Slides:



Advertisements
Similar presentations
YES C 제 1 장 C 언어의 개요 1/34 제 1 장 C 언어의 개요 문봉근. YES C 제 1 장 C 언어의 개요 2/34 제 1 장 C 언어의 개요 1.1 프로그램과 C 언어의 특징 1.2 C 언어의 프로그램 구성 1.3 비주얼 C++ 통합 환경 들어가기.
Advertisements

1 구조체 윤 홍 란 컴퓨터 프로그래밍 2 구조체 정의  구조체란 ? o 서로 다른 형의 변수들을 하나로 묶어주는 mechanism. (cf. 배열 : 같은 형의 변수들을 하나로 묶어주는 mechanism) o 예 : 카드의.
Vision System Lab, Sang-Hun Han
C++ Tutorial 1 서강대학교 데이터베이스 연구실.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express Slide 1 (of 27)
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
Internet Computing KUT Youn-Hee Han
2014 ITA 8월 강의 C Programming -1주차- C언어 기초 정대진 ( )
쉽게 풀어쓴 C언어 Express 제13장 구조체 C Express Slide 1 (of 25)
C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011
C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2005
제 2 장 배열과 스트링.
시스템 생명 주기(System Life Cycle)(1/2)
제 6 장 데이터 타입 6.1 데이터 타입 및 타입 정보 6.2 타입의 용도 6.3 타입 구성자 6.4 사례 연구
Internet Computing KUT Youn-Hee Han
C 11장. 포인터의 활용 #include <stdio.h> int main(void) { int num;
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
Chapter 03 배열, 구조체, 포인터.
시스템 생명 주기(System Life Cycle)(1/2)
자료 구조: Chapter 3 (2)구조체, 포인터
누구나 즐기는 C언어 콘서트 제4장 수식과 연산자.
개정판 누구나 즐기는 C언어 콘서트 제9장 포인터 출처: pixabay.
CHAP 3:배열, 구조체, 포인터.
제 4 장 L i s t.
head data link data link data link NULL a b c
자료 구조: Chapter 3 (2)구조체, 포인터
Chapter 9 – 구조형과 리스트 처리 Outline 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
10장 메모리 관리.
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
[INA240] Data Structures and Practice
3장. 포인터, 배열, 구조체 포인터, 배열, 구조체 학습목표 기본적 데이터 타입
Internet Computing KUT Youn-Hee Han
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
Derived Types-- Enumerated, Structure and Union
adopted from KNK C Programming : A Modern Approach
Chapter 2 Lexical Elements, Operators, and the C System
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
* 프로그램을 간단히 하기 위해 malloc 성공체크는 안 함
제 3 장 연산자 (Operators).
Introduction to Programming Language
컴퓨터 프로그래밍 기초 - 4th : 수식과 연산자 -
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
4장 자료형.
8주차: Strings, Arrays and Pointers
Chapter 4 변수 및 바인딩.
제 3장 데이터형과 연산자 Hello!! C 언어 강성호 김학배 최우영.
Operating System Multiple Access Chatting Program using Multithread
Signature, Strong Typing
Signature, Strong Typing
CHAP 1:자료구조와 알고리즘.
Signature, Strong Typing
토론을 위한 질문 배열의 이름에는 무엇이 저장되는가? C언어에서 배열 추상데이터의 store는 어떻게 구현 되는가?
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
Summary of Pointers and Arrays
Numerical Analysis Programming using NRs
C.
C++ 언어의 특징
Pointers summary.
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

[INA240] Data Structures and Practice 1.5. C Genetic Code (p.17~28) [INA240] Data Structures and Practice Youn-Hee Han http://link.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 = 12; // store 12 to memory location pointed by pi Pointer variable variable i pi … 0x22ee18 i = 10 0x22ee14 pi = 0x22ee14 0x22ee10

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

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

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

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

self-referential structures Linear Lists Linear lists Node struct Node { int data; struct Node *next; }; 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 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

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

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

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

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

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

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

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

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 (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

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

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

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

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

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

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