데이터 구조제2 장선형 표

제2 장 선형 표
2.1 선형 표 의 논리 구조 2.2 선형 표 의 순서 저장 구조 와 2.3 선형 표 의 체인 저장 구 조 를 실현 하고 2.4 순서 표 와 단일 체인 표 의 비교 2.5 선형 표 의 다른 저장 방법 을 실현 한다.
2.1 선형 표 의 논리 구조
선형 표 (Linear List) 의 정의 선형 표 는 0 개 또는 여러 개의 같은 유형의 데이터 요 소 를 가 진 유한 한 서열 이다.데이터 요소 의 개 수 는 선형 표 의 길이 로 정의 된다.길 이 는 0 시 에 빈 표 라 고 부 르 고 하나의 비 빈 표 는 보통 L = (a 1, a 2,.............................................................
2.2 선형 표 의 순서 저장 구조 와 실현
순서 표 특징: 선형 표 의 순서 저장 은 주소 연속 저장 장치 로 선형 표 의 각 요 소 를 순서대로 저장 하 는 것 을 말한다. 역할: 선형 표 에서 논리 구조 에 인접 한 데이터 요 소 는 인접 한 물리 저장 장치 에 저장 된다. 즉, 데이터 요소 물리 적 으로 저 장 된 인접 관 계 를 통 해 데이터 요소 간 의 논리 적 인접 관 계 를 나타 낸다.순서 저장 의 실현: 1 차원 배열 은 순서 표 의 데 이 터 를 저장 합 니 다.순서 표 의 실현

const int Maxsize=100;
template <class T>
class SeqList{ 
　private: 
　　T data[MaxSize]; //           
　　int length; //        
　public: 
　　SeqList ( ) ;//          
　　SeqList ( T a[ ], int n ) ; //        
　　~SeqList( ) { } //        
　　int Length ( ) {return length;} //         
      T Get ( int i ); //     ，       i     
　　int Locate ( T x ) ; //     ，        x       
　　void Insert ( int i, T x ) ; //        i         x     
　　T Delete ( int i ) ; //         i     
　　void PrintList ( ) ; //      ，           
}; 

2.3 선형 표 의 체인 식 저장 구조 와 실현
체인 식 저장 분배 의 특징: 선형 표 의 길이 에 따라 동적 으로 저장 공간 을 신청 하여 순서 저장 에 존재 하 는 저장 공간 이 확정 하기 어 려 운 문 제 를 해결한다.체인 식 저장 구조의 실현 단일 체인 표 양 방향 링크 순환 링크 등 단일 체인 표 의 실현

template <class T>
class LinkList { 
　　public: 
　　LinkList ( ) {first=new Node<T>; first -> next= NULL ;}
　    LinkList ( T a[ ], int n ) ; 
　　~LinkList ( ) ; 
　　int Length ( ) ;
　　T Get ( int i ) ; 
　　int Locate ( T x ) ;
　　void Insert ( int i, T x ) ;
　　T Delete ( int i ) ; 
　　void PrintList ( ) ; 
　　private: 
　　 Node<T>  *first; //          ,     
}; 

머리 꽂 기

//   
template <class T>  
LinkList<T>:: LinkList(T a[ ], int n) {
    first=new Node<T>;   //     
   first->next=NULL;
   Node<T> *s;
   for (int i=0; i<n; i++){ 
          s=new Node<T>; 
          s->data=a[i];  //             
          s->next=first->next;
          first->next=s;
 }
}
//   
template <class T>  
LinkList<T>:: LinkList(T a[ ], int n) {
    Node<T> *r,*s;      //   
    first=new Node<T>;   //     
 r=first;          
    for (int i=0; i<n; i++) { 
        s=new Node<T>; 
        s->data=a[i];  //             
        r->next=s; r=s;      //         
 }
    r->next=NULL;    //       ，           
 }

2.4 순서 표 와 단일 체인 표 의 비교
1. 순서 표 는 벡터 에 의 해 이 루어 집 니 다. 이것 은 랜 덤 액세스 구조 로 표 의 모든 노드 를 O (1) 시간 안에 직접 액세스 할 수 있 습 니 다. 그리고 링크 의 노드 는 처음부터 지침 을 따라 체인 을 찾 아야 얻 을 수 있 습 니 다.결론: 선형 표 의 조작 이 주로 찾 는 것 이 라면 삽입 과 삭 제 를 거의 하지 않 을 때 순서 표 로 저장 구 조 를 하 는 것 이 좋다.57348. 링크 의 모든 위치 에 삽입 하고 삭제 하려 면 지침 만 수정 해 야 합 니 다.한편, 순서 표 에 삽입 하고 삭제 하려 면 표 의 절반 에 가 까 운 결점 을 이동 해 야 한다. 특히 각 결점 의 정 보 량 이 많 을 때 결점 을 이동 하 는 시간 비용 은 상당 하 다.결론: 따라서 빈번하게 삽입 하고 삭제 하 는 선형 표 에 대해 체인 표를 사용 하여 저장 구 조 를 하 는 것 이 좋다.
2.5 선형 표 의 기타 저장 방법
1. 순환 링크

template <class T>
class CycleLinkList{
  public:
    CycleLinkList( ); 
    CycleLinkList(T a[ ], int n);  
    CycleLinkList(T a[ ], int n,int i);
    ~CycleLinkList();           
    int Length();        
    T Get(int i);          
     void Insert(int i, T x);
    T Delete(int i);        
    void PrintList( );    
 private:
   Node<T> *first;  
};

2. 더 블 링크

template <class T>
class DoubleLink {
private:
 Node<T> *head;
public:
 DoubleLink() ；
 ~DoubleLink();
 void Append(T data);
 void Display();
 void Insert(int locate , T data);
 T    Get(int locate);
 T  Delete(int locate);
};

3. 정적 링크

//                 ： 
＃define  Maxsize=           
template<class T>
 structNode{
       ElemType data; 
       int  next;  
}; 

간접 주소 지정 선형 표 의 순서 저장 장점: 무 작위 접근 지원.선형 표 의 체인 저장 장점: 데 이 터 를 삽입 하고 삭제 할 때 데 이 터 를 이동 할 필요 가 없습니다.간접 주소 지정: 포인터 와 배열 을 결합 시 키 는 방법 으로 배열 에 저 장 된 데이터 요 소 를 저장 하 는 단원 을 이 요 소 를 가리 키 는 지침 으로 바 꿉 니 다.