数据结构.txt

里面介绍的是严蔚敏《数据结构(c语言版)习题集》第二章答案

你是第22位浏览者 发布日期:2004-10-20 
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

Status  InsertOrderList(SqList &a,ElemType x)
{
	if (a.length == a.listsize) return (OVERFLOW);
	ELSE {
		i= a.length - 1;
		while (i>=0 &&x<a.elem[i]) i--;
		for(j=a.length-1;j>=i+1;j--)
			a.elem[j+1]=a.elem[j];
		a.elem[i+1]=x;
		a.length++;
		return OK;
		}
}
　

2.12 设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A＇和B＇分别为A和B中除去最大共同前缀后的子表。若A＇=B＇=空表，则A=B；若A＇=空表，而B＇≠空表，或者两者均不为空表，且A＇的首元小于B＇的首元，则A<B；否则A>B。试写一个比较A，B大小的算法。

int Compare-List(SqList a, SqList b){

  //a,b为顺序表，若a<b时，返回-1；a=b时，返回0；a>b时，返回1

  i=0;

  while (i<=a.length-1) && (i<=b.length-1) && (a.elem[i]=b.elem[i]) ++i;

  switch {

    case i=a.length && i=b.length : return 0; break;

    case (i=a.length && i<=b.length-1)

         ||(i<=a.length-1 && i<=b.length-1 && a.elem[i]<b.elem[i]) : return -1;break;

    default : return 1;

  }

}//Compare-List

　

2.19
status del-l(LinkList &la, int mink, int maxk){
  //la为带头结点的单链表的头指针，单链表中的结点以值递增有序排列

  //本算法删除表中所有值大于mink且小于maxk的元素，mink<maxk
  if (mink>=maxk) return ERROR
  p=la;
  while (p->next<>NULL && p->next->data<=mink) p=p->next;
  q=p;
  while (q->next<>NULL && q->next->data<maxk) q=q->next ;
  q=q->next;
  p1=p->next;
  while (p1<>q) {q1=p1; p1=p1->next; free(q1);}
  p->next=q;
}//del-l

2.21 
LinkList priou(LinkList la, LinkList q1){
  //返回指向单链表la中结点的指针p1，p1->next=q1
  p1=la;
  while (p1->next!=q1) p1=p1->next;
  return p1;
}//priou

void Reverse-List-l(LinkList &la) {
  //就地逆置单链表la（算法1）
  if (!la->next) return;
  p=la->next; q=priou(la, NULL);
  while (p!=q) {
    p->data〈-〉q->data;
    if (p=q) return;
    q=priou(la, q);
  }
}//Reverse-List-l

void Reverse-List-l(LinkList &la) {
  //就地逆置单链表la（算法2）
  p=priou(la, NULL); last=p;
  pre=priou(la,p);
  while (pre!=la) {
    p->next=pre;
    p=pre;
    pre=priou(la,p);
  }
  p->next=NULL;
  la->next=last;
}//Reverse-List-l

void Reverse-List-l(LinkList &la) {
  //就地逆置单链表la（算法3）
  if (!la->next) return;
  pre=la->next;
  if (!pre->next) return;
  p=pre->next; pre->next=NULL;
  next=p->next;
  while (p) {
    p->next=pre;
    pre=p;
    p=next;
    if (p) next=p->next;
  }
  la->next=pre;
  return;
}//Reverse-List-l

void Reverse-List-l(LinkList &la) {
  //就地逆置单链表la（算法4）
  p=la->next;
  if (!p || !p->next) return;
  pn=p->next; p->next=NULL;
  while (pn) {
    p=pn; pn=pn->next;
    p->next=la->next; la->next=p;
  }
  return;
}//Reverse-List-l

2.24
void MergeList(LinkList &a, LinkList &b, LinkList &c) {
  //已知单链表a和b的元素按值递增有序排列
  //归并a和b得到新的单链表c，c的元素按值递减有序
  c=a; p=a->next; q=b->next; c->next=NULL;
  while (p && q) 
    if (p->data<q->data) {
      pn=p->next; p->next=c->next;   
      c->next=p; p=pn; 
    }
    else {
      qn=q->next; q->next=c->next;
      c->next=q; q=qn;
    }
  while (p) {pn=p->next; p->next=c->next; c->next=p; p=pn;} 
  while (q) {qn=q->next; q->next=c->next; c->next=q; q=qn;}
  free(b);
}//MergeList

2.33
void CutApart-LinkList(LinkList &l, LinkList la, LinkList lb, LinkList lc){
  //单链表l中的元素含有三类字符：字母、数字和其它字符
  //本算法将l分割为la、lb和lc三个循环链表，它们分别只含字母、数字和其它字符
  la=(LinkList)malloc(sizeof(LNode)); la->next=la;
  lb=(LinkList)malloc(sizeof(LNode)); lb->next=lb;
  lc=(LinkList)malloc(sizeof(LNode)); lc->next=lc;
  pn=l->next;
  while (pn){
    p=pn; pn=pn->next;
    switch {
      case (＇a＇<=p->data && p->data<=＇z＇)
           ||(＇A＇<=p->data && p->data<=＇Z＇) : p->next=la->next; la->next=p; break; 
      case (＇0＇<=p->data && p->data<=＇9＇) : p->next=lb->next; lb->next=p; break;
      default : p->next=lc->next; lc->next=p;
    }//switch
  }//while
  free(l);
}//CutApart-LinkList

2.39
typedef struct {
  float coef;
  int expn;
}*Poly, ElemType;

float Polynomial(Poly &p, int m, float x0){
  //多项式p的顺序存储结构中依次存放有c1,e1,c2,e2,...,cm,em
  //x0为给定值，本算法计算pn(x0)的值
  x=x0^p[0].expn;
  pn=p[0].coef*x;
  for (i=1; i<=m; ++i){
     x=x*x0^(p[i].expn-p[i-1].expn);
     pn=pn+p[i].coef*x;
  }
  retrun pn;
}//Polynomial

　

(以下内容来自http://bbs.kaoyan.com) 
第二章 线性表

2.10 

Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
  if(i<1||k<0||i+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)    //如果还有比mink更大的元素
  {
    q=p->next;
    while(q->data<maxk) {q1=q;q=q->next;free(q1);} //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) q=q->next;
      p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
    }
  }//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;A->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; //pa和pb分别指向A,B的当前元素
  while(pa&&pb)
  {
    if(pa->data<pb->data)
    {
      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;
  }
  while(pa)
  {
    q=pa->next;pa->next=pc;pc=pa;pa=q; //插入A中余下的元素
  }
  while(pb)
  {
    q=pb->next;pb->next=pc;pc=pb;pb=q; //插入B中余下的元素
  }
  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])