首页 > 代码库 > 线性表之单向链表的基本操作实现
线性表之单向链表的基本操作实现
线性表之单向链表的基本操作实现
这篇文章用来回顾单向链表的相关知识并实现如下几个操作:
- 初始化
- 插入
- 删除
- 逆置
- 销毁
且实现的链表为带头节点的单线非循环链表.由于链表在尾插入时需要遍历到链表的最后一个位置,所以我需要记住最后一个节点的位置,为此,本文会简单的实现一个单向链表的类.
0.链表的定义与类中提供的API
1 typedef int ELEMENT; 2 3 struct Node_s { 4 Node_s():data(),NEXT(nullptr){} 5 ELEMENT data; 6 Node_s * NEXT; 7 }; 8 9 typedef Node_s Node; 10 typedef Node * NodePtr;
1 class CForward_List 2 { 3 public: 4 CForward_List(void); 5 6 ~CForward_List(void); 7 8 // 当空时返回真 9 bool isEmpty(); 10 11 // 从文件中读入节点数据 12 size_t readFromFile(std::string &_filename); 13 14 // 在头节点后插入一个节点 15 void insert_atHead(ELEMENT &_data); 16 17 // 在尾节点后插入一个节点 18 void insert_atTail(ELEMENT &_data); 19 20 // 在指定位置后插入一个节点 21 void insert_before(ELEMENT &_positionData,ELEMENT &_insertData); 22 23 // 删除链表中指定元素的值 24 void deleteNode_single(ELEMENT &_data); 25 26 // 销毁链表中的所有数据 27 void deleteAllData(); 28 29 // 更新链表中的值 30 NodePtr update(ELEMENT &_originalData,ELEMENT &_data); 31 32 // 搜索链表中的值的位置 33 NodePtr search(ELEMENT &_data); 34 35 // 将链表逆置 36 NodePtr reverse(); 37 38 // Sort by bubble/insert/select 39 NodePtr sort(SORTWAY _sortway); 40 41 // Show 42 void showListInfo(); 43 44 private: 45 // 节点数量 46 size_t size; 47 48 // 头节点 49 NodePtr listHeadPtr; 50 51 // 尾节点 52 NodePtr listEndPtr; 53 54 // 在一个指定位置后插入一个节点 55 void insert_after(NodePtr insertPos,ELEMENT &_data); 56 57 // 删除指定节点后的节点 58 void deleteNode_specific(NodePtr beforeDeleteNode); 59 60 // 下一个是否与当前的相等 61 bool nextEqualThis(NodePtr nodePos,ELEMENT &_data); 62 63 // 冒泡排序 64 NodePtr sort_bubble(); 65 void sort_swap(ELEMENT * _data1,ELEMENT *_data2); 66 67 // 选择排序 68 NodePtr sort_select(); 69 NodePtr sort_select_min(NodePtr _startNode); 70 71 // 插入排序 72 NodePtr sort_insert(); 73 NodePtr findInsertPos(NodePtr _newListHeadPtr,NodePtr _seekedNode); 74 void sort_insert_after(NodePtr _firstNode,NodePtr _secondNode); 75 };
下面会分步的实现前面提到的函数.
1.初始化(构造)与析构函数
初始化函数先创建一个头结点,将链表的大小置为0,指向尾部的节点为空;
1 CForward_List::CForward_List(void):listHeadPtr(nullptr),listEndPtr(nullptr) 2 { 3 size = 0; 4 listHeadPtr = new Node; 5 listEndPtr = nullptr; 6 }
析构函数为了确保所有节点都被清理会调用销毁相关的函数,在deleteAllData()函数内部会处理size的值.
1 CForward_List::~CForward_List(void) 2 { 3 // 删除所有节点信息 4 deleteAllData(); 5 6 if(!listHeadPtr) 7 delete listHeadPtr; 8 if (!listEndPtr) 9 delete listEndPtr; 10 }
2.插入操作
头插入:
其实头插入就是在头指针后插入一个节点,这里体会到了使用头结点的方便性.
1 void CForward_List::insert_atHead(ELEMENT &_data){ 2 insert_after(listHeadPtr,_data); 3 }
尾插入:
其实为插入也就是在尾指针后进行插入一个节点的行为,但是这里需要判断链表是否为空,
因为,若链表为空的话尾指针指向的对象是空的,所以需要在头结点后插入,然后将尾指针指向插入的元素即可.
否则,直接在尾指针后插入即可.
1 void CForward_List::insert_atTail(ELEMENT &_data){ 2 if (isEmpty()) 3 insert_after(listHeadPtr,_data); 4 else 5 insert_after(listEndPtr,_data); 6 }
在指定位置之前插入:
对链表进行指定元素的插入操作最重要的就是,要找到指定元素的前驱节点.然后再调用前面的 insert_after 函数即可.
1 void CForward_List::insert_before(ELEMENT &_positionData,ELEMENT &_insertData){ 2 NodePtr node = listHeadPtr; 3 while (node){ 4 if (nextEqualThis(node,_positionData)){ 5 insert_after(node,_insertData); 6 break; 7 } 8 node = node->NEXT; 9 } 10 }
nextEqualThis函数是判断传入节点node与node->next的data值是否相等,相等返回true,否则返回false;
插入操作的总结:
其实插入操作就是一个遍历的过程,要找到插入位置之前的节点是关键;
这里对两个功能进行模块化,一是在指定节点后的插入行为,二是判断当前节点是否与下一个节点相等.
具体的插入操作:
1 void CForward_List::insert_after(NodePtr _insertPos,ELEMENT &_data){ 2 NodePtr insertNode = new Node; 3 insertNode->data =http://www.mamicode.com/ _data; 4 // 判断是否要移动尾指针的位置 5 if (!_insertPos->NEXT) 6 listEndPtr = insertNode; 7 // 进行插入操作 8 insertNode->NEXT = _insertPos->NEXT; 9 _insertPos->NEXT = insertNode; 10 size++; 11 }
1 bool CForward_List::nextEqualThis(NodePtr _nodePos,ELEMENT &_data){ 2 if (!_nodePos->NEXT) 3 return false; 4 else 5 return _nodePos->NEXT->data =http://www.mamicode.com/= _data; 6 }
这里的代码和许多教科书上的代码都不尽相同,因为我想着什么是插入操作的共同点,然后将其提取出来,将代码量减少.
但是上面有一个问题就是在指定位置插入的过程中,遍历查找的操作会频繁调用nextEqualThis函数,要论如何优化的话我想要是设置为inline可能会是一个不错的选择,但是编译其听不听我的话就是另一回事了:)
3.删除操作
删除操作和前面的在指定位置插入有许多相同之处.,也是遍历以查找到删除之前的那个节点,然后在那个位置上执行删除操作.
1 void CForward_List::deleteNode_single(ELEMENT &_data){ 2 NodePtr node = listHeadPtr; 3 while (node){ 4 if (nextEqualThis(node,_data)){ 5 deleteNode_specific(node); 6 break; 7 } 8 node = node->NEXT; 9 } 10 }
具体的删除操作:
1 void CForward_List::deleteNode_specific(NodePtr _beforeDeleteNode){ 2 NodePtr deletedNode = _beforeDeleteNode->NEXT; 3 _beforeDeleteNode->NEXT = deletedNode->NEXT; 4 // 若删除的节点是尾节点,则需要重新设置尾节点 5 if (!deletedNode->NEXT) 6 listEndPtr = _beforeDeleteNode; 7 size--; 8 delete deletedNode; 9 }
删除操作的总结:
可以发现删除操作的思路和插入的大致相同,遍历是前提.但是在删除的具体操作中,需要判断是否删除的是尾指针.
4.逆置操作
逆置的思路就是遍历的过程中把当前这个节点指向前面的节点. 10 - 19 行才是关键,只是在遍历的过程中需要几个临时变量记住即将发生变化的节点.
1 NodePtr CForward_List::reverse(){ 2 NodePtr 3 head = listHeadPtr->NEXT, 4 tmpPtr = nullptr, 5 preNode = nullptr; 6 7 // Record the end_pointer 8 listEndPtr = head; 9 10 while (head){ 11 // Record the next node,beacuse I will change the next value 12 tmpPtr= head->NEXT; 13 // Reverse operation 14 head->NEXT = preNode; 15 // Record current node 16 preNode = head; 17 // Require the next node. 18 head = tmpPtr; 19 } 20 // Make the head_pointer point to the reversed list. 21 listHeadPtr ->NEXT = preNode; 22 23 return listHeadPtr; 24 }
5.排序操作
这里实现了三种排序方式,根据参数的不同做出不同的反映.可惜的是他们的平均时间复杂度都是O(n^2)
1 NodePtr CForward_List::sort(SORTWAY _sortway){ 2 if(_sortway == BUBBLESORT) 3 listHeadPtr = sort_bubble(); 4 else if (_sortway == SELECTSORT) 5 listHeadPtr = sort_select(); 6 else if (_sortway == INSERTSORT) 7 listHeadPtr = sort_insert(); 8 return listHeadPtr; 9 }
冒泡排序:
按照从大到小排序.
1 NodePtr CForward_List::sort_bubble(){ 2 for (NodePtr kNode = listHeadPtr->NEXT;kNode;kNode = kNode->NEXT) 3 for (NodePtr fNode = listHeadPtr->NEXT;fNode;fNode=fNode->NEXT) 4 if (kNode->data > fNode->data) 5 sort_swap(&kNode->data,&fNode->data); 6 return listHeadPtr; 7 }
选择排序:
按照从小到大排序.遍历到的每个元素都是最小的元素.
1 NodePtr CForward_List::sort_select(){ 2 for (NodePtr kNode = listHeadPtr->NEXT;kNode;kNode = kNode->NEXT){ 3 NodePtr minNodePtr = sort_select_min(kNode); 4 sort_swap(&kNode->data,&minNodePtr->data); 5 } 6 return listHeadPtr; 7 }
选择最小元素的具体过程;这里有一个细节,就是为什么不在sort_select_min函数传入kNode->NEXT,因为避免返回值是nullptr.导致sort_swap异常.
1 NodePtr CForward_List::sort_select_min(NodePtr _startNode){ 2 ELEMENT minData = http://www.mamicode.com/_startNode->data; 3 NodePtr minPtr = _startNode; 4 for (NodePtr fNode = _startNode->NEXT;fNode;fNode=fNode->NEXT){ 5 if (fNode->data < minData){ 6 minData = http://www.mamicode.com/fNode->data; 7 minPtr = fNode; 8 } 9 } 10 return minPtr; 11 }
插入排序:
按照从小到大排序.这里实现的不是就地的插入排序.而是新建立一个和拥有相同头结点的链表,不过并不会涉及节点的创建,只是节点之间的"再连接";
1 NodePtr CForward_List::sort_insert(){ 2 NodePtr 3 kNode = listHeadPtr->NEXT, 4 newListHeadPtr = listHeadPtr; 5 newListHeadPtr->NEXT = nullptr; 6 7 NodePtr tmp; 8 while (kNode){ 9 // 找到在新链表中可插入的位置 10 NodePtr insertPos = findInsertPos(newListHeadPtr,kNode); 11 // 临时保存下一个节点的位置 12 tmp = kNode->NEXT; 13 // 在新链表中进行插入操作 14 sort_insert_after(insertPos,kNode); 15 // 获取临时保存的下一个节点 16 kNode = tmp; 17 } 18 19 return newListHeadPtr; 20 }
插入排序的具体过程,保存怎么寻找插入的位置,以及在指定位置后进行插入操作.
1 NodePtr CForward_List::findInsertPos(NodePtr _newListHeadPtr,NodePtr _seekedNode){ 2 NodePtr kNode; 3 for (kNode = _newListHeadPtr;kNode->NEXT;kNode = kNode->NEXT){ 4 if (_seekedNode->data < kNode->NEXT->data) 5 return kNode; 6 } 7 return kNode; 8 } 9 void CForward_List:: sort_insert_after(NodePtr _insertPos,NodePtr _insertNode){ 10 if (!_insertPos->NEXT) 11 listEndPtr = _insertNode; 12 _insertNode->NEXT = _insertPos->NEXT; 13 _insertPos->NEXT = _insertNode; 14 }
交换两个节点元素:
1 void CForward_List::sort_swap(ELEMENT * _data1,ELEMENT *_data2){ 2 ELEMENT tmp; 3 tmp = *_data1; 4 *_data1 = *_data2; 5 *_data2 = tmp; 6 }
排序操作总结:
以上的排序实现都是仅仅交换节点元素,并没有实现节点的"真"交换.即连带删除/插入的操作,我认为得看具体实现要求,目前这已经能够实现链表的排序了.
6.销毁操作
这里说明一下为什么要判断size是否等于0,因为我认为若多次链表的操作之后,在进行链表的销毁肯定会size==0的,但是留一个悬念,万一之前的操作哪里有问题(new 失败...),则会导致清理完后size不等于0.
所以留着残余的数据以便查找问题所在.
1 void CForward_List::deleteAllData(){ 2 std::cout << "deleting all node "<<std::endl; 3 NodePtr node = listHeadPtr->NEXT,nextNode; 4 while (node) { 5 nextNode = node->NEXT; 6 delete node; 7 node = nullptr; 8 size--; 9 node = nextNode; 10 } 11 if(size == 0){ 12 listHeadPtr->NEXT = nullptr; 13 listEndPtr = nullptr; 14 } 15 }
好了,这些就是基本的链表操作,相关的代码可以在 我的github上参考源码.
线性表之单向链表的基本操作实现