C 언어 데이터 구조 노트 1 | 단일 체인 시트

1. 링크 의 유래
배열 은 가장 간단 한 데이터 구조 로 링크 가 복잡 하고 이 진 트 리, 그림 은 더욱 복잡 한 데이터 구조 이다.데이터 구 조 는 간단 함 에서 복잡 함 까지 그들 이 해결 해 야 할 문제 도 간단 함 에서 복잡 함 까지 이다.복잡 한 데이터 구 조 를 배 우려 면 먼저 간단 한 데이터 구 조 를 배 워 야 한다. 간단 한 데이터 구조 가 문 제 를 해결 할 수 있다 면 복잡 한 데이터 구 조 를 사용 할 필요 가 없다.배열 의 타고 난 결함 으로 인해 어떤 문 제 를 해결 할 수 없 기 때문에 사람들 은 링크 를 발명 했다.배열 의 세 가지 특징: 하나: 배열 의 모든 요소 유형 이 같 아야 합 니 다.2. 배열 은 정 의 를 내 릴 때 배열 요소 의 개 수 를 명확 하 게 지정 해 야 합 니 다. 그리고 일반적으로 개 수 는 바 꿀 수 없습니다. (Linux 커 널 에 서 는 길 어 지 는 배열 을 사용 하고 고급 언어 인 C + 에서 도 배열 로 변 하 는 것 을 지원 합 니 다)3. 특정한 요소 의 이동 은 요소 의 대면 적 이동 을 초래 하고 효율 이 높 지 않다.이러한 특징 으로 인해 배열 은 간단 하고 사용 하기 쉬 운 장점 을 가지 게 되 었 으 나 결함 도 가 져 왔 다.그러면 어떻게 이런 결함 들 을 보완 합 니까?1. 배열 의 첫 번 째 결함 은 구조 체 에 의 해 해결 된다.구조 체 는 그 중의 원소 유형 이 다 르 도록 허용 한다.2. 배열 의 두 번 째 결함 은 두 가지 해결 방향 이 있다. 1. 길 어 지 는 배열 을 사용한다.2. 링크 를 사용 합 니 다.3. 세 번 째 결함 에 대해 링크 를 사용 하 는 것 이 가장 좋 은 해결 방법 이다.
2. 단일 체인 표 실현
단일 체인 시트 의 생 성 은 대체적으로 다음 과 같은 몇 단계 가 있 습 니 다. 1. 빈 단일 체인 시트 를 만 듭 니 다. 예 를 들 어 CreateNode () 함 수 를 정의 하여 첫 번 째 노드 를 만 들 수 있 습 니 다.2. 단일 체인 시트 (추가, 삭제, 검사, 변경, 정렬) 를 조작 합 니 다. 예 를 들 어 삽입 작업 은 하나의 InsertTail () 함 수 를 정의 하여 단일 체인 시트 (또는 노드) 의 뒤에 새로운 노드 를 추가 합 니 다.3. 단일 체인 표를 소각 합 니 다. 예 를 들 어 Destroy List () 함 수 를 정의 하여 체인 표를 소각 합 니 다.
1. 첫 번 째 노드 구축
단일 체인 표 의 노드 구성
C 언어 에서 노드 를 만 드 는 방법 은 하나의 구조 체 를 정의 하 는 것 이다.

struct node 
{
     
	int data;
	struct node* pNext;
};

4. 567917. 주의: 여 기 는 하나의 구조 체 유형 만 정 의 했 을 뿐 그 자체 에 변수의 생 성 이 없 기 때문에 메모리 (예 를 들 어 데이터 형식 int, char, float, 메모리 공간 을 차지 하지 않 습 니 다) 를 사용 하지 않 습 니 다
메모리 로 노드 만 들 기
메모 리 를 왜 사용 합 니까?링크 를 만 드 는 메모리 에는 일반적으로 다음 과 같은 특징 이 있 습 니 다. 필요 한 만큼 필요 합 니 다.마음대로 삭제 하고 풀 수 있어 야 합 니 다.위의 두 가지 특징 에 따라 우 리 는 메모리 가 링크 의 노드 로 가장 적합 하 다 는 것 을 알 수 있다.다음은 노드 함 수 를 만 드 는 의사 코드 입 니 다:

CreatNode(        )
{
     
	            ；
	           ；
	         ；
	       ；
	         NULL；
}

다음은 위조 코드 의 실현 과정 입 니 다.

//       
typedef struct node StrNode_T；
StrNode_T* CreatNode(int data)
{
     
	StrNode_T* p = (StrNode_T*)malloc(sizeof(StrNode_T));
	if (NULL == p)
	{
     
		printf("malloc     ！！！！");
		return;
	}
	memset(p, 0 ,sizeof(StrNode_T));
	p->data = data;
	p->pNext = NULL;
	return p;
}

함수 의 반환 값 은 방금 만 든 노드 의 첫 주 소 를 가리 키 는 지침 입 니 다.
체인 포인터
헤드 포인터 가 노드 가 아니 라 일반 포인터 변수 로 4 개의 바이트 를 차지한다.헤드 포인터 유형 은 struct node * 형식 이기 때문에 링크 의 노드 를 가리 킬 수 있 습 니 다.하나의 전형 적 인 체인 테이블 실현 은 헤드 포인터 가 체인 테이블 의 첫 번 째 노드 를 가리 키 고 첫 번 째 노드 중의 바늘 이 다음 노드 를 가리 키 며 순서대로 유추 하면 하나의 체인 테이블 을 구성한다.
첫 번 째 간단 한 링크 구축: 1. 정의 헤드 포인터.2. 첫 번 째 노드 를 만 들 고 첫 번 째 노드 를 가리 킵 니 다.3. 다음 에 노드 를 만 들 고 새로운 노드 의 이전 노드 의 끝 부분 을 삽입 합 니 다.4. 이런 식 으로 보면 데 이 터 를 저장 해 야 하 는 만큼 데 이 터 를 만 들 고 최종 적 으로 링크 를 형성한다.

int main(void)
{
     
	StrNode_T* pHeadNode = NULL;
	pHeadNode = CreatNode(0);
	return 0;
}

2. 단일 체인 표 는 꼬리 부분 에 노드 를 삽입 하 는 것 을 실현 한다.
주로 두 단계 가 필요 합 니 다. 1. 링크 의 마지막 노드 를 찾 습 니 다. 2. 새로운 노드 와 원래 의 마지막 노드 를 연결 합 니 다.
삽입 함수

//         
void InsertTail(StrNode_T* pHeadNode, StrNode_T* pNewNode)
{
     
	if (NULL == pHeadNode)
	{
     
		return;
	}
	//        
	StrNode_T* p = pHeadNode;
	while (NULL != p->pNext)
	{
     
		p = p->pNext;
	}
	p->pNext = pNewNode;
}

인쇄 함수

//    
void print(StrNode_T* pHeadNode)
{
     
	int i = 0;
	StrNode_T* pTemp = pHeadNode;
	if (NULL == pHeadNode)
	{
     
		return;
	}
	while (pTemp != NULL)
	{
      
		printf("node%d = %d
",i,pTemp->data);
		i++;
		pTemp = pTemp->pNext;
	}
}

주 함수

int main(void)
{
     
	StrNode_T* pHeadNode = NULL;
	pHeadNode = CreatNode(0);
	InsertTail(pHeadNode, CreatNode(1));
	InsertTail(pHeadNode, CreatNode(2));
	InsertTail(pHeadNode, CreatNode(3));
	print(pHeadNode);

	return 0;
}

우리 의 프로그램 은 여기까지 두 단계, 첫 번 째 단계, 노드 를 만 들 었 습 니 다.두 번 째 단계, 노드 삽입.매번 삽입 할 때마다 생 성 함수 로 노드 를 만 들 기 때문에 매번 malloc 로 신청 하기 때문에 우 리 는 이 신청 한 메모리 에 대해 풀 어야 합 니 다.세 번 째 단계, 링크 해제.
자유 함수

//    
void Free(StrNode_T* pHeadNode)
{
     
	if (NULL == pHeadNode)
	{
     
		return;
	}
	StrNode_T* pFree = pHeadNode;
	while (pFree->pNext != NULL)
	{
     
		pHeadNode = pFree->pNext;
		free(pFree);
		pFree = pHeadNode;
	}
	free(pHeadNode);
}

그래서 main 함 수 는:

int main(void)
{
     
	StrNode_T* pHeadNode = NULL;
	pHeadNode = CreatNode(0);
	InsertTail(pHeadNode, CreatNode(1));
	InsertTail(pHeadNode, CreatNode(2));
	InsertTail(pHeadNode, CreatNode(3));
	print(pHeadNode);
	Free(pHeadNode);
	return 0;
}

3. 단일 체인 표 는 머리 에 노드 를 삽입 하 는 것 을 실현 한다.
머리 삽입 은 두 가지 절차 가 있다. 1. 새로운 노드 의 pNext 는 원래 의 첫 번 째 노드 의 첫 번 째 주 소 를 가리킨다. 즉, 새로운 노드 는 원래 의 첫 번 째 노드 와 연결된다.2. 머리 노드 의 pNext 는 새로운 노드 의 첫 번 째 주 소 를 가리 키 는데 그것 이 바로 머리 노드 와 새로운 노드 가 연결 되 는 것 이다.의사 코드 의 실현:

insert_head()
{
     
	   ：    pNext          ；
	   ：    pNext     ；	
}

InsertHead

//   
void InsertHead(StrNode_T* pHeadNode, StrNode_T* pNewNode)
{
     
	pNewNode->pNext = pHeadNode->pNext;
	pHeadNode->pNext = pNewNode;

}

3. 단일 체인 표 의 알고리즘
1. 노드 옮 겨 다 니 기
사실은 앞에서 이미 실현 되 었 습 니 다. 예 를 들 어 링크 의 노드 데 이 터 를 인쇄 하고 링크 를 풀 때 링크 를 옮 겨 다 니 며 인쇄 하고 풀 었 습 니 다!뭐 가 옮 겨 다 니 는 거 죠?데이터 가 저장 되 어 있 으 면 반드시 찾 을 것 이다. 링크 가 데 이 터 를 저장 하 는 데 사 용 된 이상 링크 에서 데 이 터 를 읽 는 방법 이 있어 야 한다. 이 방법 은 바로 링크 를 옮 겨 다 니 는 것 이다. 즉, 링크 의 각 노드 를 하나씩 꺼 내 서 방문 하 는 것 이다.옮 겨 다 니 는 요구: 빠 뜨리 지 말고 반복 하지 말고 효율 을 최대한 높 여야 한다.
2. 단일 체인 시트 를 어떻게 옮 겨 다 니 는 지