데이터 구조 와 알고리즘 (C 언어) 의 선형 표 (순서 저장 구조)

1. 선형 표 의 정의
0 개 이상 의 데이터 요소 로 구 성 된 유한 한 서열.
수학 언어 로 다음 과 같이 정의 합 니 다.
만약 에 선형 표 가 (a1,..., ai - 1, ai, ai + 1,... an) 이 라면 표 에서 ai - 1 은 ai 보다 앞 섰 고 ai 는 ai + 1 보다 앞 섰 으 며 ai - 1 은 ai 의 직접 전구 요소 이 고 ai + 1 은 ai 의 직접 후계 요소 라 고 한다.
선형 표 의 개수 n > = 0, n = 0 시 는 빈 표 이다.
2.      ADT 선형 테이블 (목록)
 data
선형 표 의 데이터 대상 집합 은 {a1, a2,... an} 각 요소 의 유형 은 DataType 입 니 다.그 중에서 첫 번 째 요소 a1 을 제외 하고 모든 요 소 는 하나의 직접적인 전구 요소 만 있 고 마지막 요소 an 을 제외 하고 모든 요 소 는 하나의 직접적인 후계 요소 만 있 으 며 데이터 요소 간 의 관 계 는 일대일 관계 이다.
operation
InitList (* L): 작업 을 초기 화하 고 빈 선형 표 L 만 들 기
ListEmpty (L): 선형 표 가 빈 표 인지 판단 합 니 다. 선형 표 가 비어 있 으 면 true 로 돌아 갑 니 다. 그렇지 않 으 면 false 로 돌아 갑 니 다.
CreateList (* L): 선형 테이블 만 들 기
PutList (L): 선형 표 인쇄
ClearList (* L): 선형 테이블 비우 기
GetElem (L, i, * e): 선형 표 L 의 i 번 째 위치 요 소 를 e 에 되 돌려 줍 니 다.
LocateElem (L, e): 선형 표 L 에서 주어진 값 e 와 같은 요 소 를 찾 습 니 다. 찾 는 데 성공 하면 이 요 소 를 되 돌려 표 의 번호 에 성공 을 표시 합 니 다. 그렇지 않 으 면 0 으로 돌아 가 는 것 은 실 패 를 표시 합 니 다.
ListInsert (* L, i, e): 선형 표 L 의 i 번 째 위치 에 새 요소 e 를 삽입 합 니 다.
ListDelete (* L, i, * e): 선형 표 의 i 번 째 위치 요 소 를 삭제 하고 e 로 값 을 되 돌려 줍 니 다.
ListLength (L): 선형 표 L 의 요소 개 수 를 되 돌려 줍 니 다.
endADT
3. 인 코딩 실현

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
#define OK 1
#define ERROR -1
enum selection{initList=1,listEmpty,createList,putList,clearList,getElem,locateElem,listInsert,listDelete,listLength};
typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;

//     ，         L
void InitList(SqList *L)
{
    L->length=0;
    printf("initList success!
");
}

//          ，      ，  true，    false
void ListEmpty(SqList L)
{
    if(L.length==0)
        printf("the list is empty!
");
    else
        printf("the list is not empty!
");
}

//     
void CreateList(SqList *L)
{
    int tmp,i=0;

    printf("create a list:
");
    printf("please input a number ('#' end):
");
    while(1==(scanf("%d",&tmp)))
    {
        L->data[i++]=tmp;
        L->length++;
    }
    fflush(stdin);//       
    printf("create successfully!
");
}

//     
void PutList(SqList L)
{
    int i;

    printf("the list is:
");
    for(i=0;i<L.length;i++)
    {
        printf("%d->",L.data[i]);
    }
    printf("the end!");
    printf("
");
}

//    
void ClearList(SqList *L)
{
    InitList(L);
}

//    L   i        e
int GetElem(SqList *L,int i,ElemType *e)
{
    if(i<=0||L->length<i||L->length==0){

        return ERROR;
    }
    *e=L->data[i-1];
    return OK;
}

//    L       e     ，      ，               ，    0    
int LocateElem(SqList L,int e)
{
    int i;
    if(L.length>0)
    {
        for(i=0;i<L.length;i++)
        {
            if(L.data[i]==e)
            {
                return i;
            }
        }
    }
    return -1;
}

//    L  i        e
int ListInsert(SqList *L,int i,ElemType e)
{
    int k;

    if(L->length==0||L->length+1<i||i<=0)
    {
        return ERROR;
    }
    if(i<=L->length)
    {
        for(k=L->length;k>=i;k--)
        {
            L->data[k]=L->data[k-1];
        }
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}


//     L     
void ListLength(SqList L)
{
    printf("       %d
",L.length);
}

//       i     ，  e    
int ListDelete(SqList *L,int i,ElemType *e)
{
    int k;

    if(L->length==0||i>L->length)
        return ERROR;
    *e=L->data[i-1];

    if(i<=L->length)
    {
        for(k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

void showItems()
{
    puts("please input <1-10> to select operation:");
    puts("-----------------------------------------------");
    puts("  1>initList      2>listEmpty     3>createList");
    puts("  4>putList       5>clearList     6>getElem");
    puts("  7>locateElem    8>listInsert    9>listDelete");
    puts("  10>listLength");
    puts("-----------------------------------------------");
}
int main()
{
    SqList L;


    while(OK)
    {
        int t,i,e;
        enum selection index;

        showItems();
        scanf("%d",&t);
        while((getchar())!='
');
        index=(enum selection)t;

        switch(index)
        {
        case initList:
            InitList(&L);
            break;
        case listEmpty:
            ListEmpty(L);
            break;
        case createList:
            CreateList(&L);
            break;
        case putList:
            PutList(L);
            break;
        case clearList:
            ClearList(&L);
            break;
        case getElem:
            printf("     :
");
            scanf("%d",&i);
            if(GetElem(&L,i,&e)==1)
            {
                printf(" %d      %d
",i,e);
            }
            else
            {
                printf("input error!
");
            }
            break;
        case locateElem:
            printf("     :
");
            scanf("%d",&e);
            if(LocateElem(L,e)>0){
                printf("success!
");
                printf("  %d       %d 
",e,LocateElem(L,e)+1);
            }
            else
            {
                printf("there is no number!
");
            }
            break;
        case listInsert:
            printf("            :
");
            scanf("%d",&i);
            scanf("%d",&e);
            if(ListInsert(&L,i,e)==1)
            {
                printf("insert success!
");
            }
            else{
                printf("input error!
");
            }
            break;
        case listDelete:
            printf("            :
");
            scanf("%d",&i);
            scanf("%d",&e);
            if(ListDelete(&L,i,&e)==1)
            {
                printf("delete success!
");
            }
            else
            {
                printf("input error!
");
            }
            break;
        case listLength:
            ListLength(L);
            break;
        default:
            fputs("error input!
",stderr);
        }
    }


    return 0;
}

4. 분석
데 이 터 를 저장 하고 읽 을 때 어느 위치 든 시간 복잡 도 는 O (1) 이 고 삽입 하거나 삭제 할 때 시간 복잡 도 는 O (n) 입 니 다.
이것 은 요소 의 개수 가 비교적 안정 적 이 고 요 소 를 자주 삽입 하거나 삭제 하지 않 으 며 더 많은 조작 은 데 이 터 를 액세스 하 는 응용 이다.
5. 선형 표 순서 저장 구조의 장단 점
장점:
표 의 요소 간 의 논리 적 관 계 를 위해 추가 저장 공간 을 늘 릴 필요 가 없다.
테이블 의 임의의 위 치 를 빠르게 접근 할 수 있 는 요소
단점:
삽입 및 삭제 작업 은 대량의 요 소 를 이동 해 야 합 니 다.
선형 표 의 길이 가 비교적 클 때 저장 공간의 용량 을 확정 하기 어렵다.
저장 공간의 '조각' 을 만 들 기 쉽다.