Chap 6: Graphs
|
|
- 대건 강
- 5 years ago
- Views:
Transcription
1 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page )
2 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v] = 무방향성그래프 : A[][] 는대칭행렬 방향성그래프 : A[][] 는비대칭행렬 대칭행렬 : A[n(n-)/] 로구현가능 6 장. 그래프 (Page )
3 인접리스트 (Adjacency List) 인접행렬의 n 행들을 n 개의연결리스트로표현 즉, 그래프 G 의각 vertex 에대해한개의연결리스트가존재 headnodes vertex link null null null null null null null 6 장. 그래프 (Page )
4 인접다중리스트 (Adjacency Multilist) Edge 별로하나의노드를할당 각 edge 를검사했다는표시를나타내는데용이 marked vertex vertex path path headnodes N N N4 N N N4 N null N5 edge(, ) edge(, ) edge(, ) N4 N5 N6 edge(, ) The lists are: vertex : N N N vertex : N N4 N5 vertex : N N4 N6 vertex : N N5 N6 N5 null N6 N6 null null edge(, ) edge(, ) 6 장. 그래프 (Page 4)
5 그래프표현방법들의분석 G 에존재하는 edge 수? 혹은 G 가연결되었는지검사. 인접행렬 : n(n )/ 개의항을조사 O(n ) 인접리스트 : O(n+e) Good if e << n / (sparse graphs) Digraph 에서 vertex 의 in-degree 를조사 인접행렬 : O(n) 인접리스트 : O(n+e) 역인접리스트 (inverse adjacency list) 를별도유지 in-degree 와 out-degree 를모두표현할수있는인접리스트구조를구현 ( 그림 6.) tail head column link for head row link for tail null null null 6 장. 그래프 (Page 5)
6 Orthogonal Representation of G Headnodes (shown twice) row column NULL NULL NULL NULL NULL NULL tail head 6 장. 그래프 (Page 6)
7 . 기초적인그래프연산들. 깊이우선탐색 (Depth First Search). 너비우선탐색 (Breadth First Search). 연결요소 (Connected Components) 4. 신장트리 (Spanning Trees) 5. 이중결합요소와단절점 (Biconnected Components and Articulation Points) 6 장. 그래프 (Page 7)
8 . Depth First Search 알고리즘 출발 vertex, v 의인접리스트부터방문 v 에인접하면서아직방문하지않은 vertex, w 를선택 w 를시작점으로하여다시깊이우선탐색시작 recursion 을이용하여구현 #define FALSE #define TRUE short int visited[max_vertices]; void dfs(int v) { struct node *w; visited[v] = TRUE; printf("%5d", v); for (w = graph[v]; w; w = w link) if (!visited[w vertex]) dfs(w vertex); } 6 장. 그래프 (Page 8)
9 Depth First Search 의동작과정 struct node *graph[]; struct node { int vertex; struct node *link}; V null 4 null V V 5 6 null V V 4 V 5 V V null depth first search order : v, v, v, v 7, v 4, v 5, v, v 6 6 장. 그래프 (Page 9)
10 . Breadth First Search 알고리즘 출발 vertex, v 의인접리스트부터방문 v 에인접한모든 vertex 들을먼저방문 그다음, v 에인접한첫번째 vertex 에인접한 vertex 중에서아직방문하지않은 vertex 들을다시차례대로방문 (Queue 를이용 ) struct queue { int vertex; struct queue *link; }; void addq(.); int deleteq(.); 6 장. 그래프 (Page )
11 Program 6.: Breadth First Search void bfs(int v) { // Vertex v부터탐색수행. visited[] 배열은 FALSE로초기화. 큐를사용 node_pointer w; struct queue *front = NULL, *rear = NULL; printf("%5d", v); visited[v] = TRUE; addq(&front, &rear, v); while (front) { v = deleteq(&front); for (w = graph[v]; w; w = w link) if (!visited[w vertex]) { printf("%5d", w vertex); addq(&front, &rear, w vertex); visited[w vertex] = TRUE; } } } 6 장. 그래프 (Page )
12 Breadth First Search 의동작과정 V V V V V 4 V 5 V 6 V null null 6 null 5 6 null breadth first search order : v, v, v, v, v 4, v 5, v 6, v 7 6 장. 그래프 (Page )
13 . Connected Components 무방향성그래프가연결되어있는지검사? dfs() 나 bfs() 를호출한후, 방문되지않은 vertex 가존재하는지를검사 그래프의 connected component 들을출력? void connected (void) { /* determine the connected components of a graph */ int i for (i = ; i < n; i++) if (!visited[i]) { dfs(i); printf("\ n"); } } 6 장. 그래프 (Page )
14 .4 Spanning Trees 정의 그래프 G 에포함된 edge 들로구성되며, G 의모든 vertex 들을포함하는트리 DFS 나 BFS 를이용하여 spanning tree 구성 Depth first spanning tree Breadth first spanning tree V V V V V V V V 4 V 5 V 6 V V 4 V 5 V 6 V 7 depth first spanning tree V 7 breadth first spanning tree 6 장. 그래프 (Page 4)
Microsoft PowerPoint - 제10장-그래프.pptx
제 강의. 그래프개념과그래프탐색 학습목차. 그래프의개념. 그래프의표현. 그래프탐색 . 그래프의개념 graph? chart? 오래된그래프문제로다음과 Köenigsberg 다리문제가있다. 이문제는다음과같은지형이있을때임의의한곳 (A,B,C,D) 에서출발하여 a 부터 f 까지 모든다리를한번씩건널수있는가? 하는문제이다. 자료구조의그래프는이러한문제를컴퓨터에표현하고알고리즘을개발하는분야이다.
More informationMicrosoft PowerPoint - ch12 - Graph, Graph Algorithms
그래프탐색 (Graph Search) 그래프의가장기본적인연산 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 많은문제들이단순히그래프의노드를탐색하는것으로해결 ( 예 ) 도로망에서특정도시에서다른도시로갈수있는지여부 ( 예 ) 전자회로에서특정단자와다른단자가서로연결되어있는지여부 ch12-44 깊이우선탐색 (DFS) 깊이우선탐색 (DFS: depth-first search)
More information11장.그래프
---------------- T STRUTURS USIN ---------------- PTR 그래프 1/32 그래프 (graph) 란? 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 그래프의예 트리 (tree) 지도, 지하철노선도 전기회로의연결상태 OS의프로세스와자원관계 인맥지도 2/32 그래프역사 오일러문제 (1800 년대 ) 다리를한번만건너서처음출발했던장소로돌아오는문제
More informationChap 6: Graphs
AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node
More informationChap 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슬라이드 1
CHAP 10: 그래프 C 로쉽게풀어쓴자료구조 생능출판사 2005 그래프 그래프 (graph): 연결되어있는객체간의관계를표현하는자료구조 그래프의예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 그래프 : 아주일반적인자료구조 ( 예 ) 트리도그래프의일종으로볼수있다. 그래프이론 (graph theory): 그래프를문제해결의도구로이용하는연구분야 그래프역사 1800
More information5장 스택
강의내용 오늘강의내용 ( 월 7 일 ) 중갂고사문제풀이 9. 그래프의숚회. 최소비용신장트리 ( 가중치그래프 ) 예습 ( 월 일 ) : 장가중치그래프 ( 계속 ) 숙제 : 연습문제 (9 장 ) :,,,,,7,8, 번풀어보기 마감일 : 9 년 월 일 ( 화 ) 9. 그래프숚회 그래프숚회 주어진어떤정점을출발하여체계적으로그래프의모든정점들을방문하는것 그래프숚회의종류
More informationMicrosoft PowerPoint - ch12 - Graph, Graph Algorithms
2015-1 12. 그래프와관련알고리즘 2015 년 5 월 28 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 그래프 (Graph) 그래프의응용예 Outline 미로찾기 인터넷라우터에서의패킷 forwarding
More information제 6 장 그래프
제 장 그래프 Copyright DBLAB, Seoul National University 그래프추상데이타타입 () 개요.. Koenigsberg 다리문제 차수 (degree) : 정점에연결된간선의수 오일러행로 (Eulerian walk) c C d g a A Kneiphof B e b D f c a C A B d b e g f D (a) Koenigsberg
More informationWISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores
프로젝트정리 1주차 : 미로를텍스트파일로만들어출력하는프로그램작성. 2주차 : 텍스트형태의미로를 MC의그래픽기능을이용하여그리는프로그램작성. 3주차 : 미로에서길찾는프로그램작성. Dept. of CS, Sogang Univ. 1 DS를이용한미로길찾기문제 DS를이용한미로길찾기문제는 2주차까지설계한미로의출발점과도착점을연결하는가장짧은경로를탐색해출력하는문제이다. NxM
More information1장. 리스트
01. 그래프를소개합니다 02. 그래프를어떻게표현할것인가? 03. 그래프순회 : 그래프를따라산책하기 04. 최소신장트리 05. 최단경로탐색 06. 위상정렬 라인하르트오일러가 쾨니히스베르크의 7 개의다리문제 를풀기위해고안해낸수학적도구. 7 개의다리를간선 (Edge) 로, 4 개의육지를정점 (Vertex) 로표현. A A Pregel River B C B C D
More informationCh.8 Procedures and Environments
Chapter 10 그래프 (graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변
More informationChapter 10 그래프 (graph) SANGJI University Kwangman KO
Chapter 10 그래프 (graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변
More informationChapter 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 informationChapter 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슬라이드 1
CHAP 10 : 그래프 yicho@gachon.ac.kr 1 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제 A,B,C,D 지역의연결관계표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러정리 모든정점에연결된간선의수가짝수이면오일러경로존재함 따라서그래프 (b) 에는오일러경로가존재하지않음 2 그래프정의
More information선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노
16. 그래프 선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노드들로구성된구조이다. 노드를정점 (vertex) 이라고부르고, 링크를간선 (edge)
More informationChapter 4. LISTS
연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는
More information쉽게배우는알고리즘 9장. 그래프알고리즘
쉽게배우는알고리즘 장. 그래프알고리즘 http://academy.hanb.co.kr 장. 그래프알고리즘 수학은패턴의과학이다. 음악역시패턴들이다. 컴퓨터과학은추상화와패턴의형성에깊은관련이있다. 컴퓨터과학이다른분야들에비해특징적인것은지속적으로차원이 급상승한다는점이다. 미시적관점에서 거시적관점으로도약하는것이다. - 도널드크누스 - - 한빛미디어 학습목표 그래프의표현법을익힌다.
More informationchap 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 informationMicrosoft 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 informationData 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 informationMicrosoft PowerPoint - slide05.pptx
Im4u 봄방학캠프 DAY 5; Elementary Graph Theory 구종만 jongman@gmail.com 그래프 (Graphs) 가장중요한 (?) 자료형인그래프의소개 그래프문제의큰두가지벽 모델링 : 현실세계의개념을그래프로나타낸다 알고리즘: 그래프로나타낸문제를해결한다 대개의문제에서는한가지벽만있다 모델링 : 문제를풀면서공부 알고리즘 : 비교적배우기쉽다
More information슬라이드 1
CHAP 10 : 그래프 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제
More informationA 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 informationchap01_time_complexity.key
1 : (resource),,, 2 (time complexity),,, (worst-case analysis) (average-case analysis) 3 (Asymptotic) n growth rate Θ-, Ο- ( ) 4 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k]
More information03_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슬라이드 제목 없음
Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each
More informationLet G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ
알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2016년 12월15일 ( 목 ) 오전 9시40분 ~) 담당교수 : 서강대학교컴퓨터공학과임인성 < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고, 반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. function MakeSet(x) { x.parent
More informationchap x: G입력
재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘
More informationchap x: G입력
원형큐 (Circular Queue) [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] front = 0, rear = 0 [2] [3] [0] [5] front = 0, rear = 3 [1] [4] [0] [5] front = 0, rear = 0 최대큐이용률 = MAX_Q_SIZE 1 3 장. 스택과큐 (Page 13) 원형큐의구현
More informationuntitled
1. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 2) => A / B * C * D + E () A / B * C * D + E void preorder(tree_ptr ptr) { if(ptr)
More information슬라이드 1
CHAP 10 : 그래프 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제
More information61 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 informationMicrosoft PowerPoint - Chap5 [호환 모드]
데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs
More information06장.리스트
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :
More information7장
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트
More informationchap 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중간고사 (자료 구조)
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 informationMicrosoft 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쉽게 배우는 알고리즘 강의노트
쉽게배우는알고리즘 ( 한빛미디어 ) 2 장. 상태공간트리의탐색 State-Space Tree State-space tree ( 상태공간트리 ) 문제해결과정의중간상태를각각한노드로나타낸트리 이장에서배우는세가지상태공간탐색기법 Backtracking Branch-and-bound A * algorithm - 2 - 한빛미디어 Travelling Salesman Problem
More information11장 포인터
Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함
More information歯MW-1000AP_Manual_Kor_HJS.PDF
Page 2 Page 3 Page 4 Page 5 Page 6 Page 7 Page 8 Page 9 Page 10 Page 11 Page 12 Page 13 Page 14 Page 15 Page 16 Page 17 Page 18 Page 19 Page 20 Page 21 Page 22 Page 23 Page 24 Page 25 Page 26 Page 27 Page
More informationMicrosoft PowerPoint - 08-Queue.ppt
Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In
More information원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를
리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은
More information5.스택(강의자료).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 informationMicrosoft PowerPoint - 제3장-배열.pptx
제 3 강. 배열 (Array) 자료구조 1 제 3 강. 배열자료구조 학습목차 1. 배열의개념 2. 구조체 3. 희소 (Sparce) 행렬 4. 다차원배열의저장 2 1. 배열의개념 리스트는일상생활에서가장많이쓰이는자료형태이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 배열 (Array) 은컴퓨터언어에서리스트를저장하는데이터타입이다. 리스트와배열은같은개념이지만다른차원의용어이다.
More informationC 언어 강의노트
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
C programming and Data Structures Overview T. H. Cormen, C. E. Leiserson and R. L. Rivest Introduction to, 3rd Edition, MIT Press, 2009 Sungkyunkwan University Hyunseung Choo choo@skku.edu Copyright 2000-2018
More information슬라이드 1
CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
More information리스트 (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 information1장. 리스트
01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef
More information서강대학교공과대학컴퓨터공학과 CSE3081 알고리즘설계와분석 (2 반 ) 기말고사 (2015 년 12 월 17 일 ) 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성
알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성대상 : 2학년 2학기생 < 주의 > 문제지는총6쪽이며, 제공한답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. 1. 다음은
More information슬라이드 1
CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
More informationuntitled
- -, (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 informationLab 5. 실습문제 (Double linked list)-1_해답.hwp
Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.
More informationPowerPoint 프레젠테이션
C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];
More informationMicrosoft 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
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
More information2002년 2학기 자료구조
자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)
More informationContents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74
큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조
More information03장.스택.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
CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임
More information<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 informationMicrosoft PowerPoint - Chap6 [호환 모드]
Data Structure (Chapter 6: Graphs) Sprig, 2 Sookmyug Womeʼs Uiv. Departmet of Multimedia Sciece Prof. Youg-Ho Park Graph 관련주요용어 ( 참고 ) Complete graph : a graph i which there is a edge betwee every pair
More informationuntitled
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예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A
예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = 1 2 3 4 5 6 7 8 9 B = 8 7 6 5 4 3 2 1 0 >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = 0 0 0 0 1 1 1 1 1 >> tf = (A==B) % A 의원소와 B 의원소가똑같은경우를찾을때 tf = 0 0 0 0 0 0 0 0 0 >> tf
More information04장.큐
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 큐 1/33 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 A B C 전단 ( front) 후단 ( rea r) 2/33 큐 ADT 삽입과삭제는 FIFO
More informationUI TASK & KEY EVENT
KEY EVENT & STATE 구현 2007. 1. 25 PLATFORM TEAM 정용학 차례 Key Event HS TASK UI TASK LONG KEY STATE 구현 소스코드및실행화면 질의응답및토의 2 KEY EVENT - HS TASK hs_task keypad_scan_keypad hs_init keypad_pass_key_code keypad_init
More informationMicrosoft PowerPoint - 알고리즘_5주차_1차시.pptx
Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1
More information이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.
More informationDBPIA-NURIMEDIA
SPFA 를기반으로개선된벨만 - 포드알고리듬 SPFA 를기반으로개선된벨만 - 포드알고리듬 진호 * 서희종 ** An improved Bellman-Ford algorithm based on SPFA Hao Chen * Hee-Jong Suh ** 요약 이논문에서 SPFA(shortest path faster algorithm) 을사용해서기존의벨만-포드 (Bellman-Ford)
More informationint main(void) int a; int b; a=3; b=a+5; printf("a : %d \n", a); printf("b : %d \n", b); a b 3 a a+5 b &a(12ff60) &b(12ff54) 3 a 8 b printf(" a : %x \
? 1 int main(void) int a; int b; a=3; b=a+5; printf("a : %d \n", a); printf("b : %d \n", b); a b 3 a a+5 b &a(12ff60) &b(12ff54) 3 a 8 b printf(" a : %x \n", &a); printf(" b : %x \n", &b); * : 12ff60,
More information01_List
List Data Structures and Algorithms 목차 추상자료형 (ADT) 배열을이용한리스트의구현 연결리스트의개념적이해 연결리스트의 ADT 구현 원형연결리스트 이중연결리스트 Data Structures and Algorithms 2 추상자료형 Abstract Data Type Data Structures and Algorithms 3 추상자료형
More informationuntitled
while do-while for break continue while( ) ; #include 0 i int main(void) int meter; int i = 0; while(i < 3) meter = i * 1609; printf("%d %d \n", i, meter); i++; return 0; i i< 3 () 0 (1)
More informationABC 10장
10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;
More information데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호
데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호 Index Chapter 01: Basic Concepts Chapter 02: Arrays and Structures Chapter 03: Stacks and Queues Chapter 04: Lists Chapter 05: Trees
More information슬라이드 1
CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터
More informationMicrosoft 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 informationo 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -
스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입
More informationLab 3. 실습문제 (Single linked list)_해답.hwp
Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.
More informationC 언어 프로그래밊 과제 풀이
과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍
More information슬라이드 1
Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음
More information<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>
#include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0
More informationK&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 informationMicrosoft PowerPoint - 자료구조2008Chap06
제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보
More informationMicrosoft PowerPoint - 제8장-트리.pptx
제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,
More information<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 informationchap8.PDF
8 Hello!! C 2 3 4 struct - {...... }; struct jum{ int x_axis; int y_axis; }; struct - {...... } - ; struct jum{ int x_axis; int y_axis; }point1, *point2; 5 struct {....... } - ; struct{ int x_axis; int
More informationA Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning
Basic Data Structures, Make, GDB Contents Data Structures Linked List Tree Hash Make 사용법 디버거 (gdb) 사용법 2/17 Reference The C Programming language, Brian W. Kernighan, Dennis M. Ritchie, Prentice-Hall Teach
More information슬라이드 1
자료구조 (Data Structures), 4 장. 리스트 담당교수 : 조미경 이번장에서학습할내용 * 리스트란? * 배열로리스트구현 * 연결리스트로리스트구현 * 연결리스트종류 * 연결리스트응용 : 다항식구현 2/63 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item 0,
More informationsna-node-ties
Node Centrality in Social Networks Nov. 2015 Youn-Hee Han http://link.koreatech.ac.kr Importance of Nodes ² Question: which nodes are important among a large number of connected nodes? Centrality analysis
More information<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >
제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다
More information<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>
한국방송통신대학교컴퓨터과학과 2 학년자료구조 제 1 장기본개념 자료와정보 3 알고리즘 4 자료 data : 현실세계에서관찰이나측정을통해수집된값 value 이나사실 fact 특정한일을수행하는명령어들의유한집합 정보 information : 자료를처리 / 추출 process 해서얻어진유용한결과 입 출 력 : 외부에서제공되는자료가있을수있다력 : 적어도한가지결과를생성한다
More informationLab 4. 실습문제 (Circular singly linked list)_해답.hwp
Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular
More informationchap x: G입력
3. 미로찾기 (Mazing Problem) 2 차원배열을이용한미로의구현 maze[row][column]: 0 길, 1 벽 그림 3.8 참조 이동방향 8 방향 (N, NE, E, SE, S, SW, W, NW) 각방향에대한 maze 배열의첨자변환 : 그림 3.9 경계지역 : 8 방향이아님. ( 모서리 : 3 방향, 변 : 5 방향 ) m p 미로를 (m +
More information슬라이드 1
-Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역
More information