Question

已知线性表La和Lb中的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。

初学者，用以下算法实现，用C语言写，不要用链表，要完整程序！！！
void MergeList(List La, List Lb, List &Lc) {
// 已知线性表La和Lb中的元素按值非递减排列。
// 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。
int La_len, Lb_len;
ElemType ai, bj;
int i=1, j=1, k=0;
InitList(Lc);
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空
GetElem(La, i, ai);
GetElem(Lb, j, bj);
if (ai <= bj) {
ListInsert(Lc, ++k, ai);
++i;
} else {
ListInsert(Lc, ++k, bj);
++j;
}
}
while (i <= La_len) {
GetElem(La, i++, ai); ListInsert(Lc, ++k, ai);
}
while (j <= Lb_len) {
GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj);
}
} // MergeList

Answer 1

#include<iostream>
using namespace std;
#include <ctime>
typedef int ElemType;
//节点定义
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//手动方式创建链表
LinkList Manual_Create_LinkList(int n)
{ cout<<"采用手动方式创建链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
for(int i = 0 ; i < n ; i++)
{ LinkList p = new LNode();
cout<<"输入第"<<(i+1)<<"个元素：";
cin>>p->data;
p->next = _LinkList->next;
_LinkList->next = p;
}return _LinkList;}
//自动方式创建链表
LinkList Auto_Create_LinkList(int n)
{ cout<<"采用自动随机数方式创建链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
srand(time(0)); //seed
for(int i = n; i > 0 ; i--)
{
LinkList p = new LNode();
p->data = rand() % 100+ 1;
p->next = _LinkList->next;
_LinkList->next = p;
}
return _LinkList;
}
/*插入非递减有序单向链表*/
void Insert_Sort_LinkList(LinkList &_LinkList,ElemType _Var)
{
LinkList _LinkList1,_LinkList2;
_LinkList1 = new LNode();
_LinkList1->data = _Var;
_LinkList2=_LinkList;
while(_LinkList2->next && _LinkList2->next->data <=_Var)
{_LinkList2 = _LinkList2->next;}
_LinkList1->next = _LinkList2->next;
_LinkList2->next = _LinkList1;
}
//建立非递减有序单向链表
LinkList Manual_Create_Ordered_LinkList(int _int)
{
cout<<"采用手动方式建立非递减有序单向链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
int i = 0;int j = 0;int k = 0;ElemType _Var;
for(i=0;i<_int;i++)
{
cout<<"输入第"<<(i+1)<<"个元素：";
cin>>_Var;

Insert_Sort_LinkList(_LinkList,_Var);
}
return _LinkList;
}
//销毁链表
void Destroy_LinkList(LinkList *myLinkList)
{
LinkList _LinkList1,_LinkList2;
if(!(*myLinkList))
{cout<<"链表不存在！"<<endl;return;}
_LinkList1 = *myLinkList;
while(_LinkList1 != NULL)
{
_LinkList2 = _LinkList1;
_LinkList1 = _LinkList1->next;
delete(_LinkList2);
}
*myLinkList = NULL;
}
//遍历链表
void Traveral_LinkList(LinkList myLinkList)
{
cout<<"------------------------------"<<endl;
cout<<"遍历链表中的元素："<<endl;
int i = 0;
/*第一种遍历方式*/
LinkList _LinkList = myLinkList->next;
while(_LinkList)
{
cout<<"输出第"<<(i+1)<<"个元素："<<_LinkList->data<<endl;
_LinkList = _LinkList->next;
i++;
}

/*第二种遍历方式*/
/*
LinkList _LinkList;
for(_LinkList = myLinkList->next;_LinkList;_LinkList=_LinkList->next)
{
cout<<"输出第"<<i<<"个元素："<<_LinkList->data<<endl;
i++;
}
*/
cout<<"------------------------------"<<endl;
}
//查找元素
LinkList Locate_LinkList(LinkList myLinkList,ElemType x)
{ while(myLinkList && myLinkList->data != x)
{
myLinkList = myLinkList->next;
}
return myLinkList;
}//反转链表
void Reverse_LinkList(LinkList &myLinkList)
{
LinkList TempLinkList = NULL;
LinkList _LinkList = myLinkList->next; //指向第一个元素
myLinkList->next = NULL; //指向最后一个元素
while(_LinkList)
{
TempLinkList = _LinkList;
_LinkList = _LinkList->next; //下移
TempLinkList->next = myLinkList->next;
myLinkList->next = TempLinkList;
}
}
/*删除指定元素*/
void Delete_LinkList(LinkList myLinkList,ElemType x)
{
int i = 0;
if(!myLinkList)
{cout<<"链表不存在！"<<endl;return;}
/*[Begin]第一种方法*/
/*
LinkList _LinkList1 = myLinkList;
LinkList _LinkList2 = myLinkList->next;
while(_LinkList2 && _LinkList2->data != x)
{ _LinkList1 = _LinkList2;
_LinkList2 = _LinkList2->next;
} if(!_LinkList2)
{cout<<"值没有找到！"<<endl;return;}
else
{ _LinkList1->next = _LinkList2->next;
delete(_LinkList2);
}
*/
/*[End]第一种方法*/
/*[Begin]第二种方法*/
/**/
LinkList _LinkList = myLinkList;
//循环条件：下个结点不为NULL，并且下个结点不为x
while(_LinkList->next != NULL && _LinkList->next->data != x)
{_LinkList = _LinkList->next;}
//判断是否已经循环到最后一个结点
if(_LinkList->next == NULL)
{cout<<"值没有找到！"<<endl;return;}
LinkList TempLinkList = _LinkList->next;
_LinkList->next = TempLinkList->next;
delete(TempLinkList);
/*[End]第二种方法*/
}

void main()
{ LinkList myLinkList;
int i=0;int num = 0;
/*[Begin]手动创建链表－－－－－－－－－－－－－－－－－－－－*/
cout<<"使用手动输入创建链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Manual_Create_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]手动创建链表－－－－－－－－－－－－－－－－－－－－－*/
/*[Begin]删除元素值－－－－－－－－－－－－－－－－－－－－－*/
cout<<"输入要删除的元素值：";
cin>>num;
Delete_LinkList(myLinkList,num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]删除元素值－－－－－－－－－－－－－－－－－－－－－－*/
Destroy_LinkList(&myLinkList); //销毁链表
/*[Begin]随机数创建链表－－－－－－－－－－－－－－－－－－－－－*/
num = 0;
cout<<"使用随机数创建链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Auto_Create_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]随机数创建链表－－－－－－－－－－－－－－－－－－－－－－*/
/*[Begin]链表元素反转－－－－－－－－－－－－－－－－－－－－－*/
cout<<"将随机数创建的链表元素反转：";
Reverse_LinkList(myLinkList);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]链表元素反转－－－－－－－－－－－－－－－－－－－－－－*/
Destroy_LinkList(&myLinkList); //销毁链表
/*[Begin]建立非递减有序单向链表－－－－－－－－－－－－－－－－－－－－－*/
cout<<"使用手动输入建立非递减有序单向链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Manual_Create_Ordered_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]建立非递减有序单向链表－－－－－－－－－－－－－－－－－－－－－－*/
} 这是可执行程序，希望能帮到你