학습 데이터 구조 -> 순서 저장 구조 선형 표 연산 의 실현

학습 데이터 구조 -> 순서 저장 구조 선형 표 연산 의 실현
삽입 작업    선형 표 L = (a1, a2, a3,..., a (i - 1), ai, a (i + 1),..., an) 가 있 음 을 알 고 있 습 니 다. 이 선형 표 의 i 요소 위치 에 데이터 b 를 삽입 하여 다음 과 같이 만 듭 니 다.        L = ( a1, a2, a3, ..., a(i-1), b, ai, a(i+1), ..., an )        1. 실현 절차        ①. 선형 표 의 i 번 째 부터 n 번 째 데이터 요 소 를 모두 뒤로 이동 합 니 다.        ②. 데이터 요소 b 를 데이터 요소 a (i - 1) 에 삽입 한 후;        ③. 선형 표 의 길 이 를 1 로 늘린다.            2. 알고리즘 설명        여기 서 C 언어 에 있 는 배열 을 사용 하여 선형 표를 표시 하고 선형 표 의 결점 은 배열 에 순서대로 저장 되 며 정상 적 인 반환 값 을 0 으로 삽입 하여 삽입 할 수 없 을 때 반환 값 은 - 1 이다.

        /*                 */
        int InsertList( List L, int i, elementtype x )
        {
            int k ;
            if( i < 1 || i > L.length + 1 )
                return -1 ;
            
            if( L.length >= MaxLen )
            {
                printf( "     !" ) ;
                return -1 ;
            }
            for( k = L.length; k >= i -1; k-- )
                L.elements[k+1] = L.elements[k] ;
            L.elements[i-1] = x ;
            L.length ++ ;
            return 0 ;
        }

            3. C 언어 실례 설명        선형 표 다섯 번 째 요소 앞 에 데이터 100 삽입:

#include<stdio.h>

#define MaxLen 100

typedef struct
{
    int length ;
    int data[MaxLen] ;
}List ;

int InsertList( List *L, int i, int x )
{
    int k ;
    if( i < 1 || i > L -> length+1 )
    {
        return -1 ;
    }
    if( L -> length >= MaxLen )
    {
        printf( "     !" ) ;
        return -1 ;
    }

    for( k = L -> length; k >= i-1; k-- )
        L -> data[k+1] = L -> data[k] ;        //    
    L -> data[i-1] = x ;        //  x
    L -> length ++ ;            //       1

    return 0 ;
}

int main()
{
    List L;
    int i;

    //      
    for( i = 0; i < 10; i++ )
        L.data[i] = i ;
    L.length = 10 ;

    //      
    InsertList( &L, 5, 100 ) ;
    for( i = 0; i < L.length; i++ )
        printf("%d ", L.data[i] );

    return 0 ;
}

    4. 시간 복잡 도 분석        선형 표 의 순서 저장 구조의 삽입 연산 에서 그 주요 한 시간 은 선형 표 에서 데이터 요소 노드 의 이동 이다. 데이터 요소 의 이동 에 필요 한 시간 은 데이터 요 소 를 삽입 하 는 위치 에 달 려 있다. 일반적인 상황 에서 우 리 는 선형 표 L 에서 모든 위치 가 데이터 요 소 를 삽입 하 는 확률 이 같다 고 생각한다. 즉, Pi = 1/(n + 1)                길이 가 n 인 선형 표 L 에 데이터 요 소 를 삽입 할 때 표 의 절반 정도 요 소 를 이동 해 야 하기 때문에 순서 촌 에 저 장 된 선형 표 L 에 삽입 작업 을 하 는 시간 복잡 도 는 O (n) 이다.               
2. 삭제 작업    선형 표 L = (a1, a2, a3,..., a (i - 1), ai, a (i + 1),..., an) 가 있 음 을 알 고 있 습 니 다. 이 선형 표 의 ai 결점 을 삭제 하여 다음 과 같이 만 듭 니 다.        L = ( a1, a2, a3, ..., a(i-1), a(i+1), ..., an )            1. 실현 절차        1 >. 선형 표 L 에서 i + 1 개의 요소 부터 n 개의 요소 까지 순서대로 한 위 치 를 앞으로 이동 합 니 다.        2 >. 선형 표 길 이 를 1 로 줄인다.            2. 알고리즘 설명        삭제 성공 시 0 을 되 돌려 줍 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.

        /*                 */
        int DeleteItem( List L, int n )
        {
            int i ;
            if( n < 1 || n >= L.length )
                return -1 ;
                
            for( i = n-1; i < L.length; i++ )
                L.elements[i] = L.elements[i+1] ;         //    
            L.length -- ;        //      1
            
            return 0 ;
        }

    3. C 언어 실례 설명        선형 표 의 다섯 번 째 요 소 를 삭제 합 니 다:

#include<stdio.h>

#define MaxLen 100

typedef struct
{
    int length ;
    int data[MaxLen] ;
}List ;

int DeleteItem( List *L, int n)
{
    int i ;
    if( n < 1 || n > L -> length )
        return -1 ;

    for( i = n-1; i < L -> length; i++ )
        L -> data[i] = L -> data[i+1] ;         //    
    L -> length -- ;        //      1

    return 0 ;
}

int main()
{
    List L;
    int i;

    //      
    for( i = 0; i < 10; i++ )
        L.data[i] = i ;
    L.length = 10 ;

    //      
    DeleteItem( &L, 5 ) ;
    for( i = 0; i < L.length; i++ )
        printf("%d ", L.data[i] );

    return 0 ;
}

    4. 시간 복잡 도 분석        선형 표 순서 저장 구조 에서 연산 을 삭제 하 는 데 걸 리 는 시간 은 주로 결점 의 이동 에 나타난다. 일반적인 상황 에서 우 리 는 선형 표 L 에서 모든 요 소 를 삭제 할 확률 이 같다 고 생각한다. Pi = 1/n 은 길이 가 n 인 선형 표 L 에 데이터 요 소 를 삽입 할 때 똑 같이 표 의 절반 정도 요 소 를 이동 해 야 한다.그래서 순서 저장 구조 삭제 연산 의 시간 복잡 도 는 O (n) 이다.        
 
3. 찾기 동작    선형 표 L = (a1, a2, a3,..., an) 이 있 음 을 알 고 있 습 니 다. 이 선형 표 에서 x 가 처음으로 나타 난 노드 위 치 를 찾 아야 합 니 다.        1. 실현 절차        1 >. 선형 표 의 첫 번 째 요소 부터 순서대로 값 x 와 비교 하고 값 이 동시에 결점 이 있 는 위 치 를 되 돌려 줍 니 다.            2. 알고리즘 설명        찾 으 면 값 이 있 는 위 치 를 되 돌려 줍 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.

        /*                 */
        int FindItem( List L, elementtype x )
        {
            int i ;
            for( i = 0; i < L.length; i++ )
                if( x == L.elements[i] )        //    
                    return i+1 ;                //       

            return -1 ;        //     -1
        }

            3. C 언어 실례 설명        선형 표 L 에서 5 번 째 로 나타 난 위 치 를 찾 습 니 다.

#include<stdio.h>

#define MaxLen 100

typedef struct
{
    int length ;
    int data[MaxLen] ;
}List ;

int FindItem( List *L, int x )
{
    int i ;
    for( i = 0; i < L -> length; i++ )
        if( x == L -> data[i] )
            return i+1 ;

    return -1 ;
}

int main()
{
    List L;
    int i;

    //      
    for( i = 0; i < 10; i++ )
        L.data[i] = i ;
    L.length = 10 ;

    //      
    printf( "%d ", FindItem( &L, 5 ) ) ;

    return 0 ;
}

    4. 시간 복잡 도 분석        일반적인 상황 에서 우 리 는 찾 은 값 x 가 선형 표 에 있 는 위치 에 있 는 확률 이 같다 고 생각한다. 즉, 무 작위 상황 에서 하나의 값 을 찾 으 려 면 선형 표 의 절반 정도 요 소 를 비교 해 야 하고 이 알고리즘 이 사용 하 는 시간 은 주로 데이터 의 비교 에 소모 되 기 때문에 그 시간 복잡 도 는 O (n) 이다.               
순서 저장 구조의 선형 표 에 대해 여기 서 열거 한 것 은 비교적 전형 적 이 고 대표 적 인 의 미 를 가 진 연산 실현 과정 이다. 다른 일부 표 의 길이, 빈 표 등 비교적 간단 한 연산 은 여기 서 일일이 실현 되 지 않 는 다.
 
--------------------
wid, 2012.12.25
 
전편