데이터 구조 단일 체인 표 의 실현 및 관련 조작

먼저 SListNode. h 에서 우리 의 단일 체인 표 결점 구조 체 정의 와 관련 조작 함수 에 대해 설명 합 니 다.
단일 체인 표 부분 은 주로 단일 체인 표 의 데이터 의 헤드 삽입, 꼬리 삽입, 머리 삭제, 꼬리 삭제 등 을 포함한다.
SListNode.h：

#pragma once
typedef int DataType;

typedef struct SListNode
{
	struct SListNode* _next;
	DataType _data;
}SListNode;//       ，            ，          data


SListNode* BuySListNode(DataType x);//      
void SListPrint(SListNode* pHead);//     
void SListDestory(SListNode** ppHead);//     

void SListPushBack(SListNode** ppHead, DataType x);//  
void SListPopBack(SListNode** ppHead);//  
void SListPushFront(SListNode** ppHead, DataType x);//  
void SListPopFront(SListNode** ppHead);//  
SListNode* SListFind(SListNode* pHead, DataType x);//      ,      
void SListInsest(SListNode** ppHead, SListNode* pos, DataType x);// pos      
void SListErase(SListNode** ppHead, SListNode* pos);//  pos     

이 어 SListNode. c 에서 관련 조작 함 수 를 정의 하여 main 함수 에서 테스트 합 니 다.

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include"SListNode.h"

SListNode* BuySListNode(DataType x)//    
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	if (tmp != NULL)
	{
		tmp->_data = x;
		tmp->_next = NULL;
		return tmp;
	}
	printf("      ！");
	return tmp;
}

void SListPrint(SListNode* pHead)//     
{
	if (pHead == NULL)
	{
		printf("       ！
");
	}
	else
	{
		while (pHead)
		{
			printf("%d->", pHead->_data);
			pHead = pHead->_next;
		}
		printf("NULL
");
	}
}

void SListDestory(SListNode** ppHead)//       
{
	SListNode* tmp;
	if (*ppHead == NULL)
		return;
	else
	{
		while (*ppHead)
		{
			tmp = *ppHead;
			*ppHead = (*ppHead)->_next;
			free(tmp);
			tmp = NULL;
		}
	}
}
void SListPushBack(SListNode** ppHead, DataType x)//       
{
	SListNode* newNode;
	SListNode* tmp;
	newNode = BuySListNode(x);
	tmp = *ppHead;
	if (NULL == *ppHead)
	{
		*ppHead = newNode;
		(*ppHead)->_next = NULL;
	}
	else
	{
		while (tmp->_next)
		{
			tmp = tmp->_next;
		}
		tmp->_next = newNode;
		newNode->_next = NULL;
	}
}

void SListPopBack(SListNode** ppHead)//       
{
	//    
	//1.      
	//2.        
	//3.       
	SListNode* tmp;
	tmp = *ppHead;
	if (*ppHead == NULL)
	{
		printf("        ，       ！");
	}
	else if ((*ppHead)->_next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{

		while ((tmp)->_next->_next)
		{
			tmp = tmp->_next;
		}
		free(tmp->_next);
		tmp->_next = NULL;
	}
}

void SListPushFront(SListNode** ppHead, DataType x)//       
{
	SListNode* newNode;
	newNode = BuySListNode(x);
	if (*ppHead == NULL)//      
	{
		*ppHead = newNode;
		(*ppHead)->_next = NULL;
	}
	else
	{
		newNode->_next = *ppHead;
		*ppHead = newNode;
	}
}

void SListPopFront(SListNode** ppHead)//       
{
	//    
	//1.      
	//2.        
	//3.       
	SListNode* tmp;
	tmp = *ppHead;
	if (*ppHead == NULL)
	{
		printf("        ，       ！");
	}
	else if ((*ppHead)->_next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		*ppHead = (*ppHead)->_next;
		free(tmp);
		tmp = NULL;
	}

}
SListNode* SListFind(SListNode* pHead, DataType x)//          
{
	SListNode* tmp;
	tmp = pHead;
	while (tmp)
	{
		if (tmp->_data == x)
		{
			return tmp;
		}
		tmp = tmp->_next;
	}
	return tmp;
}

void SListInsest(SListNode** ppHead, SListNode* pos, DataType x)//    pos     x
{
	if (pos == NULL)
	{
		printf("       ！    ！！
");
	}
	else
	{
		SListNode* tmp;
		SListNode* newNode;
		newNode = BuySListNode(x);
		tmp = *ppHead;
		if (tmp == pos)
		{
			SListPushFront(ppHead, x);
			return;
		}
		while (tmp)
		{
			if (tmp->_next == pos)
			{
				newNode->_next = tmp->_next;
				tmp->_next = newNode;
				return;
			}
			tmp = tmp->_next;
		}
		printf("          ，    ！");
	}
}

void SListErase(SListNode** ppHead, SListNode* pos)//     pos     
{
	assert(pos);
	SListNode* tmp;
	SListNode* cur;
	tmp = *ppHead;
	while (tmp->_next == pos)
	{
		tmp = tmp->_next;
	}
	cur = tmp->_next;
	tmp->_next = tmp->_next->_next;
	free(cur);
	cur = NULL;
}

int main()
{
	SListNode* SList;
	SList = BuySListNode(1);
	SListPushBack(&SList,2);
	SListPushBack(&SList, 3);
	SListPushBack(&SList, 4);
	SListPushBack(&SList, 5);
	SListPrint(SList);
	SListPopBack(&SList);
	SListPushFront(&SList, 8);
	SListPrint(SList);
	SListInsest(&SList,SListFind(SList, 2), 9);
	SListPopFront(&SList);
	SListPrint(SList);
	SListErase(&SList, SListFind(SList, 2));
	SListPrint(SList);
	SListDestory(&SList);
	SListPrint(SList);
	system("pause");
	return 0;
}

단일 체인 시트 를 파괴 하고 삭제 할 때 모든 노드 가 메모리 에 방출 되 어야 한 다 는 것 을 주의해 야 합 니 다. 왜냐하면 체인 시트 의 이러한 노드 는 새로운 노드 를 삽입 할 때마다 메모리 공간 에서 malloc 로 신청 하기 때 문 입 니 다. 이런 공간 은 연속 되 지 않 습 니 다.
순서 표 의 연속 메모리 공간 에 비해 단일 체인 표 가 방출 될 때 하나씩 방출 해 야 합 니 다. 머리 결점 만 방출 한 다음 에 머리 지침 을 비 우 는 것 이 아니 라 머리 결점 을 방출 한 후에 직접 지침 을 비 워 서 지침 이 비어 서 후속 결점 을 찾 지 못 해 메모리 가 새 지 않도록 주의해 야 합 니 다.