栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

如此简单,我怎么被干懵了

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

如此简单,我怎么被干懵了

使用标准模板库解题
#include 
#include 
#include 
using namespace std;
void print(list & ls)
{
    list::iterator it;
    for(it=ls.begin();it!=ls.end();it++)
        cout<< setw(4) << *it;
    cout << endl;
}
int main()
{
    int a[4] = {2,4,6,8};
    int b[4] = {1,3,5,7};
    list  l1(a,a+4);
    list  l2(b,b+4);
    list  l3(0);
    l3.merge(l1);
    l3.merge(l2);
    l3.sort();
    print(l3);

    return 0;
}
面向过程解题
#include 
#include 
using namespace std;

// [2,4,6,8];
// [1,3,5,7];

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}


    ~ListNode()
    {
        cout << "析构" << val << endl;
        if (next != nullptr)
            delete next;
        next = nullptr;
    };
};

ListNode* merge_two_sorted_list(ListNode* l1,ListNode* l2){

    ListNode *tempList = nullptr;
    while(l1 != nullptr )
            {
                tempList = new ListNode(l1->val, tempList);
                l1 = l1->next;
            }
    while(l2 != nullptr )
        {
            tempList = new ListNode(l2->val, tempList);
            l2 = l2->next;
        }
    l1 = nullptr;//指针用完指空
    l2 = nullptr;

    if(tempList != nullptr)
    {
        ListNode* sampleValptr = tempList->next;
        ListNode* compareValptr = tempList;
        while(sampleValptr != nullptr)
        {
            int tempValue = 0;
            while(compareValptr != sampleValptr)
                {
                    if(compareValptr->val > sampleValptr->val)
                    {
                        tempValue = compareValptr->val;
                        compareValptr->val = sampleValptr->val;
                        sampleValptr->val = tempValue;
                    }
                    compareValptr = compareValptr->next;    //取下一个比较值
                }
            compareValptr = tempList;     //重置比较比较值指针
            sampleValptr = sampleValptr->next;   //取下一个采样值
         }

        compareValptr =nullptr;//指针用完指空
        sampleValptr = nullptr;
    }

    return tempList;
}

int main()
{
    int a[4] = {2,4,6,8};
    int b[4] = {1,3,5,7};

    ListNode *List1 = nullptr;
    ListNode *List2 = nullptr;

    int i = 0;
    while(i < 4)
    {
        List1 = new ListNode(a[i], List1);
        List2 = new ListNode(b[i], List2);
        i = i+1;
    }

    ListNode* List = merge_two_sorted_list(List1,List2);
    ListNode* accessNode = List; //访问List用的指针

    while(accessNode != nullptr)
    {
        cout<< accessNode->val << " -> ";
        accessNode = accessNode->next;
    }
    cout<< "nullptr" << endl;


    accessNode = nullptr;

    delete List1;
    delete List2;
    delete List;

    List1 = nullptr;
    List2 = nullptr;
    List = nullptr;

    return 0;

}
面向对象解题
#include 
using namespace std;

class ListNode
{
private:
    int nodeData;   //节点数据
    ListNode* nextNodePointer;  //指针指向下一个节点的首地址

public:
    ListNode(int data = 0, ListNode* next = nullptr) : nodeData(data), nextNodePointer(next){};
    ListNode(const ListNode& node) : nodeData(node.nodeData), nextNodePointer(node.nextNodePointer){}

    ListNode* CreateNode(int data)
    {
        nextNodePointer = new ListNode(data);
        if (nextNodePointer != nullptr)    //如果不为空,则结点开辟空间成功
            nextNodePointer->nextNodePointer = nullptr;
        else    //如果是空,则结点开辟空间失败了
            cout << "申请节点内存失败" << endl;
        return nextNodePointer; //无论开辟成功或则失败,在列表中插入中判断
    }

    

    ~ListNode()
    {
        while (nextNodePointer != nullptr)//因为lastNodePointerNode->nextNodePointer==nullptr,所以进不来
        {
            ListNode* prelastNodePointerNode = this;//只有一个节点时,prelastNodePointerNode->nextNodePointer= nullptr,即要把头结点的下一个元素置空
            ListNode* lastNodePointerNode = prelastNodePointerNode->nextNodePointer;

            while (lastNodePointerNode->nextNodePointer != nullptr) {//如果一个节点的下一个节点是空,那他就是最后一个节点
                prelastNodePointerNode = lastNodePointerNode;
                lastNodePointerNode = lastNodePointerNode->nextNodePointer;//让lastNodePointerNode等于下一个lastNodePointerNode
            }
            cout << "    析构节点:" << lastNodePointerNode->nodeData << endl;
            prelastNodePointerNode->nextNodePointer = nullptr;//将上一个节点的指针置空,代表这是最后一个数据
            delete lastNodePointerNode;//删除最后一个节点
            lastNodePointerNode = nullptr;
        }
    };

    friend class List;//链表要访问设置next指针,申请为友元类
};

class List
{
private:
    ListNode* headNodePointer;
    ListNode* lastNodePointer;

public:
    //构造初始化链表
    List(int initialListSize = 0)//initialListSize是初始化给定的链表长度
    {
        headNodePointer = lastNodePointer = new ListNode(0);//生成头节点,头结点包含链表长度数据
        if (headNodePointer != nullptr)
        {
            initialListSize = initialListSize > 0 ? initialListSize : 0;//如果用户指定链表长度为负数,那就直接默认长度是0
            while (initialListSize > 0)
            {
                bool successToInsertNode = ValueInsert(initialListSize);//判断节点有没有插入成功
                if (successToInsertNode == false)
                {
                    cout << "创建节点阶段异常,但是成功创建" << headNodePointer->nodeData << "个节点,请尝试插入操作" << endl;
                    break;
                }
                initialListSize = initialListSize - 1;
            }
            cout << "初始化完成,列表包含" << headNodePointer->nodeData << "个节点!" << endl;
        }
        else
        {
            cout << "生成头节点异常,已创建终止列表" << endl;
        }
    }

    List(const List& list)  //做深拷贝构造
    {
        headNodePointer = lastNodePointer = new ListNode(*list.headNodePointer);  //生成头节点,头结点包含链表长度数据

        if (headNodePointer != nullptr) //判断头节点是否成功生成
        {
            while(lastNodePointer->nextNodePointer != nullptr)
            {
                lastNodePointer->nextNodePointer =  new ListNode(*lastNodePointer->nextNodePointer);;
                if (lastNodePointer->nextNodePointer != nullptr)    //拷贝构造节点成功
                {
                    lastNodePointer = lastNodePointer->nextNodePointer;
                }
                else     //拷贝构造节点失败
                {
                    cout << "拷贝构造节点失败,已创建终止列表" << endl;
                };
            }
            cout << "初始化完成,列表包含" << headNodePointer->nodeData << "个节点!" << endl;
        }
        else
        {
            cout << "生成头节点异常,已创建终止列表" << endl;
        }
    }

    //向链表中插入元素
    bool ValueInsert(int data = 0)
    {
        lastNodePointer->nextNodePointer = lastNodePointer->CreateNode(data);
        if (lastNodePointer->nextNodePointer != nullptr)//判断节点有没有申请成功
        {
            headNodePointer->nodeData++;
            lastNodePointer = lastNodePointer->nextNodePointer;
            return true;
        }
        else
        {
            cout << "节点插入失败" << endl;
            return false;
        }

    }

    //遍历链表信息
    void Show()
    {
        cout << "遍历链表信息" << headNodePointer->nodeData << "元素:";
        ListNode* forward = headNodePointer;
        while (forward->nextNodePointer != nullptr) //如果不是最后一个元素
        {
            forward = forward->nextNodePointer; //切换下一个元素
            cout << forward->nodeData << "->";
        }
        cout << "nullptr" << endl;
    }

    //级联链表
    void Concatenate(const List& list){
        if(list.headNodePointer->nextNodePointer != nullptr)
        {
            ListNode* tempNode = list.headNodePointer->nextNodePointer;
            while(tempNode != list.lastNodePointer->nextNodePointer){
                lastNodePointer->nextNodePointer =  new ListNode(*tempNode);
                if (lastNodePointer->nextNodePointer != nullptr)    //分配节点成功
                {
                    lastNodePointer = lastNodePointer->nextNodePointer;
                    tempNode=tempNode->nextNodePointer;
                    headNodePointer->nodeData++;
                }
                else
                {
                    cout << "拷贝构造节点失败,已终止复制列表" << endl;
                    break;
                }
            }
            cout << "级联链表完成,当前链表包含" << headNodePointer->nodeData << "个节点!" << endl;
        }
        else
        {
            cout << "空表,无需级联" <nextNodePointer ;
        ListNode* compareValuePointer = headNodePointer->nextNodePointer;
        while (sampleValuePointer != lastNodePointer->nextNodePointer)  //链表中只有一个节点,直接不用比较了
        {
            while(compareValuePointer != sampleValuePointer)
            {
                if(compareValuePointer->nodeData > sampleValuePointer->nodeData)
                {
                    tempValue = compareValuePointer->nodeData;
                    compareValuePointer->nodeData = sampleValuePointer->nodeData;
                    sampleValuePointer->nodeData = tempValue;
                }
                compareValuePointer = compareValuePointer->nextNodePointer;//取下一个比较值
            }

            compareValuePointer = headNodePointer->nextNodePointer;     //重置比较比较值指针
            sampleValuePointer = sampleValuePointer->nextNodePointer;   //取下一个采样值
        };

    }

    //析构链表
    ~List()
    {
        cout << "析构链表开始" << endl;
        if (headNodePointer != nullptr)
            delete headNodePointer;//删除头结点,会调用节点的析构函数,调用节点的析构函数,会删除其他节点
        cout << "析构整个链表结束" << endl;
        headNodePointer = lastNodePointer = nullptr;
    }
};


int main()
{
    List l1(0);
    l1.ValueInsert(2);
    l1.ValueInsert(6);
    l1.ValueInsert(4);
    l1.ValueInsert(8);
    l1.Show();

    List l2(0);
    l2.ValueInsert(1);
    l2.ValueInsert(5);
    l2.ValueInsert(3);
    l2.ValueInsert(7);
    l2.Show();


    List l3(l1);
    l3.Concatenate(l2);
    l3.SelfSort();
    l3.Show();

}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/960207.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号