Internet Computing KUT Youn-Hee Han

Internet Computing Laboratory @ KUT Youn-Hee Han
5장. 리스트 Internet Computing KUT Youn-Hee Han

1. 추상 자료형 리스트 (ADT List) ADT List는 목록 또는 도표를 추상화 한 것
Insertion Deletion Retrieval … Position Name Quantity 1 Beer 10 2 Gum 5 3 Apple 4 Potato 8 Onion ... Data Structure

1. 추상 자료형 리스트 (ADT List) 그렇다면, Insertion에 대해서 다음 중 어떤 것을 제공해야 하는가? 사용자는 어떤 것을 더 원하는가? 둘 다 원하는가? Insert (Data) Insert (Position, Data) Position-oriented List (위치 기반 리스트) 에서의 작업 정의 Insert(Position, Data) - 데이터를 해당 위치(Position)에 넣기 Delete(Position) - 해당 위치(Position)의 데이터를 삭제 Retrieve(Position, Data) - 해당 위치(Position)의 데이터를 Data 변수에 복사 Create( ) - 빈 리스트 만들기 Destroy( ) - 리스트 없애기 IsEmpty( ) - 빈 리스트인지 확인 Length( ) - 몇 개의 항목인지 계산 Data Structure

1. 추상 자료형 리스트 (ADT List) 구현자로서는 사용자가 어떠한 의문도 품지 않도록 Interface File의 주석을 명확히 작성해야 함 Axiom (공리) 형태의 주석 – 형식화 되어진 표현 (명확함) (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 But… Insert(1, Ramen) 의 해석 리스트 원소들을 밀리게 할 것인가, 지울 것인가 공리로도 명시하기 어려움 인터페이스 파일에 정확한 커멘트를 요함 Specification (스펙) Data Structure

2. C에 의한 리스트 구현 #define MAX 100 최대 100개 데이터를 저장 typedef struct {
Count Data[ ] 2 1 ... MAX-1 324 256 #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); 초기화 int IsEmpty(listType *Lptr); 비어있는지 확인 int Length(listType *Lptr); 리스트 내 데이터 개수 Data Structure

2. C에 의한 리스트 구현 void Insert(listType *Lptr, int Position, int Item):
void Delete(listType *Lptr, int Position); 리스트를 가리키는 포인터를 Lptr로 복사 – 참조호출 C 언어로 구현할 때 일반특성으로서 전역변수를 회피하기 위함 삽입, 삭제는 원본 자체를 바꾸는 작업이므로 참조호출이 필요 리스트 자체 데이터는 복사되지 않음. 복사에 따른 시간도 줄어든다. void Retrieve(listType *Lptr, int Position, int *ItemPtr); 호출함수의 원본 데이터를 가리키는 포인터 값을 ItemPtr로 전달받음 *ItemPtr를 변형하면 호출함수의 원본 데이터 값이 변함 Data Structure

2. C에 의한 리스트 구현 main 함수에서 함수 호출 void main( ) { listType List1;
int Result; Insert(&List1, 1, 23); Retrieve(&List1, 1, &Result); } Data Structure

2. C에 의한 리스트 구현 1차원 배열에 항목들을 순서대로 저장 삽입연산: 삽입위치 다음의 항목들을 이동하여야 함.
L=(A, B, C, D, E) 삽입연산: 삽입위치 다음의 항목들을 이동하여야 함. 삭제연산: 삭제위치 다음의 항목들을 이동하여야 함 A B C D E 1 2 3 4 5 6 7 8 9 A B C D E 1 2 3 4 5 6 7 8 9 N A B D E 1 2 3 4 5 6 7 8 9 C Data Structure

2. C에 의한 리스트 구현 #include <ListA.h> 헤더파일을 포함
void Init(listType *Lptr) { 초기화 루틴 Lptr->Count = 0; 데이터 수를 0으로 세팅 } int 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; 리스트 길이 늘림 Data Structure

2. C에 의한 리스트 구현 삽입연산 vs. 삭제연산 MAX=6 Count=5 Position=3
1 2 3 4 5 A B C D E 1 2 3 4 5 MAX=6 Count=5 Position=3 for (i=4; i>=2; i--) … 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

2. C에 의한 리스트 구현 배열을 이용하여 리스트 구현 시 장점 배열을 이용하여 리스트 구현 시 단점
배열 인덱스를 이용한 Direct Access 빠른 속도의 검색이 가능 배열을 이용하여 리스트 구현 시 단점 데이터의 최대 개수를 컴파일 이전에 미리 선언해야 함 삽입과 삭제를 위한 데이터 이동 시에 시간적 부담 Data Structure

2. C에 의한 리스트 구현 Linked List (연결 리스트)
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. A linked list is a self-referential datatype because it contains a pointer or link to another data of the same type. Data Structure

검색을 할 때 이어진 데이터를 인덱스를 이용하여 찾는 것이 아니라 포인터를 따라감으로써 찾는다. typedef struct { int Data; node* Next; } node; typedef node* Nptr; Nptr p, q; Data Structure

리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장 메모리 안에서의 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요 없음 D A C E B 메인 메모리 Data Structure

2. C에 의한 리스트 구현 Head Pointer (헤드 포인터) 첫 번째 노드를 가리키는 포인터
이어진 꾸러미를 붙잡을 수 있는 실마리와 같은 것 p = (node *)malloc(sizeof(node)); p->Data = 33; p->Next = (node *)malloc(sizeof(node)); p->Next->Data = 22; p->Next->Next = NULL; Data Structure

2. C에 의한 리스트 구현 노드의 반납 필요에 따라 노드를 만들기 위하여 동적 메모리 공간을 사용했으며 그것이 불필요해지는 순간 free를 이용하여 그 공간을 운영체제에 반납해주어야 함 Nptr Head; Head = (node *)malloc(sizeof(node)); Head -> Data = 11; Head -> Next = NULL Head = NULL; 이 부분에서 free(Head); 필요 Data Structure

2. C에 의한 리스트 구현 연결 리스트의 출력 Temp = Head; while (Temp != NULL) {
printf("%d ", Temp->Data); Temp = Temp->Next; } 왜 Temp를 사용하는가? Data Structure

2. C에 의한 리스트 구현 삽입 아래 수행 코드 전에 Temp를 삽입 직전의 노드를 가리키도록 함
p = (node *)malloc(sizeof(node)); p->Data = 8; p->Next = Temp->Next; Temp->Next = p; Data Structure

2. C에 의한 리스트 구현 삭제 아래 수행 코드 전에 Temp를 삭제 직전의 노드를 가리키도록 함
p = Temp->Next; Temp->Next = Temp->Next->Next; free p; 삭제 될 노드를 먼저 p에 담아 두고 삭제 작업이 끝나면 p를 free해야 하는 일 중요 free p를 삭제 작업 보다 먼저 수행하면? Data Structure

2. C에 의한 리스트 구현 Linked List를 활용하여 C로 구현한 리스트 중요 자료구조 listType
typedef struct { int Data; node* Next; } node; typedef node* Nptr; int Count; 리스트 길이를 추적하고 있음 Nptr Head; 헤드 포인터로 리스트 전체를 대변함 } listType; Data Structure

2. C에 의한 리스트 구현 인터페이스 코드 typedef struct { int Data; node* Next;
typedef node* Nptr; 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); int IsEmpty(listType *Lptr); int Length(listType *Lptr); Data Structure

2. C에 의한 리스트 구현 구현 코드 – Init, IsEmpty
#include <ListP.h> 헤더파일을 포함 void Init(listType *Lptr) { Lptr->Count = 0; 리스트 길이를 0으로 초기화 Lptr->Head = NULL; 헤드 포인터를 널로 초기화 } int IsEmpty(listType *Lptr) { 빈 리스트인지 확인하기 return (Lptr->Count = = 0); 리스트 길이가 0이면 빈 리스트 } Data Structure

2. C에 의한 리스트 구현 구현 코드 – Insert
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; for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; p->Next = Temp->Next; Temp->Next = p; } Lptr->Count += 1; } Lptr->Head p NULL Lptr->head p NULL (1) (2) Temp NULL (2) (1) p Data Structure

2. C에 의한 리스트 구현 배열을 이용한 Insert 구현에 비하여 Linked List를 이용한 Insert 구현의 차이점
장점 저장 공간이 꽉 차 있는지 테스트할 필요가 없음 얼마든지 동적으로 새로운 노드를 추가 가능 중간위치 삽입에 따른 밀림(Shift)이 불필요 단점 삽입직전 노드를 찾아가는 작업이 배열에 비해 오래 걸림 배열: 직접 접근 연결 리스트: 포인터를 따라서 리스트 순회 (Traversal) Data Structure

2. C에 의한 리스트 구현 구현 코드 – Delete
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; Nptr p = Temp->Next; Temp->Next = p->Next; } Lptr->Count -= 1; free (p); } Lptr->Head NULL p Temp NULL NULL p Data Structure

2. C에 의한 리스트 구현 값 기반 연결 리스트의 삭제 위와 같은 코드로는 Temp를 삭제 직전에 놓이게 할 수 없음
Temp = Lptr->Head; while((Temp != NULL) && (Temp->Data != Item) Temp = Temp->Next; Data Structure

2. C에 의한 리스트 구현 예견 (Look Ahead) 방식 But, 아래 그림에서 데이터 15인 노드 삭제
Temp가 데이터 12인 노드를 가리킬 때, Temp는 널이 아니지만 Temp->Next는 널임. Temp = Lptr->Head; while((Temp != NULL) && (Temp->Next->Data != Item) Temp = Temp->Next; Data Structure

2. C에 의한 리스트 구현 구현 코드 – Delete 2 (값 기반 삭제)
Prev는 일종의 Flag로 사용 Delete(listType *Lptr, int Item) { Nptr Prev = NULL; Nptr Temp = Lptr->Head; while((Temp != NULL) && (Temp->Data != Item) { Prev = Temp; Temp = Temp->Next; } if (Prev = = NULL) { if (Temp = = NULL) printf("No Nodes to Delete"); 리스트 자체가 비어있음 else { 삭제 대상이 첫 노드 Lptr->Head = Lptr->Head->Next; free (Temp); Lptr->Count - = 1; } else { if (Temp = = NULL) printf("No Such Nodes"); 삭제 대상이 없음 else { 삭제 대상이 중간에 있음 Prev -> Next = Temp -> Next; free (Temp); Lptr->Count - = 1; Prev NULL Temp Data Structure

2. C에 의한 리스트 구현 Doubly-Linked List (이중 연결 리스트) typedef struct {
int Data; node* Prev, Next; } node; Data Structure

2. C에 의한 리스트 구현 Tail Pointer (꼬리 포인터) 삽입은 주로 리스트의 끝부분에서 많이 발생함
Head Pointer에서 리스트 끝까지 계속 따라 가면 시간이 많이 걸림 Tail Pointer를 두어 해결함 삭제일 경우에는 Tail Pointer가 뒤로 이동해야 함 이중 연결 이어야 테일 포인터를 뒤로 이동할 수 있음. Data Structure

2. C에 의한 리스트 구현 Doubly-Linked List 의 특징 및 장점 Trade-off (타협, 균형)
정의: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 현재의 바로 이전 노드를 찾기가 쉽다. 링크가 양방향이므로 양방향으로 검색이 가능 Trade-off (타협, 균형) Singly-Linked List vs. Doubly-Linked List 삽입, 삭제의 시간 측면 메모리 사용 공간의 측면 프로그램 코딩의 양 측면 Data Structure

2. C에 의한 리스트 구현 Doubly-Linked List 구현
헤드 노드(head node): 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드 헤드 포인터와의 구별 필요 공백상태에서는 헤드 노드만 존재 삽입 연산 (1) (2) (3) (4) before new_node Data Structure

2. C에 의한 리스트 구현 Circular-Linked List (원형 연결 리스트) Time Sharing System
Time Slice 사용자 교대 Round Robin Algorithm Circular Singly-Linked List Circular Doubly-Linked List Data Structure

ListA.h (C++ Interface by Array) ListA.h (C Interface by Array)
C++ 배열에 의한 리스트와 C 배열에 의한 리스트 비교 ListA.h (C++ Interface by Array) 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 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); int IsEmpty(listType *Lptr); int Length(listType *Lptr); typedef struct { int Count; int Data[MAX]; } listType; Data Structure

3. C++에 의한 리스트 구현 C와 C++의 비교 (1/2) C++가 좀 더 조직화된 모습
클래스 안에 데이터와 데이터에 가해질 함수를 함께 넣어 놓음 C에서는 어떤 데이터가 어떤 함수에 이용되는지 분간이 어려움 함수의 선언에서 자료구조를 파라미터로 넘기느냐 마느냐의 차이 listType List1; List1.Delete(&List1, 3); vs. List1.Delete(3); List1.Delete(3)과 List2.Delete(3)이라고 할 때 작업이 가해지는 대상은 이미 정해져 있음 C에서 함수안에 자료구조가 파라미터로 들어가는 것의 의미 프로그래머는 포인터가 가리키는 것이 구조체라는 점 및 구조체의 내부 구조에 대하여 어느 정도 파악을 해야 함 C++는 Abstraction 개념을 수용하여 위와 같은 불편을 해소 Data Structure

3. C++에 의한 리스트 구현 C와 C++의 비교 (2/2) C++는 Alias를 이용하여 참조 호출 효과를 기함
C++에서 Constructor의 편리함 C++에서는 객체가 만들어 질 때 자동으로 내부 구성이 초기화됨 C에서는 listType List1; 이라고 한 후 반드시 Init(&List1)을 통하여 별도로 초기화를 해주어야 함 Data Structure

3. C++에 의한 리스트 구현 Heap 공간과 Destructor Function 복사 생성자
일단, 위 코드에서 변수 T의 공간이 Heap에 만들어지는 것이 아니라는 점 주의 malloc에 의해 T가 가리키는 변수가 Heap에 만들어짐 함수가 끝나기 전에 C의 free나 C++의 delete로 Heap 메모리 반납해야 함 C++의 소멸자 함수는 객체멤버 변수들 중 Heap에 할당되어진 것들에 대하여 공간 반납을 자동으로 할 수 있도록 코딩을 할 수 있다. 복사 생성자 교재 199~200 void fcn (int P) { int R, S[20], *T; T = (int *) malloc (sizeof(int)); } Data Structure

3. C++에 의한 리스트 구현 배열을 이용한 C++ 리스트 구현: 생성자, 복사 생성자, 소멸자
#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]; } 깊은 복사에 의해 배열 요소 모두를 복사 Data Structure

3. C++에 의한 리스트 구현 연결 리스트를 활용한 C++ 리스트 코드: 인터페이스 화일
typedef struct { int Data; node* Next; } node; typedef node* Nptr; 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; } 함수에 대한 정의는 배열을 활용한 C++ 인터페이스 파일과 완전 동일하다. => 이것이 다르다면 사용과 구현을 분리하는 객체 지향의 근본 취지에 어긋난다. Data Structure

3. C++에 의한 리스트 구현 연결 리스트를 활용한 C++ 리스트 코드: 구현 (1/3)
#include <ListP.h> listClass::listClass( ) { 생성자 함수 Count = 0; 리스트의 길이를 0으로 초기화 Head = NULL; 헤드를 널로 초기화 } bool listClass::IsEmpty( ) { 빈 리스트인지 확인하는 함수 return (Count = = 0); 배열 길이 0이면 TRUE Data Structure

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); 메모리 공간 반납 } Data Structure

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; 사본의 현재 노드에 새 노드를 붙임 (1) Temp1 = Temp1 -> Next; 새 노드로 이동 (2) Temp1->Data = Temp2->Data; 새 노드에 원본 데이터를 복사 (3) } Temp1->Next = NULL; 사본의 마지막 노드의 Next에 널을 기입 Data Structure

3. C++에 의한 리스트 구현 Head Temp1 Temp2 Head Temp1 Head Temp1 (2) (1) (3)
Data Structure

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

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

Homework 4장 연습문제 5장 연습문제 모든 문제는 C언어 함수 or C++ 함수로 작성.
20번 – 정수 N을 입력 받아서 N까지의 합을 출력하는 C함수를 다음 두 가지 형식으로 작성하라. 24번 – 참고: N2 = N*10 + 2 29번 5장 연습문제 24번 – 노드 순서를 완전히 역으로 뒤집은 리스트 반환 30번 44번 50번 모든 문제는 C언어 함수 or C++ 함수로 작성. 요구되어지는 함수 뿐만 아니라 main 까지 작성하여 수행가능 하도록 코딩함 게시물 제목은 반드시 다음을 따름 자료구조-3차- Due Date: 4월 20일, 23시 59분 59초 Data Structure

Internet Computing KUT Youn-Hee Han

Similar presentations

Presentation on theme: "Internet Computing KUT Youn-Hee Han"— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

Internet Computing KUT Youn-Hee Han

Similar presentations

Presentation on theme: "Internet Computing KUT Youn-Hee Han"— Presentation transcript:

Similar presentations

About project

지원