（02）数据结构题解－线性表

核心提示：第二章 线性表 2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{ if(i<1k<0i+k-1>a.length) return INFEASIBLE; for(count=1;i+count-1<=a.lengt

　　　　　　　　　　　　　　　　　　　　第二章 线性表
2.10
Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
  if(i<1k<0i+k-1>a.length) return INFEASIBLE;
  for(count=1;i+count-1<=a.length-k;count++) //注重循环结束的条件
　  a.elem[i+count-1]=a.elem[i+count+k-1];
  a.length-=k;
  return OK;
}//DeleteK
2.11
Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
  if(va.length+1>va.listsize) return ERROR;
  va.length++;
  for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
　  va.elem[i+1]=va.elem[i];
  va.elem[i+1]=x;
  return OK;
}//Insert_SqList
2.12
int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B
{
  for(i=1;A.elem[i]B.elem[i];i++)
　  if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];
  return 0;
}//ListComp
2.13
LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针
{
  for(p=l->next;p&&p->data!=x;p=p->next);
  return p;
}//Locate
2.14
int Length(LinkList L)//求链表的长度
{
  for(k=0,p=L;p->next;p=p->next,k++);
  return k;
}//Length
2.15
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc
{
  hc=ha;p=ha;
  while(p->next) p=p->next;
  p->next=hb;
}//ListConcat
2.16
见书后答案.
2.17
Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
{
  p=L;q=(LinkList*)malloc(sizeof(LNode));
  q.data=b;
  if(i==1)
  {
　  q.next=p;L=q; //插入在链表头部
  }
  else
  {
　  while(--i>1) p=p->next;
　  q->next=p->next;p->next=q; //插入在第i个元素的位置
  }
}//Insert
2.18
Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素
{
  if(i==1) L=L->next; //删除第一个元素
  else
  {
　  p=L;
　  while(--i>1) p=p->next;
　  p->next=p->next->next; //删除第i个元素
  }
}//Delete
2.19
Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
{
  p=L;
  while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素
  if(p->next)　  file://假如还有比mink更大的元素
  {
　  q=p->next;
　  while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素
　  p->next=q;
  }
}//Delete_Between
2.20
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
{
  p=L->next;q=p->next; //p,q指向相邻两元素
  while(p->next)
  {
　  if(p->data!=q->data)
　  {
　　  p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
　  }
　  else
　  {
　　  while(q->data==p->data)
　 {
　　 free(q);
　　 q=q->next;
　 }
　　  p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
　  }//else
  }//while
}//Delete_Equal
2.21
void reverse(SqList &A)//顺序表的就地逆置
{
  for(i=1,j=A.length;i<j;i++,j--)
　  A.elem[i]<->A.elem[j];
}//reverse
2.22
void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
{
  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; //把L的元素逐个插入新表表头
  }
  q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
{
  p=A->next;q=B->next;C=A;
  while(p&&q)
  {
　  s=p->next;p->next=q; //将B的元素插入
　  if(s)
　  {
　　  t=q->next;q->next=s; //如A非空,将A的元素插入
　  }
　  p=s;q=t;
  }//while
}//merge1
2.24
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
{
  pa=A->next;pb=B->next;PRe=NULL; file://pa和pb分别指向A,B的当前元素
  while(papb)
  {
　  if(pa->data<pb->data!pb)
　  {
　　  pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
　  }
　  else
　  {
　　  pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
　  }
　  pre=pc;
  }
  C=A;A->next=pc; //构造新表头
}//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
{
  i=1;j=1;k=0;
  while(A.elem[i]&&B.elem[j])
  {
　  if(A.elem[i]<B.elem[j]) i++;
　  if(A.elem[i]>B.elem[j]) j++;
　  if(A.elem[i]==B.elem[j])
　  {
　　  C.elem[++k]=A.elem[i]; //当发现了一个