Question

求一个C语言问题：我的代码如下，这样的题有专门的算法吗？

想问的是在最后判断的时候如何将这两组字符串先判断所有再输出漏掉的？
原题如图：

#include<stdio.h>
int main()
{
char a[10][20],b[10][20],c[10];
int x=0,i,j,n;
scanf("%d",&n);
if (n==0)
return 0;
for (i=0;i<n;i++)
scanf("%s",a[i]);
for (i=0;i<n;i++)
{
for (j=0;j<n-1;j++)
{
if (strcmp(a[i],b[j])!=0)
{
printf("case x+1 :%s\n",a[i]);
x=x+1;
return 0;
}
}
}
}

Answer 1

似乎程序里有问题

//1.没看到b的初始化
// 2. printf里面，x也是变量，不是字符常量

写个很直接的文字算法给你

//a[ ]是应到课人员名单，b[ ]是实际到课人员名单的话
//对于每一个a[i]

//应该是看a[i]是否在b[]里出现对吧。也就是说，在实际到课名单里b[ ]中搜索一个应该到课的学生a[i]，如果找到，则不用列出这个名字，否则输出这个名字。而且需要每个跷课的人（b中找不到的人）都输出。
//所以：你的两层循环变量没有问题

//但是进入循环前 需要一个bool值NOTFound作为找到与否的标志，默认为真。
// 因为要和每一个b中的值进行比较,所以不到最后不知道是否缺课，
// 如果某个b[j]和a[i]相同

// 则置NOTFound为假，否则不变。
// 内层循环结束后，
// 如果NOTFound为真，输出这个名字，即输出a[i]
// 然后重置NOTFound为真.

如果不进行预排列，这个需要查找每个元素的算法，时间复杂度是O(n*n)，双循环嘛，呵呵 。
你如果用open hash表一开始就对输入的数据b[]进行排序和优化的话，比如前面有人说到的按首字母建立静态数组，第0位代表字母a,第1位代表字母b，以此类推。然后首字母相同的单词链接在数组对应的位置后面，那么查找部分的效率可以变成接近O(n)。但是前面需要一些辅助函数，比如把字符转化为数值，以及对节点的定义和链表的操作。

Answer 2

很简单啊
因为每次只有一个人没到，所以把每组的所有名字异或就好了，结果就是没有到人的名字。
时间复杂度O(n)

#include <string.h>#include<stdio.h>
int main()
{

char a[50],b[50],c[10][50];

int x=0,i,j,index,n;

index=0;
while(1)
{
memset(a,0,50);
scanf("%d",&n);

if(n==0)
break;

n=n+n-1;
for (i=0;i<n;i++)
{
scanf("%s",b);
for(j=0;b[j]!='\0';j++)
a[j]^=b[j];
}

strcpy(c[index++],a);

}

for(i=0;i<index;i++)
printf("case %d : %s\n",i+1,c[i]);
return 0;
}

Answer 3

可以先按照单词的字典排序，然后对两个字符数组比较 如果遇到不等的 那么就是那个学生没来 复杂度是 o（nlogn+n） ，应该有更好的算法，容我想想

追问

谢谢精炼的回答，可是这样的话时间开销有压力吗？？

追答

时间开销就下去了啊，你原来的时间复杂度是 n^2