[메모] 데이터 구조 - 표

시계.
추상 데이터 형식
프로그램 설계 의 기본 법칙 중 하 나 는 규칙 이 한 페이지 를 초과 해 서 는 안 된다 는 것 이다.프로그램 을 일부 모듈 로 나 누 어 실현 할 수 있다.
모듈 화 된 장점:
디 버 깅 이 쉽다.
여러 사람 이 동시에 하나의 모듈 식 프로그램 에 대해 프로 그래 밍 하 는 것 이 더욱 쉽다.
수정 이 쉽다
추상 적 인 데이터 형식 은 일부 조작의 집합 이다.
시계 ADT
우 리 는 크기 가 0 인 시 계 를 빈 시계 (empty list) 라 고 부른다.빈 시 계 를 제외 한 모든 시계 에 대해 우 리 는 Ai + 1 이 Ai (또는 Ai 에 이 어) 라 고 말 하고 Ai - t (ii (i > 1) 라 고 부른다.
표 의 첫 번 째 요 소 는 A1 이 고, 마지막 요 소 는 AN 입 니 다. A1 의 전구 원 도 정의 하지 않 고, AN 의 후계 원 도 정의 하지 않 습 니 다. 원소 Ai 는 표 의 위 치 는 i 입 니 다.
표 의 간단 한 배열 실현
표 에 대한 모든 조작 은 배열 을 통 해 이 루어 질 수 있다.
배열 은 동태 적 으로 지 정 된 것 이다. 우 리 는 표 의 크기 를 평가 해 야 한다. 보통 크게 평가 해 야 하기 때문에 대량의 공간 을 낭비 할 수 있다.
삽입 과 삭제 의 운행 시간 이 항상 이렇게 느 리 고 표 의 크기 는 미리 알 아야 하기 때문에 간단 한 배열 은 표 와 같은 구 조 를 실현 하 는 데 사용 되 지 않 습 니 다.
체인 테이블
링크 는 메모리 에 연결 되 지 않 아 도 되 는 일련의 구조 로 구성 되 어 있 습 니 다. 모든 구 조 는 표 요소 와 이 요소 의 후계 원 을 포함 하 는 구 조 를 가리 키 는 지침 을 포함 하고 있 습 니 다. 우 리 는 Next 지침 이 라 고 부 릅 니 다. 마지막 단원 의 Next 지침 은 NULL 을 가리 키 고 있 습 니 다.
프로 그래 밍 디 테 일
몇 군데 문제 가 생 길 수 있 습 니 다.
4. 567917. 주어진 정의 에서 출발 하여 표 앞 에 요 소 를 삽입 하 는 진정한 선형 방법 은 존재 하지 않 는 다.
4. 567917. 표 앞에서 삭 제 를 실시 하 는 것 은 특수 한 상황 이다. 왜냐하면 그 는 표 의 시작 부분 을 바 꾸 었 기 때문이다.
4. 567917. 삭제 알고리즘 은 삭 제 된 요소 앞의 표 원 을 기억 하 라 고 요구 합 니 다. 4. 567918.
사실 간단 한 변 화 를 통 해 이 세 가지 문 제 를 해결 할 수 있 습 니 다. 우 리 는 표지 의 결산 점 을 남 길 것 입 니 다. 때로는 표 두 (header) 나 벙어리 노드 (Dummy node) 라 고 부 릅 니 다. 표 두 는 위치 0 곳 에 있 습 니 다. 표 두 를 사용 하면 가장 기본 적 인 지침 조작 을 할 수 있 고 특수 한 상황 의 코드 를 헷 갈 리 게 하지 않 을 수 있 습 니 다.

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int Islast( Position P, List L );
Position Find( ElmenetType X, List L );
void Insert( ElementType X, List L, Posistion P );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );

#endif

struct Node
{
    ElementType Element;
    Position Next;
};

/* Return true if L is Empty */
int IsEmpty(List L)
{
    return L->Next == NULL;
}

/* Return true is P is the last position in list L */
/* parameter L is unused in this implementation */
int IsLast( Position P, List L )
{
    return P->Next == NULL;
}

/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while(P != NULL && P->Element != X)
        P = P->Next;
    return P;
}

어떤 요소 X 를 삭제 하려 면 고려 해 야 합 니 다. X 가 한 번 이 아니 거나 아예 없 으 면 우 리 는 무엇 을 합 니까? 우리 의 예 는 처음 나타 난 X 를 삭제 합 니 다. X 가 표 에 없 으 면 우 리 는 아무것도 하지 않 습 니 다. 이 를 위해 우 리 는 Find 이전 편지 수 (Find 함수 와 유사) 를 호출 하여 X 가 함 유 된 표 원 의 전구 원 P 를 찾 습 니 다.

/* Delete first occurrence of X from a list */
/* Assume use of a header node */
void Delete(ElementType X, List L)
{
    Position P,TmpCell;
    P = FindPrevious(X, L)
    if (!IsLast(P, L))
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

/* if x is not found, then next field of returned */
/* Position is NULL */
/* Assume a header */

Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while(P->Next != NULL && P->Next->Element != X)
        P = P->Next;
    return P;
}

프로그램 을 삽입 합 니 다. 삽입 할 요 소 를 표 L 과 위치 P 와 함께 입력 합 니 다.

void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL)
        FatalError("Out of space!!");
    TmpCell->Element= X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

흔 한 오류
가장 자주 발생 하 는 오 류 는 시스템 의 까다 로 운 오류 정보 로 인해 프로그램 이 무 너 지 는 것 입 니 다.