当前位置：编程学习 > C/C++ >>

c/c++链表程序编写

数据结构与算法实验题2.2 链表合并

★实验任务

给定一个非升序列和一个非降序列，要求将其合并成一个非升序列并输出。
非升序列是指一个序列 a1 a2a3 … 满足 a1 >= a2 >= a3 …
非降序列是指一个序列 b1 b2b3 … 满足 b1 <= b2 <= b3 ...

★数据输入

第一行包括两个正整数N，M（1<=N，M<=100000），N 表示非升序列的元素个数，
M 非降序列的元素个数。

第二行包含n 个非升序列的元素，第三行包含m 个非降序列的元素。

元素之间用空格隔开。元素都为整数。

★数据输出

输出合并后的非升序列。元素间用一个空格隔开，行末不留空格。

输入示例输出示例
5 6 4 2 0 -1 -1 -2 -1 -1 -1 -1 1
4 2 0 -1 -1
-2 -1 -1 -1 -1 1

补充：只要能做出来加分没问题 我们好说话

追问：不行啊

答案：
#include <iostream>
#include <string>
using namespace std;


struct A
{
float n;
A *next;
};
//创建链表
void CreateList (A *&L, float array[], int m)
{
A *r = L, *s;
for (int i = 0; i < m; i++)
{
s = new A;
s->n = array[i];
r->next = s;
r = s;
}
r->next = NULL;
}
//初始化链表
void InitList (A *&L)
{
L = new A;
L->next = NULL;
}
//排序
void Sort (A *&L, A *H)
{
A *p, *q, *r = H->next, *s;
while (r != NULL)
{
s = r->next;
p = L;
q = p->next;
while((q != NULL) && (r->n < q->n))
{
p = q;
q = q->next;
}
r->next = p->next;
p->next = r;
r = s;
}
}


void main ()
{
float a[100000], b[100000];
int N, M;


cout << "请输入非升序列的个数:";
cin >> N;


cout << "请输入非升序列:";
for (int i = 0; i < N; i++)
cin >> a[i];


cout << "请输入非降序列的个数:";
cin >> M;


cout << "请输入非降序列:";
for (i = 0; i < M; i++)
cin >> b[i];


A *L, *H;
InitList (L);
CreateList (L, a, N);


InitList (H);
CreateList (H, b, M);
cout << endl;


Sort (L, H);
A *l = L->next;
while (l != NULL)
{
cout << l->n << ' ';
l = l->next;
}
cout << endl;
}