단일 체인 테이블 및 그 기본 조작 (C 언어 구현)

단일 체인 표 는 기본 적 인 선형 데이터 구조 로 그 구 조 는 데이터 도 메 인과 포인터 도 메 인 두 부분 으로 나 뉘 는데 데이터 도 메 인 은 데 이 터 를 저장 하 는 데 사용 되 고 하나의 정형, 하나의 배열, 하나의 구조 체 등 이 될 수 있다. 포인터 도 메 인 은 하나의 지침 을 저장 하 는 데 사용 되 고 다음 링크 노드 를 가리 키 며 모든 노드 는 지침 을 통 해 연락 할 수 있 으 며 물리 적 주 소 는 반드시 연속 되 지 않 는 다.단일 체인 표 노드 의 구조 체 는 다음 과 같다.

typedef struct Node
{
	DataType  data;        //   
	struct Node *next;     //        

}LNode,*PNode;

단일 체인 표 의 초기 화 를 할 때 헤드 노드 의 데이터 도 메 인 을 비 울 수도 있 고 그 안에 데 이 터 를 넣 을 수도 있다. 그러면 두 가지 서로 다른 단일 체인 표 가 있다. 두 가지 단일 체인 표 의 조작 을 바탕 으로 어느 정도 차이 가 있 고 헤드 노드 데이터 도 메 인 이 비어 있 을 때 후계 노드 나 다른 조작 을 방문 해도 헤드 포인터 의 방향 을 바 꾸 지 않 는 다.아래 의 조작 은 두절 점 데이터 영역 이 비어 있 지 않 은 단일 체인 표를 바탕 으로 진행 된다.

PNode LinkList;                                  //     

void Init_List(PNode *PHead)                     //     PHead         
{
	assert(PHead);
	*PHead = NULL;                           //     

}

PNode Set_Node(DataType data)                      //    
{
	PNode Node = (PNode)malloc(sizeof(LNode));
	if (NULL == Node)
	{
		perror("out of memory");
		return NULL;
	}
	else
	{
		Node->data = data;
		Node->next = NULL;
	}
	return Node;                                 //      
 
}

void Push_Back(PNode *PHead,DataType data)          //  ，       
{
	assert(NULL != PHead);
	if (*PHead == NULL)
	{
		*PHead=Set_Node(data);                //       
	}
	else
	{
		PNode TmpNode = *PHead;
		while (TmpNode->next != NULL)
		{
			TmpNode = TmpNode->next;       //        
		}
		TmpNode->next = Set_Node(data);     
	}
}

void Pop_Back(PNode *PHead)                                          //  
{
	PNode TmpNode = NULL;
	PNode PreNode = NULL;
	assert(NULL != PHead);
	if (NULL == *PHead)
	{
		return;
	}
	TmpNode = *PHead;
	PreNode = *PHead;

	while (TmpNode->next != NULL)
	{
		PreNode = TmpNode;
		TmpNode = TmpNode->next;                        //        
	}
	PreNode->next = NULL;
	free(TmpNode);
	
}

void Push_Front(PNode* pHead, DataType data)                       //  
{
	assert(pHead);
	if (NULL == *pHead)
	{
		*pHead = Set_Node(data);
	}
	else 
	{
		PNode TmpNode = *pHead;
		*pHead = Set_Node(data);
		(*pHead)->next = TmpNode;
	}
}

void Pop_Front(PNode* pHead)                                    //  
{
	assert(pHead);
	if (*pHead == NULL)
	{
		return;
	}
	else
	{
		PNode TmpNode = *pHead;
		*pHead = (*pHead)->next;
		free(TmpNode);
	}
}

void Print_List(PNode Head)                                         //       
{
	PNode TmpNode = NULL;
	assert(NULL != Head);
	TmpNode = Head;
	while (TmpNode != NULL)
	{
		printf("%d->", TmpNode->data);
		TmpNode = TmpNode->next;
	}
	printf("NULL");
	printf("
");
}

PNode Find(PNode pHead, DataType data)                           //      data     
{
	PNode TmpNode = NULL;
	assert(pHead);
	TmpNode = pHead;
	while (TmpNode->data != data)
	{
		if (TmpNode->next != NULL)
		{
			TmpNode = TmpNode->next;
		}
		else
		{
			return NULL;
		}
	}
	return TmpNode;
}

void Insert(PNode* pHead, PNode pos, DataType data)                 //    （pos）    
{
	PNode TmpNode = NULL;
	PNode PreNode = NULL;
	assert(pHead);
	if (*pHead == NULL)
	{
		return;
	}
	TmpNode = *pHead;
	if (TmpNode == pos)
	{
		Push_Front(&(*pHead), data);                      //    
		return;
	}
	while (TmpNode->next != pos)
	 {
		if (TmpNode->next != NULL)
		{		
		       TmpNode = TmpNode->next;
		       PreNode = TmpNode->next;
		}
			else
		{
			return;                                //pos       
		}
	}
	TmpNode->next = Set_Node(data);
	TmpNode->next->next= PreNode;
}

void Erase(PNode* pHead, PNode pos)                         //      (pos)  
{
	PNode TmpNode = NULL;
	PNode PreNode = NULL;
	assert(pHead);
	if (*pHead == NULL)
	{
		return;
	}
	TmpNode = *pHead;
	if (*pHead == pos)                                     //pos    
	{
		*pHead = NULL;
		free(TmpNode);
		return;
	}
	PreNode = TmpNode->next;
	while (TmpNode->next!= pos)
	{
		if (TmpNode->next != NULL)
		{
			
			TmpNode = TmpNode->next;
			PreNode = TmpNode->next;
		}
		else
		{
			return;                              //pos       
		}
	}
	TmpNode->next = PreNode->next;
	free(PreNode);

}

void RemoveAll(PNode* pHead, DataType data)     //      data   
{
	assert(pHead);
	if (*pHead == NULL)
	{
		return;
	}
	while (Find(*pHead ,data)!=NULL)
	{
		Remove(&(*pHead), data);
	}

}

void Remove(PNode *Phead, DataType data)            //    data    
{
	assert(Phead);
	if (*Phead == NULL)
	{
		return;
	}
	Erase(&(*Phead), Find(*Phead, data));          //    

}


void RemoveAll(PNode* pHead, DataType data)     //        data   
{
	assert(pHead);
	if (*pHead == NULL)
	{
		return;
	}
	while (Find(*pHead ,data)!=NULL)
	{
		Remove(&(*pHead), data);              //    
	}
}

int Length(PNode PHead)                                         //     
{
	int count = 0;
	PNode pCurNode = PHead;
	if (PHead == NULL)
	{
		return 0;
	}
	while (pCurNode != NULL)
	{
		count++;
		pCurNode = pCurNode->next;
	}
	return count;
}