PowerPoint 프레젠테이션

Similar documents
PowerPoint 프레젠테이션

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

슬라이드 1

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

06장.리스트

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

chap 5: Trees

Chapter 4. LISTS

Lab 3. 실습문제 (Single linked list)_해답.hwp

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

1장. 리스트

03_queue

11장 포인터

슬라이드 1

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

C 언어 강의노트

Chapter 4. LISTS

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Chapter 4. LISTS

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

PowerPoint 프레젠테이션

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

슬라이드 1

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

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

Microsoft PowerPoint - 06-List.ppt

슬라이드 1

Algorithms

슬라이드 1

슬라이드 1

슬라이드 1

슬라이드 1

4장

Microsoft PowerPoint - chap4_list

01_List

슬라이드 1

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 자료구조2008Chap06

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

PowerPoint 프레젠테이션

untitled

슬라이드 1

PowerPoint 프레젠테이션

Microsoft PowerPoint - 08-Queue.ppt

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

PowerPoint 프레젠테이션

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

Microsoft PowerPoint - ch07 - 포인터 pm0415

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

Microsoft PowerPoint - chap11-포인터의활용.pptx

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

설계란 무엇인가?

중간고사 (자료 구조)

Microsoft PowerPoint - 제4장-스택과큐.pptx

02장.배열과 클래스

1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout << " 양수입력 : "; cin >> *p; if (*p <= 0) cout << " 양수를입력해야합니다 " << endl; return; 동적할

Chap 6: Graphs

chap01_time_complexity.key

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문

2002년 2학기 자료구조

11장 포인터

슬라이드 1

PowerPoint Template

Microsoft PowerPoint - chap06-2pointer.ppt

PowerPoint Presentation

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

Microsoft PowerPoint - 8ÀÏ°_Æ÷ÀÎÅÍ.ppt

BMP 파일 처리

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

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

Microsoft PowerPoint - 07-chap05-Stack.ppt

설계란 무엇인가?

03장.스택.key

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

Microsoft PowerPoint - chap10-함수의활용.pptx

슬라이드 1

윤성우의 열혈 TCP/IP 소켓 프로그래밍

슬라이드 1

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

ABC 10장

Chapter #01 Subject

Frama-C/JESSIS 사용법 소개

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D>

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

chap 5: Trees

Microsoft PowerPoint - 제11장 포인터

Microsoft PowerPoint - 제3장-배열.pptx

<4D F736F F F696E74202D203137C0E55FBFACBDC0B9AEC1A6BCD6B7E7BCC72E707074>

슬라이드 1

K&R2 Reference Manual 번역본

untitled

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

Transcription:

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

Section 01 추상자료형리스트 - 목록 ( 도표 ) Position Name Quantity 1 Beer 10 2 Gum 5 3 Apple 4 4 Potato 8 5 Onion 8......... [ 표 5-1] 구매물품리스트 2

추상자료형리스트의작업 Insert(Position, Data) 데이터를해당위치 (Position) 에넣기 Delete(Position) 해당위치 (Position) 의데이터를삭제 Retrieve(Position, Data) 해당위치 (Position) 의데이터를 Data 변수에복사 Create( ) 빈리스트만들기 ( 종이준비 ) Destroy( ) 리스트없애기 ( 종이버리기 ) IsEmpty( ) 빈리스트인지확인 ( 아무것도안적혔는지확인 ) Length( ) 몇개의항목인지계산 ( 몇개나적혔는지세기 ) 3

공리 공리 추상자료형의작업을형식화 리스트공리 (alist.create( )).Length( ) = 0 (alist.insert(i, Data)).Length( ) = alist.length( ) + 1 (alist.create( )).IsEmpty( ) = TRUE (alist.insert(i, Data)).Delete(i) = alist (alist.create( )).Delete(i) = ERROR Insert(1, Ramen) 밀릴것인가, 지울것인가공리로도명시하기어려움인터페이스파일에정확한커멘트를요함 4

Section 02 C에의한리스트구현 - C 배열에의한리스트구조체 카운트변수데이터배열 Count Data[ ] 2 0 1 2... (MAX-1) 324 256 [ 그림 5-1] C 배열에의한리스트구현 5

C 배열에의한리스트 코드 5-1: ListA.h (C Interface by Array) #define MAX 100 최대 100개데이터를저장 typedef struct { int Count; 리스트길이 ( 데이터개수 ) 를추적 int Data[MAX]; 리스트데이터는정수형 listtype; 리스트타입은구조체 void Insert(listType *Lptr, int Position, int Item): 해당위치에데이터를삽입 void Delete(listType *Lptr, int Position); 해당위치데이터를삭제 void Retrieve(listType *Lptr, int Position, int *ItemPtr); 찾은데이터를 *ItemPtr에넣음 void Init(listType *Lptr); 초기화 bool IsEmpty(listType *Lptr); 비어있는지확인 int Length(listType *Lptr); 리스트내데이터개수 6

C 배열에의한리스트 void Insert(listType *Lptr, int Position, int Item): 자료구조를함수호출의파라미터로전달리스트를가리키는포인터를 Lptr 로복사해달라는것 C 언어로구현할때일반특성으로서전역변수를회피하기위함 void Insert(listType *Lptr, int Position, int Item): 삽입, 삭제는원본자체를바꾸는작업이므로참조호출이필요리스트자체데이터는복사되지않음. 복사에따른시간도줄어든다. void Retrieve(listType *Lptr, int Position, int *ItemPtr); 호출함수의원본데이터를가리키는포인터값을 ItemPtr 로 *ItemPtr 를변형하면호출함수의원본데이터값이변함 void main( ) { listtype List1; int Result; Insert(&List1, 1, 23); 리스트처음에 23을넣기 Retrieve(&List1, 1, &Result); 리스트의첫데이터를 Result에넣기 7

C 배열에의한리스트 코드 5-2: ListA.c (C Implementation by Array) #include <ListA.h> 헤더파일을포함 void Init(listType *Lptr) 초기화루틴 { Lptr->Count = 0; 데이터수를 0으로세팅 bool IsEmpty(listType *Lptr) 비어있는지확인하는함수 { return (Lptr->Count = = 0); 빈리스트라면 TRUE void Insert(listType *Lptr, int Position, int Item) 삽입함수 { if (Lptr->Count = = MAX) 현재꽉찬리스트 printf("list Full"); else if ((Position > (Lptr->Count+1)) (Position < 1)) printf("position out of Range"); 이격된삽입위치불허 else { for (int i = (Lptr->Count-1); i >= (Position-1); i--) 끝에서부터삽입위치까지 Lptr->Data[i+1] = Lptr->Data[i]; 오른쪽으로한칸씩이동 Lptr->Data[Position-1] = Item; 원하는위치에삽입 Lptr->Count += 1; 리스트길이늘림 8

연결리스트기초 typedef struct { int Data; 노드내부의실제데이터또는레코드 node* Next; Next가가리키는것은 node 타입 node; 구조체에 node라는새로운타입명부여 typedef node* Nptr; Nptr p, q; Nptr 타입이가리키는것은 node 타입 Nptr 타입변수 p, q 를선언 [ 그림 5-3] 노드, 노드포인터 9

연결리스트개념 연결리스트개념 10

연결리스트기초 노드만들기, 이어붙이기 p = (node *)malloc(sizeof(node)); p->data = 33; p->next = (node *)malloc(sizeof(node)); p->next->data = 22; p->next->next = NULL; [ 그림 5-3] 노드, 노드포인터 11

연결리스트기초 공간반납 Nptr Head; Head = (node *)malloc(sizeof(node)); Head -> Data = 11; Head -> Next = NULL Head = NULL; [ 그림 5-4] 공간반납 12

연결리스트기본조작 디스플레이 Temp = Head; While (Temp!= NULL) { printf("%d ", Temp->Data); Temp = Temp->Next; [ 그림 5-5] 연결리스트의출력 13

간단한삽입 p = (node *)malloc(sizeof(node)); p->data = 8; p->next = Temp->Next; Temp->Next = p; 연결리스트기본조작 [ 그림 5-6] 간단한삽입 14

연결리스트기본조작 간단한삭제 p = Temp->Next; Temp->Next = Temp->Next->Next; free p; [ 그림 5-7] 간단한삭제예시 15

C 연결리스트에의한리스트 C 연결리스트에의한리스트 [ 그림 5-8] 연결리스트표현을위한구조체 16

코드 5-3: ListP.h (C Interface by Linked List) typedef struct C 연결리스트에의한리스트 { int Data; 노드내부의실제데이터또는레코드 node* Next; Next가가리키는것은 node 타입, 즉자기자신타입 node; 구조체에 node라는새로운타입명부여 typedef node* Nptr; Nptr 타입이가리키는것은 node 타입 typedef struct { int Count; 리스트길이를추적 Nptr Head; 헤드포인터로리스트전체를대변함 listtype; void Insert(listType *Lptr, int Position, int Item): 해당위치에데이터를삽입 void Delete(listType *Lptr, int Position); 해당위치데이터를삭제 void Retrieve(listType *Lptr, int Position, int *ItemPtr); void Init(listType *Lptr); 초기화 bool IsEmpty(listType *Lptr); 비어있는지확인 int Length(listType *Lptr); 리스트내데이터수 17

C 연결리스트에의한리스트 코드 5-4: ListP.c (C Implementation by Linked List) #include <ListP.h> 헤더파일을포함 void Init(listType *Lptr) { Lptr->Count = 0; 리스트길이를 0으로초기화 Head = NULL; 헤드포인터를널로초기화 bool IsEmpty(listType *Lptr) 빈리스트인지확인하기 { return (Lptr->Count = = 0); 리스트길이가 0이면빈리스트 18

C 연결리스트에의한리스트 코드 5-4: ListP.c (C Implementation by Linked List) void Insert(listType *Lptr, int Position, int Item) 삽입함수 { if ((Position > (Lptr->Count+1)) (Position < 1)) printf("position out of Range"); 이격된삽입위치불허 else { Nptr p = (node *)malloc(sizeof(node)); 삽입될노드의공간확보 p->data = Item; 데이터값복사 if (Position = = 1) 첫위치에삽입할경우 { p->next = Lptr->Head; 삽입노드가현재첫노드를가리킴 Lptr->Head = p; 헤드가삽입노드를가리키게 else 첫위치가아닐경우 { Nptr Temp = Lptr->Head; 헤드포인터를 Temp로복사 for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삽입직전노드를가리키게 p->next = Temp->Next; 삽입노드의 Next를세팅 Temp->Next = p; 직전노드가삽입된노드를가리키게 Lptr->Count += 1; 리스트길이늘림 19

C 연결리스트에의한리스트 코드 5-5: 위치기반연결리스트의삭제 void Delete(listType *Lptr, int Position) 삭제함수 { if (IsEmpty(Lptr)) printf("deletion on Empty List"); 빈리스트에서삭제요구는오류 else if (Position > (Lptr->Count) (Position < 1)) printf("position out of Range"); 삭제위치가현재데이터범위를벗어남 else { if (Position = = 1) 첫노드를삭제하는경우 { Nptr p = Lptr->Head; 삭제될노드를가리키는포인터를백업 Lptr->Head = Lptr->Head->Next; 헤드가둘째노드를가리키게 else { for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삭제직전노드를가리키게 Nptr p = Temp->Next; 삭제될노드를가리키는포인터를백업 Temp->Next = p->next; 직전노드가삭제될노드다음을가리키게 Lptr->Count -= 1; 리스트길이줄임 free (p); 메모리공간반납 20

값기반연결리스트의삭제 C 연결리스트에의한리스트 Temp = Lptr->Head; while((temp!= NULL) && (Temp->Data!= Item) Temp = Temp->Next; 이코드로는템프가삭제직전에놓이게할수없음 [ 그림 5-9] 정렬된리스트의삭제 21

예견방식 Temp = Lptr->Head; while((temp!= NULL) && (Temp->Next->Data!= Item) Temp = Temp->Next; 데이터 15 인노드삭제 C 연결리스트에의한리스트 Temp 가데이터 12 인노드를가리킬때, Temp 는널이아니지만 Temp->Next 는널임 [ 그림 5-9] 정렬된리스트의삭제 22

C 연결리스트에의한리스트 코드 5-6 정렬된연결리스트의삭제 Delete(listType *Lptr, int Item) 삭제함수 { Nptr Prev = NULL; Prev는널로초기화 Nptr Temp = Lptr->Head; Temp 는헤드로초기화 while((temp!= NULL) && (Temp->Data!= Item) { Prev = Temp; Prev가 Temp를가리키게 Temp = Temp->Next; Temp 는다음노드로전진 if (Prev = = NULL) Temp가한번도전진하지않았음 { if (Temp = = NULL) 처음부터빈리스트 printf("no Nodes to Delete"); else 삭제대상이첫노드 { Lptr->Head = Lptr->Head->Next; free (Temp); Lptr->Count - = 1; else Temp가전진했음 { if (Temp = = NULL) 리스트끝까지삭제대상이없음 printf("no Such Nodes"); else 삭제대상이내부에있음 { Prev->Next = Temp -> Next; 직전노드가삭제될다음노드를가리킴 free (Temp); Lptr->Count - = 1; 23

이중연결리스트 typedef struct { int Data; node* Prev, Next; node; Prev 는이전노드를, Next 는다음노드를가리킴 [ 그림 5-10] 이중연결리스트 24

단순연결리스트의삽입 이중연결리스트 테일포인터가따로있으면유리삭제일경우에는테일포인터가뒤로이동이중연결이어야테일포인터를뒤로이동할수있음 [ 그림 5-11] 단순연결리스트의테일포인터 [ 그림 5-12] 헤드, 테일에의한이중연결리스트 25

원형연결 원형연결, 원형이중연결 타임셰어링시스템의타임슬라이스사용자교대 [ 그림 5-13] 원형연결리스트 원형이중연결 [ 그림 5-14] 이중원형연결리스트 26

Section 03 C++ 에의한리스트구현 C 배열과 C++ 배열비교 ListA.h (C++ Interface by Array) const int MAX = 100; class listclass { public: listclass( ); listclass(const listclass& L); ~listclass( ); void Insert(int Position, int Item); void Delete(int Position); void Retrieve(int Position, int & Item); bool IsEmpty( ); int Length( ); private: int Count; int Data[MAX]; #define MAX 100 ListA.h (C Interface by Array) void Init(listType *Lptr); void Insert(listType *Lptr, int Position, int Item) void Delete(listType *Lptr, int Position); void Retrieve(listType *Lptr, int Position, int *ItemPtr); bool IsEmpty(listType *Lptr); int Length(listType *Lptr); typedef struct { int Count; int Data[MAX]; listtype; [ 표 5-2] C++ 배열에의한리스트와 C 배열에의한리스트 27

C++ 배열에의한리스트 코드 5-7: ListA.cpp (C++ Implementation by Array) #include <ListA.h> listclass::listclass( ) 생성자 { Count = 0; 리스트길이를 0으로초기화 listclass::~listclass( ) { 소멸자 listclass::listclass(const listclass& L) 복사생성자 { Count = L.Count; 리스트길이를복사 for (int i = 1; i <= L.Count; ++i) Data[i-1] = L.Data[i-1]; 깊은복사에의해배열요소모두를복사 28

코드 5-8: ListP.h (C++ Interface by Linked List) typedef struct { int Data; node* Next; node; typedef node* Nptr; C++ 연결리스트에의한리스트 class listclass { public: listclass( ); listclass(const listclass& L); ~listclass( ); void Insert(int Position, int Item); void Delete(int Position); void Retrieve(int Position, int& Item); bool IsEmpty( ); int Length( ); private: int Count; Nptr Head; 29

C++ 연결리스트에의한리스트코드 5-9: ListP.cpp (C++ Implementation by Linked List) #include <ListP.h> listclass::listclass( ) 생성자함수 { Count = 0; 리스트의길이를 0으로초기화 Head = NULL; 헤드를널로초기화 bool listclass::isempty( ) 빈리스트인지확인하는함수 { return (Count = = 0); 배열길이 0이면 TRUE 30

C++ 연결리스트에의한리스트 코드 5-9: ListP.cpp (C++ Implementation by Linked List) void listclass::delete(int Position) 삭제함수 { Nptr Temp; if (IsEmpty( )) cout << "Deletion on Empty List"; 빈리스트에삭제요구는오류 else if ((Position > Count) (Position < 1)) cout << "Position out of Range"; 삭제위치가현재데이터범위를벗어남 else { if (Position = = 1) 삭제될노드가첫노드일경우 { Nptr p = Head; 삭제될노드를가리키는포인터를백업 Head = Head->Next; 헤드가둘째노드를가리키게 else 삭제노드가첫노드가아닌경우 { for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삭제될노드직전노드로이동 Nptr p = Temp->Next; 삭제될노드를가리키는포인터를백업 Temp->Next = p->next; 직전노드가삭제될노드다음을가리키게 Count - = 1; 리스트길이줄임 delete (p); 메모리공간반납 31

C++ 연결리스트에의한리스트코드 5-9: ListP.cpp (C++ Implementation by Linked List) listclass::~listclass( ) 소멸자함수 { while (!IsEmpty( )) 리스트가완전히빌때까지 Delete(1); 첫번째것을계속지우기 listclass:listclass(const listclass& L) 복사생성자함수 { Count = L.Count; 일단리스트개수를동일하게 if (L.Head = = NULL) Head = NULL 넘어온게빈리스트라면자신도빈리스트 else { Head = new node; 빈리스트아니라면일단새노드를만들고 Head->Data = L.Head->Data; 데이터복사 Nptr Temp1 = Head; Temp1은사본을순회하는포인터 for (Nptr Temp2=L.Head->Next; Temp2!= NULL; Temp2=Temp2->Next) { Temp1->Next = new node; 사본의현재노드에새노드를붙임 Temp1 = Temp1 -> Next; 새노드로이동 Temp1->Data = Temp2->Data; 새노드에원본데이터를복사 Temp1->Next = NULL; 사본의마지막노드의 Next 에널을기입 32

Section 04 배열과연결리스트비교 배열과연결리스트의비교 공간배열은정적이므로최대크기를미리예상해야함. 만들어놓은배열공간이실제로쓰이지않으면낭비연결리스트는실행시필요에따라새로운노드생성연결리스트는포인터변수공간을요함 검색시간배열은단번에찾아감 ( 묵시적어드레싱 : 인덱스연산 ) 연결리스트는헤드부터포인터를따라감 ( 현시적어드레싱 : 포인터읽음 ) 삽입, 삭제시간배열의삽입 : 오른쪽밀림 (Shift Right) 배열의삭제 : 왼쪽밀림 (Shift Left) 연결리스트 : 인접노드의포인터만변경 어떤자료구조? 검색위주이면배열이유리삽입삭제위주라면연결리스트가유리최대데이터수가예측불가라면연결리스트 33

Thank you 34