C++机试题

谁践踏了优雅 2022-08-03 12:45 139阅读 0赞

1．第一题的题目大概是输入整型数组求数组的最小数和最大数之和，例如输入1,2,3,4则输出为5，当输入只有一个数的时候，则最小数和最大数都是该数，例如只输入1，则输出为2；另外数组的长度不超过50

void main()  
\{  
int num\[50\] = \{ 0 \};  
int i, n;  
  
printf("请输入整型数组的长度(1~50)：");  
scanf("%d", &n);  
  
printf("请输入整型数组的元素：");  
for (i = 0; i<n; i++)  
\{  
scanf("%d", &num\[i\]);  
\}  
int min\_num = num\[0\];  
int max\_num = num\[0\];  
for (int j = 0; j<n; j++)  
\{  
if (max\_num<num\[j\])  
max\_num = num\[j\];  
else if (min\_num>num\[j\])  
min\_num = num\[j\];  
\}  
int sum = min\_num + max\_num;  
printf("数组中最大与最小值之和：%d\\n", sum);  
system("pause");

2．求两个长长整型的数据的和并输出，例如输入2132786478358458，354638543895，则输出。。。。

void main()  
\{  
char \*num1, \*num2; //两个长长整型数据  
int len\_num1, len\_num2; // 两个长长整型数据的长度  
int len\_max, len\_min;  
num1 = (char\*)malloc(sizeof(char));  
num2 = (char\*)malloc(sizeof(char));  
printf("输入两个长长整型数据：");  
scanf("%s", num1);  
printf("输入两个长长整型数据：");  
scanf("%s", num2);  
len\_num1 = strlen(num1);  
len\_num2 = strlen(num2);  
len\_max = (len\_num1 >= len\_num2) ? len\_num1 : len\_num2;  
len\_min = (len\_num1 <= len\_num2) ? len\_num1 : len\_num2;  
  
int max\_len = len\_max;  
char temp='0';  
char \* sum = (char \*)malloc(sizeof(char)\*len\_max);  
int i, j;  
for (int j = len\_num1 - 1, k = len\_num2 - 1; j >= 0 && k >= 0; j--, k--)  
\{  
int data = num1\[j\] - '0' + num2\[k\] - '0' + temp - '0';  
if (data > 10)  
temp = '1';  
else  
temp = '0';  
sum\[i - 1\] = data + '0';  
i--;  
\}  
i = 0;  
if (len\_num1>len\_num2)  
\{  
while (len\_num1 - len\_num2)  
\{  
sum\[i\] = num1\[i\];  
len\_num1--;  
\}  
\}  
else  
\{  
while (len\_num2 - len\_num1)  
\{  
sum\[i\] = num2\[i\];  
len\_num2--;  
\}  
\}  
sum\[len\_max\] = '\\0';  
printf("两数相加结果为：%s\\n", sum);  
system("pause");  
\}

3.通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。

比如字符串“abacacde”过滤结果为“abcde”。

void main()  
\{  
char \*str,\*outstream;  
  
str = (char\*)malloc(sizeof(char));  
outstream = (char\*)malloc(sizeof(char));  
printf("输入字符串：");  
scanf("%s", str);  
int i = 0,k=0;  
outstream\[i\] = str\[i\];  
i++; k++;  
while (str\[i\]!='\\0')  
\{  
for (int j = 0; j < i; j++)  
\{  
if (str\[i\] != str\[j\])  
\{  
if (j == i - 1)  
\{  
outstream\[k\] = str\[i\];  
k++;  
\}  
else  
continue;  
\}  
break;  
\}  
i++;  
\}  
outstream\[k\] = '\\0';  
printf("\\n%s\\n", outstream);  
system("pause");  
\}

逻辑有点麻烦了，但是代码比较简单。

4.通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。

压缩规则：

1. 仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc".

2. 压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"

void main()  
\{  
char \*str,\*outstream;  
str = (char\*)malloc(sizeof(char));  
outstream = (char\*)malloc(sizeof(char));  
printf("输入字符串：");  
scanf("%s", str);  
int i = 0, count = 1, k = 0;  
while (str\[i\]!='\\0')  
\{  
if (str\[i\] == str\[i + 1\])  
count++;  
else  
\{  
if (count > 1)  
\{  
outstream\[k\] = count + '0';  
k++;  
count = 1;  
\}  
outstream\[k\] = str\[i\];  
k++;  
\}  
i++;  
\}  
outstream\[k\] = '\\0';  
printf("\\n%s\\n", outstream);  
system("pause");  
\}

5.通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。

输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。

补充说明：

1. 操作数为正整数，不需要考虑计算结果溢出的情况。

2. 若输入算式格式错误，输出结果为“0”。

void main()  
\{  
char \*str,\*outstream;  
str = (char\*)malloc(sizeof(char));  
outstream = (char\*)malloc(sizeof(char));  
char str1\[10\];  
char str2\[10\];  
char str3\[10\];  
printf("输入字符串：");  
scanf("%s %s %s", str1,str2,str3);  
  
char temp = '0';  
int len1 = strlen(str1);  
int len3 = strlen(str3);  
  
int len\_max = (len1 > len3) ? len1 : len3;  
int i = len\_max;  
switch (str2\[0\])  
\{  
case '+':  
for (int j = len1-1,k=len3-1; j >= 0&&k>=0; j--,k--)  
\{  
int data = str1\[j\] - '0' + str3\[k\] - '0' + temp - '0';  
if (data > 10)  
temp = '1';  
else  
temp = '0';  
outstream\[i-1\] = data + '0';  
i--;  
\}  
i = 0;  
if (len1>len3)  
\{  
while (len1-len3)  
\{  
outstream\[i\] = str1\[i\];  
len1--;  
\}  
\}  
else  
\{  
while (len3 - len1)  
\{  
outstream\[i\] = str3\[i\];  
len3--;  
\}  
\}  
outstream\[len\_max\] = '\\0';  
break;  
case '-':  
int data;  
for (int j = len1-1,k=len3-1; j >= 0&&k>=0; j--,k--)  
\{  
if ((str1\[j\] - '0') < (str3\[k\] - '0'))  
\{  
data = 10 + (str1\[j\] - '0') - (str3\[k\] - '0') - (temp - '0');  
temp = '1';  
\}  
else  
\{  
data = str1\[j\] - '0' - str3\[k\] - '0';  
temp = '0';  
\}  
outstream\[i - 1\] = data + '0';  
i--;  
\}  
i = 0;  
if (len1>len3)  
\{  
while (len1 - len3)  
\{  
if (temp == '1')  
\{  
outstream\[i\] = (str1\[i\] - '0') - (temp - '0') + '0';  
temp = '0';  
\}  
else  
outstream\[i\] = str1\[i\];  
len1--;  
\}  
\}  
else  
\{  
while (len3 - len1)  
\{  
if (temp == '1')  
\{  
outstream\[i\] = str3\[i\] - '0' - temp - '0' + '0';  
temp = '0';  
\}  
else  
outstream\[i\] = str3\[i\];  
len3--;  
\}  
\}  
outstream\[len\_max\] = '\\0';  
break;  
\}  
printf("两数运算：%s %s %s = %s\\n",str1,str2,str3,outstream);  
system("pause");  
\}

6.一组人（n个），围成一圈，从某人开始数到第三个的人出列，再接着从下一个人开始数，最终输出最终出列的人

（约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。）

typedef struct Node  
\{  
int data;  
struct Node \*next;  
\}LinkList;  
  
LinkList \*create(int n)  
\{  
LinkList \*p, \*q, \*head;  
int i = 1;  
p = (LinkList\*)malloc(sizeof(LinkList));  
p->data = i;  
head = p;  
  
for (i = 1; i <= n; i++)  
\{  
q = (LinkList\*)malloc(sizeof(LinkList));  
q->data = i + 1;  
p->next = q;  
p = q;  
\}  
p->next = head; //使链表尾连接链表头，形成循环链表  
return head;  
free(p);  
p = NULL;  
free(q);  
q = NULL;  
\}  
  
void deletefun(LinkList \*L, int m)  
\{  
LinkList \*p, \*q, \*temp;  
int i;  
p = L;  
q = L;  
while (p->next != p)  
\{  
for ( i = 1; i < m; i++)  
\{  
q = p;  
p = p->next;  
\}  
printf("%5d", p->data);  
temp = p;  
q->next = p->next;  
p = p->next;  
free(temp);  
\}  
printf("%5d\\n", p->data);  
\}  
  
void main()  
\{  
int n = 7, m = 3;  
LinkList \*head1;  
head1 = create(n);  
deletefun(head1,m);  
  
system("pause");  
\}

7..输入一串字符，只包含“0-10”和“，”找出其中最小的数字和最大的数字（可能不止一个），输出最后剩余数字个数。如输入 “3,3,4,5,6,7,7”

void main()  
\{  
char \*str;  
str = (char \*)malloc(sizeof(char));  
printf("请输入字符串！\\n");  
scanf("%s", str);  
int array\[50\];  
int i = 0,k=0;  
while (str\[i\] != '\\0')  
\{  
if (str\[i\] >= '0'&&str\[i\] <= '9')  
\{  
array\[k\] = str\[i\] - '0';  
k++;  
\}  
i++;  
\}  
int max = array\[0\];  
int min = array\[0\];  
int result = k;  
for (int j = 0; j < k; j++)  
\{  
if (max < array\[j\])  
max = array\[j\];  
if (min>array\[j\])  
min = array\[j\];  
\}  
for (int j = 0; j < k; j++)  
\{  
if (array\[j\] == min||array\[j\]==max)  
result--;  
\}  
printf("剩余数字个数为:%d", result);  
system("pause");  
\}

8.输入一组身高在170到190之间（5个身高），比较身高差，选出身高差最小的两个身高；若身高差相同，选平均身高高的那两个身高；从小到大输出；  
如 输入 170 181173 186 190 输出 170 173

void main()  
\{  
int str\[50\] = \{ 0 \};  
int n;  
printf("请输入数组长度：");  
scanf("%d", &n);  
for (int i = 0; i < n; i++)  
\{  
scanf("%d", &str\[i\]);  
\}  
int maxcount = str\[0\];  
int max = str\[0\];  
int temp1, temp2;  
int currentdata = str\[0\];  
for (int i = 0; i < n; i++)  
\{  
for (int j = 0; j!=i&&j < n; j++)  
\{  
max = abs(str\[i\] - str\[j\]);  
if (maxcount > max)  
\{  
maxcount = max;  
temp1 = str\[i\];  
temp2 = str\[j\];  
\}  
\}  
\}  
cout << "|" << temp1 << "-" << temp2 << "|" << "=";  
cout << maxcount << endl;  
system("pause");  
\}

9. **删除子串**，只要是原串中有相同的子串就删掉，不管有多少个，返回子串个数,输出剩余子串

int delete\_sub\_str(const char \*str, const char \* sub\_str, char\*result)  
\{  
assert(str != NULL&&sub\_str != NULL);  
const char \*p, \*q;  
char \*t, \*temp;  
p = str;  
q = sub\_str;  
t = result;  
int n, count = 0;  
n = strlen(q);  
temp = (char\*)malloc(n + 1);  
memset(temp, 0x00, n + 1);  
while (\*p)  
\{  
memcpy(temp, p, n);  
if (strcmp(temp, q) == 0)  
\{  
count++;  
p = p + n;  
\}  
else  
\{  
\*t = \*p;  
p++;  
t++;  
\}

memset(temp, 0x00, n + 1);  
\}  
free(temp);  
return count;  
\}  
void main()  
\{  
char s\[100\] = \{ '\\0' \};  
int num = delete\_sub\_str("123abc12de345fg1hi34j123k", "123", s);  
cout << num << endl;  
cout << s << endl;  
system("pause");  
\}

10. 要求编程实现上述高精度的十进制加法。要求实现函数：void add (const char \*num1,const char \*num2, char \*result)

【输入】num1：字符串形式操作数1，如果操作数为负，则num1\[0\]为符号位'-'

num2：字符串形式操作数2，如果操作数为负，则num2\[0\]为符号位'-'

【输出】result：保存加法计算结果字符串，如果结果为负，则result\[0\]为符号位。

void move(char \*str, int length)

\{  
if (str\[0\] != '-')  
return;  
int i;  
for ( i = 0; i < length-1; i++)  
\{  
str\[i\] = str\[i + 1\];  
\}  
str\[i\] = '\\0';  
\}  
int remove\_zero(char \*result, int length)  
\{  
int count = 0;  
for (int i = length-1; i < 0; i--)  
\{  
if (result\[i\] == '\\0')  
\{  
result\[i\] = '\\0';  
count++;  
\}  
else  
return length - count;  
\}  
return length - count;  
\}  
  
void reverse(char \*result, int length)  
\{  
char temp;  
for (int i = 0; i < (length-1)/2; i++)  
\{  
temp = result\[i\];  
result\[i\] = result\[length - 1 - i\];  
result\[length - 1 - i\] = temp;  
\}  
\}  
  
int real\_add(char \* str1, char \*str2, char \*result, const bool flag)  
\{  
int len1 = strlen(str1);  
int len2 = strlen(str2);  
int n1, n2, another = 0;  
int cur\_rs = 0;  
int i, j;  
int curSum;  
for ( i = len1-1,j=len2-1; i >= 0&&j>=0; i--,j--)  
\{  
n1 = str1\[i\] - '0';  
n2 = str2\[i\] - '0';  
curSum = n1 + n2 + another;  
result\[cur\_rs++\] = curSum % 10 + '0';  
another = curSum / 10;  
\}  
if (j < 0)  
\{  
while (i>=0)  
\{  
n1 = str1\[i--\] - '0';  
curSum = n1 + another;  
result\[cur\_rs++\] = curSum % 10 + '0';  
another = curSum / 10;  
\}  
if (another != 0)  
result\[cur\_rs++\] = another + '0';  
\}  
else  
\{  
while (j >= 0)  
\{  
n2 = str2\[j--\] - '0';  
curSum = n2 + another;  
result\[cur\_rs++\] = curSum % 10 + '0';  
another = curSum / 10;  
\}  
if (another != 0)  
result\[cur\_rs++\] = another + '0';  
\}  
result\[cur\_rs\] = '\\0';  
cur\_rs = remove\_zero(result, cur\_rs);  
if (!flag)  
\{  
result\[cur\_rs++\] = '-';  
result\[cur\_rs\] = '\\0';  
\}  
reverse(result, strlen(result));  
return cur\_rs;  
\}  
  
int real\_minus(char \*str1, char \*str2, char \*result)  
\{  
int big\_len, sml\_len;  
int len1 = strlen(str1);  
int len2 = strlen(str2);  
bool flag = false;  
  
  
if (len1 < len2)  
flag = true;  
else if (len1 == len2)  
\{  
if (strcmp(str1, str2) == 0)  
\{  
result\[0\] = '0';  
result\[1\] = '\\0';  
return 1;  
\}  
else if (strcmp(str1, str2) < 0)  
flag = true;  
\}  
if (flag)  
\{  
char \*temp = str1;  
str1 = str2;  
str2 = temp;  
len1 = strlen(str1);  
len2 = strlen(str2);  
\}  
int n1, n2, another = 0;  
int i, j;  
int cur\_rs = 0;  
int curMinus;  
  
  
for ( i = len1-1,j=len2-1; i >=0&&j>=0; i--,j--)  
\{  
n1 = str1\[i\] - '0';  
n2 = str2\[i\] - '0';  
if (n1 >= n2 + another)  
\{  
result\[cur\_rs++\] = (n1 - n2 - another) + '0';  
another = 0;  
\}  
else  
\{  
result\[cur\_rs++\] = (n1 + 10 - n2 - another) + '0';  
another = 1;  
\}  
\}  
while (i >= 0)  
\{  
n1 = str1\[i--\] - '0';  
if (another != 0)  
\{  
n1 -= another;  
another = 0;  
\}  
result\[cur\_rs++\] = n1 + '0';  
\}  
result\[cur\_rs\] = '\\0';  
cur\_rs = remove\_zero(result, cur\_rs);  
if (flag)  
\{  
result\[cur\_rs++\] = '-';  
result\[cur\_rs\] = '\\0';  
\}  
reverse(result, cur\_rs);  
return cur\_rs;  
\}  
void addi(const char\*num1, const char \*num2, char \*result)  
\{  
int len1 = strlen(num1);  
int len2 = strlen(num2);  
int rs\_len;  
if (!len1 || !len2)  
return;  
char str1\[100\], str2\[100\];  
strncpy(str1, num1, len1);  
str1\[len1\] = '\\0';  
strncpy(str2, num2, len2);  
str2\[len2\] = '\\0';  
  
if (str1\[0\] == '-'&&str2\[0\] == '-')  
\{  
move(str1, len1);  
move(str2, len2);  
rs\_len = real\_add(str1, str2, result, false);  
\}  
else if (str1\[0\] == '-')  
\{  
move(str1, len1);  
rs\_len = real\_minus(str2, str1, result);  
\}  
else if (str2\[0\] == '-')  
\{  
move(str2, len2);  
rs\_len = real\_minus(str1, str2, result);  
\}  
else  
rs\_len = real\_add(str1, str2, result, true);  
\}  
void main()  
\{  
char num1\[100\], num2\[100\];  
printf("请输入两个整形数据：\\n");  
scanf("%s %s", num1, num2);  
char result\[100\];  
memset(result, 0, 100);  
addi(num1, num2, result);  
printf("%s\\n", result);  
system("pause");  
\}

11. 描述：10个学生考完期末考试评卷完成后，A老师需要划出及格线，要求如下：  
(1) 及格线是10的倍数；  
(2) 保证至少有60%的学生及格；  
(3) 如果所有的学生都高于60分，则及格线为60分

输入：输入10个整数，取值0~100

输出：输出及格线，10的倍数

void bubblesort(int arr\[\])  
\{  
int i, j, temp;  
for ( i = 0; i < 10; i++)  
\{  
for ( j = i; j < 10; j++)  
\{  
if (arr\[i\]>arr\[j\])  
\{  
temp = arr\[i\];  
arr\[i\] = arr\[j \];  
arr\[j \] = temp;  
\}  
\}  
\}  
\}  
int GetPassLine(int a\[\])  
\{  
bubblesort(a);  
if (a\[0\] >= 60)  
return 60;  
else  
return (((int)a\[4\] / 10) \* 10);  
\}  
  
void main()  
\{  
int a\[10\] = \{ 0 \};  
int result;  
printf("请输入10个分数：\\n");  
for (int i = 0; i < 10; i++)  
\{  
scanf("%d", &a\[i\]);  
\}  
result = GetPassLine(a);  
cout << "及格线：" << result << endl;  
system("pause");  
\}

12. 描述：一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯，从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始，电灯全部关着。

有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下；接着第二个学生把号码凡是2的倍数的电灯的开关拉一下；接着第三个学生把号码凡是3的倍数的电灯的开关拉一下；如此继续下去，最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后，长廊里电灯有几盏亮着。注：电灯数和学生数一致。

输入：电灯的数量

输出：亮着的电灯数量

样例输入：3

样例输出：1

\#define MAX\_NUMBER 65535  
  
int Getd(int n)  
\{  
int data\[MAX\_NUMBER\] = \{ 0 \};  
int count = 0;  
for (int i = 1; i <= n; i++)  
\{  
for (int j = 1; j <=n; j++)  
\{  
if (j%i == 0)  
data\[j\] ^= 1;  
\}  
\}  
for (int i = 0; i < n; i++)  
\{  
if (data\[i\] == 1)  
count++;  
\}  
return count;  
\}  
  
void main()  
\{  
int n;  
printf("请输入点灯数：");  
scanf("%d", &n);  
int d = Getd(n);  
cout << "剩余点灯数：" << d << endl;  
system("pause");  
\}

# 13.描述：已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。 #

地铁线A（环线）经过车站：A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18  
地铁线B（直线）经过车站：B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15

输入：输入两个不同的站名

输出：输出最少经过的站数,含输入的起点和终点，换乘站点只计算一次

输入样例：A1 A3

输出样例：3

\#define MAX\_NUMBER 65535

\#define MAX 35  
\#define SUBWAY\_A 20  
\#define SUBWAY\_B 17  
typedef struct node  
\{  
int adjvex;  
struct node \*next;  
\}edgenode;  
  
  
typedef struct  
\{  
char name\[10\];  
bool flag;  
edgenode \*link;  
\}vexnode;  
  
const char subway\_name\[SUBWAY\_A\]\[10\] = \{ "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "T1", "A10", "A11", "A12", "A13", "T2", "A14", "A15 ", "A16", "A17", "A18" \};  
const char subway\_name2\[SUBWAY\_B\]\[10\] = \{ "B1", "B2", "B3", "B4", "B5", "T1", "B6", "B7", "B8", "B9", "B10", "T2", "B11", "B12", "B13", "B14", "B15" \};  
void create(vexnode ga\[\])  
\{  
int i;  
edgenode \*p;  
for ( i = 0; i < MAX; i++)  
\{  
ga\[i\].link = NULL;  
ga\[i\].flag = true;  
if (i < SUBWAY\_A)strcpy(ga\[i\].name, subway\_name\[i\]);  
else strcpy(ga\[i\].name, subway\_name2\[i - 20\]);  
\}  
for ( i = 0; i < SUBWAY\_A; i++)  
\{  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = i - 1;  
p->next = NULL;  
ga\[i\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = i + 1;  
p->next = NULL;  
ga\[i\].link->next = p;  
if (i == 9)  
\{  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 4;  
p->next = NULL;  
ga\[i\].link->next->next = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 5;  
p->next = NULL;  
ga\[i\].link->next->next->next = p;  
\}  
else if (i == 14)  
\{  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 9;  
p->next = NULL;  
ga\[i\].link->next->next = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 10;  
p->next = NULL;  
ga\[i\].link->next->next->next = p;  
\}  
\}  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A - 1;  
p->next = NULL;  
ga\[0\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 1;  
p->next = NULL;  
ga\[0\].link->next = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A - 2;  
p->next = NULL;  
ga\[SUBWAY\_A - 1\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 0;  
p->next = NULL;  
ga\[SUBWAY\_A - 1\].link->next = p;  
  
for ( i = 1; i < SUBWAY\_B-1; i++)  
\{  
if (i == 4 || i == 5 || i == 9 || i == 10)continue;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + i - 1;  
p->next = NULL;  
ga\[i + SUBWAY\_A\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + i - 1;  
p->next = NULL;  
ga\[i + SUBWAY\_A\].link->next = p;  
\}  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 3;  
p->next = NULL;  
ga\[SUBWAY\_A + 4\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 9;  
p->next = NULL;  
ga\[SUBWAY\_A + 4\].link->next = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 9;  
p->next = NULL;  
ga\[SUBWAY\_A + 5\].link = p;  
ga\[SUBWAY\_A + 5\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 6;  
p->next = NULL;  
ga\[SUBWAY\_A + 5\].link->next = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 8;  
p->next = NULL;  
ga\[SUBWAY\_A + 9\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 14;  
p->next = NULL;  
ga\[SUBWAY\_A + 9\].link->next = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = 14;  
p->next = NULL;  
ga\[SUBWAY\_A + 10\].link = p;  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 11;  
p->next = NULL;  
ga\[SUBWAY\_A + 10\].link->next = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + 1;  
p->next = NULL;  
ga\[SUBWAY\_A\].link = p;  
  
p = (edgenode\*)malloc(sizeof(edgenode));  
p->adjvex = SUBWAY\_A + SUBWAY\_B - 2;  
p->next = NULL;  
ga\[SUBWAY\_A + SUBWAY\_B - 1\].link = p;  
// 打印各邻接节点  
for (i = 0; i<MAX; i++)\{  
printf("%s:", ga\[i\].name);  
edgenode \*s;  
s = ga\[i\].link;  
while (s != NULL)\{  
printf("->%s", ga\[s->adjvex\].name);  
s = s->next;  
\}  
printf("\\n");  
\}  
\}  
  
void main()  
\{  
vexnode ga\[MAX\];  
create(ga);  
int i;  
char str\[2\]\[10\];  
while (scanf("%s%s", str\[0\], str\[1\]) != EOF)\{  
int temp = 0;  
for (i = 0; i<MAX; i++)\{  
ga\[i\].flag = true;  
if (!strcmp(str\[0\], ga\[i\].name)) temp = i;  
\}  
queue<vexnode>q;  
q.push(ga\[temp\]);  
ga\[temp\].flag = false;  
int count = 0;  
int start = 0;  
int end = 1;  
bool find\_flag = false;  
while (!q.empty())\{  
if (find\_flag) break;  
count++;  
printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");  
printf("第%d层搜索：", count);  
int temp\_end = end;  
while (start<temp\_end)\{  
printf("%s ", q.front().name);  
if (!strcmp(q.front().name, str\[1\]))\{  
find\_flag = true;  
break;  
\}  
edgenode \*s;  
s = q.front().link;  
while (s != NULL)\{  
if (ga\[s->adjvex\].flag)\{  
q.push(ga\[s->adjvex\]);  
ga\[s->adjvex\].flag = false;  
end++;  
//printf("%s ",ga\[s->adjvex\].name);  
\}  
s = s->next;  
\}  
q.pop();  
start++;  
\}  
printf("\\n");  
\}  
printf("%d\\n", count);  
\}  
system("pause");  
\}

14. 字串转换

问题描述：将输入的字符串（字符串仅包含小写字母‘a’到‘z’），按照如下规则，循环转换后输出：a->b,b->c,…,y->z,z->a；若输入的字符串连续出现两个字母相同时，后一个字母需要连续转换2次。例如：aa 转换为 bc，zz 转换为 ab；当连续相同字母超过两个时，第三个出现的字母按第一次出现算。  
要求实现函数：void convert(char \*input,char\* output)  
【输入】 char \*input , 输入的字符串  
【输出】 char \*output ，输出的字符串  
【返回】 无

void main()  
\{  
char \*str,\*outstream;  
str = (char \*)malloc(sizeof(char));  
outstream = (char \*)malloc(sizeof(char));  
printf("请输入字符串：");  
while (scanf("%s", str) != EOF)  
\{  
int i = 0, k = 0;  
int count = 1;  
while (str\[i\] != '\\0')  
\{  
if (count == 1)  
if (str\[i\] == 'z')  
outstream\[k\] = 'a';  
else  
outstream\[k\] = (char)((int)str\[i\] + 1);  
else if (count == 2)  
if (str\[i\] == 'z')  
outstream\[k\] = 'b';  
else  
outstream\[k\] = (char)((int)str\[i\] + 2);  
else  
if (str\[i\] == 'z')  
outstream\[k\] = 'a';  
else  
outstream\[k\] = (char)((int)str\[i\] + 1);  
if (str\[i + 1\] == str\[i\])  
count++;  
else  
count = 1;  
i++;  
k++;  
\}  
outstream\[k\] = '\\0';  
cout << outstream << endl;  
\}  
system("pause");  
\}

15. 在给定字符串中找出单词（ “单词”由大写字母和小写字母字符构成，其他非字母字符视为单词的间隔，如空格、问号、数字等等；另外单个字母不算单词）；找到单词后，按照长度进行降序排序，（排序时如果长度相同，则按出现的顺序进行排列），然后输出到一个新的字符串中；如果某个单词重复出现多次，则只输出一次；如果整个输入的字符串中没有找到单词，请输出空串。输出的单词之间使用一个“空格”隔开，最后一个单词后不加空格。  
要求实现函数：void my\_word(charinput\[\], char output\[\])  
【输入】 char input\[\], 输入的字符串  
【输出】 char output\[\]，输出的字符串  
【返回】 无

void my\_word(char input\[\], char output\[\])  
\{  
char \*p;  
char \*temp;  
char \*word\[10\];  
int len\_input = strlen(input);  
int i, j;  
char except\[\] = ",";  
char \*blank = " ";  
i = 0;  
for ( i = 0; i < len\_input; i++)  
\{  
if (input\[i\]<'A' || (input\[i\]>'Z'&&input\[i\]<'a') || input\[i\]>'z')  
input\[i\] = ',';  
\}  
j = 0;  
p = strtok(input, except);  
while (NULL != p)  
\{  
word\[j++\] = p;  
p = strtok(NULL, except);  
\}  
for ( i = 0; i < 5; i++)  
\{  
printf("%s", word\[i\]);  
\}  
for ( i = 0; i < 5; i++)  
\{  
for ( j = 1; j < 5; j++)  
\{  
if (strlen(word\[j - 1\]) < strlen(word\[j\]))  
\{  
temp = word\[j\];  
word\[j\] = word\[j - 1\];  
word\[j - 1\] = temp;  
\}  
\}  
\}  
for ( i = 0; i < 5; i++)  
\{  
for ( j = i+1; j < 5; j++)  
\{  
if (strcmp(word\[i\], word\[j\]) == 0)  
word\[j\] = "\\0";  
\}  
\}  
for ( j = 0; j < 5; j++)  
\{  
if (0 == j)  
strncpy(output, word\[j\], strlen(word\[j\]) + 1);  
else  
\{  
strcat(output, blank);  
strcat(output, word\[j\]);  
\}  
\}  
return;  
\}  
void main()  
\{  
char input\[\] = "some local buses,some 1234123drivers";  
printf("筛选之前的字符串：%s\\n", input);  
char output\[30\];  
my\_word(input, output);  
printf("筛选之后的字符串：%s\\n", output);  
cout << endl;  
system("pause");  
\}

１６. 数组中数字都两两相同，只有一个不同，找出该数字：

void main()  
\{  
int str\[\] = \{ 12, 23, 23, 12, 45, 45, 67, 67, 5 \};  
int len = 9;  
int outdata = str\[0\];  
for (int i = 1; i < 9; i++)  
\{  
outdata ^= str\[i\];  
\}  
cout << outdata << endl;  
system("pause");  
\}

17.题目二：数组中数字两两相同，有两个不同，找出这两个：

int findXorSum(int\* a, int len)  
\{  
int i = 0;  
int temp = 0;  
for (; i < len; i++)  
\{  
temp = temp ^ a\[i\];  
\}  
return temp;  
\}  
int findFirstBit1(int n)  
\{  
int count = 1;  
while (!(n & 1))  
\{  
n = n >> 1;  
count++;  
\}  
return count;  
\}  
int isBit1(int a, int count)  
\{  
a = a >> count - 1;  
return (a & 1);  
\}  
void findTwoUnique(int\* a, int len)  
\{  
int i = 0;  
int m = 0, n = 0;  
int temp = findXorSum(a, len);  
int count = findFirstBit1(temp);  
for (; i < len; i++)  
\{  
if (isBit1(a\[i\], count))  
\{  
m = m ^ a\[i\];  
\}  
else  
\{  
n = n ^ a\[i\];  
\}  
\}  
printf("%d, %d", m, n);  
\}  
void main()  
\{  
int a\[\] = \{ 1, 2, 3, 4, 3, 2, 1, 5 \};  
int len = 8;  
findTwoUnique(a, len);  
system("pause");  
\}

# 18.链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现 #

# 思想：采用遍历链表，分成length/k组，对每组进行逆转，逆转的同时要将逆转后的尾和头连接起来 #

# typedef struct Node   \{   int value;   Node \*next;   \}LinkList;      void Converse(LinkList\* pPre, LinkList\*pCur)   \{   LinkList\*p = NULL;   LinkList \*pNext = NULL;   p = pPre->next;   LinkList\*p1 = NULL;   if (pCur != NULL)   pNext = pCur->next;      while (p!=pNext)   \{   p1 = p->next;   p->next = pPre;   pPre = p;   p = p1;   \}   \}   void main()   \{   int count = 0, k, i = 0, j = 0, flag = 1, length = 0, groups = 0;   scanf("%d", &k);   LinkList\* pPre = (LinkList\*)malloc(sizeof(LinkList));   LinkList\* pCur = (LinkList\*)malloc(sizeof(LinkList));   LinkList\* pNext = (LinkList\*)malloc(sizeof(LinkList));   LinkList\* head = NULL;   LinkList\* pTempTail = NULL; //指向逆转之后的尾部   LinkList\* pTempHead = NULL;      pCur->value = 1;   pPre = pCur; //创建初始链表   for (i = 2; i <= 6; i++) \{   LinkList\* node = (LinkList\*)malloc(sizeof(LinkList));   node->value = i;   pCur->next = node;   pCur = node;   \}   pCur->next = NULL;//最后一定要置NULL，c++中用new则无须置NULL   pCur = pPre;   while (pCur != NULL)   \{   length++;   pCur = pCur->next;   \}   i = 0;   groups = length / k; //分成K段   pCur = pPre;   while (i <= groups)   \{   count = 0;   while (count<k - 1 && i<groups)   \{   pCur = pCur->next;   count++;   \}   if (i<groups)   \{   pNext = pCur->next;   pTempHead = pCur; /\*没做翻转之前的头部,变成了翻转之后的尾部\*/   if (flag == 0)   \{   pTempTail->next = pTempHead;   \}   pTempTail = pPre;   Converse(pPre, pCur);   //pTempTail = pPre;   if (flag == 1)   \{   head = pCur;   flag = 0;   \}   pCur = pNext;   \}   else   \{   pTempTail->next = pNext;   \}   pPre = pCur;   i++;   \}   pCur = head;   while (j<length) \{   j++;   printf("%d", pCur->value);   pCur = pCur->next;   \}   printf("\\n");   system("pause");   \}    #

19.链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g

typedef struct node  
\{  
char val;  
struct node\*pNext;  
\}Node;  
  
Node\* CreateList(int n);  
void PrintList(Node\* pHead);  
Node \* TransNeighbor(Node \*pHead);  
  
int main()  
\{  
int n;  
scanf("%d", &n);  
Node \*pHead = CreateList(n);  
printf("before transform\\n");  
PrintList(pHead);  
TransNeighbor(pHead);  
printf("\\nafter transform\\n");  
PrintList(pHead);  
system("pause");  
return 0;  
\}  
Node \*CreateList(int n)  
\{  
Node \*pHead = (Node\*)malloc(sizeof(Node));  
Node \*pTail = pHead;  
pTail->pNext = NULL;  
int i;  
for ( i = 0; i < n; i++)  
\{  
Node \*pNew = (Node \*)malloc(sizeof(Node));  
pNew->val = 'a' + i;  
pTail->pNext = pNew;  
pNew->pNext = NULL;  
pTail = pNew;  
\}  
return pHead;  
\}  
  
void PrintList(Node\*pHead)  
\{  
Node \*p = pHead->pNext;  
int isFirst = 0;  
while (p != NULL)  
\{  
if (isFirst == 0)  
\{  
printf("%c", p->val);  
isFirst = 1;  
\}  
else  
\{  
printf("->%c", p->val);  
\}  
p = p->pNext;  
\}  
return;  
\}  
Node \*TransNeighbor(Node \*pHead)  
\{  
Node \*p = pHead->pNext;  
while (p != NULL&&p->pNext != NULL)  
\{  
char value = p->val;  
p->val = p->pNext->val;  
p->pNext->val = value;  
p = p->pNext->pNext;  
\}  
return pHead;  
\}

20. 输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘\[’,'\]'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.

int main()  
\{  
char \*str;  
str = (char\*)malloc(sizeof(char));  
char strdata\[20\];  
printf("请输入字符串：");  
scanf("%s", str);  
int i = 0;  
int k = 0;  
while (str\[i\] != '\\0')  
\{  
if (str\[i\] == '(')  
\{  
strdata\[k\] = str\[i\];  
k++;  
\}  
else if (str\[i\] == '\[')  
\{  
strdata\[k\] = str\[i\];  
k++;  
\}  
else if (str\[i\] == ')')  
\{  
strdata\[k\] = str\[i\];  
k++;  
\}  
else if (str\[i\] == '\]')  
\{  
strdata\[k\] = str\[i\];  
k++;  
\}  
else  
;  
i++;  
\}  
strdata\[k\] = '\\0';  
int len = strlen(strdata);  
int flag = 0;  
int count1 = 0;  
int count2 = 0;  
int count3 = 0;  
int count4 = 0;  
for (int j = 0; j < len; j++)  
\{  
if (strdata\[j\] == '(')  
count1++;  
if (strdata\[j\] == ')')  
count2++;  
if (strdata\[j\] == '\[')  
count3++;  
if (strdata\[j\] == '\]')  
count4++;  
\}  
if (count1 != count2 || count3 != count4)  
flag = 0;  
else  
flag = 1;  
cout << flag;  
system("pause");  
return 0;  
\}

此题还在考虑中，感觉匹配括号比较难。。。