Anyview数据结构-1

Posted on | Post modified: | In
Words count in article: 1,557 | Reading time ≈ 7

-广工Anyview题解
-数据结构部分-1

/**
【题目】试写一算法，如果三个整数a，b和c的值
不是依次非递增的，则通过交换，令其为非递增。
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Descend(int &a, int &b, int &c)
/* 通过交换，令 a >= b >= c */
{
    int temp;
    if(c>=b)
    {
        temp=b;
        b=c;
        c=temp;
    }
    if(b>=a)
    {
        temp=a;
        a=b;
        b=temp;
    }
    if(c>=b){
        temp=b;
        b=c;
        c=temp;
    }            
}

/**
【题目】试编写算法求一元多项式
P(x) = a0 + a1x + a2x^2 + … + anx^n
的值P(x0)，并确定算法中每一语句的执行次数和整个算法
的时间复杂度。
**/

1
2
3
4
5
6
7
8
9
10
float Polynomial(int n, int a[], float x)
/* 求一元多项式的值P(x)。                  */
/* 数组a的元素a[i]为i次项的系数，i=0,...,n */
{
    double px;
    int i;
    for(i=0;i<=n;i++)
        px+=a[i]*pow(x,i);
    return px;    
}

/**
【题目】已知k阶裴波那契序列的定义为
f(0)=0, f(1)=0, …, f(k-2)=0, f(k-1)=1;
f(n)=f(n-1)+f(n-2)+…+f(n-k), n=k,k+1,…
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status Fibonacci(int k, int m, int &f) 
/* 求k阶斐波那契序列的第m项的值f */
{    
    int t[60],sum,i,j;
    if(k<2||m<0) 
        return ERROR;
    if(m<k-1) 
        f=0;
    else if(m==k-1) 
        f=1;
    else{
      for(i=0;i<=k-2;i++){
        t[i]=0;
        t[k-1]=1;
        for(i=k;i<=m;i++){
            sum=0;
            for(j=i-k;j<i;j++)
                sum+=t[j];
            t[i]=sum;
        }
      }
    f=t[m];
    }                                                                                
    return OK;
}

/**
【题目】试编写算法，计算i!×2^i的值并存入数组
a[0..n-1]的第i-1个分量中 (i=1,2,…,n)。假设计
算机中允许的整数最大值为MAXINT，则当对某个k
(1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意
选择你认为较好的出错处理方法。
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Status Series(int a[], int n) 
/* 求i!*2^i序列的值并依次存入长度为n的数组a；     */
/* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */
{
   int i=0,sum=0;
   int sum1=1,sum2=1;
   int j;
   for(i=1;i<=n;i++){
        for(j=i;j>0;j--)
            sum1=sum1*j;
        for(j=i;j>0;j--)
            sum2=sum2*2;    
    sum=sum1*sum2;
        
    if(sum1>MAXINT||sum2>MAXINT||sum>MAXINT)
        return OVERFLOW;             
        
    a[i-1]=sum;
    
    sum1=1;//归位
    sum2=1;//归位
    }
   return  OK;            
}

/**
【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
void Scores(ResultType *result, ScoreType *score)
/* 求各校的男、女总分和团体总分, 并依次存入数组score */
/* 假设比赛结果已经储存在result[ ]数组中,            */
/* 并以特殊记录 {"", male, ' ', "", 0 }（域scorce=0）*/
/* 表示结束                                          */
{
typedef enum {female,male} Sex;
typedef struct{
  char *sport;     // 项目名称
  Sex  gender;     // 性别（女：female；男：male）
  char schoolname; // 校名为'A','B','C','D'或'E'
  char *result;    // 成绩
  int score;       // 得分（7,5,4,3,2或1）
} ResultType; 
typedef struct{
  int malescore;   // 男子总分
  int femalescore; // 女子总分
  int totalscore;  // 男女团体总分
} ScoreType;
int i=0;
 while(result[i].sport!=NULL)  
 {  
 switch(result[i].schoolname)     /*使用switch语句记录各院校的成绩*/
 {  
 case 'A':  
 score[0].totalscore+=result[i].score;
 if(result[i].gender==male)  
    score[0].malescore+=result[i].score;  
 else  
    score[0].femalescore+=result[i].score;  
 break;  
 case 'B':  
 score[1].totalscore+=result[i].score;
 if(result[i].gender==male)  
    score[1].malescore+=result[i].score;  
 else  
    score[1].femalescore+=result[i].score;  
 break;  
 
 case 'C':  
 score[2].totalscore+=result[i].score;  
 if(result[i].gender==male)  
    score[2].malescore+=result[i].score;  
 else  
    score[2].femalescore+=result[i].score;  
 break;  
 
 case 'D':  
 
 score[3].totalscore+=result[i].score;  
 
 if(result[i].gender==male)  
    score[3].malescore+=result[i].score;  
 else  
    score[3].femalescore+=result[i].score;  
 break;  
 
 case 'E': 
  
 score[4].totalscore+=result[i].score;  
 if(result[i].gender==male)  
    score[4].malescore+=result[i].score;  
 else  
    score[4].femalescore+=result[i].score;  
 break;  
 }
 i++;  
 }  
    int j;  
    for( j=0;j<5;j++)  {
        printf("the school %s: ", result[i].schoolname) ;   /*输出各院校的男女总分和团体总分*/
        printf("total: %f",&score[i].totalscore);  
        printf("male: %f",&score[i].malescore);  
        printf("female: %f",&score[i].femalescore);  
    }  
}

/**
【题目】试写一算法，对序列S的第i个元素赋以值e。
序列的类型定义为：
typedef struct {
ElemType elem;
int length;
} Sequence;
**/

1
2
3
4
5
6
7
8
9
Status Assign(Sequence &S, int i, ElemType e) 
/* 对序列S的第i个元素赋以值e，并返回OK。 */
/* 若S或i不合法，则赋值失败，返回ERROR   */
{    
    if(i<1||i>=S.length||S.elem==NULL)
        return ERROR;
    S.elem[i]=e;
    return OK;
}

/**
【题目】试写一算法，由长度为n的一维数组a构建一个序列S。
序列的类型定义为：
typedef struct {
ElemType elem;
int length;
} Sequence;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
Status CreateSequence(Sequence &S, int n, ElemType *a) 
/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */
/* 若构建失败，则返回ERROR                       */
{
   int i;
   if(n<1)
        return ERROR;
   S.elem=(ElemType*)malloc(n*sizeof(ElemType));
   for(i=0;i<n;i++)
        S.elem[i]=a[i];
   S.length=n;     
   return true;
}

/**
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
试写一函数，构建一个值为x的结点。
*/

1
2
3
4
5
6
7
8
9
10
11
12
LinkList MakeNode(ElemType x)
/* 构建一个值为x的结点，并返回其指针。*/
/* 若构建失败，则返回NULL。           */
{
     LNode *p;
     p=(LNode*)malloc(sizeof(LNode));
     if(p==NULL) //构建失败
        return NULL;
     p->next=NULL;
     p->data=x;
     return p;
}

/**
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkList CreateLinkList(ElemType x, ElemType y) 
/* 构建其两个结点的值依次为x和y的链表。*/
/* 若构建失败，则返回NULL。            */
{
      LNode *p;
      LNode *q;
      p=(LNode*)malloc(sizeof(LNode));
      if(p==NULL)  //构建失败
        return NULL;        
      q=(LNode*)malloc(sizeof(LNode));
      if(q==NULL)  //构建失败
        return NULL;
      p->next=q;
      q->next=NULL;
      p->data=x;
      q->data=y;
      return p;  
}

/**
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
LinkList CreateOrdLList(ElemType x, ElemType y)
/* 构建长度为2的升序链表。  */
/* 若构建失败，则返回NULL。 */
{
    LNode *p;
    LNode *q;
    
    p=(LNode*)malloc(sizeof(LNode));
    if(p==NULL)
        return NULL;
        
    q=(LNode*)malloc(sizeof(LNode));
    if(q==NULL)
        return NULL;
                
    p->next=q;
    q->next=NULL;
    if(x<y){
        p->data=x;
        q->data=y;
    }
    else{
        p->data=y;
        q->data=x;
    }
    return p;                            
}

Thanks for your reward！