선형 표 의 순서 저장 --- 순서 표

1 주 순서 표 개념: 순서 로 저 장 된 선형 표를 순서 표 라 고 하 는데 순서 표 에서 논리 적 으로 인접 한 데이터 요 소 는 물리 적 저장 위치 에서 도 인접 한 것 이다.2 주 정의 순서 표 는 1 차원 배열 로 순서 표 의 데이터 저장 을 설명 한다.순서 표 에 삽입 삭제 등 이 있 기 때문에 순서 표 의 길이 가 달라 집 니 다.따라서 배열 의 길이 가 충분 하고 정형 변수 length 를 넣 어 이때 선형 표 에서 데이터 요소 의 개 수 를 기록 하 며 순서 표 의 구 조 는 다음 과 같다.

#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
    ElemType elem[MAXSIZE];    //   
    int length;    //      
}SeqList;

3 주 순서 표 의 초기 화 순 서 는 빈 표를 만 드 는 것 으로 표 의 길 이 를 0 으로 설정 하여 데 이 터 를 저장 하지 않 았 음 을 나타 낸다 (0 번 단원 은 저장 하지 않 음).

SeqList *Init_SeqList()
{
    SeqList *L = (SeqList *)malloc(sizeof(SeqList));
    L->length = 0;
    return L;
}

4 주 순서 표 의 삽입 순서 표 의 삽입 은 표 의 i 번 째 위치 에 새로운 요소 x 를 삽입 하고 삽입 한 후에 표 의 길이 와 1 을 추가 하 는 것 을 말한다.삽 입 된 위치 가 정상 인지, 이때 시계 가 꽉 찼 는 지 주의해 야 합 니 다.

int In_SeqList(SeqList *L,int i,ElemType x)
{
    int j;
    if(L->length == MAXSIZE-1)
    {
        printf("       
");
        return FALSE;
    }
    if(i<1 || i>L->length+1)
    {
        printf("        
");
        return FALSE;
    }
    for(j=L->length ; j>=i ; j--)
        L->elem[j+1] = L->elem[j];
    L->elem[i] = x;
    L->length++;
    return TRUE;
}

5 주 순서 표 의 삭제 순서 표 의 삭 제 는 표 의 i 번 째 요 소 를 순서 표 에서 삭제 하고 삭제 한 후에 표 의 길 이 를 1 로 줄 이 는 것 을 말한다.삭 제 된 위치 가 정확 한 지, 이 시계 가 비어 있 는 지 주의 하 십시오.

int Delete_SeqList(SeqList *L,int i)
{
    int j;
    if(i<1 || i>L->length)
    {
        printf("    %d   
",i);
        return FALSE;
    }
    for(j=i ; j<=L->length-1;j++)
        L->elem[j] = L->elem[j+1];
    L->length--;
    return TRUE;
}

6 주 순서 표 의 찾기 는 순서 표 에서 주어진 요소 x 와 같은 값 을 찾 고 x 가 표 에 있 는 위 치 를 되 돌려 줍 니 다. 그렇지 않 으 면 FALSE 로 돌아 갑 니 다.

int Search_SeqList(SeqList *L,ElemType x)
{
    int i=1;
    while(i<=L->length && L->elem[i]!=x)
        i++;
    if(i > L->length)
        return FALSE;
    else
        return i;
}

7 주 두 순서 표 는 두 순서 표 A 와 B 를 합 쳐 그 요 소 는 모두 큰 것 에서 작은 것 으로 배열 한 다음 에 이 두 순서 표를 하나의 순서 표 C 로 합 쳐 C 도 큰 것 에서 작은 것 으로 배열 하도록 요구한다.

void Merge_SeqList(SeqList *A,SeqList *B,SeqList *C)
{
    int i,j,k;
    i=j=k=1;
    while(i<=A->length && j<B->length)
    {
        if(A->elem[i]<B->elem[j])
            C->elem[k++] = A->elem[i++];
        else
            C->elem[k++] = B->elem[j++];
    }
    while(i <= A->length)
        C->elem[k++] = A->elem[i++];
    while(j <= B->length)
        C->elem[k++] = B->elem[j++];
    C->length = A->length + B->length;
}

총 코드

#include 
#include 
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100

typedef int ElemType;

typedef struct
{
    ElemType elem[MAXSIZE];    //   
    int length;                //      
}SeqList;
//       
SeqList *Init_SeqList()
{
    SeqList *L = (SeqList *)malloc(sizeof(SeqList));
    L->length = 0;
    return L;
}
//      
int In_SeqList(SeqList *L,int i,ElemType x)
{
    int j;
    if(L->length == MAXSIZE-1)
    {
        printf("       
");
        return FALSE;
    }
    if(i<1 || i>L->length+1)
    {
        printf("        
");
        return FALSE;
    }
    for(j=L->length ; j>=i ; j--)
        L->elem[j+1] = L->elem[j];
    L->elem[i] = x;
    L->length++;
    return TRUE;
}
//      
int Delete_SeqList(SeqList *L,int i)
{
    int j;
    if(i<1 || i>L->length)
    {
        printf("    %d   
",i);
        return FALSE;
    }
    for(j=i ; j<=L->length-1;j++)
        L->elem[j] = L->elem[j+1];
    L->length--;
    return TRUE;
}
//      
int Search_SeqList(SeqList *L,ElemType x)
{
    int i=1;
    while(i<=L->length && L->elem[i]!=x)
        i++;
    if(i > L->length)
        return FALSE;
    else
        return i;
}
//        
void Merge_SeqList(SeqList *A,SeqList *B,SeqList *C)
{
    int i,j,k;
    i=j=k=1;
    while(i<=A->length && jlength)
    {
        if(A->elem[i]elem[j])
            C->elem[k++] = A->elem[i++];
        else
            C->elem[k++] = B->elem[j++];
    }
    while(i <= A->length)
        C->elem[k++] = A->elem[i++];
    while(j <= B->length)
        C->elem[k++] = B->elem[j++];
    C->length = A->length + B->length;
}
//         
void Show_SeqList(SeqList *L)
{
    int i;
    for(i=1;i<=L->length;i++)
    {
        printf("%d  ",L->elem[i]);
        if(i%15 == 0)
            printf("
");
    }
    printf("
");
}
void print()
{
    printf("1.    
");
    printf("2.    
");
    printf("3.    
");
    printf("4       
");
    printf("0.  
");
    printf("          :");
}
//    
void Try_SeqList()
{
    SeqList *L;
    SeqList *A,*B,*C;
    int i,x,choose;
    L = Init_SeqList();
    for(i=1 ; i<=10 ; i++)
        In_SeqList(L,i,i);
    printf("   L     :");
    Show_SeqList(L);
    do 
    {
        print();
        scanf("%d",&choose);
        switch ( choose )
        {
        case 1:
            printf("            :");
            scanf("%d%d",&i,&x);
            In_SeqList(L,i,x);
            printf("     ，   L   :");
            Show_SeqList(L);
            break;
        case 2:
            printf("          :");
            scanf("%d",&i);
            Delete_SeqList(L,i);
            printf("     ，   L   :");
            Show_SeqList(L);
            break;
        case 3:
            printf("          :");
            scanf("%d",&x);
            printf("%d  %d 
",x,Search_SeqList(L,x));
            break;
        case 4:
            A = Init_SeqList();
            B = Init_SeqList();
            C = Init_SeqList();
            In_SeqList(A,1,1);
            In_SeqList(A,2,3);
            In_SeqList(A,3,5);
            In_SeqList(A,4,7);
            printf("A : ");
            Show_SeqList(A);
            In_SeqList(B,1,2);
            In_SeqList(B,2,4);
            In_SeqList(B,3,6);
            In_SeqList(B,4,8);
            printf("B : ");
            Show_SeqList(B);
            printf("  A B
");
            Merge_SeqList(A,B,C);
            printf("C : ");
            Show_SeqList(C);
            break;
        case 0:
            return ;
        default:
            printf("      !!!
");
        }
        printf("      ……");
        getchar();
        getchar();
    } while (choose != 0);
}
int main(void)
{
    Try_SeqList();
    return 0;
}