ch2_stable_merge.c

本人讲授数据结构课程时的所写的示例程序

/*
合并两个有序表
author: kk.h
date: 2006.10
http://www.cocoon.org.cn
*/

#include "stdio.h"
typedef struct{
  int no;
  int grade;
}ElemType;

typedef struct{
  ElemType *elem;
  int length;
  int listsize;
}SqList;

int InitList(SqList *pL)
{
  pL->listsize = 10;
  pL->elem = (ElemType*)malloc(pL->listsize*sizeof(ElemType));
  pL->length=0;
}
DestroyList(SqList *pL)
{
  free(pL->elem);
}
int ListInsert(SqList *pL,ElemType e)
{
  int i,j;
  if (pL->length>=pL->listsize){
    pL->listsize = pL->listsize + 10;
    pL->elem = (ElemType *)realloc(pL->elem,(pL->listsize)*sizeof(ElemType));
  }

  /*找插入点的位置*/
  for(i=0;i<pL->length;i++){
    if (e.grade>pL->elem[i].grade)
       break;
  }

  /*向后移动数据*/
  for(j=pL->length+1;j>i;j--)
    pL->elem[j]=pL->elem[j-1];

  pL->elem[i]=e;

  pL->length=pL->length+1;
  return 1;
}
ShowList(SqList*pL)
{
  int i;
  printf("\n");
  for(i=0;i<pL->length;i++){
    printf("\n(%d,%d)",pL->elem[i].no,pL->elem[i].grade);
  }  
}

MergeList(SqList L1,SqList L2,SqList* pLm)
{
  int i1,i2,im;
  i1=0;i2=0;im=0;
  while (i1<L1.length && i2<L2.length){
    if (L1.elem[i1].grade>L2.elem[i2].grade){
      pLm->elem[im] = L1.elem[i1];
      i1++; im++;
    }else
    {
      pLm->elem[im] = L2.elem[i2];
      i2++; im++;
    }
  }

  while(i1<L1.length) {
      pLm->elem[im] = L1.elem[i1];
      i1++; im++;
  }
  while(i2<L2.length) {
      pLm->elem[im] = L2.elem[i2];
      i2++; im++;
  }

  pLm->length = im;

}

main()
{
  SqList L1,L2,Lm;
  ElemType e;
  InitList(&L1); InitList(&L2); InitList(&Lm);
  e.no=1;e.grade=85; ListInsert(&L1,e);
  e.no=2;e.grade=95; ListInsert(&L1,e);
  e.no=3;e.grade=65; ListInsert(&L1,e);
  e.no=4;e.grade=75; ListInsert(&L1,e);

  e.no=6;e.grade=80; ListInsert(&L2,e);
  e.no=7;e.grade=90; ListInsert(&L2,e);
  e.no=8;e.grade=60; ListInsert(&L2,e);
  e.no=9;e.grade=50; ListInsert(&L2,e);

  MergeList(L1,L2,&Lm);

  ShowList(&L1); ShowList(&L2); ShowList(&Lm);
  DestroyList(&L1); DestroyList(&L2); DestroyList(&Lm);

  getch();
}