학습 데이터 구조 -> 순서 저장 구조 선형 표 연산 의 실현
16271 단어 데이터 구조
삽입 작업 선형 표 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
전편
좋은 웹페이지 즐겨찾기
