C - 데이터 구조 - 선형 표

사실 현재 인터넷 에 여러 가지 가 있 습 니 다. 다만 모든 사람 이 읽 는 것 이 자신 에 게 주 는 느낌 이 다 릅 니 다. 자신 이 직접 체험 해 봐 야 정말 느 낄 수 있 습 니 다. 코드 를 읽 는 것 은 사람들 에 게 많은 깨 우 침 을 줄 수 있 습 니 다. 학습 하 는 마음으로 코드 를 보고 정 제 를 시작 합 니 다.
선형 구조의 특징: 데이터 요소 의 비 공 유한 집중 1. 유일한 '첫 번 째' 라 고 불 리 는 데이터 요소 가 존재 합 니 다. 2. 유일한 '마지막' 이 라 고 불 리 는 데이터 요소 가 존재 합 니 다. 3. 첫 번 째 를 제외 하고 집합 중의 모든 데이터 요 소 는 하나의 전구 만 있 습 니 다. 4. 마지막 을 제외 하고 집합 중의 모든 요 소 는 하나의 후속 만 있 습 니 다.
선형 표 의 유형 정의
linear list 는 가장 자주 사용 되 고 가장 간단 한 데이터 구조 이다.n 개의 데이터 요 소 를 나타 내 는 선형 서열
쉽게 말 하면 직선 적 인 데이터 구조 이다.모든 노드 는 하나의 데이터 요소 로 하나의 변수 일 수도 있 고 하나의 구조 체 일 수도 있 지만 그들 사이 에는 직선 적 인 관계 가 존재 한다.
선형 표 는 사실은 데이터 구조 집합 이다. 이런 데이터 구조 집합 은 선형 데이터 구 조 를 많이 포함 하고 순서 표, 링크, 대기 열, 스 택 등에 들어간다.
선형 표 의 순서 표시 와 실현
선형 표 의 순 서 는 한 그룹의 주소 로 연속 적 인 저장 장치 로 선형 표 의 데이터 요 소 를 순서대로 저장 하 는 것 을 말한다.

구조 체 유닛 을 정의 합 니 다

데이터 요 소 를 포함 하 는 주소 (연속 적 인 데이터 요소 주소 에 따라 데이터 삽입 및 삭제 작업)

현재 분 배 된 메모리 용량 (데이터 요소 주소 가 가득 찼 을 때 이 를 이용 하여 판단 하고 메모리 증가)

현재 의 길이 (몇 개의 데이터 요 소 를 기록 하여 우 리 는 데이터 요소 에 대한 조작 을 더욱 편리 하 게 할 수 있 습 니 다)

//               
#define LIST_INIT_SIZE 100 //              
#define LISTINCREMENT 10  //             
typedef struct {
    ElemType *elem; //        
    int   length; //     
    int   listsize;//         ( sizeof(ElemType)   )
}

선형 표 순서 표시 조작 실례 코드

/***
 *Arrlist.h
 *  Copyright © 2016  liuxinming. All rights reserved.
 *Purpose:
 *               、    、    、    、    、    、             
 ***/
#include <stdio.h>
#include <stdlib.h>
#include "string.h"

#define LIST_INIT_SIZE 100 //              
#define LISTINCREMENT 10   //             

//         
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR 0
#define INFEASIBLE -1
#define OVERLOW -2

// Status       ,            
typedef int Status;
typedef int ElemType;

// -----              -----
typedef struct
{
    ElemType * elem; //       
    int length;      //     
    int listsize;    //          ( sizeof(ElemType)   )
}SqList;

//     ：         L
Status InitList(SqList *L){
    //               
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(! L->elem) exit(OVERLOW); //       

    L->length = 0; //      0
    L->listsize = LIST_INIT_SIZE; //       
    return OK;
}// InitList_sq

//     ：   L   
//     ：     L
Status DestroyList(SqList *L){
    //         
    if (L == NULL) {
        return ERROR;
    }
    //   calloc, malloc, realloc       
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
    return OK;
}// DestroyList

//     ：   L   
//     ： L     。
Status ClearList(SqList *L){
    //         
    if (L == NULL) {
        return ERROR;
    }

    L->length = 0;
    return OK;
}// ClearList

//     ：   L   
//     ： L   ，   TRUE,    FALSE
Status ListEmpty(SqList L){
    if (L.length == 0)
        return TRUE;
    else
        return FALSE;
}// ListEmpty

//     ：   L   
//     ：  L       
Status ListLength(SqList L){
    return L.length;
}

//     ：   L   , 1<=i<=ListLength(L)
//     ： e  L  i       
Status GetElem(SqList L, int i, ElemType *e){
    if (i<1 || i>L.length)
        exit(ERROR);
    *e =* (L.elem+i-1);
    return OK;
}

//     ：   L   ，compare()         (   1,   0)。
//     ：  L  1  e    compare()        。           ，     0.
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType,ElemType)){
    ElemType *p;
    int i = 1; // i            
    p = L.elem; // p              
    while (i <= L.length && !compare(*p++,e)) {
        ++i;
    }

    if (i<=L.length)
        return i;
    else
        return ERROR;

}

//     ：   L   
//     ： cur_e L     ，      ，  pre_e      ，      ，pre_e   
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e){
    int i = 2;
    ElemType *p = L.elem + 1;
    while (i <= L.length && *p!=cur_e) {
        p++;
        i++;
    }
    if (i>L.length)
        return INFEASIBLE;
    else{
        *pre_e = *--p;
        return OK;
    }
}

//     ：   L   
//     ： cur_e L     ，       ，  next_e      ，      ,next_e   
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e){
    int i = 1;
    ElemType *p = L.elem;
    while (i < L.length && *p!=cur_e) {
        i ++;
        p ++;
    }

    if (i == L.length)
        return INFEASIBLE;
    else{
        *next_e = *++p;
        return OK;
    }
}

//     ：   L   ,1<=i<=ListLength(L)+1
//     ： L  i             e,L    1
Status ListInsert(SqList *L, int i, ElemType e){
    ElemType *newbase,*q,*p;
    if(i<1 || i>L->length+1)
        return ERROR; // i    
    if(L->length>=L->listsize) //         ,    
    {
        newbase = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newbase) exit(OVERLOW); //       
        L->elem = newbase; //    
        L->listsize += LISTINCREMENT; //       
    }

    q=L->elem+i-1; /* q      */
    for(p=L->elem+L->length-1;p>=q;--p) /*              */
        *(p+1)=*p;
    *q=e; /*   e */
    ++L->length; /*    1 */
    return OK;
}


//     ：   L      ，1,=i<=ListLength(L)
//     ：  L  i     ，  e    ,L   -1
Status ListDelete(SqList *L, int i, ElemType *e){
    ElemType *p, *q;

    if (i<1 || i>L->length)
        return ERROR; // i    
    p = L->elem+i-1; // p         
    *e = *p; //          e
    q = L->elem + L->length - 1; //        

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

//     ：   L   
//     ：   L           vi()。  vi()  ，     
Status ListTraverse(SqList L, void(*vi)(ElemType*)){
    ElemType *p;
    int i;
    p = L.elem;
    for (i=1; i<=L.length; i++) {
        vi(p++);
    }

    printf("
");
    return OK;
}

테스트 코드:

//
//  main.c
//  arrlist
//
//  Created by liuxinming on 16/9/17.
//  Copyright © 2016  liuxinming. All rights reserved.
//

#include 
#include "Arrlist.h"

//          ，Union()  
Status equal(ElemType c1,ElemType c2)
{
    if(c1==c2)
        return TRUE;
    else
        return FALSE;
}

//        Lb    La         La 
void Union(SqList *La,SqList Lb)
{
    ElemType e;
    int La_len,Lb_len;
    int i;
    La_len=ListLength(*La); //        
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e); //  Lb  i       e
        if(!LocateElem(*La,e,equal)) // La     e     ,    
        {
           ListInsert(La,++La_len,e);
        }

    }
}

void print(ElemType *c)
{
    printf("%d ",*c);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Testing start!
");
    SqList La,Lb;
    ElemType t1,t2,t3;
    t1 = 10;
    t2 = 20;
    t3 = 30;
    int t1_length,t2_length,t3_length, i;

    //          La
    InitList(&La);
    //       t1
    ListInsert(&La, 1, t1);
    //        
    t1_length = ListLength(La);
    //       t2
    ListInsert(&La, 2, t2);
    t2_length = ListLength(La);
    //       t3
    ListInsert(&La, 3, t3);
    t3_length = ListLength(La);
    //             L     
    printf("t1_length=%d,t2_length=%d,t3_length=%d
",t1_length,t2_length,t3_length);

    //    La   
    printf("La= ");
    ListTraverse(La,print);

    //   Lb   5   
    InitList(&Lb);
    for (i=1; i<=5; i++) {
        ListInsert(&Lb, i, 2 * i);
    }

    //    Lb   
    printf("Lb= ");
    ListTraverse(Lb, print);
    //    Lb  
    printf("Lb length = %d
",ListLength(Lb));

    // La U Lb
    Union(&La, Lb);

    //    L   
    printf("new La= ");
    ListTraverse(La,print);
    printf("end
");
    return 0;
}

실행 결과:
Testing start! t1_length=1,t2_length=2,t3_length=3 La= 10 20 30 Lb= 2 4 6 8 10 Lb length = 5 new La= 10 20 30 2 4 6 8 end Program ended with exit code: 0