10.42.c

数据结构习题及答案

10.42④ 序列的"中值记录"指的是：如果将此序列排序
后，它是第n/2个记录。试写一个求中值记录的算法。

实现下列函数：
KeyType MidElement(SqList &L);

顺序表的类型SqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RedType;

typedef struct {
   RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
   int     length;
} SqList;
KeyType MidElement(SqList &L)
{
  int i,j,k;
  int mid=(1+L.length)/2;
  k=L.length;
  if(k==0) return '#';
  for(i=k-1;i>=1;i--)
    if(L.r[i].key>L.r[i+1].key)
     {L.r[k+1]=L.r[i];
      L.r[i]=L.r[i+1];
      for(j=i+1;L.r[k+1].key>L.r[j].key;++j) L.r[j-1]=L.r[j];
      L.r[j-1]=L.r[k+1];
      }      
  return L.r[mid].key;
}