Anyview数据结构-3

Posted on | Post modified: | In
Words count in article: 655 | Reading time ≈ 3

-广工Anyview题解
-数据结构部分-3

/**
【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨，
改写教材3.2节中给出的升序直接插入排序算法。
顺序表的类型RcdSqList定义如下：
typedef struct {
KeyType key;
…
} RcdType;
typedef struct {
RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
int length;
} RcdSqList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertSort(RcdSqList &L)
{
   int i,j;
   for(i=1;i<L.length;i++){
     if(L.rcd[i+1].key<L.rcd[i].key){
        L.rcd[0]=L.rcd[i+1];
        j=i+1;
        do{
           j--;
           L.rcd[j+1] = L.rcd[j];
        }while(L.rcd[0].key<L.rcd[j-1].key);
        L.rcd[j] = L.rcd[0];
      }
   }
}

/**
【题目】如下所述，改写教材1.3.2节例1-10的冒泡排序算法：
将算法中用以起控制作用的布尔变量change改为一个整型
变量，指示每一趟排序中进行交换的最后一个记录的位置，
并以它作为下一趟起泡排序循环终止的控制值。
顺序表的类型RcdSqList定义如下：
typedef struct {
KeyType key;
…
} RcdType;
typedef struct {
RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
int length;
} RcdSqList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void BubbleSort(RcdSqList &L)
/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"        */
/* Status GT(RedType a, RedType b);   比较：">"        */
/* void Swap(RedType &a, RedType &b); 交换             */
{
   int i,change,j,k;                                                  
   for(i=L.length,change = 0;i>1;i--){
       change = i;
      for(j=1;j<i;++j){
         if(GT(L.rcd[j],L.rcd[j+1])){
            Swap(L.rcd[j],L.rcd[j+1]);
            k++;
            change = j+1;
         }            
      }
      while(L.rcd[change].key == L.rcd[change-1].key) //用while来跳过那些相同关键字
             change=change - 1;
      i=change;
      if(k==0)    //当有一次比较没有交换时使i= 1结束操作
         i=1;
     k=0;
  }
}

/**
【题目】已知记录序列L.rcd[1..L.length]中的关键
字各不相同，可按如下所述实现计数排序：另设数组
c[1..n]，对每个记录a[i]， 统计序列中关键字比它
小的记录个数存于c[i]，则c[i]=0的记录必为关键字
最小的记录，然后依c[i]值的大小对序列中记录进行
重新排列。试编写算法实现上述排序方法。
顺序表的类型RcdSqList定义如下：
typedef struct {
KeyType key;
…
} RcdType;
typedef struct {
RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
int length;
} RcdSqList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void CountSort(RcdSqList &L)
/* 采用顺序表存储结构，在函数内自行定义计数数组c */
{
   int k=L.length ;
   RcdSqList L1;
   int c[27];
   int i,j;
   for(i=1;i<=L.length ;i++)
      for(j=1;j<=L.length;j++){
         if(L.rcd[i].key<L.rcd[j].key)
            c[i]++;
      }
        
    for(i=1;i<=L.length;i++)
         L1.rcd[c[i]+1].key=L.rcd[i].key;
        
    for(i=1;i<=L.length;i++)       
         L.rcd[L.length-i+1].key = L1.rcd[i].key;
      
}
Thanks for your reward！