版本6和17间的区别 (跳过第11版)

练习参考答案

1. 第一章

6. 编写算法，求一元多项式的值latex($$P_n(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n$$)

   1 /*数组a指定多项式的各个系数，n指定多项式的最高次数，x指定自变量的值，返回多项式的值*/
   2 double p(double x, double a[], int n) {
   3    double result = 0.0;
   4    int i = 0;
   5    for(i = n; i >= 0; i--) {  //n+2次
   6       result *= x;            //n+1次
   7       result += a[i];         //n+1次
   8    }
   9 }

总计 = 3n+4次

2. 第二章

4. 已知顺序表L递增有序，写一个算法将X插入到线性表适当位置上，使顺序表仍然递增有序。

   1 /*顺序表list递增有序，insert_order将x插入到list当中使list仍然递增有序*/
   2 void insert_order(seq_list *list, ElemType x){
   3    int i, pos;
   4    for(i = 0; i < list->size; i++)
   5       if(list->elem[i] >= x)
   6          break;
   7    pos = i;
   8    for(i = list->size-1; i >= pos; i--)
   9       list->elem[i+1] = list->elem[i];
  10    list->elem[pos] = x;
  11 }

5. 编写一个算法，从顺序表中删除自第i个元素开始的k个元素

   1 /*删除顺序表list中从pos开始的num个元素*/
   2 void delete_from_ith(seq_list *list, int pos, int num){
   3    int i;
   4    pos--; /*把元素的逻辑位置变成数组中的存放位置。逻辑位置从1开始，存放物理位置从0开始，两者差1*/
   5    for(i = pos+num; i < list->size; i++)
   6       list->elem[i-num] = list->elem[i];
   7 }

6. 已知单链表中的元素递增排列，编写一个算法，删除链表内所有大于min小于max的元素。

   1 /*list指向带头结点单链表的头结点，元素递增有序排列，算法删除其中大于min小于max的所有元素*/
   2 void delete_between_min_and_max(linklist list, int min, int max) {
   3    node *p, *q, *nextq;
   4    for(p = list; p->next->data <= min; p = p->next)
   5       ;
   6    q = p->next;
   7    while(q!=NULL && q->data < max) {
   8       nextq = q->next;
   9       free(q);
  10       q=nextq;
  11    }
  12    p->next = q;
  13 }

7. 线性表逆置

   1 /*将顺序表list中所有元素的顺序倒过来*/
   2 void reverse(seq_list *list) {
   3    int i;
   4    for(i = 0; i < list->size /2; i++) {
   5       ElemType temp = list->elem[i];
   6       list->elem[i] = list->elem[list->size - i -1];
   7       list->elem[list->size-i-1] = temp;
   8    }
   9 }

   1 /*将头结点为list的带头结点单链表中所有的元素的顺序倒过来*/
   2 void reverse(linklist list) {
   3    node *p = list->next;
   4    list->next = NULL;
   5    while(p != NULL) {
   6       node *q = p->next;
   7       p->next = list->next;
   8       list->next = p;
   9       p = q;
  10    }
  11 }

8. 有两个按照元素递增顺序排列的单链表A和B，编写算法将A和B合并成单链表C，并要求C中的元素是递减排列的。

   1 /*A和B为两个按照元素递增顺序排列的带头结点的单链表，将A和B合并成带头结点的单链表C，C中的元素是递减排列的，C中的节点空间为原来的A和B中的节点空间，返回单链表C*/
   2 linklist merge(linklist A, linklist B) {
   3    linklist C;
   4    node *pa = A->next;
   5    node *pb = B->next;
   6    C = A;
   7    C->next = NULL;
   8    free(B);
   9    while(pa && pb) {
  10       if(pa->data < pb->data) {
  11          node *temp = pa->next;
  12          pa->next = C->next;
  13          C->next = pa;
  14          pa = temp;
  15       } else {
  16          node *temp = pb->next;
  17          pb->next = C->next;
  18          C->next = pb;
  19          pb = temp;
  20       }
  21    }
  22    while(pa) {
  23       node *temp = pa->next;
  24       pa->next = C->next;
  25       C->next = pa;
  26       pa = temp;
  27    }
  28    while(pb) {
  29       node *temp = pa->next;
  30       pa->next = C->next;
  31       C->next = pa;
  32       pa = temp;
  33    }
  34    return C;
  35 }

9. 假设有一个无头节点的循环单链表的长度大于1，s为指向链表中间某个（非第一个）节点的指针。写一个算法删除s的前驱节点。

   1 void remove_pre(node *s) {
   2    node *p;
   3    for(p = s; p->next->next != s; p = p->next)
   4       ;
   5    free(p->next)
   6    p->next = s;
   7 }

3. 第三章

7. 用带头结点的单循环链表表示队列，并只设尾指针，写出初始化、入队、出队算法。

   1 struct node {
   2    struct node *next;
   3    ElemType data;
   4 };
   5 
   6 /*初始化*/
   7 void init(struct node **tail) {
   8    *tail = (struct node *)malloc(sizeof(struct node));
   9    (*tail)->next = *tail;
  10 }
  11 
  12 /*入队*/
  13 void push(struct node **tail, ElemType x) {
  14    struct node *p = (struct node *)malloc(sizeof(struct node));
  15    p->data = x;
  16    p->next = (*tail)->next; 
  17    (*tail)->next = p;
  18    *tail = p;
  19 }
  20 
  21 /*出队*/
  22 ElemType pop(struct node **tail) {
  23    struct node *p = (*tail)->next->next;
  24    ElemType data = p->data;
  25    (*tail)->next->next = p->next;
  26    if(p==tail) tail = tail->next;/*如果最后一个节点被删除，则要修改tail指针*/
  27    free(p);
  28    return data;
  29 }

数据结构——C语言描述（耿国华） (2008-02-23 15:34:19由localhost编辑)

-  ⇤ ← 于2006-03-21 14:36:49修订的的版本6 → 
  大小: 1027
  编辑: czk
  备注:
+   ← 于2006-04-28 21:52:03修订的的版本17 → ⇥
  大小: 4999
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 1:
-练习：
+= 练习参考答案 =
 行号 3:
-= 第一章 =
+== 第一章 ==
 行号 5:
-. 编写算法，求一元多项式的值[[latex($$Pn(x)=a_0+a_1x+a_2x^2+...+a_nx^n$$)]]
+. 编写算法，求一元多项式的值[[latex($$P_n(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n$$)]]
 行号 21:
-= 第二章 =
+== 第二章 ==
 行号 37:
+. 编写一个算法，从顺序表中删除自第i个元素开始的k个元素
{{{#!cplusplus
/*删除顺序表list中从pos开始的num个元素*/
void delete_from_ith(seq_list *list, int pos, int num){
   int i;
   pos--; /*把元素的逻辑位置变成数组中的存放位置。逻辑位置从1开始，存放物理位置从0开始，两者差1*/
   for(i = pos+num; i < list->size; i++)
      list->elem[i-num] = list->elem[i];
}
}}}

6. 已知单链表中的元素递增排列，编写一个算法，删除链表内所有大于min小于max的元素。
{{{#!cplusplus
/*list指向带头结点单链表的头结点，元素递增有序排列，算法删除其中大于min小于max的所有元素*/
void delete_between_min_and_max(linklist list, int min, int max) {
   node *p, *q, *nextq;
   for(p = list; p->next->data <= min; p = p->next)
      ;
   q = p->next;
   while(q!=NULL && q->data < max) {
      nextq = q->next;
      free(q);
      q=nextq;
   }
   p->next = q;
}
}}}

7. 线性表逆置
{{{#!cplusplus
/*将顺序表list中所有元素的顺序倒过来*/
void reverse(seq_list *list) {
   int i;
   for(i = 0; i < list->size /2; i++) {
      ElemType temp = list->elem[i];
      list->elem[i] = list->elem[list->size - i -1];
      list->elem[list->size-i-1] = temp;
   }
}
}}}

{{{#!cplusplus
/*将头结点为list的带头结点单链表中所有的元素的顺序倒过来*/
void reverse(linklist list) {
   node *p = list->next;
   list->next = NULL;
   while(p != NULL) {
      node *q = p->next;
      p->next = list->next;
      list->next = p;
      p = q;
   }
}
}}}


8. 有两个按照元素递增顺序排列的单链表A和B，编写算法将A和B合并成单链表C，并要求C中的元素是递减排列的。
{{{#!cplusplus
/*A和B为两个按照元素递增顺序排列的带头结点的单链表，将A和B合并成带头结点的单链表C，C中的元素是递减排列的，C中的节点空间为原来的A和B中的节点空间，返回单链表C*/
linklist merge(linklist A, linklist B) {
   linklist C;
   node *pa = A->next;
   node *pb = B->next;
   C = A;
   C->next = NULL;
   free(B);
   while(pa && pb) {
      if(pa->data < pb->data) {
         node *temp = pa->next;
         pa->next = C->next;
         C->next = pa;
         pa = temp;
      } else {
         node *temp = pb->next;
         pb->next = C->next;
         C->next = pb;
         pb = temp;
      }
   }
   while(pa) {
      node *temp = pa->next;
      pa->next = C->next;
      C->next = pa;
      pa = temp;
   }
   while(pb) {
      node *temp = pa->next;
      pa->next = C->next;
      C->next = pa;
      pa = temp;
   }
   return C;
}
}}}

9. 假设有一个无头节点的循环单链表的长度大于1，s为指向链表中间某个（非第一个）节点的指针。写一个算法删除s的前驱节点。
{{{#!cplusplus
void remove_pre(node *s) {
   node *p;
   for(p = s; p->next->next != s; p = p->next)
      ;
   free(p->next)
   p->next = s;
}
}}}

== 第三章 ==

7. 用带头结点的单循环链表表示队列，并只设尾指针，写出初始化、入队、出队算法。
{{{#!cplusplus
struct node {
   struct node *next;
   ElemType data;
};

/*初始化*/
void init(struct node **tail) {
   *tail = (struct node *)malloc(sizeof(struct node));
   (*tail)->next = *tail;
}

/*入队*/
void push(struct node **tail, ElemType x) {
   struct node *p = (struct node *)malloc(sizeof(struct node));
   p->data = x;
   p->next = (*tail)->next; 
   (*tail)->next = p;
   *tail = p;
}

/*出队*/
ElemType pop(struct node **tail) {
   struct node *p = (*tail)->next->next;
   ElemType data = p->data;
   (*tail)->next->next = p->next;
   if(p==tail) tail = tail->next;/*如果最后一个节点被删除，则要修改tail指针*/
   free(p);
   return data;
}
}}}

"数据结构——C语言描述（耿国华）"版本比较

练习参考答案

1. 第一章

2. 第二章

3. 第三章