[데이터 구조] 헤드 없 는 단 방향 비 순환 링크 의 실현

헤드 없 는 단 방향 비 순환 링크 의 특징: 앞장 서지 않 고 next 포인터 만 있 으 며 순환 하지 않 습 니 다.
SList.h
#ifndef __SLIST_H__
#define __SLIST_H__

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
//    
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType _data;
	struct SListNode* _next;
}SListNode;

typedef struct SList
{
	SListNode* _head;
}SList;

void SListInit(SList* plist);//     
void SListDestory(SList* plist);//    
SListNode* BuySListNode(SLTDataType x);//    
void SListPushFront(SList* plist, SLTDataType x);//  
void SListPopFront(SList* plist);//  
SListNode* SListFind(SList* plist, SLTDataType x);//     
void SListInsertAfter(SListNode* pos, SLTDataType x);//  pos        
void SListInsertFront(SListNode* pos, SLTDataType x);//  pos        
void SListEraseAfter(SListNode* pos);//  pos    
void SListErase(SListNode* pos);//  pos    
void SListRemove(SList* plist, SLTDataType x);//    x
void SListPrint(SList* plist);//  
void TestSList();//    
#endif//__SLIST_H__

SList.c
#include "SList.h"

void SListInit(SList* plist)
{
	assert(plist);
	plist->_head = NULL;
}

void SListDestory(SList* plist)
{
	assert(plist);
	SListNode* cur = plist->_head;
	while (cur)
	{
		SListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	plist->_head = NULL;
}

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode =(SListNode*) malloc(sizeof(SListNode));
	newnode->_data = x;
	newnode->_next = NULL;
	return newnode;
}

void SListPushFront(SList* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist->_head;
	SListNode* newnode = BuySListNode(x);
		newnode->_next = cur;
		plist->_head = newnode;
}

void SListPopFront(SList* plist)
{
	assert(plist);
	SListNode* next = plist->_head->_next;
	free(plist->_head);
	plist->_head = next;
}

SListNode* SListFind(SList* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist->_head;
	while (cur)
	{
		if (cur->_data == x)   return cur;
	    cur = cur->_next;
	}
	return NULL;
}

//  pos        
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* next = pos->_next;
	SListNode* newnode = BuySListNode(x);
	newnode->_next = next;
	pos->_next = newnode;
}

//  pos        
void SListInsertFront(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->_next = pos->_next;
	pos->_next = newnode;
	newnode->_data = pos->_data;
	pos->_data = x;
}

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->_next->_next;
	if (pos->_next == NULL)  return;
	free(pos->_next);
	pos->_next = next ;	
}

void SListErase(SListNode* pos)
{
	assert(pos);
	SLTDataType n = pos->_next->_data;
	SListNode* next = pos->_next->_next;
	free(pos->_next);
	pos->_next = next;
	pos->_data = n;
}

void SListRemove(SList* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist->_head;
	/*if (cur->_data == x)
	{
		free(plist->_head);
		plist->_head = cur->_next;
		return;
	}*/
	SListNode* prev = NULL;
	while (cur)
	{
		SListNode* next = cur->_next;
		if (cur->_data == x)
		{
			if (cur == plist->_head)
				plist->_head = next;
			else
			{
				prev->_next = next;
				free(cur);
				cur = NULL;
			}
			break;
		}
			prev = cur;
			cur = next;
	}
}

void SListPrint(SList* plist)
{
	SListNode* cur = plist->_head;
	while (cur)
	{
		printf("%d  ", cur->_data);
		cur = cur->_next;
	}
	printf("
"); } void TestSList() { SList s1; SListInit(&s1); SListPushFront(&s1, 1); SListPushFront(&s1, 2); SListPushFront(&s1, 3); SListPushFront(&s1, 4); printf(" : "); SListPrint(&s1); printf(" : "); SListPopFront(&s1); SListPrint(&s1); printf(" 2 4 : "); SListNode* n=SListFind(&s1, 2); if (n == NULL) printf(" ! :
"); else SListInsertFront(n, 4); SListPrint(&s1); printf(" 2 4 : "); n = SListFind(&s1, 2); if (n == NULL) printf(" ! :
"); else SListInsertAfter(n, 4); SListPrint(&s1); printf(" 2 ; "); SListErase(n); SListPrint(&s1); printf(" 2 ; "); SListEraseAfter(n); SListPrint(&s1); printf(" 3 ; "); SListRemove(&s1, 3); SListPrint(&s1); SListDestory(&s1); }

Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

int main()
{
	TestSList();
	system("pause");
	return 0;
}

좋은 웹페이지 즐겨찾기