데이터 구조 - 선형 표 순서 저장

그 전에 데이터 구조 에 대한 학습 은 사상 을 중시 하고 실천 보다 작 았 다.실현 과정 에서 사실 적지 않 은 문제 가 존재 하고 있다 는 것 을 발견 하 였 다.이 단계 의 학습 과정 에서 좀 총 결 할 계획 이다.
실현 과정의 지식 은 훗날 다시 공부 하 는 데 편리 하 다.
지식 포인트: 포인터 전달 과 함수 포인터
 
포인터 전달: 데이터 양 이 많 을 때 (예 를 들 어 클래스 나 구조 체) 함수 가 파 라 메 터 를 전달 할 때 보통
전달 지침
함수 정의 시 형 삼 을 직접 조작 할 수도 있 고 변수 가 형 삼 을 받 은 후에 조작 할 수도 있 습 니 다.
Status ListTraverse(SqList *L)
{
    SqList *list_point = L;   //내부 에서 변 수 를 정의 하고 형 삼 을 받 은 후에 조작 합 니 다.
    ....
}
 
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b)
{
    DesList - > length = list a - > length + list b - > length; / 직접 조작 형 참 값,
    ....
}
 
함수 포인터
성명 / 정의: int LocateElem (SqList * L, ElemType e, Status (* cmp) (ElemType, ElemType);
호출: LocateElem (& La, 3, compare);  //compare 는 Status cmp (int, int) 형식 과 같 으 면 됩 니 다.
 
되다
typedef Status (*FunType)(ElemType, ElemType);  //  FunType 대표 로 Status xxx (int, int) 형식 함수 에 맞 는 함수 포인터
성명 / 정의: int LocateElem (SqList * L, ElemType e, FunType);
호출: LocateElem (& La, 3, compare);  //compare 는 Status cmp (int, int) 형식 과 같 으 면 됩 니 다.

//         
#include <stdio.h>
#include <malloc.h>
 
#define ElemType int
#define LIST_INCREMENT 10
#define LIST_INIT_SIZE 20
#define Status int
#define Position int
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
 
typedef struct{
ElemType *base; //     
int length;
int listsize;
}SqList;
 
typedef Status (*FunType)(ElemType, ElemType);
Status compare(ElemType, ElemType); //      1    1       0
Status GetElem(SqList *L, Position i, ElemType *e);//    i   
Status InitList_sq(SqList *L);
Status InsertList_sq(SqList *L, int i, ElemType e);//  i    base[i-1]    e
Status ListTraverse(SqList *L); //    
//int LocateElem(SqList *L, ElemType e, FunType cmp);// L    e           ，         
int LocateElem(SqList *L, ElemType e, Status (*cmp)(ElemType, ElemType));
 
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b);
 
int main()
{
    SqList list_sqA;
    SqList list_sqB;
    SqList list_sqC;
    int i;
    InitList_sq(&list_sqA);
    for (i = 1; i <= 9; i++)
    {
        InsertList_sq(&list_sqA, i, i);
        //printf("insert success
");
    }
    ListTraverse(&list_sqA);
    //i = LocateElem(&list_sqA, 4, compare);//     4     （  -1）
    //printf("%d", i);
 
    InitList_sq(&list_sqB);
    for (i = 1; i <= 20; i++)
    {
        InsertList_sq(&list_sqB, i, i*2);   
    }
    ListTraverse(&list_sqB);
 
    InitList_sq(&list_sqC);
    MergeList_sq(&list_sqC, &list_sqA, &list_sqB);
 
    ListTraverse(&list_sqC);
    return 0;
}
 
 
Status InitList_sq(SqList *L)
{
    SqList *List = L;
    if(NULL == (List->base = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType))))
        return FALSE;
 
    List->listsize = LIST_INIT_SIZE;
    List->length = 0;
 
    return OK;
}
//int LocateElem(SqList *L, ElemType e, FunType cmp);
int LocateElem(SqList *L, ElemType e, Status (*cmp)(ElemType, ElemType))//     e     
{
    int i = 0;
    SqList *List = L;
    for (i = 0; i < List->length; i++)
    {
        if (cmp(e, List->base[i]))
        {
            return i;
        }
    }
    return 0;
}
 
Status compare(ElemType a, ElemType b)
{
    if ( a <= b)
        return 1;
    else
        return 0;
}
 
Status InsertList_sq(SqList *L, int i, ElemType e)// i        1<= i <= length+1
{
    SqList *List = L;
    int k = 0;
    if ((i < 1)||(i > List->length+1))//    
    {
        return ERROR;
    }
    if (List->length == List->listsize) //     
    {
        List->base = (ElemType*)realloc(List->base, (List->length + LIST_INCREMENT)*sizeof(ElemType));
    }
 
    for(k = List->length; k >= i; k--) //k      length+1        length,   i      i-1
        List->base[k] = List->base[k-1];
    List->base[i-1] = e;//k = i -1 ; i-1  k，    i length+1    
 
    List->length++;//    
 
    return OK;
}
 
Status ListTraverse(SqList *L)
{
    SqList *list_point = L;
    int i;
    for (i = 1; i <= list_point->length; i++)
    {
        printf("%d ",list_point->base[i-1]);
    }
    printf("
");
 
    return OK;
}
 
Status GetElem(SqList *L, Position a, ElemType *e)
{
    int i = 0;
    if ((a < 1)||(a > L->length))
    {
        return ERROR;
    }
    *e = L->base[a-1];
 
    return OK;
}
 
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b)
{
    ElemType *Pa_end = list_a->base + list_a->length - 1;
    ElemType *Pb_end = list_b->base + list_b->length - 1;
    ElemType *Pa = list_a->base;
    ElemType *Pb = list_b->base;
    ElemType *P_list = DesList->base;
 
    DesList->length = list_a->length + list_b->length;
    if (DesList->listsize < DesList->length)//          
    {
        DesList->listsize = DesList->length = list_a->length + list_b->length;
        if(NULL == (DesList->base = (ElemType *)realloc(DesList->base, DesList->listsize * sizeof(ElemType))))
            return ERROR;
        P_list = DesList->base;
    }
 
    while( (Pb <= Pb_end)&&(Pa <= Pa_end) )
    {
        if (*Pa <= *Pb)
        {
            *P_list++ = *Pa++;
        }
        else
        {
            *P_list++ = *Pb++;
        }
    }
    while (Pa <= Pa_end)
    {
        *P_list++ = *Pa++;
    }
    while (Pb <= Pb_end)
    {
        *P_list++ = *Pb++;
    }
 
    return OK;
}

부족 한 점 이 있 으 니 잘 부탁드립니다. 의견 교환 을 환영 합 니 다 ~