//------------------------------------------------------------------------------ // 双链表的相关操作 //------------------------------------------------------------------------------ #include <iostream> using namespace std; // 双链表数据结构 typedef struct DNode { int data; DNode* prev; DNode* next; }DoubleList, *pDoubleList; //****************************************************************************** // Name: CreateNode // Desc: 创建双链表 //****************************************************************************** DNode* CreateDNode() { DNode* head; DNode* tempPrev; DNode* tempNext; head = new DNode; head->next = NULL; head->prev = NULL; tempPrev = NULL; tempNext = head; cout<<"please input some datas to create a doubleNode:"<<endl; int data; while(cin>>data) { // 赋值后继 tempNext->next = new DNode; tempNext = tempNext->next; tempNext->data = data; // 赋值前驱 tempNext->next = NULL; tempNext->prev = tempPrev; tempPrev = tempNext; } head = head->next; head->prev = NULL; return head; } //****************************************************************************** // Name: DNodeLength // Desc: 计算双链表的长度 //****************************************************************************** int DNodeLength(DNode* head) { if(head == NULL) return 0; DNode* currentDNode = head; int currentLength = 0; while(currentDNode != NULL) { ++currentLength; currentDNode = currentDNode->next; } return currentLength; } //****************************************************************************** // Name: PrintDNode // Desc: 打印双链表 //****************************************************************************** void PrintDNode(DNode* head) { if(head == NULL) { cout<<"链表元素为空"<<endl; } else { DNode* currentDNode = head; while(currentDNode != NULL) { cout<<currentDNode->data<<" "; currentDNode = currentDNode->next; } cout<<endl; } } //****************************************************************************** // Name: 删除双链表中的元素 // Desc: DeleteDNode(DNode* head, int data) //****************************************************************************** DNode* DeleteDNode(DNode* head, int data) { if(head == NULL) { cout<<"链表为空!"<<endl; return NULL; } else { DNode* currentNode = head; // 试图找到要删除的元素 while(currentNode != NULL && currentNode->data != data) { currentNode = currentNode->next; } if(currentNode->prev != NULL) // 有前驱 { if(currentNode->next != NULL) // 有前驱,有后继,删除中间元素 { currentNode->prev->next = currentNode->next; currentNode->next->prev = currentNode->prev; } else // 有前驱,无后继,删除最后一个元素 { currentNode->prev->next = NULL; currentNode->prev = NULL; } } else // 无前驱 { if(currentNode->next != NULL) // 无前驱,有后继,删除第一个元素 { head = head->next; // 改变了头指针地址 currentNode->next->prev = NULL; } else // 无前驱,无后继,删除唯一元素 { head = NULL; // 此处不能进行delete head操作,因为下面会删除,删除两次会有问题 } } delete currentNode; currentNode = NULL; return head; } } //****************************************************************************** // Name: InsertDNode // Desc: 双链表中插入元素,参数为位置和要插入的值 //****************************************************************************** DNode* InsertDNode(DNode* head, int pos, int data) { DNode* newDNode = new DNode; // 待插入的新节点 newDNode->data = data; newDNode->next = NULL; newDNode->prev = NULL; DNode* rightDNode = head; // 将在这个位置的前面插入 int maxPos = DNodeLength(head) ; // 双链表长度 if(head == NULL) { return newDNode; } if(pos > maxPos) // 如果越界,则插在最尾部 { pos = maxPos ; } for(int i = 1; i < pos; ++i) { rightDNode = rightDNode->next; } if(0 == pos || maxPos == pos) // 插在头部和插在尾部的单独处理 { if(pos > 0) // 尾部 { rightDNode->next = newDNode; newDNode->prev = rightDNode; newDNode->next = NULL; } else // 头部 { newDNode->next = rightDNode; newDNode->prev = NULL; rightDNode->prev = newDNode; head = newDNode; // 改变了头指针地址 } } else // 插在中间的元素 { rightDNode->prev->next = newDNode; newDNode->prev = rightDNode->prev; rightDNode->prev = newDNode; newDNode->next = rightDNode; } return head; } int main() { int deleteElem; // 要删除的元素 int addPos; // 插入的位置 int addElem; // 添加的元素 cout<<"创建双链表:"<<endl; DNode* head = CreateDNode(); cout<<"--------------------------------------------------------"<<endl; cout<<"双链表长度为: "<<DNodeLength(head)<<endl; cout<<"--------------------------------------------------------"<<endl; cout<<"打印双链表: "<<endl; PrintDNode(head); cout<<"--------------------------------------------------------"<<endl; cout<<"请输入要删除的元素:"<<endl; cin.clear(); // 创建双链表的时候,已经暂用了IO缓冲 cin>>deleteElem; head = DeleteDNode(head, deleteElem); cout<<"--------------------------------------------------------"<<endl; cout<<"打印双链表: "<<endl; PrintDNode(head); cout<<"--------------------------------------------------------"<<endl; cout<<"请输入插入元素的位置和要插入的元素"<<endl; cin>>addPos>>addElem; head = InsertDNode(head, addPos, addElem); cout<<"--------------------------------------------------------"<<endl; cout<<"打印双链表: "<<endl; PrintDNode(head); cout<<"--------------------------------------------------------"<<endl; system("pause"); return 0; }