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

Presentation on theme: "참고. 배열과 연결 리스트 비교 General List 코딩 방법 방법 1) 배열 방법 2) 연결 리스트"— Presentation transcript:

1 참고. 배열과 연결 리스트 비교 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

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

3 참고. 배열과 연결 리스트 비교 배열을 활용한 삽입연산 & 삭제연산 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

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

5 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

6 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

7 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

8 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

9 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

10 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 (정수) 참고: 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

11 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

12 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

13 4. Application Mainline for Academy Awards Data Structure

14 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

15 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

16 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

17 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

18 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

19 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

20 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

21 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

22 5. Complex Implementation
Doubly Linked Lists Insert node Data Structure

23 5. Complex Implementation
Doubly Linked Lists Delete node Data Structure

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

25 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

26 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

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

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

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