c++ 자료구조 링크드리스트 다항식 덧셈 곱셈 symbol table
- 최초 등록일
- 2012.08.28
- 최종 저작일
- 2011.10
- 12페이지/ 한컴오피스
- 가격 1,500원
소개글
연습문제 7번
7. 범용리스트를 표현하는 한가지 방법은 두 개의 필드와 모든 원자와 리스트 이름, 이 리스트들에 대한 포인터를 포함하는 테이블을 사용하는 것이다. 각 노드의 두 필드를 alink와 blink라 하자. blink는 같은 레벨의 다음 노드를 가리키거나, 아니면 0이다. alink는 하위 레벨의 노드를 가리키거나, 원자 또는 리스트 이름의 경우에는 심벌 테이블의 적절한 진입점을 가리킨다. 예를 들면 리스트 B(A,(D,E),(),B)는 책 215p의 그림 4.38과 같은 표현을 갖게 된다. 여기서 d*는 리스트 D의 첫 번째 노드를 가리키는 포인터라는 의미이다.
심벌테이블은 각 엔트리의 타입 비트를 유지한다. 이 비트는 만약 엔트리가 리스트 이름이면 1이고, 원자이면 0이다. NIL원자는 테이블에 있을수 있다. 그렇지 않으면 NIL원자를 표현하기 위해서 alink를 0으로 설정할 수 있다. 괄호 표기법으로 된 리스트를 입력하고 위와 같은 연결 표현을 만드는 c++함수 operator>>을 작성하라. 헤더 노드를 사용되지 않는다는 것에 주목하라. 함수 operator>>는 다음과 같은 함수를 사용할수 있다.
(a)int Get(a)는 이름 a를 심벌테이블에서 탐색한다. 만약 a를 테이블에서 찾지 못하면, -1이 반환되고, 그렇지 않으면 테이블에서의 a의 위치가 반환된다.
(b)put(n,t,a)는 테이블에 3원소 쌍(n,t,a)를 넣는다. 만일 이름 n이 이미 테이블에 존재하면 옛 엔트리의 타입과 주소 필드는 각각 t와 a로 변경된다.
(c)NextToken()은 입력 리스트에서 다음 토큰을 가져온다(토큰은 리스트 이름, 원자,‘(’,‘)’,‘.’이 될수 있다. 만약 더 이상의 토큰이 없으면 ‘#’이 반환된다)
사용할 모든 함수들의 코드를 작성하라. 입력 리스트는 문법적으로 정확하다고 가정해도 된다. 만일 서브리스트가 리스트 C(D,E(F,G))와 같이 이름이 붙어 있으면, 구조는 C(D,(F,G))와 같이 설정되고, E는 적절한 시작 주소를 가진 리스트로서 심벌 테이블에 입력되어야 한다.
목차
1. 문제 인식
2. 문제 접근 방법 및 분석
3. 소스코드 및 주석
4. 결과화면
5. 느낀점
본문내용
범용리스트를 표현하는 한가지 방법은 두 개의 필드와 모든 원자와 리스트 이름, 이 리스트들에 대한 포인터를 포함하는 테이블을 사용하는 것이다. 각 노드의 두 필드를 alink와 blink라 하자. blink는 같은 레벨의 다음 노드를 가리키거나, 아니면 0이다. alink는 하위 레벨의 노드를 가리키거나, 원자 또는 리스트 이름의 경우에는 심벌 테이블의 적절한 진입점을 가리킨다. 예를 들면 리스트 B(A,(D,E),(),B)는 책 215p의 그림 4.38과 같은 표현을 갖게 된다. 여기서 d*는 리스트 D의 첫 번째 노드를 가리키는 포인터라는 의미이다.
심벌테이블은 각 엔트리의 타입 비트를 유지한다. 이 비트는 만약 엔트리가 리스트 이름이면 1이고, 원자이면 0이다. NIL원자는 테이블에 있을수 있다. 그렇지 않으면 NIL원자를 표현하기 위해서 alink를 0으로 설정할 수 있다. 괄호 표기법으로 된 리스트를 입력하고 위와 같은 연결 표현을 만드는 c++함수 operator>>을 작성하라. 헤더 노드를 사용되지 않는다는 것에 주목하라. 함수 operator>>는 다음과 같은 함수를 사용할수 있다.
<중략>
poly* SelectionSort(poly *x, int i)
{
/*선택정렬 함수는 리스트와 그 리스트에서 정렬을 시작할
인덱스 및 리스트의 크기를 파라미터로 받아온다.*/
int max, j;
term temp;
max = i; // 정렬을 시작할 리스트 인덱스를 지정함.
if(x->termArray[i].coef != `#`)
{
for(j = i+1; x->termArray[j].coef != `#`; j++) // 정렬할 인덱스 이후의 데이터 중 작은 값을 찾음.
{
if(x->termArray[j].exp > x->termArray[max].exp) // 현재 지정된 최소값보다 큰 데이터를 발견하면
max = j; // 그 인덱스를 다시 지정.
참고 자료
없음