C++综合系列之模拟单链表模版

该篇有问题，正在修改中。。。

list.h

#ifndef _LIST_H_ #define _LIST_H_ #include<iostream> using namespace std; /**********************************************************************************/ /* 定义单链表结构的四种方式 */ /**********************************************************************************/ /**********************************************************************************/ /* 1. 友元类：在Node类中定义友元的方式，使List类可以访问结点的私有成员。 */ /**********************************************************************************/ //class Node //{ // friend class List; //private: // int value; // Node *next; //} //class List //{ //public: // //单链表具体操作 //private: // Node *head; //} /******************************************************************************************************/ /* 2. 内部类：在List内部定义Node类，但是Node的数据成员放在public部分，使List和Node均可以直接访问Node的成员。*/ /******************************************************************************************************/ //class List //{ //public: // //单链表具体操作 //private: // class Node // { // public: // int value; // Node *next; // } // Node *head; //} /******************************************************************************************/ /* 3. 继承：在Node类中把成员定义为protected，然后让List继承Node类，这样就可以访问Node类的成员。*/ /******************************************************************************************/ //class Node //{ //protected: // int value; // Node *next; //}; //class List : public Node //{ //public: // //单链表具体操作 //private: // Node *head; //} /***************************************************************************************************************/ /* 4. struct: 直接用struct定义Node类，因为struct的成员默认为公有数据成员，所以可直接访问（struct也可以指定保护类型）。*/ /***************************************************************************************************************/ //struct Node //{ // int data; // Node *next; //}; //class List //{ //public: // //单链表具体操作 //private: // Node *head; //} /**********************************************************************************/ /* 本文采用的是第一种友元类的方式 */ /**********************************************************************************/ //声明友元模版类（方法2.1） //template<class T> //class List; template<class T> class Node { public: Node() { // T v; // value = v; next = NULL; } Node(T v, Node<T> *ptr = NULL) { value = v; next = ptr; } //声明友元模版类（方法1） template<class E> friend class List; //声明友元模版类（方法2.2） //friend class List<T>; friend ostream &operator<<(ostream &out, Node &n) { out << n.value; return out; } private: T value; Node<T> *next; }; template<class T> class List { public: List() { head = new Node<T>; m_count = 0; } ~List() { clear(); } //获得链表的长度 int size() { m_count = 0; Node<T> *p = head; while ((p = p->next) != NULL) { m_count ++; } return m_count; } //从头部添加一个节点 void insert_front(T value) { Node<T> *pTemp = head->next; head->next = new Node<T>(value); head->next->next = pTemp; } //从尾部添加一个节点 void insert_end(T value) { Node<T> *p = head; while(p->next != NULL) p = p->next; p->next = new Node<T>(value); } //添加节点到指定位置 void insert_index(int index, T value) { if(index > size()) { cout << "index cause stack overflow." << endl; return; } Node<T> *p = head; for(int i = 1; i <= index - 1; i++)//index以第一个元素为参照计算偏移次数，并且从1开始计算索引 { p = p->next; } Node<T> *pTemp = p->next; p->next = new Node<T>(value); p->next->next = pTemp; } //反转倒置（递归） void reverse_recursive() { } //反转倒置（非递归） void reverse_nonrecursive() { } //清空链表（保留head节点） void clear() { Node<T> *pTemp = NULL; while(head->next != NULL)//head->next是关键 { pTemp = head->next;//临时变量保存头节点后面的节点，做删除用，如果直接删除将会丢失next节点指针，寻不到next节点 // head->next = pTemp->next;//将head的next指针指向head的next的next节点，不断丢弃头节点后面的节点，此处pTemp->next <=> head->next->next head->next = head->next->next; delete pTemp; } } //显示链表中所有数据 void display() { Node<T> *p = head; int count = 0; while((p = p->next) != NULL) { cout << "第" << ++count << "个节点为: " << *p << endl; } } private: Node<T> *head; //表头 int m_count; }; #endif

main.cpp

#include <iostream> #include "list.h" using namespace std; int main() { List<int> *list = new List<int>; list->insert_end(3); list->insert_end(4); list->display(); cout << "size: " << list->size() << endl; list->insert_front(1); list->display(); cout << "size: " << list->size() << endl; list->insert_index(4,2); list->display(); cout << "size: " << list->size() << endl; list->clear(); cout << "size: " << list->size() << endl; return 0; }