조 병 규 Software Quality Lab. 한 국 교 통 대 학 교 Algorithm Linear Structure 조 병 규 Software Quality Lab. 한 국 교 통 대 학 교

(순차) 리스트 (linear, ordered, sequential , dense) list 일반적으로 특성이 같은 원소 (elelment, atom, node, record)들의 순서적 집합   A = {a1, a2, a3, ∙ ∙ ∙, a1, an} 공 리스트(null list) : 원소가 없는 리스트 SQ Lab.

리스트의 조작 삽입(insertion) 삭제(deletion) 수정(correction) 순회(traverse) 검색(search) SQ Lab.

리스트의 표현 방법 배열(array) 연결 리스트(linked list) SQ Lab.

배열 배열명(array name) 각 배열에 부여한 명칭 배열 원소(array element) 배열을 구성하는 원소 배열 크기(array size) 배열을 구성하는 원소의 수 또는 배열을 구성하는 바이트(byte) 수 첨자(subscript) 배열의 특정 원소를 지적하는 것 SQ Lab.

배열의 종류 1차원 배열(one dimensional array) 2차원 배열(two dimensional array) 3차원 배열(three dimensional array) . n차원 배열(n dimensional array) SQ Lab.

문제 : 배열의 정리 각 프로그래밍 언어에서 배열 표현을 정리하시오. 배열을 이용한 원소의 삽입, 삭제, 수정, 방문, 검색의 처리하는 프로그램을 구현하시오. SQ Lab.

배열을 이용한 리스트의 구현 (1/8) SQ Lab. /*001*/ // singlyClassArray01 /*002*/ /*003*/ #include "iostream" /*004*/ /*005*/ using namespace std; /*006*/ /*007*/ const int arraySize=10; /*008*/ /*009*/ class singlyClass /*010*/ { /*011*/ private: /*012*/ int intList[arraySize]; /*013*/ int intMax; /*014*/ int index; /*015*/ public: /*016*/ singlyClass() /*017*/ { /*018*/ intMax = 0; /*019*/ } /*020*/ void insert(int); /*021*/ int remove(int); /*022*/ int search(int); /*023*/ void traverse(); /*024*/ }; /*025*/ SQ Lab.

배열을 이용한 리스트의 구현 (2/8) /*026*/ void singlyClass::insert(int intValue) /*027*/ { /*028*/ intMax = intMax + 1; /*029*/ if(intMax < arraySize) /*030*/ { /*031*/ intList[intMax] = intValue; /*032*/ } /*033*/ else /*034*/ { /*035*/ cout << "\n Error : overflow\n"; /*036*/ intMax = intMax - 1; /*037*/ } /*038*/ }; /*039*/ SQ Lab.

배열을 이용한 리스트의 구현 (3/8) /*040*/ int singlyClass::remove(int intValue) /*041*/ { /*042*/ for(index=1; index<=intMax; index++) /*043*/ { /*044*/ if(intValue==intList[index]) /*045*/ { /*046*/ for(int i=index; i<intMax; i++) /*047*/ { /*048*/ intList[i] = intList[i+1]; /*049*/ } /*050*/ intMax = intMax - 1; /*051*/ return index; /*052*/ } /*053*/ } /*054*/ return 0; /*055*/ }; /*056*/ SQ Lab.

배열을 이용한 리스트의 구현 (4/8) /*057*/ int singlyClass::search(int intValue) /*058*/ { /*059*/ for(index=1; index<=intMax; index++) /*060*/ { /*061*/ if(intValue==intList[index]) /*062*/ { /*063*/ return index; /*064*/ } /*065*/ } /*066*/ return 0; /*067*/ } /*068*/ SQ Lab.

배열을 이용한 리스트의 구현 (5/8) /*069*/ void singlyClass::traverse() /*070*/ { /*070*/ { /*071*/ if(intMax==0) /*072*/ { /*073*/ cout << "\n Have no node \n"; /*074*/ } /*075*/ else /*076*/ { /*077*/ for(index=1; index<=intMax; index++) /*078*/ { /*079*/ cout << "\n " << intList[index]; /*080*/ } /*081*/ cout << "\n"; /*082*/ } /*083*/ } /*084*/ SQ Lab.

배열을 이용한 리스트의 구현 (6/8) /*085*/ void main() /*086*/ { /*086*/ { /*087*/ singlyClass singlyObject01; /*088*/ int choice; /*089*/ int intValue; /*090*/ int index; /*091*/ /*092*/ cout << "\n insert=1, delete=2, search=3, traverse=4, quit=9 : "; /*093*/ cin >> choice; /*094*/ while(choice != 9) /*095*/ { /*096*/ switch(choice) /*097*/ { /*098*/ case 1 : // insert /*099*/ cout << " Type insert intValue : "; /*100*/ cin >> intValue; /*101*/ singlyObject01.insert(intValue); /*102*/ break; SQ Lab.

배열을 이용한 리스트의 구현 (7/8) /*103*/ case 2 : // delete /*104*/ cout << " Type remove intValue : "; /*105*/ cin >> intValue; /*106*/ index = singlyObject01.remove(intValue); /*107*/ if(index==0) /*108*/ cout << "\n Have no node \n"; /*109*/ else /*110*/ cout << "\n index : " << index << "\n"; /*111*/ break; /*112*/ case 3 : // search /*113*/ cout << " Type search intValue : "; /*114*/ cin >> intValue; /*115*/ index = singlyObject01.search(intValue); /*116*/ if(index==0) /*117*/ cout << "\n Have no node \n"; /*118*/ else /*119*/ cout << "\n index : " << index << "\n"; /*120*/ break; /*121*/ case 4 : // traverse /*122*/ singlyObject01.traverse(); /*123*/ break; /*124*/ default: cout << "\n Type Error \n"; /*125*/ } SQ Lab.

배열을 이용한 리스트의 구현 (8/8) /*126*/ cout << "\n insert=1, delete=2, search=3, traverse=4, quit=9 : "; /*127*/ cin >> choice; /*128*/ } /*129*/ /*130*/ singlyObject01.traverse(); /*131*/ /*132*/ cin.get(); /*133*/ cout << "\n\n Type any character: "; /*134*/ cin.get(); /*135*/ } SQ Lab.

연결 리스트 연결 리스트명(linked list name) 연결 리스트에 부여한 명칭 노드(node) 연결 리스트를 구성하는 원소로서       구조는 자료를 수록할 부분(data field)들과       다음 노드의 위치를 수록할 부분(pointer/link field)으로 구성된 레코드 형태 헤드 노드(head node) 연결 리스트의 처음 원소를 지적하며       경우에 따라 그 외의 정보를 수록하는 노드 연결 리스트의 크기(linked list size) 연결 리스트를 구성하는 원소의 수                           포인터/링크(pointer/link) 다음 원소의 위치(주소)를 수록하는 항목       다음 노드가 없을 경우 /(nil/null) 표현 SQ Lab.

연결 리스트의 종류 단일 연결 리스트(singly linked list) 포인터가 한 개인 원소(들)로 구성된 리스트    포인터가 한 개인 원소(들)로 구성된 리스트 다중 연결 리스트(multi linked list)    포인터가 두 개 이상인 원소(들)로 구성된 리스트  원형 리스트(circular linked list)      마지막 원소가 첫 번째 원소를 지적하게 구성된 리스트 자료수록부분 link 자료수록부분 link1 . . . linkn link 자료수록부분 SQ Lab.

문제 : 연결 리스트의 구현 각 프로그래밍 언어에서 연결 리스트를 표현하기 위한 방법을 정리하시오. 단일 연결 리스트를 구현하시오. 이중 연결 리스트를 구현하시오. 단일 환형 연결 리스트를 구현하시오. SQ Lab.

단일 연결 리스트의 구현 (1/10) /*001*/ // singlyClassLinked01 /*002*/ /*003*/ #include "iostream" /*004*/ /*005*/ using namespace std; /*006*/ /*007*/ struct nodeType /*008*/ { /*009*/ char* name; /*010*/ nodeType* link; /*011*/ }; /*012*/ /*013*/ const int null=0; /*014*/ SQ Lab.

단일 연결 리스트의 구현 (2/10) /*015*/ class singlyClass /*016*/ { /*016*/ { /*017*/ private: /*018*/ nodeType* newNode; /*019*/ nodeType* head; /*020*/ nodeType* current; /*021*/ nodeType* previousNode; /*022*/ public: /*023*/ singlyClass() /*024*/ { /*025*/ head=null; /*026*/ } /*027*/ void insert(char *); /*028*/ nodeType *remove(char *); /*029*/ nodeType *search(char *); /*030*/ void traverse(); /*031*/ }; /*032*/ SQ Lab.

단일 연결 리스트의 구현 (3/10) /*033*/ void singlyClass::insert(char *name) /*034*/ { /*035*/ newNode = new nodeType; /*036*/ newNode->name = name; /*037*/ newNode->link = null; /*038*/ if(head==null) /*039*/ { /*040*/ head = newNode; /*041*/ } /*042*/ else /*043*/ { /*044*/ current = head; /*045*/ while(current!=null) /*046*/ { /*047*/ previousNode = current; /*048*/ current = current->link; /*049*/ }; /*050*/ previousNode->link = newNode; /*051*/ } /*052*/ }; /*053*/ SQ Lab.

단일 연결 리스트의 구현 (4/10) /*054*/ nodeType *singlyClass::remove(char* name) /*055*/ { /*056*/ current = head; /*057*/ if(current!=null) /*058*/ { /*059*/ if(!strcmp(head->name, name)) /*060*/ { /*061*/ head = current->link; /*062*/ } /*063*/ else /*064*/ { /*065*/ while(current!=null) /*066*/ { /*067*/ if(strcmp(current->name, name)) /*068*/ { /*069*/ previousNode = current; /*070*/ current = current->link; /*071*/ } /*072*/ else /*073*/ { /*074*/ previousNode->link = current->link; /*075*/ break; /*076*/ } /*077*/ } /*078*/ } /*079*/ } /*080*/ return current; /*081*/ }; SQ Lab.

단일 연결 리스트의 구현 (5/10) /*082*/ /*083*/ nodeType *singlyClass::search(char* name) /*084*/ { /*085*/ current = head; /*086*/ while(current!=null) /*087*/ { /*088*/ if(strcmp(current->name, name)) /*089*/ current = current->link; /*090*/ else break; /*091*/ } /*092*/ return current; /*093*/ }; /*094*/ SQ Lab.

단일 연결 리스트의 구현 (6/10) /*095*/ void singlyClass::traverse() /*096*/ { /*096*/ { /*097*/ if(head==null) /*098*/ { /*099*/ cout << "\n Have no node \n"; /*100*/ } /*101*/ else /*102*/ { /*103*/ current = head; /*104*/ while(current!=null) /*105*/ { /*106*/ cout << "\n " << current->name; /*107*/ current = current->link; /*108*/ } /*109*/ cout << "\n"; /*110*/ } /*111*/ } /*112*/ SQ Lab.

단일 연결 리스트의 구현 (7/10) /*113*/ void main() /*114*/ { /*115*/ int choice; /*114*/ { /*115*/ int choice; /*116*/ singlyClass singlyObject01; /*117*/ char* name; /*118*/ nodeType* workNode; /*119*/ /*120*/ cout << "\n insert=1, delete=2, search=3, traverse=4, quit=9 : "; /*121*/ cin >> choice; /*122*/ while(choice != 9) /*123*/ { /*124*/ switch(choice) /*125*/ { /*126*/ case 1 : // insert /*127*/ cout << " Type insert name : "; /*128*/ name = new char; /*129*/ cin >> name; /*130*/ singlyObject01.insert(name); /*131*/ break; SQ Lab.

단일 연결 리스트의 구현 (8/10) /*132*/ case 2 : // delete /*133*/ cout << " Type remove name : "; /*134*/ name = new char; /*135*/ cin >> name; /*136*/ workNode = singlyObject01.remove(name); /*137*/ if(workNode==null) /*138*/ cout << "\n Have no node \n"; /*139*/ else /*140*/ cout << "\n delete name : " << workNode->name << "\n"; /*141*/ break; /*142*/ case 3 : // search /*143*/ cout << " Type search name : "; /*144*/ name = new char; /*145*/ cin >> name; /*146*/ workNode = singlyObject01.search(name); /*147*/ if(workNode==null) /*148*/ cout << "\n Have no node \n"; /*149*/ else /*150*/ cout << "\n search name : " << workNode->name << "\n"; /*151*/ break; /*152*/ case 4 : // traverse /*153*/ singlyObject01.traverse(); /*154*/ break; /*155*/ default: cout << "\n Type Error \n"; /*156*/ } SQ Lab.

단일 연결 리스트의 구현 (9/10) /*157*/ cout << "\n insert=1, delete=2, search=3, traverse=4, quit=9 : "; /*158*/ cin >> choice; /*159*/ } /*160*/ SQ Lab.

단일 연결 리스트의 구현 (10/10) /*161*/ singlyObject01.traverse(); /*162*/ /*163*/ cin.get(); /*164*/ cout << "\n\n Type any character: "; /*165*/ cin.get(); /*166*/ } SQ Lab.

quiz 이중 연결 리스트를 구현하시오. 단일 환형 연결 리스트를 구현하시오. SQ Lab.

제한된 리스트(restricted list) 원소의 삽입/삭제의 발생 위치를 제한하여 형성시킨 리스트 종류 SQ Lab.

스택(stack) 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 발생 나중에 삽입된 원소가 먼저 삭제 LIFO : Last In First Out 용어 - top : 원소의 삽입/삭제 위치 - pop : 원소의 삭제 - push : 원소의 삽입 SQ Lab.

quiz : 스택(stack)의 구현 배열을 이용하여 스택을 구현하시오. 연결 리스트를 이용하여 스택을 구현하시오. SQ Lab.

큐(queue) 원소의 삽입은 리스트의 한쪽 끝에서 발생(rear) 삭제는 삽입의 반대쪽 끝에서 발생(front) 먼저 삽입된 원소가 먼저 삭제 FIFO : First In First Out SQ Lab.

quiz : 큐(queue)의 구현 배열을 이용하여 큐를 구현하시오. 연결 리스트를 이용하여 큐를 구현하시오 SQ Lab.