참고. 배열과 연결 리스트 비교 General List 코딩 방법 방법 1) 배열 방법 2) 연결 리스트

Slides:



Advertisements
Similar presentations
YES C 제 1 장 C 언어의 개요 1/34 제 1 장 C 언어의 개요 문봉근. YES C 제 1 장 C 언어의 개요 2/34 제 1 장 C 언어의 개요 1.1 프로그램과 C 언어의 특징 1.2 C 언어의 프로그램 구성 1.3 비주얼 C++ 통합 환경 들어가기.
Advertisements

스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
제14장 동적 메모리.
[INA240] Data Structures and Practice
Internet Computing KUT Youn-Hee Han
Chapter 04. 연결 리스트(Linked List) 2
연결리스트(linked list).
시스템 생명 주기(System Life Cycle)(1/2)
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
5장. 리스트 리스트 학습목표 목록이나 도표처럼 여러 데이터를 관리할 수 있는 자료형을 추상화
Internet Computing KUT Youn-Hee Han
Internet Computing KUT Youn-Hee Han
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
시스템 생명 주기(System Life Cycle)(1/2)
자료 구조: Chapter 3 (2)구조체, 포인터
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
Chapter 5. General Linear List
제15장 파일 입출력 문자열을 출력하는 여러가지 방법 (15-2쪽) 문자열만 처리하는 입출력 함수
스택(stack) SANGJI University Kwangman Ko
강의 #6 큐(Queue).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Chapter 9 – 구조형과 리스트 처리 Outline 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
[INA240] Data Structures and Practice
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
6장. printf와 scanf 함수에 대한 고찰
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
14장. 포인터와 함수에 대한 이해.
11장. 1차원 배열.
Introduction To Data Structures Using C
C#.
adopted from KNK C Programming : A Modern Approach
사용자 함수 사용하기 함수 함수 정의 프로그램에서 특정한 기능을 수행하도록 만든 하나의 단위 작업
어서와 C언어는 처음이지 제14장.
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
4th HomeWork Guide (ver2.0)
3장 상수 변수 기본 자료형 키워드와 식별자 상수와 변수 기본 자료형 형변환 자료형의 재정의.
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
24장. 파일 입출력.
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
* 프로그램을 간단히 하기 위해 malloc 성공체크는 안 함
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
8주차: Strings, Arrays and Pointers
Fflush 사용이유 및 방법 [이유] 키보드에서 입력된 내용은 입력버퍼에 저장되었다가 Enter 키가 들어오면 프로그램으로 전달됨 이 때 입력버퍼에 있는 Enter 키도 프로그램으로 전달됨 그러므로 아래와 같은 프로그램에서 문자 하나를 입력해도 Enter키도 입력된 것으로.
5강. 배열 배열이란? 배열의 문법 변수와 같이 이해하는 배열의 메모리 구조의 이해 레퍼런스의 이해 다차원 배열
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
Canary value 스택 가드(Stack Guard).
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
데이터 동적 할당 Collection class.
7주차: Functions and Arrays
제 8장. 클래스의 활용 학기 프로그래밍언어및실습 (C++).
구조체(struct)와 공용체(union)
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 4 장 Record.
1. 지역변수와 전역변수 2. auto, register 3. static,extern 4. 도움말 사용법
C.
[CPA340] Algorithms and Practice Youn-Hee Han
Pointers summary.
제 4 장. 리스트(List).
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

참고. 배열과 연결 리스트 비교 General List 코딩 방법 방법 1) 배열 방법 2) 연결 리스트 It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. D A C E 메모리 안에서의 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요 없음 B 메인 메모리 Data Structure

참고. 배열과 연결 리스트 비교 배열 vs. 연결 리스트 공간적인 면에서 비교 배열  메모리에 데이터가 일렬로 붙어 있음을 의미 연결 리스트  메모리에 떨어져 있지만 포인터에 의해 연결되어 있음을 의미 배열 (선형 자료구조)이 코딩이 더 쉬움? 포인터 활용이 어려운 사람의 주관적이 견해일 뿐 공간적인 면에서 비교 배열은 정적이므로 최대크기를 미리 예상해야 함. 만들어 놓은 배열 공간이 실제로 쓰이지 않으면 낭비 연결 리스트는 실행 시 필요에 따라 새로운 노드 생성 공간 절약 연결 리스트는 포인터 변수공간을 요함. 하지만 데이터가 차지하는 공간에 비해서는 상대적으로 미미함 Data Structure

참고. 배열과 연결 리스트 비교 배열을 활용한 삽입연산 & 삭제연산 N A B C D E 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 A B C D E A B C D E A B C D E A B C D E A B N C D E Data Structure

참고. 배열과 연결 리스트 비교 검색시간의 비교 삽입, 삭제 시간의 비교 어떤 자료구조? 배열은 단번에 찾아감 Implicit (묵시적) Addressing: 인덱스 연산 연결 리스트는 헤드부터 포인터를 따라감 Explicit (현시적, 명시적) Addressing: 포인터 읽음 검색 시간면에서는 배열이 유리 삽입, 삭제 시간의 비교 배열의 삽입: 오른쪽 밀림(Shift Right) 배열의 삭제: 왼쪽 밀림(Shift Left) 연결 리스트: 인접 노드의 포인터만 변경 삽입, 삭제 시간 면에서는 연결 리스트가 유리 어떤 자료구조? 검색위주이면 배열이 유리 삽입 삭제 위주라면 연결 리스트가 유리 최대 데이터 수가 예측 불가라면 연결 리스트 하지만, 일반적으로 대부분의 경우 연결 리스트를 활용한다. Data Structure

4. Application A list of award-winning pictures and their directors (p.228~239) Three major functions Print instruction Build the list Process user inquiries Get the user’s choice Print the entire list Search for a requested year One other (important) function A compare function to compare two years (keys) main Academy Awards cmpYear printInstr buildList process getChoice printList search Data Structure

4. Application Data Structure [stdbool.h] File Name: academy.c (이후 모든 구현은 이 한 파일에 추가) #include <stdio.h> #include <stdlib.h> #include <cType.h> #include "stdbool.h" #include "list.h" #define STR_MAX 41 //const short STR_MAX = 41; typedef struct { short year; char picture [STR_MAX]; char director[STR_MAX]; } PICTURE; [stdbool.h] #ifndef _STDBOOL_H #define _STDBOOL_H typedef int _Bool; #define bool _Bool #define true 1 #define false 0 #define __bool_true_false_are_defined 1 #endif Data Structure

4. Application Data File File Name: pictures.dat 1934 "It Happened One Night" "Frank Capra" 1932 "Cavalcade" "Frank Lloyd" 1939 "Gone With the Wind" "Victor Fleming" 1941 "How Green Was My Valley" "John Ford" 1938 "You Can't Take It With You" "Frank Capra" 1942 "Mrs. Miniver" "William Wyler" 1942 "Duplicate Movie" "ERROR" 1943 "Casablanca" "Michael Curtiz" 1945 "The Lost Weekend" "William Wyler" 1946 "The Best Years of Our Lives" "William Wyler" 1947 "Gentleman's Agreement" "Elia Kazan" 1950 "All About Eve" "Joseph L. Mankiewicz" 1953 "From Here To Eternity" "Fred Zinnemann" Data Structure

4. Application Mainline for Academy Awards main void printInstr (void); LIST* buildList (void); void process (LIST* list); char getChoice (void); void printList (LIST* list); void search (LIST* list); int cmpYear (void* pYear1, void* pYear2); int main (void) { LIST* list; printInstr (); list = buildList (); process (list); printf("End Best Pictures\n" "Hope you found your favorite!\n"); return 0; } printInstr void printInstr (void) { printf("This program prints the …" … "the rest. Enjoy.\n"); return; } Data Structure

4. Application Mainline for Academy Awards buildList (1/4) LIST* buildList (void) { FILE* fpData; LIST* list; short yearIn; int addResult; PICTURE* pPic; list = createList (cmpYear); if (!list) printf("\aCannot create list\n"), exit (100); fpData = fopen("pictures.dat", "r"); if (!fpData) printf("\aError opening input file\n"), exit (110); Data Structure

4. Application Mainline for Academy Awards int *fscanf( FILE *stream, const char *format, ...) 인수 FILE *stream  읽고자 하는 FILE 포인터 const char *format  읽어 들일 데이터 서식 ...  서식에 맞춘 변수 나열 반환 읽기에 성공했다면 읽어들인 항목 개수를 반환 실패나 오류가 발생하면 -1을 반환 위 예에서 " %hd"의 의미 h: short d: int (정수) 참고: http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html buildList (2/4) while (fscanf(fpData, "%hd", &yearIn) == 1) { pPic = (PICTURE*) malloc(sizeof(PICTURE)); if (!(pPic)) printf("\aOut of Memory in build list\n"), exit (100); pPic->year = yearIn; Data Structure

4. Application Mainline for Academy Awards "%40[^\"] %*c"의 의미 %40[…] [ ] 안에 있는 것들로만 최대 40개의 글자를 읽음. 결과는 string 으로 처리한다  즉, 맨 마지막에 ‘\0’이 자동 할당 %40[^\"] "를 만날 때 까지 최대 40개의 글자를 읽음. 결과는 string 으로 처리한다  즉, 맨 마지막에 ‘\0’이 자동 할당 [^…] 의 의미  … 을 만날 때 까지 %*c 만약에 입력 버퍼에 들어와 있는 글자(예를 들어 ") 가 있다면 무시하라는 뜻 buildList (3/4) while ((fgetc(fpData)) != '\t') ; //\t 글자를 읽을 때 까지 loop while ((fgetc(fpData)) != '"') ; // " 글자를 읽을 때 까지 loop fscanf(fpData, "%40[^\"] %*c", pPic->picture); while ((fgetc(fpData)) != '\t') ; while ((fgetc(fpData)) != '"') ; fscanf(fpData, "%40[^\"] %*c", pPic->director); Data Structure

4. Application Mainline for Academy Awards addNode 는 다음의 반환값을 가짐 (list.h 참고) 0: Success 1: Duplication -1: heap overflow buildList (4/4) addResult = addNode (list, pPic); if (addResult != 0) if (addResult == -1) printf("Memory overflow adding movie\a\n"), exit (120); else printf("Duplicate year %hd not added\n\a", pPic->year); while (fgetc(fpData) != '\n') ; //\n 글자를 읽을 때 까지 loop } return list; Data Structure

4. Application Mainline for Academy Awards Data Structure

4. Application Mainline for Academy Awards process void process (LIST* list) { char choice; do { choice = getChoice (); switch (choice) { case 'P': printList (list); break; case 'S': search (list); case 'Q': break; } } while (choice != 'Q'); return; Data Structure

4. Application Mainline for Academy Awards getChoice char getChoice (void) { char choice; bool valid; printf("======== MENU ======= \n" …………); do { scanf(" %c", &choice); choice = toupper(choice); switch (choice) { case 'S': case 'P': case 'Q': valid = true; break; default: valid = false; printf("\aInvalid choice\n" "Please try again: "); } } while (!valid); return choice; Data Structure

4. Application Mainline for Academy Awards traverse 함수에서 두 번째 인자 (0, 1) 의 의미 0  list 내의 pos 포인터 초기화 1  기존 pos 포인터의 그 다음 노드를 pos가 가리키도록 함 "%hd %-40s %s\n" 의 의미 %hd  short int 출력, %-40s  왼쪽정렬로 40개의 글자칸 확보하여 string 출력, %s  (왼쪽정렬로) string 출력 printList void printList (LIST* list) { PICTURE* pPic; if (listCount (list) == 0) printf("Sorry, nothing in list\n\a"); else { printf("\nBest Pictures List\n"); traverse (list, 0, (void**)&pPic); do { printf("%hd %-40s %s\n", pPic->year, pPic->picture, pPic->director); } while (traverse (list, 1, (void**)&pPic)); } printf("End of Best Pictures List\n\n"); Data Structure

4. Application Mainline for Academy Awards search void search (LIST* list) { short year; bool found; PICTURE pSrchArgu; PICTURE* pPic; printf("Enter a four digit year: "); scanf ("%hd", &year); pSrchArgu.year = year; found = searchList (list, &pSrchArgu, (void**)&pPic); if (found) printf("%hd %-40s %s\n", pPic->year, pPic->picture, pPic->director); else printf("Sorry, but %d is not available.\n", year); return; } Data Structure

4. Application Mainline for Academy Awards cmpYear int cmpYear (void* pYear1, void* pYear2) { int result; short year1; short year2; year1 = ((PICTURE*)pYear1)->year; year2 = ((PICTURE*)pYear2)->year; if (year1 < year2) result = -1; else if (year1 > year2) result = +1; else result = 0; return result; } Data Structure

5. Complex Implementation Circularly Linked List (원형 연결 리스트) Last node’s link points to the first node Usually circularly linked lists are represented by “rear (last)” point instead of “head” point (Why?) Non-circularly linked list Circularly linked list Data Structure

5. Complex Implementation Circularly Linked List (원형 연결 리스트) Insert (at any position) 마지막 노드 뒤에 새로운 노드 추가할 때 포인트 조작 신경써야 함. Delete (at any position) Search loop (target not equal to pLoc key && pLoc link not equal to startAddress) Data Structure

5. Complex Implementation Doubly Linked Lists Each node has a pointer to both its successor and predecessor 정의: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 Singly linked list Doubly linked list Data Structure

5. Complex Implementation Doubly Linked Lists Insert node Data Structure

5. Complex Implementation Doubly Linked Lists Delete node Data Structure

5. Complex Implementation Doubly Linked Lists 의 특징 및 장점 현재의 바로 이전 노드를 찾기가 쉽다. 링크가 양방향이므로 양방향으로 검색이 가능 Trade-off (타협, 균형) Singly-Linked List vs. Doubly-Linked List 삽입, 삭제의 시간 측면 메모리 사용 공간의 측면 프로그램 코딩의 양 측면 Circularly and Doubly Linked List Data Structure

5. Complex Implementation Multilinked Lists Multilinked list  a list with two or more logical key sequences The power (장점) of the multilinked list The same set of data can be processed in multiple sequence Ex) First 10 presidents of USA 1st (logical) list: name of president 2nd (logical) list: name of first lady Data Structure

5. Complex Implementation Multilinked Lists Ex) First 10 presidents of USA 1st (logical) list: name of president 2nd (logical) list: name of first lady A list with just three elements If we follow the president links, we traverse the list through… Adams  Jefferson  Washington If we follow the spouse links, we traverse the list through… Custis  Skelton  Smith Data Structure

5. Complex Implementation Deque (Double Ended Queue ,데크) -교재에서는 안나오지만 중요한 내용- 특수한 형태의 큐로서 삽입 삭제가 Front (=Head)와 Rear에서 가해질 수 있도록 허용한 자료구조 스택과 큐의 성질을 종합한 순서 리스트 중요 연산 AddLast( ) AddFirst( ) RemoveLast( ) RemoveFirst( ) 응용 예 화면 스크롤 AddLast( ) RemoveFirst( ) Deque AddFirst( ) RemoveLast( ) Data Structure

5. Complex Implementation Deque (Double Ended Queue ,데크) 데크를 사용한 큐 구현: RemoveFirst( ), AddLast( ) 만을 사용 데크를 사용한 스택 구현: RemoveFirst( ), AddFirst( )만을 사용 Stack Operations Deque Operations Queue Operations AddFirst() AddLast() RemoveFirst() RemoveLast() Data Structure

5. Complex Implementation Deque에 대한 일련의 연산 수행 예 Deque 연산 Deque 내부 AddFirst(deque,3) (3) AddFirst(deque,5) (5, 3) RemoveFirst(deque) AddLast(deque,7) (3, 7) (7) RemoveLast(deque) () AddFirst(deque,9) (9) (9, 7) (3, 9, 7) AddLast(deque,5) (3, 9, 7, 5)