/******************************************
Copyright (C)
File name: LinkedList.c
Author: 黄成林
Description: 实现在LinkedList.h 中定义的所有函数
Others: 如若发现bug,请将与bug相关的信息发送至 472059372@qq.com
Function List:
1. void InitList(PListHead * list);/// 初始化列表
2. void CreateFromHead(PListHead list, ElemType data);/// 头插法
3. void CreateFromTail(PListHead list, ElemType data);/// 尾插法
4. PNode Get(const PListHead list, unsigned index);/// 获取指定索引处的节点
5. PNode Locate(PListHead list, ElemType key);/// 通过数据查找节点
6. unsigned int Length(PListHead list);/// 获取链表的长度
7. void InsList(PListHead list, unsigned int index, ElemType data);/// 在指定索引处 插入数据
8. void DeleteList(PListHead list, unsigned int index, ElemType * data);/// 返回指定索引处的节点并删除
9. void DestroyList(PListHead * list);/// 销毁链表
History:
1. Data: 2011-10-11
Author: 黄成林
Modification: Version 0.1
2. Data: 2011-10-11
Author: 黄成林
Modification: 将 InsList 函数中的index 限制改为 0< index < pHead->Length + 1
*******************************************/
#include <Windows.h>
#include "LinkedList.h"
static ULONG_PTR INVALIDINDEX = (ULONG_PTR)TEXT("无效索引");
static ULONG_PTR ARGLISTCANNOTBENULL= (ULONG_PTR)TEXT("参数 pHead 不能为空");
static ULONG_PTR ARGPDATACANNOTBENULL= (ULONG_PTR)TEXT("参数 pData 不能为空");
static ULONG_PTR NOMEMORY = (ULONG_PTR)TEXT("无法分配内存");
/// 初始化列表
void InitList(PListHead * pHead)
{
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] =
{
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
__try
{
(*pHead) = (PListHead)malloc(sizeof(ListHead));
(*pHead)->FirstNode = NULL;
(*pHead)->LastNode = NULL;
(*pHead)->Length = 0;
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
(*pHead) = NULL;
argArray[0] = NOMEMORY;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
}
/// 头插法
void CreateFromHead(PListHead pHead, ElemType data)
{
PNode pNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
__try
{
pNode = (PNode)malloc(sizeof(Node));
pNode->Data = data;
pNode->Next = pHead->FirstNode;
pHead->FirstNode = pNode;
if( 0 == pHead->Length++ ) pHead->LastNode = pNode;
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
argArray[0] = NOMEMORY;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
}
/// 尾插法
void CreateFromTail(PListHead pHead, ElemType data)
{
PNode pNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
__try
{
pNode = (PNode)malloc(sizeof(Node));
pNode->Data = data;
pNode->Next = NULL;
pHead->LastNode->Next = pNode;
pHead->LastNode = pNode;
if( 0 == pHead->Length++ ) pHead->LastNode = pNode;
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
argArray[0] = NOMEMORY;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
}
/// 获取指定索引处的节点
PNode Get(const PListHead pHead, unsigned index)
{
PNode pNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
if( index < 1 || index > pHead->Length )
{
argArray[0] = INVALIDINDEX;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
index--;
pNode = pHead->FirstNode;
while ( index-- > 0 )
{
pNode = pNode->Next;
}
return pNode;
}
/// 通过数据查找节点
PNode Locate(PListHead pHead, ElemType key)
{
PNode pNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
pNode = pHead->FirstNode;
while ( NULL != pNode )
{
if( 0 == memcmp((void *)&key, (void *)&pNode->Data, sizeof(ElemType)) ) break;
pNode = pNode->Next;
}
return pNode;
}
/// 获取链表的长度
unsigned int Length(PListHead pHead)
{
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
return pHead->Length;
}
/// 在指定索引处 插入数据
void InsList(PListHead pHead, unsigned int index, ElemType data)
{
PNode pNode = NULL, insertingNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] =
{
ARGLISTCANNOTBENULL
};
if( pHead == NULL ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
if( index < 1 || index > pHead->Length + 1 )
{
argArray[0] = INVALIDINDEX;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
if( 1 == index )
CreateFromHead (pHead, data); // 如果插入的索引 为 1,则使用头插法
else if( index == pHead->Length + 1)
CreateFromTail ( pHead, data); // 如果插入的索引 为 Length + 1,则使用尾插法
else
{
pNode = Get(pHead, index - 1);
__try
{
insertingNode = (PNode)malloc(sizeof(Node));
insertingNode->Data = data;
insertingNode->Next = pNode->Next;
pNode->Next = insertingNode;
pHead->Length++;
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
argArray[0] = NOMEMORY;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
}
}
/// 返回指定索引处的节点并删除
void DeleteList(PListHead pHead, unsigned int index, ElemType * pData)
{
PNode prevNode = NULL, deletingNode = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] =
{
ARGLISTCANNOTBENULL
};
if( NULL == pHead ) RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
if( NULL == pData )
{
argArray[0] = ARGPDATACANNOTBENULL;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
if( index < 1 || index > pHead->Length )
{
argArray[0] = INVALIDINDEX;
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
prevNode = Get(pHead, index - 1 );
deletingNode = prevNode->Next;
prevNode->Next = deletingNode->Next;
(*pData) = deletingNode->Data;
free((void *) deletingNode);
pHead->Length--;
}
/// 销毁链表
void DestroyList(PListHead * pHead)
{
PNode pNode = NULL, pNode2 = NULL;
ULONG_PTR argArray[EXCEPTION_MAXIMUM_PARAMETERS] = {
(ULONG_PTR)TEXT("销毁节点的过程中出现异常,内存很可能已经泄露")
};
if( NULL == pHead // 参数为 NULL
|| NULL == (*pHead) // 不存在的链表
|| NULL == (*pHead)->FirstNode // 空链表
) return;
// 获取第一个要删除的节点
pNode = (*pHead)->FirstNode;
__try
{
while(1)
{
// 保存下一个将要销毁的节点, 之所以在这不使用 (*pHead)->FirstNode, 因为解指针会影响效率
pNode2 = pNode->Next;
free( (void *)pNode ); // 这里是可能发生异常的地方
// 如果下一个节点为 NULL,则说明已经链表的所有节点已经销毁完毕
if( pNode2 == NULL) break;
pNode = pNode2; // 指定要销毁的节点
}
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
// 抛出人性化的异常
RaiseException(1, EXCEPTION_NONCONTINUABLE , 1, argArray);
}
(*pHead)->FirstNode = (*pHead)->LastNode = NULL;
(*pHead)->Length = 0;
}