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

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

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

슬라이드 1

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

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

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

chap 5: Trees

슬라이드 1

11장 포인터

Chapter 4. LISTS

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

1장. 리스트

Chapter 4. LISTS

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

Microsoft PowerPoint - 자료구조2008Chap06

06장.리스트

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

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

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

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

Chapter 4. LISTS

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

슬라이드 1

PowerPoint 프레젠테이션

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

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

슬라이드 1

슬라이드 1

Microsoft PowerPoint - 06-List.ppt

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

슬라이드 1

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

4장

슬라이드 1

Microsoft PowerPoint - chap4_list

슬라이드 1

03_queue

K&R2 Reference Manual 번역본

untitled


<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

Algorithms

중간고사 (자료 구조)

Microsoft PowerPoint - ch07 - 포인터 pm0415

Chapter #01 Subject

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

untitled

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

<4D F736F F F696E74202D20B8B6C0CCC5A9B7CEC7C1B7CEBCBCBCAD202839C1D6C2F7207E203135C1D6C2F >

chap01_time_complexity.key

C 언어 강의노트

03장.스택.key

PowerPoint Template

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

BMP 파일 처리

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

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

KNK_C_05_Pointers_Arrays_structures_summary_v02

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

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

슬라이드 1

Microsoft PowerPoint - chap06-2pointer.ppt

1장. 유닉스 시스템 프로그래밍 개요

PowerPoint 프레젠테이션

Microsoft PowerPoint - chap13-입출력라이브러리.pptx

Microsoft PowerPoint - 08-Queue.ppt

슬라이드 1


C프로-3장c03逞풚

기초컴퓨터프로그래밍

구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined data types) : 다양한자료형을묶어서목적에따라새로운자료형을

chap8.PDF

Microsoft PowerPoint - 08-chap06-Queue.ppt

슬라이드 1

01_List

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

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

UI TASK & KEY EVENT

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어

본 강의에 들어가기 전

PowerPoint 프레젠테이션

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

11장 포인터

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt

Microsoft PowerPoint - chap-11.pptx

설계란 무엇인가?

Frama-C/JESSIS 사용법 소개

PowerPoint 프레젠테이션

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

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D>

Microsoft PowerPoint - Chapter_09.pptx

쉽게 풀어쓴 C 프로그래밍

untitled

슬라이드 1


UI TASK & KEY EVENT

02장.배열과 클래스

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

Transcription:

Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular Singly-linked list의각함수를구현한다. 실습순서 단계 1. 주어지는코드와제시된함수설계를참고해 Circular singly-linked list의각함수들을완성한다. ( 이 Circular singly-linked list는 head 포인터가리스트의첫번째노드를가리키고있는리스트이다.) 1) 리스트에 data를하나삽입하는 void insertlistitem(list *list, char data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의 data를받으며반환값은없다. 이함수는매개변수로전달받은리스트에서커서가가리키는곳의다음위치에 data를삽입하는함수이다. 새로만들어지는노드는동적메모리할당을하는함수인 malloc() 을이용해서만든다. 2) 리스트의처음위치에 data를하나삽입하는 void insertlistfirstitem(list *list, char data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의 data를받으며반환값은없다. 이함수는매개변수로전달받은리스트의처음위치에 data를삽입하는함수이다. 새로만들어지는노드는동적메모리할당을하는함수인 malloc() 을이용해서만든다. 3) 리스트에서 data를하나삭제하는 void deletelistitem(list *list, char *data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의포인터를받고반환값은없다. 이함수는매개변수로전달받은리스트의커서가가리키는곳에위치하는노드를삭제하는함수이다. 삭제된노드의 data는두번째매개변수인포인터형의 data에값을저장해외부로전달하고, 삭제된노드는더이상사용할필요가없으므로할당되어있는메모리를해제한다. 4) 리스트에서커서를이동시키는함수 void moveleft (LIST *list) 와 void moveright (LIST *list) 를선언한다. 이함수들은각각커서를왼쪽과오른쪽으로이동시키는함수이며, 매개변수로 LIST형의구조체포인터를받고반환값은없다. 두함수는커서를이동시킬수없는상황에서이동을시키려하면에러메시지를출력하며이동이불가능하게구현되어야한다. (ex) 리스트에노드가한개밖에없는경우등 )

#include <stdio.h> #include <conio.h> #include <stdlib.h> // 리스트의최대크기 #define MAX 10 // 리스트노드구조체 struct ListNode char data; // 저장 data struct ListNode *next; // 다음노드의포인터 ; typedef struct ListNode LISTNODE; // 리스트구조체 struct List int listsize; // 리스트의크기 LISTNODE *cursor; // 현재커서의위치 LISTNODE *head; // 첫번째노드의주소 ; typedef struct List LIST; void initlist(list *list); // 리스트초기화함수 void printlist(list *list); // 리스트출력함수 bool isempty(list *list); // 리스트가비어있는지확인하는함수 bool isfull(list *list); // 리스트가가득차있는지확인하는함수 void insertlistitem(list *list, char data); // 리스트에 data를입력하는함수 void insertlistfirstitem(list *list, char data); // 리스트의맨앞에 data를입력하는함수 void deletelistitem(list *list, char *data); // 리스트에서 data를삭제하는함수 void moveleft(list *list); // 리스트에서커서를왼쪽으로이동시키는함수 void moveright(list *list); // 리스트에서커서를오른쪽으로이동시키는함수 void main() LIST *list; char cmd; char data; printf("**************** Choose Command!! ****************** n"); printf("+: insert, -: delete, F: full check, E: empty check n"); printf("s: insert(first) L: move left R: move right Q: Quit n"); printf("**************************************************** n"); // 리스트에동적으로메모리할당 list = (LIST *)malloc(sizeof(list)); // 리스트초기화 initlist(list);

do // 커맨드입력 printf("command: "); cmd = getch(); // 커맨드는무조건대문자로입력 cmd = toupper(cmd); putch(cmd); switch (cmd) case '+' : // data 입력 printf("type the item that be inserted. :"); data = getch(); putch(data); insertlistitem(list,data); case 'S' : // data 입력 printf("type the item that be inserted. :"); data = getch(); putch(data); insertlistfirstitem(list,data); case '-' : // data 삭제 deletelistitem(list,&data); printf("deleted Item : %c n", data); case 'E' : // 비어있는지확인 if (isempty(list)) printf ("List is empty! n"); printf ("List isn't empty n"); case 'F' : // 가득찼는지확인 if (isfull(list)) printf ("List is full! n"); printf ("List isn't full! n"); case 'L' : // 왼쪽으로커서이동 moveleft(list); case 'R' : // 오른쪽으로커서이동 moveright(list); case 'Q' : // 종료 default : // 잘못된커맨드입력시 printf(" nwrong command! Retry! n"); // 리스트출력 printlist(list); while ( cmd!='q' );

// 리스트초기화함수 void initlist(list *list) // 리스트구조체의멤버를각각초기화한다. // 리스트크기 = 0, 커서와첫번째노드 = NULL list->head = list->cursor = NULL; list->listsize = 0; // 리스트가비어있는지확인 bool isempty(list *list) if (list->listsize == 0) return true; return false; // 리스트가가득찼는지확인 bool isfull(list *list) if (list->listsize == MAX) return true; return false; // 리스트출력 void printlist(list *list) // 임시사용포인터선언 LISTNODE *tempcursor; // 리스트의첫노드를가리킴 if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); printf("item list. n"); do // 커서가있는곳은 [] 로표시 if (tempcursor == list->cursor) printf(" [%c] ",tempcursor->data); printf(" %c ",tempcursor->data); tempcursor = tempcursor->next; while(tempcursor!= list->head);

// 리스트에 data를입력하는함수 void insertlistitem(list *list, char data) if (isfull(list)) printf("list is full! Can't insert. n"); // 새로운노드선언 LISTNODE *tempnode; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->data = data; if (isempty(list)) // 리스트가비어있는경우 list->head = tempnode; list->cursor = tempnode; tempnode->next = tempnode; // 그외의경우 ( 가운데 + 마지막위치에삽입 ) tempnode->next = list->cursor->next; list->cursor->next = tempnode; list->cursor = list->cursor->next; list->listsize++; // 리스트의처음위치에 data를삽입하는함수 void insertlistfirstitem(list *list, char data) if (isfull(list)) printf("list is full! Can't insert. n"); // 새로운노드선언 LISTNODE *tempnode, *tempcursor; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->data = data; if (isempty(list)) // 리스트가비어있는경우 list->head = tempnode; list->cursor = tempnode; tempnode->next = tempnode;

// 그외의경우 // 리스트마지막노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->head) tempcursor=tempcursor->next; tempnode->next = list->head; tempcursor->next = tempnode; list->head = tempnode; list->cursor = tempnode; list->listsize++; // 리스트에서 data를삭제하는함수 void deletelistitem(list *list, char *data) // 삭제된 data를저장할임시변수 char deleted = NULL; if (isempty(list)) printf("list is empty! Can't delete. n"); // 임시로사용할포인터선언 LISTNODE *tempcursor, *tempnode; // tempnode = 삭제될노드의위치 tempnode = list->cursor; deleted = list->cursor->data; // 리스트에노드가한개만있는경우 if (list->listsize == 1) list->cursor = NULL; list->head = NULL; // 커서가리스트의첫노드에있는경우 if (list->head == list->cursor) // 리스트마지막노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->head) tempcursor=tempcursor->next; tempcursor->next = list->cursor->next; list->head = list->cursor->next; list->cursor = list->cursor->next;

// 그외의경우 ( 가운데 + 마지막노드삭제 ) // 현재커서가가리키는노드의직전노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->cursor) tempcursor=tempcursor->next; tempcursor->next = list->cursor->next; list->cursor = tempcursor; list->listsize--; // 삭제할노드의메모리해제 free(tempnode); // 삭제된 data를외부에전달 *data = deleted; // 커서를오른쪽으로이동시키는함수 void moveright(list *list) if (isempty(list)) printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없는경우 if (list->listsize == 1) printf("the cursor is in the last item! Can't move n"); list->cursor = list->cursor->next; // 커서를왼쪽으로이동시키는함수 void moveleft(list *list) if (isempty(list)) printf("list is empty! Can't move. n"); // 임시저장용포인터선언 LISTNODE *tempcursor;

// 리스트에노드가 1개밖에없는경우 if (list->listsize == 1) printf("the cursor is in the first item! Can't move n"); // 현재커서가가리키는노드직전까지 tempcursor를이동시킴 while(tempcursor->next!= list->cursor) tempcursor=tempcursor->next; list->cursor = tempcursor; 단계 2. 단계 1에서완성된프로그램을실행시켜각함수들을테스트해보고그결과화면을캡쳐하시오. 단계 3. 단계 1에서완성된프로그램을수정해서 head 포인터가리스트의마지막노드를가리키고있는형태의 Circular singly-linked list를구현하시오. 단계 1에서의프로그램과모든기능이동일하게동작하여야한다. ( 단, printlist() 함수는다음코드를참고해수정하시오.) // 리스트출력 void printlist(list *list) // 임시사용포인터선언 LISTNODE *tempcursor; if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); // 리스트의첫노드를가리킴 tempcursor = list->head->next; printf("item list. n");

do // 커서가있는곳은 [] 로표시 if (tempcursor == list->cursor) printf(" [%c] ",tempcursor->data); printf(" %c ",tempcursor->data); tempcursor = tempcursor->next; while(tempcursor!= list->head->next); 단계 4. 단계 1과단계 3에서완성된두가지종류의 Circular singly-linked List에대해삽입, 삭제의용이성을프로그래머의관점에서비교하시오. 과제수행결과 ( 결과화면및소감 )