데이터 구조 (11) 선형 표 의 일원 다항식 표시 및 추가

3236 단어 데이터 구조선형 표일원 다항식 더하기일원 다항식 표시
서론
일원 다항식 소개
추상 데이터 유형 1 원 다항식 정의
4. 567917 을 더 하면 어떻게 실현 합 니까?
결어

머리말
기호 다항식 처 리 는 표 처리 의 전형 적 인 범례 이다.이 장 은 주로 본 전형 적 인 사례 에 대해 토론 하 는 것 이다.
일원 다항식 소개
수학 적 으로 일원 다항식 pn (x) 은 승멱 에 따라 쓸 수 있다
pn(x)=p0+p1x+p2x2+...+pnxn
그것 은 n + 1 개의 계수 에서 유일 하 게 확정 된다.따라서 컴퓨터 에 서 는 선형 표 P 로 표시 할 수 있다.
P=(p0,p1,p2,...,pn)
각 항목 의 지수 i 는 그 계수 에 포함 되 어 있다.
pi 번호 에
가정 하 다
Qm (x) 는 일원 이다
m 차 다항식 은 마찬가지 로 선형 표 Q 로 표시 할 수 있다.
Q=(q0,q1,q2,...,qm)
일반성 을 잃 지 않 기 위해 서 우 리 는 가정 한다.
m < n, 두 다항식 을 더 한 결과
Rnx = Pn (x) + Qmx 는 선형 표 R 로 표시 할 수 있 습 니 다.
R=(p0+q0,p1+q1,p2+q2,...,pm+qm,pm+1,...,pn)
분명히 우 리 는 P, Q, R 에 대해 순서 저장 기 구 를 사용 하여 여러 가지 알고리즘 을 간결 하 게 정의 할 수 있다.이로써 일원 다항식 의 표시 와 더하기 문 제 는 이미 해 결 된 것 같다.그러나 일반적인 응용 에서 다항식 의 횟수 가 높 고 변화 가 많아 순서 저장 구조의 최대 길 이 를 확정 하기 어렵다.특히 처리 식 의 횟수 가 높 고 변화 가 많아 순서 저장 구조의 최대 길 이 를 확정 하기 어렵다.특히
S(x)=1+3x10000+2x20000
의 다항식 을 사용 할 때 길이 가 20001 인 선형 표 로 표시 해 야 한다. 표 에는 3 개의 비 0 요소 만 있 는데 이런 메모리 공간 에 대한 낭 비 는 피해 야 한다. 그러나 비 0 계수 만 저장 하면 해당 하 는 지 수 를 동시에 저장 해 야 한다.
일반적인 상황 에서 1 원 n 차 다항식 은 다음 과 같이 쓸 수 있다.
pn(x)=p1xe1+p2xe2+p3xe3+...+pmxem
pi 는 지수 가 ei 인 항목 의 비 0 계수 이 고 만족 합 니 다.
0≤e1만약 에 하나의 길이 가 m 이 고 모든 요소 에 두 개의 데이터 항목 (계수 항목 과 지수 항목) 의 선형 표 가 있다 면
((p1,e1),(p2,e2),...,,(pm,em))
다항식 을 유일 하 게 확정 할 수 있다.
Pn(x) 。
최 악의 경우 n + 1 (= m) 개 계수 가 0 이 아니 라 각 계수 만 저장 하 는 방안 보다 배가 많은 데 이 터 를 저장 합 니 다.하지만 앞 에 언급 된
S (x) 류 의 다항식 (식 의 횟수 가 높 고 변화 가 크다) 은 공간 을 크게 절약 할 것 이다.
다항식 에 만 '값 구하 기' 등 다항식 계수 와 지수의 연산 을 바 꾸 지 않 고 유사 한 순서 표 의 순서 저장 구 조 를 사용한다.그렇지 않 으 면 링크 구조 로.
추상 데이터 형식 일원 다항식 정의
ADT Polynomial{
    ：D＝{ ai | ai∈TermSet, i=1,2,...,m,  m≥0 
TermSet                         }
    ：R1＝{ <ai-1, ai>|ai-1, ai∈D,  ai-1     <ai     ，i=2，……，n}
    ：
     CreatPolyn（&P，m）
    ：  m       ，       P。
     DestroyPolyn（&P）
    ：     P   。
    ：       P。
     PrintPolyn（P）
    ：     P   。
    ：         P。
     PolynLength（P）
    ：     P   。
    ：       P    。
    AddPolyn（&Pa，&Pb）
    ：     Pa Pb   。
    ：         ， ：Pa=Pa+Pb，        Pb。
    SubtractPolyn(&Pa,&Pb)
    ：     Pa Pb   。
    ：         ， ：Pa=Pa-Pb，        Pb。
    MultiplyPolyn(&Pa,&Pb)
    ：     Pa Pb   。
    ：         ， ：Pa=Pa×Pb，        Pb。
}ADT Polynomial

이 정 의 를 실현 하려 면 체인 식 저장 구 조 를 사용 해 야 합 니 다.
더 하면 어떻게 실현 합 니까?
1 원 다항식 더하기 원칙: 두 개의 1 원 다항식 중 모든 지수 가 같은 항목 에 대해 대응 계 수 를 더 하고 만약 에 그 합 이 0 이 아니라면 '과 다항식' 중의 하 나 를 구성 하고 두 개의 1 원 다항식 중 모든 지수 가 다른 항목 에 대해 각각 '과 다항식' 에 베껴 쓴다.
Polynomial 정의 에 따 르 면 '와 다항식' 링크 의 결점 은 따로 생 성 되 지 않 고 두 개의 다항식 링크 에서 추출 해 야 한다.
연산 규칙: 포인터 qa 와 qb 가 각각 다항식 A 와 다항식 B 에서 현재 비교 하고 있 는 어떤 결점 을 가리킨다 고 가정 하면 두 결점 중의 지수 값 을 비교 하고 자 합 니 다. 아래 의 세 가지 상황 이 존재 합 니 다.
결어
다음 글 은 1 원 다항식 을 어떻게 실현 하 는 지, 이 절 은 1 원 다항식 을 더 하 는 아 이 디 어 를 만들어 줄 것 이다.
js 데이터 구조 - 산 목록
JAVA(조건문, 반복문 cf. try/catch, ASCII-Code, 난수)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage