A星算法的基本实现_简单实现

#include "SingleList.h" #include <stdio.h> //以下是关于单向链表的函数 //单链表创建函数 //无参数,创建成功后返回单链表指针,否则返回NULL SINGLELIST *SingleList_Create(void) { SINGLELIST *pSingleList; //分配内存操作 pSingleList = ( SINGLELIST*)malloc(sizeof( SINGLELIST)); if( pSingleList!=NULL) { //初始化链表结构的各个指针成员 pSingleList->pHead=NULL; pSingleList->pTail=NULL; pSingleList->pCur =NULL; pSingleList->uCount =0; } return pSingleList; } //单链表释放函数 //参数:要释放的单链表指针,链表节点数据释放回调函数,无返回值 void SingleList_Destroy(SINGLELIST *pSingleList,DESTROYFUNC DestroyFunc) { SINGLENODE *pNode; if( pSingleList) { //从头节点开始,一个接一个的释放链表数据及节点 pNode= pSingleList->pHead; while(pNode!=NULL) { SINGLENODE *pDelNode; pDelNode=pNode; pNode=pNode->pNext; if( DestroyFunc != NULL && pDelNode->pData != NULL) { //释放数据 (*DestroyFunc)( pDelNode->pData); } //释放节点 free(pDelNode); } //释放链表结构 free(pSingleList); } } //单链表表头添加节点函数 //参数:要插入数据的单链表指针,待插入数据,插入成功返回TRUE,否则返回FALSE int SingleList_InsertHead(SINGLELIST *pSingleList,void *pData) { SINGLENODE *pNode; //参数校验 if( pSingleList == NULL || pData == NULL) { return -1; } //新建一个节点 pNode = ( SINGLELIST *)malloc(sizeof( SINGLELIST)); if( pNode == NULL)//新节点申请不成功时返回FALSE { return -1; } pNode->pData= pData; pNode->pNext= pSingleList->pHead; pSingleList->pHead = pNode; //判断一下最初的单链表是不是空表,如果是空表则要进行pTail的相关设置 if( pSingleList->pTail == NULL) { pSingleList->pTail = pNode; } //单链表的节点数目加1 pSingleList->uCount ++; return 0; } //单链表表头弹出函数 //参数:要弹出数据的单链表,成功返回数据,否则返回NULL void *SingleList_PopHead(SINGLELIST *pSingleList) { SINGLENODE *pPopNode; void *pPopData; //参数校验 if( pSingleList == NULL || pSingleList->pHead == NULL) { return NULL; } //弹出表头的节点 pPopNode = pSingleList->pHead; pPopData = pPopNode->pData; //判断当前节点是否指向头节点 if( pSingleList->pCur == pSingleList->pHead) { pSingleList->pCur= pSingleList->pHead->pNext; } pSingleList->pHead = pSingleList->pHead->pNext; pSingleList->uCount -- ; //判断弹出数据后单链表是不是空表 if( pSingleList->uCount == 0) { pSingleList->pTail = NULL; } free(pPopNode); return pPopData; } //单链表节点删除函数 //参数:要操作的单链表,要删除的匹配数据,比较函数,释放函数,成功删除节点返回true,否则返回false int SingleList_Delete(SINGLELIST *pSingleList,void *pMatchData, COMPAREFUNC CompareFunc,DESTROYFUNC DestroyFunc) { SINGLENODE *pNode; SINGLENODE *pPrevNode; //参数校验 if( pSingleList==NULL || CompareFunc == NULL) { return -1; } pNode=pSingleList->pHead; pPrevNode = pNode; while( pNode != NULL) { //比较节点数据是否匹配 if((*CompareFunc)(pNode->pData,pMatchData)==0)//数据匹配上了,即找到了目标节点 { if( pPrevNode == pNode)//头节点就是目标节点 { pSingleList->pHead = pNode->pNext; if( pSingleList->pTail==pNode)//单链表中只有一个节点 { pSingleList->pTail = NULL; pSingleList->pCur = NULL; } } else { pPrevNode->pNext = pNode->pNext; if( pSingleList->pTail==pNode) { //如果删除的是尾节点,此时要将尾节点的指针指向尾节点的前一个节点 pSingleList->pTail = pPrevNode; } if( pSingleList->pCur ==pNode) { pSingleList->pCur = pNode->pNext; } } //释放节点数据和节点空间 if( DestroyFunc != NULL && pNode->pData != NULL) { (*DestroyFunc)(pNode->pData); } free(pNode); break;//成功删除数据后就要跳出循环 } //没有找到则继续 pPrevNode=pNode; pNode=pNode->pNext; } return 0; } //单向链的插入排序函数 //参数:要排序的单链表,比较数据大小回调函数,排序成功返回true,否则返回false int SingleList_InsertSort(SINGLELIST *pSingleList,COMPAREFUNC CompareFunc) { SINGLENODE *pNode; SINGLENODE *pPrevNode; //参数校验 if( pSingleList==NULL || CompareFunc == NULL || pSingleList->pHead == NULL) { return -1; } pNode= pSingleList->pHead; pPrevNode=NULL; while( pNode->pNext != NULL) { SINGLENODE *pTempNode; pTempNode = pSingleList->pHead; pPrevNode= NULL; while( pTempNode != pNode->pNext) { //X节点与它前面的节点都进行比较,直到找到比它大的数据Y,将X插入在Y的前面 if((*CompareFunc)(pNode->pNext->pData,pTempNode->pData)<0) { SINGLENODE *pCurNode=pNode->pNext; //执行插入操作 if( pPrevNode != NULL)//插入不在头节点前的情况 { //将pCurNode节点弹出来 pNode->pNext = pNode->pNext->pNext; //将pNode->pNext插入pTempNode之前 pPrevNode->pNext = pCurNode; pCurNode->pNext = pTempNode; } else//插入在头节点的情况 { //将pCurNode节点弹出来 pNode->pNext = pNode->pNext->pNext; //将pNoode->pNext节点变为头节点 pSingleList->pHead = pCurNode; pCurNode->pNext = pTempNode; } //修改尾指针的指向 if( pCurNode == pSingleList->pTail) { pSingleList->pTail = pNode; } break; } pPrevNode = pTempNode; pTempNode = pTempNode->pNext; } if( pTempNode== pNode->pNext)//没有插入的情况 { pNode= pNode->pNext; } } return 0; } //查看单链表是不是为空 int IsEmpty(SINGLELIST *pSingleList) { if(pSingleList->pHead == NULL) return 0; else return 1; } //查找某一个元素是不是在这个单链表中,如果在则返回1,否则返回0 int SingleList_Find(SINGLELIST *pSingleList,void *pData) { if(pSingleList->pHead== NULL) return 0; SINGLENODE *pNode; pNode = pSingleList->pHead; while(pNode!= NULL) { if(pNode->pData == pData) return 1; else pNode = pNode->pNext; } return 0; }