实习目的: 熟练掌握链表的建立及基本操作
问题描述:
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
实现过程:
一, 首先构造链表
- class List;
- class LinkNode
- {
- friend List;
- private:
- LinkNode *link;// 指向下一个节点
- int data;// 结点内容
- public:
- LinkNode (LinkNode *ptr = NULL)
- {
- link=ptr;
- }
- LinkNode(const int & item, LinkNode *ptr = NULL)
- {
- data=item;
- link=ptr;
- }
- ~LinkNode() {};
- };
- class List
- {
- private:
- LinkNode *first;// 头指针
- public:
- List ()
- {
- first = new LinkNode ();
- }// 构造函数, 开辟新空间
- void qsort ( int n);// 排序
- void Insert (int x );// 插入
- void Union(List b);// 并运算
- void input(int endTag);// 输入
- void output();// 输出
- };
二, 利用前插法构建链表
- void List :: input (int n)
- {
- LinkNode *newnode;
- int val;// 读取内容
- while(n--)
- {
- cin>>val;
- newnode=new LinkNode (val);// 创建新节点
- newnode->link=first->link;// 将新节点指向头结点的下一位
- first->link=newnode;// 头结点指向新节点
- }
- }
三, 利用冒泡进行排序
- 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;
- }
- }
附录: 插入函数
- void List ::Insert (int x )
- {
- LinkNode *newnode; ;
- newnode=new LinkNode (x);
- newnode->link=first->link;
- first->link=newnode;
- }
五, 进行输出
- void List ::output ( )
- {
- LinkNode *p=first->link;
- while(p!=NULL)
- {
- cout<<p->data<<endl;
- p=p->link;
- }
- }
六, 主程序
- int main()
- {
- List a;
- int n;
- cin>>n;
- a.input(n);
- a.qsort(n);
- List b;
- int m;
- cin>>m;
- b.input(m);
- b.qsort(m);
- a.Union(b);
- b.qsort(m+n);
- b.output();
- return 0;
- }
七, 简单介绍
本博客写的比较傻瓜, 比较简单, 因为是早期写的程序, 有些地方调用不太合理, 请见谅.
来源: http://www.bubuko.com/infodetail-3099713.html