선형 표 의 순서 저장 (1) -- 배열 표시

1. 선형 표 의 개념:
    1. 선형 표 는 가장 간단 하고 자주 사용 하 는 데이터 구조 로 보통 하나의 선형 표 는 n (n > = 0) 개의 성질 이 같은 데이터 요소 로 구 성 된 유한 한 서열 로 길 이 는 요소 의 개수 n 이 고 n = 0 일 때 이 표를 빈 표 라 고 부른다.
    2. 비 어 있 는 선형 구조의 특징: 유일한 첫 번 째 데이터 요소 와 마지막 데이터 요 소 를 가진다.또한 첫 번 째 요 소 를 제외 하고 다른 데이터 요 소 는 모두 하나의 전구 와 하나의 후계 만 있다.
    3. 선형 표 의 주요 저장 구조: 순서 저장 구조 와 체인 저장 구조.(본 편 은 주로 순서 저장 구 조 를 요약 한다)

2. 선형 표 의 순서 표시 와 실현
   순차 저장 구조의 저장 소 는 1 차원 배열 로 표시 할 수 있 으 며 고정 길이 가 있다.
   동적 분배 의 저장 구조 로 공간 을 합 리 적 으로 이용 할 수 있다.

(1) 1 차원 배열 표시
  데이터 구조:

typedef int datatype;
#define LIST_MAXSIZE 100
typedef struct
{
    datatype data[LIST_MAXSIZE];
    int length;
}Sqlist;

기본 동작:

/*     */
void InitList(Sqlist *L)
{
    L->length() = 0;
}
/*   */
int ListLength(Sqlist *L)
{
    return L->length;
}
/*     i   */
datatype GetElem(Sqlist *L,int i)
{
    if(i<1 || i>L->length)
        Error("position error");
    return L->data[i-1];
}
/*    x         */
int Search(int x,Sqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
        if(x == L->data[i])
            break;
    if(i == L->length)
        return 0;
    else
        retrun i+1; 
}
/*       i           e*/
Status Insert_Sq(Sqlist *L,int i,datatype e)
{
    datatype * q, *p;
    if(i<1 || i>L->length)
        return ERROR;
    if(L->length > LIST_MAXSIZE-1)
        retrun ERROR;
    q = &(L->data[i-1])//     

    for(p=&(L->data[L->length-1]);p>=q;--p)
    {
        *(p+1) = *p;
    }
    *q = e;
    ++L->length;
    return OK;
}
/* i      */
Status Delete_Sq(Sqlist *L,int i)
{
    datatype * p,*q;
    if(i<1 || i>L->length)
        return ERROR;
    p = &(L->data[i-1])//        

    q = &(L->data[L->length-1])//       

    for(;p<q;p++)
    {
        *p = *(p+1);
    } 
    --L->length;
    return OK;
}

병합 작업:

/*     La Lb     ，  La Lb  Lc            */
Void MergeList(Sqlist *La,Sqlist *Lb,Sqlist *Lc)
{
    int La_len,Lb_len,i=j=1,k=0;
    datatype ai,bj;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=la_len)&&(i<=lb_len)) 
    {
        ai = GetElem(La,i);
        bj = GetElem(Lb,j);
        if(ai < bj)
        {
            k++;
            i++;
            ListInsert(Lc,ai);
        }
        else
        {
             k++;
             j++;
             ListInsert(Lb,bj);
        }
    }
    while(i<=La_len)
    {
         ai = GetElem(La,i);
         i++;
         k++;
         ListInsert(Lc,ai);
    }
    while(j<=Lb_len)
    {
         bj = GetElem(Lb,j);
         j++;
         k++;
         ListInsert(Lc,bj);
    }
    Lc->length = k;
}

상기 알고리즘 은 《 데이터 구조 (c 언어 판) 》 진 명 편저 청화대학 교 에서 출판 되 었 다. 33 페이지 에 세 가지 상황 이 나 뉘 었 는데 aibj. 사실은 ai = bj 이런 상황 은 따로 열거 할 필요 가 없다. 물론 이런 사고방식 이 더욱 뚜렷 하 다. 절 차 는 다음 과 같다.

/*     La Lb     ，  La Lb  Lc            */
Void MergeList(Sqlist *La,Sqlist *Lb,Sqlist *Lc)
{
    int La_len,Lb_len,i=j=1,k=0;
    datatype ai,bj;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=la_len)&&(i<=lb_len)) 
    {
        ai = GetElem(La,i);
        bj = GetElem(Lb,j);
        if(ai < bj)
        {
            k++;
            i++;
            ListInsert(Lc,ai);
        }
        else
        if（ai == bj）
        {
            k++;
            ListInsert(Lc,ai);
            i++;
            k++;
            ListInsert(Lc,bi);
            j++; 
        }
        else
        {
             k++;
             j++;
             ListInsert(Lb,bj);
        }
    }
    while(i<=La_len)
    {
         ai = GetElem(La,i);
         i++;
         k++;
         ListInsert(Lc,ai);
    }
    while(j<=Lb_len)
    {
         bj = GetElem(Lb,j);
         j++;
         k++;
         ListInsert(Lc,bj);
    }
    Lc->length = k;
}

기본 연산 을 이용 하여 선형 표 에서 중복 되 는 불필요 한 노드 를 제거 합 니 다.

void Purge(List *L)
{
    int i,k;
    datatype x,y;
    for(i=1;i<ListLength(L);i++)
    {
        x = GetElem(L,i);
        k = i+1;
        while(k<=ListLength(L))
        {
             y = GetElem(L,k);
             if(x==y)
                 Delete(L,k);
             else
                 k++;
        }
    }
}

이 알고리즘 의 관건 은 Delete () 알고리즘 에서 l - > length 를 자동 으로 1 로 줄 이 는 것 이다.
다음으로 전송:https://blog.51cto.com/lhqvip/542016

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

선형 표 의 순서 저장 (1) -- 배열 표시

좋은 웹페이지 즐겨찾기