数据结构-加入泛型的线性表、栈、队列

#include <stdio.h> #include <stdlib.h> #include "JWList_double.h" /*######################################################################*/ /*######################################################################*/ /* 基础线性表函数声明 */ /*######################################################################*/ /*######################################################################*/ /************************************************************************/ /* 从头部开始创建链表 */ /************************************************************************/ JWList_double* JWListCreateFromHead_double(int nSize, JWListElem_double *pElemList) { PJWList_double pHead; PJWListNode_double pRear, pNode; int i; //创建一个头结点 if (NULL == (pHead = (PJWList_double)malloc(sizeof(JWList_double)))) { return NULL; } pHead->nLength = 0; pHead->pNext = NULL; if (0 == nSize) { return pHead; } //nSize不为0，在尾结点后添加后续节点 for (i = 0; i < nSize; i++) { if (NULL == (pNode = (PJWListNode_double)malloc(sizeof(JWListNode_double)))) { return pHead; } pNode->elem = pElemList[i]; if (0 == i) { pHead->pNext = pNode; pNode->pPrior = NULL; pNode->pNext = NULL; pRear = pNode; } else { pNode->pPrior = pRear; pNode->pNext = pRear->pNext; pRear->pNext = pNode; pRear = pNode; } pHead->nLength += 1; } return pHead; } /************************************************************************/ /* 从尾部开始创建链表 */ /************************************************************************/ JWList_double* JWListCreateFromTail_double(int nSize, JWListElem_double *pElemList) { PJWList_double pHead; PJWListNode_double pNode; int i; //创建一个头结点 if (NULL == (pHead = (PJWList_double)malloc(sizeof(JWList_double)))) { return NULL; } pHead->nLength = 0; pHead->pNext = NULL; if (0 == nSize) { return pHead; } //nSize不为0，在头结点后添加后续节点 for (i = 0; i < nSize; i++) { if (NULL == (pNode = (PJWListNode_double)malloc(sizeof(JWListNode_double)))) { return pHead; } pNode->elem = pElemList[i]; if (i > 0) { pHead->pNext->pPrior = pNode; } pNode->pNext = pHead->pNext; pNode->pPrior = NULL; pHead->pNext = pNode; pHead->nLength += 1; } return pHead; } /************************************************************************/ /*销毁整个链表 */ /************************************************************************/ void JWListDestroy_double( JWList_double *pList ) { PJWListNode_double pNodePrev, pNode; pNode = pList->pNext; //删除所有元素节点 while (pNode != NULL) { pNodePrev = pNode; pNode = pNode->pNext; free(pNodePrev); } //删除头节点 free(pList); } /************************************************************************/ /* 清空整个链表 */ /************************************************************************/ void JWListMakeEmpty_double( JWList_double *pList ) { PJWListNode_double pNodePrev, pNode; pNode = pList->pNext; //删除所有元素节点 while (pNode != NULL) { pNodePrev = pNode; pNode = pNode->pNext; free(pNodePrev); } pList->nLength = 0; pList->pNext = NULL; } JWList_BOOL JWListIsEmpty_double( JWList_double *pList ) { return 0 == pList->nLength ? JWLIST_TRUE : JWLIST_FALSE; } int JWListGetLength_double( JWList_double *pList ) { return pList->nLength; } /************************************************************************/ /* 获得指定索引的节点(0~长度-1)的值 */ /************************************************************************/ JWList_BOOL JWListGetAt_double( JWList_double *pList, const int nIndex, JWListElem_double *pElem ) { int i; JWListNode_double *pNode; //检查索引合法性，包含表为空的情形 if (nIndex < 0 || nIndex > pList->nLength-1) { return JWLIST_FALSE; } //从头结点遍历到指定索引的节点 pNode = pList->pNext; for (i = 1; i <= nIndex; i++) { pNode = pNode->pNext; } //获取指定节点的值 *pElem = pNode->elem; return JWLIST_TRUE; } /************************************************************************/ /* 设置指定索引的节点(0~长度-1)的值 */ /************************************************************************/ JWList_BOOL JWListSetAt_double( JWList_double *pList, const int nIndex, const JWListElem_double elem ) { int i; JWListNode_double *pNode; //检查索引合法性，包含表为空的情形 if (nIndex < 0 || nIndex > pList->nLength-1) { return JWLIST_FALSE; } //从头结点遍历到指定索引的节点 pNode = pList->pNext; for (i = 1; i <= nIndex; i++) { pNode = pNode->pNext; } //设置指定节点的值 pNode->elem = elem; return JWLIST_TRUE; } /************************************************************************/ /* 在指定索引的节点(0~长度)前插入新节点，索引==长度时表示在末尾添加新节点 */ /************************************************************************/ JWList_BOOL JWListInsert_double( JWList_double *pList, const int nIndex, const JWListElem_double elem ) { int i; JWListNode_double *pNodePrev, *pNode, *pNewNode; //检查索引合法性，包含表为空的情形 if (nIndex < 0 || nIndex > pList->nLength) { return JWLIST_FALSE; } //从头结点遍历到指定索引的节点并记录其前驱节点 pNode = pList->pNext; pNodePrev = NULL; for (i = 1; i <= nIndex; i++) { pNodePrev = pNode; pNode = pNode->pNext; } //添加指定节点 if(NULL == (pNewNode = (PJWListNode_double)malloc(sizeof(JWListNode_double)))) { return JWLIST_FALSE; } pNewNode->elem = elem; pNewNode->pNext = pNode; pNewNode->pPrior = pNodePrev; if (pNodePrev != NULL)//不是在第一个节点前插入 { pNodePrev->pNext = pNewNode; } else { pList->pNext = pNewNode; } if (NULL != pNode)//不是在末尾插入 { pNode->pPrior = pNewNode; } pList->nLength += 1;//长度+1 return JWLIST_TRUE; } /************************************************************************/ /* 删除指定索引的节点(0~长度-1) */ /************************************************************************/ JWList_BOOL JWListDelete_double( JWList_double *pList, const int nIndex, JWListElem_double *pElem ) { int i; JWListNode_double *pNodePrev, *pNode; //检查索引合法性，包含表为空的情形 if (nIndex < 0 || nIndex > pList->nLength-1) { return JWLIST_FALSE; } //从头结点遍历到指定索引的节点并记录其前驱节点 pNode = pList->pNext; pNodePrev = NULL; for (i = 1; i <= nIndex; i++) { pNodePrev = pNode; pNode = pNode->pNext; } if (pNodePrev != NULL)//不是删除第一个节点 { pNodePrev->pNext = pNode->pNext; } else { pList->pNext = pNode->pNext; } if(NULL != pNode->pNext)//不是删除末尾节点 { pNode->pNext->pPrior = pNodePrev; } pList->nLength -= 1;//长度-1 if (NULL != pElem) { *pElem = pNode->elem; } free(pNode); return JWLIST_TRUE; } /************************************************************************/ /* 在线性表中遍历找到满足pCompare函数的索引返回索引指针，没找到则返回NULL */ /************************************************************************/ PJWListNode_double JWListLocate_double( JWList_double *pList, const JWListElem_double elem, JWList_CompareFunc_double pCompare ) { PJWListNode_double pNode; //跳过头结点 pNode = pList->pNext; //遍历对比余下所有节点 while (pNode != NULL) { if (JWLIST_TRUE == pCompare(pNo