#include
using namespace std;
template
struct LNode
{ DT data;
LNode next;
};
//初始化单链表
template
bool InitList(LNode
}
if(min!=p)
{
int temp=p->data;
p->data=min->data;
min->data=temp;
}
}
}
int main()
{ int i;
LNode *LA;
LNode *LB;
LNode *LC;
InitList(LA);
InitList(LB);
InitList(LC);
cout<<"请输入创建链表LA的元素个数：";
cin>>i;
cout<<"请依次输入集合A元素为：";
CreateList(LA,i);
cout<<"有序表LA= ";
sort(LA);
DispList(LA);
cout<<endl;
cout<<"请输入创建链表LB的元素个数：";
cin>>i;
cout<<"请依次输入集合B元素为：";
CreateList(LB,i);
cout<<"有序表LB= ";
sort(LB);
DispList(LB);
LNode<int> *pa=LA->next;
LNode<int> *pb=LB->next;
if(LB->next==NULL)
DispList(LA);
if(LA->next==NULL)
DispList(LB);
LNode<int> *pc=LC;
while(pa && pb)
{
if(pa ->data <= pb->data)
{
pc->data = pa->data ;
pa = pa->next;
}
else
{
pc->data =pb->data;
pb = pb->next;
}
}
while(pa)
{
pc->next = pa;
pc= pa;
pa = pa->next;
}
while(pb)
{
pc->next = pb;
pc= pb;
pb = pb->next;
}
CreateList(LC,pc->data);
cout<<"有序表归并表LC= ";
for(pc=LC->next;pc!=NULL;pc=pc->next)
{
cout<<pc->data;
}
cout<<endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
/************************************/
/* 链表实现的头文件，文件名slnklist.h */
/************************************/
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
}node;
/*****************************************************/
/* 函数功能：建立一个空的带头结点的单链表 */
/* 函数参数：空 */
/* 函数返回值：指向node类型变量的指针 */
/* 文件名：hlnklist.c，函数名：init() */
/**************************************************** */
node *init()
{
node *head;
head = (node*)malloc(sizeof(node));
head->next = NULL;
return head;
}
/*****************************************************/
/* 函数功能：输出带头结点的单链表中各个结点的值 */
/* 函数参数：指向node类型变量的指针head */
/* 函数返回值：无 */
/* 文件名：hlnklist.c，函数名：display() */
/*****************************************************/
void display(node *head)
{
node *p;
p = head->next;/*从第一个（实际）结点开始*/
if (!p) printf("\n带头结点的单链表是空的!");
else
{
printf("\n带头结点的单链表各个结点的值为：\n");
while (p) { printf("%5d", p->info); p = p->next; }
}
}
/*****************************************************/
/* 函数功能：在带头结点的单链表中查找第i个结点地址 */
/* 函数参数：指向node类型变量的指针head */
/* int类型变量i */
/* 函数返回值：指向node类型变量的指针head */
/* 文件名hlnklist.c，函数名find() */
/*****************************************************/
node *find(node *head, int i)
{
int j = 0;
node *p = head;
if (i < 0) { printf("\n带头结点的单链表中不存在第%d个结点！", i); return NULL; }
else if (i == 0) return p;/*此时p指向的是头结点*/
while (p&&i != j)/*没有查找完并且还没有找到*/
{
p = p->next; j++;/*继续向后（左）查找，计数器加1*/
}
return p;/*返回结果，i=0时，p指示的是头结点*/
}
/***********************************************************************/
/* 函数功能：在带头结点的单链表中第i个结点后插入一个值为x的新结点 */
/* 函数参数：指向node类型变量的指针head */
/* datatype 类型变量x，int型变量i */
/* 函数返回值：指向node类型变量的指针head */
/* 文件名：hlnklist.c，函数名：insert() */
/***********************************************************************/
node *insert(node *head, datatype x, int i)
{
node *p, *q;
q = find(head, i);/*查找带头结点的单链表中的第i个结点*/
/*i=0，表示新结点插入在头结点之后，此时q指向的是头结点*/
if (!q)/*没有找到*/
{
printf("\n带头结点的单链表中不存在第%d个结点！不能插入%d！", i, x); return head;
}
p = (node*)malloc(sizeof(node));/*为准备插入的新结点分配空间*/
p->info = x;/*为新结点设置值x*/
p->next = q->next;/*插入(1)*/
q->next = p;/*插入(2)，当i=0时，由于q指向的是头结点，本语句等价于head>next=p */
return head;
}
node *mergelist(node *head1, node *head2) /*本函数的作用是将两个有序表按结点值的大小合并成一个有序表，将本函数补充完整*/
{
node *p, *q, *s;
p = head1->next;
q = head2->next;
node *head3;
head3 = head1;
head3->next = NULL;
free(head2);
while (p != NULL && q != NULL) {
if (p->info < q->info) {
s = p;
p = p->next;
}
else {
s = q;
q = q->next;
}
s->next = head3->next;
head3->next = s;
}
if (p == NULL) {
p = q;
}
while (p != NULL) {
s = p;
p = p->next;
s->next = head3->next;
head3->next = s;
}
node *ans = init();
p = head3->next;
while (p != NULL) {
s = p;
p = p->next;
s->next = ans->next;
ans->next = s;
}
return ans;
}
int main()
{
node *L1, *L2;
datatype y;
int j, n;
L1 = init(); L2 = init();
/*建表*/
printf("请输入带头结点单链表A的结点个数："); scanf("%d", &n);
printf("请输入带头结点单链表A的结点值：");
for (j = 0; j < n; j++)
{
scanf("%d", &y); L1 = insert(L1, y, j);
}
display(L1);
printf("\n");
printf("请输入带头结点单链表B的结点个数："); scanf("%d", &n);
printf("请输入带头结点单链表B的结点值：");
for (j = 0; j < n; j++)
{
scanf("%d", &y); L2 = insert(L2, y, j);
}
display(L2);
printf("\n");
/*在此处完成对mergelist函数的调用，并进行测试*/
node *L3 = mergelist(L1, L2);
printf("输出合并后的链表：");
display(L3);
}