Basic Data Structures, Make, GDB
Contents Data Structures Linked List Tree Hash Make 사용법 디버거 (gdb) 사용법 2/17
Reference The C Programming language, Brian W. Kernighan, Dennis M. Ritchie, Prentice-Hall Teach yourself C, Peter Aitken, Simon & Schuster Programming with GNU Software, Mike Loukides, O REILLY Fundamentals of Data Structures in C, Ellis Horowitz, Computer Science Press 3/17
Linked List 같은형태의데이터타입을연결한데이터타입 Single linked list Double linked list Operations next_node(); Previous_node(); add_tail(); add_head(); remove_head(); remove_tail(); insert_at(); remove_at(); 4/17
Single Linked List 한방향으로만연결이되어잇음 Stack, Queue 등다른 data structure 의기본이됨 struct Node { int value; struct Node *next; ; 1 2 3 5/17
Single Linked List struct Node *head = NULL; struct Node *tail = NULL; struct Node *alloc_node( int value ) { struct Node *node = ( struct Node * ) malloc( sizeof( struct Node ) ); node->value = value; node->next = NULL; head tail void add_head( int value ) { struct Node *node = alloc_node( value ) if( head == NULL ) { // tail is NULL too. head = tail = node; else { node->next = head; head = node; 2 1 6/17
Single Linked List void add_tail( int value ) { struct Node *node = alloc_node( value ) if( tail == NULL ) { // head is NULL too. head = tail = node; else { tail->next = node; tail = node; head tail 2 1 3 7/17
Single Linked List int remove_head( int *result ) { if( head == NULL ) { // tail is NULL too. *result = 0; return -1; head tail struct Node *temp = head; head = head->next; *result = temp->value; free( temp ); return 0; 2 1 3 Access temp after free() temp free() 후 temp 의값 (*temp) 를시도하면안된다. 8/17
Double Linked List 양방향으로연결이되어잇음 prev, next 를통해자유롭게 list 안을 traverse 할수잇음. struct Node { int value; ; struct Node *prev; struct Node *next; 1 2 3 9/17
Double Linked List struct Node *alloc_node( int value ) { struct Node *node = ( struct Node * ) malloc( sizeof( struct Node ) ); node->value = value; node->prev = NULL; node->next = NULL; head tail void add_head( int value ) { struct Node *node = alloc_node( value ) if( tail == NULL ) { // head is NULL too. head = tail = node; else { node->next = head; head->prev = node; head = node; 2 1 Implement add_tail 10/17
Double Linked List int remove_tail( int *result ) { if( tail == NULL ) { // head is NULL too. *result = 0; return -1; else { struct Node *temp = tail; tail = tail->prev; tail->next = NULL; head tail *result = temp->value; free( temp ); return 0; 2 1 3 temp 11/17
Tree Tree: Acyclic Graph Root 로부터아래방향으로내려가며엔트리들을접근할수잇다. 일반적으로 hierarchical 구조나 search 등을할때많이사용된다. struct BinaryNode { int value; ; struct Node *left; struct Node *right; struct BinaryNodeWithParent { int value; struct Node *parent; struct Node *left; struct Node *right ; struct NodeWithManyChildren { int value; struct Node *children[10]; ; struct Node *root = NULL; 12/17
Tree node_root->left = node1; root node_root->right = node2; node1->left = node3; 1 2 node2->left = node4; node2->right = node5; 3 4 5 node5->left = node 6; node_root->right->right->left == node6 6 13/17
Tree Root 의 left child : node 1 Root 의 right child : node 2 Node 4 의 parent : node 2 Node 4 의 sibling : node 5 Node 3 과 Node 4 는 sibling? No Leaf nodes : node 3, 4, 6 Degree of root : 2 Height : 4 root 1 2 3 4 5 6 14/17
Tree Traverse and Search Tree Traverse Depth-First Recursive call 로구현가능 VLR : root, 1, 3, 2, 4, 5, 6 LVR : 3, 1, root, 4, 2, 6, 5 LRV : 3, 1, 4, 6, 5, 2, root Breadth-First Search Buffer(queue) 가필요 Depth-First Search (DFS) Breadth-First Search (BFS) root 1 2 3 4 5 6 15/17
Depth-First Traverse void find_leaves_dfs( struct Node *node ) { if( node->left == NULL && node->right == NULL ) { printf( This is leaf : %d, node->value ); if( node->left!= NULL ) { find_leaves( node->left ); if( node->right!= NULL ) { find_leaves( node->right ); visit left right root 1 2 3 4 5 6 16/17
Binary Tree Definition Node 의값보다작은값을가지는 node 는왼쪽에, 큰값을가지는 node 는오른쪽에잇는 tree 장점 쉽게구현이가능하다. O(Log 2 (n)) 에원하는값을찾을수잇다. 단점 한쪽으로쏠릴 (skewed) 수잇고이경우값을찾는데오래걸릴수잇다. 17/17
Hash Hash function 값을이용하여키를생성하는함수 Hash( 값 ) = key Hash( x ) = x % 7; Hash( test ) = (116 + 101 + 115 + 116) % 13 = 6 최대한서로다른값을가지도록만드는것이중요 주로 bit operation 이나 arithmetic 연산으로구성 Tree + Hash, Array + Hash 등의조합을이용 Hash table (static hash) Table 의 index 를 hash 로결정 index of test = hash( test ) = 6 index of cs230 = hash( cs230 ) = 12 Table 의각 index 에는 hash bucket 이잇고, 그 bucket 안에실제값들이들어잇음. 18/17
Hash conflicts 같은 hash 값을가지는서로다른값이존재할수잇음 hash( jinsoo ) == hash( thread ) 해결책 : Bucket 을크게한다, Conflict block 끼리 linked list 로잆는다 (chaining), 비어잇는옆 bucket 에넣는다 (linear insert), Chaining 4 5 6 7 8 9 10 11 12 Linear insertion 4 5 6 7 8 9 10 11 12 cs230 jinsoo test cs230 jinsoo thread test thread 19/17
Hash Implementation struct hash_bucket { int count; // Word count char *string; // Value struct hash_bucket *next; // Conflict chain ; struct hash_bucket *hash_table[13] = { NULL ; struct hash_bucket *insert_into_hash ( char *key ) { int hashvalue = hash( key ); struct hash_bucket *entry = ( struct hash_bucket *)malloc( sizeof( struct hash_bucket ) ); entry->string = strdup( key ); // Initialize entry struct hash_bucket *bucket = hash_table[ hashvalue ]; if( bucket == NULL ) { hash_table[ hashvalue ] = entry; else { entry->next = bucket; bucket = entry; return entry; 20/17
struct hash_bucket *find_hash ( char *key ) { int hashvalue = hash( key ); struct hash_bucket *bucket = hash_table[ hashvalue ]; while( bucket!= NULL ) { // Chain 을포함하여값을확인한다. if( strcmp( bucket->string, key ) == 0 ) { return bucket; bucket = bucket->next; return NULL; 21/17
Make (1/2) 다중파일컴파일 1) main 함수를포함하지않는.c 파일을컴파일하여.o 파일생성 Ex) gcc c add.c sub.c 2) main 함수를포함하는.c 파일과 1) 에서생성한.o 파일을함께컴파일 ex) gcc o calculator calc.c add.o sub.o Make 란? 다수의파일로이루어진프로젝트의컴파일을쉽게하기위한도구 작업디렉토리의 Makefile 에정의된작업을수행 사용법 : make 22/17
Make (2/2) Makefile 예제 # 매크로선언 : 매크로이름 = 내용 OBJS = addmult.o subdiv.o #target name: dependency #depencency 는아래명령을수행하기전미리수행되어야하는내용 all: EX_A EX_B rm -fr *.o #EX_A 라는 target 을수행하기위해서는 OBJS 에정의된 addmult.o 와 subdiv.o 가미리컴파일되어있어야함 #dependency 리스트에.o 파일이지정되어있으면같은이름의.c 파일을 c 옵션으로자동컴파일함 EX_A : a_test.c $(OBJS) $(CC) $^ -o $@ # $( 매크로이름 ) 으로매크로치환가능, $@ : 타켓이름, $^ 는 dependency list 를나타냄 EX_B : b_test.c $(OBJS) $(CC) $^ -o $@ clean: rm -fr EX_A rm -fr EX_B rm -fr *.o 23/17
GDB (1/5) gdb 시작하기 gcc g 옵션으로컴파일한다 gdb 프로그램명 [core-dump] 로디버거시작 -d source_directory : 소스파일이잇는디렉토리지정 -x file : 디버거시작후바로실행할명령어를지정한파일 -batch : -x로지정된파일을수행하고디버거종료 프롬프트에서명령어입력 help 명령어 : 해당명령어에대한도움말보기 quit : 디버거종료 24/17
GDB (2/5) 파일수행하기 : run [arguments] [pipe or redirections] arguments 는 shell 에서입력하는것과동일 arguments 가지정되지않으면바로젂에사용한 argument 사용 에러없이종료시 : Program exited with code n 을출력 비정상적인종료 (ex. segmentation fault) 시 gdb 로제어권이넘어옴 본격적인디버깅시작 ~ 프로그램수행도중 Ctrl+C 를이용하여중단가능 25/17
GDB (3/5) list [line1,line2] [routine-name] : no args : 정지시점위의 source code 10 줄을본다 반복해서 list를치면이어지는 10줄씩계속보여준다 list 를이용하여위방향으로 10줄씩볼수잇다. line1, line2 : 두줄사이의 source code 를보여준다 routine-name : 특정함수의 code를보여준다 backtrace, where 정지시점에서활성화되어잇는모든프로시저의리스트를보여줌 up/down으로프레임갂이동할수잇다. (gdb)backtrace #0 0x22c8 in march_to_infinity() at badref.c:16 #1 0x2324 in setup() at badref.c:25 #2 0x2340 in main() at badref.c:30 (gdb) 26/17
GDB (4/5) whatis [ 변수명 ] : 변수의 type 을알수잇다. print 연산 연산 := literal 상수 [ 변수명 ] [ 함수호출문법 ] { 연산 operator { 연산 변수값혹은함수의리턴값을알수잇다. $n : 히스토리, 이후참고가능 set variable 변수명 = 값 (gdb) whatis p type = int * (gdb) print p $1 = (int *)0xf8000000 (gdb) print *p $2 = Cannot access memory at address 0xf8000000 (gdb) print $1-1 $3 = (int *)0xf7fffffc (gdb) print *$3 $5 = 0 27/17
GDB (5/5) 정지점설정 (break 명령 ) 프로그램실행중디버깅을위해정지시키고 gdb 명령을실행할수잇다. 다수의정지점을설정할수잇다. 관찰점설정 break line-number break function-name break line-or-function if condition watch condition 예 ) watch testsize>10000 //testsize 변수값이 10000 보다크면정지 condition 이없으면변수값이바뀔때정지 실행재개 continue : 다음정지점까지실행 step : 한줄씩실행 next : 한줄씩실행중함수를만나면함수젂체를실행 28/17
연습문제 1. 300 을입력받기젂까지의입력으로 binary tree 를구성하고, 300 을입력받은이후에는입력한숫자가 binary tree 안에존재하는지확인하는프로그램을작성하여라. 입력값은 integer 이다. 2. 17 개의 bucket 을가지는 hash 를이용하여입력한단어의출현횟수를세는프로그램을작성하여라. 입력값은 string 이다. Conflict 는 linear insertion 을이용하여라. Bucket 이모두찼을경우 hash table 의내용을출력하고종료하여라. strlen(), strdup(), strcmp() 29/17