author: 浥青城
pubDatetime: 2023-1-17T17:25:04
title: 数据结构之单链表以及改良
postSlug: 数据结构之单链表以及改良
featured: false
draft: false
tags:
- 数据结构
description: 用C++面对对象的思想重新构建单链表类
在学完单链表后，我发现网上的代码大多是以C语言的面向过程的思想写就的，于是我想用C++面对对象的思想重新构建一下单链表类。经过对照所有能获取的资料，总结了一共两套代码，第一套是体现的基本的链表思想，第二套则尝试融入更多带有C++特性的东西。
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<iostream>
using namespace std;
const int maxSize = 100;//设置链表最大尺寸
template<class T>
class Single_Llist //单链表
{
public:
struct Node
{
T data;
Single_Llist<T>::Node* next;
explicit Node(Single_Llist<T>::Node* ptr = nullptr) :data(T{}), next(ptr) {}
Node(const T& item, Single_Llist<T>::Node* ptr = nullptr) :data(item), next(ptr) {}
};
Single_Llist()//构造函数
{
head = new Single_Llist<T>::Node;
head->next = nullptr;
tail = nullptr;
}
Single_Llist(const Single_Llist<T>& L);//拷贝构造函数
~Single_Llist()
{
clear();
}
void clear(); //清空链表
size_t getSize() const;//返回链表长度
typename Single_Llist<T>::Node* getHead() const { return head; }//返回头指针
typename Single_Llist<T>::Node* getTail() const;//返回尾节点
typename Single_Llist<T>::Node* getFirst() const { return head->next; }//返回第一个节点
Single_Llist<T>* Search(const T& x) const;//查找
Single_Llist<T>* Locate(size_t i) const;//定位(第i个节点)
bool getData(int i, T& x) const;//取第i个节点的值
bool setData(int i, const T& x);//改变第i个节点的值
bool Insert(int i, const T& x);//在第i个节点前插入x(可以通过next域实现在结点后插入)
bool Remove(int i, T& x);//删除第i个节点
bool IsEmpty() const
{
return head->next == nullptr;
}
bool IsFull() const { return maxSize <= getSize() ? true : false; }
void Sort();// 可以改进一下，归并排序
void CreateList(T endTag);//前插法创建单链表
void CreateList_byback(T endTag);//后插法创建单链表
void print();//打印单链表
void Merge(Single_Llist<T>& LA, Single_Llist<T>& LB);//归并两条单链表并有序排列（去除重复元素）,有点类似于构造函数
Single_Llist<T>& operator=(const Single_Llist<T>& rhs);
protected:
Single_Llist<T>::Node* head;
Single_Llist<T>::Node* tail;
};
template <class T>
inline Single_Llist<T>::Single_Llist(const Single_Llist<T>& L)
{
head = tail = new Single_Llist<T>::Node;
Single_Llist<T>::Node* desptr = head;
T value;
Single_Llist<T>::Node* srcptr = L.getFirst();
while (srcptr != nullptr)
{
value = srcptr->data;
desptr->next = new Single_Llist<T>::Node(value);
srcptr = srcptr->next;
desptr = desptr->next;
tail = tail->next;
}
desptr->next = nullptr;
}
template <class T>
inline Single_Llist<T>& Single_Llist<T>::operator=(const Single_Llist<T>& rhs)
{
head = tail = new Single_Llist<T>::Node;
Single_Llist<T>::Node* desptr = head;
T value;
Single_Llist<T>::Node* srcptr = rhs.getFirst();
while (srcptr != nullptr)
{
value = srcptr->data;
desptr->next = new Single_Llist<T>::Node(value);
srcptr = srcptr->next;
desptr = desptr->next;
tail = tail->next;
}
desptr->next = nullptr;
return *this;
}
template <class T>
inline void Single_Llist<T>::clear()
{
Single_Llist<T>::Node* p = head->next;
while (p != nullptr)
{
Single_Llist<T>::Node* q = p->next;
delete p;
p = q;
}
head->next = nullptr;
tail = head;
}
template <class T>
inline size_t Single_Llist<T>::getSize() const
{
size_t count = 0;
Single_Llist<T>::Node* p = head->next;
while (p != nullptr)
{
count++;
p = p->next;
}
return count;
}
template <class T>
inline typename Single_Llist<T>::Node* Single_Llist<T>::getTail() const
{
Single_Llist<T>::Node* p = head->next;
while (p->next != nullptr)
{
p = p->next;
}
return p;
}
template <class T>
inline Single_Llist<T>* Single_Llist<T>::Search(const T& x) const
{
Single_Llist<T>::Node* p = head->next;
while (p != nullptr)
{
if (p->data == x)
{
return p;
}
p = p->next;
}
return nullptr;
}
template <class T>
inline Single_Llist<T>* Single_Llist<T>::Locate(size_t i) const
{
Single_Llist<T>::Node* p = head->next;
size_t count = 0;
while (p != nullptr)
{
count++;
if (count == i)
{
return p;
}
p = p->next;
}
return nullptr;
}
template <class T>
inline bool Single_Llist<T>::getData(int i, T& x) const
{
Single_Llist<T>::Node* p = head->next;
size_t count = 0;
while (p != nullptr)
{
count++;
if (count == i)
{
x = p->data;
return true;
}
p = p->next;
}
return false;
}
template <class T>
inline bool Single_Llist<T>::setData(int i, const T& x)
{
Single_Llist<T>::Node* p = head->next;
size_t count = 0;
while (p != nullptr)
{
count++;
if (count == i)
{
p->data = x;
return true;
}
p = p->next;
}
return false;
}
template <class T>
inline bool Single_Llist<T>::Insert(int i, const T& x)
{
Single_Llist<T>::Node* p = head;
size_t count = 0;
while (p != nullptr)
{
count++;
if (count == i)
{
Single_Llist<T>::Node* q = new Single_Llist<T>::Node;
q->data = x;
q->next = p->next;
p->next = q;
return true;
}
p = p->next;
}
return false;
}
template <class T>
inline bool Single_Llist<T>::Remove(int i, T& x)
{
Single_Llist<T>::Node* p = head;
size_t count = 0;
while (p != nullptr)
{
count++;
if (count == i)
{
Single_Llist<T>::Node* q = p->next;
x = q->data;
p->next = q->next;
delete q;
return true;
}
p = p->next;
}
return false;
}
template <class T>
inline void Single_Llist<T>::Sort()
{
int flag = 0;
while (flag == 0)
{
flag = 1;
Single_Llist<T>::Node* p = head->next;
while (p->next != nullptr)
{
if (p->data > p->next->data)
{
T temp = p->data;
p->data = p->next->data;
p->next->data = temp;
flag = 0;
}
p = p->next;
}
}
}
template <class T>
inline void Single_Llist<T>::CreateList(T endTag)
{
cout << "前插法" << endl;
cout << "输入数据，以" << endTag << "结束" << endl;
T val;//停止输入的标志:endTag
clear();
cin >> val;
bool flag = false;
while (val != endTag)
{
Single_Llist<T>::Node* newNode = new Single_Llist<T>::Node(val);
if (newNode == nullptr) cout << "内存分配失败" << endl;
newNode->next = head->next;
head->next = newNode;
if (flag == false)
{
tail = head->next;
tail->next = nullptr;
flag = true;
}
cin >> val;
}
}
template <class T>
inline void Single_Llist<T>::CreateList_byback(T endTag)
{
cout << "后插法" << endl;
cout << "输入数据， 以 " << endTag << "结束" << endl;
T val;
clear();
cin >> val;
while (val != endTag)
{
Single_Llist<T>::Node* newNode = new Single_Llist<T>::Node(val);
if (newNode == nullptr) cout << "内存分配失败" << endl;
tail->next = newNode;
tail = newNode;
cin >> val;
}
tail->next = nullptr;
}
template <class T>
inline void Single_Llist<T>::print()
{
Single_Llist<T>::Node* p = head->next;
while (p != nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
template <class T>
inline void Single_Llist<T>::Merge(Single_Llist<T>& LA, Single_Llist<T>& LB)
{
LA.Sort(), LB.Sort();
Single_Llist<T>::Node* current = head;
Single_Llist<T>::Node* ptra = LA.getFirst();
Single_Llist<T>::Node* ptrb = LB.getFirst();
while (ptra && ptrb)
{
T x, y;
x = ptra->data;
y = ptrb->data;
if (x < y)
{
current->next = new Single_Llist<T>::Node(x);
ptra = ptra->next;
current = current->next;
}
else
if (x > y)
{
current->next = new Single_Llist<T>::Node(y);
ptrb = ptrb->next;
current = current->next;
}
else
{
current->next = new Single_Llist<T>::Node(x);
ptra = ptra->next;
ptrb = ptrb->next;
current = current->next;
}
}
while (ptra)
{
current->next = new Single_Llist<T>::Node(ptra->data);
ptra = ptra->next;
current = current->next;
tail = ptra;
}
while (ptrb)
{
current->next = new Single_Llist<T>::Node(ptrb->data);
ptrb = ptrb->next;
current = current->next;
tail = ptrb;
}
}
中间略微总结一下我遇到的问题吧，首先就是发现使用模板后.h文件和.cpp文件链接不上，这算是模板类特有的写法，因为当实例化一个模板时，编译器必须看到模板确切的定义，而不仅仅是它的声明。因此，最好的办法就是将模板的声明和定义都放置在同一个.h文件中，在实现时用inline修饰保证函数符号只有一个,当然用static修饰也是可以的。(需要注意，inline是不能用在普通类普通链接实现中的，新标准取消了默认情况下inline作为内联函数的含义)
关于这一点我还发现了一个算是邪门歪道的方法，就是如果要写正常的翻译单元，也就是.h和.cpp文件，正常链接也是可以的，只需要在主函数里从原来的包含翻译单元头文件改成包含翻译单元源文件就行，但是这个方法具有很大的局限性，就是如果翻译单元里有除了模板函数以外的具体函数，那么就会报错重定义了符号。因为编译是按源文件编译，include的作用仅仅是拷贝文件到指定位置，要是在主函数(.cpp)里包含.cpp，相当于被包含的翻译单元中的函数被编译了两遍。而模板函数能成为例外的原因，就在于inline关键字，是作用于全局的，保证在函数全名相同(namespace::classname::funcname)的情况下，同名函数只被编译一次，只保留一个版本。
参与讨论
(Participate in the discussion)
参与讨论