절강대학 교 데이터 구조 제1 강: 1.1 데이터 구조 가 무엇 입 니까?

기본 개념
1.1: 데이터 구 조 는 무엇 입 니까?1.1.1: 도서 배치 문제: 토론: 중간 규모, 대규모 도서 배치 에 대해 더 좋 은 제안 이 있 습 니까?1. 도 서 를 분류 한다. 책 을 과학기술 류, 예술 류, 잡지 등 종류 로 나눈다.2. 각 유형 은 하나의 문자 나 한자 색인 에 대응 합 니 다.3. 컴퓨터 를 이용 하여 색인 디 렉 터 리 를 만 들 고 모든 책 을 유형 별로 출판 시간, 유형 별로 번 호 를 매 긴 다.4. 동적 확대: 한 유형의 책 이 컴퓨터 용량 한도 에 이 르 면 확대 할 수 있 고 책의 수량 을 늘 리 는 목적 을 달성 해 야 한다.
1.1.2: 공간 사용 에 관 한 예: PrintN 함수 실현: 하나의 프로그램 을 써 서 하나의 함수 PrintN 을 실현 하여 들 어 오 는 정수 가 N 인 매개 변 수 를 순서대로 인쇄 할 수 있 습 니 다.

#include<stdio.h> 
int N;
void printN1(int N){     //for     
	int i;
	for(i = 1;i <= N; i++){
		printf("%d、", i );
	}
	printf("
");
}

void printN2(int N){    //     
	if(N){
		printN2(N - 1);
		printf("%d、", N );
	}
} 
int main(void){
	scanf("%d" , &N);
	printN1( N );
	printN2( N );
}

1.1.3: 알고리즘 효율 에 관 한 예: 여러 가지 값 쓰기 프로그램 계산 주어진 다항식 f (X) = a0 + a1x + a2x ^ 2 +... + anx ^ n 이 지정 한 x 에 있 는 값

#include 
#include 
#include 
clock_t start, stop;
double duration;
#define MAXN 10   //       ，      +1 
#define MAXK 1e7  //            
double f1( int n, double a[], double x ){
	int i;
	double p = a[0];
	for(i = 1; i <= n; i++ )
		p += (a[i] * pow(x,i));
	return p;
} 

double f2( int n , double a[] , double x ){
	int i;
	double p = a[n];
	for( i=n ; i>0 ; i-- )
		p = a[i-1] + x* p;
	return p;
} 
int main(void){
	int i;
	double a[MAXN];  //        
	for( i = 0 ; i < MAXN ; i++ )
		a[i] = ( double ) i;

	start = clock();
	for( i=0 ; i<MAXK ; i++ )	
		f1(MAXN - 1, a , 1.1 );
	stop = clock();
	duration = ( (double) (stop - start) ) / CLK_TCK / MAXK;
	printf("ticks1 = %f 
",(double)(stop - start));
	printf("duration1 = %6.2e
",duration);
	
	start = clock();
	for( i=0 ; i<MAXK ; i++ )
		f2(MAXN - 1, a , 1.1 );
	stop = clock();
	duration = ( (double) (stop - start) ) / CLK_TCK / MAXK;
	printf("ticks2 = %f 
",(double)(stop - start));
	printf("duration2 = %6.2e
",duration);
	
	return 0;
}

프로그램 계산 주어진 다항식 f (X) = 1 + x + x ^ 2 / 2 +... + x ^ i / i +... + x ^ 100 / 100 지정 x 에 있 는 값

#include 
#include 
#include 
clock_t start, stop;
double duration;
int n = 100;
#define MAXK 2000  //            
double f1( double x , double a[]){
	int i;
	double p = a[0] = 1.0;
	for(i = 1; i <= n; i++ ){
	
		p += pow( x , i ) * a[i] ;
	}
	return p;
} 

double f2( double x , double a[]){
	int i;
	double p = a[n];
	for( i=n-1 ; i>=0 ; i-- ){
		p = a[i]+ x * p ;
	}
	return p;
} 
int main(void){
	int i;
	double a[ n + 1 ];
	a[0] = 1.0;
	for(i=1 ; i<= n ; i++ )
		a[i] = 1 / (double)i;
	start = clock();
	for( i=0 ; i<MAXK ; i++ )	
		f1( 1.1 , a );
	stop = clock();
	printf("      ：
");
	printf("f（x） = %f
",f1( 1.1 , a ));
	duration = ( (double) (stop - start) ) / CLK_TCK / MAXK;
	printf("    2000     ：ticks1 = %f 
",(double)(stop - start));
	printf("    ：duration1 = %6.2e
",duration);
	
	start = clock();
	for( i=0 ; i<MAXK ; i++ )
		f2( 1.1 , a );
	stop = clock();
	printf("
       ：
");
	printf("f（x） = %f
",f2( 1.1 , a ));
	duration = ( (double) (stop - start) ) / CLK_TCK / MAXK;
	printf("    2000     ：ticks2 = %f 
",(double)(stop - start));
	printf("    ：duration2 = %6.2e
",duration);
	
	return 0;
}