用c++完成的双链表源代码.rar_双链表资源-CSDN文库

共12个文件

h：3个

cpp：3个

ncb：1个

版权申诉

129 浏览量 2022-09-24 12:12:24 上传评论收藏 10KB RAR 举报

双链表是一种常见的数据结构，它在计算机科学中扮演着重要的角色，特别是在处理需要高效插入和删除操作的场景中。本文将深入探讨双链表的概念、结构以及如何使用C++来实现。理解双链表的基本概念是至关重要的。与单链表不同，双链表中的每个节点不仅包含数据，还包含两个指针，一个指向前一个节点（prev），另一个指向后一个节点（next）。这种设计使得在链表中进行前向和后向遍历变得非常便捷，并且允许我们在O(1)的时间复杂度内执行插入和删除操作。在C++中实现双链表，我们需要定义一个节点类（Node）来存储数据和指针。这个类通常包括三个成员：数据字段（data）、指向前一个节点的指针（prev）和指向后一个节点的指针（next）： ```cpp class Node { public: int data; Node* prev; Node* next; }; ``` 接下来，我们需要一个双链表类（DoublyLinkedList）来管理这些节点。这个类应该包含初始化、插入、删除、遍历等基本操作的方法。以下是一个简单的实现： ```cpp class DoublyLinkedList { private: Node* head; Node* tail; public: DoublyLinkedList() : head(nullptr), tail(nullptr) {} // 在链表末尾添加节点 void append(int value) { Node* newNode = new Node(); newNode->data = value; newNode->prev = tail; newNode->next = nullptr; if (tail != nullptr) { tail->next = newNode; } else { head = newNode; } tail = newNode; } // 在链表开头添加节点 void prepend(int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = head; newNode->prev = nullptr; if (head != nullptr) { head->prev = newNode; } else { tail = newNode; } head = newNode; } // 删除指定值的节点 void remove(int value) { Node* current = head; while (current != nullptr) { if (current->data == value) { if (current->prev != nullptr) { current->prev->next = current->next; } else { head = current->next; } if (current->next != nullptr) { current->next->prev = current->prev; } else { tail = current->prev; } delete current; return; } current = current->next; } } // 遍历链表并打印节点值 void traverse() { Node* current = head; while (current != nullptr) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } }; ``` 在提供的压缩包文件中，"用C++完成的双链表源代码"可能包含了上述或类似的功能实现。通过阅读和分析这段代码，你可以更好地理解双链表的工作原理和C++中的实现细节。总结来说，双链表是一种灵活的数据结构，适合需要高效前向和后向操作的情况。通过定义Node类和DoublyLinkedList类，我们可以轻松地在C++中实现双链表的各种操作。这份源代码将帮助你更深入地学习和掌握这一概念。

资源推荐

资源详情

资源评论

收起资源包目录

用c++完成的双链表源代码.rar （12个子文件）

用C++完成的双链表源代码

LinkListTest

LinkListTest.dsp 5KB

LinkListTest.opt 53KB

LinkListTest.ncb 41KB

LinkList.h 2KB

LinkListTest.cpp 456B

test.cc 321B

StdAfx.cpp 299B

StdAfx.h 769B

LinkListTest.dsw 549B

Debug

LinkList_I.h 939B

LinkList.cpp 5KB

www.pudn.com.txt 218B

// LinkList.cc // author: Ke Song based C source from pp Sister XiuJie Chen ;) // http://kesongemini.diy.163.com #include "stdafx.h" #include <iostream.h> #include <stdlib.h> // exit #include "LinkList.h" void LinkList_T:: init( void ) { _top = (LinkListNode_T *)this; _bottom = (LinkListNode_T *)this; _current= (LinkListNode_T *)this; } void LinkList_T:: prepend( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("prepend: new failed"); } else { pNode->prev = (LinkListNode_T *)this; pNode->next = _top; if( _bottom == (LinkListNode_T *) this ) _bottom = pNode; _top->prev = pNode; _top = pNode; // I don't want bearing operands' order in mind // So don't use " A = B = C " pNode->contents = contents; } } void LinkList_T:: append( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("append: new failed"); } else { pNode->prev = _bottom; pNode->next = (LinkListNode_T *)this; if (_top == (LinkListNode_T *)this) _top = pNode ; _bottom->next = pNode; _bottom = pNode; pNode->contents = contents; } } CONTENTS LinkList_T:: deleteFirst( void ) { LinkListNode_T *pNode = _top; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _top = pNode->next; _top->prev = (LinkListNode_T *)this; if (_current == pNode) _current = pNode->next; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } CONTENTS LinkList_T:: deleteLast( void ) { LinkListNode_T *pNode = _bottom; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _bottom = pNode->prev; _bottom->next = (LinkListNode_T *)this; if (_current == pNode) _current = pNode->prev; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } CONTENTS LinkList_T:: deleteCurrent( void ) { LinkListNode_T *pNode = _current; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _current = pNode->next; pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } void LinkList_T:: append2current( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("append2Current: new failed"); } else { pNode->prev = _current; pNode->next = _current->next; pNode->contents = contents; _current->next->prev = pNode; _current->next = pNode; } } void LinkList_T:: prepend2current( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("prepend2Current: new failed"); } else { pNode->prev = _current->prev; pNode->next = _current; pNode->contents = contents; _current->prev->next = pNode; _current->prev = pNode; } } void LinkList_T:: deleteAll( void ) { while (!isEmpty()) deleteFirst(); } void LinkList_T:: freeAll( void ) { while (!isEmpty()) delete deleteFirst(); } void LinkList_T:: freeCurrent( void ) { delete deleteCurrent(); } bool LinkList_T:: freeMatch ( CONTENTS contents ) { LinkListNode_T *pNode; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next) { if (pNode->contents == contents) { freeNode(pNode); return true; } } return false; } LinkListNode_T* LinkList_T:: findMatch(CONTENTS contents) { LinkListNode_T *pNode; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next) { if (pNode->contents == contents) return pNode; } return (LinkListNode_T *)NULL; } int LinkList_T:: index ( CONTENTS contents ) { LinkListNode_T *pNode; int index = 0; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next, index++) { if (pNode->contents == contents) return index; } return -1; } CONTENTS LinkList_T:: contents( int index ) { LinkListNode_T *pNode; int count = 0; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next, count++) { if (count == index) return pNode->contents; } return (CONTENTS)NULL; // (CONTENTS)-1 //old } void LinkList_T:: freeNode(LinkListNode_T *pNode) { delete deleteNode(pNode); } CONTENTS LinkList_T:: deleteNode(LinkListNode_T *pNode) { CONTENTS contents; if (pNode == (LinkListNode_T *)this) { return ((CONTENTS)NULL); } else if (pNode == _current) { return deleteCurrent(); } else { pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; contents = pNode->contents; delete pNode; return contents; } } void LinkList_T:: panic ( char *s ) //static { cout<<s<<endl; exit(1); }

评论收藏

内容反馈

版权申诉