C++数据结构第22课、单链表的具体实现

1、课程目标

— 完成链式存储结构线性表的实现

LinkList 设计要点 — 类模板，通过头结点访问后继节点 — 定义内部结点类型 Node，用于描述数据域和指针域 — 实现线性表的关键操作（增，删，查，等）LinkList 的定义

LinkList 的实现：

#ifndef LINKLIST_H #define LINKLIST_H #include "List.h" #include "Exception.h" namespace DTLib { template <typename T> class LinkList : public List<T> { protected: struct Node : public Object { T value; Node* next; }; mutable Node m_header; int m_length; public: LinkList() { m_header.next = nullptr; m_length = 0; } bool insert(const T& e) { return insert(m_length, e); } bool insert(int i, const T& e) { bool ret = (i >= 0 && i <= m_length); if(ret) { Node* node = new Node(); if(node != nullptr) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } node->value = e; node->next = current->next; current->next = node; m_length++; } else { THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert the Linklist"); } } return ret; } bool remove(int i) { bool ret = (i >= 0 && i < m_length); if(ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } Node* toDel = current->next; current->next = toDel->next; delete toDel; m_length--; } return ret; } bool set(int i, const T& e) { bool ret = (i >= 0 && i < m_length); if(ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } current->next->value = e; } return ret; } T get(int i)const { T ret; if(get(i, ret)) { return ret; } else { THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is Invalid"); } } bool get(int i, T& e)const { bool ret = (i >= 0 && i < m_length); //这个函数是一个const成员函数，const成员函数内部的成员变量是只读的，所以我们不能直接赋值，解决方法是用mutable修饰成员变量m_header，使它可以被访问。 if(ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } e = current->next->value; } return ret; } int length()const { return m_length; } void clear() { while(m_header.next != nullptr) { Node* toDel = m_header.next; m_header.next = toDel->next; delete toDel; } m_length = 0; } ~LinkList() { clear(); } }; } #endif // LINKLIST_H

main.cpp

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; int main() { LinkList<int> sl; for(int i = 0; i < 5; i++) { sl.insert(0, i); sl.set(0, i*i); } for(int i = 0; i < sl.length(); i++) { int e = 0; if(sl.get(i, e)) { cout << e << endl; } } cout << endl; sl.clear(); for(int i = 0; i < sl.length(); i++) { cout << sl.get(i) << endl; } return 0; }

2、单链表的具体实现

问题 头结点是否存在隐患？实现代码是否需要优化？

头结点的隐患

代码优化

LinkList 的实现：

#ifndef LINKLIST_H #define LINKLIST_H #include "List.h" #include "Exception.h" namespace DTLib { template <typename T> class LinkList : public List<T> { protected: struct Node : public Object { T value; Node* next; }; mutable struct : public Object { char reserved[sizeof(T)]; Node* next; } m_header; int m_length; Node* position(int i)const { Node* ret = reinterpret_cast<Node*>(&m_header); for(int p = 0; p < i; p++) { ret = ret->next; } return ret; } public: LinkList() { m_header.next = nullptr; m_length = 0; } bool insert(const T& e) { return insert(m_length, e); } bool insert(int i, const T& e) { bool ret = (i >= 0 && i <= m_length); if(ret) { Node* node = new Node(); if(node != nullptr) { Node* current = position(i); node->value = e; node->next = current->next; current->next = node; m_length++; } else { THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert the Linklist"); } } return ret; } bool remove(int i) { bool ret = (i >= 0 && i < m_length); if(ret) { Node* current = position(i); Node* toDel = current->next; current->next = toDel->next; delete toDel; m_length--; } return ret; } bool set(int i, const T& e) { bool ret = (i >= 0 && i < m_length); if(ret) { position(i)->next->value = e; } return ret; } T get(int i)const { T ret; if(get(i, ret)) { return ret; } else { THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is Invalid"); } } bool get(int i, T& e)const { bool ret = (i >= 0 && i < m_length); if(ret) { //这个函数是一个const成员函数，const成员函数内部的成员变量是只读的，所以我们不能直接赋值，解决方法是用mutable修饰成员变量m_header，使它可以被访问。 e = position(i)->next->value; } return ret; } int length()const { return m_length; } void clear() { while(m_header.next != nullptr) { Node* toDel = m_header.next; m_header.next = toDel->next; delete toDel; } m_length = 0; } ~LinkList() { clear(); } }; } #endif // LINKLIST_H

main.cpp

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; class Test { public: Test() { throw(0); } }; int main() { LinkList<Test>a; cout << "xiebs" << endl; LinkList<int> list; for(int i = 0; i < 5; i++) { list.insert(0, i); } for(int i = 0; i < list.length(); i++) { cout << list.get(i) << endl; } return 0; }

小结 — 通过类模板实现链表，包含 头结点成员 和 长度成员 — 定义结点类型，并通过堆中的节点对象构成链式存储 — 为了避免构成错误的隐患，头结点类型需要重新定义 — 代码优化是编码完成后必不可少的环节

position(0) 指向头结点，position(1) 指向首结点，position(1).value 是第0个结点的value值，position(1).next 指向第一个结点。以此类推。

position(i) ，对应于指针指向 i 前面那个结点。

所以指针指向尾结点就是 position(m_length - 1).next