注册 登录
编程论坛 C++教室

c++链表问题。

樱花雾海 发布于 2012-05-16 11:15, 397 次点击
     设计一个算法,将一个带头结点的链表A分解成为两个带头结点的链表B和C,使得B表中含有A表中序号为奇数的元素,而C表中含有A表中序号为偶数的元素,且保持其相对顺序。
我原本不打算麻烦大家的,但是教材里面关于链表的讲述实在是太少了。还请大家详细地讲解一下链表的建立,这是我最大的困扰。是C++,不是C语言。
5 回复
#2
寒风中的细雨2012-05-16 21:13
只是创建链表?
#3
寒风中的细雨2012-05-16 22:22
程序代码:
#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
请按任意键继续. . .
#4
BianChengNan2012-05-18 09:41
楼上威武
#5
寒风中的细雨2012-05-18 17:38
回复 4楼 BianChengNan
这种帖子 令回答的人心寒~~~
#6
樱花雾海2012-05-19 15:00
回复 3楼 寒风中的细雨
谢谢您的帮助
1