各位善良的学长学姐们 帮学妹看看如何写出一个完整的有序表合并的代码吧

Question

#include
using namespace std;

template
struct LNode
{ DT data;
LNode next;
};
//初始化单链表
template
bool InitList(LNode

&L)
{ L=new LNode;
if(!L)exit(1);
L->next=NULL;
return true;
}
//创建单链表
template //尾插法
bool CreateList(LNode*&L,int n)
{ LNode *p;
p=L;
LNode s;
for(int i=1;i<=n;i++)
{
s=new LNode;
if(!s)
return false;
cin>>s->data;
s->next=p->next ;
p->next=s;
p=s;
}
return true;
}
//销毁单链表
template
void DestroyList(LNode&L)
{
LNode *p;
while(L)
{ p=L;
L=L->next;
delete p;
}
L=NULL;
}
//遍历输出表
template
void DispList(LNode *&L)
{
LNode *p;
p=L->next ;
while(p)
{
cout<data;
p=p->next;
}
}
//从小到大排序
template
void sort(LNode *&L)
{
LNode *p,*q,*min;
for(p=L->next;p!=NULL;p=p->next)
{
min=p;
for(q=p->next;q!=NULL;q=q->next)
{
if(q->datadata)
min=q;

    }
    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;
}

Answer 1

#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);
}