중국 대학생 mooc - 01 - 복잡 도 3 2 점 찾기 (20 점)
1848 단어 데이터 구조
01 - 복잡 도 3 이분 찾기 (20 분)
이 문 제 는 이분 검색 알고리즘 을 실현 해 야 한다.
함수 인터페이스 정의:
Position BinarySearch( List L, ElementType X );
그 중에서
List 구조 정 의 는 다음 과 같다.typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* */
};
L 은 사용자 가 들 어 오 는 선형 표 입 니 다. 그 중에서 ElementType 요 소 는 >, =, Binary Search 를 통 해 X 가 Data 에 있 는 위 치 를 찾 아야 합 니 다. 즉, 배열 아래 에 표 시 됩 니 다 (주의: 요 소 는 아래 표 1 부터 저장 합 니 다).찾 으 면 다음 표 시 를 되 돌려 줍 니 다. 그렇지 않 으 면 특수 한 실패 표시 NotFound 를 되 돌려 줍 니 다.심판 테스트 프로그램 샘플:
#include
#include
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* */
};
List ReadInput(); /* ， 。 1 */
Position BinarySearch( List L, ElementType X );
int main()
{
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d
", P);
return 0;
}
/* */
입력 샘플 1:
5
12 31 55 89 101
31
출력 예시 1:
2
입력 샘플 2:
3
26 78 233
31
출력 예시 2:
0코드 는 다음 과 같 습 니 다:
Position BinarySearch( List L, ElementType X )/* */
{
Position i,n = L->Last;
Position start = 1, end = n;
while(start <= end)
{
i = (start + end) /2;
if(L->Data[i] > X){
end = i -1;
}
else if(L->Data[i] < X){
start = i + 1;
}
else{
return i;
}
}
return NotFound;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
