선형 표 의 순서 저장 구조 (삽입 및 삭제)

1. 순서 저장 정의
선형 표 의 순서 저장 구 조 는 주소 연속 저장 장치 로 선형 표 의 데이터 요 소 를 순서대로 저장 하 는 것 을 말한다.
2. 주소 계산 방법
선형 표 의 i 번 째 요 소 는 배열 아래 에 i - 1 로 표 시 된 위치 에 저장 하 는 것 이다.만약 에 c 개의 저장 부 를 점용 한다 고 가정 하면 선형 표 의 i + 1 개의 데이터 요소 의 저장 위치 와 i 번 째 데이터 요소 의 저장 위 치 는 다음 과 같은 관계 식 을 만족 시 킵 니 다 (LOC 는 저장 위 치 를 얻 는 함 수 를 표시 합 니 다).

LOC(ai+1) = LOC(ai) + c

즉시

LOC(ai) = LOC(ai) + (i-1)*c

3. 원소 조작 획득
4. 567917. 사고: 선형 표 의 순서 저장 구조 에 있어 GetElem 작업 을 실현 하고 선형 표 L 중의 i 번 째 위치 요소 값 을 되 돌려 줍 니 다.프로그램의 경우 i 의 수치 가 배열 아래 표 시 된 범위 내 (경 계 를 넘 지 않 음) 에 있 으 면 배열 i - 1 아래 표 시 된 값 을 되 돌려 주면 됩 니 다
코드:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status      ，           ， OK */
/*    ：     L   ，*/
/*    ： e  L  i       */
Status GetElem(SqList L, int i , ELemType *e)
{
    if(L.length==0 || i <1 || i >L.length)
        return ERROR;
    *e = L.data[i-1]; /*     i-1      */
    return OK;
}

무 작위 저장 구조 이기 때문에 시간 복잡 도 는 O (1) 이다.
4. 삽입 동작
ListInsert (* L, i, e), 즉 선형 표 L 의 i 번 째 위치 에 새 요소 e 를 삽입 합 니 다.
삽입 알고리즘 의 사고방식: * 삽입 위치 가 합 리 적 이지 않 으 면 이상 을 던 집 니 다. *선형 표 의 길이 가 배열 의 길이 보다 크 면 이상 또는 동적 으로 용량 을 증가 합 니 다. *마지막 요소 부터 i 번 째 위치 로 옮 겨 다 니 며 각각 한 위 치 를 뒤로 이동 합 니 다. *위치 i 에 요 소 를 삽입 합 니 다. *시계
코드:

/*    ：     L   ，1≤i≤ListLength(L)*/
/*    ：  L  i             e，L    1*/
Status ListInsert(SqList *L,int i ,ElemType e)
{
int k;
if(L->length==MAXSIZE)  /*     */
    return ERROR;
if(i<1 || i>L->length+1) /*  i     */
    return ERROR;
if(i<=L->length)  /*         */
{
    for (k=L->length-1;k>=i-1;k--)  /*                 */
        L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /*      */
L->length++;  /*   1*/
return OK;
}

5. 삭제 작업
삭제 알고리즘 사고방식: * 삭제 위치 가 합 리 적 이지 않 으 면 이상 을 던 집 니 다. *요소 삭제 하기; *요소 의 위 치 를 삭제 할 때 부터 마지막 요소 의 위 치 를 옮 겨 다 니 며 각각 한 위 치 를 앞으로 이동 합 니 다. *시계 길이 감소 1.
코드:

/*    ：      L   ，1≤i≤ListLength(L)*/
/*    ：   L  i     ，  e    ，L    1*/
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if(L->length==0)  /*     */
    return ERROR;
if(i<1 || i >L->length)  /*       */
    return ERROR;
*e = L->data[i-1];
if(ilength) /*          */
    {
        for(k=i;klength;k++)  /*           */
            L->data[k-1]=L->data[k];
    }
    L->length--; /*   1*/
    return OK;
}

6. 삽입 과 삭제 의 시간 복잡 도
가장 좋 은 상황:
마지막 위치 에 삽입 하면 후자 가 마지막 위 치 를 삭제 하면 시간 복잡 도 는 O (1) 이다.
최 악의 경우:
첫 번 째 위치 에 삽입 하거나 첫 번 째 요 소 를 삭제 하면 모든 요 소 를 이동 해 야 하기 때문에 시간 복잡 도 는 O (n) 입 니 다.
평균 상황:
요소 가 i 번 째 위치 에 삽입 되 거나 i 번 째 요 소 를 삭제 하기 때문에 n - i 요 소 를 이동 해 야 합 니 다.확률 원리 에 따라 위치 마다 요 소 를 삽입 하거나 삭제 할 가능성 은 같다.최종 평균 이동 횟수 와 가장 중간 에 있 는 요소 의 이동 횟수 는 n - 1 / 2 이다.
7. 선형 표 순서 저장 구조의 장단 점
장점: * 표 의 요소 간 의 논리 적 관 계 를 표시 하기 위해 추가 저장 공간 을 추가 할 필요 가 없습니다 * 표 의 모든 위 치 를 빠르게 액세스 할 수 있 는 요소
단점: * 삽입 과 삭제 작업 은 대량의 요 소 를 이동 해 야 합 니 다. *선형 표 의 길이 변화 가 비교적 클 때 저장 공간 용량 을 확정 하기 어렵다. *저장 공간의 파편 을 만들다.
참고 자료: 정 걸 저 2011 년 6 월 제1 판