Lecture/자료구조/2005

개요

• 교수 : 박상원
• 강의시간 : 수 (3), 금 (1,2)
• 게시판

교재

• 이석호, "자료구조와 C", 정익사

평가

• 중간고사 : 30%
• 기말고사 : 30%
• 과제 : 30%
• 출석 : 10%

중간고사

• 일시 : 2005년 4월 22일
• 범위 : 1장 - 5장

기말고사

• 일시 : 2005년 6월 17일
• 범위 : 6장 - 11장

교안

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

과제

베낀 것은 원본, 복사본 구분없이 1/n 점수 부여

연습문제 풀이 (3월 18일까지)

• 1-10, 1-13
• 제출내용 : Source Code, 실행 결과, 설명

다항식 연산 (3월 29일까지)

• 2.5절에 있는 zeroP, isPzero, coef, maxExp, addTerm, delTerm를 구현하고 이를 이용하여 polyAdd와 polyMult, sMult 함수를 구현하시오.
• 각 함수의 원형

int* zeroP();
int isZeroP(int* p);
int coef(int* p, int e);
int maxExp(int* p);
void addTerm(int* p, int a, int e);
void delTerm(int* p, int e);
int* sMult(int* p, int a, int e);
int* polyAdd(int* p1, int* p2);
int* polyMult(int* p1, int* p2);

• 실행방법
• 2x^3 + 4x + 1 일 경우
• 입력 데이타 : 2 3 4 1 1 0
• 메뉴로 sMult, polyAdd, polyMult를 선택할 수 있도록 하고 실행결과를 보일 것. (조교에게 검사)

연결리스트 만들기 (4월 15일까지)

• 자료구조

typedef struct listNode {
  int data;
  struct listNode* link;
} listNode;
 
typedef struct {
  int length;
  listNode* head;
  listNode* tail;
} h_linkedList;

• 작성해야할 함수

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

• 저장하는 데이타는 정수
• 제출: 소스 코드 및 설명 제출 후 조교에게 실행 결과 검사

과제 2를 연결리스트를 이용하여 재작성하기 (4월 30일까지)

• 과제 3을 변형하여 이용
• 제출: 소스 코드 및 설명 제출 후 조교에게 실행 결과 검사

덱을 이용한 스택과 큐 구현 (5월 15일까지)

• 교과에서 나오는 덱의 추상 데이타 타입의 함수 구현
• 이것을 이용하여 스택과 큐 동작 수행
• 제출: 소스 코드 및 설명 제출 후 조교에게 실행 결과 검사

히프를 이용한 정렬 알고리즘 구현 (6월 7일까지)

• 다음은 입력데이타의 형식이다.

  7 2 3 8 7 5 9 10

• 첫번째 숫자는 데이타의 개수이고, 그 다음은 입력될 데이타이다. scanf를 이용하여 데이타를 읽어들이고 이 데이타를 히프에 삽입한다.
• 결과물은 정렬된 숫자이다. 즉, 히프에서 데이타를 하나씩 삭제하면 큰 값부터 차례대로 나올 것이다. 예를 들면 결과는 다음과 같이 나와야 한다.

  10 9 8 7 5 3 2

• 제출: 소스 코드 및 설명 제출 후 조교에게 실행 결과 검사