c++链表问题。
设计一个算法,将一个带头结点的链表A分解成为两个带头结点的链表B和C,使得B表中含有A表中序号为奇数的元素,而C表中含有A表中序号为偶数的元素,且保持其相对顺序。我原本不打算麻烦大家的,但是教材里面关于链表的讲述实在是太少了。还请大家详细地讲解一下链表的建立,这是我最大的困扰。是C++,不是C语言。
#include <iostream> using namespace std; //链表的结点 template <typename T> struct Node { T m_Data; Node<T> *m_Next; Node(T nData, Node<T> *nNext=NULL) { m_Data = nData; m_Next = nNext; } Node() { m_Next = NULL; } }; //链表类 template <typename T> class CLinkList { private: Node<T> *m_Head;//链表头 int m_Length;//链表的长度 public: CLinkList() {//创建带头结点的单链表 m_Head = new Node<T>; m_Length = 0; } //获取链表的长度 int GetLength() { return m_Length; } //是否为空链表 //空 返回true //非空 返回false bool IsEmpty() { return 0==m_Length; } //在指定的结点后面插入一个结点 //成功 则返回插入的结点的地址 //失败 则返回NULL Node<T>* InsertNode(T nItem, Node<T> *nNode=NULL) { if (NULL == nNode) { nNode = this->m_Head; } ++m_Length; return nNode->m_Next = new Node<T>(nItem, nNode->m_Next); } //在指定的结点后面删除一个结点 //删除成功 返回true //删除失败 返回false bool DeleteNode(Node<T> *nNode) { if (NULL == nNode) { return false; } if (NULL == nNode->m_Next) { return false; } Node<T> *tmp = nNode->m_Next; nNode->m_Next = tmp->m_Next; delete tmp; --m_Length; return true; } //打印函数 void Print() { Node<T> *tmp = m_Head->m_Next; while (NULL != tmp) { cout << tmp->m_Data << " "; tmp = tmp->m_Next; } cout << endl; } //析构函数 ~CLinkList() { while (!IsEmpty()) { DeleteNode(m_Head); } delete m_Head; } }; int main() { CLinkList<int> *iList = new CLinkList<int>; CLinkList<char> *cList = new CLinkList<char>; int i do { cout << "输入要插入的整数以-1终结输入:"; cin >> i; if (-1 == i) { break; } iList->InsertNode(i); }while (true); cout << "\t输出单链表:"; iList->Print(); char c; do { cout << "输入要插入的字符以#终结输入:"; cin >> c; if ('#' == c) { break; } cList->InsertNode(c); }while (true); cout << "\t输出单链表:"; cList->Print(); return 0; } 输入要插入的整数以-1终结输入:9 输入要插入的整数以-1终结输入:8 输入要插入的整数以-1终结输入:7 输入要插入的整数以-1终结输入:6 输入要插入的整数以-1终结输入:5 输入要插入的整数以-1终结输入:4 输入要插入的整数以-1终结输入:3 输入要插入的整数以-1终结输入:2 输入要插入的整数以-1终结输入:1 输入要插入的整数以-1终结输入:-1 输出单链表:1 2 3 4 5 6 7 8 9 输入要插入的字符以#终结输入:f 输入要插入的字符以#终结输入:e 输入要插入的字符以#终结输入:d 输入要插入的字符以#终结输入:c 输入要插入的字符以#终结输入:b 输入要插入的字符以#终结输入:a 输入要插入的字符以#终结输入:# 输出单链表:a b c d e f 请按任意键继续. . .