厂工数据结构Anyview（C语言版）第一章答案

小灰灰 2023-01-08 08:24 157阅读 0赞

### 第一章 ###

*  一、将三个整数按升序重新排列
 *  二、求一元多项式的值
 *  三、求k阶裴波那契序列的第m项的值
 *  四、计算i!×2^i的值
 *  五、由一维数组构建一个序列
 *  六、构建一个值为x的结点
 *  七、构建长度为2且两个结点的值依次为x和y的链表
 *  八、构建长度为2的升序链表

# 一、将三个整数按升序重新排列 #

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

要求实现下列函数：  
void Descend(int &a, int &b, int &c);  
/\* 通过交换，令 a >= b >= c \*/

#include "allinclude.h"  //DO NOT edit this line
    void Descend(int &a, int &b, int &c) {
         // 通过交换，令 a >= b >= c
        // Add your code here
        int t,max;
        
        //先找出abc中的最大值
        max = (((a>=b)?a:b)>=c)?((a>=b)?a:b):c;
        
        if(max==a){
         
          if(b<c){
        
            t = b;
            b = c;
            c = t;
          }
    }
    
        if(max==b){
         
          if(a>=c){
        
            t = a;
            a = b;
            b = t;
          }else{
        
            t = b;
            b = c;
            c = a;
            a = t;
          }
        }
       
        if(max==c){
           
          if(b>=a){
        
            
            t = a;
            a = c;
            c = t;
          }else{
        
            t = c;
            c = b;
            b = a;
            a = t;
          }
        }
    }

# 二、求一元多项式的值 #

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + … + anx^n的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。  
要求实现下列函数：  
float Polynomial(int n, int a\[\], float x0);  
/\* 求一元多项式的值P(x0)。 */  
/* 数组a的元素a\[i\]为i次项的系数，i=0,1,…,n \*/

#include "allinclude.h"  //DO NOT edit this line
    float Polynomial(int n, int a[], float x0){
         
        // Add your code here
        
        float p = 0;
        float t = x0;
        
        if(n)
         for(int i = 1;i<=n;i++){
        
           p += a[i]*t;
           t = t*x0;
         }
        
        return a[0]+p;
    }

# 三、求k阶裴波那契序列的第m项的值 #

【题目】已知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均以值调用的形式在函数参数表中出现。  
要求实现下列函数：  
Status Fibonacci(int k, int m, int &f);  
/\* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/  
/* 否则（比如，参数k和m不合理）返回ERROR \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Fibonacci(int k, int m, int &f) {
         
        // Add your code here
        
        int a[100],sum;
        
        //异常处理
        if(k < 2||m < 0) return ERROR;
        
        if(m < k-1) f = 0;
    else{
        
          if(m == k-1) f = 1;
          else{
          
            //前k-1项都为0
            for(int i = 0;i < k-1;i++) a[i] = 0;
            
            //第k-1项为1
            a[k-1] = 1;
            
            //前k项和为下一项
            for(int j = k;j <= m;j++){
        
              
              sum = 0;
              
              for(int i = j-k;i < j;i++) sum += a[i];
              
              a[j] = sum;
            }
            
            f = a[m];
          }
        }
        
        return OK;
    }

# 四、计算i!×2^i的值 #

【题目】试编写算法，计算i!×2^i的值并存入数组a\[0…n-1\]的第i-1个分量中 (i=1,2,…,n)。假设计算机中允许的整数最大值为MAXINT，则当对某个k(1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。  
要求实现下列函数：  
Status Series(int a\[\], int n);  
/\* 求i!\*2^i序列的值并依次存入长度为n的数组a；若所有 */  
/* 值均不超过MAXINT，则返回OK，否则返回EOVERFLOW \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Series(int a[], int n) {
         
        // Add your code here
        
        if(n <= 0) return ERROR;
        
        int l,m;
        l = 1;
        m = 2;
        
        for(int i = 1;i <= n;i++){
        
          
          l *= i;
          
          a[i-1] = l*m;
          
          m *= 2;
            
          if(l > MAXINT||m > MAXINT||l*m > MAXINT) return EOVERFLOW;
        }
        
        return OK;
    }

# 五、由一维数组构建一个序列 #

【题目】试写一算法，由长度为n的一维数组a构建一个序列S。

要求实现下列函数：  
Status CreateSequence(Sequence &S, int n, ElemType *a);  
/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */  
/* 若构建失败，则返回ERROR \*/  
序列的定义为：  
typedef struct \{  
ElemType \*elem;  
int length;  
\} Sequence;

#include "allinclude.h"  //DO NOT edit this line
    Status CreateSequence(Sequence &S, int n, ElemType *a) {
         
      
      S.elem = a;
      
      if(NULL == S.elem||n <= 0) return ERROR;
      
      S.length = n;
      
      return OK;
    }

# 六、构建一个值为x的结点 #

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

要求实现下列函数：  
LinkList MakeNode(ElemType x);  
/\* 构建一个值为x的结点，并返回其指针。 */  
/* 若构建失败，则返回NULL。 \*/

#include "allinclude.h"  //DO NOT edit this line
    LinkList MakeNode(ElemType x) {
         
        // Add your code here
        
        LinkList p;
        
        p = (LinkList)malloc(sizeof(LNode));//sizeof里面最好不要写LinkList
        
        If(! p) return NULL;
        
        p->data = x;
        
        return p;
    }

# 七、构建长度为2且两个结点的值依次为x和y的链表 #

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

要求实现下列函数：  
LinkList CreateLinkList(ElemType x, ElemType y);  
/\* 构建其两个结点的值依次为x和y的链表。*/  
/* 若构建失败，则返回NULL。 \*/

#include "allinclude.h"  //DO NOT edit this line
    LinkList CreateLinkList(ElemType x, ElemType y) {
         
        // Add your code here
        
        LNode *p1;
        LNode *p2;
        
        p1 = (LNode *)malloc(sizeof(LNode));
        p2 = (LNode *)malloc(sizeof(LNode));
        
        if(!p1||!p2) return NULL;
        
        p1->data = x;
        p1->next = p2;
        p2->data = y;
        
        p2->next = NULL;
        
        return p1;
    }

# 八、构建长度为2的升序链表 #

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

要求实现下列函数：  
LinkList CreateOrdLList(ElemType x, ElemType y);  
/\* 构建长度为2的升序链表。 */  
/* 若构建失败，则返回NULL。 \*/

#include "allinclude.h"  //DO NOT edit this line
    LinkList CreateOrdLList(ElemType x, ElemType y) {
         
        // Add your code here
        
        LNode *p1,*p2;
        
        p1 = (LNode *)malloc(sizeof(LNode));
        p2 = (LNode *)malloc(sizeof(LNode));
        
        If(!p1||!p2) return NULL;
        
        ElemType t;
        
        if(x > y){
        
          t = x;
          x = y;
          y = t;
        }
        
        p1->data = x;
        p1->next = p2;
        p2->data = y;
        
        p2->next = NULL;
        
        return p1; 
    }