|
/************************************/ /**** ****/ /**** 数据结构 实验一 ****/ /**** ****/ /**** 作者 ： 王小康 ****/ /**** 时间 ： 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的内容 }
|
