Date:2018.03.21 qzd
book:《数据结构题集》c语言版
一、基础知识
数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
- 抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
抽象数据类型三元组的定义。
三种不同的出错处理方式：
exit 常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。
以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。
用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。
- 三种方法实现输入输出：
- 用scanf 和printf 直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
- 通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
- 通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。
二、算法设计
- 自小到大依次输出顺序读入的三个整数X,Y和Z的值。
//Date:2018.03.19 qzd
//max3.c
//input:x,y,z output:max(x,y,z)
#include <stdio.h>
int max3(int x,int y,int z){
if(x>y)
if(x>z) return x;
else return z;
else
if(y>z) return y;
else return z;
}
void main(){
int x , y ,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",max3(x,y,z));
}
- 已知k 阶斐波那契序列的定义为
f0=0 , f1=0,……,fk-2=0,fk-1=1;
fn = fn-1 +fn-2+……+fn-k,n=k,k+1,……
试编写求k 阶斐波那契序列的第m 项值的函数算法，k 和m 均以值调用的形式在函数参数表中出现。
//Date:2018.03.19 qzd
//fibonacci.cpp
//input:k,n output:fn
#include<stdio.h>
int fibonacci(int k,int n){
if(k<1) return 0;
int x;
int *p = new int[k+1];
if(!p) return 0;
int i,j;
for(i=0;i<k+1;i++){
if(i<k-1) p[i]=0;
else p[i]=1;
}
for(i=k+1;i<n+1;i++){
x = p[0];
for(j=0;j<k;j++) p[j]=p[j+1];
p[k] = 2*p[k-1] - x;
}
printf("%d\n",p[k]);
}
int main(){
int k,n;
scanf("%d%d",&k,&n);
fibonacci(k, n);
}
- 1.18
//Date:20180320 qzd
//school
#include <stdio.h>
typedef enum schoolname{A,B,C,D,E} SchoolName;
typedef enum sextype{Female,Male} SexType;
typedef struct component{
char event[3]; //xiangmu
SexType sex;
SchoolName school;
int score;
} Component;
typedef struct sum{
int MaleSum; //male score
int FemaleSum; //female score
int TotalSum; //total score
} Sum;
int main(){
int i,n;
printf("please input the number of students : ");
scanf("%d",&n);
Component a[n];
SchoolName sn;
for(i=0;i<n;i++){
printf("\n input school");
scanf("%s",&a[i].school);
printf("\n input sex");
scanf("%s",&a[i].sex);
}
struct sum temp;
temp.MaleSum=0;
temp.FemaleSum=0;
temp.TotalSum=0;
for(i=0;i<n;i++){
if(a[i].school==sn){
if(a[i].sex==Male) temp.MaleSum+=a[i].score;
if(a[i].sex==Female) temp.FemaleSum+=a[i].score;
}
}
temp.TotalSum=temp.MaleSum+temp.FemaleSum;
printf("%d",temp);
}
- 1.19
//Date:20180320 qzd
//count.cpp
//input:k output:a[i]
#include<iostream>
using namespace std;
#include<stdlib.h>
#define MAXINT 65535
#define ArrSize 100
int main(){
int i,k;
int a[ArrSize];
cout<<"Enter k:";
cin>>k;
if(k>ArrSize-1) exit(0);
for(i=0;i<=k;i++){
if(i==0) a[i]=1;
else{
if(2*i*a[i-1]>MAXINT) exit(0);
else a[i] = 2*i*a[i-1];
}
}
for(i=0;i<=k;i++){
if(a[i]>MAXINT) exit(0);
else cout<<a[i]<<" ";
}
return 0;
}
- 1.20
//Date:20180320 qzd
//ploynomial.cpp
//input:a[i],x0,n output:Pn(x0)
#include<iostream>
using namespace std;
#include<stdlib.h>
#define N 10
double polynomial(int a[],int i,double x,int n);
int main(){
double x;
int n,i;
int a[N];
cout<<"input value is x:";
cin>>x;
cout<<"poly n:";
cin>>n;
if(n>N-1) exit(0);
cout<<"a[0]--a[n]:\n";
for(i=0;i<=n;i++) cin>>a[i];
cout<<"The polynomial value is "<<polynomial(a,n,x,n)<<endl;
return 0;
}
double polynomial(int a[],int i,double x,int n){
if(i>0) return a[n-i]+polynomial(a,i-1,x,n)*x;
else return a[n];
}
