데이터 구조 복습 (2) 선형 표 (1) 순서 표

2814 단어 데이터 구조
0. 선형 표
0.1 선형 표 정의
같은 데이터 형식 을 가 진 n 개의 데이터 요소 의 유한 한 서열 은 일반적으로 L (a1, a2, a3... an) 주의 점 을 나타 낸다.
  • 저장 데이터 형식 이 모두 같다
  • 유한 합 니 다
  • 은 하나의 서열 이다. 즉, 저 장 된 내용 은 순서 가 있다
  • .
    0.2 선구자 와 후계
    첫 번 째 요소 (표 두 요소) 를 제외 하고 모든 요 소 는 하나의 전구 만 있다.마지막 요소 (표 꼬리 요소) 를 제외 하고 모든 요소 가 있 고 하나의 후계 만 있 습 니 다.
    0.3 선형 표 의 특징
    ① 표 에서 요소 의 개 수 는 유한 한 ② 표 에서 요 소 는 선후 순서 가 있 고 논리 적 인 순서 성 을 가 진 ③ 표 에서 요 소 는 모두 데이터 요소 (단독) ④ 표 중의 요소 데이터 유형 이 같다.
    1. 순서 표
    선형 표 는 논리 구조 유형 으로 서로 다른 물리 구 조 를 통 해 이 루어 지고 순서 표 와 링크 를 얻 을 수 있다.
    1.1 순서 표 의 정의
    주소 연속 저장 장치 로 선형 표 의 데이터 요 소 를 함께 저장 하여 논리 적 으로 인접 한 데이터 요 소 를 물리 적 위치 에서 도 인접 하 게 합 니 다.
    즉, 물리 적 순서 와 논리 적 순서 가 같다 는 것 이다.
    구체 적 실현 은 정적 분배 와 동적 분배 로 나 눌 수 있다
    2. 실현
    2.1 정의
    정적 할당: 배열 의 크기 를 미리 확인 합 니 다.
    #define MaxSize 50//    (  )
    typedef struct{
    	ElemType data [MaxSize];
    	int length;
    }SqList;
    

    동적 할당: 배열 의 크기 가 변 할 수 있 습 니 다.
    #define InitSize 100
    typedef struct{
    	ElemType *data;
    	int MaxSize,length;
    }SeqList;
    

    malloc: 메모리 공간 무료 신청: 메모리 공간 L. data = (ElemType *) data. malloc (size of (ElemType) * InitSize); / /Elemtype
    순서 표 특징:
    주요: 무 작위 방문, 첫 번 째 주소 와 요소 번 호 를 통 해 실천 O (1) 에서 지정 한 요소 의 저장 밀도 가 높 고 모든 노드 는 데이터 요소 의 논리 적 으로 인접 한 요소 의 물리 적 위치 만 저장 할 수 있 기 때문에 요 소 를 삽입 하고 죽 일 때 많은 요소 의 확장 용량 을 옮 겨 야 하기 때문에 불편 합 니 다.
    2.2 초기 화
    정적 할당
    void InitList(SqList &L){
    	for(int i =0;i

    동적 할당
    void InitList(SeqList &L){
    	L.data = (int *)malloc(InitSize*sizeof(int));
    	//       int
    	L.length = 0;
    	L.MaxSize=InitSize;
    }
    //       
    void IncreaseSize(SeqList &L,int len){
    	int *p=L.data;
    	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    	for(int i=0;i

    2.3 삽입
    O (n) 뒤에서 앞으로 삽입
    //      i        
    bool ListInsert(SqList 7L,int i,int e){
    	if(i>L.length+1 || i<1)
    		return false;
    	if(L.length>=MaxSize)
    		return false;
    	// i    i             
    	for(int j =L.length;j>=i;j--){
    		L.data[j]=L.data[j-1];
    	}
    	L.data[i-1]=e;
    	L.length++;
    	return true;
    }
    
    

    2.4 삭제
    O (n) 이전 뒤로 삭제
    //              
    bool ListDelete(SqList &L,int i,int &e){
    	if(i>L.length||i<1)
    		return false;
    	e = L.data[i-1];
    	for(int j =i-1;j

    2.5 찾기
    (1) 위치 별로 찾기
    O(1)
    ElemType SelectList(SeqList &L,int i){
    	if(i>L.length || i<0)
    		return 0;
    	return L.data[i-1];
    }
    

    (2) 값 으로 찾기
    O(n)
    //       
    int GetByValue(SeqList &L,int e){
    	for(int i=0;i

    좋은 웹페이지 즐겨찾기