[데이터 구조] 단 방향 링크

링크 는 매우 중요 한 데이터 구조 로 메모리 에 연속 적 으로 저장 할 필요 가 없 는 일련의 구조 로 구성 된다.본 고 는 단 방향 링크 의 기본 적 인 조작 을 토론 하고 링크 의 생 성, 끝 에 요 소 를 추가 하고 지 정 된 위치 에 요 소 를 삽입 하 며 지 정 된 단일 요소 노드 를 삭제 하고 지 정 된 요소 의 모든 노드 를 삭제 하 며 지 정 된 위치 노드, 순 서 를 삭제 하고 역순 인쇄 노드 와 통계 노드 의 갯 수 등 기초 작업 과 관련된다.
불 연속 메모리 공간 인 만큼 각 요 소 를 방문 하려 면 지침 을 통 해 찾 아야 합 니 다.링크 구조 에 서 는 데이터 필드 와 포인터 필드 를 정의 해 야 합 니 다.
1. 단 방향 링크 의 데이터 구조

typedef struct _Node
{
	int value;
	struct _Node *pnext;
}Node;

2. 헤더 가 없 는 단 방향 링크 만 들 기

void createList(Node **ppListNode, int value)
{
	Node *pListNode = NULL;
	pListNode = (Node *)malloc(sizeof(Node));
	assert(pListNode != NULL);

	pListNode->value = value;
	pListNode->pnext = NULL;

	*ppListNode = pListNode;

	return;
}

3. 링크 끝 에 요소 추가
이상 상황: 링크 가 존재 하지 않 습 니 다.

void addToTail(Node **ppListNode, int value)
{
	Node *pNew = (Node *)malloc(sizeof(Node));
	pNew->value = value;
	pNew->pnext = NULL;

	if (NULL == *ppListNode)  //    ，         ，    
	{
		*ppListNode = pNew;
		return;
	}
	else
	{
		Node *pNode = *ppListNode;
		
		while (pNode->pnext != NULL)
			pNode = pNode->pnext;

		pNode->pnext = pNew;
	}
	return;
}

4. 지정 한 위치 에 요소 삽입
이상 상황:
1) 링크 가 비어 있 음
2) 삽입 위치 0
3) 삽입 위치 가 링크 길이 보다 크다

/*   pos         value*/
void insertNode(Node **ppListNode, int pos, int value)
{
	if ((NULL == ppListNode) || (pos < 0))
		return;
	if (NULL == *ppListNode)        //    ，       
		createList(ppListNode, value);

	Node *pNode, *pNew;
	pNode = *ppListNode;

	pNew = (Node *)malloc(sizeof(Node));
	pNew->value = value;
	pNew->pnext = NULL;

	/*   0   ，         */
	if (0 == pos)
	{
		pNew->pnext = pNode;
		*ppListNode = pNew;

		return;
	}

	/*   pos         pNode*/
	while (--pos)
	{
		pNode = pNode->pnext;
		if (NULL == pNode)
			return;       //          ，    
	}

	pNew->pnext = pNode->pnext;
	pNode->pnext = pNew;

	return;
}

5. 단일 지정 요소 삭제
이상 상황:
1) 링크 가 비어 있 음
2) 삭제 할 요 소 를 헤드 노드 요소 로 한다.
3) 요소 가 링크 에 존재 하지 않 음
지적 해 야 할 것 은 단 방향 링크 에 대해 특정한 노드 를 삭제 할 때 가장 편리 한 방법 은 이 노드 의 앞 노드 를 먼저 찾 는 것 이다. 그러면 이상 한 상황 이 있다. 즉, 앞의 노드 는 링크 의 끝 노드 이 고 링크 는 지정 되 지 않 은 삭제 노드 만 있다 는 것 이다.

/*        */
void deleteValue(Node **ppListNode, int value)
{
	Node *pNode;
	if ((NULL == ppListNode) || (NULL == *ppListNode))
		return;

	if ((*ppListNode)->value == value)     //      
	{
		pNode = *ppListNode;
		*ppListNode = pNode->pnext;
		free(pNode);

		return;
	}

	pNode = *ppListNode;
	/*             ，     while   */
	if (NULL == pNode->pnext)
		return;        
	
	/*           pNode*/
	while (pNode->pnext->value != value)
	{
		pNode = pNode->pnext;
		if (NULL == pNode->pnext)
			return;        //   ，    
	}

	Node *pDel = pNode->pnext;     //pNode           
	pNode->pnext = pDel->pnext;
	free(pDel);

	return;
}

6. 링크 의 모든 지정 요소 삭제
위의 5 는 링크 에 나타 난 첫 번 째 지정 요소 노드 만 삭제 할 뿐 링크 에 있 는 모든 지정 요소 노드 를 추가 로 삭제 하고 프로그램 은 그다지 수정 되 지 않 았 습 니 다.1 차 삭제 요 소 는 5 시 에 열 거 된 이상 상황 을 다시 고려 해 야 하기 때문에 재 귀적 으로 처리 합 니 다. 그 종료 조건 은 링크 가 비어 있 거나 링크 가 끝 나 는 것 입 니 다.

/*             */
void deleteAllValue(Node **ppListNode, int value)
{
	Node *pNode;
	if ((NULL == ppListNode) || (NULL == *ppListNode))
		return;

	if ((*ppListNode)->value == value)     //      
	{
		pNode = *ppListNode;
		*ppListNode = pNode->pnext;
		free(pNode);

		return deleteAllValue(ppListNode, value);
	}

	pNode = *ppListNode;      
	/*             ，     while   */
	if (NULL == pNode->pnext)
		return;

	/*           pNode*/
	while (pNode->pnext->value != value)
	{
		pNode = pNode->pnext;
		if (NULL == pNode->pnext)
			return;        //   ，    
	}
	
	Node *pDel = pNode->pnext;     //pNode           
	pNode->pnext = pDel->pnext;
	free(pDel);

	return deleteAllValue(ppListNode, value);
}

다음 테스트 상황 통과:
1) 링크 가 비어 있 음
2) 링크 는 하나의 노드 만 있 고 이 노드 는 삭제 대상 노드 와 비 삭제 노드 이다.
3) 링크 에 지정 한 요소 없 음
4) 링크 의 모든 노드 는 삭제 요소 노드 를 지정 합 니 다.
7. 지정 한 위치의 노드 삭제
이상 상황:
1) 링크 가 비어 있 음
2) 삭제 위 치 는 헤드 노드 위치
3) 삭제 위치 가 링크 길이 보다 크다 (링크 끝 노드 뒤에 있 는 노드 포함)

/*      pos   */
void deleteNode(Node **ppListNode, int pos)
{
	if ((NULL == ppListNode) || (NULL == *ppListNode) || (pos < 0))
		return;

	Node *pNode = *ppListNode;
	if (0 == pos)         //     
	{
		*ppListNode = pNode->pnext;
		free(pNode);
		
		return;
	}

	/*   pos-1     */
	while (--pos)
	{
		pNode = pNode->pnext;
		if (NULL == pNode)
			return;    //          
	}

	Node *pDel = pNode->pnext;
	if (NULL == pDel)    //                 
		return;

	pNode->pnext = pDel->pnext;
	free(pDel);

	return;
}

8. 순서 인쇄 링크

/*      */
void printNode(Node *pListNode)
{
	if (pListNode)
	{
		printf("%d
", pListNode->value);
		printNode(pListNode->pnext);
	}
}

9. 역순 인쇄 링크

/*      */
void printNodeReverse(Node *pListNode)
{
	if (pListNode)
	{
		printNodeReverse(pListNode->pnext);
		printf("%d
", pListNode->value);
	}
}

10. 링크 노드 개 수 를 되 돌려 줍 니 다.

int countNode(Node *pListNode)
{
	/*if (NULL == pListNode)
		return 0;

	return 1 + countNode(pListNode->pnext);*/

	int count = 0;
	while (pListNode)
	{
		pListNode = pListNode->pnext;
		++count;
	}

	return count;
}

마지막 으로 몇 마디 수 다 를 떨 었 다. 실제 응용 할 때 당신 이 따로 링크 를 쓸 필요 가 없다. 다른 사람 이 바퀴 (STL, Linux 및 기타) 를 만 들 었 다. 우 리 는 사용 만 하면 된다. 가장 전형 적 인 바퀴 는 당연히 Linux 커 널 소스 코드 에서 링크 의 수량 구조 로 간단 하면 서도 간단 하지 않다.그러나 우 리 는 이 바퀴 가 어떻게 돌아 가 는 지 알 아야 만 이 바퀴 들 을 더욱 잘 다 룰 수 있다.