// C++学习笔记_14 迭代器、与容器无关的算法函数 #include "stdafx.h" #include<iostream> #include<string> #include"List.h" //这是一个单向链表类 #include"DbList.h" //这是一个双链表类 using namespace std; void TestString() { string ss = "Hello world!"; string::iterator it; //定义一个迭代器变量 //迭代器：相当于一个指针，指向 ss 内部的字符 cout << "ss:" << ss << endl; for (it = ss.begin(); it != ss.end(); it++) { // it = ss.begin()：先让 it 指向 ss 的第一个字符， // cout << *it ：输出这个字符 // it++ ：让 it 指向下一个字符。 直到末尾位置 循环结束 cout << *it << endl; } return; } template<typename T> void PrintList_0(CList<T> &tList) { for (int i = 0; i < tList.size(); i++){ cout << tList.getValue(i) << ","; } cout << "\b " << endl; // \b 退格，去掉末尾的逗号 } template<typename T> void PrintList_0(CDbList<T> &tList) { for (int i = 0; i < tList.size(); i++){ cout << tList.getValue(i) << ","; } cout << "\b " << endl; } //两个函数，除了入参类型不一样，代码实现都是一样的 //---》合并成一个 模板函数 //这个 T 可以是 CList<int>， CDbList<int> , CList<string>, ..... template<typename T> void PrintList_1(T &tList) { for (int i = 0; i < tList.size(); i++){ cout << tList.getValue(i) << ","; } cout << "\b " << endl; // \b 退格，去掉末尾的逗号 } //如果，我们想对 list 中存字符串的话，每个字符串换行输出，存整数或其他的还是不变 //----》偏特化 //--> 我们需要把 CList，CDbList ---》用一个模板来替代 //--> 把里面存的东西 int ，string, ... --> 也用一个模板来替代 //模板嵌套：第一个模板参数 CL， 第二个模板参数 T // template <typename T0> class CL 表示 CL 这个模板，本身就是一个模板类 // ---》template <typename T0> 用于声明 CL 是一个模板类，包含 1 个模板参数 T0 // ---》和 函数声明很类似，这里 T0 不起作用，可以省略 template<template <typename T0> class CL, typename T> void PrintList(CL<T> &tList) { for (int i = 0; i < tList.size(); i++){ cout << tList.getValue(i) << ","; } cout << "\b " << endl; // \b 退格，去掉末尾的逗号 } //对 string 做特化 template<template <typename T0> class CL> void PrintList(CL<string> &tList) { for (int i = 0; i < tList.size(); i++){ cout << tList.getValue(i) << endl; } cout << "\b " << endl; // \b 退格，去掉末尾的逗号 } //观察 PrintList 函数： for 循环，依次 getValue //每次 getValue 都需要从 pHead 重新往后找 //--》我们使用这个函数输出链表元素，有个问题： //效率低：输出第 M 个元素，需要从 pHead 后移 M 次 // 总共输出 N 条数据，需要查找次数为 1+2+3+...+N = N*(N-1)/2 //CList， CDbList 都需要实现getValue 函数名，入参等必须要一样，否则不能写成PrintList模板函数 //===> 解决方式： 迭代器 // 用一个指针指向元素，++ 操作自动移动到下一个元素 // --》自己来实现一个迭代器 //实现方式 //迭代器，其实是容器内部的一个类。这个类中定义一个指针指向节点的值 // 他重载 ++ 操作，让这个类的对象指向下一个节点的值 //迭代器隐藏了数据的存储方式 //使用迭代器，可以实现算法函数，可以编写与类型无关的函数 void TestList() { CList<int> iList; CDbList<int> dList; CList<string> sList; int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8 }; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){ iList.insert(i, arr[i]); dList.insert(i, arr[i]); sList.insert(i, string(5, 'A' + i)); } //接下来我们做输出 iList.Print(); dList.Print(); //如果我们想以逗号隔开？ //或者说 每行输出 4 个，每 4 个换一行输出？ //等等 //每个人都想按照自己格式输出，一般我们写一个链表，不会实现 输出的操作(调试才写这个) //--》通过 getValue 来输出 cout << "iList:"; //PrintList_1(iList); PrintList(iList); cout << "dList:"; //PrintList_1(dList); PrintList(dList); cout << "sList:"; PrintList(sList); } //使用自定义的迭代器： void TestIterator() { CList<int> iList; CList<int>::iterator it; int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8 }; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){ iList.insert(i, arr[i]); } for (it = iList.begin(); it != iList.end(); it++){ cout << *it << ","; } cout << endl; } int _tmain(int argc, _TCHAR* argv[]) { //TestString(); //TestList(); TestIterator(); system("pause"); return 0; } //作业：实现 CDbList 的迭代器
//List.h //#pragma once 这是微软的，不是通用的 #ifndef __LIST_H__ #define __LIST_H__ #include"stdafx.h" #include"stdlib.h" //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 reverse(); // 链表逆序 void Print() //遍历链表数据 { Node *pNode = pHead->pNext; while (pNode){ cout << pNode->data << " "; pNode = pNode->pNext; } cout << endl; } /// public: class iterator { friend class CList; private: Node *pNode; //指向某个节点的指针 //构造为什么要定义成private？ //-->做隐藏：外部不可见 ( pNode 在外部是不能用的) iterator(Node *pTmp) :pNode(pTmp){} public: //重载 ++，--，==, !=, * 等运算符 （这里单向链表没有--） iterator(){} // it++ 和 ++it 怎么区分 ？ iterator operator ++ () // ++it (前++) { pNode = pNode->pNext; //节点后移 return *this; //返回自己 } iterator operator ++ (int) //增加一个哑元 --》后++ //理解方式：这里 有个int，表示 ++ 连接两个变量 // () 内的东西作为第二个变量 //这里理解为 it ++ (哑元) --》 就是 it++ { iterator itTmp = *this; pNode = pNode->pNext; return itTmp; } //判断两个迭代器是否指向同一个节点 bool operator == (const iterator &it){return pNode == it.pNode;} bool operator != (const iterator &it){return pNode != it.pNode;} //重载 * --> 取节点内存储的值！！！ , 返回引用 (可以通过它修改元素) T& operator * (){return pNode->data;} //要不要重载 "->" ? // it->xxx 会被编译器解释 为 (*it).xxx }; public: //begin 和 end 是 CList的成员函数，不是 iterator的 iterator begin() { //返回iterator对象，这个对象的 pNode 指向CList的第一个节点 //iterator(Node*) 是iterator的私有构造函数，外部类 CList 不能调用 //-->解决方法: 把 CList 声明成 iterator 友元类 return iterator(pHead->pNext); } iterator end() {return iterator(NULL);} }; //模板类成员函数在外部实现，需要加上模板声明 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) { 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) { 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) { //越界判断 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 的下一个节点 //1：把下一个待删除节点保存到 pHead->pNext 中 pHead->pNext = pNode->pNext; //2：删除节点 delete pNode; //进入下一个循环，待删除节点后移 pNode = pHead->pNext; } iSize = 0; return; } template<typename T> void CList<T>::reverse() { //如果 链表节点个数小于两个，那么逆序结果不变 if (iSize < 2){ return; } Node *pNode = pHead->pNext; //待翻转节点（第0个节点） Node *pTmpNode = pNode->pNext; //下一个待翻转节点（第一个节点） //第 0 个节点的 pNext 指向NULL, 指向前，先保存它的下一个节点 pNode->pNext = NULL; pNode = pTmpNode; //从第一个节点开始到最后一个节点，依次把 pNext 指向前面那个节点 while (pNode) { pTmpNode = pNode->pNext; //保存下一个待翻转节点(后节点) //翻转节点 pNode->pNext = pHead->pNext; //重置变量，进入下一轮循环 pHead->pNext = pNode; //下一个待翻转节点指向的目标节点(前节点) pNode = pTmpNode; //下一个待翻转节点(中节点) } //pHead 的 pNext 指向最后一个节点 //--> 在循环体内已经解决了 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) { } #endif
