C言語はシングルチェーンを実現します.
25926 ワード
/***********************************************************************************
xxx.h:
Copyright Inc.(2013), All rights reserved.
Purpose: C --
Author: MaJing
Reviser: yyy
Created Time: 2016_9
************************************************************************************/
#pragma once
#include
#include
#include
#include
typedef int DataType;
typedef struct ListNode
{
DataType _data; //
struct ListNode* _next; //
}ListNode, *PListNode;
//
// ps:PushBack/PopBack PListNode* ,
// :void PushBack (PListNode& ppList, DataType x);
//
/////////////////////////////////////////////////////////////////////////////////
//
// / /
void InitSList(PListNode* ppList);
void DestorySList(PListNode* ppList);
void PrintSList(PListNode pList);
int GetLength(PListNode pList);
// / / /
void PushBack (PListNode* ppList, DataType x);
void PopBack (PListNode* ppList);
void PushFront (PListNode* ppList, DataType x);
void PopFront (PListNode* ppList);
// / /
ListNode* Find (PListNode pList, DataType x);
int Remove (PListNode* ppList, DataType x);
void Erase (PListNode* ppList, ListNode* n);
void Insert (PListNode* ppList, ListNode* n, DataType x);
void InitSList(PListNode* ppList)
{
assert(ppList);
*ppList = 0;
}
void DestorySList(PListNode* ppList)
{
ListNode* begin = *ppList;
assert(ppList);
while (begin)
{
ListNode* tmp = begin;
begin = begin->_next;
free (tmp);
}
*ppList = 0;
}
void PrintSList(PListNode pList)
{
ListNode* begin = pList;
printf("PListNode:");
while (begin)
{
printf("->%d", begin->_data);
begin = begin->_next;
}
printf("->NULL
");
}
int GetLength(PListNode ppList)
{
int length = 0;
ListNode* begin = ppList;
while (begin)
{
length++;
begin = begin->_next;
}
return length;
}
ListNode* CreateNode (DataType x)
{
ListNode* n = (ListNode*)malloc (sizeof(ListNode));
n->_data = x;
n->_next = 0;
return n;
}
void PushBack (PListNode* ppList, DataType x)
{
ListNode* n = 0;
assert(ppList);
n = CreateNode (x);
// /
if (*ppList == NULL)
{
*ppList = n;
}
else
{
ListNode* begin = *ppList;
while (begin->_next)
{
begin = begin->_next;
}
begin->_next = n;
}
}
void PopBack (PListNode* ppList)
{
ListNode* begin = 0;
assert(ppList);
// 1.
if (*ppList == 0)
{
return;
}
// 2.
if ((*ppList)->_next == 0)
{
free(*ppList);
*ppList = 0;
return;
}
// 3.
begin = *ppList;
while(begin->_next->_next != NULL)
{
begin = begin->_next;
}
free(begin->_next);
begin->_next = 0;
}
void PushFront (PListNode* ppList, DataType x)
{
ListNode* n = 0;
assert(ppList);
n = CreateNode(x);
//
// 1:
// 2:
//
if (*ppList == NULL)
{
*ppList = n;
}
else
{
n->_next = *ppList;
*ppList = n;
}
}
void PopFront (PListNode* ppList)
{
ListNode* n = 0;
assert(ppList);
// 1.
if (*ppList == NULL)
{
return;
}
// 2.
if((*ppList)->_next == NULL)
{
free(*ppList);
*ppList = NULL;
return;
}
// 3.
n = *ppList;
*ppList = n->_next;
free(n);
}
ListNode* Find (PListNode ppList, DataType x)
{
ListNode* begin = 0;
assert(ppList);
begin = ppList;
while (begin)
{
if (begin->_data == x)
{
return begin;
}
begin = begin->_next;
}
return 0;
}
void Erase (PListNode* ppList, ListNode* n)
{
ListNode* del = 0;
assert(ppList);
assert(n);
//
if(n->_next == 0)
{
PopBack(ppList);
return;
}
// n next n, n next 。
n->_data = n->_next->_data;
del = n->_next;
n->_next = n->_next->_next;
free(del);
}
int Remove (PListNode* ppList, DataType x)
{
ListNode* prev = 0;
ListNode* begin = 0;
ListNode* del = 0;
assert(ppList);
begin = *ppList;
while (begin)
{
if (begin->_data == x)
{
ListNode* del = begin;
// or
if (*ppList == begin)
{
*ppList = (*ppList)->_next;
}
else
{
prev->_next = begin->_next;
}
free(del);
return 0;
}
prev = begin;
begin = begin->_next;
}
return -1;
}
void Insert (PListNode* ppList, ListNode* n, DataType x)
{
ListNode* tmp = 0;
assert(ppList);
tmp = CreateNode(x);
// /
if(*ppList == NULL)
{
*ppList = tmp;
}
else
{
assert(n);
tmp->_next = n->_next;
n->_next = tmp;
}
}
//////////////////////////////////////////////////////////////////////////////////////
//
//
//1. , ?
//2.
//3.
//4.
//5.
//6. /
//7. ( & )
//8. ,
//9. ,
//10. k ,
//11. ? , ? ? & 。
//12. , , 。( )
//13. , , 。( )【 】
//14. 。 , next , random NULL, , 。
//15. 。void UnionSet(ListNode* l1, ListNode* l2);
//
//
void DelNonTailNode (ListNode* n)
{
ListNode* del = 0;
//
assert(n->_next);
// n next n, n next 。
n->_data = n->_next->_data;
del = n->_next;
n->_next = n->_next->_next;
free(del);
}
// x
void InsertFrontNode (ListNode* n, DataType x)
{
DataType tmpData;
ListNode* tmpNode = CreateNode(x);
assert(n);
//
tmpNode->_next = n->_next;
n->_next = tmpNode;
//
tmpData = n->_data;
n->_data = tmpNode->_data;
tmpNode->_data = tmpData;
}
//
// ( ) : n ( 1,2,3...n ) // 。 k , m ; 1 , m // ; , 。
//
ListNode* JosephCycle(PListNode pList, int m)
{
ListNode* begin = pList;
assert(pList);
while (1)
{
ListNode* del = 0;
int i = 0;
//
if (begin->_next == begin)
{
break;
}
// m-1
for (; i < m-1 ; ++i)
{
begin = begin->_next;
}
printf("%d ", begin->_data);
//
del = begin->_next;
begin->_data = begin->_next->_data;
begin->_next = begin->_next->_next;
free(del);
}
return begin;
}
//
void Reverse (PListNode& pList)
{
ListNode* newHead = NULL;
ListNode* cur = pList;
// 。
while (cur)
{
//
ListNode* tmp = cur;
cur = cur->_next;
//
tmp->_next = newHead;
newHead = tmp;
}
//
pList = newHead;
}
// -( )
void BubbleSort(PListNode pList)
{
ListNode* prev = NULL;
ListNode* next = NULL;
ListNode* tail = NULL;
// tail
while (tail != pList)
{
//
int exchange = 0;
//
prev = pList;
next = pList->_next;
while(next != tail)
{
if (prev->_data > next->_data)
{
DataType tmp = prev->_data;
prev->_data = next->_data;
next->_data = tmp;
exchange = 1;
}
prev = next;
next = next->_next;
}
if (exchange == 0)
return;
//
tail = prev;
}
}
//
//
//
void PartionSort(ListNode* left, ListNode* right)
{
if (left == right || left->_next == right)
return;
// left right [)
ListNode* key = left;
//
ListNode* prev = left, *next = left->_next;
while (next != right)
{
// key
if (next->_data <= key->_data)
{
prev = prev->_next;
if (prev != next)
{
swap(prev->_data, next->_data);
}
}
next = next->_next;
}
if (prev != key)
{
swap(prev->_data, key->_data);
}
PartionSort(left, prev);
PartionSort(prev->_next, right);
}
// -> left right [)
void QucikSort(PListNode pList)
{
PartionSort(pList, NULL);
}
// ,
PListNode Merge(PListNode pList1, PListNode pList2)
{
// ,
if (pList1 == NULL)
{
return pList2;
}
if (pList2 == NULL)
{
return pList2;
}
PListNode newList, tail;
// 。
if (pList1->_data < pList2->_data)
{
newList = pList1;
pList1 = pList1->_next;
}
else
{
newList = pList2;
pList2 = pList2->_next;
}
// , 。
tail = newList;
while (pList1 && pList2)
{
if (pList1->_data < pList2->_data)
{
tail->_next = pList1;
pList1 = pList1->_next;
tail = tail->_next;
}
else
{
tail->_next = pList2;
pList2 = pList2->_next;
tail = tail->_next;
}
}
//
if (pList1)
{
tail->_next = pList1;
}
if (pList2)
{
tail->_next = pList2;
}
return newList;
}
//
PListNode MergeRecursive(PListNode pList1, PListNode pList2)
{
PListNode mergePList;
// ,
if (pList1 == pList2)
{
return pList1;
}
// ,
if (pList1 == NULL)
{
return pList2;
}
if (pList2 == NULL)
{
return pList2;
}
if (pList1->_data < pList2->_data)
{
mergePList = pList1;
mergePList->_next = MergeRecursive(pList1->_next, pList2);
}
else
{
mergePList = pList2;
mergePList->_next = MergeRecursive(pList1, pList2->_next);
}
return mergePList;
}
// 【 】
//
PListNode FindMidNode(PListNode pList)
{
// , , 。
PListNode slow, fast;
slow = pList;
fast = pList;
while (fast && fast->_next)
{
slow = slow->_next;
fast = fast->_next->_next;
}
//
// fast ,slow 。
// fast->next ,slow 。
//
return slow;
}
// k (k > 1 && k < );
// O(N)
void DelKNode(PListNode pList, int k)
{
PListNode slow, fast;
slow = pList;
fast = pList;
assert(k > 1);
// k ,
while (fast)
{
if (--k < 0)
{
slow = slow->_next;
}
fast = fast->_next;
}
if (k < 0)
{
ListNode* del = slow->_next;
slow->_data = slow->_next->_data;
slow->_next = slow->_next->_next;
free(del);
}
}
// 【 】
// , , -1
int CheckCycle(PListNode pList, PListNode* meetNode)
{
PListNode slow, fast;
if (pList == NULL)
{
return -1;
}
slow = pList;
fast = pList;
//
// , , , 。
//
while (fast && fast->_next)
{
slow = slow->_next;
fast = fast->_next->_next;
if (slow == fast)
{
// , 。
int cycleLength = 0;
*meetNode = fast;
do{
slow = slow->_next;
++cycleLength;
}while (slow != fast);
return cycleLength;
}
}
// -1
return -1;
}
//
//
// --
// , , , !^^
//
ListNode* GetCycleEntryNode(PListNode pList, PListNode meetNode)
{
int length1 = 0, length2 = 0, interval = 0;
ListNode* begin1 = pList, *begin2 = meetNode->_next;
assert(pList);
assert(meetNode);
//
// 1: , , 。
//
while (begin1 != meetNode)
{
begin1 = begin1->_next;
++length1;
}
while (begin2 != meetNode)
{
begin2 = begin2->_next;
++length2;
}
// 2: , interval( ) 。
begin1 = pList, begin2 = meetNode->_next; //
if (length1 > length2)
{
interval = length1 - length2;
while (interval--)
{
begin1 = begin1->_next;
}
}
else if(length1 < length2)
{
interval = length2 - length1;
while (interval--)
{
begin2 = begin2->_next;
}
}
// 3: 。
while (begin1 != begin2)
{
begin1 = begin1->_next;
begin2 = begin2->_next;
}
return begin1;
}
// 【 】
//
// , 。
// , n (n ), , 。( )
// , 。
//
int CheckCross(PListNode pList1, PListNode pList2)
{
ListNode* end1 = 0, *end2 = 0;
assert(pList1 && pList2);
while (pList1)
{
end1 = pList1;
pList1 = pList1->_next;
}
while (pList2)
{
end2 = pList2;
pList2 = pList2->_next;
}
if (end1 == end2)
{
return 1;
}
return 0;
}
//
// 。
// , next , random
// NULL, , 。
//
typedef struct ComplexNode
{
DataType _data; //
struct ComplexNode* _next; //
struct ComplexNode* _random; //
}ComplexNode;
ComplexNode* CreateComplexNode(DataType x)
{
ComplexNode* tmp = new ComplexNode;
tmp->_data = x;
tmp->_next = NULL;
tmp->_random = NULL;
return tmp;
}
void CreateComplexList(ComplexNode*& head)
{
ComplexNode* n1 = CreateComplexNode(1);
ComplexNode* n2 = CreateComplexNode(2);
ComplexNode* n3 = CreateComplexNode(3);
ComplexNode* n4 = CreateComplexNode(4);
n1->_next = n2;
n2->_next = n3;
n3->_next = n4;
n4->_next = NULL;
n1->_random = n4;
n2->_random = n3;
n3->_random = n2;
n4->_random = n1;
head = n1;
}
void PrintComplexList(ComplexNode* head)
{
while (head)
{
printf("【%d】", head->_data);
printf(":random->%d", head->_random->_data);
printf(":next->");
head = head->_next;
}
printf("NULL
");
}
ComplexNode* CopyComplexList(ComplexNode* cpList)
{
ComplexNode* head = cpList;
// 1. copy
head = cpList;
while (head)
{
ComplexNode* tmp = CreateComplexNode(head->_data);
ComplexNode* prev = head;
head = head->_next;
prev->_next = tmp;
tmp->_next = head;
}
// 2. copy random
head = cpList;
while (head)
{
ComplexNode* random = head->_random;
ComplexNode* next = head->_next;
if (random)
{
next->_random = random->_next;
}
head = head->_next->_next;
}
// 3. copy , copy
head = cpList;
ComplexNode* newHead, *newTail;
if (head)
{
newHead = head->_next;
newTail = head->_next;
// copy
head->_next = head->_next->_next;
head = head->_next;
}
while (head)
{
newTail->_next = head->_next;
newTail = newTail->_next;
// copy
head->_next = head->_next->_next;
head = head->_next;
}
return newHead;
}
// PushBack
void Test1()
{
PListNode pList;
printf("Test PushBack begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PrintSList(pList);
DestorySList(&pList);
printf("Test PushBack end
");
}
// PopBack
void Test2()
{
PListNode pList;
printf("Test PopBack begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PrintSList(pList);
PopBack(&pList);
PopBack(&pList);
PopBack(&pList);
PopBack(&pList);
PrintSList(pList);
DestorySList(&pList);
printf("Test PopBack end
");
}
// PushFront
void Test3()
{
PListNode pList;
printf("Test PushFront begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
DestorySList(&pList);
printf("Test PushFront end
");
}
// PopFront
void Test4()
{
PListNode pList;
printf("Test PopFront begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
PopFront(&pList);
PopFront(&pList);
PopFront(&pList);
PopFront(&pList);
PrintSList(pList);
DestorySList(&pList);
printf("Test PopFront end
");
}
// Find
void Test5()
{
PListNode pList;
printf("Test Find begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
if(Find(pList, 4))
{
printf("Find 4 Success
");
}
if(Find(pList, 5) == 0)
{
printf("Not Find 5
");
}
DestorySList(&pList);
printf("Test Find end
");
}
// Remove
void Test6()
{
PListNode pList;
printf("Test Remove begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
Remove(&pList, 1);
Remove(&pList, 2);
Remove(&pList, 3);
Remove(&pList, 4);
PrintSList(pList);
DestorySList(&pList);
printf("Test Remove end
");
}
// Insert
void Test7()
{
PListNode pList;
printf("Test Insert begin
");
InitSList(&pList);
Insert(&pList, pList, 1);
Insert(&pList, pList, 2);
Insert(&pList, pList, 3);
PrintSList(pList);
DestorySList(&pList);
printf("Test Insert end
");
}
// Erase
void Test8()
{
ListNode* del = 0;
PListNode pList;
printf("Test Erase begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PrintSList(pList);
del = Find(pList, 1);
Erase(&pList, del);
del = Find(pList, 2);
Erase(&pList, del);
PrintSList(pList);
DestorySList(&pList);
printf("Test Erase end
");
}
/////////////////////////////////////////////////////////////////////////////////
//
// Reverse
void Test9()
{
ListNode* del = 0;
PListNode pList;
printf("Test Reverse begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
Reverse(pList);
PrintSList(pList);
DestorySList(&pList);
printf("Test Reverse end
");
}
// Sort & SortOP
void Test10()
{
ListNode* del = 0;
PListNode pList;
printf("Test Sort begin
");
InitSList(&pList);
//PushFront(&pList, 6);
//PushFront(&pList, 4);
//PushFront(&pList, 1);
//PushFront(&pList, 5);
//PushFront(&pList, 3);
//PushFront(&pList, 2);
//PushFront(&pList, 7);
//PushFront(&pList, 8);
//PushFront(&pList, 8);
//PushFront(&pList, 9);
//PushFront(&pList, 0);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 4);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 4);
PushBack(&pList, 4);
PushBack(&pList, 4);
PushBack(&pList, 4);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 4);
PushBack(&pList, 4);
PushBack(&pList, 4);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 3);
PushBack(&pList, 4);
PrintSList(pList);
//BubbleSort(pList);
QucikSort(pList);
PrintSList(pList);
DestorySList(&pList);
printf("Test Sort end
");
}
// Merge
void Test11()
{
ListNode* del = 0;
PListNode pList1;
PListNode pList2;
PListNode mergePList;
printf("Test Merge begin
");
InitSList(&pList1);
InitSList(&pList2);
InitSList(&mergePList);
PushFront(&pList1, 1);
PushFront(&pList1, 2);
PushFront(&pList1, 3);
PushFront(&pList1, 4);
PushFront(&pList2, 10);
PrintSList(pList1);
PushFront(&pList2, 0);
PushFront(&pList2, 1);
PushFront(&pList2, 5);
PushFront(&pList2, 8);
PushFront(&pList2, 9);
PrintSList(pList2);
BubbleSort(pList1);
BubbleSort(pList2);
mergePList = Merge(pList1, pList2);
PrintSList(mergePList);
DestorySList(&mergePList);
printf("Test Merge end
");
}
// MergeRecursive
void Test12()
{
ListNode* del = 0;
PListNode pList1;
PListNode pList2;
PListNode mergePList;
printf("Test MergeRecursive begin
");
InitSList(&pList1);
InitSList(&pList2);
InitSList(&mergePList);
PushFront(&pList1, 1);
PushFront(&pList1, 2);
PushFront(&pList1, 3);
PushFront(&pList1, 4);
PushFront(&pList2, 10);
PrintSList(pList1);
PushFront(&pList2, 0);
PushFront(&pList2, 1);
PushFront(&pList2, 5);
PushFront(&pList2, 8);
PushFront(&pList2, 9);
PrintSList(pList2);
BubbleSort(pList1);
BubbleSort(pList2);
mergePList = MergeRecursive(pList1, pList2);
PrintSList(mergePList);
DestorySList(&mergePList);
printf("Test MergeRecursive end
");
}
// DelNonTailNode
void Test13()
{
ListNode* del = 0;
PListNode pList;
printf("Test DelMidNode begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
del =Find(pList, 3);
DelNonTailNode(del);
PrintSList(pList);
DestorySList(&pList);
printf("Test DelMidNode end
");
}
// InsertFrontNode
void Test14()
{
ListNode* n = 0;
PListNode pList;
printf("Test InsertFrontNode begin
");
InitSList(&pList);
PushFront(&pList, 1);
PushFront(&pList, 2);
PushFront(&pList, 3);
PushFront(&pList, 4);
PrintSList(pList);
n =Find(pList, 3);
InsertFrontNode(n, 0);
PrintSList(pList);
DestorySList(&pList);
printf("Test InsertFrontNode end
");
}
// FindMidNode
void Test15()
{
ListNode* n = 0;
PListNode pList;
printf("Test FindMidNode begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PrintSList(pList);
n =FindMidNode(pList);
printf("Mid: %d
", n->_data);
PushBack(&pList, 5);
PrintSList(pList);
n =FindMidNode(pList);
printf("Mid: %d
", n->_data);
DestorySList(&pList);
printf("Test FindMidNode end
");
}
// DelKNode
void Test16()
{
ListNode* n = 0;
PListNode pList;
printf("Test DelKNode begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PrintSList(pList);
DelKNode(pList, 3);
PrintSList(pList);
DestorySList(&pList);
printf("Test DelKNode end
");
}
// CheckCycle
void Test17()
{
int length = 0;
ListNode* realEntry = 0, *getEntry = 0;
ListNode* end = 0;
PListNode pList;
PListNode meetNode = 0;
printf("Test CheckCycle begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PushBack(&pList, 5);
PushBack(&pList, 6);
PushBack(&pList, 7);
PrintSList(pList);
length = CheckCycle(pList, &meetNode);
printf("Plist Length:%d
", length);
//
end = Find(pList, 7);
realEntry = Find(pList, 4);
end->_next = realEntry;
printf("realEntry:%d
", realEntry->_data);
length = CheckCycle(pList, &meetNode);
printf("Plist Length:%d, meetNode: %d
", length, meetNode->_data);
getEntry = GetCycleEntryNode(pList, meetNode);
printf("realEntry:%d, getEntry: %d
", realEntry->_data, getEntry->_data);
//
end->_next = 0;
DestorySList(&pList);
printf("Test CheckCycLeLength end
");
}
// CheckCross
void Test18()
{
PListNode pList1, pList2;
ListNode* realCrossNode, *end;
printf("Test CheckCross begin
");
InitSList(&pList1);
InitSList(&pList2);
PushBack(&pList1, 1);
PushBack(&pList1, 2);
PushBack(&pList1, 3);
PushBack(&pList1, 4);
PushBack(&pList1, 5);
PushBack(&pList1, 6);
PushBack(&pList1, 7);
PrintSList(pList1);
PushBack(&pList2, 10);
PushBack(&pList2, 11);
PushBack(&pList2, 12);
PrintSList(pList2);
printf("Cross: %d
", CheckCross(pList1, pList2));
//
realCrossNode = Find(pList1, 4);
end = Find(pList2, 12);
end->_next = realCrossNode;
printf("Cross: %d
", CheckCross(pList1, pList2));
//
end->_next = NULL;
DestorySList(&pList1);
DestorySList(&pList2);
printf("Test CheckCycLeLength end
");
}
// JosephCycle
void Test19()
{
ListNode* end;
PListNode pList;
printf("Test JosephCycle begin
");
InitSList(&pList);
PushBack(&pList, 1);
PushBack(&pList, 2);
PushBack(&pList, 3);
PushBack(&pList, 4);
PushBack(&pList, 5);
PushBack(&pList, 6);
PushBack(&pList, 7);
PrintSList(pList);
//
end = Find(pList, 7);
end->_next = pList;
printf("JosephCycle:%d
", JosephCycle(pList, 3)->_data);
printf("Test JosephCycle end
");
}
//
void Test20()
{
ComplexNode* cpList;
CreateComplexList(cpList);
PrintComplexList(cpList);
ComplexNode* copyList = CopyComplexList(cpList);
PrintComplexList(copyList);
}