선형 구조 - 링크

6147 단어
데이터 구조 가 무엇 입 니까?
데이터 구 조 는 데이터 대상 과 이 대상 에 존재 하 는 인 스 턴 스 와 인 스 턴 스 를 구성 하 는 데이터 요소 간 의 각종 관계 이다.
데이터 구 조 는 ADT (추상 데이터 형식 Abstract Data Type) 의 물리 적 실현 이다.
데이터 구조 (data structure) 는 컴퓨터 에 데 이 터 를 저장 하고 조직 하 는 방식 이다.일반적으로 정 성 스 럽 게 선택 한 데이터 구 조 는 가장 효율 적 인 알고리즘 을 가 져 올 수 있다.
  • 문제 해결 방법의 효율 은 데이터 의 조직 방식 과 관련 이 있다
  • 문제 해결 방법의 효율 은 공간의 이용 효율 과 관련 이 있다
  • 문제 해결 방법의 효율 은 알고리즘 의 교묘 한 정도 와 관계 가 있다
  • 데이터 대상 이 컴퓨터 에서 의 조직 방식
  • 논리 구조
  • 물리 적 저장 구조
  • 추상 데이터 형식 (추상 데이터 유형)
  • 데이터 형식
  • 데이터 대상 집합
  • 데이터 집합 과 관련 된 조작 집합

  • 추상: 데이터 형식 을 묘사 하 는 방법 은 구체 적 인 실현 에 의존 하지 않 는 다. 데 이 터 를 저장 하 는 기계 와 상 관 없 이 데이터 저장 의 물리 구조 와 상 관 없 이 조작 을 실현 하 는 알고리즘 과 프로 그래 밍 언어 와 상 관 없 이 데이터 대상 집합 과 관련 조작 집합 만 묘사 하고 '어떻게 하 느 냐' 는 문제 와 관련 되 지 않 는 다.
    알고리즘 이란 무엇 인가
  • 알고리즘
  • 제 한 된 명령 집합
  • 일부 입력 수신 (유한 한 경우 입력 하지 않 음)
  • 출력 발생
  • 유한 절차 후에 반드시 종료
  • 모든 명령 은 반드시 명확 한 목표 가 있어 야 하 며 나 쁜 뜻 이 있어 서 는 안 된다.컴퓨터 가 처리 할 수 있 는 범위 내;설명 은 그 어떠한 컴퓨터 언어 와 구체 적 인 실현 수단 에 의존 하지 않 아야 한다
  • .
    무엇이 좋 은 알고리즘 입 니까?
  • 공간 복잡 도 S (n) - 알고리즘 에 따라 작 성 된 프로그램 이 실 행 될 때 저장 장치 의 길 이 를 차지 합 니 다.이 길 이 는 종종 입력 데이터 의 규모 와 관계 가 있다.공간 복잡 도가 높 은 알고리즘 은 사용 하 는 메모리 제한 을 초과 하여 프로그램 이 비정상적 으로 중 단 될 수 있 습 니 다.
  • 시간 복잡 도 T (n) - 알고리즘 에 따라 작 성 된 프로그램 이 실 행 될 때 시간 을 소모 하 는 길이 입 니 다.이 길 이 는 종종 입력 데이터 의 규모 와 관계 가 있다.시간 복잡 도가 높 은 저 효과 알고리즘 은 우리 가 살 아 있 는 동안 운행 결 과 를 기다 리 지 못 하 게 할 수도 있다.
  • 복잡 도의 선형 표현법
  • T (n) = O (f (n) 는 상수 C > 0, n0 > 0 이 존재 하여 n > = n0 이 있 을 때 T (n) < = C · f (n) 가 있 음 을 나타 낸다.
    T (n) = Ω (g (n) 는 상수 C > 0, n0 > 0 이 존재 하여 n > = n0 이 있 을 때 T (n) > = C · g (n) 이 있 음 을 나타 낸다.
    T(n) = Θ(h (n) 는 T (n) = O (h (n)) 와 T (n) = Ω (h (n) 가 동시에 있 음 을 나타 낸다.
    응용 실례
  • 최대 하위 열과
  • 구하 기
    //   N      { A1, A2, …, AN},        
    /**************************
     *	   :            *
     *     :           *
    **************************/
    int MaxSubseqSum1(int A[], int N)
    {
    	int ThisSum, MaxSum;
    	int i, j, k;
    	// i       
    	for (int i = 0; i < N; i++)
    	{
    		// j       
    		for (int j = i; j < N; j++) {
    			ThisSum = 0;    //    A[i]  A[j]    
    			for (int k = i; k <= j; k++)
    				ThisSum += A[k];
    			if (ThisSum > MaxSum)    //            
    				MaxSum = ThisSum;    //      
    		}
    	}
    	return MaxSum;
    }
    
    //    
    int MaxSubseqSum(int A[], int N)
    {
    	int ThisSum, MaxSum;
    	int i, j, k;
    	// i       
    	for (int i = 0; i < N; i++)
    	{
    		ThisSum = 0;    //    A[i]  A[j]    
    		// j       
    		for (int j = i; j < N; j++) {
    			
    			ThisSum += A[j];   //      i    j  j-1         
    			if (ThisSum > MaxSum)    //            
    				MaxSum = ThisSum;    //      
    		}
    	}
    	return MaxSum;
    }
    

    선형 구조
    선형 표 란 무엇 인가
  • 선형 표 (Linear List) 는 같은 유형의 요소 가 질서 있 는 서열 을 구성 하 는 선형 구조
  • 이다.
  • 표 의 원소 개 수 를 선형 표 의 길이
  • 라 고 한다.
  • 선형 표 에 요소 가 없 을 때 빈 표
  • 라 고 부른다.
  • 표 의 시작 위 치 를 표 두 라 고 하고 표 의 끝 위 치 를 표 미
  • 라 고 한다.
    선형 표 의 순서 저장 실현
  • 선형 저장 소
  • //        
    typedef struct LNode *List;
    typedef int Position;
    typedef int ElementType;
    
    //                       
    struct LNode {
    	ElementType Data[MAXSIZE];
    	int Last;
    };
    
    struct LNode L;
    
    //        
    List MakeEmpty()
    {
    	List Ptrl;
    	Ptrl = (List)malloc(sizeof(struct LNode));
    	Ptrl->Last = -1;
    	return Ptrl;
     }
    
    //   
    #define ERROR -1
    
    Position find(int i, ElementType X)
    {
    	Position i = 0;
    	while (i < L.Last && L.Data[i] != X)
    	{
    		i++;
    	}
    	if (i > L.Last) return ERROR;
    	else  return i;    //       
    	
    }
    
    //   
    bool Insert(List L, ElementType X, Position P)
    {
    	//         
    	if (P = MAXSIZE - 1)
    	{
    		printf("    
    "); return false; } // if (P > L->Last || P < 0) { printf("
    "); return false; } for (int i = L->Last; i >= P; i--) { // p L->Data[i + 1] = L->Data[i]; } L->Data[P] = X; // L->Last++; return true; } // bool Delete(List L, ElementType X, Position P) { // // if (P > L->Last || P < 0) { printf("
    "); return false; } // P for (int i = P+1; i <= L->Last; i++) { L->Data[i-1] = L->Data[i]; } // - 1; L->Last--; return true; }
  • 체인 저장 소
  • /*******************
    *				   *
    *              *
    *				   *
    ********************/
    
    
    //                    
    //                   
    
    //        
    //typedef struct LNode* ptrToLNode;
    typedef int ElementType;
    
    //                       
    struct LNode {
    	ElementType Data;   //        
    	LNode* Next;        //           
    };
    
    typedef LNode* Position;
    typedef LNode* List;
    
    #define ERROR NULL
    
    //    
    int Length(List Ptr)
    {
    	int j = 0;
    	while (Ptr)
    	{
    		Ptr = Ptr->Next;
    		j++;
    	}
    	return j;
    }
    
    //   
    Position Find(List L, ElementType X)
    {
    	Position p = L;    // P  L      
    	while (p && p->Data != X)
    		p = p->Next;
    	if (p)
    		return p;
    	else
    		return ERROR;
    }
    
    //   
    bool Insert(List L, ElementType X, Position p)
    {
    	Position tem, pre;
    	//   p      
    	for (pre = L; pre && pre->Next != p; pre = pre->Next);
    	
    	//     
    	if (pre = NULL)
    	{
    		printf("       
    "); return false; } else { tem = (Position)malloc(sizeof(struct LNode)); tem->Data = X; tem->Next = p; pre->Next = tem; return true; } } // bool Delete(List L, Position p) { Position tmp, pre; for (pre = NULL; pre && pre->Next != p; pre = pre->Next); if (pre == NULL || p == NULL) // p L { printf("
    "); return false; } else { // p // p pre->Next = p->Next; free(p); return true; } }

    광의 표
  • 광의 표 는 체인 표 의 홍보
  • 선형 표 에 있어 n 개의 요 소 는 모두 기본 적 인 단일 요소
  • 이다.
  • 광의 표 에서 이런 요 소 는 단일 요소 일 뿐만 아니 라 다른 광의 표
  • 일 수도 있다.
    다 중 링크
  • 다 중 링크: 링크 의 노드 는 여러 개의 연결 에 속 할 수 있다
  • .
    다 중 링크 중의 노드 의 포인터 도 메 인 은 여러 개 있 지만 두 개의 포인터 도 메 인 을 포함 하 는 링크 는 반드시 다 중 링크 가 아 닙 니 다. 예 를 들 어 쌍 선 링크 등 입 니 다.
  • 용도
  • 예 를 들 어 나무, 그림 과 같은 상대 적 으로 복잡 한 데이터 구 조 는 모두 다 중 링크 방식 으로 저장 할 수 있다.

    좋은 웹페이지 즐겨찾기