C编程思想之抽象数据类型（ADT）（二）

此篇继续前一个博客，以一个火车厢重排问题为例（这里用堆栈形式的缓冲轨），有关此题目，想必大家有所耳闻，我也在网上搜索过，发有大多都是C++版本，而C语言版本只有一版，而且我感觉有点乱，注释少，以至我没有耐心读下去。正好拿这个题目练练手，就当做个大脑体操了，呵呵，步入正题，继续体会抽象数据类型带来的好处。

关于火车厢重排的详细资料，参见下图：

这里的stack.h,stack.c以及getlib.h等同上篇中的代码。这里只贴出火车厢重排的代码。

1 /* trainsort.c --- 
  2  * 
  3  * Filename: trainsort.c
  4  * Description: 火车厢重排问题
  5  * Author: magc
  6  * Maintainer: 
  7  * Created: 五  8月 10 13:59:05 2012 (+0800)
  8  * Version: 
  9  * Last-Updated: 五  8月 10 17:37:30 2012 (+0800)
 10  *           By: magc
 11  *     Update #: 217
 12  * URL: 
 13  * Keywords: 
 14  * Compatibility: 
 15  * 
 16  */
 17 
 18 /* Commentary: 
 19  * 题目：假设一列货运列车共有n节编号分别为1~n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1~n的次序排列，以便各车厢能够停靠在与其编号一致的站点。
 20  * 为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各车厢从右到左按照编号1~n的次序通过出轨处离开转轨站。
 21  * 
 22  * 
 23  */
 24 
 25 /* Change Log:
 26  * 
 27  * 
 28  */
 29 
 30 /* Code: */
 31 #include <assert.h>
 32 #include <ctype.h>
 33 #include <errno.h>
 34 #include <limits.h>
 35 #include <string.h>
 36 #include <stdarg.h>
 37 #include <stdlib.h>
 38 #include <stdio.h>
 39 #include "../commonlib/genlib.h"
 40 #include "stack.h"
 41 void sort(int trainArray[], int t_len,int buf_num);
 42 int sendout(int outID ,stackADT buf_array[] ,int buf_num);
 43 void hold(int t_index ,stackADT buf_array[],int buf_num);
 44 bool checkout(int outID,stackADT buf_array[] ,int buf_num);
 45 
 46 
 47 int main(int argc, char * argv[])
 48 {
 49     int t_array[8] = { 8,5,3,4,7,6,2,1 };//自定义一个初始的车厢顺序
 50     int buf_num = 3;//假设有三个缓冲轨
 51     sort(t_array,8,buf_num);
 52 
 53     return 0;
 54     
 55 }
 56 /*************************************************************************
 57 *功能描述：火车厢重排
 58 *参数列表：trainArray：初始的火车厢序列数组，t_len：火车厢数量,buf_num:缓冲轨个数
 59 *返回类型：
 60 **************************************************************************/
 61 void sort(int trainArray[], int t_len,int buf_num){
 62     int outID = 1;
 63     int i;
 64     //缓冲轨用堆栈实现，多个缓冲轨用数组来组织，初始都为NULL，在使用时再初始化栈
 65     stackADT buf_array[buf_num];
 66     int m;
 67     for (m = 0; m < buf_num; m++) {
 68         buf_array[m] = NULL;
 69         
 70     }
 71     int t_index;
 72     
 73     //车厢依次从入口进入
 74     for (i = 0; i < t_len; i++) {
 75 
 76         t_index = trainArray[i];
 77         printf("%d号车厢从入口进入n",t_index);
 78         //每进来一个,例行检查
 79         if(t_index == outID){
 80             outID = sendout(outID , buf_array,buf_num);
 81             continue;
 82         }else{
 83             //            printf("%d车厢寻找缓冲轨n",trainArray[i]);
 84             hold(t_index,buf_array,buf_num);
 85             
 86             
 87         }
 88     }
 89 }
 90 /*************************************************************************
 91 *功能描述：进入出轨口
 92 *参数列表：outID:当前要进入出轨口的车厢号，buf_array:缓冲轨(堆栈)的数组，buf_num:缓冲轨(堆栈)的个数
 93 *返回类型：返回下一个应该出轨的车号
 94 **************************************************************************/
 95 int sendout(int outID ,stackADT buf_array[] ,int buf_num){
 96     printf("==>%d号车厢进入出轨口n",outID);
 97     //继续检测下一序号是否符合出轨
 98     outID++;
 99     //每当出去一个车厢后，重新检测缓冲栈中栈顶车厢号，看是否有可进入出轨口的
100     while(checkout(outID,buf_array,buf_num)){
101         outID++;
102     }
103     return outID;
104 }
105 
106 /*************************************************************************
107 *功能描述：检测缓冲轨中是否有应该进入出轨口的
108 *参数列表：outID:当前要进入出轨口的车厢号，buf_array:缓冲轨(堆栈)的数组，buf_num:缓冲轨(堆栈)的个数
109 *返回类型：是否有进入出轨口的车厢（若有，当时已经弹出），主要是后续根据此结果是否需要继续检测下一车厢号
110 **************************************************************************/
111 bool checkout(int outID,stackADT buf_array[] ,int buf_num){
112 
113     int i;
114     printf("在缓冲轨中检查%d号n",outID);
115     
116     for (i = 0; i < buf_num; i++) {
117         if(buf_array[i] != NULL && outID == StackTop(buf_array[i])){
118             Pop(buf_array[i]);
119             
120             printf("==>%d号车厢进入出轨口n",outID);
121             return TRUE;
122         }
123     }
124     return FALSE;
125     
126 
127     
128 }
129 /*************************************************************************
130 *功能描述：寻找最优缓冲轨
131 *参数列表：
132 *返回类型：
133 **************************************************************************/
134 void hold(int t_index ,stackADT buf_array[],int buf_num){
135 
136     int i,big = 0;
137     int ok_buf[2] = { -1,-1  };//用此数组来存放最优缓冲轨号和与该栈顶元素小的数组
138     
139     //big用来记录栈顶元素比当前要存放的车号差距
140     for (i = 0; i < buf_num; i++) {
141         if(buf_array[i] != NULL && StackDepth(buf_array[i])>0 && StackTop(buf_array[i])> t_index){
142             big = StackTop(buf_array[i]) - t_index;
143             if(ok_buf[0] == -1){
144                 ok_buf[0] = i;
145                 ok_buf[1] = big;
146             }else if(ok_buf[1] > big){ //当找到与车号差距更小的缓冲轨时，记录来下，备作最优
147                 ok_buf[0] = i;
148                 ok_buf[1] = big;                
149             }
150         }
151     }
152     //当没有找到最优缓冲轨时，放入新的一个缓冲轨中.
153     if(ok_buf[0] == -1 ){
154         //未找到最优缓冲轨
155         int m;
156         for (m = 0; m < buf_num; m++) {
157             if(buf_array[m] == NULL){
158                 buf_array[m] = NewStack();
159                 Push(buf_array[m],t_index);
160                 printf("%d号车厢存放到第%d个缓冲轨中n",t_index,m);
161                 
162                 return;
163             }
164         }
165         //若未成功放入一个新的缓冲轨时，说明没有足够的缓冲，
166         Error("缓冲轨不足，无法完成重排n");
167         
168     }else{
169         //已经找到最优缓冲轨
170         Push(buf_array[ok_buf[0]],t_index);
171         printf("%d号车厢存放到第%d个缓冲轨中n",t_index,ok_buf[0]);
172         return;
173     }
174     
175 }
176 
177 /* trainsort.c ends here */

CC编译运行：

若将50行的缓冲轨个数改成2,则出现缓冲不足的情况，无法完成重排，见下图：

小结：

自从用了堆栈抽象数据类型的定义，使火车厢重排只需要关注自己的业务应用逻辑代码，即使将来有所变动，层次清晰，也很好定位和修改

原文链接: https://www.cnblogs.com/linux-sir/archive/2012/08/10/2632261.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍