将两个有序线形表合并成一个有序表,要求分别按顺序存储结构和链式存储结构编程。
head_f.H文件:
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define List_Init_Size 20
#define ListIncrement 10
typedef int ElemType;
typedef int Status;
typedef ElemType * Elemp;
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
LinkList La,Lb,Lc;
typedef struct {
ElemType *elem;
int Length;
int ListSize;
} SqList;
SqList Sa,Sb,Sc;
eg.c文件:
/* ============== Program Description ============= */
/* Freshare’s 1st of dswork */
/* ================================================== */
# include "stdlib.h"
# include "stdio.h"
#include"head_f.h"
//SqList
void print_sqlist(SqList *L) {
int i;
printf(">> Size=%d Length=%d ",L->ListSize,L->Length);
for (i=0;i<L->Length;i++)
printf("%d ",L->elem[i]);
printf("/n/n");
}
Status Creat_sqlist( SqList *L)
{
L->elem=(Elemp)malloc(List_Init_Size*sizeof(ElemType));
if(L->elem==NULL)
exit(OVERFLOW);
L->Length=0;
L->ListSize=List_Init_Size;
return OK;
}
Status ListInsertsq(SqList *L,int i,ElemType e)
{
Elemp p,q;
if (i<1 || i>L->Length+1) return ERROR;
if(L->Length >= L->ListSize){
p=(ElemType*)realloc(L->elem,(L->ListSize+ListIncrement)*sizeof(ElemType));
if (p==NULL)exit(OVERFLOW);
L->elem=p;L->ListSize+=ListIncrement;
}
q=L->elem+i-1;
for(p=L->elem+L->Length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++L->Length;
return OK;
}
Status Input_sq(SqList *L) {
int done=TRUE;
ElemType e;
Creat_sqlist(L);
while (done) {
scanf("%d",&e);
if ( e!= 9999)
ListInsertsq(L,L->Length+1,e);
else done = FALSE;
}
}
SqList MergeList_Sq(SqList Sa, SqList Sb) // 算法2.7
{
Elemp pa,pb,pc,pa_last,pb_last;
pa = Sa.elem; pb = Sb.elem;
Sc.ListSize = Sc.Length = Sa.Length+Sb.Length;
pc = Sc.elem = (ElemType *)malloc(Sc.ListSize*sizeof(ElemType));
if (!Sc.elem)
exit(OVERFLOW);
pa_last = Sa.elem+Sa.Length-1;
pb_last = Sb.elem+Sb.Length-1;
while (pa <= pa_last && pb <= pb_last) {
if (*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while (pa <= pa_last) *pc++ = *pa++;
while (pb <= pb_last) *pc++ = *pb++;
return (Sc);
}
void seeSqList()
{
printf("/nPlease input the La : ");
Input_sq(&Sa) ;
printf("La: ");
print_sqlist(&Sa);
printf("Please input the Lb : ");
Input_sq(&Sb) ;
printf("Lb: ");
print_sqlist(&Sb);
Sc=MergeList_Sq(Sa,Sb);
printf("Lc: ");
print_sqlist(&Sc);
Menu_Select( );
}
//LinkList
struct LNode *creat()
{
LinkList l,p,q;
ElemType x;
l=NULL;
l=(LNode*)malloc(sizeof(LNode));
if (l==NULL)exit(OVERFLOW);
l->next=NULL;
scanf("%d",&x);
while (x!=9999)
{
p=(LNode*)malloc(sizeof(LNode));
p->data=x;
if ((l->next)==NULL)
{
l->next=p;
q=p;
}
else
{
q->next=p;
q=p;
}
scanf("%d",&x);
}
p->next=NULL;
return (l);
}
void print_LinkList (LinkList l)
{
LinkList p;
p=l;
printf(">> ");
while (p->next!=NULL)
{
p=p->next;
printf("%d ",p->data);
}
printf("/n/n");
}
LinkList MergeList_L(LinkList La, LinkList Lb) // 算法2.12
{
LinkList pa, pb, pc;
pa = La->next; pb = Lb->next;
Lc = pc = La;
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa; pc = pa; pa = pa->next;
}
else { pc->next = pb; pc = pb; pb = pb->next; }
}
pc->next = pa ? pa : pb;
free(Lb);
return (Lc);
}
void seeLinkList()
{
printf("/nPlease input the La : ");
La=creat() ;
printf("La: ");
print_LinkList(La);
printf("Please input the Lb : ");
Lb=creat() ;
printf("Lb: ");
print_LinkList(Lb);
Lc=MergeList_L(La,Lb);
printf("Lc: ");
print_LinkList(Lc);;
Menu_Select( );
}
void MenuList()
{
printf("/n**************************/n");
printf(" 1 ------- SqList/n");
printf(" 2 ------- LinkList/n");
printf(" 3 ------- Exit/n");
printf("**************************/n");
}
int Menu_Select( )
{
int done=1;
int select ;
while (done) {
MenuList( );
printf("Please input the operating code : ");
scanf("%d",&select);
switch(select)
{
case 1: seeSqList();break;
case 2: seeLinkList();break;
case 3: done=0;break;
default: printf(" /nERROR/n");
}
}
}
void main( )
{
Menu_Select();
}