데이터 구조 모델 - 단일 체인 표 실현 방식 총화

데이터 구조 모델 - 단일 체인 표 실현 방식 총화
앞에서 우 리 는 네 가지 방식 으로 실 현 된 싱글 체인 시 계 를 제 공 했 습 니 다. 앞장 서 는 노드 가 없 는 노드 가 있 고 싱글 체인 표 의 구조 체 정의 도 두 가지 방식 이 있 습 니 다. 그러면 이런 실현 방식 은 도대체 어떤 차이 가 있 습 니까? 왜 이렇게 여러 가지 실현 방식 이 나 타 났 는 지 자세히 알 아 보 겠 습 니 다.
단일 링크 구조 체 의 실현 차이
우선 우리 비교 해 보 자.
서로 다른 방식 의 단일 체인 표 가 실 현 될 때 체인 표 결점 의 실현 은 똑 같 고 다른 점 은 단일 체인 표 구조 체 의 실현 에 있다.
단일 체인 표 구조 체 의 실현

typedef int ElemType;		//        

//typedef struct LinkListNode*	PLinkListNode;			//        

//        
typedef struct LinkListNode
{
	ElemType			m_data;			//    
	struct LinkListNode	*m_next;			//    
}LinkListNode;

① length 표 지 를 가 진 단일 링크 구조 체

typedef struct LinkList
{
	LinkListNode	*m_head;				//      
	int				m_length;			//             
}LinkList;

① length 표지 가 없 는 단일 링크 구조 체

//         
typedef struct LinkListNode LinkList;

//           
typedef struct LinkListNode*  LinkList;

구별
    하나의 단일 체인 시트 에 있어 그 길 이 를 찾 을 때 이동 한 후에 단일 체인 표를 한 번 훑 어 봐 야 한다. 따라서 시간 복잡 도 는 O (N) 이다. 그 길 이 를 빨리 얻 기 위해 우 리 는 length 표 지 를 가 진 단일 체인 시트 구조 체 를 디자인 했다. 이것 은 체인 시트 의 길 이 를 자주 얻 을 때 효율 이 매우 객관 적 이다.
한편, 우 리 는 같은 시간 에 length 표 지 를 가지 지 않 은 단일 체인 표 구조 체 를 발 견 했 고 정의 하 는 방식 은 작은 차이 가 나 타 났 다.이 건 또 왜 일 까?
이 차이의 근본 은 바로 앞장 서 는 결점 의 단일 체인 시계 와 앞장 서지 않 는 결점 의 단일 체인 시계의 차이 에 있다.
단일 링크 의 노드 삽입 과 삭 제 는 바로 전구 노드 의 next 포인터 필드 의 방향 을 수정 하 는 것 입 니 다. 우 리 는 C 언어 를 배 울 때 함수 에서 변수의 값 을 언제 수정 하 든 이 변수의 지침 을 매개 변수 로 전달 해 야 한 다 는 것 을 알 고 있 습 니 다. 구체 적 으로 다음 예제 프로그램 을 참조 하 십시오.

#include <stdio.h>
#include <stdlib.h>


//            
void Modify1(int value);		//       
void Modify2(int *value);		//         

int main(void)
{
	int value = 0;
	Modify1(value);
	printf("value = %d after func

", value);		// modify failed

	Modify2(&value);
	printf("value = %d after func

", value);		// modify success

	return EXIT_SUCCESS;
}


//       
void Modify1(int value)
{
	value = 10;
	printf("value = %d in %s
", value, __func__);
}

//         
void Modify2(int *value)
{
	*value = 10;
	printf("value = %d in %s
", *value, __func__);
}

그러면 단일 링크 에서 요 소 를 삭제 할 때 함수 에서 포인터 의 방향 을 수정 해 야 합 니 다 (특히 첫 번 째 원 을 삽입 할 때 포인터 의 방향 을 수정 해 야 합 니 다). 따라서 포인터 의 지침 (즉, 이중 지침) 을 사용 해 야 합 니 다.
우리 가 실현 한 코드 의 일치 성 을 확보 하기 위해 서, 우리 의 모든 매개 변수의 전달 은 LinkList * list 를 사용 하여, 매개 변수 로 함수 에 전달 합 니 다.
이렇게 length 표 지 를 가 진 단일 체인 표 구조 체 에서 지침 의 방향 을 수정 할 때 사실은 사용 한 것 은
LinkListNode
*pNode
= list->m_head;
/ / 들 어 오 는 것 은 Linlist * 이 고, 수 정 된 것 은 * list 의 LinkList Node * m 입 니 다.헤드 는 이미 이중 지침 임 을 알 수 있다.
그럼 이중 지침 으로 m 를 수정 할 수 있 습 니 다.head 가 가리 키 는 것 (우 리 는 이렇게 이해 할 수 있 습 니 다. 들 어 오 는 것 은 LinkList * list 즉 변수의 지침 입 니 다. 그러면 변수 * list 의 값 을 수정 할 수 있 고 변수 * list 는 구조 체 로 서 그의 데 이 터 는 * m head 와 m length 입 니 다. 즉, 지침 의 방향 을 수정 할 수 있 습 니 다)

#include <stdio.h>
#include <stdlib.h>


//            
typedef struct
{
	int *value;
	int length
}List;

int gloValue1 = 0;
int gloValue2 = 10;						//     

void Modify1(List list);		//       
void Modify2(List *list);		//          


int main(void)
{

	List list = {&gloValue1, 0};
	printf("&gloValue1 = %p, &gloValue = %p
", &gloValue1, &gloValue2);
	printf("value = %d, addr = %p, length = %d after func

", *(list.value), list.value, list.length);

	Modify1(list);
	printf("value = %d, addr = %p, length = %d after Modify1

", *(list.value), list.value, list.length);

	Modify2(&list);
	printf("value = %d, addr = %p, length = %d after Modify2

", *(list.value), list.value, list.length);
	return EXIT_SUCCESS;
}


//       
void Modify1(List list)
{
	list.value = &gloValue2;								//       (      )  failed
	list.length = 10;										// failed
	printf("value = %d, addr = %p, length = %d in %s
", *(list.value), list.value, list.length, __func__);
}


//       
void Modify2(List *list)
{
	list->value = &gloValue2;								//       (      ) success
	list->length = 10;										//						  success
	printf("value = %d, addr = %p, length = %d in %s
", *(list->value), list->value, list->length, __func__);
}

    그러면 이제 문 제 는 분명 합 니 다. 지침 의 방향 을 수정 하려 면 지침 에 들 어 가 는 지침 을 매개 변수 로 해 야 합 니 다. 그러면 우 리 는 삽입 삭제 과정 에서 지침 의 방향 을 수정 하 였 습 니까?
    사실은 근본적으로 두 곳 을 수정 했다. 우 리 는 앞장 서지 않 는 단일 체인 표 실현 방식 2 에 함 수 를 삽입 하 는 실현 을 참조 했다.
① 결점 자 체 를 수정 하 는 방향 으로 이중 지침 이 필요 하 다.

//               ，          
(*list) = newNode;					//                LinkListNode **
//             
typedef struct LinkListNode*  LinkList;
//    	
LinkListNode* InsertNode(LinkList *list,	// LinkList * == LinkListNode**	 
						 int position, 
						 ElemType data)

② 결점 을 수정 하 는 지침 역 의 지향 이 므 로 결점 을 가리 키 는 지침 으로 전달 하면 된다.
4. 567913. 이제 문 제 는 명확 해 졌 지만 왜 두 가지 방식 으로 정 의 된 단일 체인 표 구조 체 는 다 릅 니까?
4. 567913. 이것 이 바로 앞장 서지 않 는 단일 체인 표 와 앞장 서 는 단일 체인 표 가 지역 의 차 이 를 실현 하 는 것 이다.
둘째. 앞장 서지 않 는 단 사슬 표 와 앞장 서 는 단 사슬 표 의 차이
우 리 는 앞장 서 는 결점 의 단일 체인 시계 가 실현 되 는 것 이 앞장 서지 않 는 결점 의 단일 체인 시계 보다 간단 하 다 는 것 을 쉽게 발견 할 수 있다. 이것 은 왜 일 까?
계속 위 에서 말 한 바 와 같이 삽입 하고 삭제 할 때 전구 지침 의 방향 을 수정 해 야 합 니 다. 특히 첫 번 째 요소 (즉, 첫 번 째 원점) 를 삽입 하고 삭제 할 때 우 리 는 두 지침 의 방향 을 바 꿔 야 합 니 다. 분명 한 두 지침 은 전구 가 없습니다. 그러면 우리 가 실현 할 때
비 두 결점 에 대해 우 리 는 직접 그 앞 구 를 찾 은 다음 에 그 앞 구 결점 의 지침 역 의 방향 을 수정 하면 된다.
두 결점 에 대해 전구 결점 이 없 으 면 우 리 는 특수 한 판단 을 필요 로 하고 두 지침 자체 의 지향 을 직접 수정 해 야 한다.
이 문 제 를 어떻게 회피 합 니까? 그러면 체인 헤더 의 위치 에 머리 노드 를 추가 하고 초기 화 할 때 머리 노드 를 만 듭 니 다. 그러면 우 리 는 첫 번 째 노드 를 삽입 하 더 라 도 첫 번 째 노드 는 전구 (즉, 머리 노드 의) 가 있 습 니 다. 그러면 우 리 는 머리 지침 을 수정 하면 머리 노드 를 수정 하 는 지침 역 의 방향 이 됩 니 다.이렇게 해서 우 리 는 전송 과 삽입 삭제 의 실현 이 통일 되 었 다.실현 하기 도 간단 하 다
자, 앞장 서지 않 고 매듭 을 짓 는 다 면 우 리 는 잘 알 겠 습 니 다. 이어서 위의 그 질문 에 대답 하 겠 습 니 다. 왜 단일 체인 표 의 구조 체 가 다 릅 니까?
앞장 서서 결점 을 맺 을 때 우리 가 전달 하 는 매개 변 수 는 이중 지침 에 들 어 갈 필요 가 없다. 링크 결점 을 가리 키 는 지침 을 통일 적 으로 전달 하면 되 기 때문에 아래 의 실현 으로 하면 된다.

//  newNode  pNode   ，    newNode pNode      
newNode->m_next = pNode->m_next;	//        LinkListNode *  ,      m_next node     ,           
pNode->m_next = newNode;			//   LinkListNode *, m_next          
//     
LinkListNode *AddNode(LinkList *list,							
					  LinkListNode *prevNode,				//   LinkListNode *,     prevNode->m_next = @@@@@
					  ElemType data)

앞장 서지 않 을 때 실현 되 고 삭 제 를 삽입 할 때 지향 점 에 들 어 가 는 지침 이 필요 한 지침 입 니 다. 그러면 LinkList Node 를 List 로 하고 매개 변 수 를 입력 할 때 List * * list 가 필요 합 니 다. 그러면 우리 의 몇 가지 실현 방식 의 함수 정의 가 일치 하지 않 습 니 다. 이런 인 코딩 방식 은 우리 가 좋아 하 는 것 이 아니 기 때문에 사용 합 니 다.

//           
typedef struct LinkListNode*  LinkList;
//         
typedef struct LinkListNode LinkList;

위 에 앞장 서 는 노드 의 단일 체인 시트 도 type: def struct LinkList Node * 를 사용 할 수 있 습 니 다. LinkList;，다만 참조 할 때 List list 를 사용 하면 됩 니 다. 함수 이름 도 일치 하지 않 습 니 다. 매개 변 수 를 List * list 로 통일 하면 내부 코드 가 실 현 될 때 모두 (* list) 로 머리 결점 을 가리 키 는 지침 을 표시 하여 실현 하기 가 쉽 지 않 습 니 다. 그래서 저 희 는 typedef struct LinkList Node 를 선 택 했 습 니 다. LinkList