C programming and Data Structures Overview T. H. Cormen, C. E. Leiserson and R. L. Rivest Introduction to, 3rd Edition, MIT Press, 2009 Sungkyunkwan University Hyunseung Choo choo@skku.edu Copyright 2000-2018 Networking Laboratory
Contents Functions Invocations Function Function Definitions Return statements Function Prototypes Call by value and call by reference Recursions Recursive Call Examples Structures Struct Declaration Structure Tag Compatible Structure Memory Allocation Accessing a Member Pointers Pointer Variable Passing Pointers to Functions Exercise Problem Networking Laboratory 2/78
Functions Networking Laboratory 3/78
Invocations Function (1/3) Function C 프로그램은하나이상의 Function 들로구성 모든 c-program 은반드시한개의 main() Function 을포함 반복되는 codes 의경우 function 으로정의하여필요시마다그 function 을호출하여사용함으로서 simplicity 의향상 Function 의종류 Library functions : System 이제공하는 Predefined-Functions User-defined functions : Programmer 에의해작성된 Functions Function Invocation Function 의호출 : Function_name() 의형식으로사용. Function 의종료 : Function 을 Call 한곳으로제어권의이동 Networking Laboratory 4/78
Invocations Function (2/3) Networking Laboratory 5/78
Invocations Function (3/3) Networking Laboratory 6/78
Function Definitions (1/2) Function 이호출되기전반드시해당 Function 을다음형식으로정의해야한다. Networking Laboratory 7/78
Function Definitions (2/2) Parameter Type List Function 호출시전달되는 arguments 에대응되는순서와 data types 을지정 Function body 내에서 identifier 로사용될수있다 Return type Function 종료될때 return statement에의해전달되는 value 의 type. Default type : integer type으로, 생략시자동 integer로간주 void type : Return Value가없는경우 void로지정 Networking Laboratory 8/78
The Return Statement Function 의실행종료, 호출한곳으로 control 을이전하는 statement 생략시는 function body 끝의 } 를만났을때자동 return 복수개의 return 문사용가능 단, 하나의 Function 에서두개의값을동시에 return 할수없음 Networking Laboratory 9/78
The Return Value Networking Laboratory 10/78
Function Prototypes (1/2) Function 사용을위해호출전에반드시필요한 Function 선언문 prototype 이생략가능한경우 모든조건이 default 인경우생략가능 : return value 의 type 과 argument 의 type 이 integer 인경우생략가능 function 이 main() function 전에정의된경우 선언형식 return-type function_name (parameter type list); Networking Laboratory 11/78
Function Prototypes (2/2) Argument 와 parameter 의 type 이일치하지않는경우 function prototype 에서지정된 type 으로 convert 됨. Networking Laboratory 12/78
Function Definition Order 한개의 file 로작성된 program 의일반적순서 1. #include, #define statements 2. Enumeration types and typedef 3. struct definition 4. Function Prototypes 5. main() Function 6 Function Definitions Networking Laboratory 13/78
main( ) 안에서의 Function Definition Networking Laboratory 14/78
Developing Large Program (1/2) 대규모 Program 의경우, 여러 ~.h 파일과 ~.c 파일로나누어작성할수있다. Team 에의한작업분담이용이해진다. 프로그램이변경될때마다변경된 ~.c 파일만을 compile 함으로서시간절약가능 Networking Laboratory 15/78
Developing Large Program (2/2) Networking Laboratory 16/78
Call by Value and Call by Reference Call-by-Value Function Invocation 이일어나면, argument 의 value 를전달받기위한 parameter 를위해메모리영역이새로생기며 argument 의값이새영역에 copy 된다. Function Invocation 의 parameter 를 identifier 로사용하여그값을 function 내에서변경한경우에도다른 memory 영역을사용함으로써실제 argument 의값은변경되지않는다 Call-by-Reference Function Invocation 이일어나면 argument 의 address 를전달한다. 실제값의 address 를변경하기때문에그값을 function 내에서변경한경우실제 argument 값이변경된다. Networking Laboratory 17/78
Example of Call by Value Networking Laboratory 18/78
Example of Call by Reference Networking Laboratory 19/78
Recursions Networking Laboratory 20/78
Recursive Call 어떤함수가자기자신을호출하는것 Networking Laboratory 21/78
Factorial 을구하는예제 Networking Laboratory 22/78
Array 의평균을구하는예제 Networking Laboratory 23/78
Drawing Patterns on the Screen (1/2) 제곱근을구하는예제 Networking Laboratory 24/78
Drawing Patterns on the Screen (2/2) 역순으로문자를출력하는예제 입력받은문장의문자들을역순으로출력한다. Networking Laboratory 25/78
Structures Networking Laboratory 26/78
Array 와 structure 의차이점 array Array의모든 element는같은 type이여야한다. Index를사용하여각 element를 access한다. structure 다른 type의 element로구성될수있다있다. 각 element는 name을갖는다. Name에의해각 element를 access한다. Networking Laboratory 27/78
Struct Declaration Collection of members(/elements) Networking Laboratory 28/78
Structure Tag 정의되는특정 structure 를지정하기위한 name 한번 structure tag 인 part 가정의되면, 이제 tag 를사용하여같은 structure type 으로선언할수있다. Networking Laboratory 29/78
Structure Tag 와변수동시선언 structure tag 를이용하여선언된변수는같은 structure type Networking Laboratory 30/78
Compatible Structure (1/2) 같은 type 의 structure variable 이면서로 assign 가능 compatible types 의조건 Structure 정의와동시에선언되는모든 variables 같은 type 의 structure 즉같은 tag 에의해선언된모든 variables Networking Laboratory 31/78
Compatible Structure (2/2) compatible type 이아닐경우 =, ==,!= 불가능 Networking Laboratory 32/78
Memory Allocation Structure로선언된데이터 type은각 member들이메모리내에순차적으로할당된다. part1의 base address가 200이고, integer size가 4byte라가정하면, 오른쪽그림과같이메모리가할당됨 Networking Laboratory 33/78
Accessing a Member (1/3) struct member operator. Structure 의각 member 를 access 하기위해. 를사용한다. Networking Laboratory 34/78
Accessing a Member (2/3) member operation Networking Laboratory 35/78
Accessing a Member (3/3) structure pointer Networking Laboratory 36/78
Structures as Argument call-by-value 로 struct 가 copy 되어사용된다. Networking Laboratory 37/78
Struct Pointer 사용 (1/2) call-by-reference 로 struct 의 address 를전달한다. Networking Laboratory 38/78
Struct Pointer 사용 (2/2) Networking Laboratory 39/78
The Use of typedef (1/2) data type 의 name 을재정의하기위해사용 readability 의증가 Networking Laboratory 40/78
The Use of typedef (2/2) typedef 를사용, struct type 을새로운 type 으로선언 Networking Laboratory 41/78
Pointers Networking Laboratory 42/78
Pointer Variable 포인터변수는변수명은같으나변수선언을할때 * 연산자를사용한다. int *a; int 형포인터 포인터변수는타입에상관없이 4 바이트다. Networking Laboratory 43/78
Passing Pointers to Functions (1/4) 포인터를 argument 로하는함수예제 Networking Laboratory 44/78
Passing Pointers to Functions (2/4) 포인터를 argument 로하는함수예제 Networking Laboratory 45/78
Passing Pointers to Functions (3/4) 포인터를 argument 로하는함수예제 Networking Laboratory 46/78
Passing Pointers to Functions (4/4) 포인터를 argument 로하는함수사용시유의점 Networking Laboratory 47/78
Exercise Problem pointer 의주소할당문제 Networking Laboratory 48/78
Approaches pointer 의예제 Networking Laboratory 49/78
Data Structures Overview Sungkyunkwan University Hyunseung Choo choo@skku.edu Copyright 2000-2018 Networking Laboratory
Contents Arrays Arrays Representation of Multidimensional Arrays Lists Singly Linked Lists Doubly Linked Lists Stacks and Queues Stack Abstract Data Type Queue Abstract Data Type Circular Queues Networking Laboratory 51/78
Arrays Networking Laboratory 52/78
Arrays (1/2) An array is a set of pairs, <index, value>, such that each index that is defined has a value associated with it A consecutive set of memory locations in C Logical order is the same as physical order int list[5], *plist[5]; /* arrays start at index 0 in C */ - integers: list[0],..., list[4] - int ptrs: plist[0],..., plist[4] Networking Laboratory 53/78
Arrays (2/2) Variable list[0] list[1] list[2] list[3] list[4] Memory Address base address = a a + sizeof(int) a + 2 sizeof(int) a + 3 sizeof(int) a + 4 sizeof(int) list[i] in C programs, C interprets it as a pointer to an integer whose address is the one in the table above int *list1; pointer variable to an int int list2[5]; five memory locations for holding integers are reserved Networking Laboratory 54/78
Representation of Multidimensional Arrays Internal Representation of Multidimensional Arrays How to state n-dimensional array into 1-dimensional array? How to retrieve arbitrary element in a[upper0][upper1] [uppern-1] the number of elements in the array n-1 P upperi i=0 e.g.) a[10][10][10] 10*10*10 = 1000 (units) Networking Laboratory 55/78
1-dimensional Array Starting-address + offset-value Assume a: starting-address 1-dimensional array a[u0] a[0] : a a[1] : a + 1 : : a[u0-1] : a + (u0-1) &a[i] = α + i Networking Laboratory 56/78
2-dimensional Array 2-dimensional array a[u 0 ][u 1 ] 0 1 u 1-1 0 a a +1 a +(u 1-1) 1 i? u 0-1 j a[i][j] = α + i u 1 + j Networking Laboratory 57/78
Stacks and Queues Networking Laboratory 58/78
Stack Abstract Data Type ADT stack Last-In-First-Out (LIFO) Ordered list, insertions and deletions are made at one end called the top Given stack S = (a 0,, a n-1 ) a 0 : bottom element a n-1 : top element a i : on top of element a i-1 (0<i<n) A top B A top C B A top D C B A top E D C B A top D C B A top Inserting and deleting elements in stack Networking Laboratory 59/78
Implementing a Stack Using a one-dimensional array stack[max_stack_size] #define MAX_STACK_SIZE 100 typedef struct { int key; } element; element stack[max_stack_size]; int top = -1; Structure element consists of only a key field, and we can add fields to or modify to meet the requirements of the application Networking Laboratory 60/78
Push and Pop Push Pop push(&top, item) void push(int *ptop, element item) { if (*ptop >= MAX_STACK_SIZE - 1) { stack_full(); return; } stack[++*ptop] = item; } element pop(int *ptop) { } pop(&top, item) if (*ptop == -1) return stack_empty(); return stack[(*ptop)--]; Networking Laboratory 61/78
Queue Abstract Data Type ADT queue First-In-First-Out (FIFO) Ordered list All insertions are made at one end called rear All deletions are made at the other end called front D rear D rear C rear C C B rear B B B A rear A A A A front front & rear front front front front Inserting and deleting elements in queue Networking Laboratory 62/78
Implementing a Queue A one-dimensional array, and two variables: front and rear #define MAX_QUEUE_SIZE 100 typedef struct { int key; /* other fields */ } element; element queue[max_queue_size]; int rear = -1; int front = -1; Networking Laboratory 63/78
Add and Delete Add to a queue void addq(int *prear, element item) { if (*prear == MAX_QUEUE_SIZE - 1) { queue_full(); return; } queue[++*prear] = item; } Delete from a queue addq(&rear, item) deleteq(&front, rear) element deleteq(int *pfront, int rear) { if (*pfront == rear) return queue_empty(); return queue[++*front]; } In deleteq() rear is used to check for an empty queue Networking Laboratory 64/78
Circular Queues (1/3) More efficient queue representation Regarding the array queue[max_queue_size] as circular Initially front and rear to 0 rather than -1 The front index always points one position counterclockwise from the first element in the queue The rear index points to the current end of the queue Networking Laboratory 65/78
Circular Queues (2/3) Empty queue [2] [3] [2] [3] J2 J3 [1] [4] [1] J1 [4] [0] [5] front = 0 rear = 0 [0] [5] front = 0 rear = 3 Empty and nonempty circular queues Networking Laboratory 66/78
Circular Queues (3/3) Full queue [2] [3] [2] [3] J2 J3 J8 J9 [1] J1 J4 [4] [1] J7 [4] J5 J6 J5 [0] [5] front = 0 rear = 5 [0] [5] front = 4 rear = 3 Full circular queues Networking Laboratory 67/78
Implementing Insertions and Deletions Use modulus operator Circular rotation of the rear *rear = (*rear + 1) % MAX_QUEUE_SIZE Circular rotation of the front *front = (*front + 1) % MAX_QUEUE_SIZE; Networking Laboratory 68/78
Add to a Circular Queue Add an item addq(front, &rear, item) void addq(int front, int *rear, element item) { *rear = (*rear + 1) % MAX_QUEUE_SIZE; if (front == *rear) { queue_full(rear); /* reset rear and print error */ return; } queue[*rear] = item; } rotate rear before we place the item in queue[rear] Networking Laboratory 69/78
Delete from a Circular Queue Delete an item deleteq(&front, rear) element deleteq(int *front, int rear) { element item; if (*front == rear) return queue_empty(); /* queue_empty returns an error key */ *front = (*front + 1) % MAX_QUEUE_SIZE; return queue[*front]; } Networking Laboratory 70/78
Lists Networking Laboratory 71/78
Singly Linked Lists Compose of data part and link part Link part contains address of the next element in a list Non-sequential representations Size of the list is not predefined Dynamic storage allocation and deallocation ptr bat cat sat vat NULL Networking Laboratory 72/78
Insertion of Singly Linked Lists To insert the word mat between cat and sat ptr bat cat sat vat NULL 1) Get a currently unused node (paddr) 2) Set paddr s data to mat mat 3) Set paddr s link to point to the address found in the link of the node cat 4) Set the link of the node cat to point to paddr Networking Laboratory 73/78
Deletion of Singly Linked Lists To delete mat from the lists ptr bat cat mat sat vat NULL 1) Find the element that immediately precedes mat, which is cat 2) Set its link to point to mat s link - No data movement in insert and delete operation Networking Laboratory 74/78
Doubly Linked Lists (1/2) Problems of singly linked lists Move to only one way direction Hard to find the previous node Hard to delete the arbitrary node Doubly linked circular lists Doubly lists + circular lists Allow two links Two way direction Networking Laboratory 75/78
Doubly Linked Lists (2/2) Doubly linked circular lists with head node llink item rlink head node Networking Laboratory 76/78
Insertion of Doubly Linked Lists Insertion into doubly linked circular lists 1. 2. 3. 4. void dinsert(node_ptr node,node_ptr newnode) { /* insert newnode to the right of node */ newnode->llink = node; newnode->rlink = node->rlink; node->rlink->llink = newnode; node->rlink = newnode; } dinsert(node, newnode) time: O(1) node node node 1 4 3 2 1 4 newnode newnode 3 2 newnode Networking Laboratory 77/78
Deletion of Doubly Linked Lists Deletion from a doubly linked circular lists void ddelete(node_ptr node, node_ptr deleted) { /* delete from the doubly linked list */ if (node == deleted) printf( Deletion of head node not permitted.\n ); else { deleted->llink->rlink = deleted->rlink; deleted->rlink->llink = deleted->llink; free(deleted); } } ddelete(node, deleted) time: O(1) node node node deleted deleted Networking Laboratory 78/78