전산 SMP 11 주차 2015. 12. 08 김범수 bskim45@gmail.com Special thanks to 박기석 (kisuk0521@gmail.com)
기말고사대비총정리 기말고사화이팅
자료구조 많은데이터를예쁘게잘저장해서 쉽고빠르게꺼내쓰려고 데이터가많아지면찾는데도오래걸린다. Example: finding a number from a set of numbers How many comparisons do we need to retrieve 7?
Array
Multi-dimension array
Sorting
왠갑자기 Sorting Array 는자료구조 우리가원하는데이터를 Array 에서빠르게찾으려면? 저장할때잘저장해서꺼내쓸때편해야한다 데이터를효율적으로관리하는방법 데이터를저장하는자료구조 + 데이터를찾는알고리즘
Array Sorting Selection Sort Bubble Sort Insertion Sort
Selection Sort Concept
Selection Sort
Bubble Sort Concept
Bubble Sort Example
Insertion Sort Concept
Insertion Sort Example
Search
Sequential Search 특징 Unsorted 배열에대해서는처음부터쭉봐야하기때문에비효율적이다. Worst Case: O(n)
Binary Search 특징 검색대상배열은 sorted 인상태여야한다. 정렬된데이터에대해서는이진검색이빠르다 매 iteration 에서반틈 (1/2) 을서치후보에서제외시킨다.( 제외된거는볼필요없음 ) O(logn)
Pointer
Pointer 란? 데이터접근에사용되는주소를저장하는타입 포인터도타입이다 int a = 4; char c = a ; int *p = &a; p : 0x10002200 0x10002204 0x10002205 4 a a c 메모리는긴일차원공간으로볼수있고, 각 byte 는자신만의주소를가지고있다.
Call-by-value
Call-by-reference
Pointer 를선언할때타입이필요한이유 int *p; char *q; 어차피크기는 4byte(32 bit) 로다똑같은거아닌가? 컴퓨터가포인터로메모리에접근해데이터를읽어올때! 그포인터타입에따라가져오는 byte 수가달라진다. int * 포인터면여기서부터 4byte 까지읽어서정수로쳐 char * 포인터면여기서부터 1byte 만읽어서문자로쳐
배열포인터 (Pointer to Arrays) *(a + i) a[i]
포인터연산 포인터 p p ± n p + n * (sizeof (one element))
포인터와배열 int a[5]={10, 20, 30, 40, 50}; int *p=&a[2]; printf( %d %d %d %d\n,a[2], *(a+2), p[0], *(p+0)); // 30 출력 printf( %d %d %d %d\n,a[1], *(a+1), p[-1], *(p-1)); // 20 출력 a p 100 104 108 112 116 108 번지 10 20 30 40 50 a[0] a[1] a[2] a[3] a[4] p[-2] p[-1] p[0] p[1] p[2] *(a+0) *(a+1) *(a+2) *(a+3) *(a+4) *(p-2) *(p-1) *(p+0) *(p+1) *(p+2)
2 차원 Array table[2] == *(table+2) table[2][1] == (*(table+2))[1] ==*(table[2]+1) ==*(*(table+2)+1) 헷갈리니다차원배열에서는 Index 를사용하자
문자열과포인터 다시한번! 여러개의문자 + \0 이들어있는배열 배열의이름은첫번째 element 의주소와같다. str[0] H e l l o W o r l d! \0 str &str[0] 그래서 scanf 로 %s 받을때 & 안붙인다!
Scopes
Storage Class ( 변수의존재기간과접근범위 ) 지역변수정적변수전역변수 register 변수 지정자 auto static extern register 저장장소스택정적데이터영역정적데이터영역레지스터 선언위치함수내부함수내부 / 외부함수내부 / 외부함수내부 유효범위함수내부함수내부 / 외부프로그램전체함수내부 생존기간함수종료시프로그램종료시프로그램종료시함수종료시 초기값초기화안됨 0 으로초기화 0 으로초기화초기화안됨 29
Dynamic Memory Allocation 동적할당
왜쓰나요? 배열의크기를입력받아그크기만큼의배열을만들고싶을때 int main(void) { int size; scanf( %d, &size); } int array[size]; Compile Error! 선언은항상맨위에와야한다. 선언후에배열이할당되어야하는데 이럴때는어떻게? 프로그램실행중에메모리를할당해데이터를저장할공간을생성하는방법
Accessing Dynamic Memory
Dynamic Memory Allocation <stdlib.h> void *malloc (size_t size); void *calloc (size_t count, size_t size); void *realloc (void* ptr, size_t newsize); void free (void* ptr);
동적할당으로 2 차원배열만들기 포인터배열 int **table; table = (int **)calloc (3, sizeof(int *)); table[0] = (int *)calloc(4, sizeof(int));
포인터의부적절한사용으로인한주요부작용들 Unreachable Memory ( 이공간을가리키는포인터가존재하지않는다 ) Dangling Pointer ( 어딘가가리키고있기는하지만, 그위치에뭐가있는지알수없다.) Buffer Overflow ( 할당되어있는양이상으로메모리를다루게되는경우 ) Segmentation Fault ( 잘못된주소접근 ) 35
Tidy Up 동적으로할당된메모리는반드시시스템에반환해야함! 그래야다른프로그램이메모리공간을활용할수있다. ( 메모리 leak) 실행전에미리할당 vs 실행중에동적으로할당하고반환 공간이필요한만큼만쓰기때문에효율적! 메모리공간의크기는정해져있다. 얼마나큰공간이필요한지알수없을때 적당히크게? 공간이부족하거나, 공간이낭비되거나
Structure
The Type Definition (typedef) A type definition, typedef, gives a name to a data type by creating a new type that can then be used anywhere a type is permitted. 프로그래머는길게쓰는것을싫어한다 typedef int INGETER;
Enumerate Type 항목혹은선택지, 일종의상수항목을만들때사용 각항목들에대해 identifier 로써하나의정수 (enumeration constant) 가할당됨 상황 ) 메뉴를만들고숫자하나입력받아서 switch 문으로각기다른함수를실행해야한다. 그냥숫자 0, 1, 2, 3 으로나누면나중에헷갈리고불편함
Initializing Enumerated Constants enum MONTHS {JAN, FEB, MAR, APR}; identifier 자동배정 0 1 2 3 enum MONTHS {JAN = 1, FEB, MAR, APR}; enum COLORS {RED, ROSE=0, CRIMSON=0, BLUE, AQUA=1};
Operations on Enumerated Types enum COLORS color1, color2; color1 = BLUE; color2 = color1; if (color1 == color2) if (color1 == BLUE) switch (color1) { case BLUE:
Initializing Enumerated Constants enum months {JAN, FEB, MAR, APR}; identifier 자동배정 0 1 2 3 enum months {JAN = 1, FEB, MAR, APR}; enum color {RED, ROSE = 0, CRIMSON = 0, BLUE, AQUA = 1};
Structure Type 관련되는 element 들의집합. 어떤타입의변수라도올수있다. 단, 함수는구조체의 element 로안된다. 오직변수만가능
Accessing Structure Elements (*pointername).fieldname pointername - >fieldname.
String
문자열의선언 char str[15] = Good Day ; 할당한용량을모두사용할필요는없습니다. char month[] = January ; 배열크기가문자열의길이에맞춰자동으로설정 char *pstr = Good Day ; char str[9] = { G, o, o, d,, D, a, y, \0 };
String Copy? char str1[6] = Hello ; char str2[6]; str2 = str1; //?
String Input/Output Functions formatted input/output functions scanf/fscanf printf/fprintf special set of string-only functions get string (gets/fgets) put string ( puts/fputs ).
Difference btw. Input functions gets/fgets gets does not include newline ( \n ), fgets does. gets does not allow to specify a maximum size for str (which can lead to buffer overflows). Scanf/gets scanf 는단어단위로 (space), gets 는줄단위로 (newline)
Difference btw. Output functions puts appends a newline( \n) at the end automatically fputs does not write additional characters
FLUSH 스트림버퍼를비우는역할을한다. Scanf 등입력받는함수사용시 The string conversion code(s) skips whitespace. Test) int a; char b; scanf( %d, &a); scanf( %c,&b); printf( %d %c\n, a, b); fflush(); #define FLUSH while(getchar!= \n )
String Manipulation Functions #include <string.h> String Length and String Copy String Compare and String Concatenate Character in String Search for a Substring and Search for Character in Set String Span and String Token String to Number
List
What to learn
Linked List 각각의 Element 가다음 Element 의위치를저장하여이어진데이터스트럭쳐 연속으로쭉이어졌다면왜배열 (Array) 를안쓸까?? Array 의장점? 단점? Linked List 의장점? 단점? List Linked List Space Complexity O(n) At O(1) O(n) Insert O(n) O(1) Remove O(n) O(1)
Linked List 한개만가리킬수도있고, 여러개를가리킬수도있고
General Linear Lists 가장일반적인직렬리스트 Retrieve Insert Change Delete Traversing Building
Insert a Node to Empty List
Insert a Node at Beginning
Insert a Node in Middle
Insert a Node at End
Insert a Node - Code
Delete First Node
Delete - General Case Pre, Cur 두개가같이움직이는거주의!!
Delete a Node - Code
Search Linear List // 리스트 plist 가있다. struct Node *pwalker = plist; while(pwalker) { If(pWalker->data == 찾는데이터 ) return 1; pwalker = pwalker->next; } return 0;
Linear List Traversal
Print Linear List
Average Linear List
Stack Last in First out (LIFO) 의데이터스트럭쳐 Insertion과 deletion이항상한쪽끝 (Top) 에서만일어난다. Push : 새로운것을넣는작업 Pop : 젤위에서하나빼는작업
Stack Implementations
Stack Data Structure
Stack _ Push
Stack _ Pop
Queue First in First out(fifo) 의데이터스트럭쳐 Insertion은한쪽끝, Deletion은다른한쪽끝에서만일어난다. : Enqueue : 큐에새로운걸넣는작업 (rear) Dequeue : 큐에서하나를제거하는작업 (front)
Queue Implementations
Queue Data Structure
Enqueue
Dequeue
한학기배운것총정리 책에사이사이박스에있는예제코드들전부다한번씩쭉보고이해하기. 코드가있는거는충분히시험에코드짜는문제로나올수있다! Data Structure 에서는다양한 Implementation 이있기때문에무작정외우기보다는어떻게구현하는지 Concept 들을꼭기억 DS 부분은코드반드시봐야합니다. 빨간색글씨로된거기억하기