数据结构实验一

/************************************/  
/****                            ****/  
/****    数据结构 实验一         ****/  
/****                            ****/  
/****    作者 ： 王小康          ****/  
/****    时间 ： 2013年11月11日  ****/  
/****                            ****/  
/************************************/  
  
#include  
#include  
#include  
typedef int ElemType;  
  
/*单项链表的声明*/  
typedef struct LNode{  
    ElemType data;  
    struct LNode *next;  
}LNode,*LinkList;  
  
/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/  
void CreateList(LinkList &L,int n)  
{  
    int i;  
    LinkList p,q;  
    L=(LinkList)malloc(sizeof(LNode)); // 生成头结点  
    L->next=NULL;  
    q=L;  
    printf("请输入%d个数据\n",n);  
    for(i=1;i<=n;i++)  
    {  
        p=(LinkList)malloc(sizeof(LNode));  
        scanf("%d",&p->data);    
        q->next=p;  
        q=q->next;  
    }  
    p->next=NULL;  
}  
  
// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同  
void ListTraverse(LinkList L,void(*vi)(ElemType))  
{// 初始条件：线性表L已存在  
 // 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败  
    LinkList p=L->next;  
    while(p)  
    {  
     vi(p->data);  
     p=p->next;  
    }  
    printf("\n");  
}  
  
/*ListTraverse()调用的函数(类型要一致)*/  
void visit(ElemType c)   
{  
    printf("%d ",c);  
}  
  
/*    归并函数                      */  
/* 参数：两个已经存在的单链表       */  
/* 返回值：归并后新的单链表的头结点 */  
LinkList MergeList(LinkList La, LinkList Lb)  
{  
    LinkList pa, pb, pc, Lc;  
    pa = La->





next;  
    pb = Lb->next;  
    Lc = pc = La;   // 用La的头结点作为Lc的头结点  
    while(pa&&pb)  
    {  
        if(pa->data < pb->data)  
        {  
            pc->next = pa;  
            pc = pa;  
            pa = pa->next;  
        }  
        else if (pa ->data > pb->data )  
        {  
            pc->next = pb;  
            pc = pb;  
            pb = pb->next;  
        }  
        else   //(pa ->data = pb->data )  
        {  
            pc->next = pa;  
            pc = pa;  
            pa = pa->next;  
            pb = pb->next;  
        }  
    }  
  
    pc->next = pa   pa:pb;  // 插入剩余段  
  
    return Lc;  
}  
  
void main()  
{  
    LinkList ha, hb, hc;  
    printf("非递减输入ha， ");  
    CreateList(ha,5);   // 正位序输入n个元素的值  
    printf("非递减输入hb， ");  
    CreateList(hb,5);   // 正位序输入n个元素的值  
  
    printf("Ha = ");  
    ListTraverse(ha,visit);   // 输出链表Ha的内容  
    printf("Hb = ");  
    ListTraverse(hb,visit);   // 输出链表Ha的内容  
  
    hc = MergeList(ha,hb);    // 按非递减顺序归并Ha和Hb,得到新表Hc  
    printf("归并后:");  
    printf("Hc = ");  
    ListTraverse(hc,visit);   // 输出链表Hc的内容  
}