알고리즘 과 데이터 구조 (1) - 선형 표

선형 표 는 가장 기본 적 이 고 간단 하 며 가장 자주 사용 하 는 데이터 구조 이다.선형 표 에서 데이터 요소 간 의 관 계 는 일대일 관계 이다. 즉, 첫 번 째 와 마지막 데이터 요 소 를 제외 하고 다른 데이터 요 소 는 모두 첫 번 째 와 끝 이 연결 되 어 있다.선형 표 의 논리 구 조 는 간단 하여 실현 과 조작 에 편리 하 다.따라서 선형 표 라 는 데이터 구 조 는 실제 응용 에서 광범 위 하 게 사용 되 는 데이터 구조 이다.
1 구조
선형 표 는 자주 사용 하 는 데이터 구조 로 다음 과 같이 선형 표 와 그 순서 저장 을 소개 하고 스 택 과 대기 열 및 그들의 순서 에 대해 상세 한 디자인 설명 을 한다.실제 응용 에서 선형 표 는 스 택, 대기 열, 문자열 등 특수 선형 표 형식 으로 사용 된다.이러한 특수 선형 표 는 모두 각자 의 특성 을 가지 기 때문에 이런 특수 선형 표 의 특성 을 파악 하 는 것 은 데이터 연산 의 신뢰성 과 조작 효율 을 향상 시 키 는 데 모두 중요 하 다.선형 표 는 하나의 선형 구조 로 n ≥ 0 개의 결점 을 포함 하 는 유한 한 서열 이다. 그 중의 결점 에 대해 있 고 하나의 시작 점 만 있 으 며 전구 가 없 지만 하나의 후계 결점 이 있다. 또한 하나의 단말기 결점 만 있 고 후계 결점 이 없 지만 하나의 전구 결점 이 있다. 다른 결점 은 모두 있 고 하나의 전구 와 하나의 후계 결점 만 있다.일반적으로 하나의 선형 표 는 하나의 선형 서열 로 나 타 낼 수 있다. k1, k2,..., kn, 그 중에서 k1 은 시작 점 이 고 kn 은 단말기 결점 이다.데이터 요소 의 질서 (순서) 집합 입 니 다.
2 특징
선형 구조의 기본 적 인 특징 은 다음 과 같다. 1. 집합 에 유일한 '제1 원소' 가 존재 한다.2. 집합 에 유일한 '마지막 요소' 가 존재 한다.3. 마지막 요 소 를 제외 하고 유일한 후계 (후 부품) 가 있다.4. 첫 번 째 요 소 를 제외 하고 유일한 전구 (앞부분) 가 있다.n (n ≥ 0) 개 데이터 요소 (결점) a1, a2,..., an 으로 구 성 된 유한 서열.데이터 요소 의 개수 n 은 표 의 길이 로 정의 합 니 다.n = 0 시 를 빈 표 라 고 합 니 다.항상 비 어 있 는 선형 표 (n > 0) 를 다음 과 같이 기록한다. (a1, a2,... an) 데이터 요소 ai (1 ≤ i ≤ n) 는 추상 적 인 기호 일 뿐 그 구체 적 인 의 미 는 서로 다른 상황 에서 다 를 수 있다.선형 표 의 기본 조작
1) MakeEmpty (L) 는 L 을 빈 테이블 로 바 꾸 는 방법 2) Length (L) 는 테이블 L 의 길 이 를 되 돌려 줍 니 다. 즉, 테이블 에 있 는 원소 개수 3) Get (L, i) 은 함수 이 고 함수 값 은 L 에 있 는 원소 (1 ≤ i ≤ n) 4) Prev (L, i) 는 i 의 전구 원소 5) Next (L, i) 는 i 의 후계 원소 6) Locate (L, x) 는 함수 이 며 함수 값 은 원소 x 가 L 에 있 는 위치 7) Insert 입 니 다.(L, i, x) 표 L 의 위치 i 에 요소 x 를 삽입 하여 원래 위치 i 를 차지 하 던 요소 와 뒤의 요 소 를 모두 뒤로 밀어 8) Delete (L, p) 표 L 에서 위치 p 의 요 소 를 삭제 합 니 다 9) IsEmpty (L) 표 L 이 빈 표 (길이 0) 이면 true 로 돌아 갑 니 다. 그렇지 않 으 면 false 10) Clear (L) 로 돌아 가 모든 요소 11) Init (L) 를 제거 합 니 다. 첫 번 째 는 선형 표 가 비어 있 는 12) Traverse (L) 를 초기 화 합 니 다.모든 요 소 를 출력 13) Find (L, x) 에서 요 소 를 찾 고 되 돌려 줍 니 다 14) Update (L, x) 수정 요소 15) Sort (L) 는 모든 요 소 를 주어진 조건 에 따라 16) strstr (string 1, string 2) 문자 배열 의 string 1 에 string 2 의 첫 번 째 주소 가 나타 납 니 다.
회고 코드 는 다음 과 같다.

#include "stdio.h"
//          
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0

typedef struct
{
    int data[MAXSIZE];
    int last;
}SeqList;

//       
SeqList SeqListInit()
{//          L
    SeqList L;  //  L    
    L.last = 0; //       
    return L;   //      
}

//     
int SeqListLocate(SeqList L, int x)
{//     L     x   。     ，            ，    -1      
    int i = 1;
    while(i <= L.last && L.data[i - 1] != x)
    {
        i++;
    }
    if (i <= L.last)
    {
        return i;   //          
    }
    else
    {
        return 0;  //     
    }
}

//      
int IsEmpty(SeqList L)
{
    return (L.last == 0 ? TRUE : FALSE);
}

//     
SeqList SeqListInsert(SeqList L, int i, int x)
{//        i       x
    int j;
    if(L.last == MAXSIZE)
    {
        printf("  
");            //   ，  
        exit(0);
    }
    if(i < 1 || i > L.last + 1)
    {
        printf("      
");     //      ，  
        exit(0);
    }
    for(j = L.last - 1; j >= i - 1; j--)
    {
        L.data[j + 1] = L.data[j];  //  i             
    }
    L.data[i - 1] = x;              //        i   
    L.last++;                       //       1
    return (L);                     //            
}

//     
SeqList SeqListDelete(SeqList L, int i)
{//         i   
    int j;
    if (i < 1 || i > L.last)
    {
        printf("    
");           //              
        exit(0);
    }
    for(j = i; j <= L.last - 1; j++)
    {
        L.data[j - 1] = L.data[j];      //     
    }
    L.last--;                           //       1
    return (L);                         //            
}

//           
SeqList SeqListMerge(SeqList Sla, SeqList Slb)
{//           Sla Slb          Slc，Slc        
    //    
    SeqList Slc;
    Slc.last = 0;
    int i = 0, j = 0, k = -1;
    while(i < Sla.last && j < Slb.last)     // Sla Slb   
    {
        if(Sla.data[i] <= Slb.data[j])
        {
            Slc.data[++k] = Sla.data[i++];  // Sla     Slc
        }
        else
        {
            Slc.data[++k] = Slb.data[j++];  // Slb     Slc
        }
    }
    while(i < Sla.last)
    {
        Slc.data[++k] = Sla.data[i++];      // Slb  ， Sla           
    }
    while(j < Slb.last)
    {
        Slc.data[++k] = Slb.data[j++];      // Sla  ， Slb           
    }
    Slc.last = k + 1;
    return (Slc);
}

//   SeqList   
void ShowData(SeqList L)
{
    int i = 0;
    for (; i < L.last; ++i)
    {
        printf("%d\t", L.data[i]);
    }
    printf("
");
}

int main()
{
    //     
    SeqList l = SeqListInit();
    l = SeqListInsert(l, 1, 20);
    l = SeqListInsert(l, 1, 13);
    l = SeqListInsert(l, 1, 10);
    ShowData(l);
    printf("L.last = %d
", l.last);

    int x = SeqListLocate(l, 10);
    printf("10 in %d
", x);


    l = SeqListDelete(l, 2);
    ShowData(l);

    SeqList l2 = SeqListInit();
    l2 = SeqListInsert(l2, 1, 44);
    l2 = SeqListInsert(l2, 1, 23);
    l2 = SeqListInsert(l2, 1, 4);
    ShowData(l2);
    l = SeqListMerge(l, l2);
    ShowData(l);
    return 0;
}

이것 은 사실 어제 돌 이 켜 본 것 입 니 다. 오늘 아침 에 야 블 로 그 를 보 낼 시간 이 있 습 니 다 ~ ~