链表的基本操作

shdwin 2019-06-21 原文

实习目的：熟练掌握链表的建立及基本操作

问题描述：

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

2）实现两个有序链表的合并：A=A∪B，要求合并后仍然有序。

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

2 1 2
3 1 2 3

输出结果为：

1
2
3

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

例如:

输入	Result
2 2 1 3 1 2 3	1 2 3

第一问是通过对链表的操作，利用冒泡排序，完成该操作。

对于第二问则是利用查找来实现A=A∪B

实现过程：

一、首先构造链表

 1 class List;
 2 class LinkNode
 3 {
 4     friend  List;
 5 private:
 6     LinkNode *link;//指向下一个节点
 7     int data;//结点内容
 8 public:
 9     LinkNode (LinkNode *ptr = NULL)
10     {
11         link=ptr;
12     }
13     LinkNode(const int & item, LinkNode *ptr = NULL)
14     {
15         data=item;
16         link=ptr;
17     }
18     ~LinkNode() {};
19 };
20 class List
21 {
22 private:
23     LinkNode *first;//头指针
24 public:
25     List ()
26     {
27         first = new LinkNode ();
28     }//构造函数，开辟新空间
29 
30     void qsort ( int n);//排序
31     void Insert (int x );//插入
32     void Union(List b);//并运算
33     void input(int  endTag);//输入
34     void output();//输出
35 };

二、利用前插法构建链表

 1 void List :: input (int n)
 2 {
 3     LinkNode  *newnode;
 4     int val;//读取内容
 5     while(n--)
 6     {
 7         cin>>val;
 8         newnode=new LinkNode (val);//创建新节点
 9         newnode->link=first->link;//将新节点指向头结点的下一位
10         first->link=newnode;//头结点指向新节点
11 
12     }
13 }

三、利用冒泡进行排序

void List ::qsort ( int n)
{

    while(n--)//进行n循环
    {
        LinkNode  *p=first->link;
        while(p->link!=NULL)//进行一次遍历
        {
            if(p->data>=p->link->data)//如果该点值小于下一个点值，data内容进行交换
            {
                int temp=p->data;
                p->data=p->link->data;
                p->link->data=temp;
            }
            p=p->link;
        }
    }
}

四、利用查找进行合并

void List ::Union(List b)
{
    LinkNode *p=first->link;
    while(p!=NULL)
    {
        LinkNode *p1=b.first->link;
        bool f=0;
        while(p1!=NULL)
        {

if(p1->data==p->data)//在A中进行查找，若找到则标志f=1，否则将B中元素插入A；

{
f=1;

break;
}

            p1=p1->link;
        }
        if(f==0)
        {
            b.Insert(p->data);//插入函数
        }
        p=p->link;

}
}

附录：插入函数

 1 void List ::Insert (int x )
 2 {
 3     LinkNode  *newnode; ;
 4 
 5     newnode=new LinkNode (x);
 6     newnode->link=first->link;
 7     first->link=newnode;
 8 
 9 
10 }

五、进行输出

1 void List ::output ( )
2 {
3     LinkNode  *p=first->link;
4     while(p!=NULL)
5     {
6         cout<<p->data<<endl;
7         p=p->link;
8     }
9 }

六、主程序

 1 int main()
 2 {
 3 
 4     List a;
 5     int n;
 6     cin>>n;
 7     a.input(n);
 8     a.qsort(n);
 9     List b;
10     int m;
11     cin>>m;
12     b.input(m);
13     b.qsort(m);
14     a.Union(b);
15     b.qsort(m+n);
16     b.output();
17 
18 
19     return 0;
20 
21 }