C++学习笔记_12 单向链表和单向链表模板 2021-04-29

// C++学习笔记_12 单向链表和单向链表模板
#include<cstdio> 
#include<iostream>
#include<string>
using namespace std;
//C 语言链表两个问题：
//1: 定义链表的时候，我们需要指定链表中存放的数据类型
//   不同数据类型的链表，需要分别实现
//2: LIST *pNode;  语义容易引起误解
//   它既可以代表一个节点，也可以代表一个链表
//--》1：通过模板类来实现。2：通过封装Node来规避歧义
//这里：头结点不放数据，仅仅表示这是链表的引子
template<typename T>
class CList
{
private:
    class Node
    {
    public:
        T data;
        Node *pNext;
        Node(T t_data) :data(t_data), pNext(NULL){}
    };
    Node *pHead;  //这是链表的头结点
    size_t iSize; //链表的长度(节点个数)
public:
    //T() : 生成一个T的默认值(比如 int 生成一个0，string 生成一个空串，等等)
    CList() :pHead(new Node(T())), iSize(0){}
    ~CList() { clear(); delete pHead;}//释放整个链表 申请的内存
    size_t size() { return iSize; } //获取链表长度
    //增删改查
    int insert(size_t pos, T t_data);
    int erase(size_t pos);
    int modify(size_t pos, T t_data);
    T& getValue(size_t pos);
    void clear(); //清空节点，保留头结点
    void Print() { //遍历链表数据
        Node *pNode = pHead->pNext;
        while (pNode){
            cout << pNode->data << " ";
            pNode = pNode->pNext;
        }
        cout << endl;
    }
};
//模板类成员函数在外部实现，需要加上模板声明
template<typename T>
int CList<T>::insert(size_t pos, T data)//在pos位置前插入节点，节点数据是 data
{
    //  pos 从 0 开始编号
    if (pos > iSize){return -1;}//越界
    Node *pNewNode = new Node(data);
    //找插入位置前面那个节点
    size_t i = 0;
    Node *pNode = pHead; //起始节点
    while (i < pos){
        pNode = pNode->pNext;
        i++;
    }
    //把 pNewNode 插入在 pNode 的后面
    //1：pNewNode 的 pNext 赋值， 指向 pNode 的下一个元素
    pNewNode->pNext = pNode->pNext;
    //2：把 pNode 的 pNext 指向 pNewNode
    pNode->pNext = pNewNode;
    iSize++;
    return 0;
}
template<typename T>
int CList<T>::erase(size_t pos)//删除在pos位置的节点
{
    if (pos > iSize - 1){ return -1; }//越界，节点不存在
    //查找待删除节点的上一个元素、
    size_t i = 0;
    Node *pNode = pHead; //起始节点
    while (i < pos){
        pNode = pNode->pNext;i++;
    }
    Node *pDelNode = pNode->pNext; //待删除节点
    //删除元素，只需要把 pNode 指向 pDelNode 的下一个节点就可以了
    pNode->pNext = pDelNode->pNext;
    delete pDelNode;//释放节点空间
    iSize--;
    return 0;
}
template<typename T>
int CList<T>::modify(size_t pos, T data)//在pos位置修改节点数据为 data
{
    if (pos > iSize - 1) { return -1;}//越界，节点不存在
    //这个时候跟上面有点不一样：不再找上一个节点，直接找需要修改的节点
    int i = 0;
    Node *pNode = pHead->pNext; //从第 0 个节点开始找
    while (i < pos){
        pNode = pNode->pNext; i++;
    }
    pNode->data = data;
    return 0;
}
template <typename T>
T& CList<T>::getValue(size_t pos)//获取pos位置节点的data
{
    //越界判断
    if (pos > iSize - 1){
        //return -1;//这个显然不行，类型和返回值类型不匹配
        //事实上这里返回什么都不合适
        //1：写 assert  --》 比较耗资源，一般在调试的时候使用
        //2：抛出异常   --》 C++比较正常的解决方法 throw out_of_range;
        //3：不做任何处理 --》C 语言的一般处理方式
        //              我们已经对外提供了 size() 这个接口
        //              使用者完全可以判断是否越界 
    }
    //这个时候跟上面有点不一样：不再找上一个节点，直接找需要修改的节点
    int i = 0;
    Node *pNode = pHead->pNext; //从第 0 个节点开始找
    while (i < pos){
        pNode = pNode->pNext;
        i++;
    }
    return pNode->data;
}
template <typename T>
void CList<T>::clear()//释放所有节点 （头结点除外）
{ 
    if (iSize == 0){return;}
    Node *pNode = pHead->pNext;
    while (pNode){ //把pNode脱链， pHead 的pNext 指向 pNode 的下一个节点
        pHead->pNext = pNode->pNext; //1：把下一个待删除节点保存到 pHead->pNext中
        delete pNode; //2：删除节点
        //进入下一个循环，待删除节点后移
        pNode = pHead->pNext;
    }
    iSize = 0;
    return;
}
//C 语言方式实现链表：单链表 -- 保存整数
//我们写链表有两种方式
// 第一种：头结点不放数据，仅仅指明 这是链表的引子
// 第二种：头结点放数据，和正常节点一样
// 这里我们写第二种情况：头结点放数据。
//节点的结构体
typedef struct tagList
{
    int data;                   //数据部分
    struct tagList *pNext;      //指向下一个节点的指针
}LIST;
//增删改查
//初始化: 传入的是 已经存在 的 LIST 对象的地址
int Init_List(LIST **ppList)
{
    *ppList = (LIST*)malloc(sizeof(LIST));
    (*ppList)->data = 0;
    (*ppList)->pNext = NULL;
    return 0;
}
//在 pHead 这个链表中，第 pos 个节点位置，插入节点，节点数据是 data
int Insert_List(LIST **ppHead, int pos, int data)
{
    LIST *pPos = *ppHead;
    int i = 0;
    //如果 pos == 0， 新插入节点做为头结点
    if (pos == 0){
        LIST *pNode = (LIST*)malloc(sizeof(LIST));
        if (pNode == NULL){   return -1;}
        pNode->data = data;
        pNode->pNext = *ppHead;
        *ppHead = pNode;  //新的头结点
        return 0;
    }
    //查找节点的时候，需要考虑是否越界
    //      越界解决：1- 插入失败，2- 插入末尾
    //还需要考虑插入位置，插入 pos 节点前 --》找 pos 前面那个节点
    while (i < pos - 1){
        if (pPos == NULL) { return -1;} //越界
        pPos = pPos->pNext;
        i++;
    }
    //
    LIST *pNode = (LIST*)malloc(sizeof(LIST));
    if (pNode == NULL){return -1;}
    pNode->data = data;
    //新增节点插入 pPos 后面
    pNode->pNext = pPos->pNext; //把 pPos 的下一个节点 作为 pNode 的下一个节点
    pPos->pNext = pNode;   // pPos 的下一个节点指向 pNode
    //这两行不能调换
    return 0;
}
//销毁链表：释放内存
void Destroy_List(LIST **ppHead) { }
void TestList()
{
    CList<int>    iList;
    CList<string> sList;
    for (int i = 0; i < 5; i++){
        iList.insert(i, i*i);
        sList.insert(i, string(3, 'A' + i));
    }
    iList.insert(2, 99);
    iList.erase(4);
    iList.modify(0, 88);
    cout << "iList:";
    iList.Print();
    cout << "sList:";
    sList.Print();
    cout << endl;
    //最后一个数据
    cout << iList.getValue(iList.size() - 1) << endl;
    //getValue 返回一个引用 --> 可以当左值使用，修改成员
    //--》我们可以不要 modify成员
    iList.getValue(0) = 77;
    iList.Print();
    return;
}
int main()
{
    TestList();
    system("pause");
  return 0;
}
//作业：实现双向链表模板