데이터 구조의 순서 표 삽입 삭제 작업 (정적 분배 실현) 및 시간 복잡 도 분석

1. 순서 표 삽입 동작
요 소 를 삽입 하 는 위 치 는 i 가 삽입 한 후에 이 삽 입 된 요 소 는 i 의 위치 입 니 다. 즉, 원래 순서 표 에 있 는 i 의 위치 에 속 하 는 요 소 를 찾 아야 합 니 다. 이 요소 의 앞 에 꽂 으 면 됩 니 다.

#include
#define MaxSize 5
typedef struct {
	int data[MaxSize]; //           
	int length; //        
} SqList;
void InitList(SqList &L) {
	for(int i = 0; i<MaxSize; i++)
		L.data[i] = 0;
	L.length = 0;
}
bool ListInsert(SqList &L,int i,int e) {
	if(i<1 || i>L.length+1) { //   i       
		printf("        ,     i  
");
		return false;
	}
	if(L.length >= MaxSize){
		printf("    ,    
");
		return false; 
	}

	for(int j=L.length; j>=i; j--) //(j   i     )
		L.data[j] = L.data[j-1];
	L.data[i-1] =e;  //    i    e (i   )
	L.length++;   //  +1
	return true;
}

int main() {
	SqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,3);
	ListInsert(L,3,4);
	ListInsert(L,4,5);
	ListInsert(L,5,6);

	bool a= ListInsert(L,2,2);
	printf("%d
",a);  //c    bool     0   1,       %d     
	printf("%d,%d",L.data[1],L.length); //     2            
	return 0;
}

2. 순서 표 삭제 작업

#include
#define MaxSize 5
typedef struct {
	int data[MaxSize];
	int length;

} SqList;

void InitList(SqList &L) {
	L.length = 5;
	for(int i=1; i<=L.length; i++){
		L.data[i-1] = i;
	//	printf("%d",L.data[i-1]);
	}
		

}
bool ListDelete(SqList &L,int i,int &e) {
	if(i<1 || i > L.length) {
		printf("        
");
		return false;
	}
	if(L.length == 0) {
		printf("      ,    ");
		return false;
	}
	e = L.data[i-1];
	for(int m=i; m<L.length; m++)
		L.data[m-1] =L.data[m];
	L.length --;
	return true;

}

int main() {
	SqList L;
	InitList(L);
	int e = -1;
	ListDelete(L,3,e);

	printf("%d",e);

}

3. 순서 표 삽입 작업 의 시간 복잡 도 분석
가장 좋 은 상황:
새 요 소 를 표 끝 에 삽입 하면 요소 i = n + 1 을 이동 하지 않 고 0 회 순환 합 니 다.즉, 가장 좋 은 시간 복잡 도 = O (1)
최 악의 경우
새 요소 가 표 머리 에 삽입 되면 표 의 n 개 요 소 는 모두 i = 1 을 이동 해 야 합 니 다.순환 n 회, 최 악의 시간 복잡 도 = O (n)
평균 상황
새 요소 삽입 은 (n + 1) 가지 선택 이 있 습 니 다. 즉, 모든 위 치 를 삽입 할 확률 은 p = 1 / (n + 1) i = 1, 순환 n 회 i = 2, 순환 n - 1 회... i = n + 1, 순환 0 회 입 니 다.
평균 순환 횟수: = np + (n - 1) p +... + 1 * p = n / 2 즉 평균 시간 복잡 도 = O (n)
4. 순서 표 삭제 작업 의 시간 복잡 도 분석
가장 좋 은 상황:
표 끝 요 소 를 삭제 하면 요소 i = n 을 이동 하지 않 고 0 회 순환 합 니 다.즉, 가장 좋 은 시간 복잡 도 = O (1)
최 악의 경우
헤더 요 소 를 삭제 하면 표 의 n - 1 개 요 소 는 i = 1 을 이동 해 야 합 니 다.순환 n - 1 회, 최 악의 시간 복잡 도 = O (n)
평균 상황
삭제 작업 은 n 가지 선택 이 있 습 니 다. 즉, 모든 위 치 를 삭제 할 확률 은 p = 1 / n i = 1, 순환 n - 1 회 i = 2, 순환 n - 2 회... i = n, 0 회 순환 합 니 다.
평균 순환 횟수: = (n - 1) p +... + 1 * p = (n - 1) / 2 즉 평균 시간 복잡 도 = O (n)