南理工2016考研复试上机题男女程序员排队

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define MALE 5   //队列中男程序员位数
  4 #define FEMALE 5 //队列中女程序员位数
  5 struct swap    //记录交换操作的结构体类型
  6 {
  7    int k;      //右交换下标
  8    int i;      //左交换下标
  9    struct swap *next;  //后继指针
 10    struct swap *front; //前驱指针
 11 };
 12 typedef struct swap swap1;
 13 
 14 struct image  //保存找到的交换操作序列的结构体类型
 15 {
 16     int k;    //右交换下标
 17     int i;    //左交换下标
 18     struct image *next;
 19 };
 20 typedef struct image image1;
 21 int number(int i, char que[]);   //函数，寻找当前序列索引下标i后的第一位女程序员下标,找到返回下标，没有找到返回-1
 22 void copy(swap1 *head, image1 *head1);    //释放head1指向的线性链表,并将head指向的交换序列链表拷贝至链表head1中
 23 
 24 void main()
 25 {
 26    int start;  //从队列开头起连续排列的女程序员序列中最后一位女程序员下标,若队列第一位是男程序员,start为-1
 27    char que[MALE+FEMALE];     //存放男女程序员队列的数组,字符'0'代表男程序员,'1'代表女程序员
 28    printf("输入男女程序员序列,0男1女\n");    //输入男女程序员序列
 29    scanf("%s", que);
 30 
 31    start=0;
 32    while(que[start]!='0')
 33    {
 34        if (que[start]=='0')   //确定从队列开头起连续排列的女程序员序列中最后一位女程序员下标
 35            break;
 36        start++;
 37    }
 38    start-=1;
 39 
 40    if (start==FEMALE-1)    //女程序员已全部放到男程序员前面，无需交换
 41    {
 42        printf("最小交换次数为0\n");
 43    }
 44    else
 45    {
 46        swap1 *head, *psnew, *before, *after;  //after指向head链表最后一个结点,before指向倒数第二个
 47        image1 *head1, *psnew1;
 48        int i, k, count, flag, minswap;  //i为回溯过程中前进深度，任何时候下标i及i前面下标位置的元素均为女程序员，k为在某下标之后找到的第一位女程序员标号
 49        char temp;                       //count用于统计交换次数,minswap为最小交换次数
 50        bool TF;                         //TF为true表示从上一轮回溯至本轮,为false表示从上一轮前进至本轮
 51        head=(swap1 *) malloc(sizeof(swap1));    //初始化交换序列链表,用于保存找到的可行交换序列
 52        head->next=NULL;
 53        head->front=NULL;
 54        before=head;
 55        after=head;
 56 
 57        head1=(image1 *) malloc(sizeof(image1));   //初始化head1链表，用于保存交换次数最少的交换序列
 58        head1->next=NULL;
 59 
 60        i=start;
 61        TF=false;
 62        count=0;
 63        flag=0;
 64 
 65        while (1)
 66        {
 67            if (i==start) //从start处开始试探
 68            {
 69                if (TF==false)  //第一次试探
 70                {
 71                    k=number(i, que);  
 72                }
 73                else
 74                {
 75                    k=number(k, que);
 76                    if (k==-1)    //在start处已无法找到下一个可交换女程序员，试探结束
 77                        break;
 78                }
 79 
 80                temp=que[i+1];
 81                que[i+1]=que[k];   //找到可交换女程序员k，交换i+1,,和k
 82                que[k]=temp;
 83                count++;
 84                psnew=(swap1 *) malloc(sizeof(swap1));
 85                psnew->k=k;
 86                psnew->i=i+1;         //交换操作(i+1, k)加入链表
 87                psnew->next=NULL;
 88                after->next=psnew;
 89                psnew->front=after;
 90                before=after;
 91                after=psnew;
 92                i++;                //递进至下一层
 93                TF=false;
 94            }
 95            else
 96            {
 97                if (TF==false)      //进至新的一层i>start,从i后开始寻找第一个女程序员位置
 98                    k=number(i, que);
 99                else
100                    k=number(k, que);   //回溯至本层，从上一次找到的女程序员位置后寻找第一个女程序员
101 
102                if (k==-1)
103                {
104                    if (TF==false)
105                    {
106                        if (flag==0)        //所有女程序员均已排到男程序员前面,判断flag值，比较count以决定是否更新count和head1链表
107                        {
108                            copy(head, head1);
109                            minswap=count;
110                            flag=1;
111                        }
112                        else
113                        {
114                            if (minswap>count)
115                            {
116                                copy(head, head1);
117                                minswap=count;
118                            }
119                        }
120                    }
121 
122                    k=after->k;  //找到最后一轮交换操作(i,k)
123                    i=after->i;
124                    temp=que[i];
125                    que[i]=que[k]; //,回溯交换que[i],que[k]
126                    que[k]=temp;
127                    count--;
128                    free(after);
129                    before->next=NULL;   //删掉head链表尾节点
130                    after=before;
131                    before=before->front;
132                    i--;    //回溯至上一层
133                    TF=true;
134                }
135                else
136                {
137                    if (k!=i+1)    //进入本层时TF==false,此时从i后寻找第一个女程序员下标，由于找到的女程序员要和i+1位置交换
138                    {
139                        temp=que[i+1];    //所以，若该女程序员就位于i+1位置，该段语句不执行，否则就应
140                        que[i+1]=que[k];  //将找到的女程序员k和i+1交换，并将交换操作放入head链表
141                        que[k]=temp;
142                        count++;
143                        psnew=(swap1 *) malloc(sizeof(swap1));
144                        psnew->k=k;
145                        psnew->i=i+1;
146                        psnew->next=NULL;
147                        after->next=psnew;
148                        psnew->front=after;
149                        before=after;
150                        after=psnew;
151                    }
152                    i++;    //递进至下一层
153                    TF=false;
154                }
155            }
156        }
157        printf ("把女程序员交换至最前面所需最小交换次数为%d\n", minswap);    //输出最小交换次数
158        printf("交换次数最小的交换方式为:\n");
159        i=start+1;
160        for (psnew1=head1->next; psnew1!=NULL; psnew1=psnew1->next)    //输出交换操作
161        {
162            printf("交换序列中第%d个和第%d个程序员\n", psnew1->i+1, psnew1->k+1);
163        }
164    }
165 }
166 
167 int number(int i, char que[])
168 {
169     for (int j=++i; j<MALE+FEMALE; j++)
170     {
171         if (que[j]=='1')
172             return j;
173     }
174 
175     return -1;
176 }
177 
178 void copy(swap1 *head, image1 *head1)
179 {
180     image1 *p, *tail;
181     swap1 *psnew;
182 
183     while(head1->next!=NULL)    //释放head1链表
184     {
185         p=head1->next;
186         head1->next=p->next;
187         free(p);
188     }
189 
190     tail=head1;
191     for (psnew=head->next; psnew!=NULL; psnew=psnew->next)
192     {
193         p=(image1 *) malloc(sizeof(image1));   //拷贝
194         p->k=psnew->k;
195         p->i=psnew->i;
196         p->next=NULL;
197         tail->next=p;
198         tail=p;
199     }
200 }