◆2.11② 设顺序表L中的数据元素递增有序。
试写一算法，将x插入到L的适当位置上，并保
持该表的有序性。

要求实现下列函数：
void InsertOrderList(SqList &L, ElemType x)

顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;

void InsertOrderList(SqList &L, ElemType x)
// 在有序的顺序表 L 中保序插入数据元素 x
{
   int i=0,j;     
   if(x>=L.elem[L.length-1]) L.elem[L.length]=x;//如果x大于表最后一个元素

，则直接插到最后面
   else{   while(L.elem[i]<=x) i++;            //找到x的插入位置
           for(j=L.length-1;j>=i;j--)  L.elem[j+1]=L.elem[j] ;
           L.elem[i]=x;
       }
   L.length++;                 //表长加1

}

 

 

 

◆2.12③ 设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，
A'和B'分别为A和B中除去最大共同前缀后的子表（例如，
A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大
的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后
的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，
则A=B；若A'=空表，而B'≠ 空表，或者两者均不为空表，
且A'的首元小于B'的首元，则A<B；否则A>B。试写一个比
较A和B大小的算法。（注意：在算法中，不要破坏原表A
和B，也不一定先求得A'和B'才进行比较）。

要求实现下列函数：
char Compare(SqList A, SqList B);

顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;

 

char Compare(SqList A, SqList B)
{  int pa=A.length,pb=B.length,i=1,j=1;
   if(A.elem[0]>B.elem[0]) return '>';  //直接先由第一个元素判断谁大
   if(A.elem[0]<B.elem[0]) return '<';
   else                                 //如果第一个元素相同，则分以下情况
      { if(pa==pb)
         { while(i<=pa-1&&j<=pb-1)
           { if(A.elem[i]>B.elem[j]) return '>';  //相对应的元素逐个比较
             if(A.elem[i]<B.elem[j]) return '<';
             if(A.elem[i]==B.elem[j]) {i++;j++;}  //直到末尾都相等，则输出“=”
            }
          return '=';
         }
        
         if(pa<pb)
         {  while(i<=pa-1&&j<=pb-1)
           { if(A.elem[i]>B.elem[j]) return '>';
             if(A.elem[i]<B.elem[j]) return '<';
             if(A.elem[i]==B.elem[j]) {i++;j++;}    //元素依然相同，i达到A表表长的限制，跳出
            }                                       //则 B表大于A表
          return '<';
         }
        
         if(pa>pb)
         {   while(i<=pa-1&&j<=pb-1)
           { if(A.elem[i]>B.elem[j]) return '>';
             if(A.elem[i]<B.elem[j]) return '<';
             if(A.elem[i]==B.elem[j]) {i++;j++;}  //元素依然相同，i达到A表表长的限制，跳出
            }                                    //则 B表小于A表
          return '>';
         }
      }
            
}

 

 

2.13② 试写一算法在带头结点的单链表结构上实现线性表操作
Locate(L,x)。

实现下列函数：
LinkList Locate(LinkList L, ElemType x);
// If 'x' in the linked list whose head node is pointed
// by 'L',  then return pointer pointing node 'x',
// otherwise return 'NULL'

单链表类型定义如下：
typedef struct LNode {
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

LinkList Locate(LinkList &L, ElemType x)
//  If 'x' in the linked list whose head node is pointed
//  by 'L', then return pointer ha pointing node 'x',
//  otherwise return 'NULL'
{    LinkList p;
     p=L->next;
     while(p)
      {  if(p->data==x)  return p;   //找到x则输出
         else p=p->next;             //找不到则指针指向下一位
      }
      return NULL;                  //表里没有x
                
}

 

 

2.14② 试写一算法在带头结点的单链表结构上实现线性表
操作Length(L)。

实现下列函数：
int Length(LinkList L);
// Return the length of the linked list
// whose head node is pointed by 'L'

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

 

int Length(LinkList L)
// Return the length of the linked list
// whose head node is pointed by 'L'
{  int j=0;
   LinkList P;
   P=L->next;
   while(P!=NULL)
   {  P=P->next;
      j++;
   }
  
   return j;

}

 

 

2.16③  已知指针la和lb分别指向两个无头结点单链表中
的首元结点。 下列算法是从表la中删除自第i个元素起共
len个元素后，将它们插入到表lb中第i个元素之前。试问
此算法是否正确? 若有错，则请改正之。

实现下列函数：
Status DeleteAndInsertSub(LinkList &la, LinkList &lb,
                          int i, int j, int len);
// la和lb分别指向两个单链表中第一个结点，        */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len)
{  LinkList p,s,q,w;
   p=la;s=lb;w=NULL;
   int a=1,b=1,c=1;
   if(i<=0||j<=0||len<=0)  return INFEASIBLE;
   while(p&&a<i)
   { w=p;p=p->next;a++;}            //建立一个w的空链表来存放la的数据
   if(!p) return INFEASIBLE;  
   q=p;
   while(q&&b<len)
   { q=q->next; b++;}
   if(!q) return INFEASIBLE;
   if(!w) la=q->next;      //i=1的情况，删除len个元素后，将len+1号元素移到第一个结点存放，其他元素向前移
   else w->next=q->next;  //将删除了len个元素后的其他元素跟前面链接起来
   if(j==1)
   { q->next=lb;lb=p;}
   else
   {  while(s&&c<j-1)             //如果只有j-1位，插在表后，如果有j位，插在j-1位后就是插在j位前。
      {s=s->next;c++;}
      if(!s) return INFEASIBLE;
      q->next=s->next;
      s->next=p;     
   }
   return OK;
}

 

 

◆2.19③  已知线性表中的元素以值递增有序排列，并以
单链表作存储结构。试写一高效的算法，删除表中所有值
大于mink且小于maxk的元素(若表中存在这样的元素)同时
释放被删结点空间，并分析你的算法的时间复杂度（注意：
mink和maxk是给定的两个参变量，它们的值可以和表中的
元素相同，也可以不同）。

实现下列函数：
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

void DeleteSome(LinkList &L, ElemType mink, ElemType maxk)
{   LinkList p,q,w;
    p=L->next;
    w=NULL;
    while(p->data<=mink)  //先将第一个结点的数据跟mink比较，
    {w=p;
     p=p->next;           //如果小于mink，则指向下一个结点
     if(!p) break;         //如果大于mink，跳出
    }
   
    while(p->data<maxk)   //将跳出的p所指向的数据跟maxk比较
    {q=p;                  //如果大于，则跳出
     p=q->next;            //如果小于则将在有效范围内的数据删除并释放结点空间
     free(q);
     if(!p) break;
    }
     w->next=p;           //将删除后的前后两段重新链接
}

 

 

2.20②  同2.19题条件，试写一高效的算法，删除表中所
有值相同的多余元素 (使得操作后的线性表中所有元素的
值均不相同) 同时释放被删结点空间，并分析你的算法的
时间复杂度。

实现下列函数：
void Purge(LinkList &L);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

void Purge(LinkList &L)
{  LinkList p,q,w;
   p=L->next;
   q=p;                         //将q指向第一个结点
   p=p->next;                  //将p指向第二个结点
   while(p)                   //如果p不为空
   { if(q->data==p->data)      //q的元素与p的元素比较，如果相等
      { w=p->next;             //用w保存p下一位的节点的地址
        q->next=w;             //将该结点地址保存到q的指针域
        free(p);                //释放p
        p=w;                    //将p移到下一个结点
        if(!p)  break;          //如果p为空了，跳出，不为空，重新循环
 
      }
      else{q=p;                  //q和p的元素不相等
              p=p->next;            //则同时将q和p指向下一位，然后重新循环判断
              if(!p)  break;
             }
  }     
}

 

 

◆2.21③ 试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。

实现下列函数：
void Inverse(SqList &L);

顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;

 

void Inverse(SqList &L)
{ int p,n=0,pa=L.length-1;
  while( n<=pa/2)
  {p= L.elem[n];
   L.elem[n]= L.elem[pa-n];
   L.elem[pa-n]=p;
   n++;
  }
}

 

◆2.22③  试写一算法，对单链表实现就地逆置。

实现下列函数：
void Inverse(LinkList &L);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

void Inverse(LinkList &L)
{  LinkList p,q;  
   p=L->next;
   L->next=NULL;    //将头结点与第一个结点断开，设为空
   while(p)          //从第一个元素起，将后面的数依次插入到表的头部 ，成为新的第一个元素
   { q=p->next;
     p->next=L->next;
     L->next=p;
     p=q;
     }

}

 

 

2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn)，试写
一个按下列规则合并A、B为线性表C的算法，即使得
      C=(a1,b1,...,am,bm,bm+1,...,bn)  当m≤n时；
或者  C=(a1,b1,...,an,bn,an+1,...,am)  当m＞n时。
线性表A、B和C均以单链表作存储结构，且C表利用A表和
B表中的结点空间构成。注意：单链表的长度值m和n均未
显式存储。

实现下列函数：
void Merge(LinkList ha, LinkList hb, LinkList &hc)

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

 

void Merge(LinkList ha, LinkList hb, LinkList &hc)
{  LinkList p,q,s,t;
  p=ha->next;                  //p为a表第一个结点
  q=hb->next;                   //q为b表第一个结点
  hc=ha;                       //用用a表的头结点做c表表头结点
  s=hc->next;
  if(!p) hc=hb;         //如果p空，c表即为b表
  if(!q) hc=ha;         //如果q空，c表即为a表
  while(p&&q)
   {                        //将a，b表中的元素间隔插入c表
      s=p->next;
      p->next=q;
      if(s)              //如果s非空，即a表元素未完
      {t=q->next;
       q->next=s;
      }
      p=s;q=t;
   }
   free(hb);              //释放b表头结点
}

 

2.26④  假设以两个元素依值递增有序排列的线性表
A和B分别表示两个集合（即同一表中的元素值各不相
同），现要求另辟空间构成一个线性表C，其元素为A
和B中元素的交集，且表C中的元素也依值递增有序排
列。试对单链表编写求C的算法。

实现下列函数：
void Intersect(LinkList &hc, LinkList ha, LinkList hb);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

 

void Intersect(LinkList &hc, LinkList ha, LinkList hb)
{  LinkList p,q,w;
   p=ha->next;                            //p为A表第一个结点
   q=hb->next;                            //q为B表第一个结点
   hc=(LinkList)malloc(sizeof(LNode));
   hc->next=NULL;                        //建立一个带头结点的单链表C
   w=hc;
   while(p&&q)              //p，q非空
   {if(p->data==q->data)             //如果两表第一位的数据相同 ；或是循环中相同
     {w->next=(LinkList)malloc(sizeof(LNode));  //在c表中生成新的结点
      w=w->next;                               //移到下一个结点
      w->data=p->data;                         //将相同的数据存入c表
      p=p->next;                               //p指向下一个结点
      q=q->next;                              //q指向下一个结点
   }
    if(p->data>q->data)  q=q->next;   //如果不同，且A表第一位大于B表第一位，则B表
                                                                 //中q指向下一个结点 ，然后循环
    if(p->data<q->data)  p=p->next;   //同上
   }
}

 

2.31②  假设某个单向循环链表的长度大于1，且表
中既无头结点也无头指针。已知s为指向链表中某个
结点的指针，试编写算法在链表中删除指针s所指结
点的前驱结点。

实现下列函数：
ElemType DeleteNode(LinkList s);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

 

ElemType DeleteNode(LinkList s)
{   LinkList p,w;  ElemType e;
    w=s;                 //将s赋给w ，此时是s所指向的结点
    w=w->next;           //w指向下个结点
    if(w->next==s)       //如果w的指针域里存的是s的地址，也就是该表只有两个结点
    {s->next=s;          //则在原来s的指针域里存上自己的地址
     e=w->data;          //取出第二个节点的元素
     free(w);            //释放该节点
     }
    else                  //该表的结点数大于二
    {while(w->next!=s)    //如果w的指针域里存的不是s的地址
     { p=w;               //用p保留这一个结点
       w=w->next;         //w指向下一个结点，直到满足跳出
     }
     p->next=s;            //跳出后，也就是w的下一个结点是s所指向的,则把s的地址存入w的上一个结点
     e=w->data;            //取出w的元素
     free(w);                 //释放结点
     return e;              //返回删除点的值
    }

 

 

2.32②  已知有一个单向循环链表，其每个结点中
含三个域：prev、data和next，其中data为数据域，
next为指向后继结点的指针域，prev也为指针域，
但它的值为空(NULL)，试编写算法将此单向循环链
表改为双向循环链表，即使prev成为指向前驱结点
的指针域。

实现下列函数：
void PerfectBiLink(BiLinkList &CL);

双向循环链表类型定义如下：
typedef struct BiNode {
    ElemType       data;
    int            freq; // 2.38题用
    struct BiNode *prev,
                  *next;
} BiNode, *BiLinkList;

 

void PerfectBiLink(BiLinkList &CL)
{ BiLinkList p,w,s;
  p=s=CL->next;     //其中s是记住开始时的那个结点
  while(p->next!=s)     //只要p的下一位不是s，则可以继续循环
  {w=p;                   //用w记录p当前位
   p=p->next;             //p指向下一位
   p->prev=w;             //将p的 前指针域存上上个结点的地址
   }
   s->prev=p;             //直到p的下一位是s，则将s的前指针域存上此时p的地址
}

 

◆2.33③  已知由一个线性链表表示的线性表中含有
三类字符的数据元素（如：字母字符、数字字符和其
它字符），试编写算法将该线性链表分割为三个循环
链表，其中每个循环链表表示的线性表中均只含一类
字符。

实现下列函数：
void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

 

void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll)
{   
    LinkList p,q,w,s,f,a,b,c;
    p=ll->next;
    lc=(LinkList)malloc(sizeof(LNode));        //置空三个表
    ld=(LinkList)malloc(sizeof(LNode));
    lo=(LinkList)malloc(sizeof(LNode));
    q=lc;  a=q->next;           //标记第一个结点
    w=ld;  b=w->next;           //标记第一个结点
    f=lo;  c=f->next;           //标记第一个结点
    while(p)       //线性链表未走完
    { if(('A'<=p->data&&p->data<='Z')||('a'<=p->data&&p->data<='z'))  //如果是字母字符
       { s=(LinkList)malloc(sizeof(LNode));    //申请新的结点，下同
         q->next=s;
         s->data=p->data;
         s->next=a;                    //最后结点指向头结点，形成循环链表
         q=q->next;
         p=p->next;
       }
       else if('0'<=p->data&&p->data<='9')   //如果是数字字符
       {  s=(LinkList)malloc(sizeof(LNode));
          w->next=s;
          s->next=b;                     //最后结点指向头结点，形成循环链表
          s->data=p->data;
          w=w->next;
          p=p->next;
       }
       else                               //其他字符
       { s=(LinkList)malloc(sizeof(LNode));
         f->next=s;
         s->data=p->data;
         s->next=c;              //最后结点指向头结点，形成循环链表
         f=f->next;
         p=p->next;
       }
    }
        
}

 

 

 2.37④  设以带头结点的双向循环链表表示的线性

表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的

算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。

实现下列函数：

void ReverseEven(BiLinkList &L);

双向循环链表类型定义如下：

typedef struct BiNode {

    ElemType       data;

    int            freq; // 2.38题用

    struct BiNode *prev,

                  *next;

} BiNode, *BiLinkList;

  

void ReverseEven(BiLinkList &L)

{ BiLinkList p,q,r,s;

  p=L->next;     //p为第一个结点

  s=p->next;     //s为第二个结点

  q=s->next;     //q为第三个结点

  r=L->prev;     //r为最后一个结点

  if(s==L||q==L) L=L;    //如果表中只有一个或两个结点，则表不变

  else

  {  if(q==r)      //表中有三个结点

      {p->next=q;    //第一个指向第三个

       q->next=s;    //第三个指向第二个

       s->next=L;    //第二个指向头结点

       q->prev=p;    //q的前驱结点是p

       L->prev=s;     //L的前驱结点是s

       s->prev=q;     //s的前驱结点是q

      }

     else                   //表中三个结点以上

     {

       while(s!=r&&p!=r)

       {p->next=q;

        q->prev=p;        

        p=q;            //将p移向下一个结点 

        q=p->next->next;

        s->next=r->next;

        r->next->prev=s;

        r->next=s;      //将第二个结点变成最后一个节点

        s->prev=r;      //原第二个节点前驱结点是原最后一个结点  

        s=p->next;     //s始终为p的下一个结点，然后循环

       }

     }

 

  }

}

2.39③  试对稀疏多项式Pn(x)采用存储量同多项式项

数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为

给定值），并分析你的算法的时间复杂度。

实现下列函数：

float Evaluate(SqPoly pn, float x);

多项式的顺序存储结构:

typedef struct {

   int  coef;

   int  exp;

} PolyTerm;

typedef struct {

   PolyTerm *data;

   int       length;

} SqPoly;

float Evaluate(SqPoly pn, float x)

{ int i,j;

  float p=1,s=0;    

  for(i=0;i<pn.length;i++)

   { p=1;

     for(j=pn.data[i].exp;j>0;j--) p=p*x;  //计算指数项

     s=s+pn.data[i].coef*p;         //每加一项后的值

    }  

  return s;   

}

◆2.41②  试以循环链表作稀疏多项式的存储结构，

编写求其导函数的算法，要求利用原多项式中的结

点空间存放其导函数（多项式），同时释放所有无

用（被删）结点。

实现下列函数：

void Difference(LinkedPoly &pa);

链式多项式的类型定义：

typedef struct PolyNode {

    int  coef;

    int  exp;

    struct PolyNode *next;

} PolyNode, *PolyLink;  // 多项式元素（项）结点类型

typedef PolyLink LinkedPoly; // 链式多项式

void Difference(LinkedPoly &pa)

{  LinkedPoly p,q;

   p=pa->next;        //标记第一个结点

   if(p->exp==0)           //如果第一项的指数为0，则要把这项删除

   { q=p;

     p=p->next;

     pa->next=p;      

     free(q);

   }

   while(p!=pa)              //当p不等于头结点时循环

   {p->coef=p->coef*p->exp;  //每一项的系数变成原来系数与指数的乘积

    p->exp--;                //指数减1

    p=p->next;

   } 

}