先来看一下双向链表和双向循环链表的逻辑结构:
下面我们将用c/c++语言实现双向循环链表:
#include <iostream> #include <malloc.h> #include <windows.h> using namespace std; typedef struct _DATA_//数据 { char name[40]; }Data,*pData; typedef struct _NODE_//节点 { Data data;//数据域 //指针域 _NODE_* pNext;//后继指针 _NODE_* pPre;//前驱指针 }Node,*pNode; typedef struct _TABLE_//管理员 { pNode pHead;//头指针(头节点) pNode pTail;//尾指针(尾节点) int nodeCount;//节点数 }Table,*pTable; ////////////////////// //声明 pNode createNode(Data data);//创建节点 void linkNode(pTable pTableTemp,pNode pNodeNew);//将创建的节点插入链表 void printList(pTable pTableTemp);//遍历链表 int getNodeCount(pTable pTableTemp);//返回节点个数 void freeList(pTable pTableTemp);//释放所有节点 pNode findNode(pTable pTableTemp,char* name);//查找节点 void deleteNode(pTable pTableTemp,pNode pNodeTemp);//删除节点 ///////////////////// //测试 int main(void) { Table table = {0}; Data data = {0}; char temp[40]; for(int i = 0; i < 4; i++) { cout<<"input name:"; cin>>data.name; pNode pNodeTemp = createNode(data); linkNode(&table,pNodeTemp); } printList(&table); cout<<"input data to del:"; cin>>temp; pNode pNodeDel = findNode(&table,temp); if(pNodeDel != NULL) { deleteNode(&table,pNodeDel); } printList(&table); freeList(&table); return 0; } //////////////////////////////////////////// //具体实现 pNode createNode(Data data) { pNode pNodeNew = (pNode)malloc(sizeof(Node));//申请内存 if(pNodeNew != NULL)//申请成功 { pNodeNew->data = data;//数据域赋值 pNodeNew->pNext = pNodeNew->pPre = NULL;//指针域赋值 return pNodeNew;//返回新生成的节点 } return NULL;//失败时返回空 } void linkNode(pTable pTableTemp,pNode pNodeNew)//节点插入 { if(pTableTemp->pHead == NULL)//如果头指针为空 { pTableTemp->pHead = pTableTemp->pTail = pNodeNew;//头指针和尾指针均指向新节点 pTableTemp->pHead->pPre = pTableTemp->pTail->pNext = pNodeNew;//对节点的指针域赋值(指向自身) } else//否则 { pTableTemp->pTail->pNext = pNodeNew;//尾节点的后继指针指向新节点 pTableTemp->pHead->pPre = pNodeNew;//头节点的前驱指针指向新节点 pNodeNew->pPre = pTableTemp->pTail;//新节点的前驱指针指向尾节点 pNodeNew->pNext = pTableTemp->pHead;//新节点的后继指针指向首节点 pTableTemp->pTail = pNodeNew;//尾指针后移,并指向新生成的节点 } pTableTemp->nodeCount++;//节点数++ } void printList(pTable pTableTemp) { pNode pNodeTemp = pTableTemp->pHead; for(int i = 0; i < pTableTemp->nodeCount; i++) { cout<<pNodeTemp->data.name<<" "; pNodeTemp = pNodeTemp->pNext; } cout<<endl; } int getNodeCount(pTable pTableTemp) { return pTableTemp->nodeCount; } void freeList(pTable pTableTemp) { if(pTableTemp != NULL) { pNode pNodeTemp = pTableTemp->pHead; pNode pNodeDel = NULL; for(int i = 0; i < pTableTemp->nodeCount; i++) { pNodeDel = pNodeTemp->pNext; free(pNodeTemp); pNodeTemp = pNodeDel; } } } pNode findNode(pTable pTableTemp,char* name) { pNode pNodeTemp = pTableTemp->pHead; int iOK = -1; for(int i = 0; i < pTableTemp->nodeCount; i++) { iOK = strcmp(name,pNodeTemp->data.name); if(iOK == 0) { return pNodeTemp; } else { pNodeTemp = pNodeTemp->pNext; } } return NULL; } void deleteNode(pTable pTableTemp,pNode pNodeTemp) { if(pNodeTemp == pTableTemp->pHead)//待删除节点为头节点 { pTableTemp->pHead = pNodeTemp->pNext; pTableTemp->pTail->pNext = pTableTemp->pHead; } else if(pNodeTemp == pTableTemp->pTail)//待删除节点为尾节点 { pTableTemp->pTail = pNodeTemp->pPre; pTableTemp->pHead->pPre = pTableTemp->pTail; } else//待删除节点为中间节点 { pNodeTemp->pNext->pPre = pNodeTemp->pPre; pNodeTemp->pPre->pNext = pNodeTemp->pNext; } free(pNodeTemp);//释放节点 pTableTemp->nodeCount--; }
需要注意的是,插入删除算法。
插入分两种情况,如果链表为空,逻辑结构如下图:
如果链表不为空,则逻辑结构如下:
应该针对不同情况分别处理.