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

Size: px
Start display at page:

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

Transcription

1 연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조

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

3 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입 삭제연산이많이발생하는경우에성능상의문제발생 순차자료구조는배열을이용하여구현하기때문에배열이갖고있는메모리사용의비효율성문제를그대로가짐 순차자료구조에서의연산시간에대한문제와저장공간에대한문제를개선한자료표현방법필요 3

4 q 연결자료구조 v 연결자료구조 (Linked Data Structure) 자료의논리적인순서와물리적인순서가일치하지않는자료구조 각원소에저장되어있는다음원소의주소에의해순서가연결되는방식 Ø 물리적인순서를맞추기위한오버헤드가발생하지않는다. 여러개의작은공간을연결하여하나의전체자료구조를표현 Ø 크기변경이유연하고더효율적으로메모리사용 연결리스트 리스트를연결자료구조로표현한구조 연결하는방식에따라단순연결리스트와원형연결리스트, 이중연결리스트, 이중원형연결리스트 4

5 q 연결자료구조 v 노드 연결자료구조에서하나의원소를표현하기위한단위구조 < 원소, 주소 > 의구조 데이터필드 (data field) Ø 원소의값을저장 Ø 저장할원소의형태에따라서하나이상의필드로구성 링크필드 (link field) Ø 다음노드의주소를저장 Ø 포인터변수를사용하여주소값을저장 5

6 q 연결자료구조 노드연결방법에대한이해 - 기차놀이 1 이름표뽑기 2 자기가뽑은이름의사람을찾아서연결하기 : 희진 삼식 삼순 Ø X 표를뽑은사람은마지막기차 기차는이름표를들고있는방향으로움직인다. 6

7 q 연결자료구조 노드연결방법에대한이해 - 기차놀이 기차놀이와연결리스트 Ø 기차놀이하는아이들 : 연결리스트의노드 Ø 이름표 : 노드의링크필드 선형리스트와연결리스트의비교 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week 에대한선형리스트 7

8 q 연결자료구조 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week 에대한연결리스트 8

9 q 연결자료구조 리스트이름 week - 연결리스트의시작을가리키는포인터변수 Ø 포인터변수 week 는연결리스트의첫번째노드를가리키는동시에연결된 리스트전체를의미 연결리스트의마지막노드의링크필드 - 노드의끝을표시하기위해서 null( 널 ) 저장 공백연결리스트 - 포인터변수 week에 null을저장 ( 널포인터 ) 각노드의필드에저장한값은포인터의점연산자를사용하여액세스 Ø week.data : 포인터 week가가리키는노드의데이터필드값 월 Ø week.link : 포인터 week가가리키는노드의링크필드에저장된주소값 리스트 week 의노드에대한 C 프로그램구조체정의 typedef struct Node{ char data[4]; struct Node* link; }; 9

10 q 연결자료구조 리스트이름 week - 연결리스트의시작을가리키는포인터변수 Ø 포인터변수 week 는연결리스트의첫번째노드를가리키는동시에연결된 리스트전체를의미 연결리스트의마지막노드의링크필드 - 노드의끝을표시하기위해서 null( 널 ) 저장 공백연결리스트 - 포인터변수 week에 null을저장 ( 널포인터 ) 각노드의필드에저장한값은포인터의점연산자를사용하여액세스 Ø week.data : 포인터 week가가리키는노드의데이터필드값 월 Ø week.link : 포인터 week가가리키는노드의링크필드에저장된주소값 리스트 week 의노드에대한 C 프로그램구조체정의 typedef struct Node{ char data[4]; struct Node* link; }; 10

11 q 단순연결리스트 v 단순연결리스트 (singly linked list) 노드가하나의링크필드에의해서다음노드와연결되는구조를가진연결리스트 연결리스트, 선형연결리스트 (linear linked list), 단순연결선형리스트 (singly linked linear list) 예 ) 11

12 q 단순연결리스트 v 단순연결리스트의삽입 리스트 week2=( 월, 금, 일 ) 에서원소 월 과 금 사이에새원소 수 삽입하기 1 삽입할새노드를만들공백노드를메모리에서가져와서포인터변수 new 가가리키게한다. 2 new 의데이터필드에 수 를저장한다. 12

13 q 단순연결리스트 3 new 의앞노드, 즉 월 노드의링크필드값을 new 의링크필드에저장 week2 100번지 200번지 300번지 100 월 200 금 300 일 null new 번지 수 월 노드의링크필드에 new 의값 (new 가가리키고있는새노드의주소 ) 을저장 100번지 200번지 300번지 week2 100 월 150 금 300 일 null 150 번지 new 150 수

14 q 단순연결리스트 v 단순연결리스트의삭제 리스트 week2=( 월, 수, 금, 일 ) 에서원소 수 삭제하기 1 삭제할원소의앞노드 ( 선행자 ) 를찾는다. 2 앞노드의링크필드에, 삭제할원소 수 의링크필드값을저장한다. 100번지 200번지 300번지 week2 100 월 번지 금 300 일 null 수

15 q 단순연결리스트 v 자유공간리스트 (free space list) 사용하기전의메모리나사용이끝난메모리를관리하기위해노드 로구성하여연결한리스트 자유공간리스트에서대기중인노드들 사용중인노드들 15

16 q 단순연결리스트 자유공간리스트에서의노드할당알고리즘 getnode( ) if (Free = null) then underflow( ); // 언더플로우처리루틴 new Free; // ❶ Free Free.link; // ❷ return new; end getnode( ) [ 알고리즘 6-1] 16

17 q 단순연결리스트 자유공간리스트에서의노드할당과정 자유공간리스트 free 에서노드를할당할때는항상첫번째노드할당 초기상태 1 new Free; 리스트 free 의첫번째노드의주소를포인터 new 에저장하여포인터 new 가할당할 노드를가리키게한다. Free 번지 번지 번지 null new

18 q 단순연결리스트 2 Free Free.link; 포인터 free 에리스트의두번째노드의주소 (Free.link) 저장 Free 번지 200번지 300번지 null... new 100 이제자유공간리스트 free 의첫번째노드는리스트에서의미적으로분리된 상태이므로포인터 new 를반환 (return new;) 해줌으로써새노드를할당 18

19 q 단순연결리스트 자유공간리스트로의노드반환알고리즘 returnnode(old) old.link Free; // ❶ Free old; // ❷ end returnnode( ) [ 알고리즘 6-2] 자유공간리스트로의노드반환과정 반환되는노드는자유공간리스트 free 의첫번째노드로다시삽입 초기상태 19

20 q 단순연결리스트 1 old.link Free; 자유공간리스트 free 의첫번째노드주소를반환할노드포인터 old.link 에저장 하여포인터 old 의노드가리스트 free 의첫번째노드를가리키게한다. Free 번지 번지 null old 번지 Free old; 포인터 old 의값즉, 반환할노드의주소를포인터 free 에저장하여리스트 free 의첫번째노드로지정 Free 번지 번지 old 번지

21 q 단순연결리스트 v 단순연결리스트의삽입알고리즘 첫번째노드로삽입하기 returnnode(old) old.link Free; // ❶ Free old; // ❷ end returnnode( ) [ 알고리즘 6-3] 1 new getnode( ); 삽입할노드를자유공간리스트에서할당받는다. 21

22 q 단순연결리스트 2 new.data x; 새노드의데이터필드에 x 를저장 3 new.link L; 삽입할노드를연결하기위해서리스트의첫번째노드주소를삽입할새노드 new의링크필드에저장하여, 새노드 new가리스트의첫번째노드를가리키게한다. L 번지 번지 번지 null new 번지 x

23 q 단순연결리스트 4 L new; 리스트의첫번째노드주소를저장하고있는포인터 L 에, 새노드의주소를저장 하여, 포인터 L 이새노드를첫번째노드로가리키도록지정 L 번지 번지 번지 null new 번지 x

24 q 단순연결리스트 중간노드로삽입하기 리스트 L에서포인터변수 pre가가리키고있는노드의다음에데이터필드값이 x인새노드를삽입하는알고리즘 리스트의중간노드삽입알고리즘 insertmiddlenode(l, pre, x) new getnode( ); new.data x; if (L=null) then { // ❶ L new; // ❶-a new.link null; // ❶-b } else { // ❷ new.link pre.link; // ❷-a pre.link new; // ❷-b } end insertmiddlenode( ) [ 알고리즘 6-4] 24

25 q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 1 L new; 리스트포인터 L 에새노드 new 의주소를저장하여, 새노드 new 가리스트의첫번째노드가되게한다. L new 번지 x 2 new.link null; 리스트의마지막노드 new 의링크필드에 null 을저장하여마지막노드임을표시 L 700 new 번지 x null 25

26 q 단순연결리스트 Ø 리스트 L 이공백리스트가아닌경우 1 new.link pre.link; 노드 pre 의링크필드값을노드 new 의링크필드에저장하여, 새노드 new 가노드 pre 의다음노드를가리키도록한다. L 번지 200번지 번지 null pre 100 new 번지 x

27 q 단순연결리스트 2 pre.link new; 포인터 new 의값을노드 pre 의링크필드에저장하여, 노드 pre 가새노드 new 를 다음노드로가리키도록한다. L 번지 200번지 번지 null pre 100 new 번지 x

28 q 단순연결리스트 마지막노드로삽입하기 새노드 new 를마지막노드로삽입하는알고리즘 insertlastnode(l, x) new getnode(); new.data x; new.link null; if (L = null) then { L new; return; } temp L; while (temp.link null) do temp temp.link; temp.link new; end insertlastnode() // ❶-a // ❶-b // ❷-a // ❷-b // ❷-c [ 알고리즘 6-5] 28

29 q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 Ø [ 알고리즘 6-4] 에서공백리스트에노드를삽입하는연산과같은연산 Ø 삽입하는새노드 new 는리스트 L 의첫번째노드이자마지막노드 29

30 q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 1 temp L; 현재리스트 L 의마지막노드를찾기위해노드를순회할임시포인터 temp 에리스트의첫번째노드의주소를지정 L 번지 번지 번지 null temp while (temp.link null) do temp temp.link; while 반복문을수행하여순회포인터 temp가노드의링크필드를따라이동하면서링크필드가 null인마지막노드찾기수행 100번지 200번지 300번지 100 L null temp 100 temp 200 temp

31 q 단순연결리스트 3 temp.link new; 순회포인터 temp 가가리키는노드즉, 리스트의마지막노드의링크필드에삽입 할새노드 new 의주소를저장하여, 리스트의마지막노드가새노드 new 를연결 L 번지 번지 번지 700 temp 번지 new 700 x null 31

32 q 단순연결리스트 v 단순연결리스트의삭제알고리즘 리스트 L에서포인터 pre가가리키는노드의다음노드를삭제하는알고리즘 포인터 old : 삭제할노드 deletenode(l, pre) if (L = null) then error; else { old pre.link; if (old = null) then return; pre.link old.link; } returnnode(old); end deletenode( ) // ❶ // ❷ // ❷-a // ❸ // ❷-b // ❷-c [ 알고리즘 6-6] 32

33 q 단순연결리스트 Ø 리스트 L 이공백리스트가아닌경우 1 old pre.link; 노드 pre 의다음노드의주소를포인터 old 에저장하여, 포인터 old 가다음노드를가리키게한다. L 번지 번지 번지 번지 null pre 200 old

34 q 단순연결리스트 2 if (old = null) then return; 만약노드 pre 가리스트의마지막노드였다면 : Ø pre.link 의값은 null 이므로포인터 old 의값은 null 이된다. 결국노드 pre 다음의삭제할노드가없다는의미이므로삭제연산을수행하지못하고반환 (return). L 번지 번지 번지 null pre 300 old null 34

35 q 단순연결리스트 3 pre.link old.link; 삭제할노드 old 의다음노드 (old.link) 를노드 pre 의다음노드 (pre.link) 로연결 L 번지 번지 번지 번지 null pre 200 old returnnode(old); 삭제한노드 old 를자유공간리스트에반환 35

36 q 단순연결리스트 v 단순연결리스트의노드탐색알고리즘 리스트의노드를처음부터하나씩순회하면서노드의데이터필드 의값과 x 를비교하여일치하는노드를찾는연산 searchnode(l, x) temp L; while (temp null) do { if (temp.data = x ) then return temp; temp temp.link; } return temp; end searchnode() // ❶ // ❷ // ❸ [ 알고리즘 6-7] 36

37 q 단순연결리스트 단순연결리스트프로그램 001 public class Ex6_1{ [ 예제 6-1] 002 public static void main(string args[]){ 003 LinkedList L = new LinkedList(); 004 System.out.println("(1) 공백리스트에노드 3개삽입하기 "); 005 L.insertLastNode(" 월 "); 006 L.insertLastNode(" 수 "); 007 L.insertLastNode(" 일 "); 008 L.printList(); System.out.println("(2) 수노드뒤에금노드삽입하기 "); 011 ListNode pre = L.searchNode(" 수 "); 012 if(pre == null) 013 System.out.println(" 검색실패 >> 찾는데이터가없습니다."); 014 else{ 015 L.insertMiddleNode(pre, " 금 "); 016 L.printList(); 017 } 37

38 q 단순연결리스트 단순연결리스트프로그램 [ 예제 6-1] System.out.println("(3) 리스트의노드를역순으로바꾸기 "); 020 L.reverseList(); 021 L.printList(); System.out.println("(4) 리스트의마지막노드삭제하기 "); 024 L.deleteLastNode(); 025 L.printList(); 026 } 027 } class LinkedList{ 030 private ListNode head; 031 public LinkedList(){ 032 head = null; 033 } 034 public void insertmiddlenode(listnode pre, String data){ 035 ListNode newnode = new ListNode(data); 38

39 q 단순연결리스트 단순연결리스트프로그램 036 newnode.link = pre.link; 037 pre.link = newnode; 038 } 039 public void insertlastnode(string data){ 040 ListNode newnode = new ListNode(data); 041 if(head == null){ 042 this.head = newnode; 043 } 044 else{ 045 ListNode temp = head; 046 while(temp.link!= null) temp = temp.link; 047 temp.link = newnode; 048 } 049 } 050 public void deletelastnode(){ 051 ListNode pre, temp; 052 if(head == null) return; [ 예제 6-1] 39

40 q 단순연결리스트 단순연결리스트프로그램 053 if(head.link == null){ 054 head = null; 055 } 056 else{ 057 pre = head; 058 temp = head.link; 059 while(temp.link!= null){ 060 pre = temp; 061 temp = temp.link; 062 } 063 pre.link = null; 064 } 065 } 066 public ListNode searchnode(string data){ 067 ListNode temp = this.head; 068 while(temp!= null){ 069 if(data == temp.getdata()) [ 예제 6-1] 40

41 q 단순연결리스트 단순연결리스트프로그램 070 return temp; 071 else temp = temp.link; 072 } 073 return temp; 074 } 075 public void reverselist(){ 076 ListNode next = head; 077 ListNode current = null; 078 ListNode pre = null; 079 while(next!= null){ 080 pre = current; 081 current = next; 082 next = next.link; 083 current.link = pre; 084 } 085 head = current; 086 } [ 예제 6-1] 41

42 q 단순연결리스트 단순연결리스트프로그램 087 public void printlist(){ 088 ListNode temp = this.head; 089 System.out.printf("L = ("); 090 while(temp!= null){ 091 System.out.printf(temp.getData()); 092 temp = temp.link; 093 if(temp!= null){ 094 System.out.printf(", "); 095 } 096 } 097 System.out.println(")"); 098 } 099 } class ListNode{ 102 private String data; 103 public ListNode link; [ 예제 6-1] 42

43 q 단순연결리스트 단순연결리스트프로그램 104 public ListNode(){ 105 this.data = null; 106 this.link = null; 107 } 108 public ListNode(String data){ 109 this.data = data; 110 this.link = null; 111 } 112 public ListNode(String data, ListNode link){ 113 this.data = data; 114 this.link = link; 115 } 116 public String getdata(){ 117 return this.data; 118 } 119 } [ 예제 6-1] 43

44 q 원형연결리스트 v 원형연결리스트 (circular linked list) 단순연결리스트에서마지막노드가리스트의첫번째노드를가리키게하여리스트의구조를원형으로만든연결리스트 단순연결리스트의마지막노드의링크필드에첫번째노드의주소를저장하여구성 링크를따라계속순회하면이전노드에접근가능 100번지 200번지 300번지 L... 44

45 q 원형연결리스트 v 원형연결리스트의삽입연산 마지막노드의링크를첫번째노드로연결하는부분만제외하고는단순연결리스트에서의삽입연산과같은연산 첫번째노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를삽입하는알고리즘 insertfirstnode(cl, x) new getnode(); new.data x; if (CL = null) then { // ❶ CL new; // ❶-a new.link new; // ❶-b } else{ // ❷ temp CL; // ❷-a while (temp.link CL) do // ❷-b temp temp.link; [ 알고리즘 6-8] new.link temp.link; // ❷-c temp.link new; // ❷-d CL new; // ❷-e } end insertfirstnode() 45

46 q 원형연결리스트 Ø 원형리스트가공백리스트인경우 삽입하는노드 new 는리스트의첫번째노드이자마지막노드가되어야함 [ 초기상태 ] CL null new 번지 x 1 CL new; 포인터 CL 이노드 new 를가리키게한다. CL 700 new 번지 x 2 new.link new; 노드 new 가자기자신을가리키게함으로써노드 new 를첫번째노드이자마지막노드가되도록지정한다. CL 700 new 번지 x

47 q 원형연결리스트 Ø 원형리스트가공백리스트가아닌경우 1 temp CL; 리스트가공백리스트가아닌경우에는첫번째노드의주소를임시순회포인터 temp 에저장하여노드순회의시작점을지정한다. CL 번지 200번지 300번지 temp 2 while (temp.link CL) do temp temp.link; while 반복문을수행하여순회포인터 temp 를링크를따라마지막노드까지이동 CL 번지 번지 번지 temp 200 temp 300 temp 47

48 q 원형연결리스트 3 new.link temp.link; 리스트의마지막노드의링크값을노드 new 의링크에저장하여, 노드 new 가노드 temp 의다음노드를가리키게한다. 리스트 CL 은원형연결리스트이므로마지막노드의다음노드는리스트의첫번째노드가된다. CL 번지 200번지 300번지 번지 new 700 x temp 4 temp.link new; 포인터 new 의값을포인터 temp 가가리키고있는마지막노드의링크에저장하여, 리스트의마지막노드가노드 new 를가리키게한다. CL 번지 200번지 300번지 700번지 new 700 x temp

49 q 원형연결리스트 5 CL new; 노드 new 의주소를리스트포인터 CL 에저장하여노드 new 가리스트의첫번째노드가되도록지정 CL 번지 번지 번지 번지 new 700 x temp [ 알고리즘 6-8] 실행결과 CL 번지 x 번지 번지 번지

50 q 원형연결리스트 중간노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를포인터 pre 가가리키는 노드의다음노드로삽입하는알고리즘 insertmiddlenode(cl, pre, x) new getnode(); new.data x; if (CL=null) then { // ❶ CL new; new.link new; } else { // ❷ new.link pre.link; // ❷-a pre.link new; // ❷-b } end insertmiddlenode() [ 알고리즘 6-9] 50

51 q 원형연결리스트 1 new.link pre.link; 노드 pre 의다음노드로 new 를삽입하기위해서, 먼저노드 pre 의다음노드 (pre.link) 를 new 의다음노드 (new.link) 로연결 CL 번지 200 번지 300 번지 번지 100 pre 200 new 번지 x

52 q 원형연결리스트 2 pre.link new; 노드 new 의주소를노드 pre 의링크에저장하여, 노드 pre 가노드 new 를가리키 도록한다. CL 번지 번지 300 번지 번지 100 pre 200 new 번지 x

53 q 원형연결리스트 v 원형연결리스트의삭제연산 원형연결리스트 CL에서포인터 pre가가리키는노드의다음노드를삭제하고삭제한노드는자유공간리스트에반환하는연산 포인터 old 는삭제할노드지시 deletenode(cl, pre) if (CL = null) then error; else { old pre.link; // ❶ pre.link old.link; // ❷ if (old = CL) then // ❸ CL old.link; // ❸-a returnnode(old); // ❹ } end deletenode() [ 알고리즘 6-10] 53

54 q 원형연결리스트 1 old pre.link; 노드 pre 의다음노드를삭제할노드 old 로지정 CL 번지 번지 300 번지 번지 100 pre 200 old pre.link old.link; 노드 old 의이전노드와다음노드를서로연결 CL 번지 200 번지 300 번지 번지 100 pre 200 old

55 q 원형연결리스트 Ø 삭제할노드 old 가리스트포인터 CL 인경우 1 CL old.link; 첫번째노드를삭제하는경우에는노드 old 의링크값을리스트포인터 CL 에저장하여두번째노드가리스트의첫번째노드가되도록조정 CL 번지 번지 300 번지 번지 200 old 100 pre

56 q 이중연결리스트 v 이중연결리스트 (doubly linked list) 양쪽방향으로순회할수있도록노드를연결한리스트 이중연결리스트의노드구조 두개의링크필드와한개의데이터필드로구성 llink(left link) 필드 : 왼쪽노드와연결하는포인터 rlink(right link) 필드 : 오른쪽노드와연결하는포인터 노드구조에대한구조체정의 public class DblNode{ DblNode llink; String data; DblNode rlink; } ; 56

57 q 이중연결리스트 단순연결기차 이중연결기차 57

58 q 이중연결리스트 리스트 week=( 월, 수, 금 ) 의이중연결리스트구성 원형이중연결리스트 이중연결리스트를원형으로구성 58

59 q 이중연결리스트 양방향기차만들기준비 59

60 q 이중연결리스트 양방향기차만들기 1 : 왼쪽사람의오른손이름표받기 60

61 q 이중연결리스트 양방향기차만들기 1 : 왼쪽사람에게자기이름주기 61

62 q 이중연결리스트 양방향기차만들기 2 : 오른쪽사람의왼손이름표받기 62

63 q 이중연결리스트 양방향기차만들기 2 : 오른쪽사람에게자기이름주기 63

64 q 이중연결리스트 양방향기차만들기 : 완성 64

65 q 이중연결리스트 이중연결리스트에서의삽입연산과정 ❶ 삽입할노드를가져온다. ❷ 새노드의데이터필드에값을저장한다. ❸ 새노드의왼쪽노드의오른쪽링크 (rlink) 를새노드의오른쪽링크 (rlink) 에저장한다. ❹ 그리고왼쪽노드의오른쪽링크 (rlink) 에새노드의주소를저장한다. ❺ 새노드의오른쪽노드의왼쪽링크 (llink) 를새노드의왼쪽링크 (llink) 에저장한다. ❻ 그리고오른쪽노드의왼쪽링크 (llink) 에새노드의주소를저장한다. 65

66 q 이중연결리스트 이중연결리스트에서의삽입알고리즘 insertnode(dl, pre, x) new getnode(); new.data x; new.rlink pre.rlink ; pre.rlink new; new.llink pre; new.rlink.llink new; end insertnode() // ❶ // ❷ // ❸ // ❹ [ 알고리즘 6-11] 66

67 q 이중연결리스트 이중연결리스트 DL 에서포인터 pre 가가리키는노드의다음노드 로노드 new 를삽입하는과정 초기상태 67

68 q 이중연결리스트 1 new.rlink pre.rlink ; 노드 pre 의 rlink 를노드 new 의 rlink 에저장하여, 노드 pre 의오른쪽노드를삽입 할노드 new 의오른쪽노드로연결 68

69 q 이중연결리스트 2 pre.rlink new; 새노드 new 의주소를노드 pre 의 rlink 에저장하여, 노드 new 를노드 pre 의오른 쪽노드로연결 69

70 q 이중연결리스트 3 new.llink pre; 포인터 pre 의값을삽입할노드 new 의 llink 에저장하여, 노드 pre 를노드 new 의 왼쪽노드로연결 70

71 q 이중연결리스트 4 new.rlink.llink new; 포인터 new 의값을노드 new 의오른쪽노드 (new.rlink) 의 llink 에저장하여, 노드 new 의오른쪽노드의왼쪽노드로노드 new 를연결 71

72 q 이중연결리스트 삭제 : 오른손이름표넘겨주기 72

73 q 이중연결리스트 삭제 : 왼손이름표넘겨주기 73

74 q 이중연결리스트 삭제완료 74

75 q 이중연결리스트 이중연결리스트에서의삽입연산과정 ❶ 삭제할노드의오른쪽노드의주소 (old.rlink) 를삭제할노드의왼쪽노드 (old.llink) 의오른쪽링크 (rlink) 에저장한다. ❷ 삭제할노드의왼쪽노드의주소 (old.llink) 를삭제할노드의오른쪽노드 (old.rlink) 의왼쪽링크 (llink) 에저장한다. ❸ 삭제한노드를자유공간리스트에반환한다. 이중연결리스트에서의삭제알고리즘 deletenode(dl, old) old.llink.rlink old.rlink; // ❶ old.rlink.llink old.llink; // ❷ returnnode(old); // ❸ end deletenode( ) [ 알고리즘 6-12] 75

76 q 이중연결리스트 이중연결리스트 DL 에서포인터 old 가가리키는노드를삭제하는 과정 초기상태 76

77 q 이중연결리스트 1 old.llink.rlink old.rlink; 삭제할노드 old 의오른쪽노드의주소를노드 old 의왼쪽노드의 rlink 에저장하여, 노드 old 의오른쪽노드를노드 old 의왼쪽노드의오른쪽노드로연결 77

78 q 이중연결리스트 2 old.rlink.llink old.llink; 삭제할노드 old 의왼쪽노드의주소를노드 old 의오른쪽노드의 llink 에저장하여, 노드 old 의왼쪽노드를노드 old 의오른쪽노드의왼쪽노드로연결 78

79 q 이중연결리스트 3 returnnode(old); 삭제된노드 old 는자유공간리스트에반환 79

80 q 다항식의연결자료구조표현 v 단순연결리스트를이용하여다항식표현 다항식의항 : 단순연결리스트의노드 노드구조 각항에대해서계수와지수를저장 계수를저장하는 coef 와지수를저장하는 expo 의두개의필드로구성 링크필드 : 다음항을연결하는포인터로구성 노드에대한구조체정의 public class Node { float coef; int expo; Node link; }; 80

81 q 다항식의연결자료구조표현 다항식의단순연결리스트표현예 다항식 A(x)=4x 3 +3x 2 +5x 다항식 B(x)=3x 4 +x 3 +2x+1 81

82 q 다항식의연결자료구조표현 v 다항식연결자료구조의삽입연산 다항식에항을추가하는알고리즘 Ø 다항식리스트포인터 PL, coef 필드값을저장한변수 coef, expo 필드값을저장한변수 expo 리스트 PL 의마지막노드의위치를지시하는포인터 last 사용 appendterm(pl, coef, expo, last) new getnode( ); new.expo expo; new.coef coef; new.link null; if (PL = null) then { // ❶ PL new; // ❶-a last new; // ❶-b } else { // ❷ last.link new; // ❷-a last new; // ❷-b } end appendterm( ) [ 알고리즘 6-13] 82

83 q 다항식의연결자료구조표현 공백다항식에서의항삽입연산 초기상태 1 PL new; 포인터 new 의값을리스트포인터 PL 에저장하여, 노드 new 가리스트 PL 의첫번째노드가되도록연결 2 last new; 포인터 new 의값을포인터 last 에저장하여, 포인터 last 가리스트 PL 의마지막노드인노드 new 를가리키도록지정 83

84 q 다항식의연결자료구조표현 다항식에서의항삽입연산 초기상태 1 last.link new; 포인터 new 의값을노드 last 의링크에저장하여, 노드 new 를노드 last 의다음 노드로연결 84

85 q 다항식의연결자료구조표현 2 last new; 포인터 new 의값을포인터 last 에저장하여, 노드 new 를리스트 PL 의마지막노 드로지정 85

86 q 다항식의연결자료구조표현 다항식리스트 A 에 appendterm() 알고리즘을사용하여 2x 0 항 ( 상수항 2) 추가예 86

87 q 다항식의연결자료구조표현 v 다항식의덧셈연산 덧셈 A +B =C 를단순연결리스트자료구조로연산 Ø 다항식 A 와 B, C 의항을지시하기위해서세개의포인터를사용 Ø 포인터 p : 다항식 A 에서비교할항을지시 Ø 포인터 q : 다항식 B 에서비교할항을지시 Ø 포인터 r : 덧셈연산결과만들어지는다항식 C 의항을지시 1 p.expo < q.expo : 다항식 A 항의지수가작은경우 포인터 q 가가리키는다항식 B 의항을 C 의항으로복사 q 가가리키는항에대한처리가끝났으므로 q 를다음노드로이동 87

88 q 다항식의연결자료구조표현 88

89 q 다항식의연결자료구조표현 2 p.expo = q.expo : 두항의지수가같은경우 p.coef와 q.coef를더하여 C 의항, 즉 r.coef에저장하고지수가같아야하므로 p.expo( 또는 q.expo) 를 r.expo에저장 다음항을비교하기위해포인터 p와 q를각각다음노드로이동 89

90 q 다항식의연결자료구조표현 3 p.expo > q.expo : 다항식 A 항의지수가큰경우 포인터 p 가가리키는다항식 A 의항을 C 의항으로복사 p 가가리키는항에대한처리가끝났으므로 p 를다음노드로이동 90

91 q 다항식의연결자료구조표현 다항식의덧셈알고리즘 addpoly(a, B) [ 알고리즘 6-14] // 단순연결리스트로표현된다항식 A와 B를더하여새로운다항식 C를반환 p A; q B; C null; // 결과다항식 r null; // 결과다항식의마지막노드를지시 while (p null and q null) do { // p, q는순회용참조변수 case { p.expo = q.expo : sum p.coef + q.coef if (sum 0) then appendterm(c, sum, p.expo, r); p p.link; q q.link; p.expo < q.expo : appendterm(c, q.coef, q.expo, r); q q.link; 91

92 q 다항식의연결자료구조표현 다항식의덧셈알고리즘 else : // p.expo > q.expo인경우 appendterm(c, p.coef, p.expo, r); p p.link; } // end case } // end while [ 알고리즘 6-14] while (p null) do { // A의나머지항들을 C에복사 appendterm(c, p.coef, p.expo, r); p p.link; } while (q null) do { // B의나머지항들을 C에복사 appendterm(c, q.coef, q.expo, r); q q.link; } return C; end addpoly() 92

93 q 다항식의연결자료구조표현 다항식의덧셈예 A(x)=4x 3 +3x 2 +5x B(x)=3x 4 +x 3 +2x+1 초기상태 93

94 q 다항식의연결자료구조표현 1 4x 3 항과 3x 2 항에대한처리 p.expo < q.expo 이므로지수가큰 q 노드를리스트 C 에복사 포인터 q 는다음노드로이동 94

95 q 다항식의연결자료구조표현 2 4x 3 항과 1x 3 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드를리스트 C 에추가 포인터 p 와 q 는다음노드로이동 95

96 q 다항식의연결자료구조표현 3 3x 2 항과 2x 1 항에대한처리 p.expo > q.expo 이므로지수가큰 p 노드를리스트 C 에복사 포인터 p 는다음노드로이동 96

97 q 다항식의연결자료구조표현 4 5x 1 항과 2x 1 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드를리스트 C 에추가 포인터 p 와 q 는다음노드로이동 97

98 q 다항식의연결자료구조표현 5 B(x) 의남은항에대한처리 포인터 p가 null이므로다항식 A 의항에대한처리끝 처리할항이남아있는다항식 B 의포인터 q는 null이될때까지모든노드를복사하여리스트 C에추가 98

99 IT CookBook 자바로배우는쉬운자료구조 6 장끝

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

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

More information

Algorithms

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

More information

슬라이드 1

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

More information

06장.리스트

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

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

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

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

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

리스트 (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

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

More information

슬라이드 1

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

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

Microsoft PowerPoint - chap4_list

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

More information

11장 포인터

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

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

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

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

More information

슬라이드 1

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

More information

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

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

More information

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

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

More information

슬라이드 1

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

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

슬라이드 1

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

More information

슬라이드 1

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

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

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

Microsoft PowerPoint - 자료구조2008Chap06

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

More information

슬라이드 1

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

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

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

중간고사 (자료 구조)

중간고사 (자료 구조) 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

Microsoft PowerPoint - ch08_큐 [호환 모드]

Microsoft PowerPoint - ch08_큐 [호환 모드] 큐 (Queue) 자바로배우는쉬운자료구조 이장에서다룰내용 1 큐 2 큐의구현 3 큐의응용 2 큐 (1) 큐 (Queue) 스택과마찬가지로삽입과삭제의위치가제한된유한순서리스트 큐의뒤에서는삽입만하고, 앞에서는삭제만할수있는구조 삽입한순서대로원소가나열되어가장먼저삽입 (First-In) 한원소는맨앞에있다가가장먼저삭제 (First-Out) 된다. 선입선출구조 (FIFO,

More information

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

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

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

4장. 순차자료구조

4장. 순차자료구조 순차자료구조방식 자바로배우는쉬운자료구조 이장에서다룰내용 1 선형리스트 2 선형리스트의구현 3 다항식의순차자료구조표현 4 행렬의순차자료구조표현 2 선형리스트 (1) 리스트 (List) 자료를나열한목록 ( 집합 ) 리스트의예 3 선형리스트 (2) 선형리스트 (Linear List) 순서리스트 (Ordered List) 자료들간에순서를갖는리스트 선형리스트의예 4

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

02장.배열과 클래스

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

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

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

슬라이드 1

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

More information

01_List

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

More information

Microsoft PowerPoint - ch07_스택 [호환 모드]

Microsoft PowerPoint - ch07_스택 [호환 모드] 스택 (Stack) 자바로배우는쉬운자료구조 이장에서다룰내용 1 스택 2 스택의추상자료형 3 스택의구현 4 스택의응용 2 스택 (1) 스택 (stack) 접시를쌓듯이자료를차곡차곡쌓아올린형태의자료구조 스택에저장된원소는 top 으로정한곳에서만접근가능 top 의위치에서만원소를삽입하므로먼저삽입한원소는밑에쌓이고, 나중에삽입한원소는위에쌓인다. 마지막에삽입 (Last-In)

More information

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

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

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

PowerPoint 프레젠테이션

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

More information

PowerPoint Presentation

PowerPoint Presentation 자바프로그래밍 1 배열 손시운 ssw5176@kangwon.ac.kr 배열이필요한이유 예를들어서학생이 10 명이있고성적의평균을계산한다고가정하자. 학생 이 10 명이므로 10 개의변수가필요하다. int s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; 하지만만약학생이 100 명이라면어떻게해야하는가? int s0, s1, s2, s3, s4,

More information

q 이장에서다룰내용 1 객체지향프로그래밍의이해 2 객체지향언어 : 자바 2

q 이장에서다룰내용 1 객체지향프로그래밍의이해 2 객체지향언어 : 자바 2 객체지향프로그래밍 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 객체지향프로그래밍의이해 2 객체지향언어 : 자바 2 q 객체지향프로그래밍의이해 v 프로그래밍기법의발달 A 군의사업발전 1 단계 구조적프로그래밍방식 3 q 객체지향프로그래밍의이해 A 군의사업발전 2 단계 객체지향프로그래밍방식 4 q 객체지향프로그래밍의이해 v 객체란무엇인가

More information

설계란 무엇인가?

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

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

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

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 - 제11장 포인터

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

More information

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

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

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

슬라이드 1

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 @ Lesson 3 if, if else, if else if, switch case for, while, do while break, continue : System.in, args, JOptionPane for (,, ) @ vs. logic data method variable Data Data Flow (Type), ( ) @ Member field

More information

PowerPoint Presentation

PowerPoint Presentation 객체지향프로그래밍 클래스, 객체, 메소드 ( 실습 ) 손시운 ssw5176@kangwon.ac.kr 예제 1. 필드만있는클래스 텔레비젼 2 예제 1. 필드만있는클래스 3 예제 2. 여러개의객체생성하기 4 5 예제 3. 메소드가추가된클래스 public class Television { int channel; // 채널번호 int volume; // 볼륨 boolean

More information

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

Microsoft PowerPoint - 제6장-연결리스트.pptx 제 6 강의. 연결리스트 1. 포인터타입 2. 단순연결리스트 3. 연결리스트를이용한스택의구현 4. 연결리스트를이용한큐의구현 5. 리스트구현방법의정리 1 리스트자료구조 데이터연산설명 스택 int stack[100]; (10, 30, 40, 20) push(35); y=pop(); 삽입과삭제가한쪽끝 큐 int queue[100]; (10, 30, 40, 20)

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

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7> 한국방송통신대학교컴퓨터과학과 2 학년자료구조 제 1 장기본개념 자료와정보 3 알고리즘 4 자료 data : 현실세계에서관찰이나측정을통해수집된값 value 이나사실 fact 특정한일을수행하는명령어들의유한집합 정보 information : 자료를처리 / 추출 process 해서얻어진유용한결과 입 출 력 : 외부에서제공되는자료가있을수있다력 : 적어도한가지결과를생성한다

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

11장 포인터

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

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

PowerPoint 프레젠테이션

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

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

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 @ Lesson 2... ( ). ( ). @ vs. logic data method variable behavior attribute method field Flow (Type), ( ) member @ () : C program Method A ( ) Method B ( ) Method C () program : Java, C++, C# data @ Program

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

Microsoft PowerPoint - chap-11.pptx

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

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

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

[ 마이크로프로세서 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

e-비즈니스 전략 수립

e-비즈니스 전략 수립 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:

More information

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 (   ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각 JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( http://java.sun.com/javase/6/docs/api ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각선의길이를계산하는메소드들을작성하라. 직사각형의가로와세로의길이는주어진다. 대각선의길이는 Math클래스의적절한메소드를이용하여구하라.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 3. 트리 3.1 트리의개요 3.2 이진트리 3.3 트리의운행 3.1 트리의개요 트리 : 그래프의일종 데이터 : 노드 순환적정의 T = {R, T 1,T 2, T n } R : 루트 T i : 서브-트리 ( 트리 ) 3.1 트리의개요 1. 노드 2. 근노드 3. 서브트리 4. 차수 5. 단노드 6. 간노드 (nonterminal node) 7. 부-노드,

More information

JAVA PROGRAMMING 실습 08.다형성

JAVA PROGRAMMING 실습 08.다형성 2015 학년도 2 학기 1. 추상메소드 선언은되어있으나코드구현되어있지않은메소드 abstract 키워드사용 메소드타입, 이름, 매개변수리스트만선언 public abstract String getname(); public abstract void setname(string s); 2. 추상클래스 abstract 키워드로선언한클래스 종류 추상메소드를포함하는클래스

More information

Microsoft PowerPoint 자바-기본문법(Ch2).pptx

Microsoft PowerPoint 자바-기본문법(Ch2).pptx 자바기본문법 1. 기본사항 2. 자료형 3. 변수와상수 4. 연산자 1 주석 (Comments) 이해를돕기위한설명문 종류 // /* */ /** */ 활용예 javadoc HelloApplication.java 2 주석 (Comments) /* File name: HelloApplication.java Created by: Jung Created on: March

More information

설계란 무엇인가?

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

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

슬라이드 1

슬라이드 1 Recursion SANGJI University KO Kwangman () 1. 개요 재귀 (recursion) 의정의, 순환 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로되어있는경우에적합한방법 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 실습 1 배효철 th1g@nate.com 1 목차 조건문 반복문 System.out 구구단 모양만들기 Up & Down 2 조건문 조건문의종류 If, switch If 문 조건식결과따라중괄호 { 블록을실행할지여부결정할때사용 조건식 true 또는 false값을산출할수있는연산식 boolean 변수 조건식이 true이면블록실행하고 false 이면블록실행하지않음 3

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

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

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

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

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node

More information

쉽게 풀어쓴 C 프로그래밊

쉽게 풀어쓴 C 프로그래밊 Power Java 제 27 장데이터베이스 프로그래밍 이번장에서학습할내용 자바와데이터베이스 데이터베이스의기초 SQL JDBC 를이용한프로그래밍 변경가능한결과집합 자바를통하여데이터베이스를사용하는방법을학습합니다. 자바와데이터베이스 JDBC(Java Database Connectivity) 는자바 API 의하나로서데이터베이스에연결하여서데이터베이스안의데이터에대하여검색하고데이터를변경할수있게한다.

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

PowerPoint 프레젠테이션

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

More information

PowerPoint Template

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

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

Chap 6: Graphs

Chap 6: Graphs 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1) 5.1 AOV

More information

<4D F736F F F696E74202D20C1A63038C0E520C5ACB7A1BDBABFCD20B0B4C3BC4928B0ADC0C729205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D20C1A63038C0E520C5ACB7A1BDBABFCD20B0B4C3BC4928B0ADC0C729205BC8A3C8AF20B8F0B5E55D> Power Java 제 8 장클래스와객체 I 이번장에서학습할내용 클래스와객체 객체의일생직접 메소드클래스를 필드작성해 UML 봅시다. QUIZ 1. 객체는 속성과 동작을가지고있다. 2. 자동차가객체라면클래스는 설계도이다. 먼저앞장에서학습한클래스와객체의개념을복습해봅시다. 클래스의구성 클래스 (class) 는객체의설계도라할수있다. 클래스는필드와메소드로이루어진다.

More information

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될

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

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

PowerPoint Presentation

PowerPoint Presentation Package Class 3 Heeseung Jo 목차 section 1 패키지개요와패키지의사용 section 2 java.lang 패키지의개요 section 3 Object 클래스 section 4 포장 (Wrapper) 클래스 section 5 문자열의개요 section 6 String 클래스 section 7 StringBuffer 클래스 section

More information