链表

目的:熟练掌握链表的建立及基本操作

问题描述:

1)实现链表的排序(升序)

2)实现两个有序链表的合并:A=A∪B,要求合并后仍然有序。

提交前请将所有的提示信息去掉,只保留最后的输出结果。例如运行时:从键盘直接输入:

2 1 2
3 1 2 3 

输出结果为:

1
2
3

分别表示第一个链表元素个数为2,元素分别为 1,2 ;第二个链表元素个数为3,元素分别为1,2,3。

代码如下:

#include <iostream>
using namespace std;
class List;
class LinkNode{
LinkNode* Union(List list1,List list2);
friend class List;
friend LinkNode* Union(List list1,List list2);
private:
    LinkNode *link;
    int data;
public:
    LinkNode(LinkNode *ptr=NULL)
    {
        link=ptr;
    }
    LinkNode(const int &item,LinkNode *ptr=NULL)
    {
        data=item;
        link=ptr;
    }
};
class List{
private:
    LinkNode *first;
public:
    List()
    {
        first=new LinkNode();
    }
    List(LinkNode *p)
    {
        first=p;
    }
    void Sort();
    void Input();
    void Output();
    LinkNode* GetHead()
    {
        return first;
    }
    int Length()
    {
        int count=0;
        LinkNode *p;
        p=first->link;
        while(p!=NULL)
        {
            count++;
            p=p->link;
        }
        return count;
    }
};
void List::Input(){
    int num,item;
    LinkNode *newNode;
    cin>>num;
    for(int i=0;i<num;i++)
    {
        cin>>item;
        newNode=new LinkNode(item);
        newNode->link=first->link;
        first->link=newNode;
    }
}
void List::Output(){
    LinkNode *p=first->link;
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p=p->link;
    }
}
void List::Sort(){
    LinkNode *p1,*p2,*p;
    int count=0;
    p=first->link;
    while(p!=NULL)
    {
        count++;
        p=p->link;
    }
    for(int i=0;i<count-1;i++)
      {
          p=first->link;

        for(int j=0;j<count-i-1;j++)
    {
        p1=p;
        p2=p->link;
        if((p1->data)>(p2->data))
        {
            int temp;
            temp=p1->data;
            p1->data=p2->data;
            p2->data=temp;
        }
        p=p->link;
    }
    }
}
LinkNode* Union(List list1,List list2){
    LinkNode *p1,*p2,*p3;
    p1=p3=list1.GetHead();
    p2=list2.GetHead();
    int x=list1.Length(),count;
    for(int i=0;i<x;i++)
    {
        p1=p1->link;
        p2=list2.GetHead();
        count=0;
        for(int j=0;j<list2.Length();j++)
        {
            p2=p2->link;
            if((p1->data)==(p2->data))
            {
                p3->link=p1->link;
                count++;
            }
        }
        if(count==0)
        p3=p3->link;
    }
    p3=list1.GetHead();
    while(p3->link)
    {
        p3=p3->link;
    }
    p3->link=list2.GetHead()->link;
    return list1.GetHead();

}
int main()
{
    List list1,list2;
    list1.Input();
    list2.Input();
    List list3(Union(list1,list2));
    list3.Sort();
    list3.Output();
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注