◆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
{ElemType *p;
for(p=&L.elem[L.length-1];*p>x;--p)
   *(p+1)=*p;
   *(p+1)=x;
   ++L.length;

}

 

◆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'的首元，则AB。试写一个比
较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)
// 比较顺序表A和B,
//   返回'<', 若A
//       '=', 若A=B;
//       '>', 若A>B
{ int i;
for(i=1;i<=A.length&&i<=B.length;i++)
    if(A.elem[i]!=B.elem[i])
      return A.elem[i]>B.elem[i]?'>':'<';
  if(A.length==B.length) return '=';
  return A.length>B.length?'>':'<';

}

 

◆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'
{struct LNode *p; 
for(p=L->next;p&&p->data!=x;p=p->next);
  return p;

}

◆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'
{ struct LNode *p;
  int x=0;
  for(p=L;p->next;p=p->next,x++);
  return x;

}

 

◆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)
// la和lb分别指向两个单链表中第一个结点，        */
{LNode *p,*q,*r,*t;
  int m;
  p=la;
  t=NULL;
  q=lb;
  m=1;
  if(i==0||j==0||len==0)return ERROR;
  if(i==1&&j==1&&len==1){la=p->next;p->next=q;lb=p;return OK;}
  else{
  while(p&&m
    {t=p;
     p=p->next;
     m++;
     }
  if(!p)return ERROR;
  r=p;
  for(m=1;r&&mnext;
    if(r==NULL)return ERROR;
  if(i==1){la=r->next;}
  else {t->next=r->next;}
   if(j==1){r->next=lb;lb=p;}
  for(m=1;mnext!=NULL;m++)q=q->next;
  if(q==NULL)return ERROR;
  r->next=q->next;
  q->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)
{   struct LNode *p,*q; p=L;
  while(p->next->data<=mink) p=p->next;
  if(p->next)  
  {
    q=p->next;
    while(q->datanext;
    p->next=q;
  }

}

 

 

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

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

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

 

void Purge(LinkList &L)
{LNode *p,*q;
  p=L->next;
  while(p->next!=NULL)
     {
     if(p->data==p->next->data)
     {q=p->next;
     p->next=p->next->next;
     free(q);
     }
     else p=p->next;
    
     }

}

 

◆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 i,j=L.length-1;
 for(i=0;i
  {L.elem[i]+=L.elem[j-i];
  L.elem[j-i]=L.elem[i]-L.elem[j-i];
  L.elem[i]=L.elem[i]-L.elem[j-i];}
}
 

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

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

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

 

 

void Inverse(LinkList &L)
{ struct LNode *p,*q,*s;
p=L->next;q=p->next;s=q->next;p->next=NULL;
  while(s->next)
  {
    q->next=p;p=q;
    q=s;s=s->next;
  }
  q->next=p;s->next=q;L->next=s;

}

 

 

◆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)
{ struct LNode *p,*q,*s,*t;
p=ha->next;q=hb->next;hc=ha;
  while(p&&q)
  {
    s=p->next;p->next=q;
    if(s)
    {
      t=q->next;q->next=s;
    }
    p=s;q=t;
  }

}

 

◆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)
{ struct LNode *p,*q,*pc,*s;
 p=ha->next;q=hb->next;
  pc=(LNode*)malloc(sizeof(LNode));
 hc=pc;
  while(p&&q)
  {
    if(p->datadata) p=p->next;
    else if(p->data>q->data) q=q->next;
    else
    {
      s=(LNode*)malloc(sizeof(LNode));
      s->data=p->data;
      pc->next=s;pc=s;
      p=p->next;q=q->next;
    }
  }

 

}

 

 

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

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

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

 

 

ElemType DeleteNode(LinkList s)
{ LNode *p,*q;
   p=s;
   while(p->next->next!=s)p=p->next;
   q=p->next;
   p->next=s;      
   return (q->data);

}
 

◆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)
{ struct BiNode *p;
 for(p=CL;!p->next->prev;p=p->next) p->next->prev=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)
{  LNode *p,*q,*r,*s,*t;
 lc=(LinkList)malloc(sizeof(LNode));
 ld=(LinkList)malloc(sizeof(LNode));
 lo=(LinkList)malloc(sizeof(LNode));
 p=lc;
 q=ld;
 r=lo;
 
 for(t=ll->next;t;t=t->next)
 {if(t->data>='A'&&t->data<='Z'||t->data>='a'&&t->data<='z')
  {s=(LinkList)malloc(sizeof(LNode));
   p->next=s;
   s->data=t->data;
   p=p->next;
  }
 else
   {if(t->data>='0'&&t->data<='9')
    {s=(LinkList)malloc(sizeof(LNode));
    q->next=s;
    s->data=t->data;
    q=q->next;
    }
    else
    {s=(LinkList)malloc(sizeof(LNode));
     r->next=s;
     s->data=t->data;
     r=r->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)
{BiNode *p,*q,*r,*s;
  p=L->next;
  s=p->next;
  q=p->next->next;
  r=L->prev;
  if(q==L);
  else
  {  if(q==r)
  {p->next=q;
   q->prev=p;
   s->next=r->next;
   r->next->prev=s;  
   r->next=s;
   s->prev=r;
   }
  else
  {
  while(s!=r&&p!=r)
  {
   q->prev=p;
   p->next=q;
   p=q;
   q=p->next->next;
   s->next=r->next;
   r->next->prev=s;  
   r->next=s;
   s->prev=r;
   s=p->next;
  }
 
  }
 
  }
 
}

 

◆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)
{ float sum,xp;
  int ex;
 PolyTerm *q;
  xp=1;q=pn.data;
  sum=0;ex=0;
  while(q->coef)
  {
    while(exexp) xp*=x;
    sum+=q->coef*xp;
    q++;
  }
  return sum;

}

 

◆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)
{PolyNode *p;
 p=pa->next;
  if(!p->exp)
  {
    pa->next=p->next;p=p->next;
  }
  while(p!=pa)
  {
    p->coef*=p->exp--;
    p=p->next;
  }

}