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

简介: 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;
}
//作业:实现双向链表模板
相关文章
|
6天前
|
存储 C++ 容器
C++STL(标准模板库)处理学习应用案例
使用C++ STL,通过`std:vector`存储整数数组 `{5, 3, 1, 4, 2}`,然后利用`std::sort`进行排序,输出排序后序列:`std:vector&lt;int&gt; numbers; numbers = {5, 3, 1, 4, 2}; std:sort(numbers.begin(), numbers.end()); for (int number : numbers) { std::cout &lt;&lt; number &lt;&lt; &quot; &quot;; }`
14 2
|
17天前
|
编译器 C++
C++入门指南:10分钟带你快速了解模板究竟是什么(建议收藏!!)
C++入门指南:10分钟带你快速了解模板究竟是什么(建议收藏!!)
25 0
|
17天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
20天前
|
安全 算法 编译器
【C++ 泛型编程 进阶篇】深入探究C++模板参数推导:从基础到高级
【C++ 泛型编程 进阶篇】深入探究C++模板参数推导:从基础到高级
239 3
|
20天前
|
存储 算法 编译器
【C++ TypeName用法 】掌握C++中的TypeName:模板编程的瑞士军刀
【C++ TypeName用法 】掌握C++中的TypeName:模板编程的瑞士军刀
233 0
|
20天前
|
安全 算法 C++
【C++泛型编程 进阶篇】模板返回值的优雅处理(二)
【C++泛型编程 进阶篇】模板返回值的优雅处理
31 0
|
20天前
|
安全 算法 编译器
【C++泛型编程 进阶篇】模板返回值的优雅处理(一)
【C++泛型编程 进阶篇】模板返回值的优雅处理
40 0
|
20天前
|
存储 算法 编译器
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
44 1
|
20天前
|
机器学习/深度学习 算法 编译器
【C++ 泛型编程 中级篇】深度解析C++:类型模板参数与非类型模板参数
【C++ 泛型编程 中级篇】深度解析C++:类型模板参数与非类型模板参数
46 0
|
20天前
|
设计模式 程序员 C++
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
192 2