데이터 구조: 순서 표 ADT 의 실현

선형 구 조 는 간단 하고 자주 사용 하 는 데이터 구조 이 고 선형 표 는 전형 적 인 데이터 구조 이다.
       일반적인 상황 에서 프로그램 에 데 이 터 를 저장 해 야 한다 면 가장 간단 하고 효과 적 인 방법 은 선형 표 에 저장 하 는 것 이다.대량의 데 이 터 를 조직 하고 검색 해 야 더 복잡 한 데이터 구 조 를 사용 하 는 것 을 고려 할 수 있다.
       모든 데이터 구조 에서 가장 간단 한 것 은 선형 표 이다.일반적으로 선형 표 는 n (n > = 0) 개 데이터 요소 의 유한 한 서열 로 정의 된다.기록:
                                                  L = (a(1),···,a(i),a(i+1),···,a(n))
       그 중에서 L 은 표 명 이 고 a (i) 는 데이터 요소 이 며 더 이상 분할 할 수 없 는 원자 데이터 이 며 결점 이나 표 항 이 된다.
       선형 표 는 유한 한 서열 로 표 중의 각 결점 이 연이어 배열 되 고 두 개의 인접 한 결점 사이 에 직접적인 전구 와 직접적인 후계 의 관계 가 있다 는 것 을 의미한다.선형 표 에는 유일한 첫 번 째 결점 과 마지막 결점 이 존재 한다. 첫 번 째 결점 은 전구 가 없고 마지막 결점 은 후계 가 없다. 모든 결점 은 기껏해야 하나의 직접 전구 만 있 고 기껏해야 하나의 직접 후계 만 있다.
       선형 표 의 저장 은 두 가지 가 있 는데 그것 이 바로 순서 저장 방식 과 체인 표 저장 방식 이다.순서 저장 방식 으로 이 루어 진 선형 표를 순서 표 라 고 하 는데 배열 을 표 로 하 는 저장 구조 이다.여기 순서 표를 말씀 드 리 겠 습 니 다.
       순서 표 의 정의: 선형 표 의 모든 노드 를 논리 적 인 순서에 따라 컴퓨터 저장 소 에서 지정 한 저장 위치 에서 시작 하 는 연속 저장 공간 에 순서대로 저장 합 니 다.
       특징 순서 표 에서 각 결점 의 논리 적 순 서 는 저 장 된 물리 적 순서 와 일치 합 니 다. 즉, i 번 째 결점 은 i 번 째 물리 적 위치 (1 < = i < = n) 에 저 장 됩 니 다.
                  (2) 순서 표 의 모든 결점 에 대해 순서 방문 도 할 수 있 고 무 작위 방문 도 할 수 있다.시계의 첫 번 째 결점 부터 시작 할 수 있 는 때 다.                               하나하나 방문 해도 결점 번호 에 따라 직접 방문 할 수 있다.
다음은 ADT 의 C++ 구현 순서 표를 보 여 줍 니 다.
1. 순서 표 의 기본 조작
1. 구조 함수
sz 를 지정 하여 배열 의 길 이 를 정의 합 니 다.

LinearList::LinearList(int sz){
    //    ，    size,      
    if(sz>0){
        data = new T[sz];//      
        if(data!=NULL){//    
            MaxSize = sz;
            last = -1;
        }
        else{
            cerr<

2. 지정 한 요소 찾기
여 기 는 표 에서 앞 뒤로 순서대로 찾 습 니 다.

int LinearList::Search(T &x) const{
    //    ：           x
    int i = 0;//    
    while(i<=last&&data[i]!=x){
        i++;
    }
    if(i>last){
        return -1;//   
    }
    else{
        return i+1;//  
    }
}

3. 삽입 동작
       순서 표 의 삽입 작업 은 비교적 간단 합 니 다. 순서 표 의 마지막 요소 의 아래 표 시 는 last 라 고 가정 합 니 다. 삽 입 된 요 소 는 x 입 니 다. 아래 표 시 된 i 의 위치 에 삽입 하려 면 원래 순서 표 에서 아래 표 시 된 i 를 last 의 결점 으로 한 단계 뒤로 이동 한 다음 에 x 를 아래 표 시 된 i 의 위치 에 삽입 하면 됩 니 다.

void LinearList::Insert(int i,T &x){
    //i   ，    
    if(last==MaxSize-1){
        cerr<last+1){
        cerr<i;j--){//    
        data[j] = data[j-1];
    }
    data[i] = x;//  i    x
    cout<

4. 삭제 작업
        작업 을 삭제 하 는 사상 은 삽입 작업 과 비슷 합 니 다. 선형 표 의 마지막 요소 의 아래 표 시 를 last 라 고 가정 하고 아래 표 시 된 요 소 를 삭제 하려 면 아래 표 시 를 i + 1 에서 last 의 결점 으로 한 자리 앞으로 이동 하면 됩 니 다.

//     i   
int LinearList::Delete(int i){
    if(i<0||i>last){
        cerr<=0){
        last--;//   -1
        for(int j=i;j<=last;j++){//      
            data[j] = data[j+1];
        }
        cout<

5. 원소 x 이전의 원소 가 져 오기

//  x       
T LinearList::GetPrior(T &x){
    if(Length()==0){
        cout<

6. 원소 x 의 아래 표 시 를 획득

T LinearList::GetNext(T &x){
    if(Length()==0){
        cout<

7. 인쇄 순서 표

void LinearList::PrintList(){
    for(int i=0;i<=last;i++){
        cout<

8. 순서 표 비우 기 (석조 함수 이용)

~LinearList(){delete[] data;}

9. 순서 표 길이 조작

//           
int Length() const {return last+1;}

2. 완전한 ADT 와 함수 조작
1. 데이터 구조의 정의 와 기본 조작 함수 에 대한 설명

/*
   ADT
*/
#include 
#include 
using namespace std;

typedef double T;

class LinearList{
public:
    int last;
    int LinearListLength;//     
    int MaxSize;//            
    int LinearListLast;//            
    T *data;//            
public:
    LinearList(int sz);
    ~LinearList(){delete[] data;}

    //           
    int Length() const {return last+1;}
    //    x      
    int Search(T &x) const;
    //   i    x
    void Insert(int i,T &x);
    //    x   
    int Delete(int i);
    //   
    int IsEmpty(){return last==-1;}
    //     
    int IsFull(){return last==MaxSize-1;}
    //   i   
    T GetData(int i){return data[i-1];};
    //   x     
    T GetPrior(T &x);
    //   x     
    T GetNext(T &x);
    //     
    void PrintList();
};

2. 조작 함수 의 구체 적 인 실현

LinearList::LinearList(int sz){
    //    ，    size,      
    if(sz>0){
        data = new T[sz];//      
        if(data!=NULL){//    
            MaxSize = sz;
            last = -1;
        }
        else{
            cerr<last){
        return -1;//   
    }
    else{
        return i+1;//  
    }
}

void LinearList::Insert(int i,T &x){
    //i   ，    
    if(last==MaxSize-1){
        cerr<last+1){
        cerr<i;j--){//    
        data[j] = data[j-1];
    }
    data[i] = x;//  i    x
    cout<last){
        cerr<=0){
        last--;//   -1
        for(int j=i;j<=last;j++){//      
            data[j] = data[j+1];
        }
        cout<