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

본 고 는 나의 개인 블 로그 에 첫 발 을 내 디 뎠 다.https://staunchkai.com
선형 구 조 는 비교적 간단 하고 자주 사용 하 는 데이터 구조 로 그 특징 은 첫 번 째 요소 가 직접적인 전구 가 없고 마지막 요소 가 직접적인 후계 가 없 는 것 을 제외 하고 집합 중의 나머지 요 소 는 모두 유일한 직접적인 전구 와 직접적인 후계 가 있다 는 것 이다.선형 구조의 저장 방식 은 두 가지 가 있 는데 그것 이 바로 순서 저장 과 체인 저장 이다.
순차 기억 구조
주소 연속 저장 장치 로 표 의 각 요 소 를 한 번 에 저장 합 니 다. 표 는 논리 적 구조 에서 인접 한 요 소 는 물리 적 구조 에서 도 인접 합 니 다. 예 를 들 어:

{a1, a2, a3, ..., an}

구현 코드
정의.
구조 체 를 사용 하여 순서 표를 정의 하 다.

#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20

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

생 성 순서 표

/*     */
Status CreateList(SqList *L)
{
    int L_length;

    printf("      ：");
    scanf("%d", &L_length);
    printf("   %d    ：
", L_length);

    int i = 0;
    while(i < L_length)
    {
        scanf("%d", &L->data[i]);
        i++;
    }
    L->length = L_length - 1;
    return OK;
}

인쇄 순서 표

/*     */
Status Print(SqList L)
{
    if(L.length >= 0)
    {
        printf("
      ：");
        for(int i = 0; i <= L.length; i++)
        {
            printf("%d ", L.data[i]);
        }
        return OK;
    }
    else
    {
        printf("   ！！！");
        return ERROR;
    }
}

요소 삽입
삽입 연산 을 하려 면 두 가지 관건 적 인 문 제 를 분명히 해 야 한다.

삽입 이 성공 하지 못 한 경우 어떻게 해 야 합 니까?

삽입 에 성공 한 후에 표 에 무슨 변화 가 생 겼 습 니까?

/*      */
Status ListInsert(SqList *L, int i, ElemType e)
{
    /*         */
    if(L->length == MAXSIZE -1)    // L->length           ，  MAXSIZE    0   ，   -1
    {
        printf("                  ，    ...");
        return ERROR;
    }

    /*             */
    if(i < 1 || i > L->length + 2)  // i     1    ，   1    ，L->length   +1，           ，   +2
    {
        printf("        ...");
        return ERROR;
    }

    /*            ，       ，         */
    for(int k = L->length; k >= i - 1; k--)
    {
        L->data[k + 1] = L->data[k];
    }
    L->data[i - 1] = e;
    L->length++;    //        ，       +1
    return OK;
}

요소 삭제

/*      */
Status DeleteElem(SqList *L, int i, ElemType *e)
{
    if(L->length < 0)
    {
        printf("    ...");
        return ERROR;
    }

    if(i < 1 || i > L->length + 1)
    {
        printf("        !!!");
        return ERROR;
    }

    *e = L->data[i - 1];    //          

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

원소 찾기

/*      */
Status GetElem(SqList L, ElemType e)
{
    for(int k = 0; k <= L.length; k++)
    {
        if(e == L.data[k])
            return k + 1;
        else
        {
            printf("      ...");
            return ERROR;
        }
    }
    return OK;
}

테스트 코드

int main()
{
    SqList L;   //        
    CreateList(&L);     //    
    ElemType e;

    while(1)
    {
        printf("
1.        
");
        printf("2.     
");
        printf("3.     
");
        printf("4.     
");
        printf("5.   
");
        printf("
    ：");

        int select;
        scanf("%d", &select);

        if(select == 5)
            return 0;

        switch(select)
        {
            case 1:
                Print(L);
                break;
            case 2:
                printf("
        ：");
                int insPosition, insElem;
                scanf("%d",&insPosition);
                printf("
        ：");
                scanf("%d",&insElem);
                if(ListInsert(&L, insPosition, insElem) == OK)
                    printf("    ！");
                break;
            case 3:
                printf("
          ：");
                int deletePosition;
                scanf("%d", &deletePosition);
                if(DeleteElem(&L, deletePosition, &e) == OK)
                    printf("    ，       %d", e);
                break;
            case 4:
                printf("        ：");
                int FindElem, FindElemPosition;
                scanf("%d", &FindElem);
                FindElemPosition = GetElem(L, FindElem);
                if(FindElemPosition == OK)
                    printf("    ，   ：%d", FindElemPosition);
                break;
            default:
                printf("    ...");
                break;
        }
    }
    return 0;
}