// 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; } //作业：实现双向链表模板
