第二章 数据结构实现基础 习题解答
Question
请编写程序模拟简单运算器的工作。假设计算器只能计算加减乘除运算，运算数和运算结果都是整数，4种运算符的优先级相同，按从左到右的顺序计算。
Analysis
关注下面几个点：
- 当遇上输入字符
=时，认为运算结束，开始输出结果 - 优先级相同，并且从左往右算，那么相当于只需要把当前的左右两数进行运算即可
My Code
#include<stdio.h>
int main()
{
int a,b,c,flag=0; #flag作为一个标志参数，当flag不为零的时候判定输入违法
char ch;
scanf("%d",&a); #获取当前左边的运算数
while((ch=getchar())!='=') #获取运算符，当运算符不为=号时继续运算，否则输出
{
scanf("%d",&b); #获取当前右运算数
if((ch=='/')&&(b==0)) #判断合法性
{
flag=1;break;
}
switch(ch) #获取当前左边运算数
{
case '+':a=a+b;break;
case '-':a=a-b;break;
case '*':a=a*b;break;
case '/':a=a/b;break;
default :
flag=1;break;
}
if(flag) break;
}
if(flag)
{
printf("ERROR");
}
else
{
printf("%d",a);
}
return 0;
}
本题代码出自：CSDN博主「Du798566」的原创文章
原文链接：https://blog.csdn.net/Du798566/article/details/104751177
Question
请编写程序将一个大小为的整数数组循环左移
位。如：1，2，3，4，5，6，7，8循环左移三位后的结果为：4，5，6，7，8，1，2，3。
Analysis
简单的数组操作，只需要利用一个双重循环，外循环为层，内循环为
层，外循环是每一次移位，内循环是移位操作需要做的循环。移位操作只需要取一个中间临时变量
tmp记录数组第一个元素，接着将每个数往前移位即可。
My Code
#include<stdio.h>
int main()
{
int n,m,i,j,tmp;
scanf("%d",&n);
scanf("%d",&m);
int a[n];
for(i=0; i<n; i++)
scanf("%d",&a[i]);
for(i=m; i>0; i--)
{
tmp = a[0];
for(j=0; j<n-1; j++)
{
a[j] = a[j+1];
}
a[n-1] = tmp;
}
for(i=0; i<n-1; i++)
printf("%d,",a[i]);
printf("%d",a[n-1]);
return 0;
}
Question
请编写程序，输入整数和
，输出
的结果。
Analysis
简单的循环即可
My Code
#include<stdio.h>
int main()
{
int n,a,i,sum=0,ca=1;
scanf("%d",&n);
scanf("%d",&a);
for(i=1; i<n+1; i++)
{
ca = ca * a;
sum = sum + ca;
}
printf("%d",sum);
return 0;
}
Question
请编写函数在递增的整数序列链表中插入一个新整数，并保持该序列的有序性。
Analysis
本质上很简单，只需要找到链表中这个新整数该处的位置即可，由于这是一个递增的链表，我们可以从第一个结点开始依次比较各个结点存储的整数与新整数之间的大小关系，直到找到存储的整数比新整数大的结点，将新整数插在这个结点之前即可。为了更好的验证程序的正确性，此处还给出依照给出数据创造一个链表的函数List read()，为了实现函数read()还需要给出另外一个函数void Attach(int data,List *rear)。当然，如果对于这部分不理解，可以暂时不管，第三章会详细介绍的。
这个题其实最难的点在于怎么在当前结点前面插入一个新结点，建议阅读文章：https://blog.csdn.net/bitboss/article/details/51610580
My Code
#include<stdio.h>
typedef struct Node *List;
struct Node{
int Data;
List Next;
};
List read();
void Attach(int data,List *rear);
void Attach(int data,List *rear)
{
List p;
p = (List)malloc(sizeof(struct Node));
p->Data = data;
p->Next = NULL;
(*rear)->Next = p;
*rear = p;
}
List read()
{
int n,data,j;
List L,rear;
L = (List)malloc(sizeof(struct Node));
rear = L;
scanf("%d",&n);
while(n--){
scanf("%d",&data);
Attach(data, &rear);
}
return L;
}
int main()
{
List L,K,tmp,tmpp;
int num;
scanf("%d",&num);
L = read()->Next;
K = L;
tmp = malloc(sizeof(struct Node));
while(K){
if(K->Data >= num)
{
tmpp = K->Next;
K->Next = tmp;
tmp->Next = tmpp;
break;
}
if(K->Next == NULL)
{
tmpp = K->Next;
K->Next = tmp;
tmp->Next = tmpp;
break;
}
K = K->Next;
}
tmp->Data = K->Data;
K->Data = num;
while(L){
printf("%d,",L->Data);
L = L->Next;
}
return 0;
}
Question
请编写函数将两个链表表示的递增整数序列合并为一个递增的整数序列。请直接使用原序列中的结点。
Analysis
这个题目就是链表中最基础的题目了，实际上这个问题的题目描述是有问题的，应该描述为合并为一个不减的整数数列，为了更好理解这个题，建议观看第三章关于多项式加法实现的相关代码。
My Code
List Merge( List L1, List L2 )
{
List font,rear,p,k;
font = malloc(sizeof(struct Node));
rear = font;
p = L1->Next;
k = L2->Next;
while(p && k)
{
if(p->Data <= k->Data)
{
rear->Next = p;
rear = p;
p = p->Next;
}
else if(p->Data > k->Data)
{
rear->Next = k;
rear = k;
k = k->Next;
}
}
if(p)
rear->Next = p;
else if(k)
rear->Next = k;
L1->Next = NULL;
L2->Next = NULL;
return font;
}
Question
请编写一个递归函数计算下列式子：
Analysis
递归计算多项式的值是理解递归函数很好也很简单的例子，没什么好分析的，直接撸就完事了。
My Code
#include<stdio.h>
#include<math.h>
typedef float ElementType;
ElementType getSum(int n, ElementType x);
ElementType getSum(int n, ElementType x)
{
if(n == 1)
return x;
else if(n > 1)
{
return pow(-1,n-1)*pow(x,n) + getSum(n-1,x);
}
}
int main()
{
int n;
float sum,x;
scanf("%d %f",&n,&x);
sum = getSum(n,x);
printf("%f",sum);
return 0;
}
Question
设有一个球从高度为米的地方落下，碰到地面后又弹到高度为原来0.9倍的位置，然后又落下，再弹起，再落下
请编写递归和非递归函数，求初始高度为
的球落下后到基本停下来（高度小于
）时在空中所经过的路程总和。
Analysis
实际上这就是一个数列求和的问题，递归的方法而言应该很简单，实际上不递归用循环直接求解也应该很简单，值得注意的是合理的满足精度要求。
My Code
#include<stdio.h>
#include<math.h>
float recursionGetDistance(float h);
float getDistance(float h);
float recursionGetDistance(float h)
{
float dist;
if(h < 1e-6 && h>0)
return 0;
else if(h >= 1e-6)
{
dist = h + h * 0.9;
h = h * 0.9;
return dist + recursionGetDistance(h);
}
}
float getDistance(float h)
{
float sum = 0,dist;
while(h >= 1e-6){
dist = h + h * 0.9;
h = h * 0.9;
sum = sum + dist;
}
return sum;
}
int main()
{
float h;
scanf("%f",&h);
printf("%f\n",recursionGetDistance(h));
printf("%f\n",getDistance(h));
return 0;
}
Question
请编写递归函数，输出1,2,3,,
的全排列（
小于10），并观察
逐步增大时程序的运行时间。
Analysis
有序列：，不难知道，所谓的全排列就是每个位置上的数，都与其后面每个数交换，基于此，我们可以得出全排列的递归算法。此题稍有难度，给出的代码没有完全解决这个问题，但是解决了难度大的部分，剩下的只是输入与计时。
My Code
#include<iostream>
using namespace std;
//交换
void swap(int &a , int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
//全排列递归算法
void Perm(int list[] , int k ,int m)
{
//list 数组存放排列的数，K表示层 代表第几个数，m+1表示数组的长度
if(k==m)
{
//K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
for(int i=0 ;i<=m ;i++)
cout<<list[i];
cout<<endl;
}
else{
for(int i=k;i<=m;i++)
{
swap(list[i],list[k]);
Perm(list,k+1,m);
swap(list[i] , list[k]);
}
}
}
int main(void)
{
int a[]={1,2,3};
int m=2;
Perm(a,0,2);
}
代码来自：版权声明：本文为CSDN博主「MsStrbig」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/MsStrbig/article/details/79823555
Question
请思考一下，是否可以设计一个递归过程，实现对n个整数的排序。考虑两种不同的递归过程：
- 将
个整数的排序问题转化为对
个整数排序问题的递归；
- 将
个整数排序问题的递归。
Analysis
此处只提供第一种递归过程的代码，这是简单的。
My Code
#include<stdio.h>
void sortInt(int List[], int i, int n);
void sortInt(int List[], int i, int n)
{
int tmp,count,constant,j;
if(i < n-1)
{
constant = 100000000;
for(j=i; j<n;j++)
{
if(List[j] <= constant)
{
constant = List[j];
count = j;
}
}
tmp = List[i];
List[i] = List[count];
List[count] = tmp;
sortInt(List,i+1,n);
}
}
int main()
{
int i,n;
scanf("%d",&n);
int List[n];
for(i=0;i<n;i++)
scanf("%d",&List[i]);
sortInt(List,0,n);
for(i=0;i<n-1;i++)
printf("%d,",List[i]);
printf("%d",List[n-1]);
return 0;
}
