数据结构第二章习题

int  compare (Sqlist A,Sqlist B)

{  //返回值为-1，A中的单词在前，返回值为1，B中的单词在前。

j=0;   while(j{  if(A.elem[j]B.elem[j])  return 1;    else j++; }

if(A.lenght>B.length)  return 1;  else  return -1;

}

2.6 顺序表的就地逆置

void Invert_sq(Sqlist &A)

{

    for(i=0;i{

    K=A.elem[i];   A.elem[i]=A.elem[A.length-i-1];    A.elem[A.length-i-1]=k;   }  }

2.7  ha和hb两个指针，链表长度为m，n。将他们链接到一起。

  void Cat_LinkList(LinkList ha,LinkList hb,LinkList &hc)

{

    If(m{   P=ha;    while(p->next) p=p->next; //指针p指向ha的最后一个结点

    P->next=hb;   //将hb连接在ha后

    hc=ha;

}

Else

{  P=hb;    While(p->next) p=p->next; //指针p指向hb的最后一个结点

    P->next=ha; //将ha连接在hb后

    hc=hb;

}

}   //时间复杂度：O(min(m,n))

2.8

void Union_Link(LinkList ha,LinkList hb,LinkList & hc)

{   Pa=ha;  pb=hb;    I f(!pa)  hc=hb;  //若ha为空链表   else  If (!pb)  hc=ha;  //若hb为空

else

{   while(pa->next && pb)

{   hb=hb->next; //删除hb中第一个结点，头指针hb后移

    pb->next=pa->next;   pa->next=pb;    pa=pa->next;  pa=pa->next;   pb=hb;  

}

If (!pa->next) pa->next=pb; //若链表hb长度大于ha，则将hb中剩下的结点直接连接在ha后

hc=ha;  //新链表头指针

}}

2.9一个线表表示的线性表中有3累字符的数据元素。将他分割为3个循环链表

void Seg_LinkList(LinkList &L, LinkList &La,LinkList &Lb, LinkList &Lc)

{//   

    La=(ElemType*)malloc(sizeof(Lnode));//创建头结点

    Lb=(ElemType*)malloc(sizeof(Lnode));     Lc=(ElemType*)malloc(sizeof(Lnode));

pa=La;  pb=Lb;  pc=Lc;  pa->next=NULL; pb->next=NULL; pc->next =NULL;  

P=L->next;  free(L);    L=p;  while(p)

    {    L=L->next; //从链表中撤离第一个结点，此时头指针后移

if(p->data为数字)

{  p->next=pa->next; pa->next=p;   pa=pa->next;  }

else if(p->data为字母)

{    p->next=pb->next;    pb->next=p;    pb=pb->next; }

else 

{ p->next=pc->next; pc->next=p;    pc=pc->next;    p=L;  //指针p指向L的第一个结点    }

//构建三个循环链表

pa->next=La;   pb->next=Lb;  pc->next=Lc;

}

2.10以待头结点的双向循环链表表示线性表l，时间复杂度n

void Seg2_Link(LinkList &L)

{//为了保证算法的时间复杂度为O(n)，可从尾结点开始操作，每隔一个结点，将其前驱删除，并插入到最后。用指针p1从第n个结点开始往前移动，删除其前驱，用p2往后移动，在p2后面插入结点。

//若结点为偶数个，删除的第一个结点应为第n-2个，若结点数为奇数个，删除的第一个结点为第n-1个，因此要先求结点数

q=L->next;  k=0; 

while(q->next!=L) //循环链表判断尾结点的条件

{ k++; q=q->next;}

    if(k%2) p1=p2=L->prior;

    else { p1=L->prior->prior; p2=L->prior;}

    while(p1!=L)  //p1从后往前移动，直到移动到头结点为止

    { q=p1->prior;    q->prior->next=p1;    p1->prior=q->prior;

     q->next=p2->next; p2->next=q;

q->prior=p2; q->next->prior=q;   p1=p1->prior;  p2=p2->next;  } }

2.11有序表中的元素递增排列。以单链表存储。高效算法。Mink   maxk

void delete_Link(LinkList &L,Elemtype mink,Elemtype maxk)

{   p=L;  //p指向头结点

    while(p->next->data<=mink)    p=p->next;   q=p->next;    while(q->data    {     p->next=q->next;          free(q);     q=p->next; }}

2.12

 void union_Link(LinkList LA,LinkList LB,LinkList &LC)

{    pa=LA->next; pb=LB->next;   while(LA->next!=NULL &&LB->next!=NULL)

    {  if(pa->data<=pb->data)

        {   LA->next=pa->next;   pa->next=LC->next;  LC->next=pa; }

else

{  LB->next=pb->next; pb->next=LC->next; LC->next=pb;  }

}

while(LA->next!=NULL) //如果LB中结点已经全部处理完，现在只需将LA中结点依次插入到LC中

{   LA->next=pa->next;    pa->next=LC->next;  LC->next=pa;  }

while(LB->next!=NULL) //如果LA中结点已经全部处理完，现在只需将LB中结点依次插入到LC中

{   LB>next=pb->next;       pb>next=LC->next;  LC->next=pb;   }  }

2.13有两个元素递增排列的有序表a和b。构造c为交集元素。

void Union_Sq(SqList LA, SqList LB, SqList &LC)

{   i=0;j=0; k=1; 

LC.elem[0]=-9999; //LC中第一个元素空间不用，为了操作方便，可设一个顺序表中不存在的值

while(i{

if(LA.elem[i]<=LB.emem[j])   //如果LA中元素较小，将其插入到LC中

if(LA.elem[i]!=LC.elem[k-1])  //如果LA中当前元素与LC中K前一个元素不相等，则插入当前元素

{ LC.elem[k++]=LA.elem[i++]; LC.length++;}

else i++;

else   //如果LB中元素较小，将其插入到LC中

if(LB.elem[j]!=LC.elem[k-1]) //如果LB中当前元素与LC中K前一个元素不相等，则插入当前元素

{ LC.elem[k++]=LB.elem[j++]; LC.length++;}

else j++;

}

while(iif(LA.elem[i]!=LC.elem[k-1])

{ LC.elem[k++]=LA.elem[i++]; LC.length++;}

while(jif(LB.elem[j]!=LC.elem[k-1])

{ LC.elem[k++]=LB.elem[j++]; LC.length++;}

}