[데이터 구조] 제1장 - 서론 (독서 노트)

제1장 서론
□ 1.1 데이터 구조 가 무엇 인지 좋 은 프로그램 을 만 들 기 위해 서 는 처리 대상 의 특징 과 처리 대상 간 에 존재 하 는 관 계 를 분석 해 야 한다. 이것 이 바로 데이터 구조 이다.데이터 구 조 는 비수 치 계산 을 연구 하 는 프로그램 설계 문제 에서 컴퓨터 의 조작 대상 과 그들 간 의 관계 와 조작 등 을 연구 하 는 학과 이다.데이터 구 조 는 수학, 컴퓨터 하드웨어, 컴퓨터 소프트웨어 세 가지 사이 에 있 는 핵심 과정 이다.이것 은 일반 프로 그래 밍 의 기초 일 뿐만 아니 라 컴 파일 러, 운영 체제, 데이터 베이스 시스템 과 다른 시스템 프로그램 과 대형 응용 프로그램 을 디자인 하고 실현 하 는 중요 한 기초 이기 도 한다.
□ 1.2 기본 개념 과 용어 1. 데이터 (data): 객관 적 인 사물 에 대한 기호 로 컴퓨터 과학 에서 컴퓨터 에 입력 되 고 컴퓨터 프로그램 에 처 리 될 수 있 는 모든 기 호 를 총칭 한다.데이터 의 의 미 는 매우 광범 위 하 다. 예 를 들 어 이미지 소리 등 은 모두 인 코딩 을 통 해 데이터 의 범주 로 돌아 갈 수 있다.2. 데이터 요소 (data element): 데이터 의 기본 단 위 는 컴퓨터 프로그램 에서 하나의 전체 로 고려 하고 처리 합 니 다.예 를 들 어 나무의 바둑판 구조 와 같이 그림 은 모두 데이터 요소 이다.3. 데이터 대상 (data object): 성질 이 같은 데이터 요소 의 집합 입 니 다.데이터 의 하위 집합 입 니 다.4. 데이터 구조 (data structure): 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합 이다.5. 데이터 형식 (data type): 값 의 집합 과 이 값 에 정 의 된 작업 의 총칭 입 니 다.6. 추상 적 인 데이터 형식 (abstract data type): 수학 모델 과 이 모델 에 정 의 된 작업 을 말한다.7. 다 형 데이터 형식 (polymorphic data type): 그 값 의 성분 이 불확실 한 데이터 형식 을 말 합 니 다.예 를 들 어 데이터 형식 Triplet, 그 요소 e1, e2 와 e3 는 정수 나 문자 나 문자열 일 수 있 고 심지어 여러 가지 성분 으로 복잡 하 게 구 성 될 수 있다.그러나 그 요소 가 어떤 특성 을 가지 든 요소 간 의 관 계 는 같 고 기본 적 인 조작 도 같다.
네 가지 기본 적 인 데이터 구조: 1. 집합: 구조 중의 데이터 요소 간 에 같은 집합 에 속 하 는 관 계 를 제외 하고 다른 관 계 는 없다.2. 선형 구조: 구조 중의 데이터 요소 사이 에 일대일 관계 가 존재 한다.3. 트 리 구조: 구조 중의 데이터 요소 사이 에 여러 개의 관계 가 존재 한다.4. 도형 구조 와 그물 모양 구조: 구조 중의 데이터 요소 사이 에 여러 개의 관계 가 존재 한다.
□ 1.3 추상 데이터 형식의 표현 과 ADT 추상 데이터 형식 이름 { 데이터 대상: (데이터 대상 의 정의) 데이터 관계: (데이터 관계 의 정의) 기본 작업: (기본 작업 의 정의)} ADT 추상 데이터 형식 이름
□ 1.4 알고리즘 과 알고리즘 분석 알고리즘 (algorithm) 은 특정한 문제 해결 절차 에 대한 설명 으로 명령 의 유한 한 서열 로 그 중에서 모든 명령 은 하나 이상 의 조작 을 나타 낸다.알고리즘 의 중요 한 특징: 가난 성 (모든 단 계 는 가난 한 시간 안에 완성 할 수 있 음), 확정 성 (이의 없 음), 타당 성, 입력 (하나의 알고리즘 은 0 개 이상 의 입력 이 있 음), 출력 (하나의 알고리즘 은 하나 이상 의 출력 이 있 음) 이 있 습 니 다.알고리즘 디자인 의 요구: 정확성 (correctness), 가 독성 (readability), 건장 성 (robustness), 효율 과 저 저장량 수요.
□ 알고리즘 효율 의 도량형 은 한 프로그램의 실행 시간 에 보통 두 가지 방법 이 있다. 사후 통계 방법, 사전 분석 추산 방법 이다.고급 언어 로 작 성 된 프로그램 이 컴퓨터 에서 실 행 될 때 소모 되 는 시간 은 다음 과 같은 요소 에 달 려 있다.3. 프로그램 을 작성 하 는 언어 는 같은 알고리즘 에 대해 언어 를 실현 하 는 등급 이 높 을 수록 집행 효율 이 낮다.4. 컴 파일 러 가 만 든 기계 코드 의 품질.5. 기계 가 명령 을 수행 하 는 속도.특정한 알고리즘 운행 작업량 의 크기 는 문제 의 규모 나 문제 규모 의 함수 에 만 의존한다.시간 복잡 도: 점 근 시간 복잡 도 (asymptotic time complextiy) 라 고도 부른다. 그 는 문제 규모 n 의 증가 에 따라 알고리즘 집행 시간의 성 장 률 은 F (n) 의 성 장 률 과 같다 고 말 했다.시간 복잡 도 는 일반적인 상황 에서 최 악의 상황 에서 의 시간 복잡 도 를 가리킨다.문장의 빈도: 이 문장의 중복 집행 횟수 를 가리킨다.보통 상수 단계, 선형 단계, 제곱 단계 가 있다.빈도 에 대하 여 우 리 는 가능 한 한 여러 단계 의 알고리즘 을 사용 해 야 하 며, 지수 단계 의 알고리즘 을 사용 하 는 것 을 원 하지 않 는 다.공간 복잡 도 (space complexity): 알고리즘 에 필요 한 저장 공간의 양 입 니 다.
코드 1: 데이터 형식 Triplet 의 정의

typedef int Status; /* Status      ,           ， OK  */
typedef int ElemType; /*         ElemType         */

/*               */
typedef ElemType *Triplet; /*  InitTriplet           */
/* Triplet   ElemType     ，  ElemType      */

/*       Triplet ElemType( c1-1.h  )     (8 ) */
Status InitTriplet(Triplet *T,ElemType v1,ElemType v2,ElemType v3)
{ /*     :     T,   T         v1,v2 v3 */
   *T=(Triplet)malloc(3 * sizeof(ElemType));
   if(!*T)
     exit(OVERFLOW);

   (*T)[0]=v1,(*T)[1]=v2,(*T)[2]=v3;
   return OK;
}

Status DestroyTriplet(Triplet *T)
{ /*     ：   T    */
   free(*T);
   *T = NULL;
   return OK;
}

Status Get(Triplet T, int i, ElemType *e)
{ /*     ：   T   ，1≤i≤3。    ： e  T  i    */
   if(i <1 || i > 3)
     return ERROR;
   *e = T[i-1];
   return OK;
}

Status Put(Triplet T, int i, ElemType e)
{ /*     ：   T   ，1≤i≤3。    ：  T  i    e */
   if(i<1||i>3)
     return ERROR;
   T[i-1] = e;
   return OK;
}

Status IsAscending(Triplet T)
{ /*     ：   T   。    ：  T          ，  1，    0 */
   return(T[0] <= T[1] && T[1] <= T[2]);
}

Status IsDescending(Triplet T)
{ /*     ：   T   。    ：  T          ，  1，    0 */
   return(T[0] >= T[1] && T[1] >= T[2]);
}

Status Max(Triplet T,ElemType *e)/*      */
{ /*     ：   T   。    ： e  T           */
   *e = (T[0]>=T[1]) ? ((T[0]>=T[2]) ? T[0]:T[2]) 
	   :((T[1]>=T[2]) ? T[1]:T[2]);
   return OK;
}

Status Min(Triplet T,ElemType *e)
{ /*     ：   T   。    ： e  T           */
   *e = (T[0]<=T[1]) ? (( T[0]<=T[2] ) ? T[0]:T[2])
		:(( T[1]<=T[2] )?T[1]:T[2]);
   return OK;
}

int _tmain(int argc, _TCHAR* argv[])
{
   Triplet T;
   ElemType m;
   Status i;

   i=InitTriplet(&T,5,7,9);
   printf("        ，i=%d(1:  ) T     ：%d %d %d
",i,T[0],T[1],T[2]); /*  ElemType      ，     printf()    。 */
   i=Get(T,2,&m);
   if(i==OK)
     printf("T  2   ：%d
",m);
   i=Put(T,2,6);
   if(i==OK)
     printf(" T  2    6 ，T     ：%d %d %d
",T[0],T[1],T[2]);
   i=IsAscending(T); /*        ElemType     , ElemType      ,       */
   printf("          ，i=%d(0:  1: )
",i);
   i=IsDescending(T);
   printf("          ，i=%d(0:  1: )
",i);
   if((i=Max(T,&m))==OK) /*        */
     printf("T      ：%d
",m);
   if((i=Min(T,&m))==OK)
     printf("T      ：%d
",m);
   DestroyTriplet(&T); /*             */
   printf("  T ，T=%u(NULL)
",T);
	return 0;
}

코드 2: 거품 알고리즘 의 시간 복잡 도

/*
             ，          n(n-1)/2
                  O（n２）
*/
void bubble_sort(int a[], int n)
{
	int i = 0;
	int j = 0;
	int change = FALSE;/*change          ，        */
	int temp;

	for (i = n - 1, change = TRUE; i >= 1 && change; --i ){
		change = FALSE;
		/*        */
		for (j = 0; j < i; ++j){
			if (a[j] > a[j+1]){
				/*              */
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				change = TRUE;
			}
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int intArray[] = {1,4,3,2,5};
	/* intArray                     */
	bubble_sort(intArray, sizeof(intArray)/sizeof(intArray[0]));
	return 0;
}