[데이터 구조] 헤드 없 는 단 방향 비 순환 링크 의 실현
4748 단어 데이터 구조의 시 뮬 레이 션 실현
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;
}