C 언어 로 순서 표 의 첨삭 과 역 치 를 실현 하 다.

데이터 구조 에서 우리 가 가장 먼저 접촉 한 것 은 순서 표 입 니 다. 그러면 순서 표 는 무엇 입 니까?순서 표 는 컴퓨터 메모리 에 배열 로 저 장 된 선형 표 로 주소 연속 저장 장치 로 데이터 요 소 를 순서대로 저장 하 는 선형 구 조 를 말한다.선형 표 는 순서대로 저장 하 는 방식 으로 저장 하 는 것 을 순서 표 라 고 한다.순서 표 는 표 의 결산 점 을 컴퓨터 메모리 의 주소 연속 저장 장치 에 순서대로 저장 하 는 것 이다.
기왕 그것 이 수조 의 특징 이 있 고 선형 이라는 특징 을 가지 고 있 는 이상 가장 기본 적 인 증가, 삭제, 조사, 수정, 역 치 는 반드시 파악 해 야 할 것 이다. 오늘 우 리 는 순서 표 의 원소 에 대해 어떻게 첨삭, 수정 과 역 치 를 하 는 지 조사해 보 자.

    ：
void InitSeqList(PSeqList seq);   //      
void PushBack(PSeqList pSeqList, DataType data);  //       
void PopBack(PSeqList pSeqList);   //       
void PushFront(PSeqList pSepList, DataType data);  //       
void PopFront(PSeqList pSeqList);    //       
void Insert(PSeqList pSeqList, int pos, DataType data);  //        
void Erase(PSeqList pSeqList, int pos);  //         
int Find(PSeqList pSeqList, DataType data);  //    
void Remove(PSeqList PseqList, DataType data);  //      
int Empty(PSeqList pSeqList);   //  
void PrintSeqList(PSeqList pSeqList);  //     
void Inverse(PSeqList pSeqList);    //     
void Change(PSeqList pSeqList,DataType data1,DataType data2);   //             

     ：
#include
#include
#include

#define MAX_SIZE 10
typedef int DataType;

typedef struct SeqList
{
    DataType array[MAX_SIZE];
    int size;
}SeqList,*PSeqList;

void InitSeqList(PSeqList seq)    //      
{
    memset(seq->array,0,MAX_SIZE*(sizeof(DataType)));
    seq->size=0;
}

int Empty(PSeqList seq)     //  
{
    if(seq->size > MAX_SIZE)
        return 1;
     else  return 0;
}

void PushBack(PSeqList seq, DataType data)  //       
{
    assert(seq);     //    ，      
    if(Empty(seq))
        {
            return;
         }

    seq->array[seq->size]=data;
    seq->size++;
}

void PopBack(PSeqList seq)      //       
{
     assert(seq);
     if(Empty(seq))
        {
            return;
         }

     --seq->size;
}

void PushFront(PSeqList seq, DataType data)     //       
{
    int i=0; 
    assert(seq);
     if(Empty(seq))
        {
            return;
         }
     for(i=seq->size;i>0;i--)
     {
         seq->array[i]=seq->array[i-1];
     }
     seq->array[0]=data;
     seq->size++; 
}

void PopFront(PSeqList seq)     //       
{
    int i=0; 
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=0;isize-1;i++)
    {
         seq->array[i]=seq->array[i+1];
    }
    --seq->size;
}

void Insert(PSeqList seq, int pos, DataType data)        //        
{
    int i=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=seq->size;i>pos;i--)
    {
        seq->array[i]=seq->array[i-1];
    }
    seq->array[pos]=data;
    seq->size++; 
}

void Erase(PSeqList seq, int pos)    //        
{
    int i=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=pos;isize;i++)
    {
        seq->array[i]=seq->array[i+1];
    }
    --seq->size;
}

int Find(PSeqList seq, DataType data)    //         
{
    int i=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=0;isize;i++)
    {
        if(seq->array[i]==data)
        {
          printf("%d      %d  
",data,i+1);
          return;
        }
    }
    printf("          ！
");
    return;
}

void Remove(PSeqList seq, DataType data)   //           
{
    int j=0;
    int i=0;
    int ret=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=0;isize;i++)
    {
        if(seq->array[i]==data)
        {
            for(j=i;jsize-1;j++)
            {
                seq->array[j]=seq->array[j+1];
            }
            --seq->size;
            return;
        }
    }
    printf("%d   ！
",data);
}

void PrintSeqList(PSeqList seq)     //     
{
    int i=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=0;isize;i++)
    {
        printf("%d ",seq->array[i]);
    }
    printf("
");
}

void Inverse(PSeqList seq)    //      
{
    int i=0;
    int temp=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }

    for(i=0;isize)/2;i++)
    {
        temp=seq->array[i];
        seq->array[i]=seq->array[seq->size-1-i];
        seq->array[seq->size-1-i]=temp;
    }
}

void Change(PSeqList seq,DataType data1,DataType data2)      //             
{
    int i=0;
    assert(seq);
    if(Empty(seq))
        {
            return;
         }
    for(i=0;isize;i++)
    {
        if(seq->array[i]==data1)
        {
            seq->array[i]=data2;
            return;
        }
    }
    printf("%d   ！
",data1);
}

    ：
void text()
{
    SeqList seq;
    InitSeqList(&seq);    //   
    PrintSeqList(&seq);

    PushBack(&seq,1);
    PushBack(&seq,2);
    PushBack(&seq,3);
    PushBack(&seq,4);
    PushBack(&seq,5);
    PushBack(&seq,6);
    PushBack(&seq,7);    //       
    PrintSeqList(&seq);

    PopBack(&seq);       //       
    PrintSeqList(&seq);

    PushFront(&seq,8);
    PushFront(&seq,9);    //       
    PrintSeqList(&seq);

    PopFront(&seq);       //       
    PrintSeqList(&seq);

    Insert(&seq,3,10);    //    
    PrintSeqList(&seq);

    Erase(&seq,3);        //    
    PrintSeqList(&seq);

    Inverse(&seq);       //  
    PrintSeqList(&seq);

    Find(&seq,9);        //  
    PrintSeqList(&seq);

    Remove(&seq,9);      //      
    PrintSeqList(&seq);

    Change(&seq,9,2);    //      
    PrintSeqList(&seq);
}

int main()
{
    text();
    system("pause");
    return 0;
}

여기 서 우 리 는 순서 표를 정리 할 수 있다.

실현 방법 은 간단 하 다.많은 고급 언어 중에서 배열 유형 이 있 고 전체적으로 실현 하기 쉽다.

모든 요소 의 저장 위 치 는 간단 한 공식 으로 계산 할 수 있다.

검색 과 인쇄 작업 은 모두 선형 시간 으로 실행 되 고 요 소 를 옮 기 는 데 걸 리 는 시간 이 비교적 고정 적 입 니 다.그래서 자주 찾 아야 할 상황 에 적합 합 니 다.

순서대로 저 장 된 공간 은 정적 으로 분배 되 므 로 MAX 를 미리 지정 해 야 합 니 다.SIZE 크기.이 로 인해 공간의 낭 비 를 초래 할 수도 있다.

삽입 과 삭제 의 대가 가 매우 높다. 이 두 가지 조작 은 최 악의 상황 에서 시간 복잡 도 는 O (n) 로 평균 적 으로 이 두 가지 조작 은 절반 의 요 소 를 이동 해 야 할 것 으로 추정 된다.

순서 표 에 요 소 를 삽입 하거나 삭제 하 는 것 은 매우 복잡 하 다. 요 소 를 하나씩 이동 한 다음 에 삽입 하거나 삭제 해 야 한다.따라서 순서 표 에 삽입 하거나 삭제 하 는 것 은 낭비 적 인 행위 이 고 모든 노드 가 이동 하 는 횟수 는 표 의 절반 이 며 시간 복잡 도 는 상대 적 으로 높다.만약 에 만들어 진 모델 에 삭 제 된 요 소 를 삽입 해 야 할 요소 가 너무 많 으 면 순서 표를 선택 할 지 여 부 는 종합 적 으로 고려 해 야 한다.