目录
2. 【函数】在顺序表中，输入一个元素插入到原表的最小元素之前
1. 【程序片段题】约瑟夫问题（顺序表实现）
【问题描述】
约瑟夫环问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀的顺序是：5，4，6，2，3，1。
【输入形式】
输入两个正整数N和M，N表示N个人，M表示报数到M；
【输出形式】
输出依次出列的序号。以空格作为分隔。
【样例输入1】
6 5
1 2 3 4 5 6
【样例输出1】
5 4 6 2 3 1
【样例输入2】
3 3
3 2 1
【样例输出2】
1 3 2
【评分标准】
用顺序表实现，补充函数内容实现程序要求。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct List{
int *data;
int len;
int size;
}List,*PList;
int Init(PList L){
L->data=(int *)malloc(sizeof(int));
L->len=0;
L->size=MAX;
return 1;
}
int Create(PList L,int n){
int i;
for(i=0;i<n;i++){
scanf("%d",&L->data[i]);
L->len++;
}
return 1;
}
int YSF(PList L,int n,int m){
int i,t,k;
k=n;
t=0;
for(i=0;i<=n;i++){
if(i==n) i=0;
if(L->data[i]!=0) t++;
if(t==m){
printf("%d ",L->data[i]);
L->data[i]=0;
k--;
t=0;
}
if(k==0) break;
}
return 1;
}
int main(){
List L;
int n,m;
scanf("%d %d",&n,&m);
Init(&L);
Create(&L,n);
YSF(&L,n,m);
return 0;
}
2. 【函数】在顺序表中，输入一个元素插入到原表的最小元素之前
【问题描述】
设有顺序表，输入一个元素插入到顺序表最小元素之前。
【输入形式】
第一行输入一个N(N>=0且N<=100)；
第二行输入N个整数（以空格分隔）；
第三行输入一个整数（将该整数插入到顺序表最小元素之前）
【输出形式】
输出插入后的顺序表元素
【样例输入】
5
12 98 34 -87 -23
20
【样例输出】
12 98 34 20 -87 -23
【评分标准】
补充指定函数内容，不得修改程序中其他代码。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct List{
int *data;
int len;
int size;
}List,*PList;
int Init(PList L){
L->data=(int *)malloc(sizeof(int)*MAX);
L->len=0;
L->size=MAX;
return 1;
}
int Create(PList L){
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&L->data[i]);
L->len++;
}
return 1;
}
int Min(PList L){
int i,min,pos,e;
min=L->data[0];
scanf("%d",&e);
for(i=0;i<L->len;i++){
if(min>L->data[i]){
min=L->data[i];
}
}
for(i=0;i<L->len;i++){
if(L->data[i]==min){
pos=i;
break;
}
}
for(i=L->len-1;i>=pos;i--){
L->data[i+1]=L->data[i];
}
L->data[pos]=e;
L->len++;
return 1;
}
int Print(PList L){
int i;
for(i=0;i<L->len;i++){
printf("%d ",L->data[i]);
}
printf("\n");
return 1;
}
int main(){
List L;
Init(&L);
Create(&L);
Min(&L);
Print(&L);
return 0;
}
3. 顺序表实现集合差集
【问题描述】
设两个集合A、B用顺序表表示，求A-B。
【输入形式】第一行输入两个整数N、M（大于0小于100），分别表示两个集合的长度；
第二行输入第一个集合的N个元素；
第三行输入第二个集合的M个元素；
【输出形式】
输出第一个集合和第二个集合的差集。（若差集为空集，则输出*）
【样例输入1】
5 4
4 23 -9 30 6
23 45 6 2
【样例输出1】
4 -9 30
【样例输入2】
4 6
10 20 30 40
10 20 30 40 50 60
【样例输出2】
*
【评分标准】
必须用顺序表表示集合；差集运算用算法函数实现，实现过程利用顺序表的基本操作。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct List{
int *data;
int len;
int size;
}List,*PList;
int Init(PList L){
L->data=(int *)malloc(sizeof(int)*MAX);
L->len=0;
L->size=MAX;
return 1;
}
int Create(PList L,int n){
int i;
for(i=0;i<n;i++){
scanf("%d",&L->data[i]);
L->len++;
}
return 1;
}
int Delete(PList L,int e){
int i,pos;
for(i=0;i<L->len;i++){
if(L->data[i]==e){
pos=i;
break;
}
}
for(i=pos;i<L->len-1;i++){
L->data[i]=L->data[i+1];
}
L->len--;
return 1;
}
PList f(PList L1,PList L2){
int i,j;
for(i=0;i<L1->len;i++){
for(j=0;j<L2->len;j++){
if(L1->data[i]==L2->data[j]){
Delete(L1,L1->data[i]);
i--;
break;
}
}
}
return L1;
}
int Print(PList L){
int i;
for(i=0;i<L->len;i++){
printf("%d ",L->data[i]);
}
printf("\n");
return 1;
}
int main(){
List L1,L2;
int m,n;
scanf("%d %d",&n,&m);
Init(&L1);
Init(&L2);
Create(&L1,n);
Create(&L2,m);
f(&L1,&L2);
if(L1.len==0) printf("*\n");
else Print(&L1);
return 0;
}
4. 【函数】删除顺序表中第一个值等于x的元素
【问题描述】
设有顺序表，删除顺序表中第一个值等于x的元素。
【输入形式】
第一行输入一个N(N>=0且N<=100)；
第二行输入N个整数（以空格分隔）；
第三行输入要删除的元素值x。
【输出形式】
输出删除第一个值等于x的元素后的顺序表
【样例输入】
5
12 98 34 -87 -23
34
【样例输出】
12 98 -87-23
【评分标准】
补充函数，完成上述功能。
#include<stdio.h>
#include<malloc.h>
#define MAX 10
#define IN 10
typedef struct List{
int *data;
int len;
int size;
}List,*PList;
int Init(PList L){
L->data=(int *)malloc(sizeof(int)*MAX);
L->len=0;
L->size=MAX;
return 1;
}
int Create(PList L){
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&L->data[i]);
L->len++;
}
return 1;
}
int Print(PList L){
int i;
for(i=0;i<L->len;i++){
printf("%d ",L->data[i]);
}
return 1;
}
int Delete(PList L){
int x;
scanf("%d",&x);
int i,j;
for(i=0;i<L->len;i++){
if(L->data[i]==x){
for(j=i;j<L->len-1;j++){
L->data[j]=L->data[j+1];
}
L->len--;
break;
}
}
return 1;
}
int main(){
List L;
Init(&L);
Create(&L);
Delete(&L);
Print(&L);
return 0;
}