| |
Today, to achieve the basic operations under the list, including the creation of a node, the first plug tail plug, first delete the tail deleted, the first pass to find an intermediate node of the list, look for the list of the penultimate x node, delete headless list of non-end node, set against the list, as follows:
#include "SLinkList.h"
#include
#include
#include
void PrintList (SListNode * pHead) // print the list from the pointer position
{
while (pHead)
{
printf ( "->% d", pHead-> data);
pHead = pHead-> next;
}
printf ( " n");
}
static SListNode * _BuyNode (DataType x) // Create a new node
{
SListNode * ret = (SListNode *) malloc (sizeof (SListNode));
ret-> next = NULL;
ret-> data = x;
if (ret)
{
return ret;
}
printf ( "Failed to create node n"); // prompt creation failed
return NULL;
}
void PushBack (SListNode * & pHead, DataType x) // end plug
{
if (pHead == NULL)
{
pHead = _BuyNode (x);
}
else
{
SListNode * tail = pHead;
while (tail-> next)
{
tail = tail-> next;
}
tail-> next = _BuyNode (x);
}
}
void PopBack (SListNode * & pHead) // End deleted
{
if (pHead == NULL)
{
return;
}
else if (pHead-> next-> next == NULL)
{
free (pHead-> next);
pHead = NULL;
}
else
{
SListNode * tail = pHead;
while (tail-> next-> next)
{
tail = tail-> next;
}
free (tail-> next);
tail-> next = NULL;
}
}
void PushFront (SListNode * & pHead, DataType x) // plug head
{
if (pHead == NULL)
{
pHead = _BuyNode (x);
}
else
{
SListNode * tmp = _BuyNode (x);
tmp-> next = pHead;
pHead = tmp;
}
}
void PopFront (SListNode * & pHead) // t delete head
{
if (pHead == NULL)
{
return;
}
else
{
SListNode * tail = pHead;
pHead = pHead-> next;
tail-> next = NULL;
free (tail);
}
}
SListNode * Find (SListNode * pHead, DataType x) // x to find the node, if there is returned to the node, if it exists return empty
{
if (pHead == NULL)
{
return NULL;
}
SListNode * tail = pHead;
while (tail)
{
if (tail-> data == x)
{
return tail;
}
tail = tail-> next;
}
return NULL;
}
void Insert (SListNode * & pos, DataType x) // given a node is inserted after the position
{
SListNode * tmp = _BuyNode (x);
if (pos == NULL)
{
pos = tmp;
}
else
{
tmp-> next = pos-> next;
pos-> next = tmp;
}
}
void Erase (SListNode * & pos) // Delete the head of the list of non-end node
{
if (pos == NULL)
{
return;
}
else if (pos-> next == NULL)
{
printf ( "The node is tail node can not be deleted n");
}
else
{
SListNode * tmp = pos-> next;
pos-> data = pos-> next-> data;
pos-> next = pos-> next-> next;
free (tmp);
tmp = NULL;
}
}
void ReveseList (SListNode * & pHead) // the list of Retrograde
{
SListNode * tail = pHead;
while (tail-> next)
{
SListNode * tmp = NULL;
tmp = tail-> next;
tail-> next = tail-> next-> next;
tmp-> next = pHead;
pHead = tmp;
}
}
SListNode * FindminList (SListNode * pHead) // iteration of the loop to find the list of intermediate nodes
{
assert (pHead);
SListNode * quick = pHead;
SListNode * slow = pHead;
while (quick)
{
slow = slow-> next;
if (quick-> next)
quick = quick-> next-> next;
else
return slow;
}
return slow;
}
SListNode * FindListPosList (SListNode * pHead, int lastpos) // Find the list of the penultimate node lastpos
{
SListNode * quick = pHead;
SListNode * slow = pHead;
while (quick && lastpos--)
{
quick = quick-> next;
}
if (quick == NULL)
{
return slow;
}
while (quick)
{
quick = quick-> next;
slow = slow-> next;
}
return slow;
}
Test case as follows:
1234567891011121314151617181920212223242526272829303132333435363738
3940414243444546474849505152535455565758596061626364656667686970717
2737475767778798081828384858687888990919293949596979899100101102103
104105 #include
#include
#include "SLinkList.h"
void Test1 () // PushBack, PrintList, PopBack
{
SListNode * pHead = NULL;
PushBack (pHead, 1);
PushBack (pHead, 2);
PushBack (pHead, 3);
PushBack (pHead, 4);
PushBack (pHead, 5);
PrintList (pHead);
PopBack (pHead);
PopBack (pHead);
PrintList (pHead);
PopBack (pHead);
PopBack (pHead);
PopBack (pHead);
PrintList (pHead);
}
void Test2 () // PushFront, Popfront
{
SListNode * pHead = NULL;
PushFront (pHead, 5);
PushFront (pHead, 4);
PushFront (pHead, 3);
PushFront (pHead, 2);
PushFront (pHead, 1);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
PopFront (pHead);
PrintList (pHead);
}
void Test3 () // Find, Insert
{
SListNode * pHead = NULL;
PushFront (pHead, 5);
PushFront (pHead, 4);
PushFront (pHead, 3);
PushFront (pHead, 2);
PushFront (pHead, 1);
Insert (pHead, 0);
pHead = Find (pHead, 3);
PrintList (pHead);
Insert (pHead, 4);
PrintList (pHead);
}
void Test4 () // Erase
{
SListNode * pHead = NULL;
SListNode * tmp = NULL;
PushFront (pHead, 5);
PushFront (pHead, 4);
PushFront (pHead, 3);
PushFront (pHead, 2);
PushFront (pHead, 1);
tmp = Find (pHead, 5);
Erase (tmp);
PrintList (pHead);
}
void Test5 () // ReveseList
{
SListNode * pHead = NULL;
PushBack (pHead, 1);
PushBack (pHead, 2);
PushBack (pHead, 3);
PushBack (pHead, 4);
PushBack (pHead, 5);
ReveseList (pHead);
PrintList (pHead);
}
void Test6 () // FindLastposList
{
SListNode * pHead = NULL;
SListNode * ret = NULL;
PushBack (pHead, 1);
PushBack (pHead, 2);
PushBack (pHead, 3);
PushBack (pHead, 4);
PushBack (pHead, 5);
ret = FindListPosList (pHead, 2);
printf ( "% d n", ret-> data);
ret = FindListPosList (pHead, 6);
printf ( "% d n", ret-> data);
}
int main ()
{
Test1 ();
Test2 ();
Test3 ();
Test4 ();
Test5 ();
Test6 ();
system ( "pause");
return 0;
} |
|
|
|