01_List

Size: px
Start display at page:

Download "01_List"

Transcription

1 List Data Structures and Algorithms

2 목차 추상자료형 (ADT) 배열을이용한리스트의구현 연결리스트의개념적이해 연결리스트의 ADT 구현 원형연결리스트 이중연결리스트 Data Structures and Algorithms 2

3 추상자료형 Abstract Data Type Data Structures and Algorithms 3

4 추상자료형 (ADT) 의이해 추상자료형이란? 자료형에적용가능한연산또는기능의명세서 예 카드의삽입 카드의추출 ( 카드를빼냄 ) 동전의삽입 동전의추출 ( 동전을빼냄 ) 지폐의삽입 지폐의추출 ( 지폐를빼냄 ) Data Structures and Algorithms 4

5 지갑을의미하는구조체 Wallet 의정의 자료형과관련이있는연산을함께정의해야완전한자료형 typedef struct int coin; int bill; Wallet; // 동전의수 // 지폐의수 자료형 Wallet 의정의 + 자료형 Wallet 의연산의정의 int TakeOutMoney(Wallet * pw, int coin, int bill); void PutMoney(Wallet * pw, int coin, int bill); // 돈꺼내는연산 // 돈넣는연산 Data Structures and Algorithms 5

6 ADT 와자료구조학습순서 자료구조의 ADT를정의한다. ADT를근거로자료구조를활용하는 main 함수를정의 ADT를근거로자료구조를구현 올바른 ADT 의정의 자료구조의내부구현이감춰지도록정의 자료구조를쉽게이해하려면자료구조를활용하는 main 함수를먼저작성 Data Structures and Algorithms 6

7 연습 2 차원좌표계의한점의 ADT 를정의해보자 사용가능한연산은각 x, y 좌표의 +, - 계산으로한정함 typedef struct int x; int y; point; point add(point, point); // 좌표계의두점의합 point sub(point, point); // 좌표계의두점의차 Data Structures and Algorithms 7

8 배열을이용한리스트의구현 Data Structures and Algorithms 8

9 리스트구분및특징 구분 순차리스트 : 배열을기반으로구현된리스트 연결리스트 : 메모리의동적할당을기반으로구현된리스트 특징 저장형태 : 데이터를나란히 ( 하나의열로 ) 저장 저장특성 : 중복이되는데이터의저장을허용 Data Structures and Algorithms 9

10 리스트자료구조의 ADT 리스트의초기화 typedef int LData; 데이터저장 저장된데이터의탐색및탐색초기화 Data Structures and Algorithms 10

11 리스트자료구조의 ADT 다음데이터의참조 ( 반환 ) 을목적으로호출 바로이전에참조 ( 반환 ) 이이뤄진데이터의삭제 현재저장되어있는데이터의수를반환 Data Structures and Algorithms 11

12 리스트의 ADT 를기반으로한 main 함수 실행을위해필요한파일들 ArrayList.h 리스트자료구조의헤더파일 ArrayList.c 리스트자료구조의소스파일 ListMain.c 리스트관련 main 함수가담긴소스파일 Data Structures and Algorithms 12

13 리스트의초기화와데이터저장과정 리스트의초기화 int main(void) List list; // 리스트의생성.... ListInit(&list); // 리스트의초기화.... 초기화된리스트에데이터저장 int main(void).... LInsert(&list, 11); LInsert(&list, 22); LInsert(&list, 33);.... // 리스트에 11을저장 // 리스트에 22를저장 // 리스트에 33을저장 Data Structures and Algorithms 13

14 리스트의노드순회과정 LFirst: 리스트순회의시작 int main(void).... if( LFirst(&list, &data) ) // 첫데이터변수 data에저장 printf("%d ", data); while( LNext(&list, &data) ) // 다음데이터변수 data에저장 printf("%d ", data);.... 데이터참조일련의과정 LFirst LNext LNext LNext LNext.... Data Structures and Algorithms 14

15 리스트의노드삭제 LRemove 함수는연이은호출을허용하지않음! int main(void).... if( LFirst(&list, &data) ) if(data == 22) LRemove(&list); // LFirst 함수를통해참조한데이터삭제! while( LNext(&list, &data) ).... if(data == 22) LRemove(&list); // LNext 함수를통해참조한데이터삭제! Data Structures and Algorithms 15

16 배열기반리스트의헤더파일정의 1 리스트를배열기반으로구현하기위한선언을포함 #ifndef ARRAY_LIST_H #define ARRAY_LIST_H #define TRUE 1 #define FALSE 0. // 참 매크로정의 // 거짓 매크로정의 /*** ArrayList 의정의시작 ****/ #define LIST_LEN 100 typedef int LData; // 저장할대상의자료형을변경을위한 typedef 선언 typedef struct ArrayList LData arr[list_len]; int numofdata; int curposition; ArrayList; // 배열기반리스트를의미하는구조체 // 리스트의저장소배열 // 저장된데이터의수 // 현재참조데이터의위치 Data Structures and Algorithms 16

17 배열기반리스트의헤더파일정의 2 배열기반리스트 ADT 의함수들 /*** ArrayList 와관련된연산들 ****/ typedef ArrayList List; // 리스트의변경을용이하게하기위한 typedef 선언 void ListInit(List * plist); void LInsert(List * plist, LData data); // 초기화 // 데이터저장 int LFirst(List * plist, LData * pdata); // 첫데이터참조 int LNext(List * plist, LData * pdata); // 두번째이후데이터참조 LData LRemove(List * plist); int LCount(List * plist); // 참조한데이터삭제 // 저장된데이터의수반환 #endif Data Structures and Algorithms 17

18 배열기반리스트의초기화 초기화대상은구조체변수의멤버이기때문에구조체의정의를기반으로함수를작성 void ListInit(List * plist) (plist->numofdata) = 0; (plist->curposition) = -1; // 데이터 0개가리스트에저장됨 // -1: 참조하지않았음 Data Structures and Algorithms 18

19 배열기반리스트의삽입 배열에데이터저장 void LInsert(List * plist, LData data) if(plist->numofdata > LIST_LEN) // 더이상저장할공간이없다면 printf(" 저장이불가능합니다.\n"); return; plist->arr[plist->numofdata] = data; // 데이터저장 (plist->numofdata)++; // 저장된데이터수증가 Data Structures and Algorithms 19

20 배열기반리스트탐색 int LFirst(List * plist, LData * pdata) // 초기화, 첫데이터참조 if(plist->numofdata == 0) // 저장된데이터가하나도없다면 return FALSE; (plist->curposition) = 0; *pdata = plist->arr[0]; return TRUE; // 참조위치초기화 ; 첫데이터참조를의미 // pdata가가리키는공간에데이터저장 int LNext(List * plist, LData * pdata) // 다음데이터참조 // 더이상참조할데이터가없다면 if(plist->curposition >= (plist->numofdata)-1) return FALSE; (plist->curposition)++; *pdata = plist->arr[plist->curposition]; return TRUE; 데이터반환은매개변수로 함수의반환은연산성공여부 Data Structures and Algorithms 20

21 배열기반리스트의삭제 삭제기본모델 Data Structures and Algorithms 21

22 배열기반리스트의삭제 삭제된데이터는리턴값으로전달 LData LRemove(List * plist) int rpos = plist->curposition; int num = plist->numofdata; int i; LData rdata = plist->arr[rpos]; // 삭제할데이터의인덱스값참조 // 삭제할데이터를임시저장 for(i=rpos; i<num-1; i++) plist->arr[i] = plist->arr[i+1]; (plist->numofdata)--; (plist->curposition)--; return rdata; // 데이터의수감소 // 참조위치하나되돌림 // 삭제된데이터의반환 Data Structures and Algorithms 22

23 리스트에구조체변수저장하기 1 : Point.h Point.h: 리스트에저장할 Point 구조체변수의헤더 typedef struct _point int xpos; int ypos; Point; // Point 변수의 xpos, ypos 값설정 void SetPointPos(Point * ppos, int xpos, int ypos); // Point 변수의 xpos, ypos 정보출력 void ShowPointPos(Point * ppos); // 두 Point 변수의비교 int PointComp(Point * pos1, Point * pos2); Data Structures and Algorithms 23

24 리스트에구조체변수저장하기 2 : Point.c void SetPointPos(Point * ppos, int xpos, int ypos) ppos->xpos = xpos; ppos->ypos = ypos; void ShowPointPos(Point * ppos) printf("[%d, %d] \n", ppos->xpos, ppos->ypos); int PointComp(Point * pos1, Point * pos2) if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos) return 0; else if(pos1->xpos == pos2->xpos) return 1; else if(pos1->ypos == pos2->ypos) return 2; else return -1; Data Structures and Algorithms 24

25 리스트에구조체변수저장하기 3 ArrayList.h 배열 구조체 실행을위한파일구성 Point.h, Point.c ArrayList.h, ArrayList.c PointListMain.c 구조체 Point를위한파일배열기반리스트구조체 Point의변수저장 Data Structures and Algorithms 25

26 PointListMain.c : 초기화및저장 int main(void) List list; Point comppos; Point * ppos; ListInit(&list); /*** 4 개의데이터저장 ***/ ppos = (Point*)malloc(sizeof(Point)); SetPointPos(ppos, 2, 1); LInsert(&list, ppos); ppos = (Point*)malloc(sizeof(Point)); SetPointPos(ppos, 2, 2); LInsert(&list, ppos); Data Structures and Algorithms 26

27 PointListMain.c : 참조및조회 int main(void) /*** 저장된데이터의출력 ***/ printf(" 현재데이터의수 : %d \n", LCount(&list)); if(lfirst(&list, &ppos)) ShowPointPos(ppos); while(lnext(&list, &ppos)) ShowPointPos(ppos); printf("\n"); Data Structures and Algorithms 27

28 PointListMain.c : 삭제 int main(void) /*** xpos 가 2 인모든데이터삭제 ***/ comppos.xpos=2; comppos.ypos=0; if(lfirst(&list, &ppos)) if(pointcomp(ppos, &comppos)==1) ppos=lremove(&list); free(ppos); while(lnext(&list, &ppos)) if(pointcomp(ppos, &comppos)==1) ppos=lremove(&list); free(ppos); Data Structures and Algorithms 28

29 배열기반리스트의장점과단점 배열기반리스트의단점 배열길이는초기에결정되며, 변경불가능 삭제과정에서데이터이동 ( 복사 ) 가매우빈번함 배열기반리스트의장점 쉬운데이터참조 : 인덱스값으로어디든한번에참조가능 Data Structures and Algorithms 29

30 연결리스트의개념적이해 Data Structures and Algorithms 30

31 Linked 의의미 typedef struct _node int data; // 데이터를담을공간 struct _node * next; // 연결의도구! Node; Data Structures and Algorithms 31

32 LinkedRead.c: 초기화 typedef struct _node int data; struct _node * next; Node; head, tail, cur 이연결리스트의핵심! head 와 tail 은연결을추가및유지하기위한것 cur 은참조및조회를위한것 int main(void) Node * head = NULL; Node * tail = NULL; Node * cur = NULL; Node * newnode = NULL; int readdata;.... Data Structures and Algorithms 32

33 LinkedRead.c: 삽입 1 while(1) printf(" 자연수입력 : "); scanf("%d", &readdata); if(readdata < 1) break; // 노드의추가과정 newnode = (Node*)malloc(sizeof(Node)); newnode->data = readdata; newnode->next = NULL; if(head == NULL) head = newnode; else tail->next = newnode; tail = newnode; Data Structures and Algorithms 33

34 LinkedRead.c: 삽입 2 while(1) printf(" 자연수입력 : "); scanf("%d", &readdata); if(readdata < 1) break; // 노드의추가과정 newnode = (Node*)malloc(sizeof(Node)); newnode->data = readdata; newnode->next = NULL; if(head == NULL) head = newnode; else tail->next = newnode; tail = newnode; Data Structures and Algorithms 34

35 LinkedRead.c: 데이터순회 if(head == NULL) printf(" 저장된자연수가존재하지않습니다. \n"); else cur = head; printf("%d ", cur->data); while(cur->next!= NULL) cur = cur->next; printf("%d ", cur->data); Data Structures and Algorithms 35

36 LinkedRead.c: 데이터삭제 if(head == NULL) return 0; else Node * delnode = head; Node * delnextnode = head->next; printf("%d 을삭제 \n", head->data); free(delnode); while(delnextnode!= NULL) delnode = delnextnode; delnextnode = delnextnode->next; printf("%d 을삭제 \n", delnode->data); free(delnode); Data Structures and Algorithms 36

37 연결리스트의 ADT 구현 Data Structures and Algorithms 37

38 정렬기능추가된연결리스트의 ADT 리스트자료구조의 ADT 리스트의초기화 typedef int LData; 리스트자료구조의 ADT 다음데이터의참조 ( 반환 ) 을목적으로호출 데이터저장 바로이전에참조 ( 반환 ) 이이뤄진데이터의삭제 저장된데이터의탐색및탐색초기화 현재저장되어있는데이터의수를반환 Data Structures and Algorithms 10 Data Structures and Algorithms 11 함수포인터가사용됨 Data Structures and Algorithms 38

39 새로운노드의추가위치 새노드를연결리스트의머리에추가 장점 : 포인터변수 tail 이불필요 단점 : 저장된순서를유지하지않음 새노드를연결리스트의꼬리에추가 장점 : 저장된순서가유지 단점 : 포인터변수 tail 이필요 Data Structures and Algorithms 39

40 SetSortRule 함수선언 void SetSortRule ( List * plist, int (*comp)(ldata d1, LData d2) ); 반환형이 int이고, int (*comp)(ldata d1, LData d2) LData형인자를두개전달받는, int (*comp)(ldata d1, LData d2) 함수의주소값을전달해라! int (*comp)(ldata d1, LData d2) 인자로전달이가능한함수의예 int WhoIsPrecede(LData d1, LData d2) // typedef int LData; if(d1 < d2) return 0; // d1이정렬순서상앞선다. else return 1; // d2가정렬순서상앞서거나같다. Data Structures and Algorithms 40

41 정렬의기준을결정하는함수에대한약속! 약속에근거한함수정의의예 int WhoIsPrecede(LData d1, LData d2) if(d1 < d2) return 0; // d1 이정렬순서상앞선다. else return 1; // d2 가정렬순서상앞서거나같다. 함수호출예 int cr = WhoIsPrecede(D1, D2); Data Structures and Algorithms 41

42 우리가구현할더미노드기반연결리스트 머리에새노드를추가하되더미노드없는경우 첫번째노드와두번째이후의노드추가및삭제방식이다를수있음 머리에새노드를추가하되더미노드있는경우 노드의추가및삭제방식이항상일정 LinkedRead.c 와문제 04-2 의답안인 DLinkedRead.c 를비교 Data Structures and Algorithms 42

43 정렬기능추가된연결리스트의구조체 노드의구조체표현 typedef struct _node // typedef int LData; LData data; // 필요한변수들은모두구조체로묶어야함 struct _node * next; Node; 연결리스트의구조체표현 typedef struct _linkedlist Node * head; // 더미노드를가리키는멤버 Node * cur; // 참조및삭제를돕는멤버 Node * before; // 삭제를돕는멤버 int numofdata; // 저장된데이터의수를기록하기위한멤버 int (*comp)(ldata d1, LData d2); // 정렬의기준을등록하기위한멤버 LinkedList; Data Structures and Algorithms 43

44 정렬기능추가된연결리스트헤더파일 : DLinkedList.h #define TRUE 1 #define FALSE 0 typedef int LData; typedef struct _node LData data; struct _node * next; Node; typedef LinkedList List; void ListInit(List * plist); void LInsert(List * plist, LData data); int LFirst(List * plist, LData * pdata); int LNext(List * plist, LData * pdata); LData LRemove(List * plist); int LCount(List * plist); typedef struct _linkedlist void SetSortRule(List * plist, int (*comp)(ldata d1, LData d2)); Node * head; Node * cur; Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; Data Structures and Algorithms 44

45 더미노드연결리스트구현 : 초기화 초기화함수 void ListInit(List * plist) plist->head = (Node*)malloc(sizeof(Node)); // 더미노드의생성 plist->head->next = NULL; plist->comp = NULL; plist->numofdata = 0; typedef struct _linkedlist Node * head; Node * cur; Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; Data Structures and Algorithms 45

46 더미노드연결리스트구현 : 삽입 1 void LInsert(List * plist, LData data) if(plist->comp == NULL) // 정렬기준이없다면 FInsert(plist, data); // 머리에노드를추가 else // 정렬기준이있다면 SInsert(plist, data); // 정렬기준에따라노드추가 void FInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); // 새노드생성 newnode->data = data; // 새노드에데이터저장 newnode->next = plist->head->next; // 새노드가다른노드를가리키게함 plist->head->next = newnode; // 더미노드가새노드를가리킴 (plist->numofdata)++; // 저장된노드의수를하나증가 Data Structures and Algorithms 46

47 더미노드연결리스트구현 : 삽입 2 더미노드를사용하면모든경우에동일한삽입과정을거침 void FInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); // 새노드생성 newnode->data = data; // 새노드에데이터저장 newnode->next = plist->head->next; // 새노드가다른노드를가리키게함 plist->head->next = newnode; // 더미노드가새노드를가리킴 (plist->numofdata)++; // 저장된노드의수를하나증가 Data Structures and Algorithms 47

48 더미노드연결리스트구현 : 참조 1 int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) // 더미노드가 NULL을가리킨다면, return FALSE; // 반환할데이터가없음 plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // cur이가리키던것을 before가가리킴 // cur은그다음노드를가리킴 // cur이가리키는노드의데이터전달 // 데이터반환성공 Data Structures and Algorithms 48

49 더미노드연결리스트구현 : 참조 2 int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) // 더미노드가 NULL을가리킨다면, return FALSE; // 반환할데이터가없음 plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // cur이가리키던것을 before가가리킴 // cur은그다음노드를가리킴 // cur이가리키는노드의데이터전달 // 데이터반환성공 Data Structures and Algorithms 49

50 더미노드연결리스트구현 : 삭제 1 cur 은삭제후재조정의과정을거쳐야함 before 는 LFirst 또는 LNext 호출시재설정됨 삭제전 삭제후 Data Structures and Algorithms 50

51 더미노드연결리스트구현 : 삭제 2 LData LRemove(List * plist) Node * rpos = plist->cur; LData rdata = rpos->data; plist->before->next = plist->cur->next; plist->cur = plist->before; Dlinkedlist.c DLinkedlist.h DLinkedlistmain.c 확인하기 free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 51

52 연결리스트의정렬삽입의구현 Data Structures and Algorithms 52

53 정렬기준설정 단순연결리스트의정렬관련요소세가지 1 2 void SetSortRule(List * plist, int (*comp)(ldata d1, LData d2)) plist->comp = comp; SetSortRule 함수정의에 정렬기준함수포함 typedef struct _linkedlist SetSortRule 함수를통해전달된 Node * head; 함수의리턴정보저장을위한 Node * cur; LinkedList의멤버 comp Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; 3 void LInsert(List * plist, LData data) if(plist->comp == NULL) Sinsert 함수가 comp의정렬기준 FInsert(plist, data); 대로데이터를저장 else SInsert(plist, data); Data Structures and Algorithms 53

54 SInsert 함수 void SInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); Node * pred = plist->head; newnode->data = data; // 새노드가들어갈위치를찾기위한반복문! while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 newnode->next = pred->next; pred->next = newnode; (plist->numofdata)++; Data Structures and Algorithms 54

55 다음상황에서 SInsert(&slist, 5); 실행 Data Structures and Algorithms 55

56 comp 가 0 을반환한다는것은첫번째인자인 data 가정렬순서상앞서기 때문에 head 에가까워야한다는의미! Data Structures and Algorithms 56

57 Data Structures and Algorithms 57

58 정렬의핵심인 while 반복문 반복의조건 1 pred->next!= NULL pred 가리스트의마지막노드를가리키는지묻기위한연산 반복의조건 2 plist->comp(data, pred->next->data)!= 0 새데이터와 pred 의다음노드에저장된데이터의우선순위비교를위한함수호출 while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 Data Structures and Algorithms 58

59 comp 의반환값과그의미 comp 가 0 을반환 첫번째인자인 data 가정렬순서상앞서서 head 에더가까워야하는경우 comp 가 1 을반환 두번째인자인 pred->next->data 가정렬순서상앞서서 head 에더가까워야하는경우 while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 Data Structures and Algorithms 59

60 정렬의기준을설정하기위한함수의정의 함수의정의기준 두개의인자를전달받도록함수를정의 첫번째인자의정렬우선순위가높으면 0 을, 그렇지않으면 1 을반환 오름차순정렬을위한함수의정의 Dlinkedlist.c DLinkedlist.h int WhoIsPrecede(int d1, int d2) DLinkedlistSortmain.c if(d1 < d2) return 0; // d1이정렬순서상앞선다. else return 1; // d2가정렬순서상앞서거나같다. Data Structures and Algorithms 60

61 원형연결리스트 Data Structures and Algorithms 61

62 원형연결리스트의이해 단순연결리스트의마지막노드는 NULL 을가리킴 원형연결리스트의마지막노드는첫번째노드를가리킴 Data Structures and Algorithms 62

63 원형연결리스트의노드추가 모든노드가연결되어있기때문에머리와꼬리구분이없음 두경우의노드연결순서가같다 head 가가리키는노드가다르다. Data Structures and Algorithms 63

64 원형연결리스트의장점 단순연결리스트처럼머리와꼬리를가리키는포인터변수를각각두지않아도, 하나의포인터변수만있어도머리또는꼬리에노드를간단히추가할수있다. Data Structures and Algorithms 64

65 원형연결리스트 연결리스트를가리키는포인터변수하나로머리와꼬리를쉽게확인가능 꼬리를가리키는포인터변수 : tail 머리를가리키는포인터변수 : tail->next Data Structures and Algorithms 65

66 변형된원형연결리스트의구현범위 이전에구현한연결리스트와기능동일 조회관련 Lfirst 삭제관련 Lremove 이외의부분 조회관련 Lnext 원형연결리스트를계속해서순환하는형태로변경! 삽입관련 앞과뒤에삽입이가능하도록두개의함수정의! 정렬관련 정렬과관련된부분전부제거 Data Structures and Algorithms 66

67 원형연결리스트의헤더파일과초기화함수 CLinkedList.h typedef int Data; typedef struct _node Data data; struct _node * next; Node; typedef struct _CLL Node * tail; Node * cur; Node * before; int numofdata; CList; typedef CList List; void ListInit(List * plist); void LInsert(List * plist, Data data); void LInsertFront(List * plist, Data data); int LFirst(List * plist, Data * pdata); int LNext(List * plist, Data * pdata); Data LRemove(List * plist); int LCount(List * plist); CLinkedList.c void ListInit(List * plist) plist->tail = NULL; plist->cur = NULL; plist->before = NULL; plist->numofdata = 0; // 모든멤버를 NULL 과 0 으로초기화 Data Structures and Algorithms 67

68 원형연결리스트구현 : 첫번째노드삽입 void LInsertFront(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) // 첫노드 plist->tail = newnode; newnode->next = newnode; else // 두번째노드이후 newnode->next = plist->tail->next; plist->tail->next = newnode; (plist->numofdata)++; Data Structures and Algorithms 68

69 원형연결리스트구현 : 두번째이후노드머리로삽입 void LInsertFront(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) // 첫노드 plist->tail = newnode; newnode->next = newnode; else // 두번째노드이후 newnode->next = plist->tail->next; plist->tail->next = newnode; 새노드추가 (plist->numofdata)++; Data Structures and Algorithms 69

70 원형연결리스트구현 : 앞과뒤의삽입과정비교 1 노드를머리에추가한결과 노드를꼬리에추가한결과 Data Structures and Algorithms 70

71 원형연결리스트구현 : 앞과뒤의삽입과정비교 2 void LInsert(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) tail의위치가다름 plist->tail = newnode; newnode->next = newnode; else newnode->next = plist->tail->next; plist->tail->next = newnode; plist->tail = newnode; //Linsertfront와차이 (plist->numofdata)++; Data Structures and Algorithms 71

72 원형연결리스트구현 : 조회 LFirst int LFirst(List * plist, Data * pdata) if(plist->tail == NULL) // 저장된노드가없다면 return FALSE; plist->before = plist->tail; plist->cur = plist->tail->next; *pdata = plist->cur->data; return TRUE; typedef struct _CLL Node * tail; Node * cur; Node * before; int numofdata; CList; cur 이가리키는노드가머리! typedef CList List; Data Structures and Algorithms 72

73 원형연결리스트구현 : 조회 LNext int LNext(List * plist, Data * pdata) if(plist->tail == NULL) // 저장된노드가없다면 return FALSE; plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; 이어지는 LNext 호출결과 원형연결리스트이므로 리스트의끝을검사하는 코드가없다! Data Structures and Algorithms 73

74 원형연결리스트구현 : 노드의삭제 ( 복습 ) 핵심연산 1. 삭제할노드의이전노드가, 삭제할노드의다음노드를가리키게한다. 2. 포인터변수 cur 을한칸뒤로이동시킨다. // 더미기반단순연결리스트의삭제! LData LRemove(List * plist) Node * rpos = plist->cur; LData rdata = rpos->data; 핵심연산 2 plist->before->next = plist->cur->next; plist->cur = plist->before; 핵심연산 1 free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 74

75 원형연결리스트구현 : 노드의삭제 ( 그림비교 ) 더미기반단순연결리스트 원형연결리스트 삭제과정이비슷해보이지만원형연결리스트에는더미노드가없기때문에 상황에따라삭제의과정이달라짐 Data Structures and Algorithms 75

76 원형연결리스트노드삭제구현 1 Data LRemove(List * plist) Node * rpos = plist->cur; Data rdata = rpos->data; if(rpos == plist->tail) // 삭제대상을 tail이가리킨다면 if(plist->tail == plist->tail->next) // 마지막남은노드라면 plist->tail = NULL; else plist->tail = plist->before; plist->before->next = plist->cur->next; plist->cur = plist->before; free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 76

77 원형연결리스트노드삭제구현 2 예외상황 1. 삭제할노드를 tail 이가리키는경우 2. 삭제할노드를 tail 이가리키는데, 그노드가마지막노드라면 Data Structures and Algorithms 77

78 이중연결리스트 Data Structures and Algorithms 78

79 양방향연결리스트의이해 양방향리스트를위한노드의표현 typedef struct _node Data data; struct _node * next; struct _node * prev; Node; Data Structures and Algorithms 79

80 양방향으로노드를연결하는이유! 오른쪽노드로의이동이쉽고, 양방향으로이동이가능하다! 양방향으로연결하는코드도복잡하지않음 // 단순연결리스트의 LNext int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) return FALSE; // 양방향연결리스트의 LNext int LNext(List * plist, Data * pdata) if(plist->cur->next == NULL) return FALSE; plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // before 유지불필요 plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; Data Structures and Algorithms 80

81 양방향연결리스트모델 LRemove 함수를 ADT에서제외 ADT에왼쪽노드의데이터를참조하는 LPrevious 함수를추가 새노드는머리에추가 Data Structures and Algorithms 81

82 양방향연결리스트의헤더파일 : DBLinkedList.h typedef int Data; typedef struct _node Data data; struct _node * next; struct _node * prev; Node; typedef struct _dblinkedlist Node * head; Node * cur; int numofdata; DBLinkedList; typedef DBLinkedList List; void ListInit(List * plist); void LInsert(List * plist, Data data); int LFirst(List * plist, Data * pdata); int LNext(List * plist, Data * pdata); // LPrevious 함수는 LNext 함수와반대로이동 int LPrevious(List * plist, Data * pdata); int LCount(List * plist); Data Structures and Algorithms 82

83 연결리스트의구현 : 리스트의초기화 ListInit 함수의정의에참조해야하는구조체의정의 typedef struct _dblinkedlist Node * head; Node * cur; int numofdata; DBLinkedList; head 와 numofdata 만초기화필요 멤버 cur 은조회의과정에서초기화됨 void ListInit(List * plist) plist->head = NULL; plist->numofdata = 0; Data Structures and Algorithms 83

84 연결리스트의구현 : 노드삽입의구분 1 빈리스트에삽입 Data Structures and Algorithms 84

85 연결리스트의구현 : 노드삽입의구분 2 두번째이후부터의노드삽입 Data Structures and Algorithms 85

86 연결리스트의구현 void LInsert(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = plist->head; if(plist->head!= NULL) plist->head->prev = newnode; newnode->prev = NULL; plist->head = newnode; (plist->numofdata)++; Data Structures and Algorithms 86

87 양방향연결리스트의구현 : 데이터조회 int LFirst(List * plist, Data * pdata) if(plist->head == NULL) return FALSE; plist->cur = plist->head; *pdata = plist->cur->data; int LNext(List * plist, Data * pdata) if(plist->cur->next == NULL) return FALSE; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; return TRUE; int LPrevious(List * plist, Data * pdata) if(plist->cur->prev == NULL) return FALSE; LFirst와 LNext는단방향연결리스트동일 plist->cur = plist->cur->prev; *pdata = plist->cur->data; return TRUE; LPrevious 와 LNext 의차이는이동방향뿐 Data Structures and Algorithms 87

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

윤성우의 열혈 TCP/IP 소켓 프로그래밍

윤성우의 열혈 TCP/IP 소켓 프로그래밍 C 프로그래밍프로젝트 Chap 22. 구조체와사용자정의자료형 1 2013.10.10. 오병우 컴퓨터공학과 구조체의정의 (Structure) 구조체 하나이상의기본자료형을기반으로사용자정의자료형 (User Defined Data Type) 을만들수있는문법요소 배열 vs. 구조체 배열 : 한가지자료형의집합 구조체 : 여러가지자료형의집합 사용자정의자료형 struct

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ 00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (

More information

1장. 리스트

1장. 리스트 01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E > 제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

Algorithms

Algorithms 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것

More information

C 언어 강의노트

C 언어 강의노트 C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11

More information

슬라이드 1

슬라이드 1 -Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

More information

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7> 제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked

More information

PowerPoint Template

PowerPoint Template 18 동적할당과고급처리 인터넷정보과 1 2/19 동적할당 목적 다음과같은일반변수의선언과사용은변수를정적 (static) 으로사용 int a = 10; 메모리사용예측이부정확한경우는충분한메모리를미리확보해야하는것은비효율 동적 (dynamic) 메모리할당 (Memory Allocation) 동적인메모리할당을위해서는함수 malloc() 을이용, 메모리공간을확보 함수 malloc()

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Lab 5. 실습문제 (Double linked list)-1_해답.hwp Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.

More information

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Function) 1. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,

More information

Microsoft PowerPoint - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap11-포인터의활용.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에

More information

Microsoft PowerPoint - chap10-함수의활용.pptx

Microsoft PowerPoint - chap10-함수의활용.pptx #include int main(void) { int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; } 1 학습목표 중 값에 의한 전달 방법과

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770> 연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.

More information

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE> 쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트 이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다. 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

Microsoft PowerPoint - chap12-고급기능.pptx

Microsoft PowerPoint - chap12-고급기능.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 가 제공하는 매크로 상수와 매크로

More information

Microsoft PowerPoint - Chapter_09.pptx

Microsoft PowerPoint - Chapter_09.pptx 프로그래밍 1 1 Chapter 9. Structures May, 2016 Dept. of software Dankook University http://embedded.dankook.ac.kr/~baeksj 구조체의개념 (1/4) 2 (0,0) 구조체 : 다양한종류의데이터로구성된사용자정의데이터타입 복잡한자료를다루는것을편하게해줌 예 #1: 정수로이루어진 x,

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li Linked List 2011 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

More information

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센 Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

More information

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D> 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.

More information

슬라이드 1

슬라이드 1 Linked List 2015 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

More information

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1. 표준입출력 표준입출력 입력 : 키보드, scanf 함수 출력 : 모니터, printf 함수문제 : 정수값 2개를입력받고두값사이의값들을더하여출력하라. #include int main(void) int Num1, Num2; int

More information

05_tree

05_tree Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical

More information

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ Linked List 2010 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

More information

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조

More information

Microsoft PowerPoint - 자료구조2008Chap06

Microsoft PowerPoint - 자료구조2008Chap06 제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 리스트 5 장. 리스트 목록이나도표처럼여러데이터를관리할수있는자료형을추상화 데이터삽입, 삭제, 검색등필요작업을가함스택과큐는리스트의특수한경우에해당 학습목표 추상자료형리스트개념과필요작업을이해한다. 배열로구현하는방법, 연결리스트로구현하는방법을숙지한다. C로구현할때와 C++ 로구현할때의차이점을이해한다. 자료구조로서배열과연결리스트의장단점을이해한다. 1 Section 01

More information

금오공대 컴퓨터공학전공 강의자료

금오공대 컴퓨터공학전공 강의자료 C 프로그래밍프로젝트 Chap 14. 포인터와함수에대한이해 2013.10.09. 오병우 컴퓨터공학과 14-1 함수의인자로배열전달 기본적인인자의전달방식 값의복사에의한전달 val 10 a 10 11 Department of Computer Engineering 2 14-1 함수의인자로배열전달 배열의함수인자전달방식 배열이름 ( 배열주소, 포인터 ) 에의한전달 #include

More information

Microsoft PowerPoint - chap4_list

Microsoft PowerPoint - chap4_list Chap. 4 : 리스트 (list) 2007 학년도 2 학기 리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트

More information

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]

More information

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조 - Part2- 제 2 장다차원배열이란무엇인가 학습목차 2.1 다차원배열이란 2. 2 2 차원배열의주소와값의참조 2.1 다차원배열이란 2.1 다차원배열이란 (1/14) 다차원배열 : 2 차원이상의배열을의미 1 차원배열과다차원배열의비교 1 차원배열 int array [12] 행 2 차원배열 int array [4][3] 행 열 3 차원배열 int array [2][2][3]

More information

중간고사 (자료 구조)

중간고사 (자료 구조) Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함. 215. 1. 27. 1 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070> 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include "QuickSort.h" 7 using namespace std; 8 9 10 Node* Queue[100]; // 추가입력된데이터를저장하기위한 Queue

More information

KNK_C_05_Pointers_Arrays_structures_summary_v02

KNK_C_05_Pointers_Arrays_structures_summary_v02 Pointers and Arrays Structures adopted from KNK C Programming : A Modern Approach 요약 2 Pointers and Arrays 3 배열의주소 #include int main(){ int c[] = {1, 2, 3, 4}; printf("c\t%p\n", c); printf("&c\t%p\n",

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 4. 리스트 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 리스트추상데이터타입 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 :

More information

02장.배열과 클래스

02장.배열과 클래스 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20 많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 :

More information

슬라이드 1

슬라이드 1 자료구조 (Data Structures), 4 장. 리스트 담당교수 : 조미경 이번장에서학습할내용 * 리스트란? * 배열로리스트구현 * 연결리스트로리스트구현 * 연결리스트종류 * 연결리스트응용 : 다항식구현 2/63 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item 0,

More information

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 5 장. 리스트 리스트 목록이나도표처럼여러데이터를관리할수있는자료형을추상화 데이터삽입, 삭제, 검색등필요작업을가함 스택과큐는리스트의특수한경우에해당 학습목표 추상자료형리스트개념과필요작업을이해한다. 배열로구현하는방법, 연결리스트로구현하는방법을숙지한다. C 로구현할때와 C++ 로구현할때의차이점을이해한다. 자료구조로서배열과연결리스트의장단점을이해한다. 1 목록 ( 도표

More information

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는

More information

슬라이드 1

슬라이드 1 CHAP 4 : 리스트 조영임 yicho@gachon.ac.kr 1 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item0, item1,..., itemn 1) 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace,

More information

슬라이드 1

슬라이드 1 CHAP 4: 리스트 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트 L ( item0, item1,..., itemn 1) 리스트의연산

More information

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx #include int main(void) { int num; printf( Please enter an integer "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; } 1 학습목표 을 작성하면서 C 프로그램의

More information

4장

4장 CHAP 4: 리스트 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item 0, item 1,..., item n 1) 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 영어알파벳 : (a, b,,z) 카드 : (Ace, 2,3,,King) 쇼핑리스트 리스트의연산 새로운항목을리스트의끝,

More information

Microsoft PowerPoint - 06-List.ppt

Microsoft PowerPoint - 06-List.ppt Chapter 4. 리스트 (List) Today.. 리스트의개념과추상데이터타입 리스트구현방법 배열 (Array) vs. 연결리스트 (Linked List) 2 1 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item 0, item 1,..., item 1 ) 리스트의예

More information

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - chap06-2pointer.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.

More information

슬라이드 1

슬라이드 1 CHAP 4: 리스트 C 로쉽게풀어쓴자료구조 생능출판사 2005 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item0, item1,..., itemn 1) 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King)

More information

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

untitled

untitled if( ) ; if( sales > 2000 ) bonus = 200; if( score >= 60 ) printf(".\n"); if( height >= 130 && age >= 10 ) printf(".\n"); if ( temperature < 0 ) printf(".\n"); // printf(" %.\n \n", temperature); // if(

More information

기초컴퓨터프로그래밍

기초컴퓨터프로그래밍 구조체 #include int main() { } printf("structure\n"); printf("instructor: Keon Myung Lee\n"); return 0; 내용 구조체 (struct) Typedef 공용체 (union) 열거형 (enum) 구조체 구조체 (structure) 어떤대상을표현하는서로연관된항목 ( 변수 )

More information

C 언어 프로그래밊 과제 풀이

C 언어 프로그래밊 과제 풀이 과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍

More information

11장 포인터

11장 포인터 누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리

More information

Chapter #01 Subject

Chapter #01  Subject Device Driver March 24, 2004 Kim, ki-hyeon 목차 1. 인터럽트처리복습 1. 인터럽트복습 입력검출방법 인터럽트방식, 폴링 (polling) 방식 인터럽트서비스등록함수 ( 커널에등록 ) int request_irq(unsigned int irq, void(*handler)(int,void*,struct pt_regs*), unsigned

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information

Frama-C/JESSIS 사용법 소개

Frama-C/JESSIS 사용법 소개 Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie

More information

구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined data types) : 다양한자료형을묶어서목적에따라새로운자료형을

구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined data types) : 다양한자료형을묶어서목적에따라새로운자료형을 (structures) 구조체정의 구조체선언및초기화 구조체배열 구조체포인터 구조체배열과포인터 구조체와함수 중첩된구조체 구조체동적할당 공용체 (union) 1 구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined

More information

Chapter 06. 스택(Stack)

Chapter 06. 스택(Stack) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 06. 스택 (Stack) Introduction To Data Structures Using C Chapter 06. 스택 (Stack) Chapter 06-1: 스택의이해와 ADT 정의 2 스택 (Stack) 의이해 스택은 먼저들어간것이나중에나오는자료구조 로서 초코볼이담겨있는통에비유할수있다.

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

untitled

untitled int i = 10; char c = 69; float f = 12.3; int i = 10; char c = 69; float f = 12.3; printf("i : %u\n", &i); // i printf("c : %u\n", &c); // c printf("f : %u\n", &f); // f return 0; i : 1245024 c : 1245015

More information

Microsoft PowerPoint - chap13-입출력라이브러리.pptx

Microsoft PowerPoint - chap13-입출력라이브러리.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 스트림의 기본 개념을 알아보고,

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning C Programming Practice (II) Contents 배열 문자와문자열 구조체 포인터와메모리관리 구조체 2/17 배열 (Array) (1/2) 배열 동일한자료형을가지고있으며같은이름으로참조되는변수들의집합 배열의크기는반드시상수이어야한다. type var_name[size]; 예 ) int myarray[5] 배열의원소는원소의번호를 0 부터시작하는색인을사용

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임

More information

OCW_C언어 기초

OCW_C언어 기초 초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향

More information

09_hash

09_hash Hash Data Structures and Algorithms 목차 빠른탐색 : 해쉬테이블 예제 좋은해쉬함수 충돌의해결 구현 응용 : Bloom Filter Data Structures and Algorithms 2 빠른탐색 : 해쉬테이블 Data Structures and Algorithms 3 테이블 : Key-Value 의집합 사전구조또는맵 (map)

More information

Microsoft PowerPoint - 제11장 포인터(강의)

Microsoft PowerPoint - 제11장 포인터(강의) 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

More information

7장

7장 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트

More information

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D> 리눅스 오류처리하기 2007. 11. 28 안효창 라이브러리함수의오류번호얻기 errno 변수기능오류번호를저장한다. 기본형 extern int errno; 헤더파일 라이브러리함수호출에실패했을때함수예 정수값을반환하는함수 -1 반환 open 함수 포인터를반환하는함수 NULL 반환 fopen 함수 2 유닉스 / 리눅스 라이브러리함수의오류번호얻기 19-1

More information

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 이중포인터란무엇인가? 포인터배열 함수포인터 다차원배열과포인터 void 포인터 포인터는다양한용도로유용하게활용될수있습니다. 2 이중포인터

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Chapter 08 함수 01 함수의개요 02 함수사용하기 03 함수와배열 04 재귀함수 함수의필요성을인식한다. 함수를정의, 선언, 호출하는방법을알아본다. 배열을함수의인자로전달하는방법과사용시장점을알아본다. 재귀호출로해결할수있는문제의특징과해결방법을알아본다. 1.1 함수의정의와기능 함수 (function) 특별한기능을수행하는것 여러가지함수의예 Page 4 1.2

More information

03장.스택.key

03장.스택.key ---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():

More information

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예

More information

K&R2 Reference Manual 번역본

K&R2 Reference Manual 번역본 typewriter structunion struct union if-else if if else if if else if if if if else else ; auto register static extern typedef void char short int long float double signed unsigned const volatile { } struct

More information

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 제 8 장. 포인터 목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 포인터의개요 포인터란? 주소를변수로다루기위한주소변수 메모리의기억공간을변수로써사용하는것 포인터변수란데이터변수가저장되는주소의값을 변수로취급하기위한변수 C 3 포인터의개요 포인터변수및초기화 * 변수데이터의데이터형과같은데이터형을포인터 변수의데이터형으로선언 일반변수와포인터변수를구별하기위해

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드

More information

Microsoft PowerPoint - C++ 5 .pptx

Microsoft PowerPoint - C++ 5 .pptx C++ 언어프로그래밍 한밭대학교전자. 제어공학과이승호교수 연산자중복 (operator overloading) 이란? 2 1. 연산자중복이란? 1) 기존에미리정의되어있는연산자 (+, -, /, * 등 ) 들을프로그래머의의도에맞도록새롭게정의하여사용할수있도록지원하는기능 2) 연산자를특정한기능을수행하도록재정의하여사용하면여러가지이점을가질수있음 3) 하나의기능이프로그래머의의도에따라바뀌어동작하는다형성

More information

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,

More information

Microsoft PowerPoint - 제11장 포인터

Microsoft PowerPoint - 제11장 포인터 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

More information

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 #define _CRT_SECURE_NO_WARNINGS #include #include main() { char ch; printf(" 문자 1개를입력하시오 : "); scanf("%c", &ch); if (isalpha(ch))

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Chapter 10 포인터 01 포인터의기본 02 인자전달방법 03 포인터와배열 04 포인터와문자열 변수의주소를저장하는포인터에대해알아본다. 함수의인자를값과주소로전달하는방법을알아본다. 포인터와배열의관계를알아본다. 포인터와문자열의관계를알아본다. 1.1 포인터선언 포인터선언방법 자료형 * 변수명 ; int * ptr; * 연산자가하나이면 1 차원포인터 1 차원포인터는일반변수의주소를값으로가짐

More information

2002년 2학기 자료구조

2002년 2학기 자료구조 자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)

More information