Lecture/자료구조/2007

개요

• 교수 : 박상원
• 조교 : 박원주
  • wjpark@dislab.hufs.ac.kr
  • 공대 401호
  • Tel: 330-4547
• 수업시간 : 월 (5,6), 화 (2)

교안

1. 소프트웨어 공학과 프로그래밍 기법
2. 순차 데이타 표현
3. 연결 데이타 표현
4. 스택
5. 큐
6. 트리
7. 이원탐색트리
8. 그래프
9. 가중치 그래프
10. 정렬
11. 균형 탐색 트리

과제

다항식 덧셈

• 제출 기간 : 3월 26일 까지
• 두 다항식을 더하여 그 결과를 출력한다.

예) p1 = 2x^3 + 3x + 3 
p2 = 3x^6 + 23x^3 - 3 x
문제) p1 + p2
입력형태 :
3 3 3 1 3 0
3 6 23 3 -3 1

• 출력형태 : 3x^6 + 26x^3 + 3
• 제출문 : 보고서
• 하루 늦을때 마다 1점 감점
• 조교에게 실행 결과 검사 맡을 것

단순 연결 리스트 이해

• 제출 기간 : 4월 2일 까지
• 교안 44페이지~49페이지에 있는 코드를 입력 및 컴파일
• 컴파일 후 debugging mode로 한 라인씩 수행
• 각 코드의 의미를 분석하는 보고서 작성

• 연합엠티와 관련하여 4월 4일(수요일)로 제출일을 변경합니다.

Double linked list

• 제출 기간 : 4월 4일 까지
• 교안 61 페이지에 있는 다음 함수를 작성하시오. 리스트는 이중 연결 리스트로 만드시오.

void addLastNode(h_linkedList* H, char* x)
void reverse(h_linkedList* H)
void deleteLastNode(h_linkedList* H)
void printList(h_linkedList* H)

사용 언어 : C, C++

리스트 노드와 리스트 헤드의 자료구조는 다음과 같다.

typedef struct listNode {
     char data[5];  /* char* data; 로 해도 무방 */
     struct listNode* next;
     struct listNode* prev;
} listNode;
 
typedef struct {
    int length;
    listNode* head;
    listNode* tail;
} h_linkedList;

main 함수는 위 4개의 함수를 조합하여 실행 결과를 확인할 수 있도록 작성

(예제)

void main(int argc, char** argv)
{
    h_linkedList* h;
    h = (h_linkedList*)malloc(sizeof(h_linkedList));
    h->length = 0; h->head = h->tail = 0;
    /* 혹은 위 코드를 memset(h, 0, sizeof(h_linkedList)); 으로 해도 됨 */
    /* 이 함수는 h 번지부터 sizeof(h_linkedList) 바이트를 0으로 채움 */
    addLastNode(h, "kim");
    addLastNode(h, "park");
    addLastNode(h, "lee");
    addLastNode(h, "hong");
    printList(h);
    reverse(h);
    printList(h);
    deleteLastNode(h);
    printList(h);
    deleteLastNode(h);
    printList(h);
}

C++로 작성할 학생은 다음과 같이 class를 만들면 됩니다.

(예시)

class LinkedList
{
public:
    LinkedList();
    void addLastNode(char* x);
    void reverse();
    void deleteLastNode();
    void printList();
private:
    int length;
    listNode* head;
    listNode* tail;
};
이 경우 main 함수는 다음과 같습니다.
void main(int argc, char** argv)
{
    LinkedList list;
    list.addLastNode("kim");
    list.addLastNode("park");
    list.addLastNode("lee");
    list.addLastNode("hong");
    list.printList();
    list.reverse();
    list.printList();
    list.deleteLastNode();
    list.printList();
    list.deleteLastNode();
    list.printList();
}

연산자 우선순위를 고려한 전자계산기 작성

• 제출 기간 : 5월 15일 까지
• 연산자 우선순위를 고려한 계산기 작성
• 입력 형태 : 23 * 45 + 3 * ( 2 + 35) - 화면에서 텍스트로 입력받는다.
• 작성요령 : 입력된 수식을 스택을 이용하여 후위식으로 변환 후, 후위식을 스택을 이용하여 계산한다.
• 제출할 내용 : 보고서, 결과는 조교에게서 검사

Max Heap 작성

• 제출 기간 : 5월 31일 까지
• 입력 : 10 4 3 15 52 54 43 11 5 9 8

  처음의 10은 데이터의 개수를 뜻한다.

• 출력 : 54 52 43 15 11 9 8 5 4 3
• 제출물 : 보고서, 코드
• 코드는 조교에게 수행검사를 맡을 것