Anyview 数据结构 第一章

数据结构习题

【题目】试写一算法，如果三个整数a，b和c的值

不是依次非递增的，则通过交换，令其为非递增。

void Descend(int &a, int &b, int &c)
/* 通过交换，令 a >= b >= c */
{
    if (a<=b)
    {
        int t=a;
        a=b;
        b=t;
        if (b<=c)
        {
            int t1=b;
            b=c;
            c=t1;
            if (a<=b)
            {
                int t2=a;
                a=b;
                b=t2;
            }
        }
    }   
}

【题目】试编写算法求一元多项式

P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法
的时间复杂度。

float Polynomial(int n, int a[], float x)
/* 求一元多项式的值P(x)。                  */
/* 数组a的元素a[i]为i次项的系数，i=0,...,n */
{
     int i, j;
    float t;
    float sum = 0.0;
    for (i = 2; i<n+1; i++)
    {
            t = x;
            for (j = 1; j<i; j++)
                t *= x;
        sum += a[i] * t;
    }
        sum = sum + a[0];
        sum = sum + a[1] * x;
    return sum;
}

测试数据：

A$: P0(x) = -2-6x^1-4x^2+9x^3-7x^4
A$:   P0(0.947100) = -9.256912
A$:   P0(0.669900) = -6.518545
A$:   P0(1.329900) = -17.781443
E$: P0(x) = -2-6x^1-4x^2+9x^3-7x^4
E$:   P0(0.947100) = -3.434864
E$:   P0(0.669900) = -4.516258
E$:   P0(1.329900) = 1.781132
----- Error -----

优化后的代码

float Polynomial(int n, int a[], float x)
/* 求一元多项式的值P(x)。                  */
/* 数组a的元素a[i]为i次项的系数，i=0,...,n */
{
    float p = a[n];
    for (i = 1; i<=n; i++)
    {
        p = a[n-i] + 
    }
        sum = sum + a[0];
        sum = sum + a[1] * x;
    return sum;
}

【题目】已知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 */
{
        int i,j;
    if (k < 2 || m < 0)
        return  ERROR;
    if (m < k - 1)
    {
        f = 0;
        return OK;
    }
    if (m == k || m == k - 1)
    {
        f = 1;
        return OK;
    }
    else
    {
        int* l;
        l = (int*)malloc(k * sizeof(int));
        for (i = 0; i < k - 1; i++)
            l[i] = 0;
        l[k - 1] = 1;
        for (i = k; i < m; i++)
        {
            for (j = k - 1; j > 0; j--)
            {
                int tmp = l[j];
                l[j] = l[j - 1];
                l[j - 1] = tmp;
            }
            int v = 0;
            for (j = 0; j < k; j++)
                v += l[j];
            l[k - 1] = v;
            f = 0;
            for (j = 0; j < k; j++)
                f += l[j];
        }
    }
    return OK;
}

【题目】试编写算法，计算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，否则OVERFLOW */
{
    int i,j = 1,k=1;
    for (i = 1;i<=n;i++)
    {
        j *= i;
        k *=2;
        if (i<n && (j*k)>= MAXINT / ((i+1)*2))
            return OVERFLOW;
        a[i-1] =  j*k;
    }
    return OK;   
}

【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，

各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
******/
相关定义：

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;

void Scores(ResultType *result, ScoreType *score)
/* 求各校的男、女总分和团体总分, 并依次存入数组score */
/* 假设比赛结果已经储存在result[ ]数组中,            */
/* 并以特殊记录 {"", male, ' ', "", 0 }（域scorce=0）*/
/* 表示结束                                          */
{
    ResultType *r=result;
    ScoreType *s=score;
    while (NULL!=r->score)
    {
        int i=r->schoolname-'A';
        //
        if (r->gender==male)
            s[i].malescore+=r->score;
        else
            s[i].femalescore+=r->score;
        s[i].totalscore=s[i].malescore+s[i].femalescore;
        //printf("%c学校总分：%d\n",r->schoolname,s[i].totalscore);
        r++;
    }
}
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;
*******/

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

/******

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

序列的类型定义为：

typedef struct {
  ElemType  *elem;
  int  length;
} Sequence;

*******/

Status CreateSequence(Sequence &S, int n, ElemType *a) 
/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */
/* 若构建失败，则返回ERROR                       */
{
     if (n<=0)
        return ERROR;
    //Sequence *s=&S;
    S.length=n;
    S.elem=(ElemType*) malloc (n*sizeof(ElemType));
    int i;
    ElemType  *p;
    for (i=0,p=S.elem;p<S.elem+n;p++,i++)
    {
        *p=a[i];
    }
    return OK;
}

/******

【题目】链表的结点和指针类型定义如下

    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;

试写一函数，构建一个值为x的结点。
*******/

LinkList MakeNode(ElemType x)
/* 构建一个值为x的结点，并返回其指针。*/
/* 若构建失败，则返回NULL。           */
{
    LNode *p;
    p=(LNode*) malloc (sizeof(LNode));
    if (NULL==p)    return NULL;
    p->data=x;
    LinkList L;
    L->next=p;
    return p;
}

/******

【题目】链表的结点和指针类型定义如下

    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;

试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
******/

LinkList CreateLinkList(ElemType x, ElemType y) 
/* 构建其两个结点的值依次为x和y的链表。*/
/* 若构建失败，则返回NULL。            */
{
      LNode *p1, *p2;
    p1=(LNode*) malloc (sizeof(LNode*));
     p2=(LNode*) malloc (sizeof(LNode*));
    if (NULL==p1 || NULL==p2)    return NULL;
    p1->data=x;
    p2->data=y;
    LinkList L;
    L=p1;
    L->next=p2;
    return L;
}

/******

【题目】链表的结点和指针类型定义如下

    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;

试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
******/

LinkList CreateOrdLList(ElemType x, ElemType y)
/* 构建长度为2的升序链表。  */
/* 若构建失败，则返回NULL。 */
{
    LNode *p1,*p2;
   p1=(LNode*) malloc (sizeof(LNode*));
   p2=(LNode*) malloc (sizeof(LNode*));
    if (NULL==p1 || NULL==p2)    return NULL;
    x<y ? (p1->data=x,p2->data=y) : (p1->data=y,p2->data=x);
    LinkList L;
    L=p1;
    L->next=p2;
    return L;
}

https://blog.csdn.net/lzc394049722/article/details/51836980