Microsoft PowerPoint - 제6장-연결리스트.pptx

Size: px
Start display at page:

Download "Microsoft PowerPoint - 제6장-연결리스트.pptx"

Transcription

1 제 6 강의. 연결리스트 1. 포인터타입 2. 단순연결리스트 3. 연결리스트를이용한스택의구현 4. 연결리스트를이용한큐의구현 5. 리스트구현방법의정리 1

2 리스트자료구조 데이터연산설명 스택 int stack[100]; (10, 30, 40, 20) push(35); y=pop(); 삽입과삭제가한쪽끝 큐 int queue[100]; (10, 30, 40, 20) insert(35); y=delete(); 삽입과삭제가양쪽끝 삽입과삭제가아무곳에서나일어난다. 리스트 ( 순서있는리스트 ) Ordered List int list[100]; (10, 30, 40, 20) insert(35); y=delete(); ( 문제점 ) => 데이터가많으면순서를유지하기위하여데이터이동이많아진다. ( 해결방법 )? 2

3 동적 (dynamic) 데이터의관리 프로그램실행중데이터가이동을많이한다면? - 데이터가움직이지않으면검색을빨리할수있다. - 데이터는삽입, 삭제연산에의하여위치와개수가변한다. - 데이터가변경되어위치가바뀌면검색을빨리하기위한위한재배치를한다. 3

4 1. 포인터타입 (Pointers) 연결리스트는기억장소의임의의구조체로구현된노드를서로연결하여리스트를만든다. 따라서다음데이터가저장된노드의기억장소를저장하는 ( 가리키는 ) 값이필요하다. 기억장소의주소값을저장하는데이터타입을 포인터 (pointer) 타입 이라한다 기억장소 -> 기억장소의주소 -> 주소를저장하는기억장소 1020 번지 번지 1020 기억장치 ( 정수저장 ) 기억장소주소 주소를기억하는변수 ( 포인터변수 ) 서울시하늘동 100 번지 서울시하늘동 100 번지 장소 ( 집 ) 주소 주소를기록한종이 4

5 포인터타입사용예 1 int x; /* 내용을저장하는정수형변수 */ int *y; /* 주소를저장하는정수형변수 */ int z; x= 10; /* 내용 10을저장 */ y = &x; /* x의주소를저장, x의주소값을알필요없다.*/ z = *y; /* 주소 y가가리키는곳의내용을저장 */ /* z = x와같은의미가된다. */ int a[10]; /* 배열변수 a는주소값으로처리한다. */ /* 그이유는배열의내용전체를이동할경우보다주소값을알려주면편하기때문이다. */ x(100 번지 ) 10 y(104 번지 ) 100 z(108 번지 ) 10 a(120 번지 ) 번지 5

6 포인터사용의예 2 예제 1) 아래프로그램을실행하고결과를살펴보아라. #include <stdio.h> int main() { int i, *pi; float f, *pf; pi = &i; // i의주소값 pf = &f; // j의주소값 *pi = 1024; *pf = (float) 3.14; printf("an integer=%d,a float=%f\n", *pi, *pf); 6

7 예제 2) 아래프로그램을예제 1 프로그램과비교하여보아라. 포인터변수와포인터가가리키는기억장소확보하여데이터를저장하고기억장소반납 /* DBLAB pointer.c */ #include <stdio.h> #include <malloc.h> int main() { int *pi; float *pf; pi = (int *)malloc(sizeof(int)); /* 기억장소배정 */ pf = (float *)malloc(sizeof(float)); /* 기억장소배정 */ *pi = 1024; *pf = (float) 3.14; printf("an integer=%d,a float=%f\n", *pi, *pf); free(pi); /* 기억장소반환 */ free(pf); 7

8 실행문장 => 1: int i,*pi; 2: float f,*pf; /* 변수 i, pi, f, pf 의기억장소가할당된다. */ 기억장소 0 NULL i(int) pi(int *) 0.0 NULL f(float) pf(float *) 힙기억장소 출력 8

9 실행문장 => 3: pi = (int *)malloc(sizeof(int)); 4: pf = (float *)malloc(sizeof(float)); /* 변수 pi, pf 에힙에서임의의기억장소가할당되어각각정수형, 실수형포인터로변환되어주소값을저장한다 */ 기억장소 i(int) pi(int *) f(float) pf(float *) 힙기억장소 번지 번지 출력 9

10 실행문장 => 5: *pi = 1024; 6: *pf = 3.14; /* 변수 pi, pf 가가리키는곳에 1024 와 3.14 를저장한다.*/ 기억장소 i(int) pi(int *) f(float) pf(float *) 힙기억장소 번지 번지 출력 10

11 실행문장 => 7: printf( an integer=%d,a float=%f\n,*pi,*pf); /* 변수 pi, pf 가가리키는곳의값을출력한다.*/ 기억장소 i(int) pi(int *) f(float) pf(float *) 힙기억장소 번지 번지 출력 an integer=1024,a float=

12 실행문장 => 8: free(pi); 9: free(pf); /* 변수 pi, pf 가가리키는기억장소를반환한다. pi, pf 가가리키는값은남아있지만사용하면 error 이다.*/ 기억장소 i(int) pi(int *) f(float) pf(float *) 힙기억장소 출력 an integer=1024,a float=

13 데이터의관리 : 배열과연결리스트 배열 ( 리스트 ) 연결리스트 ( 리스트 ) 구현방법배열로선언예 ) int list[n]; 연결리스트예 ) list_ptr ptr; 검색이진검색트리를이용한검색 조작 ( 삽입, 삭제 ) 삽입과삭제후데이터재배치가힘들다. 데이터는그대로두고포인터로데이터를연결한다. 13

14 연결리스트를만들기위한구조체선언 - ( 자기참조구조체, self referential structure, a pointer to itself) - ( 동적인자료의할당과해지 (allocation/deallocation) 를위한자료구조 ) struct node { int data; // 데이터 struct node *link; // 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; data(int) link(list_ptr) list 타입 14

15 리스트자료의예 list_node item1, item2, item3; item1.data = 10; item2.data = 20; item3.data = 30; item1.link = item2.link = item3.link = NULL; // 포인터초기값 item1 item2 item 리스트의연결예 item1.link=&item2; item2.link=&item3; item1 item2 item

16 프로그램 1 - 노드를 3개선언하여연결하여리스트로만든다. #include <stdio.h> #include <malloc.h> struct node { int data; // 데이터 struct node *link;// 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; int main(void) { list_node item1, item2, item3; item1.data = 10; item2.data = 20; item3.data = 30; item1.link = item2.link = item3.link = NULL; // 포인터초기값 printf("%d %d %d\n", item1.data, item2.data, item3.data); 16

17 프로그램 2 - 노드를 3개기억장소에서받아와서연결하여리스트로만든다 #include <stdio.h> #include <malloc.h> struct node { int data; // 데이터 struct node *link;// 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; int main(void) { list_ptr first, second, third; first = (list_ptr)malloc(sizeof(list_node)); second = (list_ptr)malloc(sizeof(list_node)); third = (list_ptr)malloc(sizeof(list_node)); third->link = NULL; first->data = 10; second->data = 20; third->data = 30; first->link = second; second->link = third; 17 printf("%d %d %d\n", first->data, second->data, third->data);

18 2. 단순연결리스트 (Singly Linked Lists) 연결리스트의가장간단한형태로그냥 연결리스트 라고부른다. 노드들을연결한형태이며노드는데이터부분과링크부분으로구성된다. 데이터부분은한개혹은여러개의속성을저장할수있다. 링크부분은다음노드의주소값을가리킨다. 동적기억할당과해제가가능하다. 단순연결리스트 ptr

19 예 1) 단순연결리스트노드의선언과생성 struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; list_node 타입의구조 data(int) link(list_ptr) 19

20 예 2) 빈리스트에노드를한개생성하여 50 을저장 list_ptr ptr = NULL; ptr=(list_ptr)malloc(sizeof(list_node)); // 기억장소를 Heap 영역에서 ( 동적 ) 할당받는문장 ptr->data=50; ptr->link=null; ptr ptr->data 50 ptr->link NULL 20

21 예 3) 단순연결리스트 삽입알고리즘 30과 70 사이에 50을삽입한다면? 1) 기억장소로부터노드를얻는다.( 주소값 : paddr) ptr NULL 주소값을변수 paddr 에저장 paddr 2) 노드에 50 데이터를저장한다. ptr NULL paddr 50 21

22 3) paddr 노드의링크값에 30 노드의링크값을저장한다. ptr NULL paddr 50 4) 30 노드의링크값에 paddr 을저장한다. ptr NULL paddr 50 22

23 예 4) 단순연결리스트 삭제알고리즘 ptr NULL 1 2 1) 삭제할 50 노드의앞노드 30 을찾는다. 2) 30 노드의링크를 50 노드의링크가가리키는데이터로바꾼다. 23

24 예 5) 연결리스트의생성함수 ( 정수형데이터저장, 리스트포인터반환 ) list_ptr create() { list_ptr first, second; first = (list_ptr)malloc(sizeof(list_node)); second = (list_ptr)malloc(sizeof(list_node)); second->link=null; second->data=20; first->data=10; first->link=second; return first; first second NULL 24

25 Q/A 다음그림에서노드가가리키는곳 first second NULL * 다음이가리키는곳은? first -> data first -> link -> data first -> link -> link second -> link 다음의값은? first -> data first -> link -> data first -> link -> link -> link second -> link (*first).data 25

26 예6) 리스트생성실험프로그램 : 1개의노드동적 (dynamic) 생성 #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; int main() { list_ptr ptr = NULL; ptr = (list_ptr)malloc(sizeof(list_node)); ptr->data = 10; /* 리스트의값 */ ptr->link = NULL; printf(" %d n", ptr->data); 26

27 예 7)-1 리스트생성실험프로그램 : 4 개의노드를반복문으로생성 #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; ptr 40 int main() { list_ptr ptr = NULL, before=null; int i; for(i=1; i<=4; i++) //=> create( ) { ptr = (list_ptr)malloc(sizeof(list_node)); ptr->data = i*10; /* 리스트의값 */ ptr->link = before; before=ptr; printf(" %d n", ptr->data); // => print_list( ) printf(" %d n", ptr->link->data); printf(" %d n", ptr->link->link->data); printf(" %d n", ptr->link->link->link->data); /* for( ; ptr; ptr=ptr->link) printf(" %d n", ptr->data); */ NULL 27

28 예 7)-2 리스트출력함수 print_list( ) while not end of the list do print out data field; move to the next node; end; void print_list(list_ptr ptr) { printf( The list contains: ); for( ; ptr; ptr = ptr->link) printf( %4d, ptr->data); printf( \n ); 28

29 예 7)-3 리스트생성실험프로그램 함수 create() 로작성 #include <stdio.h> #include <malloc.h> struct node { int data; // int 로 struct node *link; ; typedef struct node list_node; typedef list_node *list_ptr; list_ptr create(int); // 함수원형선언... void print_list(list_ptr p); void delete(list_ptr p, int k); int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); //

30 list_ptr create(int n) // QUIZ : 30을끝에다붙인다. { list_ptr first, temp = NULL, before = NULL; // for (int i = 1; i <= n; i++) // { temp = (list_ptr)malloc(sizeof(list_node)); temp->data =(n- i+1) * 10; temp->link = before; before = temp; // 중요 first = temp; return first; void print_list(list_ptr p) { list_ptr temp; for (temp = p; temp; temp = temp->link) //temp!= NULL { printf("%d ", temp->data); // 수정 printf(" n"); ptr NULL 30

31 예 8)-1 연결리스트실험 - k 값을가진노드삭제함수 delete ( ) #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; /* 7-3 동일 create, print_list */ int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); // delete(p, 30); print_list(p); // // 리스트에서 k 값노드삭제... void delete(list_ptr p, int k) { list_ptr temp, before; if (!p) return; // p 가 NULL 이면아무것도않는다. // k 앞노드를 before 에저장한다. before = NULL; for (temp = p; temp!= NULL; temp = temp->link) { if (temp->data == k) { before->link = temp->link; break; // k 앞노드링크를 k 노드링크값으로치환. before = temp; // QUIZ : 맨처음노드의데이터가 k 이면어떻게해야하는가? 실험을해보고결과를살피자 31

32 예 8)-2 연결리스트실험 - k 값을가진노드삽입 insert ( ) #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; /* 7-3 동일 create, print_list */ int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); // insert(p, 35); print_list(p); // void insert(list_ptr p, int k) { list_ptr temp, before, temp1; if (!p) return; // p 가 NULL 이면아무것도않는다. // k 앞노드를 before 에저장한다. before = NULL; for (temp = p; temp!= NULL; temp = temp->link) { if (temp->data > k) { temp1 = (list_ptr)malloc(sizeof(list_node)); temp1->data = k; temp1->link = temp; before->link = temp1; break; // k 앞노드링크를 k 노드링크값으로치환. before = temp; 32

33 예 9) 노드삽입 : ptr 이가리키는리스트에 aptr 이가리키는노드다음에 x(50) 삽입 ptr NULL ptr NULL aptr 50 temp 33

34 /* node 변수가가리키는곳다음에데이터 50 을노드를삽입 */ 함수로작성했을경우 ptr 대신 ptr 주소값 *ptr 을인자로전달하는이유 => 다음페이지참고 void insert(list_ptr *ptr, list_ptr aptr, int x) { list_ptr temp; temp=(list_ptr)malloc(sizeof(list_node)); temp->data=50; if(*ptr) // 연결리스트가빈리스트가아닐경우 { temp->link = aptr->link; aptr->link = temp; else { // 연결리스트가비어있는경우처리 temp->link = NULL; *ptr = temp; 34

35 [ 참고 ] ptr 대신 ptr의주소값 *ptr 을인자로전달하는이유 => 함수에서 ptr 값의변화된값을받기위하여주소인자로전달앞의 insert( ) 함수의경우 ptr 값이바뀌어반환될수있기떄문에바뀐값을받을수있도록 ptr의주소값을전달한다. ( 선언 ) void insert(list_ptr ptr, list_ptr node) { ptr 대신 void insert(list_ptr *ptr, list_ptr node) { *ptr 로사용 ( 호출 ) main() { insert(ptr, node) 대신 main() { insert(&ptr, node) 로호출 35

36 예 10) 노드삭제 - ptr: 리스트첫노드를가리키는포인터변수 - aptr 삭제될노드를가리키는변수 - trail: 삭제될노드의바로앞노드를가리키는변수 ptr trail aptr NULL 삭제될노드가첫노드일경우 ( 삭제후 ptr 값이바뀌는경우 ) 와그렇지않은경우로나눈다. 1) 삭제될노드가리스트의첫노드일때 리스트시작인 ptr 값이바뀐다 ptr=aptr trail Trail =NULL ptr NULL (a) 삭제전 NULL (a) 삭제후 36

37 2) 그외의경우리스트시작인 ptr 값이안바뀐다 ptr trail aptr ptr NULL NULL (a) 삭제전 (a) 삭제후 void delete(list_ptr *ptr, list_ptr trail, list_ptr aptr) { if(aptr==*ptr) /* 첫노드가지울노드와같을때 */ *ptr=aptr->link; else /* 그외의경우 */ trail->link = aptr->link; free(aptr); 37

38 3. 연결리스트를이용한스택과큐의구현 3.1. 연결리스트를이용한스택의구현 (Dynamically Linked Stacks) top NULL 연결리스트스택 #define MAX_STACKS 10 /* n=max_stacks=10 */ typedef struct stack *stack_ptr; typedef struct stack { 연결리스트를이용한스택구조의선언 int item; stack_ptr link; ; stack_ptr top; 38

39 top element key link NULL 스택의초기상태 top = NULL 스택의상태 - 비어있는스택 : top = NULL -꽉찬상태 malloc( ) 함수호출시기억장소공간이부족할때 39

40 /* top 대신 top 의주소값 *top 을인자로전달하는이유 => push() 함수에서 top 값의변화된값을받기위하여주소인자로전달 */ void push(stack_ptr *top, int data) { stack_ptr temp = (stack_ptr)malloc(sizeof (stack)); if(!temp) { fprintf(stderr, The memory is full\n ); exit(1); temp->item=item; temp->link=*top; *top = temp; 스택의 push() 함수 - 리스트맨앞에노드를삽입 40

41 int pop(stack_ptr *top) { stack_ptr temp = *top; int data; if(!temp ) { fprintf(stderr, The stack is empty\n ); exit(1); 스택의 pop( ) 함수 data=temp->item; -리스트맨앞의노드삭제 *top=temp->link; free(temp); return data; 41

42 /* 연결리스트스택정의여기에 */ int main() { int e; push(20); push(40); push(40); push(40); push(60); 스택테스트의 main 함수 printf(" Begin Stack Test...\n"); while(!isempty()) { e = pop(); printf("value = %d\n", e); 42

43 3.2. 연결리스트를이용한큐의구현 (Dynamically Linked Queues) front rear NULL 연결리스트큐 연결리스트를이용한 1 개의큐구현 #define MAX_QUEUES 10 /* m=max_queues=10 */ typedef struct queue *queue_ptr; typedef struct queue { element item; queue_ptr link; ; queue_ptr front, rear; 43

44 front element key link rear NULL 큐의초기상태 front = rear = NULL 큐의상태 - 비어있는큐 : front = NULL -꽉찬상태: malloc( ) 함수호출시기억장소확보가안될때 44

45 void insert(queue_ptr *front, queue_ptr *rear, element x) { queue_ptr temp = (queue_ptr)malloc(sizeof(queue)); if(!temp ) { fprintf(stderr, The memory is full\n ); exit(1); temp->item=x; temp->link=null; if(*front) (*rear)->link=temp; else *front = temp; *rear = temp; 연결리스트큐에삽입함수 insert( ) - 리스트의맨뒤 (rear) 에삽입 45

46 element delete(queue_ptr *front) { queue_ptr temp=*front; element x; if(!(*front)) { fprintf(stderr, The queue is empty\n ); exit(1); 연결리스트큐에삭제함수 delete( ) - 리스트의맨앞에서삭제 x=temp->item; *front=temp->link; free(temp); return x; 46

47 Q/A linkedlist-queue.c 프로그램을실행해보자 ( 실험 1) linkedlist-queue.c 프로그램을실행해보고 4 장의 queue.c 프로그램과비교해보자 ( 실험 2) 큐에있는원소의수를세는함수를작성하여라 (linkedlist-queue.c) int elementcount(queue_ptr front, queue_ptr rear) { /* 여기작성 */ 47

48 4. 연결리스트를이용한다항식문제해결 연결리스트를이용한응용이많이있지만대표적인예로다항식의계산을보도록한다. 다항식은 A(x) = 7x 3 + 4x 같은식처럼여러개의항 (term) 으로구성된식이다. 다항식에관한연산을하기위해서항의검색, 삽입, 삭제가필요하고이러한연산을하기위한자료구조로연결리스트를사용하면편리하다. - 두개의다항식의덧셈을통하여연결리스트를조작하는프로그래밍기법 - 연결리스트의노드를획득하고해지하는함수를통하여기억장소를관리 48

49 4.1. 다항식 (Polynomials) 과연결리스트 다항식이란? 다항식은 A(x) = 7x 3 + 4x 같은식처럼여러개의항 (term) 으로구성된식이다. 다항식의계산, 두개의다항식의덧셈, 곱셈등에관한여러가지문제를해결하려면다항식을컴퓨터프로그램에표현하여저장하여야한다. 저장된다항식은여러가지연산과정을거쳐서계산을하거나, 다항식끼리덧셈, 다항식끼리곱셈등을하게된다. 이러한문제를효율적으로해결하려면다항식의항들을저장하는방법을잘선택하여야한다. 자료구조기초함수들함수들 다항식자료구조 컴퓨터에저장 항의비교 같은항찾기 두항을더하기 다항식의계산 다항식의덧셈 다항식의곱셈 두항을곱하기 항의삽입 항의삭제 49

50 다항식을배열에표현하면? 예를들어다음다항식 7x 3 + 4x 은배열에다음 { (7,3), (4,2), (2,0) 을저장하여야한다. 예를들어다음과같이선언하고계수 (coefficient) 만을배열에저장하면된다. int poly [10]; 배열 poly

51 다항식을연결리스트에표현하면? 다음다항식을배열로표현하면어떻게될까? 7x x 방법 1 : 배열에단순저장 - 방법 2 : 연결리스트로다항식의항 { (7,1000), (4,23), (2,0) 을저장 다항식을연결리스트로표현하면? A(x) = a m-1 x m a 0 x0 typedef struct poly_node *poly_ptr; typedef struct poly_node { int coef; int expon; poly_ptr link; ; poly_ptr a,b,d; coef expon link 51

52 예 ) a a = 3x x NULL b b = 8x 14-3x x NULL 52

53 4.2. 연결리스트를이용한다항식의덧셈 연결리스트로표현된두개의다항식을더하는프로그램을작성하여보자. a = 3x x b = 8x 14-3x x 6 d = 11x 14-3x x x a NULL d NULL b NULL 53

54 연결리스트로표현된두개의다항식 a, b 를더하는경우를단계별로보자. (a) a->expon == b->expon ( 지수가같은경우 ) 두다항식 a,b 의최고차항두개를비교하여같으면두항의계수를더하여새로운다항식 d 에항을만든다. 덧셈후포인터를이동한다 NULL 8 a NULL b NULL d 54

55 (b) a->expon < b->expon (b 의지수가더큰경우 ) 두다항식 a,b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다. 예의경우 b 가가르키는지수값이크므로 b 의항을 d 에더한다 NULL a NULL b NULL 55

56 (c) a->expon > b->expon (a 의지수가더큰경우 ) 두다항식 a, b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다 ( 예의경우 a 의가르키는지수값이크므로 a 의항을 d 에더한다 ) NULL a NULL b NULL d 56

57 (d) a->expon < b->expon 두다항식 a,b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다 ( 예의경우 b 가가르키는지수값이크므로 b 의항을 d 에더한다 ) NULL NULL a b NULL d 57

58 (e) b == NULL; 두다항식 a,b 중 b 의항이 NULL 이되면 a 의남은항을 d 에복사하여연결한다 ( 예의경우 a 가가르키는지수값이크므로 b 의항을 d 에더한다 ) NULL NULL a b = NULL NULL d 58

59 두다항식의덧셈 - 앞의예를참고하여두개의다항식을더하는프로그램 padd() 를작성하였다. padd() 함수 /* 두개의다항식을더하는함수, 인자는두다항식의포인터, 결과는새로생성된다항식의포인터이다 */ poly_ptr padd(poly_ptr a,poly_ptr b) { poly_ptr front,rear,temp; int sum; rear=(poly_ptr)malloc(sizeof(poly_node)); if(is_full(rear)) { fprintf(stderr, The memory is full n ); exit(1); front = rear; while(a && b) switch(compare(a->expon,b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef,b->expon,&rear); b = b->link; break; ( 계속 ) 59

60 case 0: /* a->expon = b->expon */ sum = a->coef + b->coef; if(sum) attach(sum,a->expon,&rear); a = a->link; b = b->link; break; case 1: /* a->expon > b->expon */ attach(a->coef,a->expon,&rear); a = a->link; for( ; a; a=a->link) attach(a->coef,a->expon,&rear); for( ; b; b=b->link) attach(b->coef,b->expon,&rear); rear->link = NULL; temp=front; front=front->link; free(temp); return front; 60

61 리스트의끝에노드를첨가 padd() 함수에서필요한다항식의끝에항을붙이는함수 attach() 이다. attach 함수 /* 항을다항식에연결하는함수, 인자는항의계수, 지수, 다항식의포인터이고출력인자는다항식포인터 *ptr 이다 */ void attach(float coef, int exp, poly_ptr *ptr) { poly_ptr temp; temp=(poly_ptr)malloc(sizeof(poly_node)); if(is_full(temp)) { fprintf(stderr, The memory is full n ); exit(1); temp->coef = coef; temp->expon = exp; (*ptr)->link = temp; *ptr=temp; 61

62 두개의다항식을더하는프로그램의수행시간은? m, n : 두다항식의항의수 -계수덧셈 O(min{m, n) -지수비교 O(m + n) - 다항식 d의노드생성시간 O(m + n) 전체시간복잡도 O(m + n) 62

63 4.3. 연결리스트노드의관리 다항식의예에서연산을하다보면필요없는항이만들어진다. 이러한항은기억장소에다시반환되어야한다. 예 아래예에서임시로계산된다항식 temp 의모든항은기억장소에반환되어야한다. e (x) = a(x) * b(x) + d(x) ( 프로그램 ) poly_ptr a, b, d, temp, e; a = read_poly(); b = read_poly(); d = read_poly(); temp = pmult(a, b); e = padd(temp, d); print_poly(e); 63

64 다항식을가리키는포인터가인자로주어지면다항식에포함된항을하나씩모두기억장소에반환하는프로그램은다음과같다. 다항식의삭제 erase 함수 /* 다항식항을기억장소로반환하는함수인자는다항식의포인터이다. */ void erase(poly_ptr *ptr) { poly_ptr temp; while (*ptr) { temp = *ptr; *ptr = (*ptr)->link; free(temp); 64

65 노드 ( 항 ) 의할당과해지 다항식의계산을위해자주일어나는노드의생성과해지를위하여노드를저장하는리스트 ( 노드창고 ) 를만들어놓을수도있다. - 처음에모든사용가능한노드를기억장소 ( 연결리스트 ) 에모아둔다. - avail : 연결리스트의처음을가르키는포인터 avail 1 2 n 초기연결리스트 NULL 노드저장소 (Storage pool) 65

66 get_node 함수 /* 노드가필요할경우노드저장소에서노드한개를를반환해주는함수 get_node() */ poly_ptr get_node(void) { poly_ptr node; if (avail) { node = avail; avail = avail->link; else { node = (poly_ptr)malloc(sizeof(poly_node)); if(is_full(node)) { fprintf(stderr, The memory is full n ); exit(1); return node; 66

67 ret_node 함수 /* 필요없는노드를반환받아노드저장소 avail 에저장하는함수 ret_node() */ void ret_node(poly_ptr ptr) { ptr->link = avail; avail = ptr; erase 함수 /* 필요없는다항식전체를받아서각노드를반복하여 avail 연결리스트에반환하는함수 */ void erase(poly_ptr *ptr) { poly_ptr temp; while (*ptr) { temp = *ptr; *ptr = (*ptr)->link; ret_node(temp); 67

68 다항식의노드를쉽게반환하려면? 다항식의노드를반환하는함수 erase() 는 O(n) 의시간이소요된다. 좀더효율적인방법으로 O(1) 의시간에해결하려면? - 다항식을원형연결리스트로바꾼다. ( 마지막노드의링크가리스트의시작노드를가리킨다.) ptr - 효율적인 erase 알고리즘 - 알고리즘효율성 O(1) cerase 함수 /* 필요없는노드들을한번에원형노드저장소에반환하는함수 */ void cerase(poly_ptr *ptr) { if(*ptr) { temp = (*ptr)->link; (*ptr)->link = avail; avail = temp; *ptr = NULL; 68

69 5. 리스트와연결리스트 (List and Linked List) 리스트 (list) - 순서가있는데이터를말한다. - 리스트자료에대한연산은검색, 변경 ( 삽입, 삭제 ) 이다. - 스택과큐는리스트의특수한형태이다. 리스트자료구조의구현 - 배열은리스트자료구조를구현하는방법이다. - 연결리스트도리스트를구현하는방법이다. 배열을이용한리스트구현은다음과같은장단점이있다. - 연속된기억장소 - 데이터의중간에삽입, 삭제시데이터이동이필요하다. - 데이터의크기가수행전 ( 컴파일때 ) 결정된다. - 정적인기억장소할당 (static storage allocation) 69

70 리스트자료구조 순서가있는자료의총칭. 검색과변경 ( 삽입과삭제 ) 연산이필요한자료구조 일반리스트 삽입과삭제가임의의장소에서일어남. 스택 큐 삽입과삭제가한쪽끝에서일어남 삽입은 rear 에서삭제는 front 에서일어남 70

71 리스트자료구조를구현하는프로그램자료구조의종류 ( 설명 ) 왼쪽은자료구조이고오른쪽은구현방법이다. 예를들면스택은배열로구현할수도있고연결리스트로도구현할수있다. 리스트자료구조 자료구조구현 일반리스트 배열 스택 원형배열 큐 연결리스트 71

72 리스트자료구조와연산 리스트자료구조연산 삽입 삭제 insert ( ) delete ( ) insertfirst() insertlast ( ) deletefirst ( ) deletelast ( ) 리스트자료구조 스택자료구조 큐자료구조 ( 리스트연산 ) Insert(), delete(), ( 스택연산 ) insertfirst()=push(), deletefirst()=pop(), ( 큐연산 ) deletefirst(), insertlast(), 72

73 리스트를구현하는두가지방법의비교 배열연결리스트설명 구현방법 배열로선언예 ) int list[n]; 연결리스트예 ) list_ptr ptr; 기억장소확보시점 프로그램수행전 (compile time) 정적기억장소할당 ( 기억장소 N 개로시작 ) 프로그램수행후 (run time) 동적기억장소할당 ( 기억장소 1 개로시작 ) 배열에서기억장소가수행전에할당되는경우기억장소크기가고정되고, 사용여부에관계없이기억장소를확보한다. 기억장소연속성 연속된기억장소할당 기억장소힙 (heap) 영역에서임의로할당 연결리스트에서는기억장소가여기저기흩어져있고링크를통하여연결이된다. 삽입과삭제알고리즘 O(n) O(1) 프로그래밍은연결리스트가복잡하다. 73

74 Review 포인터는데이터의효율성, 함수의주소인자, 동적인자료구조의세가지기능을구현하기위한방법이다. 포인터는주소값을저장하며수행시간 ( 동적, dynamic) 에리스트데이터들을주소값으로연결하는데사용된다. 리스트를배열을이용하면쉽게표현할수있다. 연결리스트는포인터를이용하여리스트데이터를연결하는방법이다. 연결리스트는스택과큐를구현하는방법이된다. 다항식문제는배열을이용하여해결할수있다 연결리스트의생성과반환을위한함수들에대한정확한이해가필요하다. C 언어에서주로쓰는함수는 malloc() 과 free() 함수이다. 74

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

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

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

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

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

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

슬라이드 1

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

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

슬라이드 1

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

More information

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

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

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

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

06장.리스트

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

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

untitled

untitled - -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front) A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top #define MAX_STACK_SIZE 100 int

More information

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt 배열이란? Chapter. 배열구조체포인터 같은형의변수를여러개만드는경우에사용 int A, A, A, A,, A; int A[]; 4 5 6 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i tmp ) tmp = score[i]; Today...

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

1장. 리스트

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

More information

Microsoft PowerPoint - 자료구조2008Chap06

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

More information

Microsoft PowerPoint - 제3장-배열.pptx

Microsoft PowerPoint - 제3장-배열.pptx 제 3 강. 배열 (Array) 자료구조 1 제 3 강. 배열자료구조 학습목차 1. 배열의개념 2. 구조체 3. 희소 (Sparce) 행렬 4. 다차원배열의저장 2 1. 배열의개념 리스트는일상생활에서가장많이쓰이는자료형태이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 배열 (Array) 은컴퓨터언어에서리스트를저장하는데이터타입이다. 리스트와배열은같은개념이지만다른차원의용어이다.

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

<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

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

02장.배열과 클래스

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

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

슬라이드 1

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

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

11장 포인터

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

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

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

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

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 - 제4장-스택과큐.pptx

Microsoft PowerPoint - 제4장-스택과큐.pptx 제 4 강의. 스택과큐자료구조 1 제 4 강. 스택과큐자료구조 학습목차 1. 스택과큐자료구조 2. 스택자료구조 3. 큐자료구조 4. 원형큐의구현 2 1. 스택 (Stack) 과큐자료구조 리스트, 스택과큐 (Stack and Queue) 스택과큐는리스트자료구조의특별한경우이다. 리스트 - 순서가있다 - 읽기, 삽입 (insert) 과삭제 (delete) 를리스트의어느곳에서나행함

More information

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

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

More information

Algorithms

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

More information

슬라이드 1

슬라이드 1 CHAP 3: 배열, 구조체, 포인터 C 로쉽게풀어쓴자료구조 Copyright 생능출판사 25 배열이란? 같은형의변수를여러개만드는경우에사용 int A, A, A2, A3,,A9; int A[]; 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i

More information

5.스택(강의자료).key

5.스택(강의자료).key CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.

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

슬라이드 1

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

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

4장

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

More information

슬라이드 1

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

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

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

More information

PowerPoint 프레젠테이션

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

More information

슬라이드 1

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

More information

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

금오공대 컴퓨터공학전공 강의자료 C 프로그래밍프로젝트 Chap 13. 포인터와배열! 함께이해하기 2013.10.02. 오병우 컴퓨터공학과 13-1 포인터와배열의관계 Programming in C, 정재은저, 사이텍미디어. 9 장참조 ( 교재의 13-1 은읽지말것 ) 배열이름의정체 배열이름은 Compile 시의 Symbol 로서첫번째요소의주소값을나타낸다. Symbol 로서컴파일시에만유효함 실행시에는메모리에잡히지않음

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

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - chap-11.pptx 쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.

More information

Microsoft PowerPoint - 제11장 포인터

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

More information

슬라이드 1

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

More information

슬라이드 1

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

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

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

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

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

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

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - 스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입

More information

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

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

More information

슬라이드 1

슬라이드 1 Array, Structure, and Pointer 2019 SANGJI University Kwang-Man Ko () 배열 (array) 이란? 같은형의변수를여러개만드는경우에사용 int A0, A1, A2, A3,,A9; int A[10]; 0 1 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램

More information

OCW_C언어 기초

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

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

설계란 무엇인가?

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

More information

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

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

More information

슬라이드 1

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

More information

61 62 63 64 234 235 p r i n t f ( % 5 d :, i+1); g e t s ( s t u d e n t _ n a m e [ i ] ) ; if (student_name[i][0] == \ 0 ) i = MAX; p r i n t f (\ n :\ n ); 6 1 for (i = 0; student_name[i][0]!= \ 0&&

More information

Microsoft PowerPoint - chap06-1Array.ppt

Microsoft PowerPoint - chap06-1Array.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-1 참고자료 배열 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 배열의선언과사용 같은형태의자료형이많이필요할때배열을사용하면효과적이다. 배열의선언 배열의사용 배열과반복문 배열의초기화 유연성있게배열다루기 한빛미디어

More information

Data Structure

Data Structure Function & Pointer C- 언어의활용을위한주요기법 (3) Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 함수의인자전달 함수의인자전달 함수의인자전달방식 인자전달의기본방식은복사다. 함수호출시전달되는값을매개변수를통해서전달받는데, 이때에값의복사가일어난다. int main(void) int val = 10;

More information

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

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.

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

슬라이드 1

슬라이드 1 CHAP 3: 배열, 구조체, 포인터 배열이란? 같은형의변수를여러개만드는경우에사용 int A, A1, A2, A3,,A9; int A[1]; 1 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=1;i tmp

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

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

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 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

Microsoft Word - FunctionCall

Microsoft Word - FunctionCall Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack

More information

Microsoft PowerPoint - 07-chap05-Stack.ppt

Microsoft PowerPoint - 07-chap05-Stack.ppt / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.

More information

ABC 10장

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

More information

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

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

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

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

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

More information

Algorithms

Algorithms 자료구조 & 알고리즘 스택과큐 (Stack and Queue) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 스택의개념및구현 큐의개념및구현 2 스택 스택의개념및구현 스택의구현 스택의응용 큐의개념및구현 3 스택 (Stack) 스택의구조 후입선출 (LIFO, Last-In-First-Out) 삽입 PUSH

More information

PowerPoint Template

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

More information

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 5 강. 배열, 포인터, 참조목차 배열 포인터 C++ 메모리구조 주소연산자 포인터 포인터연산 배열과포인터 메모리동적할당 문자열 참조 1 /20 5 강. 배열, 포인터, 참조배열 배열 같은타입의변수여러개를하나의변수명으로처리 int Ary[10]; 총 10 개의변수 : Ary[0]~Ary[9]

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 3. 배열, 구조체, 포인터 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 배열 배열 같은형의변수를여러개만드는경우에사용 int A, A1, A2, A3,,A9; int A[1]; 1 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램

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

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

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

PowerPoint Template

PowerPoint Template 10 포인터 1 주소 Address( 주소 ) 메모리에는그메모리의저장장소의위치를나타내는주소값 주소 (address) 는 1 바이트마다 1 씩증가하도록메모리에는연속적인번호가구성 2 주소연산자 & & 변수 변수의주소값을알아내려면변수앞에주소연산자 & (ampersand) 를이용 주소값이용장단점 주소값을이용하면보다편리하고융통성있는프로그램이가능 그러나복잡하고어려운단점

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

Microsoft PowerPoint - Chapter_08.pptx

Microsoft PowerPoint - Chapter_08.pptx 프로그래밍 1 1 Chapter 8. Pointers May, 2016 Dept. of software Dankook University http://embedded.dankook.ac.kr/~baeksj 포인터의개념 (1/6) 2 포인터란 : 다른객체를가리키는변수 객체의메모리주소를저장하는변수 기호적방식 (symbolic way) 으로주소사용 포인터와관련된연산자

More information

CHAP 3:배열, 구조체, 포인터

CHAP 3:배열, 구조체, 포인터 CHAP 3: 배열, 구조체, 포인터 배열 같은형의변수를여러개만들때 int A, A1, A2, A3,,A9; int A[1]; 1 2 3 4 5 6 7 8 9 언제배열을사용하면효율적인프로그래밍이되는가? - 반복코드를작성할때 예 ) 최대값을구하는프로그램. 만약배열이없었다면? max=score[]; for(i=1;i max)

More information

PowerPoint 프레젠테이션

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

More information

Microsoft PowerPoint - chap06-5 [호환 모드]

Microsoft PowerPoint - chap06-5 [호환 모드] 2011-1 학기프로그래밍입문 (1) chapter 06-5 참고자료 변수의영역과데이터의전달 박종혁 Tel: 970-6702 Email: jhpark1@seoultech.ac.kr h k 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- ehanbit.net 자동변수 지금까지하나의함수안에서선언한변수는자동변수이다. 사용범위는하나의함수내부이다. 생존기간은함수가호출되어실행되는동안이다.

More information

Microsoft PowerPoint - Chapter14_17.pptx

Microsoft PowerPoint - Chapter14_17.pptx Computer Engineering g Programming g 2 - 제 17 장동적메모리와연결리스트 - 제 14 장포인터활용 Lecturer: JUNBEOM YOO jbyoo@konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적할당메모리 연결리스트 이중포인터 포인터배열 다차원배열과포인터 main

More information

슬라이드 1

슬라이드 1 CHAP 5 : 스택 yicho@gachon.ac.kr 1 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 3 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분

More information